龔 偉，葉玉堂，張 睿，羅 穎

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

0 引 言

圖像配準(zhǔn)是對取自不同時間、不同傳感器或者不同視角的同一場景的兩幅圖像或者多副圖像匹配的過程，它被廣泛的應(yīng)用在遙感圖像、醫(yī)學(xué)影像、三維重構(gòu)、機(jī)器人視覺等諸多領(lǐng)域中［1］。在需要結(jié)合多個圖像數(shù)據(jù)源的圖像分析任務(wù)中，圖像配準(zhǔn)是最為關(guān)鍵的一步［2］，直接關(guān)系著其后處理的效率和精確度。

目前圖像配準(zhǔn)的方法總的來說有3種：基于像素灰度的圖像配準(zhǔn)，基于特征的圖像配準(zhǔn)和基于其他理論的圖像配準(zhǔn)［3－4］?；诨叶?相 關(guān) 的 匹 配 算 法［5－6］直 接 利 用 全 部 可 用的圖像灰度信息，因此能提高檢測的精度和魯棒性。但是它計(jì)算量大，難以達(dá)到實(shí)時性要求，而且一旦進(jìn)入信息貧乏的區(qū)域，會導(dǎo)致誤匹配率的上升［7］?；趫D像特征的配準(zhǔn)方法［8－9］提取了圖像的顯著特征，大大壓縮圖像的信息量，使得計(jì)算量小，速度較快，而且它對圖像灰度的變化具有魯棒性，目前被較為廣泛的應(yīng)用［7］?；谄渌碚摰膱D像配準(zhǔn)包括基于模型的匹配技術(shù)、基于解釋的圖像匹配技術(shù)、基于神經(jīng)網(wǎng)絡(luò)的匹配方法［10］等。

由于傳統(tǒng)的基于特征的圖像配準(zhǔn)算法所采用的特征點(diǎn)都需要經(jīng)過大量的計(jì)算，比如邊緣點(diǎn)、Sift角點(diǎn)、Harris角點(diǎn)等，并且在找到之后還需要利用較多補(bǔ)充信息進(jìn)行特征點(diǎn)的匹配，在高分辨率圖像或者復(fù)雜圖像的配準(zhǔn)上效率較低。為了降低算法的復(fù)雜度，提高圖像配準(zhǔn)效率，使圖像的實(shí)時性檢測得以實(shí)現(xiàn)，考慮到與模板相近似的目標(biāo)圖像采集過程中，平移、旋轉(zhuǎn)以及縮放基本不改變圖像表面的連通區(qū)域外形以及比例特征，因此本文針對具有復(fù)雜多連通區(qū)域的圖像提出了基于連通區(qū)域特征的配準(zhǔn)方法。

1 基于連通區(qū)域特征的圖像配準(zhǔn)算法

1.1 圖像的二值化

考慮到在實(shí)際的采圖過程中，在相同條件下，同一目標(biāo)在背景上的平移、旋轉(zhuǎn)以及一定的縮放基本不會改變目標(biāo)的連通區(qū)域比例和顏色屬性，可以使用固定閾值或者自適應(yīng)二值化的方法對目標(biāo)進(jìn)行二值化提取，但必須保證目標(biāo)圖像區(qū)域保持不變，不存在其他外來干擾和大的信息缺失。

1.2 連通區(qū)域的查找

迄今為止，連通區(qū)域檢測算法已經(jīng)比較完善，針對不同復(fù)雜度的圖像都有不同的解決方法?？偟膩碚f，這些算法大致可以分為3種：

（1）像素法：將像素點(diǎn)作為檢測的基本單元，計(jì)算量較大，對內(nèi)存要求比較高，在對高分辨率圖像進(jìn)行標(biāo)記時效率低下。

（2）線標(biāo)記法：將目標(biāo)區(qū)域內(nèi)的連續(xù)像素點(diǎn)構(gòu)成的線段作為檢測的基本單位，普遍具有計(jì)算量較少、占用內(nèi)存少的優(yōu)點(diǎn)?，F(xiàn)有的許多算法［11－14］對游程標(biāo)記法進(jìn)行了優(yōu)化，減少了大量冗余計(jì)算，使其具有更快的速度。

（3）面標(biāo)記法：主要包括區(qū)域增長法。基于區(qū)域生長的標(biāo)記算法不存在標(biāo)簽不連續(xù)的問題，但是僅適用于二值圖像中有少量前景像素的情況，當(dāng)前景像素在二值圖像中所占的比例較大時算法效率急劇下降［15－16］。

考慮到游程法的優(yōu)點(diǎn)，本文用該方法對圖像的連通區(qū)域進(jìn)行檢測。通過將連通區(qū)域的重心作為圖像的特征點(diǎn)，面積等屬性作為篩選條件來完成圖像的匹配。

1.2.1 基于游程鏈的連通區(qū)域檢測算法

在圖像處理中，游程編碼是將一系列重復(fù)的像素點(diǎn)值使用該值和一個計(jì)數(shù)值進(jìn)行表示，例如數(shù)據(jù) ｛255，255，255，0，0，0，0｝，可表示為 ｛3，255，4，0｝，可見，游程編碼的位數(shù)遠(yuǎn)遠(yuǎn)少于原始字符串的位數(shù)。同時，判斷游程的連通性問題也就轉(zhuǎn)變?yōu)榕袛嘤纬涕g首尾元素的相鄰性問題，相對來說計(jì)算簡單且計(jì)算量少。

為了便于處理，本文算法在掃描圖像時分別記錄每一行的游程鏈?zhǔn)孜沧鴺?biāo)。根據(jù)幾何關(guān)系易知，假設(shè)X1s、X1e代表某一行中的一條游程鏈的起點(diǎn)和終點(diǎn)橫坐標(biāo)，X2s、X2e代表下一行中一條游程鏈的起點(diǎn)和終點(diǎn)橫坐標(biāo)，當(dāng)二者之間同時滿足式（1）和式（2）時，即可判定二者相連通

對圖像按照從上至下的順序進(jìn)行掃描，每次只需判定當(dāng)前游程鏈與上一行游程鏈的連通性情況，并加以歸納處理，直至掃描完成即可完成所有連通區(qū)域的標(biāo)記。

以二值圖像為例，0代表背景像素，1代表前景像素。定義值m＝0作為標(biāo)記的起始值。

步驟1：對當(dāng)前行（假設(shè)為第n行）進(jìn)行掃描，獲取游程的首尾位置坐標(biāo)，根據(jù)式（1）和式（2）得到該游程與（n－1）行游程鏈間的連通關(guān)系，如果無連通，則將m作為標(biāo)記賦予當(dāng)前游程，記為 ｛X，Y，m｝，同時m＋1；否則，進(jìn)入步驟2。

步驟2：若是相連通的已標(biāo)記游程鏈只存在一種標(biāo)記，則將該標(biāo)記值賦予該游程；否則，先將任一標(biāo)記賦予當(dāng)前游程鏈，再把其他標(biāo)記的游程統(tǒng)一進(jìn)行標(biāo)記的整理。重復(fù)以上步驟，直至掃描完成。

步驟3：根據(jù)完成的游程鏈標(biāo)記值來計(jì)算連通區(qū)域的屬性。計(jì)算連通區(qū)域的面積，只需統(tǒng)計(jì)所有屬于這個連通區(qū)域的游程所代表的像素?cái)?shù)目之和；計(jì)算連通區(qū)域的重心縱坐標(biāo)，首先需要計(jì)算每個游程的長度與其所在行數(shù)的乘積，然后將所有的乘積加起來，最后除以總的像素?cái)?shù)；連通區(qū)域的重心橫坐標(biāo)即為所有屬于這個連通區(qū)域的游程所代表的像素橫坐標(biāo)之和與連通區(qū)域面積的商［12］。

1.3 匹配點(diǎn)的篩選及查找

為了獲得相匹配的特征點(diǎn)對，本文算法對檢測到的連通區(qū)域按照其屬性進(jìn)行了多重篩選，具體步驟如下。

步驟1：根據(jù)連通區(qū)域的面積按照從大到小的順序進(jìn)行排序，同時舍去一些小面積區(qū)域。

步驟2：連通區(qū)域分組。由于不同圖像之間難免存在差別，相似的連通區(qū)域之間可能造成匹配錯誤，因此對排序過的連通區(qū)域?qū)傩詳?shù)組進(jìn)行分割。若當(dāng)前元素與上一元素的面積比小于一定閾值θ時，將數(shù)組分割開；否則，將該元素與上一元素添加在同一個數(shù)組里。重復(fù)此過程，直至數(shù)組全部處理完畢。這一方法避免了相似區(qū)域之間存在的錯位可能，使得匹配點(diǎn)的查找更準(zhǔn)確。

步驟3：根據(jù)面積以及數(shù)組長度進(jìn)行初步匹配。比較模板圖像與待配準(zhǔn)圖像對應(yīng)的數(shù)組集合，對于第一組對應(yīng)點(diǎn)的選取，當(dāng)兩個集合中的第一個數(shù)組包含的元素?cái)?shù)目一樣，且平均面積之比約等于圖像面積比，則認(rèn)為這兩個數(shù)組滿足匹配條件，否則認(rèn)為圖像有較大差異存在。取這兩個數(shù)組包含的元素的坐標(biāo)平均值作為匹配點(diǎn)對。由于同一幅圖像中的連通區(qū)域比例應(yīng)該保持不變，對其后的對應(yīng)點(diǎn)的選取按照同一圖像中的面積比進(jìn)行篩選。設(shè)待配準(zhǔn)圖像上的一個待篩選數(shù)組平均面積與其上一已匹配區(qū)域面積之比為scale1，模板圖像上的對應(yīng)待篩選數(shù)組平均面積與其上對應(yīng)的已匹配區(qū)域面積之比為scale2，如果scale1/scale2∈（1－α，1＋α）則認(rèn)為兩個數(shù)組初步匹配，其中α為選取的誤差范圍值。取相匹配數(shù)組包含的元素的坐標(biāo)平均值作為匹配點(diǎn)對。循環(huán)此過程，最終獲得匹配點(diǎn)組。

步驟4：根據(jù)已得匹配點(diǎn)間的距離屬性進(jìn)行進(jìn)一步篩選。由于在小面積區(qū)域出現(xiàn)錯誤匹配點(diǎn)的可能性比較大，將第一組匹配點(diǎn)以外的點(diǎn)對與第一組點(diǎn)對進(jìn)行比較，分別在兩幅圖像中計(jì)算兩條線段的長度，由簡單的幾何關(guān)系易知二者應(yīng)該滿足圖像間的縮放比例。由此最終篩選出符合條件的匹配點(diǎn)。

1.4 仿射變換矩陣

仿射變換是將一個仿射空間中的點(diǎn)和向量分別對應(yīng)到另一個仿射空間中的點(diǎn)和向量的映射。由于仿射變換將點(diǎn)映射到點(diǎn)，因此它也將線段映射到線段，將面映射到面，等等［17］。在線性代數(shù)中，線性變換能夠用矩陣表示。如果T是一個把Rn映射到Rm的線性變換，且珝x是一個具有n個元素的列向量，那么T（珝x）＝A珝x。我們把m×n的矩陣A，稱為T的變換矩陣。二維圖像的仿射變換可以用一個3×3的矩陣來表示

其中（x1，y1）與（x’1，y’1）代表目標(biāo)圖像與模板圖像上的對應(yīng)點(diǎn)對，以此類推。將上式表示為T’＝T＊H，根據(jù)矩陣的逆運(yùn)算可求得變換矩陣H：H＝T－1＊T’。

按照1.3中的方法得出匹配點(diǎn)組，將其中的數(shù)據(jù)代入式（3）中，從而求得變換矩陣H。再根據(jù)下式

即可進(jìn)行圖像的轉(zhuǎn)換，將目標(biāo)圖像與模板圖像進(jìn)行坐標(biāo)的統(tǒng)一。式（4）中，（x，y）與（x’，y’）分別代表目標(biāo)圖像與轉(zhuǎn)換后的圖像上的對應(yīng)點(diǎn)。

由于最終得出的匹配點(diǎn)對可能超出3組，而仿射變換矩陣中只用到3組，為了進(jìn)一步提高精度，從而得到最佳矩陣，采用最小均方根誤差法（RMSE）

式中：n——所得匹配點(diǎn)對的數(shù)目，（xi，yi）——模板圖上的點(diǎn)，（xi’，y’i）——與（xi，yi）相匹配的目標(biāo)圖像上的點(diǎn)經(jīng)過仿射變換后得到的坐標(biāo)。求出C3n個仿射變換矩陣，并得到這些矩陣對應(yīng)的ε值，將最小的ε值對應(yīng)的矩陣作為最終結(jié)果用于圖像的恢復(fù)。

1.5 圖像的插值運(yùn)算

由于配準(zhǔn)后所得出的像素坐標(biāo)位置可能不在整數(shù)像素上，因此需要用灰度插值的方法對像素值進(jìn)行估計(jì)。常用的方法包括最近鄰法、雙線性插值法、三次立方卷積插值法。假設(shè)目標(biāo)像素經(jīng)過反向變換得到在源圖上的對應(yīng)浮點(diǎn)坐標(biāo)（i＋u，j＋v）。

最鄰近法將源圖像上距離（i＋u，j＋v）最近的點(diǎn)的像素值作為目標(biāo)點(diǎn)像素值，該方法速度最快，但縮放質(zhì)量差，圖像容易出現(xiàn)鋸齒和失真。三次立方卷積插值法以（i＋u，j＋v）周圍4×4范圍內(nèi)的像素做插值運(yùn)算，圖像質(zhì)量最好，但計(jì)算量最大，速度最慢。

雙線性插值法通過（i＋u，j＋v）這4個近鄰坐標(biāo)的像素值來計(jì)算目標(biāo)像素值，設(shè)4個近鄰坐標(biāo)為（i，j）、（i＋1，j）、（i，j＋1）、（i＋1，j＋1），則目標(biāo)像素值為

式中：f（i，j）——源圖像（i，j）處的像素值，以此類推。該方法速度相對最鄰近法慢，但圖像質(zhì)量較好，圖像平滑，不過會造成輪廓模糊。

本文采用雙線性插值法進(jìn)行圖像的恢復(fù)，過程如下：根據(jù)式（4）可得下面關(guān)系

將設(shè)定的轉(zhuǎn)換圖像上的像素坐標(biāo)反射到源圖像上，若是浮點(diǎn)坐標(biāo)，且周圍4個近鄰像素值不完全相同，則根據(jù)式（5）獲取像素值，否則直接將任一近鄰值賦予該坐標(biāo)。重復(fù)此過程，直至所有坐標(biāo)像素值獲取完畢。

1.6 算法流程

綜上，本文算法流程圖如圖1所示。

圖1 本文算法流程

2 實(shí)驗(yàn)結(jié)果與分析

為了評價本文算法的執(zhí)行效果，選取了兩幅灰度化圖像進(jìn)行測試，分別對其進(jìn)行旋轉(zhuǎn)、平移、縮放的組合變換，然后使用本文算法對圖像進(jìn)行恢復(fù)，最后將通過雙線性插值算法獲得的圖像與模板圖像進(jìn)行相減，以相減后的圖像效果以及算法中通過最小均方根誤差法得出的結(jié)果ε作為評價的標(biāo)準(zhǔn)。

算法均以C＃語言編寫，在Visual Studio 2010平臺上進(jìn)行測試，硬件配置為 AMD Athlon 64 2.2GHz處理器，1.00GB內(nèi)存，Windows XP系統(tǒng)。測試圖如下，其中圖2為數(shù)字圖像處理中常用的lena圖3為Lena圖配準(zhǔn)結(jié)果，圖4為實(shí)際采集的PCB電路板圖，具體實(shí)驗(yàn)結(jié)果見表1。

上述圖片經(jīng)過RMSE方法計(jì)算所得結(jié)果ε∈（0，1），說明配準(zhǔn)精度基本控制在1個像素以內(nèi)。將上述配準(zhǔn)結(jié)果圖放縮到原始大小后可以看出，配準(zhǔn)結(jié)果基本恢復(fù)了圖像的位置，與源圖可以保持一致。

同時也可以看出，待配準(zhǔn)圖與模板圖的匹配點(diǎn)對較少，配準(zhǔn)結(jié)果圖的白色線條基本處于邊緣部位，這主要是由于本文待配準(zhǔn)圖像在變換過程中產(chǎn)生了一定的畸變，無法完全保持不變，且本文在算法中設(shè)置的各種閾值比較嚴(yán)格，實(shí)際檢測過程中可以根據(jù)圖像特點(diǎn)適當(dāng)調(diào)整；此外，由于雙線性插值算法的局限性造成了圖像邊緣的細(xì)節(jié)丟失，因此配準(zhǔn)結(jié)果中邊緣殘留較多，實(shí)際恢復(fù)圖像可以根據(jù)需要采取三次立方卷積插值等更高精度的圖像復(fù)原方法。

圖5 PCB板圖像配準(zhǔn)結(jié)果

表1 實(shí)驗(yàn)圖像測試結(jié)果

通過大量實(shí)驗(yàn)證明，本文算法是有效的，在算法效率方面具有一定優(yōu)勢，配準(zhǔn)后的圖像可以與模板圖像保持一致。

3 結(jié)束語

本文提出了一種基于連通區(qū)域特征的圖像配準(zhǔn)算法，能夠矯正具有復(fù)雜多連通區(qū)域的圖像位置。由于使用了連通區(qū)域的屬性特征作為配準(zhǔn)的參考依據(jù)，當(dāng)要確定兩幅圖像的特征點(diǎn)對應(yīng)關(guān)系時相對于傳統(tǒng)的基于特征點(diǎn)的圖像配準(zhǔn)方法具有更大優(yōu)勢，降低了算法復(fù)雜度和計(jì)算量，提高了檢測效率。理論分析和實(shí)驗(yàn)證明，本文方法是切實(shí)可行的，不僅檢測速度較快，而且具有較高的精確度，在工業(yè)產(chǎn)品的外觀檢測等領(lǐng)域中具有應(yīng)用價值。

［1］Seeking technology.Visual C＋ ＋ typical digital image processing algorithms and implementations［M］.Beijing：People Post Press，2006：498－501（in Chinese）.［求是科技.Visual C＋＋數(shù)字圖像處理典型算法及實(shí)現(xiàn) ［M］.北京：人民郵電出版社，2006：498－501.］

［2］LIU Caiyun，DU Yuren.Rotated image registration using adaptive polar transform ［J］.Journal of Yangzhou University（Natural Science Edition），2011，14（1）：65－69（in Chinese）.［劉彩云，杜宇人.一種自適應(yīng)極坐標(biāo)變換的旋轉(zhuǎn)圖像配準(zhǔn)方法 ［J］.揚(yáng)州大學(xué)學(xué)報(bào)（自然科學(xué)版）2011，14（1）：65－69.］

［3］YANG Fanglin.Study on image registration techniques with higher registration ratio and velocity ［D］.Taiyuan：Master＇s Degree Thesis in the University of North，2005：1－3（in Chinese）.［陽方林.高配準(zhǔn)率快速圖像配準(zhǔn)技術(shù)研究 ［D］.太原：中北大學(xué)碩士學(xué)位論文，2005：1－3.］

［4］SUN Chao.A study of image registration algorithms and applications of document image registration［D］.Chengdu：Master＇s Degree Thesis in the University of Electronic Science and Technology，2009：1－8（in Chinese）.［孫超.圖像配準(zhǔn)算法研究及文檔圖像配準(zhǔn)中的應(yīng)用 ［D］.成都：電子科技大學(xué)碩士學(xué)位論文，2009：1－8.］

［5］（Xuhua Huang.Fast image matching algorithm based on gray Level［J］.Control Technology of Tactical Missile，2005，4（51）：25－27（in Chinese）.［黃旭華.基于灰度的圖像快速匹配算法 ［J］.戰(zhàn)術(shù)導(dǎo)彈控制技術(shù)，2005，4（51）：25－27.］

［6］LUO Jianwen，Konofagou E E.A fast normalized cross－correlation calculation method for motion estimation［J］.IEEE Trans Ultrason Ferroelectr Freq Control，2010，57（6）：1347－1357.

［7］XIONG Ling.A survey of image matching in computer vision［J］.Journal of Hubei University of Technology，2006，21（3）：171－173（in Chinese）.［熊凌.計(jì)算機(jī)視覺中的圖像匹配綜述［J］.湖北工業(yè)大學(xué)學(xué)報(bào)，2006，21（3）：171－173.］

［8］SONG Yuncen，YE Yutang，LUO Ying，et al.A registration algorithm based on color image processing and Hausdorff distance measure［C］.The 14th National Conference Proceedings of Image and Graphics.Beijing：Tsinghua University Press，2008：525－528（in Chinese）.［宋昀岑，葉玉堂，羅穎，等.一種基于彩色圖像處理和Hausdorff距離的配準(zhǔn)算法 ［C］.第十四屆全國圖象圖形學(xué)學(xué)術(shù)會議論文集.北京：清華大學(xué)出版社，2008：525－528.］

［9］LU Shan，LEI Yingjie，KONG Weiwei，et al.Image registration method based on key point feature and improved Hausdorff distance［J］.Systems Engineering and Electronics，2011，33（7）：1664－1667（in Chinese）.［魯珊，雷英杰，孔韋韋，等.基于空間點(diǎn)特征和改進(jìn)Hausdorff距離的圖像配準(zhǔn)方法 ［J］.系統(tǒng)工程與電子技術(shù)，2011，33（7）：1664－1667.］

［10］WANG Jun，ZHANG Mingzhu.Progress on image matching algorithm ［J］.Journal of Atmospheric and Environmental Optics，2007，2（1）：11－15（in Chinese）.［王軍，張明柱.圖像匹配算法的研究進(jìn)展 ［J］.大氣與環(huán)境光學(xué)學(xué)報(bào)，2007，2（1）：11－15.］

［11］SHEN Qiaonan，AN Xuehui.Connected component labeling algorithm based on run recursive method［J］.Computer Applications，2010，6（11）：1616－1618（in Chinese）. ［沈喬楠，安雪暉.基于游程遞歸的連通區(qū)域標(biāo)記算法 ［J］.計(jì)算機(jī)應(yīng)用，2010，6（11）：1616－1618.］

［12］ZHANG Erhu，F(xiàn)ENG Jiang.Run－list based connected components labeling for Blob analysis ［J］.Journal of Applied Sciences，2008，26（5）：536－540（in Chinese）.［張二虎，馮江.Blob分析中基于游程鏈的連通區(qū)域標(biāo)記 ［J］.應(yīng)用科學(xué)學(xué)報(bào)，2008，26（5）：536－540.］

［13］GAO Hongbo，WANG Weixing.New connected component labeling algorithm for binary image ［J］.Computer Applications，2007，27（11）：2776－2785（in Chinese）.［高紅波，王衛(wèi)星.一種二值圖像連通區(qū)域標(biāo)記的新算法 ［J］.計(jì)算機(jī)應(yīng)用，2007，27（11）：2776－2785.］

［14］HE Lifeng，CHAO Yuyan，Kenji Suzuki.A run－based onescan labeling algorithm ［C］.Proceedings of the 6th International Conference on Image Analysis and Recognition.Berlin：Springer，2009：93－102.

［15］CHEN Baisheng.A new algorithm for binary connected components labeling［J］.Computer Engineering and Applications，2006，42（25）：46－47（in Chinese）.［陳柏生.一種二值圖像連通區(qū)域標(biāo)記的新方法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42（25）：46－47.］

［16］ZHANG Yunzhe，ZHAO Hai，SONG Chunhe，et al.New method for component－labeling in binary image［J］.Application Research of Computers，2010，27（11）：4335－4337（in Chinese）.［張?jiān)普?，趙海，宋純賀，等.一種新的連通區(qū)域標(biāo)記算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（11）：4335－4337.］

［17］Philip J Schneider，David H Eberly.Geometric tools for computer graphics［M］.ZHOU Changfa，transl.Beijing：Electronics Industry Press，2005：69－75（in Chinese）.［Philip J Schneider，David H Eberly.計(jì)算機(jī)圖形學(xué)幾何工具算法詳解［M］.周長發(fā)，譯.北京：電子工業(yè)出版社，2005：69－75.］