基于投票約束的Hough 變換直線檢測(cè)算法

張喜民，詹海生，余奇穎

（1.陜西國(guó)際商貿(mào)學(xué)院信息工程學(xué)院，陜西西安 712046；2.西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710071）

基于機(jī)器視覺的精密測(cè)量技術(shù)已成為國(guó)內(nèi)外研究熱點(diǎn)[1-3]。自動(dòng)檢測(cè)圖像中零件直線邊緣是尺寸測(cè)量的重要環(huán)節(jié)，邊緣直線檢測(cè)的精度直接影響零件尺寸測(cè)量的精度。目前，直線檢測(cè)算法大部分都是基于Hough 變換技術(shù)，其具有對(duì)噪聲不敏感、穩(wěn)健性好、對(duì)遮擋易處理等優(yōu)點(diǎn)[4-9]。

標(biāo)準(zhǔn)Hough 變換直線檢測(cè)算法是在圖像的邊緣提取圖上實(shí)現(xiàn)的，因此，會(huì)依賴邊緣檢測(cè)算法的準(zhǔn)確性。對(duì)于有較高邊緣密度的圖像會(huì)出現(xiàn)大量錯(cuò)誤結(jié)果。同時(shí)，由于對(duì)每個(gè)邊緣像素點(diǎn)都需要計(jì)算參數(shù)，計(jì)算量較大。Hough 變換直線檢測(cè)算法的改進(jìn)主要體現(xiàn)在提高算法性能和提高檢測(cè)準(zhǔn)確度兩個(gè)方面，在提高算法性能方面，已有大量研究論文和應(yīng)用[9-13]，Mukhopadhyay等和Hassanein等對(duì)這些進(jìn)展進(jìn)行了詳細(xì)綜述[8]。而在提高直線檢測(cè)準(zhǔn)確率方面的研究成果相對(duì)較少，典型的有Lee 等提出了離散Hough 變換算法(DHT)，Chung 等在DHT 的基礎(chǔ)上進(jìn)一步提出了基于方向的離散Hough 變換算法(ODHT)[3]，這兩種算法采用多參數(shù)的離散Hough 變換，可提高直線檢測(cè)率，但多參數(shù)的引入導(dǎo)致了較大計(jì)算量；針對(duì)虛假直線、線段信息缺失等問題，Almazan 等提出的馬爾可夫鏈邊緣直線段檢測(cè)器算法，其能夠檢測(cè)到更為完整的直線段，但計(jì)算量較大[14]；王競(jìng)雪等對(duì)檢測(cè)得到的邊緣像素進(jìn)行編組[15-16]，先過濾獨(dú)立像素點(diǎn)和短邊緣，再對(duì)每一個(gè)邊緣組分別進(jìn)行Hough 變換，降低了邊緣組間干擾、提高了檢測(cè)準(zhǔn)確度；徐超等提出結(jié)合隨機(jī)抽樣一致性算法和模型預(yù)檢驗(yàn)的改進(jìn)隨機(jī)Hough 變換算法[17-18]，該算法通過對(duì)像素點(diǎn)進(jìn)行分組，計(jì)算相鄰像素點(diǎn)的梯度方向差分，降低了直線檢測(cè)過程中的誤檢情況，但計(jì)算量也較大。

在進(jìn)行工業(yè)生產(chǎn)線零件尺寸測(cè)量時(shí)，既要滿足精度要求又要保證算法的時(shí)間性能，上述算法為提高直線檢測(cè)精確度引入了較復(fù)雜的計(jì)算，降低了算法的時(shí)間性能，不能滿足生產(chǎn)要求。筆者在應(yīng)用Hough 變換、隨機(jī)Hough 變換對(duì)類矩形小插件進(jìn)行邊緣直線檢測(cè)時(shí)發(fā)現(xiàn)，由于邊角圓弧設(shè)計(jì)以及制造工藝等原因，小插件的棱有弧度，對(duì)采集圖像邊緣提取后，一條棱變成兩條相距很近的有弧度的邊緣線，這些邊緣線彎曲部分的像素點(diǎn)很容易在Hough 空間形成偽峰，偽峰值會(huì)對(duì)周圍的真峰值點(diǎn)產(chǎn)生抑制[3]，導(dǎo)致Hough 變換及其衍生算法直線檢測(cè)不準(zhǔn)確。為此，提出了基于投票約束的Hough 變換直線檢測(cè)算法，通過設(shè)計(jì)新的Hough 空間投票權(quán)重策略來抑制偽峰的產(chǎn)生，進(jìn)而提高直線檢測(cè)的精準(zhǔn)度。該方法引入的計(jì)算量小，在提高精準(zhǔn)度的同時(shí)基本不降低算法的時(shí)間性能。

1 算法設(shè)計(jì)

1.1 Hough變換直線檢測(cè)算法

Hough 變換是圖像處理中識(shí)別幾何形狀的方法，它利用圖像空間X-Y與Hough 參數(shù)空間ρ-θ的點(diǎn)與線的對(duì)偶性，把原始圖像中給定形狀的直線或曲線變換成Hough 參數(shù)空間的一個(gè)點(diǎn)。圖像空間中同一條直線或曲線上的多個(gè)點(diǎn)在Hough 參數(shù)空間中將成為為一個(gè)正弦曲線簇，且曲線簇相交于一點(diǎn)，稱該點(diǎn)為峰值點(diǎn)，如圖1 所示。通過檢測(cè)該峰值點(diǎn)，就可檢測(cè)對(duì)應(yīng)圖像空間中的一條直線或曲線。

圖1 Hough變換的點(diǎn)線對(duì)偶原理

若圖像空間X-Y中的點(diǎn)(x1,y1)、點(diǎn)(x2,y2)在直線L上，則它們都與Hough 參數(shù)空間ρ-θ中的一個(gè)峰值點(diǎn)相對(duì)應(yīng)，反之，參數(shù)空間ρ-θ中的一個(gè)峰值點(diǎn)就和圖像空間X-Y中的一條直線相對(duì)應(yīng)。Hough 變換直線檢測(cè)算法的過程如下：

1）設(shè)置正向夾角和法線距離的取值范圍[θmin,θmax]和[ρmin,ρmax]，將Hough 參數(shù)空間網(wǎng)格量化成M×N個(gè)單元(M為θ的等分?jǐn)?shù)，N為ρ的等分?jǐn)?shù))，并設(shè)置累加器矩陣Q[M×N]初始值為0；

2）對(duì)于圖像空間中的每個(gè)點(diǎn)(x,y)執(zhí)行步驟3）；

3）令s=(θmax-θmin)/M為步長(zhǎng)，對(duì)于0≤i

4）檢測(cè)累加器矩陣Q[M×N]中的極大值，獲取峰值點(diǎn)網(wǎng)格下標(biāo)[mH,nH]，由式（2）計(jì)算ρL和θL；

5）根據(jù)ρL和θL由式（3）計(jì)算圖像空間X-Y中直線L的參數(shù)：斜率p和截距q，并檢測(cè)到直線。

1.2 投票約束的Hough變換直線檢測(cè)算法

由于零件的棱本身是帶有弧度的，對(duì)應(yīng)到圖像中不存在完全理論上的直線。類矩形小零件在彎曲處產(chǎn)生的像素點(diǎn)很容易在Hough 空間形成偽峰，干擾直線檢測(cè)的精度。針對(duì)上述問題，該文提出通過設(shè)計(jì)新的Hough 空間投票權(quán)重策略來抑制偽峰的產(chǎn)生，提高直線檢測(cè)精度。

算法的投票策略：給邊緣上弧度較小的像素點(diǎn)一個(gè)較大的投票權(quán)重，而給弧度較大的非線性邊緣像素點(diǎn)一個(gè)較小的投票權(quán)重。算法具體實(shí)現(xiàn)過程如下：

1）對(duì)采集圖像采用3×3 模板進(jìn)行中值濾波，得到增強(qiáng)圖像；

2）應(yīng)用基于RANSAC 去離群點(diǎn)的SIFT 特征匹配算法[3]對(duì)增強(qiáng)圖像進(jìn)行圖像配準(zhǔn)變換，得到精準(zhǔn)的配準(zhǔn)圖像；

3）應(yīng)用最大化類間方差的方法(Otsu)，迭代求出灰度值t，將t與0.5×t分別作為高低閾值傳入Canny算子，提取配準(zhǔn)圖像邊緣得到二值圖像；

4）將Hough 參數(shù)空間網(wǎng)格量化成M×N個(gè)單元（M為θ的等分?jǐn)?shù)，N為ρ的等分?jǐn)?shù)），并設(shè)置累加器矩陣Q[M×N]的初始值全為0；

5）對(duì)于二值圖像空間中的每個(gè)點(diǎn)(x,y)執(zhí)行步驟6）、7）；

6）令s=π/M為步長(zhǎng)，對(duì)于0≤θ<π，用式（1）循環(huán)計(jì)算ρ，對(duì)ρ進(jìn)行量化，求取網(wǎng)格下標(biāo)j；

7）判定像素點(diǎn)(x,y)是否處于預(yù)設(shè)的高投票權(quán)區(qū)域，用式（4）計(jì)算二值圖像像素點(diǎn)的空間投票權(quán)，再用式（5）更新累加器矩陣Q；

8）檢測(cè)累加器矩陣Q[M×N]中的極大值，獲取峰值點(diǎn)所在矩陣的行列位置，再由式（2）計(jì)算ρL和θL；

9）根據(jù)ρL和θ L由式（3）計(jì)算圖像空間中直線的參數(shù)：斜率p和截距q，并檢測(cè)到零件的邊緣直線L。

2 實(shí)驗(yàn)與分析

2.1 實(shí)驗(yàn)系統(tǒng)組成

實(shí)驗(yàn)系統(tǒng)硬件由計(jì)算機(jī)、工業(yè)數(shù)碼相機(jī)、遠(yuǎn)心鏡頭、紅色環(huán)狀LED 光源、直流穩(wěn)壓電源、支架等組成，如圖2 所示。

圖2 實(shí)驗(yàn)系統(tǒng)硬件組成

實(shí)驗(yàn)系統(tǒng)中計(jì)算機(jī)配置：Intel(R) Core(TM) i7-9700K、4.90 GHz，8 GB DDR4 內(nèi)存，256 GB 固態(tài)硬盤；工業(yè)數(shù)碼相機(jī)為1 292×964 分辨率的單色CCD相機(jī)，采集到的圖像通過USB3.0 接口傳輸給計(jì)算機(jī)；遠(yuǎn)心鏡頭選用焦距固定、景深大的物方遠(yuǎn)心鏡頭，具有平行光輸出、畸變非常小的特點(diǎn)，以保證采集圖像的質(zhì)量；紅色環(huán)狀LED 光源向下均勻照射待檢測(cè)的零件，減少了外部光照的影響，以獲取低噪聲的清晰圖像，直流穩(wěn)壓電源為環(huán)形光源提供穩(wěn)定的+12 V。

實(shí)驗(yàn)系統(tǒng)軟件環(huán)境采用Windows7 64 位專業(yè)版操作系統(tǒng)；測(cè)量應(yīng)用軟件用C++語言開發(fā)，軟件開發(fā)環(huán)境采用Visual Studio 2015；支持庫采用MFC 類庫和計(jì)算機(jī)視覺庫OpenCV4.5.1。

2.2 直線檢測(cè)實(shí)驗(yàn)與分析

2.2.1 直線檢測(cè)實(shí)驗(yàn)結(jié)果

以手機(jī)尾插零件為檢測(cè)對(duì)象，任選取一幅采集圖像，分別用標(biāo)準(zhǔn)HT 算法、概率HT 算法和該文提出的算法進(jìn)行實(shí)驗(yàn)，Hough 變換的相關(guān)參數(shù)選取如下：斜率取值范圍為[0,180°]，截距的取值范圍為[0，1 000]，M為1 000，N為1 800；該文算法在確定投票權(quán)重時(shí)，鑒于手機(jī)尾插外形較規(guī)整及算法時(shí)間性能的要求，只設(shè)計(jì)一個(gè)高投票權(quán)區(qū)域，圓心選零件基準(zhǔn)圖像幾何中心位置，根據(jù)手機(jī)尾插的外形尺寸選取參數(shù)：Ci=280、λ=1/2 800。3 種算法檢測(cè)到的前8 個(gè)峰值點(diǎn)所對(duì)應(yīng)直線的實(shí)驗(yàn)結(jié)果如圖3 所示。

圖3 3種直線提取算法實(shí)驗(yàn)效果

從圖3(b)可以看出，HT 算法給出的前8 個(gè)最顯著峰值點(diǎn)中有4 個(gè)是噪聲像素產(chǎn)生的偽峰(對(duì)應(yīng)4 條誤檢測(cè)直線)，噪聲像素主要來自于類矩形插件在四個(gè)角處的不規(guī)則彎曲邊緣；概率HT 算法也不能抑制噪聲像素的影響，前8 個(gè)最顯著峰值點(diǎn)中也有兩個(gè)偽峰(對(duì)應(yīng)兩條誤檢測(cè)直線)，如圖3(c)所示；該文算法檢測(cè)到的前8 條直線均為有效邊緣直線，如圖3(d)所示。實(shí)驗(yàn)結(jié)果表明，該文算法能有效抑制偽峰的產(chǎn)生，誤提取的直線數(shù)目小于另外兩種算法，具有較高的直線檢測(cè)精準(zhǔn)度。

2.2.2 偽峰抑制效果分析

為了進(jìn)一步分析該文算法對(duì)Hough 空間偽峰抑制作用，分別抽取標(biāo)準(zhǔn)Hough 算法和該文算法檢測(cè)到的前10 000 個(gè)點(diǎn)，用Matlab 分別繪制抽取點(diǎn)在Hough 空間的分布情況，結(jié)果如圖4 所示。

從圖4 中可以看出，標(biāo)準(zhǔn)HT 算法得到的檢測(cè)點(diǎn)在Hough 空間中的分布相對(duì)嘈雜，偽峰點(diǎn)與真峰點(diǎn)包圍在一起，形成一個(gè)近似的錐形，如圖4(a)所示，說明真峰旁邊充斥著無數(shù)偽峰點(diǎn)，真峰不能顯著突出；該文算法得到的檢測(cè)點(diǎn)在Hough 空間中的分布峰值明顯尖銳，如圖4(b)所示，說明真峰點(diǎn)被偽峰點(diǎn)包圍在一起的情況較少，真峰銳利突出，很好地抑制了Hough 空間中偽峰的高度，進(jìn)而提高了直線檢測(cè)的精準(zhǔn)度。

2.2.3 直線檢測(cè)實(shí)驗(yàn)精度分析

對(duì)300 張采集的手機(jī)尾插圖像分別采用標(biāo)準(zhǔn)Hough 算法、概率Hough 算法以及該文提出的投票約束的Hough 算法進(jìn)行直線檢測(cè)實(shí)驗(yàn)，以式（6）的平均直線檢測(cè)精準(zhǔn)度P作為評(píng)判標(biāo)準(zhǔn)：

式中，Lall為遍歷峰值點(diǎn)檢測(cè)到直線數(shù)，Lright為最終需要檢測(cè)到的直線數(shù)，對(duì)于手機(jī)尾插零件為8。

圖4 算法偽峰抑制效果圖

表1 是3 種算法檢測(cè)精準(zhǔn)度與時(shí)間性能的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果，可以得出，該文算法的檢測(cè)精準(zhǔn)度最高，平均直線檢測(cè)精準(zhǔn)度P達(dá)到89%，較標(biāo)準(zhǔn)Hough 算法、概率Hough 算法有較大幅度的提升；該文算法引入的計(jì)算量小，算法的時(shí)間性能與標(biāo)準(zhǔn)Hough 算法相當(dāng)。由于概率Hough 算法只進(jìn)行部分像素點(diǎn)映射，其算法的時(shí)間性能較好，但精度最差。

表1 3種算法檢測(cè)精準(zhǔn)度與時(shí)間性能實(shí)驗(yàn)結(jié)果

3 結(jié)束語

Hough 變換算法被廣泛用于圖像直線檢測(cè)，但該算法用于類矩形小插件尺度測(cè)量中邊緣直線檢測(cè)時(shí)，易在Hough 空間形成偽峰、影響邊緣檢測(cè)精準(zhǔn)度，為此，提出了基于投票約束的Hough 變換直線檢測(cè)算法，該算法通過引入Hough 空間投票權(quán)重分配新策略來抑制偽峰產(chǎn)生，提高了圖像邊緣直線檢測(cè)精準(zhǔn)度，以手機(jī)尾插零件進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，與標(biāo)準(zhǔn)Hough 算法、概率Hough 算法相比較，該文算法直線檢測(cè)精準(zhǔn)度有較大的提升，可達(dá)到89%。該文算法引入的計(jì)算量小，在提高檢測(cè)準(zhǔn)確度的同時(shí)基本不會(huì)降低算法的時(shí)間性能，該文算法可根據(jù)具體情況設(shè)置多個(gè)高投票權(quán)區(qū)域及調(diào)整參數(shù)，以適用于其他零件，達(dá)到最優(yōu)直線檢測(cè)效果，且該研究已應(yīng)用于某型檢測(cè)設(shè)備研制中。