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

張 霓，章承成，何熊熊

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

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

張 霓，章承成，何熊熊

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

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

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

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

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

1 算法思路

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

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

2 基于壓縮感知的SIFT種子點(diǎn)提取

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

2.1SIFT特征提取

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

1) 建立尺度空間.利用不同尺度空間的差分與圖像的卷積來(lái)建立高斯差分尺度空間(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)特征點(diǎn)檢測(cè)與精確定位.將每個(gè)采樣點(diǎn)與它相鄰26個(gè)點(diǎn)比較(同尺度8 個(gè)、上下相鄰尺度9 個(gè)×2 個(gè))[8]，選取最大值或最小值點(diǎn)為候選特征點(diǎn)；用三維二次擬合函數(shù)來(lái)得到特征點(diǎn)的精確位置；同時(shí)去除不穩(wěn)定的邊緣極值點(diǎn)和對(duì)比度低的點(diǎn)，以增強(qiáng)匹配的穩(wěn)定性和抗噪聲能力.

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

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

(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)算法在實(shí)驗(yàn)中的穩(wěn)健性，Low[8]建議對(duì)每個(gè)特征點(diǎn)采用4 個(gè)×4 個(gè)種子點(diǎn)來(lái)描述，每個(gè)種子點(diǎn)含有8 個(gè)方向的信息向量，這樣每個(gè)特征點(diǎn)的特征向量就有128 維.

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

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

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

F=ΨX

(4)

(5)

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

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

(6)

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

(7)

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

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

(8)

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

3 稠密視差圖的計(jì)算

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

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

其中搜索種子點(diǎn)主要是通過(guò)對(duì)SIFT計(jì)算出的視差建立一個(gè)能量函數(shù)[19],即

(9)

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

4 實(shí)驗(yàn)分析

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

圖2 原圖像Fig.2 Original image

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

圖3 種子點(diǎn)提取的實(shí)驗(yàn)結(jié)果比較Fig.3 Comparison of experimental results of extraction of seed dots

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

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

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

5 結(jié) 論

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

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

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

[3] 李海濱，劉婷婷，張強(qiáng)，等.采用自適應(yīng)搜索范圍的多介質(zhì)立體匹配算法[J].中國(guó)科技論文，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í)別技術(shù)研究[J].浙江工業(yè)大學(xué)學(xué)報(bào)，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é)報(bào),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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61473262)

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

TP391

A

1006-4303(2017)03-0310-05