尺度與特征強度自適應(yīng)的SURF特征點匹配算法

胡曉彤，任 輝，劉 楠

(天津科技大學計算機科學與信息工程學院，天津 300222)

基于特征點的圖像配準算法首先在圖像中提取特征點，然后建立兩幅圖像之間特征點的配準關(guān)系，其廣泛應(yīng)用于圖像匹配、三維成像等領(lǐng)域．Bay等提出了 SURF(speeded-up robust features)算法[1]，它是對SIFT(scale invariant feature transform)算法的一種改進，其性能超過了SIFT且能夠獲得更快的速度[2]．文獻[3]中的局部特征算法的性能比較實驗表明：SURF算法是性能最為魯棒的局部特征算法[3]．在對SURF算法的改進研究方面，已經(jīng)有許多的研究成果．潘建平等[4]通過圖像分塊策略改善提取特征點的均勻性，引用相對距離理論剔除異常匹配點，從而提高了匹配點的可靠性；?？×值萚5]將 SVM 與 SURF相結(jié)合，所得到的特征點歐氏距離歸一化后輸入到SVM中，通過線下學習，對每幅圖像自主地選取合適的閾值，實現(xiàn)了特征點之間的自適應(yīng)匹配，使得匹配精度有了一定程度的提高；貢超等[6]提出采用擴散距離對SURF特征進行匹配，提高了匹配的正確率與魯棒性．在提高 SURF匹配速度方面，胡 旻 濤等[7]提出利用圖像熵信息對特征點進行篩選，并利用快速近鄰搜索算法進行特征匹配，有效地改善了匹配效率．上述改進算法對于提高 SURF算法的性能進行了有益的探索．但是，迄今為止尚無法實現(xiàn) SURF特征點的匹配精度與匹配成功率間的平衡．

為此，本文在深入研究 SURF特征點的尺度、特征強度與匹配性能間關(guān)系的基礎(chǔ)上，提出了特征點尺度與特征強度自適應(yīng)的SURF圖像特征點匹配算法，從而獲得更多高精度的匹配特征點對，實現(xiàn)了高性能的SURF特征點匹配．

1 SURF特征點檢測

SURF算法是一種基于尺度空間的特征點檢測與匹配算法，其不僅對圖像旋轉(zhuǎn)、平移、縮放和噪聲具有較好的魯棒性，而且在光照變化、視角變化及圖像模糊等情況下也能得到較好的匹配結(jié)果[8]．

SURF算法首先對圖像進行高斯平滑處理，并建立高斯尺度空間，然后通過計算 Hessian矩陣行列式的局部極值來確定特征點的位置．對于尺度為σ的空間中任一點(x, y)的Hessian矩陣定義為

式中：Lxx是高斯二階導卷積的結(jié)果，其中；Lxy、Lyy與 Lxx具有相似的含義．

1.1 特征點的描述

為保持特征點的旋轉(zhuǎn)不變性，在特征點位置確定后，計算每一個特征點的主方向．為此，在以特征點為中心，半徑為 6σ(σ為特征點的尺度)的圓形區(qū)域內(nèi)，對圖像在x和y方向進行 Harr小波響應(yīng)運算，Harr小波邊長取4σ，并使用尺度為2σ的高斯加權(quán)函數(shù)對 Harr小波響應(yīng)值進行高斯加權(quán)，使得越靠近特征點的響應(yīng)貢獻越大；然后，用π/3大小的扇形區(qū)域范圍遍歷整個圓形區(qū)域，并將水平方向響應(yīng)和垂直方向響應(yīng)的矢量和模的最大值的方向定義為特征點的主方向．

以特征點為中心，構(gòu)造一邊垂直于主方向且邊長為 20σ的正方形窗口區(qū)域，并將該窗口區(qū)域劃分成4×4的子區(qū)域，如圖 1所示．在每一個子區(qū)域內(nèi)，進行5σ×5σ個采樣點的水平方向和垂直方向的Harr小波響應(yīng)的計算，分別記作dx和dy，同樣使用尺度為2σ的高斯加權(quán)函數(shù)對 Harr小波響應(yīng)值進行高斯加權(quán)，以增加對幾何變換的魯棒性．然后將每個子區(qū)域的響應(yīng)值和響應(yīng)值的絕對值相加形成

圖1 SURF 特征點的描述Fig. 1 SURF point features

由此，每個子區(qū)域就形成了一個四維特征描述向量

對于每一個特征點，形成4×4×4＝64維的特征向量．同時，為保證對光照不變性，對特征向量進行歸一化處理，得到最終的SURF描述符．

1.2 特征點的匹配

特征點的匹配是實現(xiàn)圖像配準的關(guān)鍵，特征點匹配的精度直接影響著后續(xù)處理的準確性[9]．根據(jù)SURF特征點描述符中包含的特征點鄰域信息，采用K最近鄰法找出每個特征點潛在的兩個最佳匹配點；最終，通過匹配點的距離最佳值與次佳值比率優(yōu)選出最佳匹配點對．

2 定位精度的影響因素

在基于SURF特征點的圖像配準過程中，特征點的匹配精度影響圖像間配準變換模型參數(shù)的估算．如何選取更多高精度匹配特征點對是提高圖像配準精度的關(guān)鍵．

2.1 特征點尺度

根據(jù)SURF特征點的檢測與描述方法可知，特征點的尺度是特征點具有的重要特征，同時也反映了用于描述該特征點的圖像區(qū)域的大小．圖 2中的圓形區(qū)域即為計算圓心所代表的特征點的特征向量所使用的圖像區(qū)域，而該圓的半徑則被定義為該特征點的尺度．

由于用于描述小尺度特征點的圖像區(qū)域較小，能夠更加準確地描述該點的特征，從而使得小尺度特征點間的匹配具有更高的定位精度[10]．不過，小尺度特征點只占圖像中所有特征點的一部分，使不同尺度的特征點均能獲得較高的定位精度是實現(xiàn)高性能SURF特征點匹配的關(guān)鍵．

圖2 SURF 特征點的尺度描述Fig. 2 SURF point scale

目前，尚未見定量分析SURF特征點的尺度與定位精度間關(guān)系的研究．為此，需要定量分析 SURF特征點的尺度對定位精度的影響程度，并在此基礎(chǔ)上，探索受特征點尺度影響較小的匹配機制，為高性能的SURF特征點匹配提供保障．

2.2 特征強度

SURF特征點匹配算法采用 K最近鄰法搜索出每個特征點潛在的兩個最佳匹配點，并定義相似度最高的待匹配特征點的特征向量的歐氏距離 d1與相似度次高的待匹配特征點的特征向量的歐氏距離 d2的比值 d1/d2為該特征點的特征強度．同時，設(shè)定特征強度閾值，只有當待匹配特征點的特征強度值小于該閾值時，才將該特征點對作為匹配成功點對．

由于相似度越高的特征點的特征強度值越小的可能性越高，故較小的特征強度閾值能夠保證相似度較高的特征點對才被保留下來，從而提高配準的定位精度．然而，如果將特征強度閾值設(shè)置較小，即只保留特征強度較高的特征點，則可能導致匹配成功率降低，使最終獲得的匹配點對數(shù)量不足，無法實現(xiàn)高性能的特征點匹配．因此，只有深度研究 SURF特征點的特征強度閾值與匹配性能間的關(guān)系，才能夠保持定位精度和匹配成功率的平衡，從而有望實現(xiàn)高性能的特征點匹配．

2.3 尺度、特征強度與定位精度的關(guān)系

雖然小尺度、高特征強度的特征點能夠獲得較高的定位精度，但可能造成匹配成功的特征點對數(shù)量不夠多，無法實現(xiàn)高性能的特征點匹配的問題．

同時，傳統(tǒng)的SURF特征點匹配算法采用統(tǒng)一的特征強度閾值，當該閾值被設(shè)置得較小時，可能會造成部分定位精度較高的小尺度特征點未能匹配成功；而當該閾值被設(shè)置得較大時，可能會造成部分定位精度較低的大尺度特征點被保留下來．故采用統(tǒng)一的特征強度閾值，可能影響整體的定位精度，或使匹配成功的特征點對的數(shù)量減少，無法達到定位精度與匹配成功的特征點對數(shù)量間的平衡．

為此，需要深入研究 SURF特征點的尺度、特征強度與定位精度、匹配成功率間的關(guān)系，探索高性能的SURF特征點匹配．

3 實驗分析

3.1 尺度與定位精度的關(guān)系

在已知圖像旋轉(zhuǎn)角度(實驗中取 5°)的條件下，將圖 2所示與旋轉(zhuǎn)后的圖像進行特征點匹配；隨后，基于原圖上特征點的坐標與旋轉(zhuǎn)角度計算旋轉(zhuǎn)后匹配點的理論坐標值；最后，計算旋轉(zhuǎn)圖像上相匹配的特征點的真實坐標值與理論坐標值間的差作為定位誤差進行分析．圖 3所示為特征點定位誤差的絕對值．從圖 3可以看出：在特征強度一定的情況下，小尺度特征點(尺度＜20)的定位誤差相對于大尺度特征點(尺度≥40)普遍較小，說明小尺度特征點具有較高的定位精度．

圖3 不同尺度特征點的定位誤差Fig. 3 Positioning errors at different scale feature points

為了定量分析特征點尺度與定位精度間的關(guān)系，將圖2所示圖像與測試用圖像進行特征點匹配，對匹配成功的特征點計算其定位誤差，從而分析不同尺度的特征點的定位精度．分析時，采用待匹配圖像中匹配成功的特征點坐標與原圖中相應(yīng)的特征點經(jīng)旋轉(zhuǎn)后坐標間的差值作為特征點的定位誤差，結(jié)果見表 1．

表1 不同尺度特征點的平均定位誤差Tab. 1 Average positioning errors of feature points of different scales

從表 1可以看出：隨著特征點尺度的增大，其平均定位誤差呈上升趨勢，如尺度≥40的特征點的平均定位誤差接近尺度＜20的特征點的定位誤差的3倍．

3.2 特征強度與定位精度的關(guān)系

為了深入研究特征強度閾值與特征點定位精度間的關(guān)系，分別設(shè)置不同的特征強度閾值，分析高、中、低特征強度閾值下的特征點定位誤差，結(jié)果見圖 4．

圖4 不同特征強度特征點的定位誤差Fig. 4 Positioning errors of feature points of different intensity

從圖 4可以看出，隨著特征強度閾值的增大，定位誤差呈逐步增大的趨勢，表明特征強度閾值的設(shè)置對于特征點的定位精度確有影響．

為了進一步定量分析特征強度閾值與定位精度間的關(guān)系，在尺度相同的情況下(實驗中取尺度小于40)，分析不同特征強度閾值下匹配成功的特征點的數(shù)量與定位誤差，結(jié)果見表2．

表2 不同強度特征點的平均定位誤差Tab. 2 Average positioning errors of feature points of different strength

從表 2可以看出：隨著特征強度閾值的提高，平均定位誤差呈上升趨勢．同時，不同特征強度的特征點間的定位誤差差異也較大，如特征強度在 0.5與0.8之間的特征點的平均定位誤差接近特征強度小于0.2的特征點的定位誤差的3倍．

3.3 尺度、特征強度與定位精度的關(guān)系

上述實驗結(jié)果表明：采用小尺度特征點或者降低特征強度閾值均能有效提高匹配成功的特征點對的定位精度，但可能造成匹配成功率的下降．為了進一步研究尺度、特征強度與定位精度間的關(guān)系，針對不同尺度的特征點，分別設(shè)置不同的特征強度閾值，進行特征點匹配實驗，結(jié)果見表3．

表3 不同尺度和特征強度下特征點的平均定位誤差Tab. 3 Average positioning errors of feature points of different scales and characteristic intensities

從表 3可以看出：特征點尺度越小，同時特征強度值越小的情況下，匹配點對間的平均定位誤差越小，也即定位精度更高．同時，對于小尺度特征點來說，即便特征強度值稍大，也能夠獲得較高的定位精度．而對于大尺度特征點，只有當特征強度值較小時，才能獲得高精度的匹配點對．

4 改進算法

前文分析表明，采用統(tǒng)一的特征強度閾值無法實現(xiàn)定位精度與匹配成功率間的平衡．因此，本文提出一種特征點尺度與特征強度自適應(yīng)的 SURF特征點匹配算法．

4.1 算法原理

對定位精度較高的小尺度特征點，采用較大的特征強度閾值，以保留更多的小尺度特征點；對定位精度不高的大尺度特征點，采用較小的特征強度閾值，以剔除定位精度較低的大尺度特征點．

具體算法流程如下：

(1)提取模板圖像SURF特征點；

(2)根據(jù)尺度大小將 SURF特征點分為 3類：尺度＜20、20≤尺度＜40、尺度≥40；

(3)提取待測圖像 SURF特征點，分別在 0.2、0.5、0.8的特征強度閾值下與步驟(2)所得的 3類特征點進行匹配，得到匹配結(jié)果．

4.2 算法的比較

為了驗證算法的有效性，使用傳統(tǒng)SURF算法以及基于 SVM 的改進 SURF算法與本文提出的自適應(yīng)算法對多幅圖像對進行了特征點匹配實驗．?？×值萚5]所提出的 SVM 與 SURF相結(jié)合的算法采用SVM選取合適的匹配閾值，提高了匹配精度，與本文所提出的算法具有較高的可對比性，因此選取此改進算法進行對比．

在傳統(tǒng)的SURF匹配算法中，將特征強度閾值設(shè)置為被普遍采用的 0.66．本文提出的自適應(yīng)算法的參數(shù)設(shè)置為尺度小于20的特征點的特征強度閾值為0.8；尺度在[20，40]區(qū)間的特征點的特征強度閾值為0.5；尺度大于40的特征點的特征強度閾值為0.2，為不同尺度的特征點設(shè)置為不同的匹配規(guī)則．所選測試用圖見圖5，實驗結(jié)果見表4．

圖5 測試用圖Fig. 5 Test images

表4 算法匹配性能比較Tab. 4 Matching performance of different algorithms

從表 4可以看出：傳統(tǒng)算法平均定位誤差較大，而基于 SVM 的 SURF改進算法針對整幅圖像選取一個適宜的特征強度閾值，故其平均定位誤差要小于傳統(tǒng)的 SURF算法，但匹配點對數(shù)量下降較明顯；與傳統(tǒng)的SURF算法相比，本算法在獲得相近數(shù)量的匹配點對的情況下，平均定位誤差降低了 10%～15%；與基于SVM的SURF改進算法相比，本算法在定位誤差基本相同的情況下，匹配成功的特征點數(shù)增加了11%～48%．上述結(jié)果表明，本算法較好地實現(xiàn)了特征點的平均定位誤差與匹配成功率間的平衡．

5 結(jié) 語

本文在深入研究SURF特征點的尺度、特征強度與定位精度間關(guān)系的基礎(chǔ)上發(fā)現(xiàn)：隨著特征點尺度的減小，特征點的定位誤差呈下降趨勢；另外，隨著特征強度閾值的降低，特征點的定位誤差也呈下降趨勢，但同時都伴隨著匹配成功特征點對數(shù)量的下降．為此，本文提出了一種尺度和特征強度的自適應(yīng)SURF特征點配準算法，通過特征強度閾值與尺度間的相互適應(yīng)，使保持特征點的定位精度與匹配成功率間的平衡成為可能．實驗結(jié)果表明：本算法在有效地提高了特征點的定位精度的同時，獲得了數(shù)量更多的匹配特征點對．