基于穩(wěn)定特征點和SLIC超像素分割的快速立體匹配

錢 超，張曉林

（中國科學院 上海微系統(tǒng)與信息技術研究所，上海 200050）

基于穩(wěn)定特征點和SLIC超像素分割的快速立體匹配

錢 超，張曉林

（中國科學院 上海微系統(tǒng)與信息技術研究所，上海 200050）

針對目前立體匹配中存在的匹配精度和匹配速度很難兼顧的問題，提出了一種基于穩(wěn)定特征點和SLIC超像素分割算法的快速立體匹配。利用SURF算法高速有效地提取出特征點進行匹配，并且利用三角剖分的方法對穩(wěn)定特征點作進一步處理，以此匹配作為先驗知識來減少其余各點的匹配誤差和搜索空間，同時又加入了SLIC超像素分割算法的限制因素進一步提高精度，這樣使得立體匹配算法在精度上和速度上都得到了很好的提高。對Middlebury中的標準數(shù)據(jù)進行測試的結果表明，該算法能較為快速準確地獲得視差。

機器視覺；立體匹配；SLIC超像素分割算法；三角剖分；SURF算法

通過校正好的圖像對獲取圖像深度信息是三維重建等計算機視覺問題中很重要的一部分，我們一般稱之為立體匹配獲取視差。這在三維重建、虛擬視點渲染、自動駕駛、醫(yī)療診斷中都有著廣闊的應用。

視差是指一個物體在左右兩幅圖上水平坐標的差距，比如視差為d的物體在左圖的坐標是（x，y），在右圖的坐標是（x-d，y）。在得到了視差d之后，我們可以用三角測量的原理計算圖像深度信息：

f是相機的焦距，B是相機中心之間的距離。

根據(jù)Scharstein and Szeliski（2002）的綜述，典型的立體匹配算法分為 4個步驟：匹配代價計算、代價聚合、視差計算、視差優(yōu)化[1]。前兩步是關于代價計算的部分，而后兩部分是視差計算的部分。

根據(jù)匹配方式不同可以將立體匹配算法分為兩類：局部匹配和全局匹配。其中局部方法選擇那個使得圖像中小區(qū)域內(nèi)總體不相似度最小的視差值，而全局方法則是通過最小化一個關于整幅圖相似性和平滑性的能量函數(shù)來求得視差。局部方法有cencus變換算法[2]，自適應窗口匹配算法[3]，總體而言匹配速度較快，但是在面對光照、弱紋理或者紋理重復、遮擋等等傳統(tǒng)立體匹配挑戰(zhàn)的時候局部性這個特性往往使得表現(xiàn)不盡如人意；相對而言全局方法克服了這些問題，計算復雜度大大增高，典型的全局方法有 BP（置信度傳播）[4]、圖割[5]等等，這些算法在實際使用的時候十分依賴計算能力以及性能的優(yōu)化。

文中提出了一種基于穩(wěn)定特征點和SLIC超像素分割算法的立體匹配，用SURF算法[6]提取特征點，再利用這些穩(wěn)定特征點的高魯棒性匹配作為約束，使用三角剖分[7]的方法形成2D網(wǎng)格作為其余像素視差判斷的先決條件，再加入SLIC超像素分割算法[8]的結果來約束增加平滑性，最后得到優(yōu)化的視差結果。

1 文中算法

首先，用SURF算法提取左右兩幅圖的特征點，進行匹配，去除非平行匹配點，得到穩(wěn)定匹配的特征點，再利用這些穩(wěn)定匹配的特征點使用三角剖分的方法形成2D網(wǎng)格作為剩余像素視差判斷的先決條件，在約束中同時加入SLIC超像素分割算法的結果以增加視差圖的連續(xù)性，最后經(jīng)過一致性判斷后得到優(yōu)化過的視差圖。

圖1 算法步驟

1.1 SURF算法特征提取和匹配優(yōu)化

SURF（Speeded Up Robust Feature）意指加速的具有魯棒性的特征，由Bay2006年提出。這項技術由SIFT[9-10]算子改進而來，比SIFT快好幾倍，采用了harr特征[11]以及積分圖像的概念，這大大加快了程序運行時間。

國內(nèi)干法分級設備的回收率一般在60%～70%，同時因分選設備的磨損快、高壓風機的安全經(jīng)濟問題以及細灰的收集和除塵等問題，均制約著電選的進一步發(fā)展。由于電選脫炭效率低、工藝不成熟，目前還未獲得廣泛應用。湖南某研究院于2006年在福建青州某造紙廠的自備電廠內(nèi)進行了電選法工業(yè)試驗研究，但系統(tǒng)一直不穩(wěn)定，精礦熱值小于12.54 MJ/kg，尾灰燒失量大于10%，至今未正常使用。

1）構建Hessian矩陣：

其中I（x，y）代表圖像像素，G（t）代表二階標準高斯函數(shù)

2）對Hessian矩陣的行列式進行簡化：

3）構建尺度空間精確定位極值點。

4）確定方向得到特征描述子。

1.2 三角剖分建立2D網(wǎng)格

Delauney三角剖分的準則：

1）空圓特性：Delaunay三角網(wǎng)是唯一的 （任意四點不能共圓），在Delaunay三角形網(wǎng)中任一三角形的外接圓范圍內(nèi)不會有其它點存在。

2）最大化最小角特性：在散點集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角盡可能的大。

1.3 SLIC超像素分割算法

SLIC（Simple linear iterative clustering）簡單線性迭代聚類事實上是k-means[12]在超像素生成上的一個應用，不過有兩個重要的區(qū)別：

1）優(yōu)化過程中距離計算的數(shù)目會隨著搜索空間接近超像素大小而顯著減少。

2）所使用的加權的距離度量標準結合了顏色和空間的近似結果，與此同時還控制著超像素塊的大小和緊湊性。

1.4 視差獲得及優(yōu)化

我們已經(jīng)得到了部分穩(wěn)定特征點的匹配，現(xiàn)在用貝葉斯方法進行分析。用S={s1，s2，…，sM}代表匹配好的穩(wěn)定特征點對，對于每一個穩(wěn)定特征點 sM=（uM，vM，dM）T，其中（uM，vM）代表坐標，dM代表視差。令O={o1，o2，…，oN}作為參考圖像中的待匹配點，假設左右圖像對應的觀察點和S在給定視差的條件下滿足獨立分布，則聯(lián)合概率分布函數(shù)為：

定義先驗分布函數(shù)為均勻分布與高斯采樣的線性和:

其中i表示點（un，vn）所屬三角剖分的索引數(shù)，通過方程組可以解出每一個參數(shù)（ai，bi，ci）。

相似度定義為以觀察點為中心的9*9窗口的像素的NCC函數(shù)[14]，以含有約束條件的Laplace分布作為似然概率分布：

其中β是一個常量，概率不為0的條件保證了在同一條極線上尋找右圖的匹配點。

我們使用最大后驗概率來計算視差，后驗概率可以表示為：

找出使得這個后驗概率最大的dn作為每個像素的視差值。表示與在同一極線上的右圖中的觀察點。通過建模可得觀察點有如下的性質(zhì)：

對于每一個視差dn，在右圖中的觀察點都是唯一的，所以我們用取了概率密度函數(shù)的負對數(shù)的能量函數(shù)求解使得p最大的視差：

只有當{d-μ|＜3σ的時候才計算能量函數(shù)，通過對每個像素操作，可以得到稠密的視差圖。由于像素點可以處于多個三角形內(nèi)，那么這些最小化能量函數(shù)的計算可以并行進行。

在此之后，將左圖求右圖和右圖求左圖的結果利用一致性判斷去除不一致點集。

2 實驗驗證

為了驗證算法的實際效果，將算法的每一步依次實現(xiàn)，并采用國際通用的Middlebury立體匹配算法測試平臺上的4組圖像數(shù)據(jù)集進行測試。這4組圖像數(shù)據(jù)分別是：Tsukuba、Venus、Teddy[15]、Cones，都有真實的視差Ground Truth可供對比。實驗結果均在CPU為Intel core i5 2.40GHz，操作系統(tǒng)為Windows7的PC上用VS2010開發(fā)編譯平臺實現(xiàn)的，多幅圖像平均每幅運行時間為1.572 3 s。實驗結果如下：

其中Tsukuba的分辨率是 384*288，Venus的分辨率是434*383，Teddy和Cones的分辨率是450*375。

表1顯示了所提出的算法與現(xiàn)有幾個算法效果對比，其中精確的值是根據(jù)Middlebury網(wǎng)站上的真實視差圖計算得來，在表中，我們計算了非遮擋區(qū)域 （Nonocc）、所有區(qū)域（All）、視差不連續(xù)區(qū)域（Disc）所產(chǎn)生的匹配錯誤像素點所占的百分比，相應的調(diào)整誤差計算的范圍即可。

圖2 所提算法在Middlebury圖像對上的結果

表1 匹配結果誤差百分比

可以看出，由于穩(wěn)定特征點的較為準確的先驗知識，所提算法在視差不連續(xù)區(qū)域有一定的優(yōu)勢，總體效果優(yōu)于所對比的其余算法。

3 結束語

文中將匹配好的穩(wěn)定特征點和SLIC超像素分割的結果作為先驗知識，利用貝葉斯的方法對后續(xù)匹配作出了限制，提高了匹配精度，減少了大區(qū)域的匹配誤差，與此同時，由于其余像素搜索空間的減小在運行時間方面也有了較大提升。在匹配精度方面，穩(wěn)定特征點的選擇和得到視差后的優(yōu)化還可以有所提升。

[1]Scharstein D，Szeliski R.A Taxonomy and evaluation of dense Two-frame stereo correspondence algorithms[J].International Journal of Computer Vision，2002，47（1-3）:7-42.

[2]Weber M，Humenberger M，Kubinger W.A very fast censusbased stereo matching implementation on a graphics processing unit[C]//2009 IEEE 12th International Conference on. Computer Vision Workshops（ICCV Workshops），2009:786-793.

[3]Kuk-Jin Y，In So K.Adaptive support-weight approach for correspondence search[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2006，28（4）:650-656.

[4]Felzenszwalb P F，Huttenlocher D P.Efficient belief propagation for early vision[J].International Journal of Computer Vision，2006，70（1）:41-54.

[5]Kolmogorov V，Zabih R.Computing visual correspondence with occlusions using graph cuts[C]//Computing visual correspondence with occlusions using graph cuts.IEEE，2001（2）:508-515.

[6]Bay H，Tuytelaars T，Gool L V.SURF:Speeded up robust features[J].Computer Vision&Image Understanding，2006，110（3）:404-417.

[7]Lee D T，Schachter B J.Two algorithms for constructing a delaunay triangulation[J].International Journal of Parallel Programming，1980，9（3）:219-242.

[8]Radhakrishna A，Appu S，Kevin S，et al.SLIC superpixels compared to state-of-the-art superpixel methods[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2012，34（11）:2274-2282.

[9]Lowe D G.Object recognition from local scale-invariant features[C]//1999.The Proceedings of the Seventh IEEE International Conference on.Computer Vision，1999（2）:1150-1157.

[10]Lowe D G.Lowe D G.Distinctive image features from Scaleinvariant keypoints[J].International Journal of ComputerVision，2004，60（2）：91-110.

[11]Mita T，Kaneko T，Hori O.Joint Haar-like Features for Face Detection [C]//Tenth IEEE International Conference on. Computer Vision，Iccv，2005（2）:1619-1626.

[12]Kanungo T，Mount D M，Netanyahu N S，et al.An Efficient k-Means Clustering Algorithm:Analysis and Implementation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence，2002，24（7）:881-892.

[13]Geiger A，Roser M，Urtasun R.Efficient Large-Scale Stereo Matching[C]//Proceedings of the 10th Asian conference on Computer vision-Volume Part I.Springer-Verlag，2010:25-38.

[14]Yoo J C，Han T H.Fast Normalized Cross-Correlation[J].Circuits Systems&Signal Processing，2009，28（6）:819-843.

[15]Scharstein D，Szeliski R.High-accuracy stereo depth maps using structured light[C]//In IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR 2003），2003（1）：195-202.

Fast stereo matching algorithm based on steady features and SLIC superpixels

QIAN Chao，ZHANG Xiao-lin
（Shanghai Institute of MicroSystem and Information Technology，Chinese Academy of Sciences，Shanghai 200050，China）

Focus on the problem existing in stereo matching that the accuracy and speed can not advance together，we propose a fast matching algorithm which is based on steady feature points and SLIC Superpixels.We use SURF algorithm to extract the feature points efficiently，then these points is triangulated for building a prior on disparities to reduce the search space and matching errors，SLIC Superpixels is treated as another restrictive condition at the mean time for further advancing matching accuracy and speed.Results for Middlebury standard test data shows that the algorithm can obtain disparities more quickly and accurately.

machine vision；stereo matching；SLIC Superpixels algorithm；triangulation；SURF algorithm

TN911.73

A

1674－6236（2016）23-0146-03

2016-03-21稿件編號：201603287

中國科學院戰(zhàn)略性先導科技專項（B類）（XDB02080005）

錢 超（1991—），男，江蘇揚州人，碩士研究生。研究方向：計算機視覺。