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

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

0 引 言

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

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

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

1 輪廓曲線特征點(diǎn)提取

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

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

1.2 多邊形遞歸逼近算法

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

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

定義2 線段L由C中兩個(gè)不同的點(diǎn)Pi和Pi＋k唯一確定，

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

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

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

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

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

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

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

Output：近似多邊形的頂點(diǎn)序列，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；對(duì)點(diǎn)序列C0＝｛Pi（xi，yi）｜i＝left，left＋1，…，right｝，如果-Pk∈C0，使得max（D（Pk，Lk））＞，其中則將Pk壓入點(diǎn)數(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：對(duì)C0L，令C0＝C0L，即right＝k－1；對(duì)C0R，令C0＝C0R，即left＝k。繼續(xù)執(zhí)行步驟2；

步驟4：輸出V。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟4：對(duì)Vmodel中每個(gè)特征點(diǎn)作一次平移變換

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

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

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

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

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

步驟10：輸出Mbest和。

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

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

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

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

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

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

圖4 零件圖像控制點(diǎn)和主軸方向的提取

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

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

圖5 加入預(yù)匹配前后匹配耗時(shí)散點(diǎn)

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

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

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

4 結(jié)束語(yǔ)

在現(xiàn)代二次元光電檢測(cè)儀器中，快速、穩(wěn)定、準(zhǔn)確地檢測(cè)每一個(gè)工件等物體決定其檢測(cè)性能。傳統(tǒng)RANSAC算法無(wú)法穩(wěn)定快速地匹配待檢測(cè)物體圖像和其CAD標(biāo)準(zhǔn)檔，而本文加入預(yù)匹配的優(yōu)化RANSAC算法在準(zhǔn)確性前提下可以使檢測(cè)速度更快、穩(wěn)定性更好，完全達(dá)到了預(yù)期的檢測(cè)性能，實(shí)驗(yàn)結(jié)果表明此算法使檢測(cè)速度顯著得到提高。在有關(guān)機(jī)器視覺的光電檢測(cè)儀器領(lǐng)域，需要檢測(cè)有CAD標(biāo)準(zhǔn)檔的物體的儀器中，對(duì)采集到的圖像和其CAD文檔之間大都可以使用這種改進(jìn)的RANSAC匹配算法進(jìn)行快速匹配檢測(cè)。所以這種匹配算法在檢測(cè)儀器中有廣泛的應(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）.［王丙勤，郭立，鄭邁.基于特征匹配的亞像素級(jí)全景圖像配準(zhǔn)算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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）.［陳付幸，王潤(rùn)生.基于預(yù)檢驗(yàn)的快速隨機(jī)抽樣一致性算法 ［J］.軟件學(xué)報(bào)，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］.自動(dòng)化學(xué)報(bào)，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ù)檢驗(yàn)［J］.中國(guó)圖像圖形學(xué)報(bào)，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ì) 算 機(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ì)算機(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ì)算機(jī)圖形學(xué)教程 ［M］.北京：機(jī)械工業(yè)出版社，2006：104－109.］

［15］Andrew Mustun.DXF 庫(kù)（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.