Rocky的部落格

http://www.cnblogs.com/cfantaisie/archive/2011/06/05/2073343.html

Hough變換用來在圖象中查找直線。它的原理很簡單：假設有一條與原點距離為s，方向角為θ的一條直線，直線上的每一點都滿足方程7.1：

 s = xcosθ + ysinθ

  可以利用這個變換找出圖中最長的直線，實現算法如下：

1．創建一個二維數組hDistAlpha，其中第一維表示距離s（計算可能出現的最大距離為，用來確定數組第二維的大小），第二維表示方向角θ（書上正好和我說的相反，但看了程序以後我更堅持自己的想法）。

2．創建一個二維數組Line，計算每條直線的上下兩個端點。

3．對圖像中的每個黑點，角度的變化范圍從00到1780(角度每次增加20 )，按方程(7.1)求出對應的距離s來，相應的數組元素[s][]加1，同時相應的填寫數組Line的內容。

4．所有的象素都算完後，找到數組元素中最大的，就是最長的那條直線。直線的端點可以在Line中找到。

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/tlovet1314/archive/2010/09/01/5856319.aspx

霍夫變換是圖像處理中識別幾何形狀的一種方法，在圖像處理中有著廣泛應用，霍夫變換不受圖形旋轉的影響，易於進行幾何圖形的快速變換。基於霍夫變換的改進方法也有很多，其中一個重要的方法是廣義霍夫變換，可以用來檢測任意形狀的曲線。

最簡單的霍夫變換是在圖像中識別直線。在平面直角坐標系(x-y)中，一條直線可以用方程

y = kx + b

表示。對於直線上一個確定的點(x₀,y₀)，有

y₀ = kx₀ + b

這表示參數平面(k-b)中的一條直線。因此，圖像中的一個點對應參數平面中的一條直線，圖像中的一條直線對應參數平面中的一個點。對圖像上所有的點作霍夫變換，最終所要檢測的直線對應的一定是參數平面中直線相交最多的那個點。這樣就在圖像中檢測出了直線。在實際應用中，直線通常采用參數方程

p = xcosθ + ysinθ.

類似的還有檢測線段、圓、圓弧、橢圓、矩形等的霍夫變換。

霍夫變換是圖像處理中從圖像中識別幾何形狀的基本方法之一，應用很廣泛，也有很多改
進算法。最基本的霍夫變換是從黑白圖像中檢測直線(線段)。
我們先看這樣一個問題：設已知一黑白圖像上畫了一條直線，要求出這條直線所在的位置
。我們知道，直線的方程可以用y=k*x+b 來表示，其中k和b是參數，分別是斜率和截距。過某一點
(x0,y0)的所有直線的參數都會滿足方程y0=kx0+b。即點(x0,y0)確定了一族直線。方程y0=kx0+b在
參數k--b平面上是一條直線，(你也可以是方程b=-x0*k+y0對應的直線)。這樣，圖像x--y平面上的
一個前景像素點就對應到參數平面上的一條直線。我們舉個例子說明解決前面那個問題的原理。設
圖像上的直線是y=x, 我們先取上面的三個點：A(0,0), B(1,1), C(22)。可以求出，過A點的直線
的參數要滿足方程b=0, 過B點的直線的參數要滿足方程1=k+b, 過C點的直線的參數要滿足方程
2=2k+b, 這三個方程就對應著參數平面上的三條直線，而這三條直線會相交於一點(k=1,b=0)。　同
理，原圖像上直線y=x上的其它點(如(3,3),(4,4)等)　對應參數平面上的直線也會通過點(k=1,b=0)
。這個性質就為我們解決問題提供了方法：

首先，我們初始化一塊緩沖區，對應於參數平面，將其所有數據置為0.

對於圖像上每一前景點，求出參數平面對應的直線，把這直線上的所有點的值都加１。

最後，找到參數平面上最大點的位置，這個位置就是原圖像上直線的參數。

上面就是霍夫變換的基本思想。就是把圖像平面上的點對應到參數平面上的線，最後通過
統計特性來解決問題。假如圖像平面上有兩條直線，那麼最終在參數平面上就會看到兩個峰值點，
依此類推。

在實際應用中，y=k*x+b形式的直線方程沒有辦法表示x=c形式的直線(這時候，直線的斜
率為無窮大)。所以實際應用中，是采用參數方程p=x*cos(theta)+y*sin(theta)。這樣，圖像平面
上的一個點就對應到參數p---theta平面上的一條曲線上。其它的還是一樣。

在看下面一個問題：我們要從一副圖像中檢測出半徑以知的圓形來。這個問題比前一個還
要直觀。我們可以取和圖像平面一樣的參數平面，以圖像上每一個前景點為圓心，以已知的半徑在
參數平面上畫圓，並把結果進行累加。最後找出參數平面上的峰值點，這個位置就對應了圖像上的
圓心。在這個問題裡，圖像平面上的每一點對應到參數平面上的一個圓。

把上面的問題改一下，假如我們不知道半徑的值，而要找出圖像上的圓來。這樣，一個辦
法是把參數平面擴大稱為三維空間。就是說，參數空間變為x--y--R三維，對應圓的圓心和半徑。
圖像平面上的每一點就對應於參數空間中每個半徑下的一個圓，這實際上是一個圓錐。最後當然還
是找參數空間中的峰值點。不過，這個方法顯然需要大量的內存，運行速度也會是很大問題。

有什麼更好的方法麼?我們前面假定的圖像都是黑白圖像(2值圖像)，實際上這些2值圖像
多是彩色或灰度圖像通過邊緣提取來的。我們前面提到過，圖像邊緣除了位置信息，還有方向信息
也很重要，這裡就用上了。根據圓的性質，圓的半徑一定在垂直於圓的切線的直線上，也就是說，
在圓上任意一點的法線上。這樣，解決上面的問題，我們仍采用2維的參數空間，對於圖像上的每
一前景點，加上它的方向信息，都可以確定出一條直線，圓的圓心就在這條直線上。這樣一來，問
題就會簡單了許多。

接下來還有許多類似的問題，如檢測出橢圓，正方形，長方形，圓弧等等。這些方法大都
類似，關鍵就是需要熟悉這些幾何形狀的數學性質。霍夫變換的應用是很廣泛的，比如我們要做一
個支票識別的任務，假設支票上肯定有一個紅顏色的方形印章，我們可以通過霍夫變換來對這個印
章進行快速定位，在配合其它手段進行其它處理。霍夫變換由於不受圖像旋轉的影響，所以很容易
的可以用來進行定位。

霍夫變換有許多改進方法，一個比較重要的概念是廣義霍夫變換，它是針對所有曲線的，
用處也很大。就是針對直線的霍夫變換也有很多改進算法，比如前面的方法我們沒有考慮圖像上的
這一直線上的點是否連續的問題，這些都要隨著應用的不同而有優化的方法。