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

汪 松，王俊平，萬(wàn)國(guó)挺，王 樂

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

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

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

1 圖像匹配預(yù)處理

圖像在成像過程中易受到隨機(jī)噪聲、成像傳感器變化以及在不同時(shí)間受到不同環(huán)境的影響，使所得到的原始圖像都不是理想的待配準(zhǔn)圖像，這些圖像間的差異可能會(huì)使后面的配準(zhǔn)產(chǎn)生錯(cuò)誤的結(jié)果或無(wú)法配準(zhǔn)。所以在進(jìn)行圖像匹配之前，對(duì)原始圖像進(jìn)行預(yù)處理是非常必要的，圖像預(yù)處理也是圖像配準(zhǔn)整個(gè)過程必不可少的環(huán)節(jié)。為減少噪聲，增強(qiáng)圖像邊緣特征信息，提高匹配點(diǎn)的精度和數(shù)量，經(jīng)實(shí)驗(yàn)筆者對(duì)圖像進(jìn)行高斯和Wallis濾波處理，這樣特征提取效果較好。

1.1 高斯濾波

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

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

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

1.2 W allis濾波

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

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

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

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

2 特征點(diǎn)提取與匹配

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

從文獻(xiàn)［12］中可知尺度空間的構(gòu)造大約占總時(shí)間的30%～55%，優(yōu)化空間較大。為提高提取特征點(diǎn)的效率，筆者根據(jù)文獻(xiàn)［12］采用簡(jiǎn)化尺度空間的SIFT算法提取特征點(diǎn)，即取高斯金字塔的組數(shù)為2，每組3層的固定金字塔進(jìn)行尺度空間的構(gòu)造。表1列出了傳統(tǒng) SIFT算法和簡(jiǎn)化SIFT算法完成匹配的時(shí)間。

表1 一般SIFT和簡(jiǎn)化SIFT耗時(shí)對(duì)比Table 1 run time of SIFT and simplified SIF

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

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

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

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

3 筆者算法在優(yōu)化線網(wǎng)檢測(cè)的應(yīng)用

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

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

圖6 優(yōu)化前的線網(wǎng)Fig.6 Line network before optim ization

圖7 優(yōu)化后的線網(wǎng)Fig.7 Optim ized reticle

表2 匹配點(diǎn)對(duì)x，y坐標(biāo)與平移量Table2 the coordinates and shift ofmatched points

4 實(shí)驗(yàn)結(jié)果與結(jié)論

匹配方法的性能評(píng)價(jià)指標(biāo)有匹配正確率、匹配時(shí)間和匹配精度3方面。為驗(yàn)證筆者方法，針對(duì)有缺陷的版圖圖像從這3個(gè)方面進(jìn)行檢驗(yàn)。實(shí)驗(yàn)結(jié)果表明，該方法提取的匹配點(diǎn)在數(shù)量、準(zhǔn)確率等方面都優(yōu)于一般SIFT算法。該方法是一種有效的圖像匹配方法，具有精度高、魯棒性強(qiáng)、穩(wěn)定性高、適用性強(qiáng)等優(yōu)點(diǎn)，并在優(yōu)化線網(wǎng)檢測(cè)的應(yīng)用得到較好效果。同時(shí)，該方法為圖像拼接等相關(guān)領(lǐng)域后續(xù)產(chǎn)品的生成提供了精確的匹配點(diǎn)。在匹配時(shí)間方面由于該方法的特征點(diǎn)數(shù)量較多，所以匹配耗時(shí)較多，對(duì)該方法的實(shí)時(shí)性還需要進(jìn)一步的研究。

［1］蘇宇.基于特征點(diǎn)的圖像拼接技術(shù)研究［D］.西安:西安電子科技大學(xué)，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］王宏力，賈萬(wàn)波.圖像匹配算法研究綜述［J］.計(jì)算機(jī)技術(shù)與應(yīng)用，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，F(xiàn)rancois 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，F(xiàn)eng N.Fastwallis image enhancement algorithm with CUDA［J］.Journal of Shenyang Shenyang University of Technoloy，2011，33(3):293－298.

［12］曹世翔，江潔.一種簡(jiǎn)化SIFT的圖像配準(zhǔn)算法［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.