基于PCA-SIFT的立體匹配算法

宋淳愷

（同濟(jì)大學(xué)電子與信息工程學(xué)院，上海 201804)

基于PCA-SIFT的立體匹配算法

宋淳愷

（同濟(jì)大學(xué)電子與信息工程學(xué)院，上海 201804)

在雙目立體視覺(jué)技術(shù)中，立體匹配算法研究是最基本的問(wèn)題，SIFT算法由于對(duì)存在尺度變化等情況下的圖像都能夠?qū)崿F(xiàn)圖像的準(zhǔn)確匹配而受到廣泛的使用。然而，SIFT算法比較復(fù)雜，導(dǎo)致算法耗時(shí)效率低。為了降低算法的復(fù)雜度，滿足研究對(duì)于實(shí)時(shí)性的要求，提出一種小波變換結(jié)合PCA-SIFT算法的綜合的立體匹配算法。采用這種綜合算法能夠剔除大量圖像誤匹配，減少匹配計(jì)算量和時(shí)間，加快運(yùn)算速度。

小波；SIFT算法；立體匹配

0 引言

雙目立體視覺(jué)是圖像處理領(lǐng)域中的熱門(mén)方向，隨著研究的深入，在機(jī)器人、自動(dòng)駕駛等領(lǐng)域得到了使用，是一種從二維圖像中獲取三維信息的方法。它首先獲取左右兩幅圖像的二維位置信息，再根據(jù)左右兩個(gè)攝像機(jī)的參數(shù)和相對(duì)位置，按照視差原理計(jì)算圖像中物體三維距離信息。雙目立體視覺(jué)系統(tǒng)分為攝像機(jī)標(biāo)定、圖像矯正、立體匹配和深度計(jì)算這幾個(gè)步驟，在這里面立體匹配是最關(guān)鍵的部分。在目前的立體匹配算法中，SIFT算法得到了廣泛的使用，在現(xiàn)有的國(guó)內(nèi)外雙目立體視覺(jué)匹配算法中處于領(lǐng)先的地位[1]。SIFT主要優(yōu)點(diǎn)在于其特征點(diǎn)尺度、旋轉(zhuǎn)和光照不變性方面[2～3]明顯優(yōu)于其他特征描述子。但是，如果圖像灰度差異大，將會(huì)導(dǎo)致錯(cuò)誤的匹配。而且SIFT的算法計(jì)算量大，不適用于實(shí)時(shí)性要求較高的系統(tǒng)。

針對(duì)以上的問(wèn)題，本文提出一種基于小波變換和PCA-SIFT算法的立體匹配算法，其目的是提高圖像匹配的速度和精度。圖像經(jīng)過(guò)小波變換之后得到的低分辨率成分受圖像局部細(xì)節(jié)的影響降低，提高了特征提取的能力和速度。而且通過(guò)閾值的設(shè)置，可以剔除匹配點(diǎn)對(duì)中明顯的錯(cuò)誤匹配，獲得相對(duì)精確的結(jié)果。

首先通過(guò)小波分解將圖像分解為低頻成分和高頻成分，對(duì)低頻成分進(jìn)行圖像匹配。然后在使用SIFT算法進(jìn)行匹配時(shí)，用主元分析法替換直方圖法，實(shí)現(xiàn)描述子的降維。減少描述子維數(shù)可以提高匹配速度。最后將實(shí)驗(yàn)結(jié)果與SIFT結(jié)果進(jìn)行對(duì)比，證明本文方法的魯棒性和更高的效率。

1 小波分析

小波分析是繼傅里葉分析后的重大突破，目前已經(jīng)廣泛運(yùn)用于圖像領(lǐng)域。它以傅里葉的頻率變換作為基礎(chǔ)，增加了時(shí)間上的變換，使得其可以在時(shí)間和頻率上分別對(duì)信號(hào)進(jìn)行局部的分析，從而使分析結(jié)果更加的有效。小波分析經(jīng)過(guò)伸縮和平移的方式得到不同尺度的小波，然后利用這些不同的小波分析信號(hào)。小波分析使用時(shí)間分辨率高的小波分析頻率高的信號(hào)，使用頻率分辨率高的小波分析頻率低的信號(hào)[4]。

小波變換基本原理如下：用基函數(shù)的加權(quán)和得到信號(hào)的近似公式，也就是用基函數(shù)來(lái)表示或者逼近信號(hào)。母小波可以通過(guò)伸縮和平移得到基礎(chǔ)函數(shù)[5]，先將母函數(shù)縮放a倍，然后平移b：

在小波變換中，首先需要對(duì)它的兩個(gè)因子進(jìn)行離散化，構(gòu)建規(guī)范的正交基。Haar小波是比較典型的規(guī)范正交基。Haar小波的母小波公式為：

對(duì)應(yīng)的縮放函數(shù)表示為：

Haar小波速度快、維度小，可以滿足算法的實(shí)時(shí)性要求，因此在這里采用Haar小波分析。在多層分析的結(jié)果中，由于從第二層開(kāi)始所得到的低頻分量的圖像匹配點(diǎn)數(shù)很少，而多層分解的反復(fù)，也會(huì)增加匹配的時(shí)間。通過(guò)實(shí)驗(yàn)表明在小波分解的第一層可以得到正確的結(jié)果；但是在小波分解第二和第三層，由于圖像小波分解使圖像信息大幅度減少，會(huì)由于匹配點(diǎn)對(duì)不足而無(wú)法進(jìn)行圖像配準(zhǔn)。因此，在本文中，僅僅使用第一層的低頻分量進(jìn)行匹配。

多尺度小波分解各層重建圖像顯示如圖1所示。

圖1 小波分解

2 PCA-SIFT算法

SIFT，即尺度不變特征轉(zhuǎn)換，是用于圖像處理領(lǐng)域的一種描述符。該算法通過(guò)生成一個(gè)描述符，對(duì)于特征尺度有不變性，能夠在圖像中計(jì)算出關(guān)鍵點(diǎn)，首先構(gòu)建尺度空間找到興趣點(diǎn)，接下來(lái)在興趣點(diǎn)上尋找關(guān)鍵點(diǎn)，利用該點(diǎn)周?chē)c(diǎn)的梯度方向，分配給關(guān)鍵點(diǎn)特定的方向，最后給每一個(gè)關(guān)鍵點(diǎn)設(shè)置一個(gè)矢量作為下一步匹配計(jì)算的依據(jù)，該矢量的維度為128[6～8]。具體步驟如下：

為了能更加有效地檢測(cè)到關(guān)鍵點(diǎn)，將相鄰尺度下的圖像函數(shù)相減得到高斯差分函數(shù)，利用該函數(shù)與圖像函數(shù)進(jìn)行卷積，通過(guò)不同尺度的卷積乘積，最后得到一個(gè)高斯差分的相應(yīng)值圖像D（x，y，σ）。公式為：

為了獲得一個(gè)穩(wěn)定的特征點(diǎn)，將不好的特征點(diǎn)除去，還需要?jiǎng)h減不穩(wěn)定的一部分邊緣點(diǎn)。下式可以確定特征點(diǎn)的穩(wěn)定性。

其中H（x，y）是Hessian矩陣。通過(guò)上一步已經(jīng)可以提取出特征點(diǎn)在圖像中的位置，接下來(lái)要給每個(gè)特征點(diǎn)分配一個(gè)方向，通過(guò)確定關(guān)鍵點(diǎn)周?chē)袼攸c(diǎn)的相應(yīng)梯度方向的分布特征，指定關(guān)鍵點(diǎn)的方向參數(shù)，使其具備旋轉(zhuǎn)不變性。每個(gè)關(guān)鍵點(diǎn)都有其特定的尺度σ，依據(jù)這個(gè)尺度參數(shù)，可以獲得最靠近該尺度值的高斯圖像。把關(guān)鍵點(diǎn)作為中心，以4.5σ為半徑，計(jì)算圖像在這個(gè)區(qū)域中的梯度模值和方向。

m（x，y）是點(diǎn)（x，y）的模值，θ（x，y）是點(diǎn)（x，y）的方向。在關(guān)鍵點(diǎn)的梯度方向處理結(jié)果計(jì)算出來(lái)之后，接著使用直方圖來(lái)統(tǒng)計(jì)關(guān)鍵點(diǎn)周?chē)袼氐奶荻饶Ｖ岛头较颉Ｔ谡麄€(gè)直方圖中，用橫軸來(lái)表示梯度方向，用縱軸來(lái)表示該方向所對(duì)應(yīng)的模值。在關(guān)鍵點(diǎn)梯度信息直方圖中，把0°～360°分成36份，每10度的區(qū)域作為直方圖中的一個(gè)立柱。以直方圖的最大峰值作為該關(guān)鍵點(diǎn)的方向。如果同時(shí)有一個(gè)約有最大峰值80%能量的峰值存在，那么將此方向定義為該點(diǎn)的輔方向。通過(guò)這個(gè)步驟一個(gè)關(guān)鍵點(diǎn)可能測(cè)到不同的幾個(gè)方向，這能夠提高算法魯棒性。

在SIFT算法中，為了保證特征矢量的旋轉(zhuǎn)不變性，首先以特征點(diǎn)為中心，將坐標(biāo)旋轉(zhuǎn)為特征點(diǎn)的主方向，在每個(gè)子區(qū)域8個(gè)方向的梯度上計(jì)算直方圖，通過(guò)繪制每個(gè)方向的模值形成一個(gè)種子點(diǎn)。一個(gè)特征點(diǎn)有4×4個(gè)種子點(diǎn)，每一個(gè)種子點(diǎn)的向量信息有8個(gè)方向，因此一共有4×4×8=128維。在生成兩幅圖像的SIFT特征向量之后，需要計(jì)算關(guān)鍵點(diǎn)的向量之間的歐氏距離，并以距離值作為關(guān)鍵點(diǎn)的相似度判定值。把第一幅圖像中的一個(gè)關(guān)鍵點(diǎn)取出來(lái)，并從第二幅圖像中找出其與前者歐氏距離最近的前兩個(gè)關(guān)鍵點(diǎn)，找到這兩個(gè)后計(jì)算它們同第一幅中關(guān)鍵點(diǎn)的歐氏距離，如果較小的值除以較大的值小于一定的百分比閾值，則為可以接受的匹配點(diǎn)。降低閾值雖然會(huì)減少匹配點(diǎn)數(shù)，但是會(huì)提高穩(wěn)定性。

SIFT的尺度不變性可以減小尺度、光照和旋轉(zhuǎn)對(duì)匹配的影響，提高匹配成功率，但是考慮到SIFT以下特點(diǎn)[9]：

（1）SIFT特征提取算法需要反復(fù)地計(jì)算平滑卷積和統(tǒng)計(jì)加權(quán)直方圖，浮點(diǎn)計(jì)算極大，因而算法復(fù)雜度高、計(jì)算時(shí)間長(zhǎng)。

（2）SIFT算法提取大量特征點(diǎn)，但其中只有很少一部分可以正確匹配，給未匹配成功的特征點(diǎn)建立描述子會(huì)占用大量時(shí)間，影響匹配和搜索速度。

這里采用改進(jìn)的PCA-SIFT，在保留尺度不變性的同時(shí)降低維度，大量減少了算法運(yùn)行的時(shí)間。Y.Ke和R.Sukthankar提出的PCA-SIFT，用主元分析法來(lái)替換原SIFT算法中的直方圖法，實(shí)現(xiàn)描述子的降維[10]。主要區(qū)別在于描述子的簡(jiǎn)化：不再使用原來(lái)的4×4×8個(gè)描述子，而是以41×41的圖像區(qū)域作為一個(gè)計(jì)算范圍，得到數(shù)量為3042個(gè)的梯度導(dǎo)數(shù)，然后采用PCA方法，將之前得到的3042維方向矢量降到36維。

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

為了驗(yàn)證算法的有效性，將不同算法做實(shí)驗(yàn)比較，并對(duì)結(jié)果進(jìn)行分析。在實(shí)驗(yàn)中對(duì)SIFT、PCA-SIFT、小波+SIFT、小波+PCA-SIFT的性能進(jìn)行了對(duì)比分析。實(shí)驗(yàn)結(jié)果如圖所示。

圖2～圖4為同一組圖像在不同匹配算法下的效果圖，圖中顯示的均為經(jīng)過(guò)圖像校正后的輸出圖像。左、右半部分別為左攝像機(jī)和右攝像機(jī)拍攝的圖像。由以上4種匹配方法得出的性能結(jié)果統(tǒng)計(jì)見(jiàn)表1。

表1 匹配結(jié)果統(tǒng)計(jì)

圖2 SIFT方法

圖3 PCA-SIFT方法

圖4 小波+SIFT方法

圖5 小波+PCA-SIFT方法

由匹配結(jié)果可以得出，采用小波變換進(jìn)行預(yù)處理后減少了匹配點(diǎn)數(shù)，降低了匹配復(fù)雜度，減少了算法的運(yùn)行時(shí)間。綜合采用小波和PCA-SIFT變換的算法在降低了特征提取和特征匹配的復(fù)雜度的同時(shí)，提高了圖像特征點(diǎn)的正確匹配率，最終大大增強(qiáng)了算法的實(shí)時(shí)性。

4 結(jié)語(yǔ)

從上述理論分析和實(shí)驗(yàn)結(jié)果可以看出，基于小波和PCA-SIFT算法的方法能夠滿足較高精度，同時(shí)使得特征提取和匹配的復(fù)雜度大大降低，算法在實(shí)時(shí)性和準(zhǔn)確性方面得到了顯著的提高。由上述算法的分析以及實(shí)驗(yàn)結(jié)果對(duì)比可見(jiàn):

（1）文中提出的算法采用基于PCA-SIFT的特征匹配，在保證匹配結(jié)果有效性和準(zhǔn)確性的同時(shí)，極大提高了匹配效率和運(yùn)算速度。

（2）PCA-SIFT算法在特征匹配時(shí)需要檢測(cè)特征點(diǎn)，這一步要多次使用高斯差分函數(shù)進(jìn)行運(yùn)算，占據(jù)了大部分時(shí)間。文中算法為了減少特征描述生成的次數(shù)，在生成特征描述子之前先對(duì)圖片進(jìn)行小波分解，使得該階段的計(jì)算量大大減少，迅速提高了實(shí)時(shí)性。小波+ PCA-SIFT算法生成的特征點(diǎn)個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于SIFT算法，從而使匹配特征點(diǎn)數(shù)大量減少，縮短了匹配的時(shí)間。

[1] 潘華，郭戈.立體視覺(jué)研究的進(jìn)展[J].計(jì)算機(jī)測(cè)量與控制，2004，12（12）：1121～1124

[2] DG，L..Distinctive Image Features from Scale-Invariant Keypoints[J]，2004，60（2）:91～110

[3] K.，M.，S.C..A Performance Evaluation of Local Descriptors[C].2005，27（10）:1615～1630

[4] 孫延奎.小波分析及其應(yīng)用[J]，2004:199～205

[5] 宋國(guó)鄉(xiāng)，馮象初，甘小冰.數(shù)值泛函與小波理論[J]，2003:西安電子科技出版社

[6] 宰小濤，趙宇明.基于SIFT特征描述子的立體匹配算法[C].微計(jì)算機(jī)信息，2007，23（24）：285～287

[7] Lowe，D.G.，I.O.E.A.Engineer.Object Recognition from Local Scale-Invariant Features[M].in Computer Vision，1999.The Proceedings of the Seventh IEEE International Conference on vol.2.1999

[8] Cong，Y.，X.Chen，Y.Li.Research on the SIFTAlgorithm in Image Matching[C].in ICFMD2011.2011.Taiwan，China

[9] 趙欽君，趙東標(biāo)，韋虎.Harris-SIFT算法及其在雙目立體視覺(jué)中的應(yīng)用[J].電子科技大學(xué)學(xué)報(bào)，2010，39（4）：546～550

[10] R，Y.K.S.A More Distinctive Representation for Local Image Descriptors[J].in IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2004.Washington，USA

Stereo Matching Algorithm Based on PCA-SIFT

SONG Chun-kai
（School of Electronics and Information Engineering，Tongji University，Shanghai 201804）

In binocular stereo vision technology,stereomatching algorithm research is themost basic problem,SIFT algorithm has been widely used due to be able to achieve the accuracy of the image matching in circumstances such as changing the existing scale of image.However, SIFT computation is too complex so it leads to a long time,and the efficiency is low.In order to reduce the complexity of the algorithm to achieve real-time requirements in research,proposes a combination of wavelet transform and PCA-SIFT stereo matching algorithm. Adopting this integrated algorithm can eliminate a large number of image matching errors,reduce the matching computation,shorten matching time,speed up the operation.

Wavelet;SIFTA lgorithm;Stereo Matching

1007-1423（2015）06-0031-05

10.3969/j.issn.1007-1423.2015.06.007

宋淳愷（1989-），男，浙江慈溪人，在讀碩士研究生，研究方向?yàn)閳D像處理立體視覺(jué)領(lǐng)域

2015-01-08

2015-01-20