基于SIFT算法的圖像匹配方法

汪 松，王俊平，萬國挺，王 樂

(西安電子科技大學通信工程學院，西安710071)

近年來，隨著匹配技術的迅猛發展，圖像匹配在全景圖合成、物體3D重建、航空攝影測量、三維地圖制作等領域具有廣泛應用［1］。因此針對圖像匹配技術的研究從未停止。

目前圖像匹配方法分為基于灰度的圖像匹配方法［2］、基于特征的圖像匹配方法［3］和基于解釋的圖像匹配算法［4］。文獻［2－5］詳細介紹了基于灰度的匹配方法，但這種方法對圖像變形、光照、尺度變化等情況有一定的敏感性。因此不具有適用性。由于基于解釋的圖像匹配算法應用較少，并且該方法需要建立在圖像自動判讀的專家系統上，目前還沒有取得突破性的進展。基于特征的圖像匹配方法，如 CCH算法［6］、Harris算法［7］、SIFT算法［8］等都能夠較好的適應圖像變形、光照變化等情況，而且技術比較成熟。Mikolajczyk等［9］對以上算法做了系統的比較，結果表明SIFT算法檢測效果最好。但SIFT算法存在匹配點數量有限、算法效率低、精度差、并且在特征點分布均勻的情況下正確匹配率低。人們提出了很多的匹配方法以解決上述問題帶來的匹配困難。根據Brown［10］理論，各種匹配方法都是特征空間、相似性度量、搜索空間和搜索策略4個關鍵要素的不同選擇組合。因此，筆者依據Brown理論，在設計匹配方法時，首先在特征點提取前對待匹配圖像進行匹配預處理，然后基于簡化SIFT算法在搜索策略方面進行了改進，采用KD樹雙向匹配方法，在匹配點數量、匹配點的精度和匹配重復點方面都有所提高。筆者通過對有共同缺陷的版圖進行圖像匹配實驗，并驗證得到了較好的效果，最后將該方法應用于優化版圖的線網自動檢測方面，進一步驗證了該方法的適用性。試驗證明該方法不僅滿足圖像拼接等相關領域對匹配技術高精度、高準確率的要求，而且在集成電路版圖優化線網檢測領域也有較好的適用性。

1 圖像匹配預處理

圖像在成像過程中易受到隨機噪聲、成像傳感器變化以及在不同時間受到不同環境的影響，使所得到的原始圖像都不是理想的待配準圖像，這些圖像間的差異可能會使后面的配準產生錯誤的結果或無法配準。所以在進行圖像匹配之前，對原始圖像進行預處理是非常必要的，圖像預處理也是圖像配準整個過程必不可少的環節。為減少噪聲，增強圖像邊緣特征信息，提高匹配點的精度和數量，經實驗筆者對圖像進行高斯和Wallis濾波處理，這樣特征提取效果較好。

1.1 高斯濾波

高斯濾波的實現方法比較常見，這里不再累述，把處理前后的圖像列出，如圖1是一幅480× 421像素的缺陷版圖。高斯濾波后的圖像如圖2所示。直觀上看，圖2的噪聲已被濾除，但邊緣有些模糊，這是后續進行Wallis濾波所需步驟，實驗結果表明這樣的預處理效果提高了圖像匹配點數量和精度，并不影響原始圖像的邊緣信息和匹配點在原始圖像上的顯示。

圖1 高斯濾波前缺陷版圖Fig.1 The former defects territory of the Gaussian filter

圖2 高斯濾波后版圖圖像Fig.2 The Gaussian filtered territory image

1.2 W allis濾波

高斯濾波后的圖像存在一定程度的邊緣模糊等問題?？紤]到Wallis濾波是一種局部的影像變換，它可增強影像的紋理模式和影像反差同時壓制噪聲，提高了影像的信噪比。因此筆者采用Wallis濾波器處理圖像2。Wallis濾波器的一般形式為［11］:

其中g(x，y)為原始圖像的灰度值;f(x，y)為Wallis濾波后圖像的灰度值;mg為原始圖像的局部灰度均值;sg為原始圖像的局部灰度方差值;mf為結果圖像局部灰度均值的目標值;sf為結果圖像局部灰度方差值的目標值;c∈［0，1］為圖像反差的擴展常數;b∈［0，1］為圖像的亮度系數。

圖3為Wallis濾波后圖像?？砂l現圖2模糊的邊緣信息經過濾波后邊緣更加突出、版圖缺陷更加明顯、紋理更加清晰，這為特征點的提取提供了更多的點、邊緣等特征信息。

圖3 W allis濾波后版圖效果圖Fig.3 W allis filtered territory effect diagram

2 特征點提取與匹配

SIFT算法分為構造尺度空間、極值點檢測、精確確定極值點位置、特征點方向分配、生成特征點描述子［8］5個步驟。

從文獻［12］中可知尺度空間的構造大約占總時間的30%～55%，優化空間較大。為提高提取特征點的效率，筆者根據文獻［12］采用簡化尺度空間的SIFT算法提取特征點，即取高斯金字塔的組數為2，每組3層的固定金字塔進行尺度空間的構造。表1列出了傳統 SIFT算法和簡化SIFT算法完成匹配的時間。

表1 一般SIFT和簡化SIFT耗時對比Table 1 run time of SIFT and simplified SIF

從表1可看出簡化SIFT的耗時為一般方法的1/2，在算法效率方面有所提高。實驗驗證簡化后的SIFT算法提高了效率，而且特征點的數量并不比一般SIFT算法少很多。

一般特征點匹配采用單向匹配方法，匹配方法簡便，但容易產生誤匹配，而且由于一個特征點可能具有多個方向，在匹配時可能產生重復的匹配點。筆者為提高圖像匹配的準確率，采取雙向匹配方法，即基于單向匹配結果，反過來求第2個特征集中已被匹配的特征點在第1個特征點集中匹配點，距離比小于某個閾值的特征點為正確匹配點［13］。雙向匹配方法既去除了重復匹配點，又提高了匹配準確率。圖4為一般SIFT算法對缺陷版圖提取特征點的圖像效果，共得到802對匹配點，經過RANSAC剔除后有665對正確匹配點。圖5為筆者方法提取特征點的圖像效果，共得到2659對匹配點，無錯匹配點。

圖4 一般SIFT方法缺陷版圖匹配效果Fig.4 The general SIFT method defects territory matching effect

圖5 筆者方法缺陷版圖匹配效果Fig.5 The author method defects territorymatching effect

3 筆者算法在優化線網檢測的應用

隨著集成電路復雜度與芯片面積的增加和亞波長光刻技術的廣泛應用，導致集成電路(IC)成品率降低，進一步影響了半導體產品市場競爭和質量［14］。版圖優化的目標是在不改變電路性能的情況下，調整版圖上的布線使關鍵面積降低，從而提高其成品率，因此，版圖優化對提高IC成品率具有重要的研究意義［15］。

版圖優化主要是通過對版圖結構和線網位置的改變來達到減小面積、延遲和功耗的目的。對于優化后的版圖進行移動線網的檢測也是版圖優化中不可缺少的步驟。筆者通過該方法對優化前和優化后的版圖進行圖像匹配，然后以匹配點對的位置關系檢測移動的線網。如圖6為優化前的版圖，圖6中綠色線框內是需要優化的線網，圖7為線網移動后的優化版圖。同圖6相比圖7中的線網進行了簡單的平移，先通過該方法對圖6和圖7進行匹配，然后根據線網上的一對匹配點R-1、L-1的坐標關系可以檢測出線網在x，y方向的平移量。如表2所示，列出了x，y的坐標和平移量，以像素為單位。

圖6 優化前的線網Fig.6 Line network before optim ization

圖7 優化后的線網Fig.7 Optim ized reticle

表2 匹配點對x，y坐標與平移量Table2 the coordinates and shift ofmatched points

4 實驗結果與結論

匹配方法的性能評價指標有匹配正確率、匹配時間和匹配精度3方面。為驗證筆者方法，針對有缺陷的版圖圖像從這3個方面進行檢驗。實驗結果表明，該方法提取的匹配點在數量、準確率等方面都優于一般SIFT算法。該方法是一種有效的圖像匹配方法，具有精度高、魯棒性強、穩定性高、適用性強等優點，并在優化線網檢測的應用得到較好效果。同時，該方法為圖像拼接等相關領域后續產品的生成提供了精確的匹配點。在匹配時間方面由于該方法的特征點數量較多，所以匹配耗時較多，對該方法的實時性還需要進一步的研究。

［1］蘇宇.基于特征點的圖像拼接技術研究［D］.西安:西安電子科技大學，2008.

SU Yu.Research on image mosaic based on feature points［D］.Xi’an:Xidian University，2008.

［2］Mortani M，Sationh F.Image template matching based on ratio ofmean and cent－ral pixel in local area［J］. Proceedings of the SPIE－The International Society for Optical Engineering，2007，67(94):1－6.

［3］Barbara Zitova，Jan Flusser.Image registr－ation methods:a survery［J］.Image and Vis－ion Computing，2003，21(11):977－100.

［4］王宏力，賈萬波.圖像匹配算法研究綜述［J］.計算機技術與應用，2008(6):17－19.

Wang Hong－Li，Jia Wan－bo.Study on image matching algorithm［J］.Progress of comp－uter technology and Application，2008(6):17－19.

［5］Shimizu Masao，Okutomi Masatoshi.Multi－Parameter simultaneous estimationg on area－based matching［J］. International Journal of Computer Vision，2006，67 (3):327－342.

［6］C R Huang，C SChen，PC Chung.Contrast context histogram－A discriminating local descriptor for imagematching［J］.International Conference on Pattern Recognition，2006(4):53－56.

［7］Marco Loog，Francois Lauze.The improbability of harris interest points［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(6):1141－1147.

［8］Lowe D G.Distinctive image features from scale－invariant keypoints［J］.Inter－national Journal of Computer Vision，2004，60(2):91－110.

［9］Mikolajczyk K，Schmid C.A performance evaluation of local descriptor［J］.IEEE Transactions on Pattern A－nalysis and Ma－chine Intelligenee，2005，27(10):1615－1630.

［10］Brown LG.A survey of image registrati－on technique［J］. ACM Computing Surverys，1992，24(4):325－376.

［11］Han X，Wu QS，Feng N.Fastwallis image enhancement algorithm with CUDA［J］.Journal of Shenyang Shenyang University of Technoloy，2011，33(3):293－298.

［12］曹世翔，江潔.一種簡化SIFT的圖像配準算法［J］.紅外與激光工程，2010(4):35－39.

Cao SX，Jiang J.A simplified SIFT algorithm for image registration［J］.Infra－red and Laser Engineering，2010 (4):35－39.

［13］Iftikhar Hussain，Muhammad Zubair，Jamil Ahmed.Bidirectional exact pattern matching algorithm［C］//Modern Problems of Radio Engineering，Telecommunicaions and Computer science.Ukraine，2010:293－296.

［14］Wang Jun－ping，Hao Yue.Short critical area computationalmethod usingmath－ematicalmorphology［J］.CIS，2005，38(2):796－803.

［15］Barnt T S，Bickford J，Weger a J.Product yield prediction system and critical area database［C］//Advanced emiconductor Man－uacturing Conference，2007:351－355.