錢 超，張曉林

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

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

錢 超，張曉林

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

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

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

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

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

f是相機(jī)的焦距，B是相機(jī)中心之間的距離。

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

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

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

1 文中算法

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

圖1 算法步驟

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

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

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

1）構(gòu)建Hessian矩陣：

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

2）對Hessian矩陣的行列式進(jìn)行簡化：

3）構(gòu)建尺度空間精確定位極值點(diǎn)。

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

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

Delauney三角剖分的準(zhǔn)則：

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

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

1.3 SLIC超像素分割算法

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

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

2）所使用的加權(quán)的距離度量標(biāo)準(zhǔn)結(jié)合了顏色和空間的近似結(jié)果，與此同時(shí)還控制著超像素塊的大小和緊湊性。

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

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

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

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

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

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

我們使用最大后驗(yàn)概率來計(jì)算視差，后驗(yàn)概率可以表示為：

找出使得這個(gè)后驗(yàn)概率最大的dn作為每個(gè)像素的視差值。表示與在同一極線上的右圖中的觀察點(diǎn)。通過建?？傻糜^察點(diǎn)有如下的性質(zhì)：

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

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

在此之后，將左圖求右圖和右圖求左圖的結(jié)果利用一致性判斷去除不一致點(diǎn)集。

2 實(shí)驗(yàn)驗(yàn)證

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

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

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

圖2 所提算法在Middlebury圖像對上的結(jié)果

表1 匹配結(jié)果誤差百分比

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

3 結(jié)束語

文中將匹配好的穩(wěn)定特征點(diǎn)和SLIC超像素分割的結(jié)果作為先驗(yàn)知識，利用貝葉斯的方法對后續(xù)匹配作出了限制，提高了匹配精度，減少了大區(qū)域的匹配誤差，與此同時(shí)，由于其余像素搜索空間的減小在運(yùn)行時(shí)間方面也有了較大提升。在匹配精度方面，穩(wěn)定特征點(diǎ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

中國科學(xué)院戰(zhàn)略性先導(dǎo)科技專項(xiàng)（B類）（XDB02080005）

錢 超（1991—），男，江蘇揚(yáng)州人，碩士研究生。研究方向：計(jì)算機(jī)視覺。