卷 第 22 期 .32 No.22 第 32 Vol ·人工智能及识别技术· 计 算 机 工 程 Computer Engineering 2006 年 11 月 November 2006 文章编号：1000—3428(2006)22—0209—03 文献标识码：A 中图分类号：TP391 基于图像分割的快速立体匹配算法 徐 青1，王敬东1，李 鹏1，李洪海2 (1. 南京航空航天大学自动化学院，南京 210016；2. 淮阳工学院，淮安 223200) 摘 要：针对 Tao 的平滑表面假设提出了一种基于图像分割的快速立体匹配算法。算法把参考图分割成多个区域，计算其中可靠区域的平 面模板，通过贪婪算法把平面模板分配给不可靠区域使得全局评价函数取到最小值。该算法能克服基于局部算法中存在的边界模糊，以及 低纹理区误匹配严重的缺点，解决了传统的基于全局算法中计算量过大的问题。实验表明，该算法能同时满足高精度和高实时性的要求。 关键词：立体匹配；图像分割；贪婪算法 Fast Stereo Matching Algorithm Based on Image Segmentation XU Qing1, WANG Jingdong1, LI Peng1, LI Honghai2 (1. College of Automation Engineering, Nanjing University of Aeronautics & Astronautics, Nanjing 210016; 2. Huaiyin lnstitute of Technology, Huaian 223200) 【Abstract】This paper presents a segment-based stereo matching algorithm using Tao’s smooth surface hypothesis. In proposed algorithm, the reference image is divided into segments, the planes of reliable segments are computed. A greedy strategy is used to minimize the global energy. The proposed algorithm can overcome the shortcoming of local algorithms which do poorly in textureless areas or near discontinuities. The expensive computing cost for traditional global algorithms can also be resolved. Experiments demonstrate that the algorithm can meet both demands for high resolution and real time. 【Key words】Stereo matching; Image segmentation; Greedy algorithm 1 概述 立体匹配通过寻找同一空间景物在不同视点下投影图像 的像素间的一一对应关系，最终得到该景物的视差图。本文 讨论的是立体匹配中双目视觉的情况，即只对两张图片进行 处理。立体匹配是目前计算机视觉研究中的一个难点和热点， 在许多计算机视觉的应用中它都是很关键的一个步骤，如三 维重构(3D reconstruction)[1]、基于图像的绘制(Image Based Rendering)[2]等。 Daniel Scharstein和Richard Szeliski对目前常见的一些立 体匹配算法和算法的评判标准做了一个很好的总结[3]。总体 来说，立体匹配算法大致可分为 2 类：(1)基于区域(窗口)的 算法，这种算法能够很容易地恢复出高纹理区域的视差，但 在低纹理区域会造成大量的误匹配，从而导致边界模糊，同 时对遮挡的区域也很难进行处理；(2)基于全局的算法，该算 法一般用相容性约束和平滑性约束来构成一个评价函数，再 通过各种最优算法来求得评价函数的最小值，尤其是采用最 小割(graph cuts)思想的算法[4]在精度上取得了很好的效果。 然而传统的基于全局的算法存在的最大问题是计算量过大， 在实时性要求比较高的情况下不适合采用。 Tao提出一种基于彩色图像分割的立体匹配算法框架[5]， 该算法框架基于平滑表面假设，即在单一的色彩区域中视差 变化是平滑的，这样就可以通过一个平面模板(以下简称平面 模 板 为 模 板 ) 公 式 ([ 为模板参数)，由该公式计算出来的视差称之为模 板视差。基于这个假设，就可以把传统的基于全局算法中对 每个点分配最优视差的问题转化为对每个区域分配最优模板 d x y ( , a bx = + ]T c + cy a b ) 来 描 述 该 区 域 的问题，从而大大提高了算法的实时性。 本算法借鉴了 Tao 算法框架的基本思想，对模板计算和 评价函数的选取进行了改进。在 Tao 的算法中，模板参数为 直接对分割后对所有区域进行计算所得，由于分割后存在一 些可靠点较少的区域(不可靠区域)，因此这些区域计算出来 的模板参数并不准确。本算法先只对可靠点数较多的区域(可 靠区域)计算其模板参数，并采用区域融合的方法进行模板优 化，从而增强了模板计算的鲁棒性。另外在全局优化过程中， 本算法采用了新的评价函数，使得模板对各区域的相似度匹 配代价只需计算一次，进一步降低了算法的计算量。 2 图像分割算法 图像分割是整个算法的基础，本算法采用Pedro和Daniel 提出的基于图论的高效图像分割算法[6]，该算法具有精度高 和实时性好的特点。一般来说，为了使平滑表面假设更加可 靠，应使各区域色彩尽量单一，可将区域间色彩差异的阈值 参数适当调低，使划分的区域偏小一点。 表 1 给出了各张检验图进行图像分割的运算时间。图 1 为 Tsukuba 图用该算法进行图像分割后的结果。本文中算法 结果均在 CPU 为 Pentium4 2.8GHz 的 PC 机上运行所得，操 作系统为 WindowsXP，编程工具为 VC6。用于检验本算法的 图 片 全 部 来 自 Middlebury 图 片 库 (www.middlebury.edu/ stereo)，这些图片可以检验立体匹配算法在各种不同环境下 的表现情况。 作者简介：徐 青(1981－)，男，硕士生，主研方向：计算机视觉； 王敬东，副教授；李 鹏、李洪海，讲师 收稿日期：2006-05-28 E-mail：nuaaxq@hotmail.com —209— 

表 1 各张检验图进行图像分割的运算时间 图 片 Venus (434×383) Sawtooth (434×380) Tsukuba (384×288) Map (284×216) 运算时间(s) 0.703 0.703 0.438 0.219 (a) 原图 (b)分割效果 图 1 Tsukuba 图的原图和分割效果 3 模板计算 3.1 视差初始值获取 为了讨论方便，假设两幅图像的外极线已经被校准过了， x y )相匹 ', )与匹配图中的一点( ' 如果参考图中的一点( x , 配，则应满足以下的对应关系： y ' ⋅ , , ( ) x x + 1± y y =' d x y ( ， yxds ，用于保证视差 = 式中 s ＝ 中均选取左视图为参考图，右视图为匹配图，故取 (1) ) 始终为非负值。本文 s ＝－1。 本算法先采用了SAD(Sum of Absolute Differences)计算 各像素在不同视差时的匹配代价(matching cost)。如果采用大 窗口进行计算，在低纹理区将获得更加可靠的初始匹配结果， 但同时也会不可避免地增强前景膨胀效应[1]，所以在本算法 中所有点的匹配代价都用 3×3 小窗口进行计算。 视差的初始值的精确性对模板的估计影响很大，除了通 常采用的交叉校验外，又加入了相似点滤除[7]的处理，从而 增强了初始值的可靠性。若参考图中的某点在匹配图中存在 可靠匹配点，该点被称为可靠点，否则为不可靠点。 3.2 初始模板计算 利用已获取的可靠点，便可进行模板参数的计算。本算 法采用的是加权最小二乘法求模板参数，并进行多次迭代直 至参数收敛。显然，一个区域可靠点数越多，该区域计算所 ，若满 得的模板参数越可靠。设某个区域可靠点数为 足式(2)，该区域被定为可靠区域，否则为不可靠区域。本算 法只对可靠区域进行模板计算。 visible N (2) [ w d i i − ( a + bx i + cy i ) ]2 (3) ≥ visible N 模板的误差 定义为 N v ∆ f a b c ( , ) , N = ∆ = visible ∑ i = 1 f ∂ 当 = 0 ， f ∂ ∂ f = 0 ， ， 取得最小值，解得： ∆ = 0 i i i i i i i 2 ＝ ⎡ ⎢ ⎢ ⎢ ⎣ ⎤ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎣ a b c (4) ∑ ∑ ∑ dw i i xdw i ydw c ∂ ∑ yw i i ∑ yxw i i ∑ 2 yw i b ∂ ∑ xw i ∑ xw i i ∑ yxw i i ⎤ ⎥ ⎥ ⎥ ⎦ 式中 为第 i 个点的加权系数。 iw iw a ∂ ∑ w ⎡ i ⎢ ∑ xw ⎢ i ∑ yw ⎢ ⎣ i iw 第 1 次计算模板参数时，令 ＝1， 取各点的视差初 始值。以后每迭代一次， 、 都要更新一次。利用前一 次的模板参数可计算出各点模板视差，在模板视差附近一定 范围内重新选取匹配代价最小的视差作为新的 。加权二乘 id id ⎤ ⎥ ⎥ ⎥ ⎦ i i i i id —210— id 法的基本思想是若某点的 与模板视差的偏差越大，该点的 权系数应该越小，这里取： + (5) ， bx cy w = e − + d Kt ) − i i i i a ( 3.3 区域优化和模板优化 = t 区域分割后，很可能将原属于一个模板的区域分割成若 干个独立的区域，使得整个算法精度降低，运算量增大，因 此需要把这类区域进行融合。 设两个模板的参数分别为 [ ] ，若 ] ，[ a a b c c T T 1 1 1 b 2 2 2 满足式(6)，该两个模板被定为相似模板。 a 1 − a 2 + bW 1 ⋅ − b 2 + cH ⋅ − c 2 1 δ< d (6) 式中 W 、 H 分别为图像的宽度与高度， dδ 为视差的容错 范围。 将 3.2 节计算出来的初始模板依次放入模板集合，每次 都与集合内已存在的模板进行比对，如果集合中存在当前模 板的相似模板，则当前模板不放入模板集合。接下来，用模 板集合里的模板对各个不可靠区域进行初始分配(可靠区域 的模板定为该区域计算所得模板或其相似模板)。令： (7) C S P i , ( ) = ( ∑ x y , ) ∈ − S O ( c x y d , , ) , d S iP iP ( ) 为模板 对区 式中 为模板集合中的一个模板，C iPS ),x y 处计算所 域 的相似度匹配代价， 为模板 在点 ( iP 得的模板视差， ( ) ,x y 视差为 d 时的匹配代 c 价。区域内可能成为遮挡点的像素点将不进行计算。低纹理 区域的不可靠点主要是由于像素点间色彩接近造成的，而高 纹理区域的不可靠点往往就是遮挡点，因此本算法取高纹理 处的不可靠点作为可能遮挡点。 x y d 为点 ( , ) , 对于如何划分高低纹理区域，本算法采用了文献[3]中的 判断方法，令： 1 9 yxg ( = ) , i 式中 ( ∂ I ∂ x j ) 表示在 ) i ( , g x y < gT ，点 ( , gT ，当 ( , ) 于高纹理区域。 y 1 x 1 + −= ∑ ∑+ i ( , xj −= 1 y 1 ( ⎡ ⎢⎣ j ) ∂ ∂ I x ,() i j ) 2 ⎤ ⎥⎦ (8) 点处的水平梯度。预先设定阈值 x y 即属于低纹理区域，否则属 ) 对于每个不可靠区域，取模板集合中相似度匹配代价最 小的一个模板作为该区域的初始模板。如果相邻区域分配的 模板一致，则认为这些区域应属于同一个模板，因此把它们 合并为一个区域。合并后生成的新区域分为两种情况： (1)新区域的可靠点数满足式(2)，该区域被定为可靠区 域，按 3.2 节的方法计算其模板，若模板集合中不存在相似 模板，则加入模板集合。 (2)新区域的可靠点数不满足式(2)，该区域被定为不可靠 区域。 4 采用贪婪算法进行模板分配 s E data = + ∑ = 本算法采用基于全局的算法中常用的评价函数[3]： E = dataE E (9) EK smooth ( ) (10) i PSC , i ( (11) ∑ P ,( δ i i i SS , 为第 i 块区域分配的模板 后的相似度匹配 式中 ( C S 代价，第 i 块区域与第 块区域为相邻区域， L 为它们的 ( ) smooth L ) iP P ) ,i ≠ P j ) j j i j ( ),i j 

边界长度。当 P ≠ i P j 时， δ ( P i ≠ P j ) = 1 ，否则为 0。 n m mn 然而，通过对每个不可靠区域进行模板分配使得式(10) 中的 取得最小值是一个 NP 完全问题(NP-complete)。假设 E 有 个不可靠区域，模板集合中有 个模板，那么模板分配 共有 种组合方式，计算量很大。为此本算法采用了与文 献[5]类似的贪婪算法来求全局最优解。在求解过程中，每次 只改变不可靠区域 的模板，而同时其他区域模板均不作改 E iS 变，选取使 的最小值等价转化为求 最小值。 ( P δ) i E 最小时模板作区域 的模板。此时可将求 (12) PSC i iS iE ∑ ⋅ K P E L ) ≠ + = ( ) i ,( , s j j i i jS 式中各模板对所有不可靠区域的相似度匹配代价只需计算 1 次，并将结果存储起来，以后每次迭代时直接调用即可。而 Tao 算法采用前向转换(Forward Warping)来计算相似度匹配 代价，因此每次模板改变后都需要重新计算，运算量较大。 图像中所有不可靠区域都依次计算 1 遍视为迭代 1 次， 当某次迭代后所有区域的模板均无改变，则认为算法收敛， 停止迭代。 在算法过程中采用以下一些措施可以进一步提高算法实 时性：(1)每个不可靠区域只取相邻区域的模板中不同于当前 模板的进行计算。(2)若上次迭代中周围区域的模板都没有变 化，则本区域的模板在这次迭代中也不改变。 5 实验结果 本文采用误匹配像素百分比(Percentage of Bad Matching, C T ( d = − > ) ( ) ) ( B δ d Cd ( ( yx , 式中 PBM)对算法精度进行评判。 d (13) ) yx , yx , 计算所得视差， 1 ∑ N ( ) yx , x y , ) 为点 为该点 dδ 为视差容错范围。表 2 为算法中参数的选取 的真实视差， 情况，表 3 反映了不同算法的精度对比，表 4 反映了它们运 算时间对比。图 2 展示了本算法对 Venus 图和 Tsukuba 图的 运算效果。从中可以看出视差图边界清晰，定位准确，且低 纹理区域的视差也得到了很好的恢复。 表 2 算法参数选取 yx , d T ) ( Nv 500 K 2 Tg δd 1.0 4 表 3 各算法 PBM 值比较 图片 算法 Our method Pix-to-Pix[8] Dyn.prog[9] Graph cuts[4] Venus Sawtooth Tsukuba 0.77 6.30 10.10 1.79 2.05 2.31 4.84 1.30 2.48 5.12 4.12 1.94 表 4 各算法运算时间比较 Ks 20 Map 1.66 0.50 3.33 0.31 (384×288) Map(284×216) (434×383) Sawtooth(434×380) Tsukuba Venus 0.813 1.360 0.035 0.072 0.661 0.348 230 288 1.391 0.070 0.626 255 0.547 0.028 0.278 167 图片 算法 Our method Pix-to-Pix[8] Dyn.prog[9] Graph cuts[4] (a) (b) (c) (d) (e) (f) 图 2 算法对 Venus 图和 Tsukuba 图的运算效果 图 2(a)为 Venus 图的参考图，图 2(b)为 Venus 图的本算 法所得的视差图，图 2(c)为 Venus 图的真实视差图，图 2(d) 为 Tsukuba 图的参考图，图 2(e)为 Tsukuba 图的本算法所得 的视差图，图 2(f)为 Tsukuba 图的真实视差图。 6 结论 本文在 Tao 的平面模板假设基础上提出了一种基于图像 分割的快速立体匹配算法。实验表明，本算法克服了基于区 域算法中存在的边界模糊，低纹理区误匹配严重的缺点，同 时，又解决了传统的基于全局算法中计算量过大，实时性不 好的问题。因而，本算法能很好地满足在一些计算机视觉应 用场合的高精度高实时性要求。 参考文献 1 Ali M, Shah J R, Ahmed M. 3D Reconstruction and Model Acquisition in Real World Scenes Using Stereo Imagery[C]. the 7th International Multi Topic Conference, of Objects Proceedings of Islamabad, Pakistan, 2003: 32-37. 2 Nguyen H T, Minh N. Do Image-based Rendering with Depth Information Using the Propagation Algorithm[C]. Proceedings of Acoustics, Speech, and Signal Processing, Philadelphia, USA, 2005: 589-592. 3 Scharstein D, Szeliski R. A Taxonomy and Evaluation of Dense International Two-frame Stereo Correspondence Algorithms[J]. Journal of Computer Vision, 2002, 47(1): 7-42. 4 Kolmogorov V, Zabih R. Computing Visual Correspondence with Occlusions Using Graph Cuts[C]. Proceedings of the 8th International Conference on Computer Vision, Vancouver, Canada, 2001: 508-515. 5 Tao H, Sawhney H S, Kumar R. A Global Matching Framework for International Stereo Computation[C]. Proceedings of Conference on Computer Vision, Vancouver, Canada, 2001: 532-539. 6 Felzenszwalb P F, Huttenlocher D P. Efficient Graph-based Image Segmentation[J]. International Journal of Computer Vision, 2004, 59(2): 167-181. the 8th 7 Hirschmuller H. Improvements in Real-time Correlation-based Stereo Vision[C]. Proc. of IEEE Conf. on Computer Vision and Pattern Recognition, 2001: 141-148. 8 Birchield S, Tomasi C. A Pixel Dissimilarity Measure That is Insensitive to Image Sampling[J]. IEEE TPAMI, 1998, 20(4): 401-406. 9 Bobick A F, Intille S S. Large Occlusion Stereo[J]. International Journal of Computer Vision, 1999, 33(3): 181-200. —211—