張 霓，章承成，何熊熊

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

基于壓縮感知的快速SIFT準(zhǔn)稠密匹配算法

張 霓，章承成，何熊熊

(浙江工業(yè)大學(xué) 信息工程學(xué)院，浙江 杭州 310023)

提出了一種基于壓縮感知的SIFT準(zhǔn)稠密立體匹配算法.該算法利用壓縮感知理論的稀疏投影將SIFT的高維特征描述子投影到低維空間上，選取RANSAC算法對匹配的結(jié)果進(jìn)行去偽匹配處理，并將提取的匹配點作為種子點沿著極線方向生長，獲取稠密的視差圖.該算法利用壓縮感知的稀疏投影，大大減小了特征匹配的運算量，同時利用種子生長使視差圖變稠密.實驗結(jié)果表明：與未加入壓縮感知的種子擴(kuò)散立體匹配算法相比，這種算法計算速度更快，誤匹配的百分比也較低，是一種快速有效的立體匹配算法.

SIFT；壓縮感知；RANSAC；立體匹配；種子擴(kuò)散；視差

立體匹配[1]一直是計算機(jī)視覺中的熱點問題，其目的是尋找左右兩幅圖像中的對應(yīng)點以計算視差，獲取物體的深度信息，匹配結(jié)果的好壞直接影響后面三維重建的準(zhǔn)確性.立體匹配算法主要分為稠密匹配、稀疏匹配和準(zhǔn)稠密匹配.稠密匹配是指通過相關(guān)的一些算法來獲取大量的匹配對，生成致密的視差圖[2].經(jīng)典的稠密匹配算法有基于區(qū)域的立體匹配算法，如灰度差絕對值平方和(SAD)算法[3]、歸一化互相關(guān)(NCC)算法[4]以及Census[5]變換算法等，這些稠密立體匹配算法直接對圖像像素點進(jìn)行匹配，雖可獲得稠密的視差圖，但計算復(fù)雜度高，在光照變化的情況下，會發(fā)生左右兩幅圖像幅度失真，其匹配精度會急劇下降.而稀疏匹配是指基于特征的匹配算法，這類立體匹配算法計算量小，速度快，匹配精度高.但由于匹配的是圖像中的一些特征點，只能得到稀疏的視差圖，通過它們只能恢復(fù)出稀疏點云，不能有效恢復(fù)三維立體表面[6].準(zhǔn)稠密匹配算法[7]是介于稠密匹配和稀疏匹配之間的一種立體匹配算法，它克服了兩者的缺點，可以得到比稀疏匹配更為稠密的匹配點，且比稠密匹配的計算量的小、復(fù)雜度低.Lhuillier等[7]提出的準(zhǔn)稠密匹配算法是利用稀疏的匹配點，將其作為種子點并在其周圍擴(kuò)散出更多的匹配點.稀疏種子點的獲取是準(zhǔn)稠密匹配算法的核心組成部分.SIFT算法[8]是目前廣泛應(yīng)用的一種魯棒性最好的特征提取和匹配的算法，因SIFT算子對旋轉(zhuǎn)、尺度和光照都具有不變性而在立體匹配中得到廣泛應(yīng)用.但SIFT算法的特征描述子維數(shù)過高，計算速度慢，不能滿足實時性要求.近年來,壓縮感知理論[9-11]也開始被引入到立體匹配鄰域中.Eva等[12]將CS引入特征提取中，直接從感知測量值中重建感興趣的圖像特征，丟棄不相關(guān)的信息.楊颯等[13]將壓縮感知應(yīng)用到圖像配準(zhǔn)中，提出了稀疏投影與SIFT結(jié)合的圖像配準(zhǔn)算法(SRP-SIFT)，用稀疏投影矩陣對特征點周圍的局部小塊的特征進(jìn)行降維，減少了算法的復(fù)雜性.

為了克服基于SIFT的立體匹配算法計算量大、不能獲取稠密的視差圖的問題，提出了一種用于已標(biāo)定圖像的快速準(zhǔn)稠密立體匹配算法.首先使用SIFT對圖像提取特征點，通過壓縮感知的隨機(jī)投影來降低SIFT的特征向量的維數(shù)，在不丟失特征主要信息的前提下提高了特征匹配的速度；然后將匹配點作為種子點擴(kuò)散到整幅圖像上，得到稠密的視差圖.最后將實驗結(jié)果(基于壓縮感知的SIFT算法加種子擴(kuò)散算法)與SIFT算法加種子擴(kuò)散算法進(jìn)行比較，證明本算法在降低算法復(fù)雜性的同時還保證了視差圖的質(zhì)量.

1 算法思路

本算法基于壓縮感知原理，首先使用SIFT算法檢測圖像的特征點，然后用壓縮感知對獲取的特征點降維，獲取低維的特征向量，再用RANSAC算法對獲取的匹配點去除誤匹配來得到用于區(qū)域增長的種子點；最后沿著極線方向?qū)@些種子點進(jìn)行擴(kuò)散，并把新增的匹配點作為新的種子點，以此類推，最終得到稠密的匹配圖和視差圖.算法的流程圖如圖1所示.

圖1 算法流程圖Fig.1 Algorithm flowchart

2 基于壓縮感知的SIFT種子點提取

基于壓縮感知的SIFT立體匹配算法的第一步是用SIFT算法獲取種子點，并對種子點進(jìn)行匹配，種子點匹配的準(zhǔn)確與否以及匹配速度直接影響了算法的性能.針對SIFT算法的特征向量多，計算復(fù)雜等問題，將SIFT局部特征提取與壓縮感知稀疏投影相結(jié)合，先用SIFT算法提取參考圖像與待測圖像的局部特征，然后采用壓縮感知的隨機(jī)投影將特征向量投影到低維空間上，再進(jìn)行特征匹配.

2.1SIFT特征提取

本算法采用SIFT算法提取圖像的局部特征，具體步驟如下：

1) 建立尺度空間.利用不同尺度空間的差分與圖像的卷積來建立高斯差分尺度空間(DOG)，可得

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))×I(x,y)=L(x,y,kσ)-L(x,y,σ)

(1)

式中：I(x,y)為原始圖像；G(x,y,σ)為高斯核；σ為尺度因子，該值越小表示圖像平滑的越少，相應(yīng)的尺度也越小，Low[8]的論文中初始尺度σ=1.6；L代表圖像的尺度空間.

2)特征點檢測與精確定位.將每個采樣點與它相鄰26個點比較(同尺度8 個、上下相鄰尺度9 個×2 個)[8]，選取最大值或最小值點為候選特征點；用三維二次擬合函數(shù)來得到特征點的精確位置；同時去除不穩(wěn)定的邊緣極值點和對比度低的點，以增強(qiáng)匹配的穩(wěn)定性和抗噪聲能力.

3)特征點的方向.由特征點鄰域像素的梯度的幅值m(x,y)和方向((x,y)來指定特征點的梯度方

向參數(shù)，其中L函數(shù)與式(1)中的L函數(shù)一樣同為圖像的尺度空間，計算式為

(2)

θ(x,y)=tan-1((L(x,y+1)-L(x,y-1))/ (L(x+1,y)-L(x-1,y)))

(3)

4)特征描述子生成.為了增強(qiáng)算法在實驗中的穩(wěn)健性，Low[8]建議對每個特征點采用4 個×4 個種子點來描述，每個種子點含有8 個方向的信息向量，這樣每個特征點的特征向量就有128 維.

2.2 基于壓縮感知的特征壓縮

由于SIFT算法獲取的種子點的特征向量可高達(dá)128 維，而進(jìn)行SIFT特征匹配時必須要計算參考圖像中的特征點與待匹配圖像中每一特征點的距離，而這每一個距離都包含了到128 維的數(shù)據(jù)，這直接導(dǎo)致了匹配時的大計算量.為了實現(xiàn)數(shù)據(jù)的快速匹配，這里引入壓縮感知算法，采用隨機(jī)投影矩陣將高維的特征描述符投影到低維空間上以降低算法的復(fù)雜度，減少算法運行的時間.

將已經(jīng)獲得的128維×1維列向量F稀疏表示為

F=ΨX

(4)

(5)

式中：X為128維×1維列向量；若X中有k個不為零的系數(shù)，則信號X的稀疏度為k；fi為F的元素；xi為X的元素；φi為Ψ的行向量.構(gòu)建一個M維×128維稀疏隨機(jī)投影矩陣R將128維×1維的描述子投影到M維的子空間中，Y為得到的隨機(jī)測量值，得

YM×N=RM×128X128×N,M?12

(6)

這樣每個特征點的信息就包含在了維的特征向量中.為了兼顧隨機(jī)投影的有效性，同時又能夠減少計算的復(fù)雜度，這里選擇s=3，R的矩陣元素為

(7)

2.3 基于壓縮感知的特征匹配

特征描述子降維之后，選擇計算描述子之間的歐式距離作為相似性度量，同時采用最近鄰與次近鄰比值法[14]對特征向量進(jìn)行匹配.設(shè)點A的特征描述向量為UA=[a1,a2,…,am]，點B的特征描述向量為UB=[b1,b2,…,bn]，則UA和UB的絕對值距離為

(8)

在待匹配圖中找出與參考圖像的特征點的描述子距離最近與次近的點B與點C，若d(UA,UB)/d(UA,UC)的比值T小于某個閾值時，則匹配成功.這里設(shè)置的閾值為0.6.最后使用隨機(jī)一致性(Random sample consensus, RANSAC)[15]算法去除由于自身對稱性可能造成的誤匹配點.

3 稠密視差圖的計算

至此，匹配的過程基本結(jié)束，接下來要實現(xiàn)匹配得到的視差圖，由于SIFT特征匹配算法只是完成了離散的特征點匹配，得到的是稀疏的匹配的特征點和稀疏的視差圖，無法獲得完整的圖像匹配點信息.為了得到連續(xù)的匹配點和稠密的視差圖，同時減少擴(kuò)散時間，這里將已獲取的匹配點作為種子點，采用加入極線約束的擴(kuò)散算法對種子點進(jìn)行擴(kuò)散，直至遍歷整個圖像，使視差圖成為一個致密的圖.

種子點擴(kuò)散[16-17]的步驟：將通過RANSAC去除誤匹配之后的穩(wěn)定的匹配點對作為種子點，按照順序?qū)⑺鼈兎湃敕N子隊列中；若隊列非空，取出隊列中第一對種子點，在其鄰域的一定搜索窗內(nèi)尋找匹配點，找到匹配點后就將該對種子點從隊列中刪除，將獲取的新種子點放入種子隊列的末尾中，重復(fù)此步驟直至種子隊列為空.為了提高搜索效率，這里引入極線約束[18](即匹配點一定在對應(yīng)的極線上)，由于這里用于實驗的圖像都是經(jīng)過校準(zhǔn)后的，因此它的匹配點的兩條極線在圖像的同一條行掃描線上.這樣就可以將二維的搜索窗變?yōu)檠刂痪S的極線方向，對左圖中已確定的種子點，在右圖中按照相應(yīng)的極線的方向上進(jìn)行種子點的掃描擴(kuò)散，這樣可以大大減少擴(kuò)散的時間.

其中搜索種子點主要是通過對SIFT計算出的視差建立一個能量函數(shù)[19],即

(9)

式中：d為已匹配的特征點的視差；i為圖像的高度；j為圖像的寬度；L(i,j)，R(i,j)分別為左右圖像中點(i,j)的灰度值，若該能量值小于一定的值，則認(rèn)為該點屬于種子點，掃描直到極線結(jié)束，最終獲得稠密的視差圖.

4 實驗分析

在實時性要求較高的應(yīng)用中，好的立體匹配算法不僅需要獲取準(zhǔn)確的匹配率以及高質(zhì)量的視差圖，同時還要兼顧算法的運算量，而算法的運算量是和特征描述子的維數(shù)息息相關(guān)的.因此為了驗證算法的有效性，實驗一將SIFT算法與基于壓縮感知的SIFT算法從提取的匹配點的數(shù)目、準(zhǔn)確率以及匹配時間上比較；實驗二將SIFT+種子擴(kuò)散算法與基于壓縮感知的SIFT+種子擴(kuò)散算法這兩種算法從匹配的視差圖的好壞、匹配的時間上做比較.實驗圖片選用Middlebury數(shù)據(jù)庫中的Teddy圖片[20].實驗中，軟件工具是Win7 32位操作系統(tǒng)，MATLABR2010b編程環(huán)境，硬件環(huán)境是Corei3，CPU2.4GHz，4GB內(nèi)存.圖2為實驗選取的圖像.

圖2 原圖像Fig.2 Original image

圖3(a)為SIFT算法獲取的作為種子點的匹配點對的匹配結(jié)果，圖3(b)為提出的基于壓縮感知的SIFT算法獲取的種子匹配點對.表1為這兩種方法提取種子點的時間及準(zhǔn)確率比較.從圖3和表1的數(shù)據(jù)可以看出：加入壓縮感知的SIFT算法匹配成功的點數(shù)比SIFT算法少，但匹配速度比SIFT算法快，這是由于使用了壓縮感知的稀疏變換來構(gòu)成低維數(shù)的特征描述符，減少了SIFT描述子匹配時的計算量，所以匹配時間大大減少.同時，該方法通過RANSAC算法可以自行剔除錯誤匹配對，匹配準(zhǔn)確率也較SIFT算法有一定提高，使得其作為擴(kuò)散的種子點更穩(wěn)定.

圖3 種子點提取的實驗結(jié)果比較Fig.3 Comparison of experimental results of extraction of seed dots

算法名稱匹配對的數(shù)量/個正確匹配的數(shù)量/個匹配率/%匹配時間/sSIFT736284．937．382基于壓縮感知的SIFT464393．483．736

圖4(a)為teddy圖片的標(biāo)準(zhǔn)視差圖，圖4(b，c)分別為SIFT+種子極線擴(kuò)散算法以及SIFT+壓縮感知+種子極線擴(kuò)散方法得到的視差圖.從圖4的結(jié)果來看：基于SIFT特征的兩種種子擴(kuò)散匹配算法，都可以取得比較令人滿意的擴(kuò)散結(jié)果.同時，這兩種算法即特征匹配與種子極線擴(kuò)散結(jié)合的算法由于沿極線方向擴(kuò)散，加快了擴(kuò)散的速度，減小了計算冗余，整體算法時間都不長，SIFT+種子擴(kuò)散算法的整體運行時間為26 s，而本算法由于在SIFT特征匹配時還加入了壓縮感知，運行時間僅為15 s，更進(jìn)一步的提高了整體的匹配速度.

圖4 立體匹配視差圖比較Fig.4 Comparison of disparity maps of stereo matching

5 結(jié) 論

傳統(tǒng)的稠密立體匹配算法匹配速度慢，而基于特征的稀疏立體匹配算法獲得視差圖不夠稠密，且SIFT特征匹配的特征描述向量階段的維數(shù)高、計算復(fù)雜以及運算時間長.而基于壓縮感知的SIFT加種子擴(kuò)散的準(zhǔn)稠密立體匹配算法能很好的克服這些缺點，它使用壓縮感知理論的稀疏隨機(jī)投影對SIFT提取的128維特征描述子進(jìn)行降維，大大提高了種子點的匹配速度，從而使整個算法的速度獲得提高；同時使用種子擴(kuò)散理論將匹配的種子點進(jìn)行擴(kuò)散，獲取了稠密的視差圖.采用SIFT+種子擴(kuò)散算法、基于壓縮感知的SIFT+種子擴(kuò)散算法針對圖像進(jìn)行實驗比對，結(jié)果表明：這兩種算法都能獲取較精確的視差圖，且本算法的匹配速度明顯超過未加入壓縮感知的SIFT立體匹配算法.但是該算法針對的是已標(biāo)定的圖像，下一步的研究將是考慮把算法運用到未標(biāo)定的圖像中去，進(jìn)一步考察本算法的匹配有效性.

[1] 湯一平，龐成俊，周宗思，等.雙目全方位視覺傳感器及其極線校正方法[J].浙江工業(yè)大學(xué)學(xué)報，2011,39(1):86-91.

[2] 陳友慶.基于區(qū)域增長的雙目視覺三維重建技術(shù)研究[D].成都：西南交通大學(xué),2010.

[3] 李海濱，劉婷婷，張強(qiáng)，等.采用自適應(yīng)搜索范圍的多介質(zhì)立體匹配算法[J].中國科技論文，2014，9(4):456-464.

[4] WEI S D, LAI S H. Fast template matching based on normalized cross correlation with adaptive multilevel winner update[J]. IEEE transaction on image processing,2008,17(11):2227-2235.

[5] RAMIN Z, JOHN W. Non-parametric local transforms for computing visual correspondence[M]. Stockholm: Computer Vison-ECCV′94,1994:151-158.

[6] 邵琪克,陳勝勇,劉盛.基于約束擴(kuò)散法匹配的序列圖像三維建模研究[D].杭州：浙江工業(yè)大學(xué),2014.

[7] LHUILLIER M, QUAN L. Match propagation for image-based

modeling and rendering[J]. IEEE transactions on pattern analysis and maching intelligence,2002,24(6):1140-1146.

[8] DAVID G L. Distinctive image features from scale-invariant keypoints[J]. International journal of computer vision,2004,60(2):91-110.

[9] DONOHO D L. Compressive sensing[J]. IEEE transaction on informational theory,2006,52(4):1289-1306.

[10] CANDES E, OMBERG J, TAO T. Robust uncertainty principles: exact signal recognition from highly incomplete frequency information[J]. IEEE transaction informational theory,2006,52(2):489-509.

[11] 于愛華,白煌,孫斌斌,等.基于優(yōu)化投影矩陣的人臉識別技術(shù)研究[J].浙江工業(yè)大學(xué)學(xué)報，2016,44(4):392-398.

[12] EVA L, MONTSE N. Compressive spectrum sensing based on spectral shape feature detection[C]//Wireless Communication Systems. Barcelona: Universitat Polit`ecnica de Catalunya,2013:1-5.

[13] 楊颯,楊春玲.基于壓縮感知與尺度不變特征變換的圖像配準(zhǔn)算法[J].光學(xué)學(xué)報,2014,34(11):1-5

[14] 薛振華.圖像局部不變性特征提取與匹配[D].天津：天津大學(xué),2013.

[15] WU X Q, ZHAO Q S, BU W. A SIFT-based contactless palmprint verification approach using iterative RANSAC and local palmprint descriptors[J]. Pattern recognition,2014,47(10):3314-3326.

[16] LIU R, HE L, LU K. An algorithm for image match propagation[C]//Industrial Control and Electronics Engineering(ICICEE), 2012 International Conference on. Berlin: IEEE,2012:759-762.

[17] JUHO K, SAMI S B. Quasi-dense wide baseline matching using match propagation[C]//IEEE Conference on Computer Vision and Pattern Recognition. Berlin: IEEE,2007:1-8.

[18] 葛磊.雙目魚眼鏡頭匹配算法研究[D].天津：天津理工大學(xué),2014.

[19] WANG W, ZHU H. A robust quasi-dense wide baseline matching method[C]//Computational Intelligence and Security(CIS), 2015 11th International Conference on.Portland: IEEE,2015:113-116.

[20] DANIEL S, ALEXANDER V R, RICK S. Middlebury stereo vision page[DB/OL]. [2016-10-10]. http://vision.middlebury.edu/stereo/data/scenes2003/.

(責(zé)任編輯：陳石平)

Fast SIFT quasi-dense matching algorithm based on compressive sensing

ZHANG Ni, ZHANG Chengcheng, HE Xiongxiong

(College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China)

This paper proposes a fast SIFT quasi-dense stereo matching algorithm based on compressive sensing. By the sparse projection of compressive sensing theory, the high-dimensional feature descriptors of SIFT are projected into the low-dimensional space. The RANSAC algorithm is used to remove the false match. The extracted matching points are taken as seed points and grow along the polar line direction to obtain the dense disparity maps. This algorithm uses the sparse projection of compressive sensing to greatly reduce the amount of feature matching calculations. It also uses seed growth to make the disparity map denser. Experimental results show that the algorithm proposed in this paper is faster and the percentage of mis-matched is also lower than the seeded stereo matching algorithm without compressive sensing. It is a fast and effective stereo matching algorithm.

SIFT; compressive sensing; RANSAC; stereo matching; seed diffusion; disparity

2016-10-09

國家自然科學(xué)基金資助項目(61473262)

張 霓(1970—)，女，浙江杭州人，副教授，碩士生導(dǎo)師，研究方向為機(jī)器人視覺、多移動機(jī)器人協(xié)同及無人機(jī)，E-mail：zn@zjut.edu.cn.

TP391

A

1006-4303(2017)03-0310-05