基于IRANSAC-IRLS 直線擬合算法及應(yīng)用

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

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

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

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

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

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

1 直線邊緣提取

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

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

該點(diǎn)的梯度幅值F：

該點(diǎn)梯度方向θ：

（2）通過(guò)高低閾值來(lái)判斷點(diǎn)是否為邊緣，對(duì)圖像中的弱紋理是通過(guò)判斷該點(diǎn)的梯度幅值是不是梯度方向上的局部最大值，保證了該算法良好的弱紋理檢測(cè)效果。

2 RANSAC 算法

2.1 RANSAC 算法基本思想

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

2.2 RANSAC 算法改進(jìn)方向

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

（1）在樣本子集選取的時(shí)候，可以根據(jù)某些約束條件對(duì)隨機(jī)抽樣的樣本子集進(jìn)行約束，來(lái)減少錯(cuò)誤抽取和檢驗(yàn)的次數(shù)。

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

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

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

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

3.1 IRANSAC 算法

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

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

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

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

式中：Gi為該點(diǎn)的梯度方向，然后計(jì)算該點(diǎn)到直線的距離di：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 仿真實(shí)驗(yàn)

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

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

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

4.2 實(shí)際產(chǎn)品實(shí)驗(yàn)

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

5 結(jié)語(yǔ)

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