7.1　傳統(tǒng)Hough變換的直線檢測［1］

保羅·哈夫于1962年提出了Hough變換法，并申請了專利。該方法將圖像空間中的檢測問題轉(zhuǎn)換到參數(shù)空間，通過在參數(shù)空間里進(jìn)行簡單的累加統(tǒng)計完成檢測任務(wù)，并用大多數(shù)邊界點滿足的某種參數(shù)形式來描述圖像的區(qū)域邊界曲線。這種方法對于被噪聲干擾或間斷區(qū)域邊界的圖像具有良好的容錯性。Hough變換最初主要應(yīng)用于檢測圖像空間中的直線，最早的直線變換是在兩個笛卡兒坐標(biāo)系之間進(jìn)行的，這給檢測斜率無窮大的直線帶來了困難。1972年，杜達(dá)（Duda）將變換形式進(jìn)行了轉(zhuǎn)化，將數(shù)據(jù)空間中的點變換為ρ-θ參數(shù)空間中的曲線，改善了其檢測直線的性能。該方法被不斷地研究和發(fā)展，在圖像分析、計算機視覺、模式識別等領(lǐng)域得到了非常廣泛的應(yīng)用，已經(jīng)成為模式識別的一種重要工具。

直線的方程可以用式（7.1）來表示。

y=kx+b　　 （7.1）

其中，k和b分別是斜率和截距。過x-y平面上的某一點（x0，y0）的所有直線的參數(shù)都滿足方程y0=kx0+b。即過x-y平面上點（x0，y0）的一族直線在參數(shù)k-b平面上對應(yīng)于一條直線。

由于式（7.1）形式的直線方程無法表示x=c（c為常數(shù)）形式的直線（這時候直線的斜率為無窮大），所以在實際應(yīng)用中，一般采用式（7.2）的極坐標(biāo)參數(shù)方程的形式。

ρ=xcosθ+ysinθ　　 （7.2）

其中，ρ為原點到直線的垂直距離，θ為ρ與x軸的夾角（如圖7.1所示）。

根據(jù)式（7.2），直線上不同的點在參數(shù)空間中被變換為一族相交于p點的正弦曲線，因此可以通過檢測參數(shù)空間中的局部最大值p點，來實現(xiàn)x-y坐標(biāo)系中直線的檢測。

一般Hough變換的步驟如下。

①將參數(shù)空間量化成m×n（m為θ的等份數(shù)，n為ρ的等份數(shù)）個單元，并設(shè)置累加器矩陣Q［m×n］；

②給參數(shù)空間中的每個單元分配一個累加器Q（θi，pj）（0<i<m-1， 0<j<n-1），并把累加器的初始值置為零；

③將直角坐標(biāo)系中的各點（xk，yk）（k=1，2，…，s，s為直角坐標(biāo)系中的點數(shù)）代入式（7.2），然后將θ0～θm-1也都代入其中，分別計算出相應(yīng)的值pj；

④在參數(shù)空間中，找到每一個（θi，pj）所對應(yīng)的單元，并將該單元的累加器加1，即Q（θi，pj）=Q（θi，pj）+1，對該單元進(jìn)行一次投票；

⑤待x-y坐標(biāo)系中的所有點都進(jìn)行運算之后，檢查參數(shù)空間的累加器，必有一個出現(xiàn)最大值，這個累加器對應(yīng)單元的參數(shù)值作為所求直線的參數(shù)輸出。

由以上步驟看出，Hough變換的具體實現(xiàn)是利用表決方法，即曲線上的每一點可以表決若干參數(shù)組合，贏得多數(shù)表決的參數(shù)就是勝者。累加器陣列的峰值就是表征一條直線的參數(shù)。Hough變換的這種基本策略還可以推廣到平面曲線的檢測。

圖7.2表示了一個二值圖像經(jīng)過傳統(tǒng)Hough變換的直線檢測結(jié)果。圖像大小為512×480像素，運算時間為652ms（CPU速度為1GHz）。

Hough變換是一種全局性的檢測方法，具有極佳的抗干擾能力，可以很好地抑制數(shù)據(jù)點集中存在的干擾，同時還可以將數(shù)據(jù)點集擬合成多條直線。但是，Hough變換的精度不容易控制，因此，不適合對擬合直線的精度要求較高的實際問題。同時，它所要求的巨大計算量使其處理速度很慢，從而限制了它在實時性要求很高的領(lǐng)域的應(yīng)用。