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

宋淳愷

（同濟大學電子與信息工程學院，上海 201804)

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

宋淳愷

（同濟大學電子與信息工程學院，上海 201804)

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

小波；SIFT算法；立體匹配

0 引言

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

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

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

1 小波分析

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

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

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

對應的縮放函數表示為：

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

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

圖1 小波分解

2 PCA-SIFT算法

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

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

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

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

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

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

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

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

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

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

3 實驗結果與分析

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

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

表1 匹配結果統計

圖2 SIFT方法

圖3 PCA-SIFT方法

圖4 小波+SIFT方法

圖5 小波+PCA-SIFT方法

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

4 結語

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

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

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

[1] 潘華，郭戈.立體視覺研究的進展[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] 孫延奎.小波分析及其應用[J]，2004:199～205

[5] 宋國鄉，馮象初，甘小冰.數值泛函與小波理論[J]，2003:西安電子科技出版社

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

2015-01-08

2015-01-20