基于空間約束的快速魯棒特征匹配優(yōu)化

趙 燁蔣建國(guó) 洪日昌

(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院 合肥 230009)

1 引言

基于特征的配準(zhǔn)方法以其計(jì)算量較少、速度快等特點(diǎn)廣泛應(yīng)用于機(jī)器視覺(jué)、圖像拼接、目標(biāo)識(shí)別、3維重建、圖片旅游、視頻摘要等諸多領(lǐng)域[14]-。尤其以基于 Lowe[5,6]提出的尺度不變特征轉(zhuǎn)換 (Scale Invariant Feature Transform, SIFT)算法應(yīng)用較為廣泛。SIFT算法將尺度不變特征子與梯度方向描述子相結(jié)合，具有圖像縮放、旋轉(zhuǎn)、光照和仿射不變性等優(yōu)點(diǎn)。然而由于 SIFT描述子的維度較高導(dǎo)致計(jì)算過(guò)于復(fù)雜，難以滿足在對(duì)速度要求高的場(chǎng)景。為了降低計(jì)算復(fù)雜度，縮短匹配時(shí)間，隨后有很多研究人員提出了各種基于 SIFT 的改進(jìn)算法。文獻(xiàn)[7]提出了采用主成分分析(Principal Component Analysis, PCA)的方法對(duì) SIFT描述子進(jìn)行降維的PCA-SIFT算法，其算法中PCA-SIFT描述子的維度可以降低到 20維，但是該描述子的通用性不如SIFT描述子，需要通過(guò)有代表性的圖像計(jì)算投影矩陣，并且在執(zhí)行快速匹配時(shí)的精度也不如SIFT，不太滿足實(shí)際應(yīng)用[8]。文獻(xiàn)[9]提出梯度位置方向直方圖 (Gradient Location Orientation Histogram,GLOH)算法，把SIFT中棋盤(pán)格狀的塊狀分區(qū)變成同心圓形的放射狀分區(qū)，再使用PCA降低維度。該算子的獨(dú)特性比 SIFT要好，但是計(jì)算更復(fù)雜。文獻(xiàn)[10]提出的快速魯棒特征(Speeded Up Robust Features, SURF)算法是一種快速的特征檢測(cè)和描述算法。該算法在特征點(diǎn)檢測(cè)和向量描述中巧妙地利用快速積分和箱式濾波，在繼承 SIFT算法對(duì)圖像縮放與亮度變化不敏感、抗干擾以及魯棒性強(qiáng)的同時(shí)，大幅加快了特征的提取速度，基于SURF特征配準(zhǔn)已成為模式識(shí)別領(lǐng)域中的一個(gè)新的研究熱點(diǎn)。

但是SURF的匹配精度還不夠優(yōu)良，得到的特征匹配點(diǎn)還存在一定數(shù)量的誤匹配。而SURF主要應(yīng)用在圖像處理的前端，其配準(zhǔn)精度直接影響到整個(gè)系統(tǒng)性能。為了進(jìn)一步提高SURF匹配精度，文獻(xiàn)[11]提出了結(jié)合顏色和全局特征的 SURF特征算法，文獻(xiàn)[12]通過(guò)加權(quán)的方式把 SURF特征與局部顏色直方圖結(jié)合起來(lái)。鑒于視覺(jué)詞之間的幾何關(guān)系在圖像識(shí)別中起到重要作用，近來(lái)文獻(xiàn)[13]采用最佳尺度空間的選擇來(lái)提高匹配性能，雖然以上的改進(jìn)算法在一定程度上提高了匹配精度，但由于計(jì)算過(guò)于復(fù)雜，時(shí)間消耗非常大。因此，在保證計(jì)算復(fù)雜度基本不變的要求下，如何提高SURF匹配精度仍然是尚待解決的問(wèn)題。

在以往算法中，特征點(diǎn)之間的空間關(guān)系往往被忽略，這使得計(jì)算成本高昂。特征點(diǎn)間的空間關(guān)系很容易獲得，而且計(jì)算簡(jiǎn)便易行，為此本文提出一種基于空間約束的 SURF特征匹配優(yōu)化算法(SC-SURF)，通過(guò)選擇最優(yōu)匹配點(diǎn)計(jì)算投影矩陣，同時(shí)利用最優(yōu)匹配點(diǎn)構(gòu)造參考坐標(biāo)系產(chǎn)生空間信息表，二者結(jié)合起來(lái)對(duì)按匹配度加權(quán)的匹配點(diǎn)進(jìn)行幾何核查，以提高匹配的高效性和有效性。

2 SURF特征點(diǎn)匹配

SURF算法利用最近鄰比率方法判斷匹配度，最近鄰比率算法就是使用最近鄰距離與次近鄰距離的比值作為兩幅圖像的相似性判定度量，當(dāng)該比值在一定的閾值范圍內(nèi)時(shí)則認(rèn)定該特征點(diǎn)是匹配特征點(diǎn)。

距離比閾值是特征點(diǎn)之間建立匹配關(guān)系的紐帶。Lowe的實(shí)驗(yàn)給出了距離比與概率密度分布曲線，如圖1所示。閾值越小，匹配點(diǎn)的正確概率越大，然而匹配點(diǎn)數(shù)越少；閾值越大，匹配點(diǎn)數(shù)越多，但匹配準(zhǔn)確率越小。Lowe將距離比閾值設(shè)為0.8。本文在SURF特征點(diǎn)匹配中按照最近鄰比率對(duì)匹配點(diǎn)進(jìn)行優(yōu)先隊(duì)列實(shí)現(xiàn)。

通過(guò)上面方法對(duì)SURF特征點(diǎn)進(jìn)行匹配，得到的匹配點(diǎn)仍然存在一定數(shù)量的誤匹配，為了提高匹配精度，需要對(duì)特征點(diǎn)進(jìn)行二次匹配。

3 SURF特征點(diǎn)的二次匹配

3.1 幾何校驗(yàn)方法

為了進(jìn)一步提純和濾除誤匹配，一般采用幾何校驗(yàn)來(lái)實(shí)現(xiàn)SURF特征點(diǎn)的二次匹配。應(yīng)用最廣泛的幾何校驗(yàn)方法是隨機(jī)抽樣一致性(RANSAC)算法[14]。它是一種在一組觀測(cè)數(shù)據(jù)集中估計(jì)模型參數(shù)的迭代方法，可以從數(shù)據(jù)樣本中準(zhǔn)確擬合數(shù)學(xué)模型，然后采用隨機(jī)抽樣驗(yàn)證去除噪聲點(diǎn)。但該方法的性能在外點(diǎn)較多的情況下將受到很大影響，而且計(jì)算復(fù)雜度高，得到的結(jié)果并不理想。所以SURF的幾何校驗(yàn)策略需要一種更簡(jiǎn)便有效的方法。為此本文提出利用簡(jiǎn)化的 RANSAC算法結(jié)合空間約束策略來(lái)實(shí)現(xiàn)幾何校驗(yàn)。

3.2 二次匹配優(yōu)化策略

特征點(diǎn)間的空間關(guān)系很容易獲得，而且計(jì)算簡(jiǎn)便易行，本文從SURF特征點(diǎn)之間的相對(duì)空間關(guān)系出發(fā)，以最優(yōu)匹配點(diǎn)構(gòu)造參考坐標(biāo)生成空間約束矩陣，可以大大地簡(jiǎn)化計(jì)算復(fù)雜度。同時(shí)選擇最優(yōu)匹配點(diǎn)做為初始數(shù)據(jù)集進(jìn)而簡(jiǎn)化 RANSAC算法，最后二者結(jié)合起來(lái)通過(guò)正誤率分析實(shí)現(xiàn)幾何校驗(yàn)。

3.2.1空間約束矩陣 SURF匹配點(diǎn)之間的空間位置信息可以用一個(gè)矩陣表示[15]，對(duì)于任意N個(gè)匹配點(diǎn)，第i個(gè)和第j個(gè)匹配點(diǎn)滿足關(guān)系，從而使得空間信息表M中元素取值如式(1)，式(2)所示。

匹配點(diǎn)在新坐標(biāo)系下的坐標(biāo)為

那么形成了3維空間約束矩陣M：

圖1 Lowe實(shí)驗(yàn)的概率密度分布曲線

3.2.2簡(jiǎn)化的RANSAC算法 RANSAC算法模型的參數(shù)估計(jì)是不斷通過(guò)內(nèi)外點(diǎn)進(jìn)行迭代計(jì)算和反復(fù)測(cè)試來(lái)完成的，初始模型參數(shù)是由隨機(jī)抽取樣本數(shù)據(jù)計(jì)算得到的，所以具有很大的不確定性，而初始參數(shù)的優(yōu)劣直接決定著迭代次數(shù)和計(jì)算成本。本文簡(jiǎn)化 RANSAC的方法是選擇少數(shù)最優(yōu)匹配點(diǎn)作為初始樣本數(shù)據(jù)，這樣得到初始模型參數(shù)很接近真實(shí)值，可以通過(guò)設(shè)置盡量少的迭代次數(shù)來(lái)得到盡量真實(shí)的單應(yīng)性矩陣參數(shù)，提高了計(jì)算效率。

本文選擇投影變換矩陣作為圖像變換模型，變換關(guān)系為

這是8個(gè)參數(shù)的投影變換，至少需要4個(gè)匹配對(duì)來(lái)生成，利用最小二乘法求解這8個(gè)參數(shù)。

初始樣本數(shù)據(jù)數(shù)目n可按照式(9)確定：

這里0N是一次匹配的匹配點(diǎn)數(shù)目，并且為樣本數(shù)目步長(zhǎng), μ為比例因數(shù)。

3.2.3空間幾何校驗(yàn) 待配準(zhǔn)的兩幅圖像根據(jù)相應(yīng)的匹配對(duì)分別產(chǎn)生空間約束矩陣和，對(duì)和矩陣中的異值點(diǎn)進(jìn)行統(tǒng)計(jì)，生成異值矩陣W：

為了確保匹配精度，K值選擇應(yīng)大于 2，但考慮到運(yùn)算速度，K取值又不能過(guò)大，一般選擇K=3。最后得到特征點(diǎn)在空間約束矩陣下的錯(cuò)誤率為id。

圖2 最優(yōu)匹配點(diǎn)構(gòu)成參考坐標(biāo)系

設(shè)模型參數(shù)變換得到匹配點(diǎn)坐標(biāo)值與實(shí)際坐標(biāo)的距離值為jd，匹配點(diǎn)判別按照式(12)進(jìn)行，由于透視變換矩陣僅為少數(shù)數(shù)據(jù)得出，不能保證求得最精確的結(jié)果，所以采用兩個(gè)約束條件相互補(bǔ)充。

式中α為比例因子, γ均為距離閾值。

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

實(shí)驗(yàn)的運(yùn)行環(huán)境為 Genuine Intel(R) T2400(CPU), 1.83 GHz主頻，2 G內(nèi)存的PC機(jī)。采用牛津大學(xué)的局部仿射變換數(shù)據(jù)集[16]，分別對(duì)SC-SURF算法與SIFT算法、SURF算法和帶有RANSAC校驗(yàn)的SURF算法進(jìn)行了對(duì)比實(shí)驗(yàn)，匹配性能主要從匹配準(zhǔn)確率(Precision)-召回率(Recall)和匹配速度兩個(gè)方面進(jìn)行分析。鑒于準(zhǔn)確率與召回率往往是矛盾的，因此本文又采用一個(gè)綜合指標(biāo)加權(quán)調(diào)和平均(F-Measure)來(lái)幫助分析，加權(quán)調(diào)和平均是準(zhǔn)確率和召回率加權(quán)調(diào)和平均：

4.1 匹配性能測(cè)試實(shí)驗(yàn)

對(duì)測(cè)試圖像在旋轉(zhuǎn)和尺度變化、視角變化、模糊變化、光照變化和JPEG壓縮等典型變換下進(jìn)行了匹配實(shí)驗(yàn)。其中SIFT的對(duì)比度閾值為0.02, S為3, O為7, SURF的描述子為64維，SC-SURF中的比例因子α根據(jù)多次測(cè)試實(shí)驗(yàn)效果最佳時(shí)的取值為0.1，距離閾值。利用已知的單向性矩陣判斷匹配效果，最后將大量的實(shí)驗(yàn)數(shù)據(jù)平均后，得到各種典型變換下各算法的查準(zhǔn)率-召回率曲線和加權(quán)調(diào)和平均曲線，如圖 3～圖 7所示。在旋轉(zhuǎn)和尺度變換情況下，測(cè)試圖像角度旋轉(zhuǎn)3045°°～，尺度因子變化1～4倍。視角變化的測(cè)試圖片不僅有60°的旋轉(zhuǎn)視角，還有尺度和照度上的變化。從圖3，圖4的曲線中可以看出SC-SURF算法不論在尺度、旋轉(zhuǎn)變化還是視角變化下的匹配效果均好于其他算法。這是因?yàn)榧尤肓丝臻g約束和旋轉(zhuǎn)坐標(biāo)，所以 SC-SURF具有更好的旋轉(zhuǎn)不變性和尺度不變性。

JPEG序列是利用標(biāo)準(zhǔn)的xv圖像瀏覽器通過(guò)改變圖像質(zhì)量參數(shù)從40\%到2\%產(chǎn)生的，在抗JPEG壓縮方面，如圖7所示，SURF算法與RANSACSURF和 SC-SURF效果差異不大，都能很有效地抗壓縮變化。在以上各種圖像變換的情況下，SIFT的準(zhǔn)確率指標(biāo)較好，但其召回率較差，所以綜合指標(biāo)加權(quán)調(diào)和平均性能較低，然而 DoG檢測(cè)子比Hessian檢測(cè)子可以提取更多的特征點(diǎn)數(shù)，一般SIFT檢測(cè)到的特征點(diǎn)數(shù)目是SURF檢測(cè)到的2～5倍。因此在對(duì)匹配速度要求不高的情況下，SIFT算法還是比SURF得到更廣泛的應(yīng)用。

圖3 視角變化時(shí)各算法的性能比較

圖4 縮放旋轉(zhuǎn)變化時(shí)各算法的性能比較

圖5 光照變化時(shí)各算法的性能比較

圖6 圖像模糊時(shí)各算法的性能比較

圖7 JPEG壓縮時(shí)各算法的性能比較

圖8給出了在視角變化下的匹配示例。測(cè)試圖像為Graf中img1與img2，距離比閾值為0.7，匹配結(jié)果為：SIFT的匹配點(diǎn)對(duì)是1230對(duì)，其中正確匹配對(duì)是1179對(duì)，配準(zhǔn)率為0.95854。SURF的匹配點(diǎn)對(duì)是734對(duì)，其中正確匹配對(duì)是611對(duì)，配準(zhǔn)率為0.8324。RANSAC-SURF的匹配點(diǎn)對(duì)是695對(duì)，其中正確匹配對(duì)是 611對(duì)，配準(zhǔn)率為 0.8791。SCSURF的匹配點(diǎn)對(duì)是691對(duì)，其中正確匹配對(duì)是611對(duì)，配準(zhǔn)率為 0.8842。綠色空心圓為正確匹配點(diǎn)，紅色十字形表示錯(cuò)誤匹配點(diǎn)，可見(jiàn) SIFT的配準(zhǔn)率是最高的。

圖9所示是4種算法在近重復(fù)圖像下的匹配示例。

綜合上面的實(shí)驗(yàn)結(jié)果，SC-SURF的匹配性能明顯優(yōu)于其他算法，在匹配的有效性上相比于原始SURF有很大的改進(jìn)。

4.2 匹配速度測(cè)試實(shí)驗(yàn)

為了評(píng)估SC-SURF算法的計(jì)算復(fù)雜度，對(duì)這4種算法進(jìn)行匹配速度測(cè)試。為了統(tǒng)一參數(shù)，SC-SURF算法與其余3種算法的距離比閾值均設(shè)為0.7，其余參數(shù)設(shè)置與上面實(shí)驗(yàn)相同。在前面所述的運(yùn)行環(huán)境下，樣本數(shù)目取100對(duì)，圖10給出了SIFT和SURF匹配時(shí)間的比較，圖11比較了RANSACSURF和SC-SURF的二次匹配時(shí)間。

由以上圖表可知，RANSAC-SURF在個(gè)別情況下的計(jì)算復(fù)雜度很高，這是由于樣本點(diǎn)中的外點(diǎn)過(guò)多，而 RANSAC要擬合的仿射矩陣總是受污點(diǎn)感染而達(dá)不到最優(yōu)矩陣造成的。SIFT和 SURF的運(yùn)行時(shí)間主要取決于檢測(cè)到特征點(diǎn)的數(shù)目。SIFT的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)大于SURF，大約是SURF的10～30倍。同時(shí) SC-SURF的二次匹配運(yùn)行速度相對(duì)RANSAC-SURF快3～100倍，在個(gè)別情況時(shí)能高達(dá)幾千倍，它的運(yùn)行時(shí)間大約是SURF的2%左右，所以本文算法相對(duì)于原始SURF運(yùn)行時(shí)間基本保持一致，但匹配精度大大提高。本文算法相對(duì)于RANSAC-SURF運(yùn)行速度大幅度提高，同時(shí)匹配精度也比后者略好。

5 結(jié)束語(yǔ)

本文以SURF作為圖像的局部特征，構(gòu)建了一種基于空間約束的 SURF特征點(diǎn)匹配的優(yōu)化算法SC-SURF。為提高算法對(duì)各類(lèi)變化圖像的適應(yīng)性，在 BBF匹配搜索中按照最近鄰比率進(jìn)行優(yōu)先級(jí)排序，把匹配點(diǎn)間的空間約束關(guān)系和簡(jiǎn)化的RANSAC算法結(jié)合起來(lái)進(jìn)行幾何校驗(yàn)，從而提高匹配精度和速度。通過(guò)對(duì)在圖像縮放和旋轉(zhuǎn)、光照、視角、模糊和壓縮等圖像典型變化下的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析，SC-SURF算法在匹配準(zhǔn)確率上明顯超過(guò) SURF和SIFT算法，在匹配時(shí)間上控制在毫秒級(jí)，在保持與SURF運(yùn)行時(shí)間幾乎不變情況下，大幅提高了匹配精度。同時(shí)在比 RANSAC-SURF的匹配精度略好的情況下，減少了計(jì)算復(fù)雜度。該算法在實(shí)際應(yīng)用中仍存在很多待改進(jìn)之處，由于對(duì)最優(yōu)匹配點(diǎn)依賴(lài)性較強(qiáng)，因此如何進(jìn)一步完善最優(yōu)匹配的選擇條件，是下一步待研究的問(wèn)題。

圖8 視角變化的匹配結(jié)果(綠色圓形符號(hào)表示正確匹配點(diǎn)，紅色十字形符號(hào)表示錯(cuò)誤匹配點(diǎn))

圖9 匹配實(shí)例(由上到下依次是SIFT, SURF, RANSAC-SURF和SC-SURF)

圖10 SURF與SIFT運(yùn)行時(shí)間對(duì)比

圖11 SC-SURF與RANSAC-SURF二次匹配運(yùn)行時(shí)間對(duì)比

[1] Rudinac S, Larson M, and Hanjalic A. Learning crowdsourced user preferences for visual summarization of image collections[J]. IEEE Transactions on Multimedia, 2013,15(6): 1231-1243.

[2] Wang M, Ni B, Hua X, et al.. Assistive tagging: a survey of multimedia tagging with human-computer joint exploration[J]. ACM Computing Surveys, 2012, 44(4): 1-25.Conference on Computer Vision, Los Alamitos, 1999:1150-1157.

[6] Lowe D. Distinctive image features from scale-invariant keypoints [J]. International Journal of Computer Vision, 2004,60(2): 91-110

[7] Ke Y and Sukthankar R. PCA-SIFT: a more distinctive representation for local image descriptors[C]. Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Washington D. C., 2004: 506-513.

[8] Juan L and Gwun O. A comparison of SIFT, PCA-SIFT and SURF [J]. International Journal of Image Processing, 2009,3(4): 143-152.

[9] Mikolajczyk K and Schmid C. A performance evaluation of local descriptors[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(10): 1615-1630.

[10] Bay H, Ess A, Tuytelaars T, et al.. Speeded-Up Robust Features (SURF)[J]. International Journal on Computer Vision and Image Understanding, 2008, 110(3): 346-359.

[11] Yoon H, Chung H, and Hahn H. SURF Algorithm with color and global characteristics[C]. Proceedings of ICCAS-SICE International Joint Conference, Fukuoka, 2009: 183-187.

[12] Fan P, Men A, Chen M, et al.. Color-SURF: a SURF descriptor with local kernel color histograms [C]. Proceedings of IEEE International Conference on Network Infrastructure and Digit Content Proceedings, Beijing, 2009: 726-730.

[13] Ehsan S, Kanwal N, Clark A, et al.. An algorithm for the contextual adaption of SURF octave selection with good matching performance: best octaves [J]. IEEE Transactions on Image Processing, 2012, 21(1): 297-304.

[14] Fischler M and Bolles R. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[J]. Communications of the Association for Computing Machinery, 1981, 24(6):381-395.

[15] Zhou W, Lu Y, Li H, et al.. Spatial coding for large scale partial-duplicate web image search[C]. Proceedings of the 18th ACM the International Conference on Multimedia, New York, 2010: 25-29.

[16] The Oxford University: Affine Covariant Features Database of Oxford University[OL]. http://www.robots.ox.ac.uk,2012.4.