宋淳愷

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

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

宋淳愷

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

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

小波；SIFT算法；立體匹配

0 引言

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

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

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

1 小波分析

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

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

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

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

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

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

圖1 小波分解

2 PCA-SIFT算法

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

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

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

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

m（x，y）是點（x，y）的模值，θ（x，y）是點（x，y）的方向。在關(guān)鍵點的梯度方向處理結(jié)果計算出來之后，接著使用直方圖來統(tǒng)計關(guān)鍵點周圍像素的梯度模值和方向。在整個直方圖中，用橫軸來表示梯度方向，用縱軸來表示該方向所對應(yīng)的模值。在關(guān)鍵點梯度信息直方圖中，把0°～360°分成36份，每10度的區(qū)域作為直方圖中的一個立柱。以直方圖的最大峰值作為該關(guān)鍵點的方向。如果同時有一個約有最大峰值80%能量的峰值存在，那么將此方向定義為該點的輔方向。通過這個步驟一個關(guān)鍵點可能測到不同的幾個方向，這能夠提高算法魯棒性。

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

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

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

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

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

3 實驗結(jié)果與分析

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

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

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

圖2 SIFT方法

圖3 PCA-SIFT方法

圖4 小波+SIFT方法

圖5 小波+PCA-SIFT方法

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

4 結(jié)語

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

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

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

[1] 潘華，郭戈.立體視覺研究的進(jìn)展[J].計算機(jī)測量與控制，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] 宋國鄉(xiāng)，馮象初，甘小冰.數(shù)值泛函與小波理論[J]，2003:西安電子科技出版社

[6] 宰小濤，趙宇明.基于SIFT特征描述子的立體匹配算法[C].微計算機(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算法及其在雙目立體視覺中的應(yīng)用[J].電子科技大學(xué)學(xué)報，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-），男，浙江慈溪人，在讀碩士研究生，研究方向為圖像處理立體視覺領(lǐng)域

2015-01-08

2015-01-20