羅金鐄，胡小平，彭向前，黃泓

（湖南科技大學(xué) 機電工程學(xué)院，湘潭 411201）

直線邊緣是工業(yè)生產(chǎn)零件中最常見的輪廓特征[1]，它包含了最基本的幾何信息和拓撲信息。在對工業(yè)生產(chǎn)的零件圖像進行處理的過程中[2]，往往需要對直線邊緣進行擬合或定位，但是由于零件表面存在臟污，或者加工工藝的問題，使得直線邊緣存在沾連、毛刺等噪聲，導(dǎo)致直線上的邊緣點會偏離直線，對圖像處理的結(jié)果產(chǎn)生較大地影響。因此，研究在噪聲較多的情況下，快速而準(zhǔn)確地擬合出直線邊緣是非常有意義的[3]。

在直線擬合方面的研究中，國內(nèi)外學(xué)者已經(jīng)取得了不少研究成果。文獻[4]提出將霍夫變換[5]和梯度下降結(jié)合的方法擬合邊緣直線，但是該方法對線性噪聲敏感，容易出現(xiàn)誤判，而且擬合精度不高；傳統(tǒng)最小二乘法（least-squares line fitting，LS）擬合速度很快，但其容易受到噪聲點的干擾，在噪聲點多于10%的情況下就不能精確的擬合出直線的參數(shù)；文獻[6]提出迭代重加權(quán)最小二乘直線擬合算法，該算法在噪聲點少時能夠得到很高的擬合精度，但是在噪聲點較多，導(dǎo)致初始擬合偏差較大的情況下，不能擬合出高精度的直線邊緣。以上算法在噪聲點多的情況下，都不能擬合出準(zhǔn)確的直線。

為解決噪聲點對擬合精度的影響，文獻[7]提出隨機抽樣一致性算法，它具有優(yōu)良的魯棒性，能夠通過迭代在含有70%噪聲點的點集中尋找出最優(yōu)模型，但其最終的擬合精度依賴于額外的擬合算法，而且算法的耗時會隨著噪聲點的增加呈指數(shù)增長[8]；文獻[9]為了提高RANSAC 算法的運行速度，提出一種基于預(yù)檢驗的抽樣一致性算法，總的來說確實能提高算法的運行速度，但是在其隨機的子集選取過程中，可能會將正確的模型誤判成錯誤的模型，在噪聲多時，可能會陷入無限次的抽樣與檢驗的過程中。綜上所述，如何在含有大量噪聲點的點集中快速而準(zhǔn)確地擬合出直線的參數(shù)是十分重要的。

針對直線邊緣存在大量噪聲點的情況下，RANSAC算法效率低、精度不高的問題，提出IRANSAC-IRLS算法。首先，通過Canny 算子提取出直線的邊緣；然后，利用直線上的邊緣點的梯度方向相近，將梯度方向引入邊緣點RANSAC 擬合，降低錯誤的隨機抽取次數(shù)，篩選出擬合時的部分噪聲點；最后，對IRANSAC 提取出來的局內(nèi)點進行迭代加權(quán)最小二乘擬合，降低數(shù)據(jù)本身的誤差對擬合的影響，提高擬合的精度。仿真實驗和實際產(chǎn)品實驗證明該算法具有良好的時效性和魯棒性。

1 直線邊緣提取

在進行擬合之前，都需要獲取直線的邊緣點集，微分算子是圖像處理的各種邊緣檢測方法中最常用的方法，Canny 算子[10]具有良好的邊緣檢測效果，該方法通過建立梯度幅值圖，利用高低兩個閾值來提取圖像中的邊緣，考慮了梯度幅值與梯度方向之間的關(guān)系，抗干擾能力最強，對于圖像中的弱紋理也具有良好的檢測效果，本文通過Canny 算法提取出直線邊緣，其算法步驟如下：

（1）用高斯函數(shù)對圖像進行濾波，作平滑運算，然后對圖像進行卷積處理，得到該點x 方向上的梯度值Fx，該點y 方向上的梯度值Fy。

該點的梯度幅值F：

該點梯度方向θ：

（2）通過高低閾值來判斷點是否為邊緣，對圖像中的弱紋理是通過判斷該點的梯度幅值是不是梯度方向上的局部最大值，保證了該算法良好的弱紋理檢測效果。

2 RANSAC 算法

2.1 RANSAC 算法基本思想

RANSAC 是一種從模型數(shù)據(jù)中隨機抽取滿足模型的最小樣本數(shù)來估計樣本的數(shù)學(xué)模型的方法，其利用模型的余集對隨機抽取的樣本進行檢驗[11]，然后通過迭代的思想進行最優(yōu)模型的尋找，由于算法通過迭代進行尋求最優(yōu)，犧牲了算法的時效性，算法的運行時間隨著噪聲點的增加呈指數(shù)增長，不能滿足工業(yè)實時性的要求[12]。

2.2 RANSAC 算法改進方向

通過RANSAC 算法的基本思想，可以分析出RANSAC 算法的基本的優(yōu)化方向，可向著以下兩個方向進行優(yōu)化：

（1）在樣本子集選取的時候，可以根據(jù)某些約束條件對隨機抽樣的樣本子集進行約束，來減少錯誤抽取和檢驗的次數(shù)。

（2）當(dāng)通過樣本子集估計出總體模型后，可以只利用剩余點中的一部分來對估計的總體模型進行驗證，但該優(yōu)化方向在噪聲點多時可能會造成誤檢驗，從而陷入無限次的抽取和檢驗中。

3 基于IRANSAC-IRLS 的直線擬合算法

經(jīng)Canny 提取的直線邊緣數(shù)據(jù)中包含了大量噪聲點，而隨著噪聲點的增加，RANSAC 算法的運行時間呈指數(shù)增長，為解決這一問題，利用同一條直線上的點的梯度方向相近，將梯度方向引入RANSAC算法中，提出IRANSAC-IRLS 直線擬合算法，該算法利用梯度方向?qū)ANSAC 算法中隨機抽取的樣本進行約束，減少誤抽取，提高算法的效率，同時引入梯度方向?qū)?nèi)點的判斷模型進行改進，減少提取出來的局內(nèi)點點集中的噪聲點，然后再結(jié)合迭代加權(quán)最小二乘法對提取出來的最優(yōu)局內(nèi)點點集進行擬合，提高最終的擬合精度，其算法的流程如圖1所示。

圖1 算法流程Fig.1 Algorithm flow chart

3.1 IRANSAC 算法

（1）在邊緣點集上隨機抽取確定直線方程的最小點數(shù)，即2 個點，設(shè)點1 的梯度方向為G1，點2 的梯度方向為G2，如果隨機抽取的2 個點在同一條直線上，則兩點的梯度方向差的絕對值應(yīng)在一定范圍內(nèi)，自定義2 個抽樣點梯度方向差的閾值Tg，公式如下：

如抽取的兩點的梯度方向不滿足公式（3），則重新抽取。如滿足，那么使用這兩點計算直線估計模型，并以這兩點的梯度方向的平均值作為直線的梯度方向的主方向Mg：

（2）遍歷剩余的點，如果點為直線上的點，應(yīng)滿足2 個條件：

①首先，該點的梯度方向應(yīng)和直線的梯度方向主方向差值的絕對值小于閾值t：

式中：Gi為該點的梯度方向，然后計算該點到直線的距離di：

②設(shè)定距離閾值D，若di＜D，則滿足第2 條件；若同時滿足上述2 個條件，則可認為該點為局內(nèi)點，否則是局外點，即噪聲點。遍歷結(jié)束后，計算出所有局內(nèi)點的數(shù)目，并計算內(nèi)點的比例ε＝局內(nèi)點總數(shù)/數(shù)據(jù)點總數(shù)。

（3）重復(fù)進行步驟（1）和步驟（2），進行迭代，保存局內(nèi)點最多的最優(yōu)模型，保存當(dāng)前迭代次數(shù)N，直到N 大于終止迭代次數(shù)m。

RANSAC 的迭代終止次數(shù)m 可以根據(jù)理論計算，計算公式如下：

由文獻[13]可知，在置信度為η0的條件下，循環(huán)多次后，應(yīng)至少存在一次采樣，使得選擇出來的b個抽樣子集均為局內(nèi)點，置信度η0為在樣本中抽取一個好樣本的概率，一般設(shè)置在［0.95，0.99］的范圍內(nèi)；b 表示模型估計所需要的最小點數(shù)，本文取2；ε 表示局內(nèi)點在所有樣本點中所占的比例。

對改進算法進行分析，首先該方法在樣本點抽取后，利用抽樣點的梯度方向?qū)Τ跏汲闃幽Ｐ瓦M行預(yù)檢驗，降低了計算的時間；其次，在樣本點檢驗時利用梯度方向條件，進一步對擬合時的部分噪聲點進行二次篩選，降低了局內(nèi)點集合的誤差。

3.2 迭代加權(quán)最小二乘法擬合

經(jīng)IRANSAC 提取出的局內(nèi)點需要進行擬合，傳統(tǒng)的擬合常使用標(biāo)準(zhǔn)的最小二乘擬合法，與直線距離較遠的點和與直線距離相近的點都擁有相同的權(quán)重，得到的直線參數(shù)并不是理想的。因此，引入迭代加權(quán)最小二乘法對局內(nèi)點進行擬合，根據(jù)點到直線的距離對每個點進行加權(quán)，其目標(biāo)損失函數(shù)如下：

式中：Wi為各邊緣點對應(yīng)權(quán)重，i=1，2，…，num；k 為斜截式直線的斜率；b 為斜截式直線的截距。

將點到直線的距離d 作為權(quán)函數(shù)變量：

權(quán)函數(shù)有Tukey、Geman-MClure、Huber 等類型，本文采用Huber 權(quán)函數(shù)，各點對應(yīng)的權(quán)函數(shù)如下：

式中：u 為設(shè)置距離閾值。

為求解式（8），對式（8）的k 和b 分別求偏導(dǎo)，得到：

采用常規(guī)最小二乘法求解，解得初始k0和b0；代入式（8）～式（12），更新權(quán)重，多次迭代求解斜率k和截距b，然后根據(jù)角度和截距的變化量來設(shè)置迭代終止條件。

4 實驗與分析

4.1 仿真實驗

為了驗證IRANSAC-IRLS 直線擬合算法的有效性，在2.50 GHz 的i7-6500U～CPU 平臺上進行仿真，假設(shè)要擬合的直線為y=0.1x+20，其角度為5.7106°，構(gòu)建噪聲點比例分別為20%、40%、60%、80%的300數(shù)據(jù)點，直線上的點的梯度方向設(shè)置在直線主方向角的［-10，+10］之間隨機分布，噪聲點的梯度方向在直線主方向角的［-90，+90］之間隨機分布。

設(shè)置IRANSAC-IRLS 算法中的計算模型參數(shù)需要的最小數(shù)據(jù)點b=2，置信概率η＝0.98，抽樣點梯度方向差的閾值Tg=2°，點與直線的梯度主方向差的閾值t=30°，點到直線的距離閾值D=1。設(shè)置迭代最小二乘法距離閾值u=0.8，終止迭代條件為直線的角度變化量小于0.008°。對不同噪聲點比例下RANSAC-LS 與IRANSAC-IRLS 算法的直線擬合精度和效率進行仿真分析，100 次數(shù)據(jù)的平均值如表1 所示。

表1 300 數(shù)據(jù)點時RANSALC-LS 和IRANSAC-IRLS 的數(shù)據(jù)分析Tab.1 Data analysis of RANSALC-LS and IRANSAC-IRLS at 300 data points

4.2 實際產(chǎn)品實驗

為驗證IRANSAC-IRLS 算法在工業(yè)實際數(shù)據(jù)中是否有實際的應(yīng)用價值和應(yīng)用效果，對比分析不同的直線擬合算法在實際應(yīng)用的使用效果。將本文算法在兩種產(chǎn)品中進行測試，并與霍夫擬合、IRLS和RANSAC-LS 直線擬合算法進行對比，其中產(chǎn)品1為某含噪試管直線邊緣，具有440 個數(shù)據(jù)點；產(chǎn)品2為某液晶屏幕直線邊緣，具有2700 個邊緣數(shù)據(jù)點。通過實驗可得，對于兩種實際工業(yè)圖像數(shù)據(jù)，本文提出的IRANSAC-IRLS 擬合精度相較于霍夫直線擬合和IRLS 的擬合精度有較大地提高?；舴蛑本€擬合容易受噪聲點的干擾擬合出多條直線，而工業(yè)環(huán)境下往往是需要擬合出最優(yōu)直線，IRLS 受噪聲點的影響導(dǎo)致初始偏差大的情況下，也無法擬合出精準(zhǔn)的直線參數(shù)。RANSAC-LS 在產(chǎn)品1 和產(chǎn)品2 中的擬合時間分別為22 ms 和788 ms；IRANSAC-IRLS在產(chǎn)品1 和產(chǎn)品2 中的擬合時間分別為11 ms 和144 ms；IRANSAC-IRLS 算法在產(chǎn)品1 和產(chǎn)品2 中的擬合效率相較于RANSAC-LS 分別提高50.0%和81.7%，擬合精度也有所提高。

5 結(jié)語

本文提出的IRANSAC-IRLS 直線擬合算法，在RANSAC-LS 的基礎(chǔ)上通過引入梯度方向?qū)﹄S機抽取的樣本進行約束，減少了錯誤抽取的次數(shù)，提高了算法的時效性；對提取出來的局內(nèi)點進行迭代加權(quán)最小二乘直線擬合，降低數(shù)據(jù)本身的誤差對擬合的影響，提高了最終的擬合精度。仿真實驗結(jié)果表明，在噪聲點比例20%、40%、60%、80%的條件下，IRANSAC-IRLS 擬合效率比RANSAC-LS 分別提高16.3%、41.9%、47.5%、53.2%，擬合精度分別提升14.3%、16.7%、44.0%、69.0%，能有效地提高含有大量噪聲點的直線邊緣的擬合效率和精度。將本文算法應(yīng)用于不同的工業(yè)產(chǎn)品圖像的直線擬合中，驗證了本文的算法具有良好的時效性和魯棒性，能廣泛地應(yīng)用于自動化行業(yè)，但是該算法只適用于直線擬合，未來如何讓其適用與多種形狀的擬合，是后續(xù)要研究的方向。