基于優(yōu)化RANSAC算法的二次元快速穩(wěn)定配準(zhǔn)

孫 強(qiáng)，葉玉堂，宋昀岑，張 靜，姚 嬌，周戀玲，陳 偉

（電子科技大學(xué)，光電信息學(xué)院，四川 成都610054）

0 引 言

二次元光電檢測儀是將工業(yè)相機(jī)采集到的待檢測零件等物體的光電圖像和其CAD標(biāo)準(zhǔn)檔進(jìn)行對比，然后再分析比較，以達(dá)到檢測其缺陷的目的。其中圖像配準(zhǔn)是每次檢測過程中至關(guān)重要的一步。配準(zhǔn)的穩(wěn)定性、精確性以及速度等條件直接影響儀器的整體檢測性能。

圖像配準(zhǔn)［1－2］是圖像處理和計算機(jī)視覺研究領(lǐng)域中的熱點問題，也是許多該領(lǐng)域的理論和應(yīng)用的基礎(chǔ)。配準(zhǔn)的目的就是找到兩幅圖像的匹配對應(yīng)關(guān)系，即匹配模型參數(shù)M。由Fishler和Bolles提出的隨機(jī)抽樣一致性算法（random sample consensus，RANSAC）是計算機(jī)視覺領(lǐng)域內(nèi)應(yīng)用最廣泛的Robust模型參數(shù)估計算法之一［3－4］，對錯誤率超過50%的數(shù)據(jù)仍然能夠處理。但在RANSAC算法的模型參數(shù)檢驗中，全部參與全部數(shù)據(jù)必然會造成計算浪費，而且匹配穩(wěn)定性也會受到影響。如果能減少參與全部數(shù)據(jù)檢驗的模型參數(shù)數(shù)量，就會提高RANSAC算法的效率和穩(wěn)定性。

為了解決零件圖像和CAD標(biāo)準(zhǔn)檔圖像的穩(wěn)定快速匹配，針對零件圖像的特點，本文提出了首先進(jìn)行預(yù)匹配的處理方案，然后再利用RANSAC算法對零件圖像的特征點和CAD文檔對應(yīng)的特征點進(jìn)行匹配。通過實驗，這種優(yōu)化后的算法在匹配準(zhǔn)確地前提下，速度和穩(wěn)定性都有很大的提高。

1 輪廓曲線特征點提取

1.1 目標(biāo)輪廓提取

采集到的零件圖像為灰度圖像，為了得到零件輪廓，首先對圖像進(jìn)行二值化，然后進(jìn)行邊界跟蹤得到零件目標(biāo)的單像素輪廓［5］。

1.2 多邊形遞歸逼近算法

結(jié)合本文的零件目標(biāo)輪廓，多邊形近似算法定義如下［1－2］：

定義1 令C為零件目標(biāo)輪廓離散曲線上的N（N＞1）個點組成的序列，C＝｛Pi（xi，yi）｜i＝1，2，…，N｝，其中（xi，yi）為序列中的第i個點Pi點的坐標(biāo)。

定義2 線段L由C中兩個不同的點Pi和Pi＋k唯一確定，

定義4 零件輪廓的多邊形近似曲線PA滿足如下條件：

（1）PA＝｛L1，L2，…，Lnum（PA）｝；

（3）num（PA）為PA中線段的數(shù)目；

（4）令SPA為全部多邊形近似曲線PA的集合。給定一個最大誤差閾值，則零件輪廓的多邊形近似問題可以描述為求取線段序列使且對于滿足num（PA2）＜num（PA1）的

基于以上定義，本文給出了對零件輪廓進(jìn)行多邊形近似的遞歸逼近算法［6－9］，如圖1所示。

Algorithmn1：輪廓多邊形近似的遞歸逼近算法

Input：零件輪廓組成的點的序列C＝｛Pi（xi，yi）｜i＝1，2，…，N｝，閾值誤差。

Output：近似多邊形的頂點序列，V＝｛Pi（xi，yi）｜i＝1，2，…，m｝，其中m為多邊形邊數(shù)。

步驟1：初始化C0＝C，left＝1，right＝N，V＝φ；執(zhí)行步驟2；

步驟2：如果right–left＜2，則執(zhí)行步驟4；對點序列C0＝｛Pi（xi，yi）｜i＝left，left＋1，…，right｝，如果-Pk∈C0，使得max（D（Pk，Lk））＞，其中則將Pk壓入點數(shù)組V，并將C0劃分為C0L和C0R，其中C0L＝｛Pi（xi，yi）｜i＝left，left＋1，…，k－1｝，C0R＝｛Pi（xi，yi）｜i＝k，k＋1，…，right｝，執(zhí)行步驟3；否則執(zhí)行步驟4；

步驟3：對C0L，令C0＝C0L，即right＝k－1；對C0R，令C0＝C0R，即left＝k。繼續(xù)執(zhí)行步驟2；

步驟4：輸出V。

圖1 多邊形近似的遞歸逼近

2 加入預(yù)匹配的RANSAC算法原理

通過對零件圖像輪廓的多邊形近似和對零件CAD的解析，得到兩個特征點集。如果用傳統(tǒng)的RANSAC匹配算法就是直接對兩個點集合進(jìn)行匹配，這樣會造成很大一部分浪費計算，影響了匹配的速度和穩(wěn)定性，也可能導(dǎo)致匹配不成功［10－11］。作為改進(jìn)，首先將零件圖像和其CAD標(biāo)準(zhǔn)檔進(jìn)行重心匹配，接著主軸在一個小范圍內(nèi)掃描預(yù)匹配，最后利用RANSAC對預(yù)匹配好的兩個點集進(jìn)行再一次優(yōu)化匹配。

本文下一步先介紹區(qū)域的矩分析，得到目標(biāo)區(qū)域的主軸，然后介紹匹配關(guān)系矩陣。

2.1 區(qū)域的矩描述［12］

對于二維函數(shù)f（x，y），它的（p＋q）階混合原點矩定義為

mpq＝而（p＋q）階混合中心矩定義為

對于數(shù)字圖像，（p＋q）階原點矩和中心矩分別定義為

2.2 匹配關(guān)系矩陣M

記零件CAD上一個特征點像素坐標(biāo)為Qm＝（xm，ym），零件圖像上對應(yīng)的特征點的像素坐標(biāo)為Qo＝（xo，yo），則平移向量Δt＝［Δtx，Δty］＝［xo–xm，yo–ym］

記旋轉(zhuǎn)角為θ。本文是先對零件CAD圖形和零件圖像之間先進(jìn)行平移變換T，然后再進(jìn)行旋轉(zhuǎn)變換R。為了便于表示，采用齊次坐標(biāo)表示。下面討論討論具體變換關(guān)系［13－14］。

Qm＝（xm，ym）經(jīng)過平移變換過程后點記為＝則平移變換過程為

則從Qm到Qo的平移旋轉(zhuǎn)變換關(guān)系為

其中M＝RT兩個特征點之間的匹配關(guān)系矩陣。

2.3 改進(jìn)的RANSAC算法描述

Algorithmn2：零件CAD模型與圖像目標(biāo)特征點的基于矩的預(yù)匹配的RANSAC快速匹配算法。

Input：零件CAD模型（Model）外邊界輪廓點Cmodel＝以及特征點Vmodel＝Model邊界輪廓重心零件目標(biāo)圖像（Object）外邊界輪廓點序列

Output：零件CAD模型（Model）、圖像目標(biāo)（Object）特征點之間的變換矩陣M以及對應(yīng)匹配點。

步驟1：將Cobject作為Algorithmn1的輸入得到Object近似多邊形頂點序列

步驟3：將Cmodel和Cobject代入（2）～（3）計算Model和Object的主軸取向αmodel、αobject.；

步驟4：對Vmodel中每個特征點作一次平移變換

步驟5：考慮到Object邊界提取和多邊形近似的誤差，將旋轉(zhuǎn)Δα＝αobject－αmodel后得到的點序列和Vobject不一定是最佳匹配；在此作下微調(diào)，將旋轉(zhuǎn)角度下上擴(kuò)展Δφ，并將增長間隔定為Δθ，則可得到在Δβ＝Δα±Δφ范圍內(nèi)以重心為旋轉(zhuǎn)點旋轉(zhuǎn)后得到的特征點列的集合計算得到在第k（1≤k≤N）次旋轉(zhuǎn)中，得到的VbmodelΔt，Δβk中個特征點與Vobject中點的最短距離點的距離和dΔβi達(dá)到最小，并將Vobject中與VbmodelΔt，Δβk中個 特 征 點 對 應(yīng) 的 最 短 距 離 點 集 記 為則此時預(yù)匹配完成，執(zhí)行步驟6；

步驟6：置投票數(shù)voteCount＝0，NMSSs＝2；

步驟7：在Vmodel隨機(jī)抽取NMSSs個特征點，與原字符串中對應(yīng)的NMSSs個點組成最小樣本點集MSSs；根據(jù)式（5）將Model的樣本點集向Object上的樣本點集進(jìn)行變換，計算得到變換矩陣MMSSs；執(zhí)行步驟8；

步驟8：根據(jù)式（5）計算Vmodel點集中所有點經(jīng)過矩陣MMSSs變換后得到的點集為原字符串，接著得到中每個點與Vobject最近距離點組成的點集為；對中的所有點與中對應(yīng)點的距離進(jìn)行比較，如果d＜dis＿threshold，則voteCount＋＋；如果（voteCount/♂）＞voteRateThreshold，則進(jìn)入步驟9，否則進(jìn)入步驟7；

步驟9：將Vmodel和中對voteCount有貢獻(xiàn)的點帶入式（5）對變換矩陣進(jìn)行優(yōu)化，得到Model和Object點集最佳匹配的變換矩陣Mbest；進(jìn)入步驟10；

步驟10：輸出Mbest和。

圖2 零件圖像和其CAD標(biāo)準(zhǔn)檔

3 實驗及結(jié)果分析

3.1 零件CAD標(biāo)準(zhǔn)檔和零件目標(biāo)圖像的主軸方向和控制點的確定

測試的零件的CAD標(biāo)準(zhǔn)檔如圖2（b）所示，通過dxflib開源庫［15－16］可以解析此CAD對應(yīng)的DXF文件，得到每個線段、圓弧段的實際坐標(biāo)尺寸（mm）信息。檢測前通過對系統(tǒng)進(jìn)行標(biāo)定，得到一個像素和實際長度mm的換算關(guān)系為0.00533mm/pixel.最終計算得到CAD標(biāo)準(zhǔn)檔中零件輪廓的重心坐標(biāo)為81105.743），主軸取向αmodel＝0，以及每部分拐點即特征點坐標(biāo)序列其中

對零件圖像進(jìn)行輪廓提取，得到的輪廓圖像如圖3所示，得到零件輪廓組成的點序列C＝｛Pi（xi，yi）｜i＝1，2，…，N｝，其中N＝13425。通過對提取出的輪廓區(qū)域進(jìn)行矩分析，得到零件圖像輪廓的重心和主軸方向如圖4所示。其 中

圖3 零件目標(biāo)輪廓

圖4 零件圖像控制點和主軸方向的提取

3.2 預(yù)匹配加入前后匹配速度穩(wěn)定性的比較

本文分別用傳統(tǒng)的RANSAC算法和加入預(yù)匹配的RANSAC算法對此零件CAD模型控制點集Vmodel和其采集到的圖像提取到的圖4（b）對應(yīng)的紅色控制點集Vobject進(jìn)行了100次匹配測試，dist＿threshold＝50，voteRateThreshold＝90%；實驗用的是Intel Core 2CPU，主頻1.83G，內(nèi)存2G，用C＋＋語言實現(xiàn)算法，得到的匹配耗時散點圖如圖5所示。從圖中可以看出，未匹配的時間分布沒有什么規(guī)律，并且大量分布在200ms以上；而加入預(yù)匹配的時間分布耗時整體偏低，并且大部分分布在10～20ms之間，速度更快。

圖5 加入預(yù)匹配前后匹配耗時散點

計算得到加入預(yù)匹配前后的100次耗時的標(biāo)準(zhǔn)差分別為128.0531ms和5.9650ms，進(jìn)一步說明加入預(yù)匹配后的匹配耗時更加穩(wěn)定。

圖6為某次預(yù)匹配的過程中dΔβi的變換規(guī)律，選取的Δφ＝3＊Δα.從Δ圖中可以看到，旋轉(zhuǎn)角度Δβ從Δα－Δφ旋轉(zhuǎn)到Δα＋Δφ的過程中，dΔβi出現(xiàn)一個最小值，對應(yīng)的角度為Δβdmin＝1.4196°.和理想角度Δα＝αobject－αmodel＝1.8402°有一定差距，但已經(jīng)非常接近，是由于零件目標(biāo)圖像的輪廓邊緣提取以及其控制點的提取誤差造成匹配角度的誤差。

圖6 dΔβi 的變化規(guī)律

4 結(jié)束語

在現(xiàn)代二次元光電檢測儀器中，快速、穩(wěn)定、準(zhǔn)確地檢測每一個工件等物體決定其檢測性能。傳統(tǒng)RANSAC算法無法穩(wěn)定快速地匹配待檢測物體圖像和其CAD標(biāo)準(zhǔn)檔，而本文加入預(yù)匹配的優(yōu)化RANSAC算法在準(zhǔn)確性前提下可以使檢測速度更快、穩(wěn)定性更好，完全達(dá)到了預(yù)期的檢測性能，實驗結(jié)果表明此算法使檢測速度顯著得到提高。在有關(guān)機(jī)器視覺的光電檢測儀器領(lǐng)域，需要檢測有CAD標(biāo)準(zhǔn)檔的物體的儀器中，對采集到的圖像和其CAD文檔之間大都可以使用這種改進(jìn)的RANSAC匹配算法進(jìn)行快速匹配檢測。所以這種匹配算法在檢測儀器中有廣泛的應(yīng)用前景。

［1］Kafieh R，Mehri A，Sadri S.Automatic landmark detection in cephalometry using a modified Active shape model with sub image matching ［C］.International Conference on Machine Vision，2007：73－78.

［2］WANG Bingqin，GUO Li，ZHENG Mai.Sub－pixel image registration algorithm in image panoramic mosaic ［J］.Computer Engineering and Application，2008，29（17）：191－194（in Chinese）.［王丙勤，郭立，鄭邁.基于特征匹配的亞像素級全景圖像配準(zhǔn)算法 ［J］.計算機(jī)工程與設(shè)計，2008，29（17）：191－194.］

［3］Marco Zuliani.RANSAc for dummies ［EB/OL］.［2011－08－06］. http：//vision.ece.ucsb.edu/～ zuliani/Research/RANSAC/docs/.

［4］CHEN Fuxing，WANG Runsheng.Fast RANSAC with preview model parameters evaluation ［J］.Journal of Software，2005，16（8）：1431－1437（in Chinese）.［陳付幸，王潤生.基于預(yù)檢驗的快速隨機(jī)抽樣一致性算法 ［J］.軟件學(xué)報，2005，16（8）：1431－1437.］

［5］Milan Sonka，Vaclav Hlavac，Ronger Boyle.Image Processing，Analysis，and Machine Vision ［M］.USA：Thomson，2008：329－323.

［6］LV Zhe，WANG Fuli，CHANG Yuqiang，et al.An improved sequential polygonal approximation algorithm on skeleton curves［J］.Acta Automatica Sinica，2008，34（12）：1467－1474（in Chinese）.［呂哲，王福利，常玉清，等.一種改進(jìn)的骨架曲線串行多邊形近似算法 ［J］.自動化學(xué)報，2008，34（12）：1467－1474.］

［7］Masood A，Haq S A.A novel approach to polygonal approximation of digital curves ［J］.Journal of Visual Communication and Image Representation，2007，18（3）：264－274.

［8］Cornea N D，Min P.Curve－skeleton properties applications and algorithms ［J］.IEEE Transactions on Visualization and Computer Graphics，2007，13（3）：530－548.

［9］Byoung Ju Yun，Jae Soo Cho，Yun Ho Ko.An efficient polygonal approximation method in the rate－distortion sense ［J］.International Journal of Information Technology，2006，12（2）：47－54.

［10］TIAN Wen，WANG Hongyuan，XU Fan，et al.Enhanced RANSAC with adaptive pre－verification ［J］.Journal of Image and Graphics，2009，14（5）：973－977（in Chinese）.［田文，王宏遠(yuǎn)，徐帆，等.RANSAC算法的自適應(yīng) Tc，d預(yù)檢驗［J］.中國圖像圖形學(xué)報，2009，14（5）：973－977.］

［11］QU Tianwei，AN Bo，CHEN Guilan.Application of improved RANSAC algorithm to image registration ［J］.Journal of Computer Applications，2010，30（7）：1849－1872（in Chinese）.［曲天偉，安波，陳桂蘭.改進(jìn)的RANSAC算法在圖像配 準(zhǔn) 中 的 應(yīng) 用 ［J］. 計 算 機(jī) 應(yīng) 用，2010，30（7）：1849－1872.］

［12］SUN Jixiang.Image analysis ［M］.Beijing：Science Press，2005：123－127（in Chinese）.［孫即祥.圖像分析 ［M］.北京：科學(xué)出版社，2005：123－127.］

［13］Peter Shirley.Fundamentals of computer graphics ［M］.GAO Chunxiao，ZHAO Qingjie，ZHANG Wenyao，transl.2nd ed.Bejing：Posts＆Telecom Press，2007：94－101（in Chinese）.［Peter Shirley.計算機(jī)圖形學(xué) ［M］.高春曉，趙清杰，張文耀，譯.2版.北京：人民郵電出版社，2007：94－101.］

［14］SUN Zhengxing，ZHOU Liang，ZHENG Hongyuan，et al.Computer graphics course ［M］.Beijing：China Machine Press，2006：104－109（in Chinese）.［孫正興，周良，鄭洪源，等.計算機(jī)圖形學(xué)教程 ［M］.北京：機(jī)械工業(yè)出版社，2006：104－109.］

［15］Andrew Mustun.DXF 庫（dxflib）使 用 指 南 ［EB/OL］.［2011－08－06］. http：//opencv－extension－library. googlecode.com/svn/doc/gdal－doc/dxf＿lib.html.

［16］RibbonSoft.DXF library ［EB/OL］.［2011－08－06］.http：//www.qcad.org/dxflib.html.