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

李欣言　杜文華　王俊元　段能全　關　波　湯　恒　李　博

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

?

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

李欣言杜文華王俊元段能全關波湯恒李博

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

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

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

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

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

1　基元識別算法的思路

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

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

2.1分割點位置修正

采用多邊形近逼近算法將通過測量系統獲取的被測物體的平面輪廓曲線進行分割。由于多邊形逼近算法獲得的分割點與閾值的選取有關，導致多邊形控制點與圖像真實拐點之間產生偏差，最終影響輪廓的準確識別。現對此分割點進行修正。

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

判斷dAO、dOB的大小：

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

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

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

② 當dAO

③ 依此方法再進行下一個分割點的修正，直至全部分割點都修正完畢。

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

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

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

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

(D2+E2-4F>0)

(1)

設分割點A、B、C的坐標分別為(xa,ya)、(xb,yb)、(xc,yc)，代入式(1)可求得方程的系數：

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

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

hmax=Max(hi)

設hi是輪廓SAB與對應的多邊形邊AB的最大距離，d2是輪廓SBC與對應的邊BC的最大距離。

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

2.3加權最小二乘擬合算法

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

考慮離群值的影響，在進行擬合計算時為每個點引入Tukey[13]權重系數ωi，進行直線擬合時以：

為目標函數，對直線參數α、β、γ進行優化，式中λ為拉格朗日乘數。

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

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

為目標函數，對圓弧參數α、β、ρ進行優化。圖4為輪廓分割與基元識別的算法流程圖。

3　實驗結果及分析

3.1平面輪廓角點的檢測精度與檢測速度的對比分析

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

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

表1　Airplane 圖像平面輪廓特征點檢測效果

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

3.2平面輪廓的特征點檢測

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

表2　分段數據的曲線類型判斷結果

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

4　結語

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

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

[2]王飛,杜文華,關波,等.基于視覺的刀具參數高精度測量[J].計算機工程與設計,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]鄭軍,劉正文,馬兆瑞,等.基于最小誤差逼近的輪廓特征點提取[J].清華大學學報：自然科學版,2008，48(2)：165-168.

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

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

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

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

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

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

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

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

(編輯孫德茂)

如果您想發表對本文的看法，請將文章編號填入讀者意見調查表中的相應位置。

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年生，碩士研究生，主要研究方向為機器視覺、圖像處理。

2015-09-15)

160121

*山西省研究生優秀創新資助項目(20133095)