基于連通區(qū)域特征的圖像配準方法

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

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

0 引 言

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

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

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

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

1.1 圖像的二值化

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

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

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

（1）像素法：將像素點作為檢測的基本單元，計算量較大，對內存要求比較高，在對高分辨率圖像進行標記時效率低下。

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

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

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

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

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

為了便于處理，本文算法在掃描圖像時分別記錄每一行的游程鏈首尾坐標。根據幾何關系易知，假設X1s、X1e代表某一行中的一條游程鏈的起點和終點橫坐標，X2s、X2e代表下一行中一條游程鏈的起點和終點橫坐標，當二者之間同時滿足式（1）和式（2）時，即可判定二者相連通

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

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

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

步驟2：若是相連通的已標記游程鏈只存在一種標記，則將該標記值賦予該游程；否則，先將任一標記賦予當前游程鏈，再把其他標記的游程統一進行標記的整理。重復以上步驟，直至掃描完成。

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

1.3 匹配點的篩選及查找

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

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

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

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

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

1.4 仿射變換矩陣

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

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

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

即可進行圖像的轉換，將目標圖像與模板圖像進行坐標的統一。式（4）中，（x，y）與（x’，y’）分別代表目標圖像與轉換后的圖像上的對應點。

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

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

1.5 圖像的插值運算

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

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

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

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

本文采用雙線性插值法進行圖像的恢復，過程如下：根據式（4）可得下面關系

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

1.6 算法流程

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

圖1 本文算法流程

2 實驗結果與分析

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

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

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

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

圖5 PCB板圖像配準結果

表1 實驗圖像測試結果

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

3 結束語

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

［1］Seeking technology.Visual C＋ ＋ typical digital image processing algorithms and implementations［M］.Beijing：People Post Press，2006：498－501（in Chinese）.［求是科技.Visual C＋＋數字圖像處理典型算法及實現 ［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）.［劉彩云，杜宇人.一種自適應極坐標變換的旋轉圖像配準方法 ［J］.揚州大學學報（自然科學版）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）.［陽方林.高配準率快速圖像配準技術研究 ［D］.太原：中北大學碩士學位論文，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）.［孫超.圖像配準算法研究及文檔圖像配準中的應用 ［D］.成都：電子科技大學碩士學位論文，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)術導彈控制技術，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］.湖北工業(yè)大學學報，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距離的配準算法 ［C］.第十四屆全國圖象圖形學學術會議論文集.北京：清華大學出版社，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）.［魯珊，雷英杰，孔韋韋，等.基于空間點特征和改進Hausdorff距離的圖像配準方法 ［J］.系統工程與電子技術，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］.大氣與環(huán)境光學學報，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ū)域標記算法 ［J］.計算機應用，2010，6（11）：1616－1618.］

［12］ZHANG Erhu，FENG Jiang.Run－list based connected components labeling for Blob analysis ［J］.Journal of Applied Sciences，2008，26（5）：536－540（in Chinese）.［張二虎，馮江.Blob分析中基于游程鏈的連通區(qū)域標記 ［J］.應用科學學報，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ū)域標記的新算法 ［J］.計算機應用，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ū)域標記的新方法 ［J］.計算機工程與應用，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）.［張云哲，趙海，宋純賀，等.一種新的連通區(qū)域標記算法 ［J］.計算機應用研究，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.計算機圖形學幾何工具算法詳解［M］.周長發(fā)，譯.北京：電子工業(yè)出版社，2005：69－75.］