師 碩，于 明，于洪麗，閻 剛，薛翠紅

(河北工業(yè)大學(xué)a.計(jì)算機(jī)科學(xué)與軟件學(xué)院;b.國際合作與交流處;c.電氣工程學(xué)院，天津300130)

責(zé)任編輯:任健男

SIFT(Scale Invariant Feature Transform)算法是Lowe在1999年提出的一種特征點(diǎn)提取算法[1]，此算法在圖像局部特征研究過程中具有里程碑的作用。Lowe采用DoG(Difference of Gaussians)算法來快速求解高斯拉普拉斯空間中的極值點(diǎn)，加快了特征提取的速度，并在2004年對此算法進(jìn)行完善總結(jié)，將特征點(diǎn)檢測、特征矢量生成和特征匹配等過程完整地結(jié)合在一起進(jìn)行優(yōu)化[2]。SIFT算法對圖像尺度變化和旋轉(zhuǎn)變化具有不變性，并且對圖像變形和光照變化有較強(qiáng)的穩(wěn)定性，能夠在光照、分辨率、圖像畸形、旋轉(zhuǎn)、壓縮等變化的條件下，保證特征描述符不變，從而提高圖像匹配的魯棒性。因此，SIFT算法已被廣泛應(yīng)用到計(jì)算機(jī)視覺的諸多領(lǐng)域，如圖像重建[3]、全景圖拼接[4-5]及遙感圖像配準(zhǔn)[6]等。

雖然SIFT算法具有上述的優(yōu)點(diǎn)，但其算法復(fù)雜，而且特征描述符是高達(dá)128維的特征向量，使得圖像匹配時(shí)速度較慢，很難滿足實(shí)時(shí)性要求。降低維數(shù)是解決SIFT算法匹配效率低的一種方法，Ke[7]等人在SIFT基礎(chǔ)上提出了PCA-SIFT算法，首先利用主成分分析(PCA)算法對大量特征點(diǎn)的鄰域梯度進(jìn)行統(tǒng)計(jì)分析，生成低維的特征空間;然后把特征點(diǎn)的鄰域梯度向量映射到生成的低維空間中，產(chǎn)生一個(gè)低維的描述向量，最終將128維高維特征降低到20維，提高了匹配效率。但PCA算法要求樣本數(shù)據(jù)呈橢圓分布，且建立的是線性模型，對于非線性的高維數(shù)據(jù)，效果不及SIFT算法[8]。于麗莉[9]提出基于圖像Radon變換的改進(jìn)SIFT特征匹配算法，首先在圖像的SIFT特征點(diǎn)區(qū)域內(nèi)作一系列不同方向的直線，然后以這些直線上的圖像Radon變換作為SIFT特征向量描述符并對其進(jìn)行降維，文中最后得到24維特征描述符。但此方法中所用多條直線之間的夾角值的選取沒有確定標(biāo)準(zhǔn)，因此不能判斷降維后的特征描述符的最佳維度。本文在分析SIFT匹配過程的基礎(chǔ)上，提出用街區(qū)距離和棋盤距離的線性組合來代替歐氏距離，作為特征描述符之間的相似性度量，在不影響算法魯棒性的情況下，減少了匹配時(shí)間，提高了算法的效率。

1 匹配原理及常用距離

1.1 匹配的基本原理

當(dāng)確定圖像特征點(diǎn)并生成特征描述符后，就要按照相似性度量進(jìn)行特征點(diǎn)匹配。適宜的相似性度量方法不僅能夠提高匹配效果，同時(shí)還能降低度量算法的時(shí)間復(fù)雜度，通常采用相似距離來度量相似性。特征點(diǎn)匹配技術(shù)通常采用最近鄰方法，即兩組特征點(diǎn)集合中找到兩兩距離最近的特征點(diǎn)匹配對，理想狀態(tài)這個(gè)匹配對對應(yīng)的是場景中的同一個(gè)位置[10]。假定2幅圖像中，基準(zhǔn)圖像P的特征點(diǎn)集合為Fp={p1，p2，…，pm}，其中m為特征點(diǎn)總數(shù)，待匹配圖像Q的特征點(diǎn)集合為Fq={q1，q2，…，qn}，其中n為特征點(diǎn)總數(shù)，計(jì)算Fp集合中的每個(gè)特征點(diǎn)pi(i=1，2，3，…，m)與集合Fq中每個(gè)特征點(diǎn)qi(i=1，2，3，…，n)之間的距離。這樣得到的最近鄰并不能保證匹配正確，因此SIFT算法對得到最近鄰距離和次近鄰距離進(jìn)行相除，發(fā)現(xiàn)當(dāng)其比值小于0.8時(shí)，該匹配對是正確的可能性很高;反之，匹配對是錯(cuò)誤的可能性很大，因此Lowe在文章中將此比值的判斷閾值取0.8[2]。

1.2 常見距離

SIFT算法在匹配過程中采用歐式距離作為相似性度量。在n維空間中兩點(diǎn)x和y的常見距離度量如下所述:

1)歐氏距離(Euclidean Distance，ED)，也稱為L2范式，如式(1)所示

2)街區(qū)距離(City Block Distance，CBD)也稱為曼哈頓距離，也稱為L1范式，如式(2)所示

3)棋盤距離(Chessboard Distance，CD)，也稱為切比雪夫距離，如式(3)所示

由式(2)、式(3)可知，計(jì)算L1和L∞比計(jì)算L2減少了乘法計(jì)算，可以提高效率。并且容易證明L∞≤L2≤L1[11]，若用L1直接代替L2，所得的值必偏大;用L∞直接代替L2，求得的值必偏小。因此采用L1和L∞適當(dāng)?shù)木€性組合代替L2，這樣既可以保證計(jì)算效率，又可以使計(jì)算偏差減少。

2 相似性度量優(yōu)化

L1和L∞線性組合可以看成是n維空間中一些超平面的方程，這些超平面圍成一個(gè)超多面體。因此計(jì)算L1和L∞線性組合代替L2，就可以看成是用相應(yīng)的超多面體去逼近超球。根據(jù)文獻(xiàn)[12]，可采用α(L1+L∞)和αL1+βL∞兩種方式代替SIFT匹配中的歐氏距離。本文中將α(L1+L∞)和αL1+βL∞分別稱為單系數(shù)法和雙系數(shù)法。

2.1 單系數(shù)法度量優(yōu)化

用α(L1+L∞)這種單系數(shù)的線性組合來代替L2，其中α是一個(gè)需要選擇確定的實(shí)數(shù)。利用相應(yīng)的超多面體去逼近超球來確定α，可分為如下情況:使超多面體恰在超球內(nèi)部時(shí)，得到0.5為α的上確界;使超多面體恰在超球體外部，得到為α的一個(gè)下確界，其中n為維數(shù);使超多面體與超球體面積相等，得到α的最優(yōu)解，其表達(dá)式如式(4)所示

式中:n為維數(shù)。

因?yàn)镾IFT特征描述符為128維，將128代入到式(4)中得到α=0.111 6為最優(yōu)。α的最優(yōu)解保證了單系數(shù)法作為相似性度量和歐氏距離具有相同的匹配正確率。

2.2 雙系數(shù)法度量優(yōu)化

L1和L∞還可以用αL1+βL∞這種雙系數(shù)的線性組合代替L2，其中α，β是需要確定的實(shí)數(shù)。利用相應(yīng)的超多面體去逼近超球來確定α和β，如式(5)所示

式(5)中k的值又分為如下三種情況確定:使超多面體恰在超球內(nèi)部時(shí)，，此值為k的上確界;使超多面體恰在超球體外部時(shí)，k=，為k的下確界;使超多面體與超球體面積相等時(shí)，得到k的最優(yōu)解，表達(dá)式如式(6)所示

式中:n為維數(shù)。

將128代入式(6)計(jì)算得到k值，再根據(jù)式(5)，計(jì)算得α=0.086 749，β=0.981 448為最優(yōu)解。α和β的最優(yōu)解保證了雙系數(shù)法作為相似性度量和歐氏距離具有相同的匹配正確率。

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

本實(shí)驗(yàn)采用Lowe提供的兩組圖像和一組自然光線不同焦距拍攝的圖像進(jìn)行實(shí)驗(yàn)，圖像如圖1所示，其中，圖1a、圖1b和圖1c由Lowe提供，圖1d和圖1e是拍攝圖像。采用MATLAB R2010a編程，運(yùn)行在Intel Pentium Dual CPU 3.00 GHz和1 Gbyte RAM的計(jì)算機(jī)上，Window XP操作系統(tǒng)。

圖1 實(shí)驗(yàn)圖像

實(shí)驗(yàn)首先提取圖像的SIFT特征點(diǎn)，然后對圖1a和圖1b、圖1a和圖1c、圖1d和圖1e以歐氏距離作為相似性度量進(jìn)行匹配，再分別用單系數(shù)法α(L1+L∞)和雙系數(shù)法αL1+βL∞代替特征點(diǎn)間的歐氏距離作為相似性度量，并且選用0.5，0.6，0.7，0.8作為最近鄰和次近鄰距離比值的判斷閾值進(jìn)行特征對提純。結(jié)果表明在同一閾值下采用三種相似性度量匹配過程所得到的特征點(diǎn)數(shù)和特征對、匹配正確率都相同，但匹配時(shí)間不同，計(jì)算街區(qū)距離和棋盤距離的線性組合比計(jì)算歐氏距離用時(shí)短、效率高，并且雙系數(shù)法稍快。不同閾值下匹配用時(shí)如表1所示。

表1 不同閾值下匹配用時(shí)

所得特征點(diǎn)數(shù)和匹配對數(shù)隨最近鄰和次近鄰距離比值閾值的增大而減少。比較發(fā)現(xiàn)，當(dāng)閾值取0.6時(shí)，具有較好的匹配結(jié)果，三組圖像閾值取0.6時(shí)匹配結(jié)果如圖2所示。

圖2 閾值為0.6時(shí)的匹配結(jié)果

因此，在不改變SIFT特征向量的生成過程，通過改變匹配過程中相似性度量計(jì)算方法，也能提高SIFT算法匹配的時(shí)間效率。

4 結(jié)論

本文在分析SIFT算法的基礎(chǔ)上，研究了提高匹配效率的方法。在特征向量匹配過程中用棋盤距離和街區(qū)距離的線性組合代替歐氏距離進(jìn)行圖像匹配。實(shí)驗(yàn)結(jié)果表明，獲得的特征點(diǎn)數(shù)和特征點(diǎn)對沒有改變。因此，在保證SIFT算法的魯棒性不變的情況下，有效提高了匹配效率。由于SIFT算法的可擴(kuò)展性很強(qiáng)，但需要在各個(gè)尺度上進(jìn)行計(jì)算，使其算法復(fù)雜，今后應(yīng)研究改進(jìn)SIFT算法來實(shí)現(xiàn)圖像匹配的實(shí)時(shí)性。

[1]LOWE D G.Object recognition from local scale-invariant feature[C]//Proc.the Seventh IEEE International Conference on Computer Vision.Corfu，Greece:IEEE Press，1999:1150-1157.?

[2]LOWE D G.Distinctive image features from scale-invariant key points[J].International Conference of Computer Vision，2004，60(2):90-110.

[3]張志，葉蓬，王潤生.基于SIFT特征的多幀圖像超分辨重建[J].中國圖象圖形學(xué)報(bào)，2009，14(11):2373-2377.

[4]MATTHEW B，LOWE D G.Recognizing panoramas[C]//Proc.the Ninth IEEE International Conference on Computer Vision.Nice，F(xiàn)rance:IEEE Press，2003:1218-1225.

[5]何敬，李永樹，魯恒，等.基于SIFT特征點(diǎn)的無人機(jī)影像拼接方法研究[J].光電工程，2011，38(2):122-126.

[6]李芳芳，賈永紅.利用線特征和SIFT點(diǎn)特征進(jìn)行多源遙感影像配準(zhǔn)[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版，2010，35(2):233-236.

[7]KE Y，SUKTHANKAR R.PCA-SIFT:a more distinctive representation for local image descriptors[C]//Proc.the IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington，DC:IEEE Press，2004:506-513.

[8]MIKOLAJCZYK K，SCHMID C.A performance evaluation of local descriptors[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1615-1630.

[9]于麗莉，戴青.一種改進(jìn)的SIFT特征匹配算法[J].計(jì)算機(jī)工程，2011，37(2):210-212.

[10]王會(huì)峰，劉上乾，汪大寶.基于序列圖像特征配準(zhǔn)的攝像機(jī)旋轉(zhuǎn)補(bǔ)償算法[J].光學(xué)精密工程，2008，16(7):1330-1334.

[11]王曉華，傅衛(wèi)平，梁元月.提高SIFT特征匹配效率的方法研究[J].機(jī)械科學(xué)與技術(shù)，2009，28(9):1252-1255.

[12]王鉦旋，李海軍，周春光.高維空間中用計(jì)算街區(qū)距離和棋盤距離的線性組合代替計(jì)算歐式距離[J].小型微型計(jì)算機(jī)系統(tǒng)，2004，25(12):2120-2125.