一種平面輪廓分割與基元識別方法研究*

李欣言　杜文華　王俊元　段能全　關(guān)　波　湯　恒　李　博

(中北大學(xué)機(jī)械與動力工程學(xué)院，山西 太原 030051)

?

一種平面輪廓分割與基元識別方法研究*

李欣言杜文華王俊元段能全關(guān)波湯恒李博

(中北大學(xué)機(jī)械與動力工程學(xué)院，山西 太原 030051)

為提高視覺測量系統(tǒng)的檢測精度與檢測速度，提出了一種平面輪廓分割與識別算法。首先對經(jīng)過多邊形逼近算法進(jìn)行輪廓分割獲得的分割點(diǎn)位置按一定規(guī)則進(jìn)行修正；然后對分割點(diǎn)間的線段類型加以識別，對過度分割的圓弧段進(jìn)行融合處理；最后用加權(quán)最小二乘擬合算法抑制了大的離群值的影響，將輪廓擬合成相對應(yīng)的幾何基元。對提出的方法分別進(jìn)行檢測精度與檢測速度對比實(shí)驗(yàn)和基元識別能力測試實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，提出的方法基元識別準(zhǔn)確、檢測速度快、通用性好。

機(jī)器視覺；輪廓分割；基元識別；多邊形逼近

近年來，隨著機(jī)器視覺技術(shù)測量精度及測量速度的提高，其在機(jī)械零件尺寸[1]、刀具[2]參數(shù)測量等方面的應(yīng)用越來越多。這些三維零件、刀具在采用視覺技術(shù)進(jìn)行測量時，被檢測圖像經(jīng)邊緣檢測后獲得主要由直線、圓弧、圓等基元構(gòu)成的平面輪廓。平面輪廓基元識別是檢測系統(tǒng)必不可少的關(guān)鍵環(huán)節(jié)，識別的準(zhǔn)確性直接影響后續(xù)尺寸測量的精度；識別的效率直接影響檢測系統(tǒng)的實(shí)時性。因此在進(jìn)行視覺處理中需要對這些平面輪廓進(jìn)行精確的分段識別和重構(gòu)。

對由測量設(shè)備獲取的二維輪廓進(jìn)行分段與識別，國內(nèi)外有很多學(xué)者進(jìn)行了相應(yīng)的研究。Jayachandran A[3]提出了基于模糊邏輯的圖像處理新方法和新思想，用模糊推理來檢測角，有效地抑制了圖像噪聲，取得了良好的效果。徐越[4]為實(shí)現(xiàn)重疊目標(biāo)的精確分割，提出了一種Snake模型與角點(diǎn)檢測相結(jié)合的重疊目標(biāo)分割方法。鄭軍等[5]針對輪廓曲線的多邊形近似和特征點(diǎn)提取，提出了多邊形逼近誤差和局部最小誤差逼近特征點(diǎn)的定義和相應(yīng)的實(shí)現(xiàn)算法。顧步云[6]針對包含直線、圓弧特征的截面輪廓數(shù)據(jù)，通過計算離散點(diǎn)曲率進(jìn)行特征點(diǎn)的提取與數(shù)據(jù)分段。王英惠[7-9]在文獻(xiàn)[7-8]中分別用近似曲率的十一點(diǎn)法和曲率差分圖的方法進(jìn)行平面輪廓的精確分段與識別；在文獻(xiàn)[9]中采用約束最小二乘算法對輪廓進(jìn)行了重構(gòu)。伍濟(jì)鋼[10]用HOUGH變換改進(jìn)的曲率法來識別平面輪廓圖元。胡魁賢[11]以線段和圓弧為逼近基元對封閉的截面曲線進(jìn)行分段擬合，該算法簡單有效，較好地解決以直線和圓弧為基元的截面曲線擬合問題。張習(xí)文[12]以線段和圓弧為逼近基元，研究基于改進(jìn)遺傳算法的曲線擬合，較好地解決了用線段和圓弧擬合曲線問題。在深入研究現(xiàn)有平面輪廓分段識別與重構(gòu)等方法的基礎(chǔ)上，本文提出了一種新的平面輪廓分割與基元識別方法。

1　基元識別算法的思路

采用多邊形近逼近算法將輪廓曲線進(jìn)行分割，找出邊界輪廓的分割點(diǎn)；針對該算法分割點(diǎn)不精準(zhǔn)的缺點(diǎn)，采用一種規(guī)則對該分割點(diǎn)的位置進(jìn)行判別，如不符合條件則進(jìn)行修正；然后對基元進(jìn)行識別，對圓弧段輪廓是否過度分割進(jìn)行判別，如屬于過度分割則對其進(jìn)行融合；最后采用擬合算法對分割后的輪廓進(jìn)行擬合。

2　輪廓分割與基元識別算法的方法

2.1分割點(diǎn)位置修正

采用多邊形近逼近算法將通過測量系統(tǒng)獲取的被測物體的平面輪廓曲線進(jìn)行分割。由于多邊形逼近算法獲得的分割點(diǎn)與閾值的選取有關(guān)，導(dǎo)致多邊形控制點(diǎn)與圖像真實(shí)拐點(diǎn)之間產(chǎn)生偏差，最終影響輪廓的準(zhǔn)確識別?，F(xiàn)對此分割點(diǎn)進(jìn)行修正。

如圖1所示，S為一段平面輪廓，A、O、B為經(jīng)多邊形近逼近算法獲得的分割點(diǎn)。SAO、SOB為分割后的輪廓，dAO、dOB分別為該輪廓段與所對應(yīng)的逼近多邊形的邊AO、OB之間的最大距離。

判斷dAO、dOB的大小：

①當(dāng)dAO>dOB，則將分割點(diǎn)O向SAO段移動一個輪廓控制點(diǎn)到點(diǎn)O′。SAO′、SOB′為分割后的輪廓，DAO′、DO′B分別為重新分割后的輪廓段與所對應(yīng)的逼近多邊形的邊AO′、O′B之間的最大距離。

判斷：若Max{DAO′，DO′B}>Max{dAO，dOB}，則不做處理，此分割點(diǎn)O保留；

若Max{DAO′，DO′B}Max{dAO，dOB}的條件。

② 當(dāng)dAO

③ 依此方法再進(jìn)行下一個分割點(diǎn)的修正，直至全部分割點(diǎn)都修正完畢。

2.2基元識別與輪廓段的融合

經(jīng)過多邊形近逼近后，輪廓中的有些圓弧段處于過度分割狀態(tài)，因此需要對這些圓弧段進(jìn)行檢測，如屬于過度分割，則需要進(jìn)行融合。取原始輪廓S上的4個分割點(diǎn)A、B、C、D，如圖2所示。

Q是由點(diǎn)A、B、C擬合得到的圓弧段，其一般式方程為：

Q={(x,y)|x2+y2+D·x+E·y+F=0}

(D2+E2-4F>0)

(1)

設(shè)分割點(diǎn)A、B、C的坐標(biāo)分別為(xa,ya)、(xb,yb)、(xc,yc)，代入式(1)可求得方程的系數(shù)：

設(shè)圓弧段Q的圓心坐標(biāo)為O，半徑為ρ，由式(1)可得：

ki(xi,yi)是輪廓SAC段上的任一控制點(diǎn)，計算其到圓心O(xo,yo)的距離與圓弧半徑ρ之差：

hmax=Max(hi)

設(shè)hi是輪廓SAB與對應(yīng)的多邊形邊AB的最大距離，d2是輪廓SBC與對應(yīng)的邊BC的最大距離。

若hmaxMax{d1,d2}，則輪廓段SAB按直線AB處理。以此方法再分析下一段輪廓SBC和SCD，經(jīng)過多次迭代直到?jīng)]有需要合并處理的對象為止。

2.3加權(quán)最小二乘擬合算法

為了表征輪廓信息，提取輪廓參數(shù)，需要對分割后的輪廓段進(jìn)行擬合。最小二乘法是一種較常用的方法。當(dāng)輪廓邊緣存在大的離群值時，由于最小二乘法采用的是平方距離，那些與擬合線距離較遠(yuǎn)的點(diǎn)在擬合過程中會擁有非常大的權(quán)重，導(dǎo)致其魯棒性差。

考慮離群值的影響，在進(jìn)行擬合計算時為每個點(diǎn)引入Tukey[13]權(quán)重系數(shù)ωi，進(jìn)行直線擬合時以：

為目標(biāo)函數(shù)，對直線參數(shù)α、β、γ進(jìn)行優(yōu)化，式中λ為拉格朗日乘數(shù)。

圖3為一刀具測量圖像，圖中的凸起為未擦拭干凈的切屑。采用上述算法進(jìn)行五次迭代后的擬合直線，基本上排除了大的離群值對原輪廓線的影響。

對圓弧形輪廓段擬合時以：

為目標(biāo)函數(shù)，對圓弧參數(shù)α、β、ρ進(jìn)行優(yōu)化。圖4為輪廓分割與基元識別的算法流程圖。

3　實(shí)驗(yàn)結(jié)果及分析

3.1平面輪廓角點(diǎn)的檢測精度與檢測速度的對比分析

有些平面輪廓中的特征點(diǎn)的類型為角點(diǎn)，如文獻(xiàn)[10]中的Airplane圖像，圖5a所示。分別用文獻(xiàn)[10]中的改進(jìn)的曲率法及本文提出的方法對其進(jìn)行特征點(diǎn)檢測，檢測結(jié)果如圖5b、c所示。

Airplane輪廓共有38個特征點(diǎn)，對上述2種特征點(diǎn)檢測方法的正確率、誤判率、漏判率、檢測時間進(jìn)行對比分析，結(jié)果如表1所示。

表1　Airplane 圖像平面輪廓特征點(diǎn)檢測效果

從表1可以看出，本文提出的方法同樣能100%檢測出輪廓中的特征點(diǎn)，且檢測時間少于文獻(xiàn)[10]中的方法。在某些在線實(shí)時測量過程中，需要在有限的時間內(nèi)對大量圖片進(jìn)行處理，利用本文提出的方法可以更好地滿足此類需求。

3.2平面輪廓的特征點(diǎn)檢測

為了測試本文提出的方法對其他類型的特征點(diǎn)的檢測能力以及特征點(diǎn)檢測的精確程度，采用文獻(xiàn)[6]、[10]中使用的平面輪廓圖像，如圖6a所示。圖6b為經(jīng)本文算法進(jìn)行基元識別后的結(jié)果，■表示識別出的特征點(diǎn)，不同基元以不同灰度區(qū)分開。表2為分段數(shù)據(jù)的曲線類型判斷結(jié)果。

表2　分段數(shù)據(jù)的曲線類型判斷結(jié)果

上述結(jié)果表明了利用本文算法所提取的特征點(diǎn)精度較高，幾乎不存在“偽”特征點(diǎn)。并且準(zhǔn)確地識別了相鄰特征點(diǎn)之間的分段輪廓的基元屬性。

4　結(jié)語

本文提出了一種將平面輪廓按照幾何基元分割為直線和圓弧的算法。該算法能準(zhǔn)確識別平面輪廓中的直線、圓弧，且計算速度較快。在刀具在線實(shí)時測量中有較好的應(yīng)用。

[1] 李紅鋼,杜文華,曾志強(qiáng),等.基于機(jī)器視覺的圓筒形零件直角梯形槽槽寬檢測研究[J].包裝工程,2013(3)：83-87.

[2]王飛,杜文華,關(guān)波,等.基于視覺的刀具參數(shù)高精度測量[J].計算機(jī)工程與設(shè)計,2015(2)：524-528.

[3]Jayachandran A, Dhanashakeran R, Sugel Anand O.Fuzzy information system based digital image segmentation by edge detection Source[C].2010 IEEE International Conference on Computational Intelligence and Computing Research:IEEE Computer Society,2010：794-798.

[4]Xu Yue,Li Yinghui,Song Huaibo.Segmentation method of overlapped double apples based on Snake model and corner detectors[J]. Nongye Gongcheng Xuebao/Transactions of the Chinese Society of Agricultural Engineering,2015,31(1):196-203.

[5]鄭軍,劉正文,馬兆瑞,等.基于最小誤差逼近的輪廓特征點(diǎn)提取[J].清華大學(xué)學(xué)報：自然科學(xué)版,2008，48(2)：165-168.

[6]顧步云,周來水,李濤.一種新的截面輪廓特征點(diǎn)識別與分段曲線類型判別算法[J]. 機(jī)械科學(xué)與技術(shù),2007，26(11)：1398-1402.

[7]王英惠,吳維勇,趙汝嘉.平面輪廓的分段與識別技術(shù)[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2002，14(12)：1142-1145.

[8]吳維勇,王英惠,周晏.平面輪廓識別與分段技術(shù)的研究與快速實(shí)現(xiàn)[J].圖學(xué)學(xué)報,2003，24(14)：14-19.

[9]王英惠,吳維勇.基于分段與識別技術(shù)的平面輪廓的精確重構(gòu)[J].圖學(xué)學(xué)報,2007，28(5)：43-48.

[10]伍濟(jì)鋼,賓鴻贊.用HOUGH變換改進(jìn)的曲率法識別平面輪廓圖元[J].圖學(xué)學(xué)報,2011，32(2)：102-106.

[11]胡魁賢,嚴(yán)宏志,朱自冰,等.截面輪廓曲線分段約束擬合[J].計算機(jī)工程與科學(xué),2009(7)：53-56.

[12]張習(xí)文,歐宗瑛.基于遺傳算法的以線段和圓弧為基元的曲線擬合[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2002，14(2)：144-147.

[13]Mosteller F,Tukey J W .Data analysis and regression[M].Reading,MA:Addison-Wesley,1977.

(編輯孫德茂)

如果您想發(fā)表對本文的看法，請將文章編號填入讀者意見調(diào)查表中的相應(yīng)位置。

Research on the method of planar contour segmentation and recognition of the geometric primitives

LI Xinyan, DU Wenhua, WANG Junyuan, DUAN Nengquan, GUAN Bo, TANG Heng, LI Bo

(School of Mechanical and Power Engineering, North University of China, Taiyuan 030051, CHN)

In order to improve the detection accuracy and speed of the vision measurement system, a method of planar contour segmentation and recognition is proposed. First, the position of the points of division obtained by the polygon approximation algorithm is modified by a certain rule. Then the types of line segments between the points are identified, and the over segmented arc is combined. In the end, the affect of large outliers is limited by the weighted least squares fitting algorithm. And the contour is synthesized into the corresponding geometric elements. Experimental demonstration of the proposed method is carried out by testing accuracy and speed detection contrast experiments and identification ability of basic element experiments. Experimental results show that the proposed method has the characteristics of high accuracy, fast detection speed and good generality.

machine vision; contour segmentation; primitive recognition; polygon approximation

TP391

A

李欣言，女，1989年生，碩士研究生，主要研究方向?yàn)闄C(jī)器視覺、圖像處理。

2015-09-15)

160121

*山西省研究生優(yōu)秀創(chuàng)新資助項(xiàng)目(20133095)