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

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

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

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

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

1 匹配原理及常用距離

1.1 匹配的基本原理

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

1.2 常見距離

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

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

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

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

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

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

L1和L∞線性組合可以看成是n維空間中一些超平面的方程，這些超平面圍成一個超多面體。因此計算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，其中α是一個需要選擇確定的實數(shù)。利用相應(yīng)的超多面體去逼近超球來確定α，可分為如下情況:使超多面體恰在超球內(nèi)部時，得到0.5為α的上確界;使超多面體恰在超球體外部，得到為α的一個下確界，其中n為維數(shù);使超多面體與超球體面積相等，得到α的最優(yōu)解，其表達(dá)式如式(4)所示

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

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

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

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

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

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

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

3 實驗結(jié)果及分析

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

圖1 實驗圖像

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

表1 不同閾值下匹配用時

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

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

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

4 結(jié)論

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

[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é)報，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特征點的無人機(jī)影像拼接方法研究[J].光電工程，2011，38(2):122-126.

[6]李芳芳，賈永紅.利用線特征和SIFT點特征進(jìn)行多源遙感影像配準(zhǔn)[J].武漢大學(xué)學(xué)報:信息科學(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ī)工程，2011，37(2):210-212.

[10]王會峰，劉上乾，汪大寶.基于序列圖像特征配準(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]王鉦旋，李海軍，周春光.高維空間中用計算街區(qū)距離和棋盤距離的線性組合代替計算歐式距離[J].小型微型計算機(jī)系統(tǒng)，2004，25(12):2120-2125.