7.2　過已知點(diǎn)Hough變換的直線檢測［2］

以上介紹的Hough變換直線檢測方法是一種窮盡式搜索，計(jì)算量和空間復(fù)雜度都很高，很難在實(shí)時(shí)性要求較高的領(lǐng)域內(nèi)應(yīng)用。為了解決這一問題，多年來許多學(xué)者致力于Hough變換算法的高速化研究。例如，將隨機(jī)過程、模糊理論等與Hough變換相結(jié)合，或者將分層迭代、級(jí)聯(lián)的思想引入到Hough變換過程中，大大提高了Hough變換的效率。本節(jié)以過已知點(diǎn)的改進(jìn)Hough變換為例，介紹一種直線的快速檢測方法。

過已知點(diǎn)的改進(jìn)Hough變換方法，是在Hough變換基本原理的基礎(chǔ)上，將逐點(diǎn)向整個(gè)參數(shù)空間的投票轉(zhuǎn)化為僅向一個(gè)“已知點(diǎn)”參數(shù)空間投票的快速直線檢測方法。其基本思想是：首先找到屬于直線上的一個(gè)點(diǎn)，將這個(gè)已知點(diǎn)p0的坐標(biāo)定義為（x0，y0），將通過p0的直線斜率定義為m，則坐標(biāo)和斜率的關(guān)系可用下式表示：

（y-y0）=m（x-x0）　　 （7.3）

定義區(qū)域內(nèi)目標(biāo)像素pi的坐標(biāo)為（xi，yi），（0≤i<n，n為區(qū)域內(nèi)目標(biāo)像素總數(shù)），則pi點(diǎn)與p0點(diǎn)之間連線的斜率mi可用下式表示：

mi=（yi-y0）/（xi-x0）　　 （7.4）

將斜率值映射到一組累加器上，每求得一個(gè)斜率，將使其對(duì)應(yīng)的累加器的值加1，因?yàn)橥粭l直線上的點(diǎn)求得的斜率一致，所以當(dāng)目標(biāo)區(qū)域中有直線成分時(shí)，其對(duì)應(yīng)的累加器出現(xiàn)局部最大值，將該值所對(duì)應(yīng)的斜率作為所求直線的斜率。

當(dāng)xi=x0時(shí)，mi為無窮大，這時(shí)式（7.4）不成立。為了避免這一現(xiàn)象，當(dāng)xi=x0時(shí)，令mi=2，當(dāng)mi>1或mi<-1時(shí)，采用式（7.5）的計(jì)算值替代mi，這樣無限域的mi被限定在了（-1，3）的有限范圍內(nèi)。在實(shí)際操作時(shí)設(shè)定斜率區(qū)間為［-2，4］。

m'i=1/mi+2　　 （7.5）

過已知點(diǎn)Hough變換的具體步驟如下：

①將設(shè)定的斜率區(qū)間等分為10個(gè)子區(qū)間，即每個(gè)子區(qū)間的寬度為設(shè)定斜率區(qū)間寬度的1/10；

②為每個(gè)子區(qū)間設(shè)置一個(gè)累加器nj（1≤j≤10）；

③初始化每個(gè)累加器的值為0，即nj=0；

④從上到下，從左到右逐點(diǎn)掃描圖像，遇到目標(biāo)像素時(shí)，由式（7.4）及式（7.5）計(jì)算其與已知點(diǎn)p0之間的斜率m，m值屬于哪個(gè)子區(qū)間就將哪個(gè)子區(qū)間累加器的值加1；

⑤當(dāng)掃描完全部處理區(qū)域之后，將累加器的值為最大的子區(qū)間及其相鄰的兩個(gè)子區(qū)間（共3個(gè)子區(qū)間）作為下一次投票的斜率區(qū)間，重復(fù)上述①～④步，直到斜率區(qū)間的寬度小于設(shè)定斜率檢測精度為止，例如，m=0.05，這時(shí)將累加值為最大的子區(qū)間的中間值經(jīng)過式（7.5）設(shè)定條件的逆變換后作為所求直線的斜率值。

過已知點(diǎn)Hough變換的直線檢測過程如圖7.3所示。

圖7.4為過已知點(diǎn)Hough變換的直線檢測結(jié)果，圖中檢出直線上的“+”表示已知點(diǎn)的位置，處理時(shí)間為35ms。也就是說，對(duì)于該圖，在同等條件下，過已知點(diǎn)Hough變換的處理速度比一般Hough變換快將近20倍。

利用過已知點(diǎn)Hough變換的直線檢測方法，其關(guān)鍵問題是如何正確地選擇已知點(diǎn)。在實(shí)際操作中，一般選擇容易獲取的特征點(diǎn)為已知點(diǎn)，例如，某個(gè)區(qū)域內(nèi)的像素分布中心等。

在實(shí)際應(yīng)用中，往往通過對(duì)檢測對(duì)象特征的分析，獲取少量的目標(biāo)像素點(diǎn)，通過減少處理對(duì)象來提高Hough變換的處理速度。檢測對(duì)象的特征一般采用亮度或者顏色特征。例如，在檢測公路車道線時(shí)，可以通過分析車道線的亮度或者某個(gè)顏色分量，首先找出車道線在每條橫向掃描線上的分布中心點(diǎn)，然后僅對(duì)這些中心點(diǎn)進(jìn)行Hough變換，就可以極大地提高處理速度。在進(jìn)行特征點(diǎn)的提取時(shí)，某些特征點(diǎn)可能會(huì)出現(xiàn)誤差，但是由于Hough變換的統(tǒng)計(jì)學(xué)特性，部分誤差不會(huì)影響最終的檢測結(jié)果。