基于区域增长的自适应窗口立体匹配算法
罗三定, 陈海波
(中南大学 信息科学与工程学院, 湖南 长沙, 410083)
摘要: 针对基于区域的立体匹配算法支持窗口难以选择的问题, 提出一种新的自适应窗口区域立体匹配算法。 该区域增长的方法可以动态地获得形状和大小均具有自适应特性的支持窗口, 并通过区域视差范围估计、 核心窗口视差近似、 动态搜索步距调整等方法使算法得到改进。 研究结果表明: 该算法对于视差不连续和遮挡区域都有着良好的适应性; 采用该算法获得的视差图像的准确度高达95%, 且计算时间缩短到5 s以内。
关键词: 立体匹配; 自适应窗口; 视差估计; 动态伸缩; 边界约束
中图分类号:TP391 文献标识码:A 文章编号: 1672-7207(2005)06-1042-06
Stereo matching algorithm of adaptive window based on region growing
LUO San-ding, CHEN Hai-bo
(School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: Aimed at the supported windows selected difficultly in stereo matching algorithm based on local areas, a new stereo matching algorithm of adaptive windows via region growing was proposed. This region growing method can offer appropriate shape and size of supported windows adaptively. In addition, this algorithm is improved by estimating the scope of disparity, approximating the disparity of the core window, adjusting the step dynamically. The results show that this algorithm has good adaptability in discontinuous and occlude areas. It can offer robust disparity estimation image using this algorithm. The precision of the algorithm is more than 95%, and its calculating time is less than 5 s.
Key words: stereo matching; adaptive window; disparity estimation; dynamic expanding and contracting; edge restriction
立体匹配问题是计算机视觉研究的热点问题之一。 目前, 已提出的获得高密视差图立体匹配算法大致可以分成基于全局的立体匹配算法和基于区域的立体匹配算法两类[1]。 由于图像中可能存在周期性重复特征、 噪声、 遮断效应、 光学畸变和投影畸变等因素的影响, 计算某一点的深度信息时, 往往要从其邻域获得支持。 对于基于区域的立体匹配算法, 如何确定支持邻域(窗口)是其中最为关键的问题。 然而, 在一幅图像中, 不同的像素点往往要求不同的支持窗口, 且窗口大小与形状必须具有较强的适应性。
为此, T.Kanade和M.Okutomi提出了自适应窗口模型[2], 利用灰度方差和视差方差信息计算视差置信度来调节窗口的大小。 但是由于计算过程复杂, 窗口的形状仅限于长方形窗口。 另外, 视差的初始估计对视差结果影响较大。
另一个广泛应用的算法是多窗口算法[3]。 对于每一个像素点, 计算有限的几个不同形状窗口, 性能最好的窗口被保留。 由于计算过程复杂, 用于计算的给定窗口个数有限(〈10), 且给定窗口形状和大小不能保证支持窗口具有好的适应性。
为保证支持窗口具有好的适应性, 作者提出一种基于区域增长的自适应窗口模型。 对于固定的视差d, 动态地增长每个像素点的支持窗口, 从而获得不同大小、 不同形状的支持窗口。 为了减少计算的复杂程度, 采用估计视差搜索范围、 核心窗口视差近似和动态调整搜索步距的几种技术方法。 采用筑波(Tsukuba)大学提供的图片进行检验。
1 窗口动态增长策略
为衡量视差匹配的有效性, 首先给出窗口代价函数, 然后根据该函数动态地进行窗口增长。
1.1 代价函数
设待处理的图像为L(x, y), R(x, y)。 不失一般性, 假定基线平行于x轴。 进一步假定L(x, y)和R(x, y)是同一物体同一光照条件的左、 右图像。 则定义匹配误差函数ed为:
ed=|L(x, y)-R(x-d, y)|(1)
其中: d 为视差值。
对于其他的误差匹配函数参见文献[4]。 窗口代价函数[5]给定如下:
其中: Sw为窗口大小, 也就是像素点的个数; α和β为比例系数; γ为小窗口抑制参数。
式(2)中的第1项是指在该窗口中的平均错误率。 显然, 如果对于给定视差d越接近真实视差, 则该项的值就越小。 用窗口的大小Sw进行正规化, 使得不同大小窗口的误差具有可比较性。
式(2)中的第2项是方差信息, 同样, 给定视差d越接近真实视差, 则该项的值就越小。 当窗口越大时, 第3项的值就越小。 这是因为大窗口包含的信息更多, 匹配的视差结果更准确, 在前面2项的值相同时, 更希望采用较大的窗口。 系数α, β和参数γ的值通过权衡三者关系通过实验给出。
1.2 动态窗口增长策略
对于考察点, 首先构造以该点为中心的最小支持窗口。 对固定视差d计算该窗口代价函数Cd。 然后, 开始动态窗口增长。
窗口的动态增长策略描述如下:
a. 以考察点为原点, 沿x轴分别向正方向和负方向增长窗口。 每加入一个像素点就重新计算窗口代价Cd, 一旦新得到窗口代价Cd′与前一个窗口代价Cd的差值大于给定的阈值或者窗口边界值大于给定的最大值, 则停止增长, 并且记录x轴的边界。
b. 采用步骤a.的策略动态增长y轴方向的点。
c. 对于每个给定的视差d都采用步骤a.和b.的方法计算动态窗口的代价函数Cd。 最后保留窗口代价函数值最小的动态窗口和对应的视差d。
其动态增长过程如图1所示。
图 1 窗口增长过程
Fig. 1 Process for window growing
采用以上的方法得到的支持窗口优点主要有: 首先, 获得到的窗口中尽可能地包含了具有相同视差的像素点; 其次, 对于无纹理区域使得窗口尽可能的大, 因此, 得到的窗口不再局限于简单的长方形, 而是自动生成的具有视差自适应的最佳区域; 最后, 该算法不需要对视差进行初始的估计, 从而避免了对初始视差估计的依赖性。
2 边界保持和遮挡检测
2.1 边界保持问题
在一般情况下, 物体的边界两侧视差变化比较大, 边界的一侧是前景物体, 另外一侧是背景。 如图2所示, 假定此时需要计算的视差中心点为O, 矩形检测点窗口W中浅灰色区域处在背景区域R1上, 视差为d1。 深灰色区域处在前景物体R2上, 视差为d2, 假设此时自适应窗口的视差取值为d2且已经增长到边界, 那么再加入R1中的点必然明显增加匹配误差, 使误差函数值超出给定的阈值。 而采用上面的算法, 自适应窗口将回退到边界区域, 从而保证视差窗口内视差的一致性, 也就保证了视差边界的正确性。
图 2 边界保持示意图
Fig. 2 Schematic diagram of preserving edge
2.2 遮挡检测问题
对于遮挡情况的处理一直都是立体匹配中的难点和主要问题。 在复杂场景中, 经常会存在没有匹配点的遮挡点。 然而, 大多数立体匹配算法都没有处理这种情况。 近年来, 一些学者利用顺序性约束[6-9]来检测遮挡问题, 并且取得较好的效果。 这里采用检测匹配函数的值大小和利用匹配惟一性约束来检测遮挡区域。
在一般情况下, 假设遮挡区域与误匹配区域在视差范围内不具备相似的光照函数值。 那么, 分如下2种情况, 如图3所示。
图 3 遮挡情况示意图
Fig. 3 Schematic diagram of occlusion area
a. 假如q不是被遮挡点, 必然有一个正确匹配点p′与之对应, 那么, 它们的误差函数c(q, p′)值必然小于误匹配点的c(q, p)。 也就是在本文算法中该种情况会被自动检测得知。
b. 假如q是遮挡点, 它将有可能与一个误匹配点p匹配, 那么根据假设它们的误差函数值c(q, p′)必然较大。
因此, 当全部视差计算完全之后, 假如误差函数值大于给定的阈值, 那么就把它标注为遮挡点。
3 算法优化和分析
以上提出的动态窗口的增长策略可以自动生成最佳窗口区域, 但采用逐步增长方式将使得计算复杂度很高。 该算法的时间复杂度为O(MNDI), 其中M和N分别为图像的高度和宽度, D为视差的搜索范围, I为窗口的平均增长步数。 所以, 应从分析算法的时间复杂度入手, 进一步研究改进策略, 提高算法的计算速度。
经分析, 算法的时间消耗主要集中在以下3个方面:
a. 所需搜索的视差范围。 如果事先可以确定所需搜索的视差范围, 那么, 将可以大幅度地减少视差搜索空间。
b. 匹配点数目。 图像越大其像素点个数越多, 逐点匹配必然造成巨大的计算量。 若能有效地减少匹配点个数, 则所需计算时间随之降低;
c. 窗口动态增长的方式。 由于窗口的生成采用的是逐点增长方式, 因此窗口的增长速度比较慢。 若能采用快速增长方式, 则将高效地提高计算速度。
3.1 视差搜索范围的估计
对于视差搜索范围的问题, 不再是在整幅图像上来搜索, 而是将图像分成R个子图像, 对每个子图像来估计视差范围, 从而减小视差的搜索范围。 算法的具体步骤描述如下:
a. 输入左右图像。
b. 将输入图像分割成R块子图像(P×Q)。
c. 采用蒙托卡洛随机实验的方法[10]估计每个小块的视差范围。
d. 计算各子块的视差范围。
获得准确的视差范围, 理论上希望使用尽量多的采样点。 由于在一定的小区域内视差是连续的, 所以可以采用简化的采样方法, 如图4所示。
图 4 简化的采样点
Fig. 4 Simple sampling
分别采用子图像中的左上, 右上, 中心, 左下, 右下的像素点, 采用提出的区域增长算法计算视差。 然后找出最大视差值和最小视差值, 作为该小区域的视差范围。 经过优化, 算法的时间复杂度将减少为:
其中: K为采样点个数, P、 Q分别为子图像的高度和宽度, Di为第i个子图像的视差搜索范围, I为平均窗口的像素增长步数。 实验表明, 经过对视差搜索范围估计后, 优化算法的时间复杂度大幅度降低了, 还能保证足够好的视差计算结果。
3.2 核心窗口的视差取值
并非对于图像每个像素点都要完全按以上步骤进行视差计算。 因为针对一个像素点计算视差时, 每当窗口增长时, 新加入的点都是和中心窗口具有相同视差估计期望的点, 所以可以同时更新窗口内期望估计概率大于给定值的像素点, 更新窗口中的其他点不必一一进行匹配计算。 给定点的视差估计的概率[11]:
其中: k为独立于视差的正规化因子; di, j为点i和点j之间的视差差值; w为支持窗口。
然而, 事实上, 期望估计的概率是很难求得的, 基于中心部位视差估计正确概率较大, 采用一次性更新核心窗口的方法来减少匹配计算的像素点数。 图像的核心窗口定义如下:
最小核心窗口即考察点的初始支持窗口(3×3)。 核心窗口是包含最小核心窗口的扩展区域, 扩展范围不超过给定值ε(如ε≤3), 且扩展部分像素点的加入不会增大窗口代价函数值。
每当生成一个考察点的窗口, 就用该考察点的最佳视差值作为对应核心窗口内的像素点的视差近似值。 从而减少匹配计算量。 算法的时间复杂度可以减少到:
其中: λ为核心窗口的像素平均值。
3.3 窗口增长改进策略
为提高窗口增长效率, 提出两种改进的动态增长策略。
3.3.1 动态伸缩策略
假设用考察点的视差来替代该邻域内点的视差准确率f(l)类似高斯分布, 其逆函数为g(τ)。
其中: σ为方差。
从考察点向外延伸, 希望探索到的点的期望视差准确率为τ0(0.5〈τ0〈1), 对应的延伸距离l1为g(τ0)。 同样的期望视差准确率τ0从l1处继续向外延伸, 因以l1为新参考点的准确率服从同样分布f(l), 于是相对原始参考点的分布为[f(l)] 2, 则新的探索距离增量应由[f(l)]2的逆函数求得, 即l2=g[(τ0)-2]。 如此类推, 在位置
进行第k+1次延伸时探索距离增量lk+1=g[(τ0)-k]。 由于g(τ)是随τ增大急剧下降的, 可见探索距离增量li是随i递减的。
为了计算简单起见, 可构造一个能充分反映距离增量递减规律的近似函数,
lk=τkl0, 0.5〈τ〈1。(7)
σ越大, 则曲线越平坦, 同样的期望准确率条件下探索步距就越大, 图像中物体越大, 探索步距就有理由更大些。 策略描述如下:
a. 构造考察点(x0, y0)的最小支持窗口, 并计算对应的代价函数值Cd。 给定τ, k=0和l0的初始值。
b. 在原窗口边界基础上延伸lk个像素点后, 再计算新的代价函数Cd′, 若满足代价函数值变化量小于给定阈值, 则代价函数值更新为Cd′, 新的窗口边界为延伸后的边界, k增1, 继续步骤b, 直到窗口边界大于给定值; 否则, 转步骤c。
c. 退回到k-1步时的窗口边界, 采用单像素逐步增长方式, 直到代价函数值变化量大于给定阈值。
d. 对窗口内所有y=y0的点, 用同样策略沿y轴方向进行动态增长。 最后生成自适应窗口。
与逐步增长方式相比, 试探的步数显著减少, 提高了窗口增长速度。 算法时间复杂度减少到:
其中: Ir为新的平均增长步数。
在考察点的支持窗口就是最小支持窗口的极端情况下, 该策略会增加8×(l0-4)次代价函数计算。 但由于这种情况发生的概率相当小, 通常支持窗口的大小都在25个像素点以上(见表1)。 当3〈l0≤6时, 该策略的计算时间总是显著减少。
表 1 平均窗口大小
Table 1 Average size of windows
由表1可知, 筑波(Tsukuba)大学的5幅立体匹配图片计算得到的平均支持窗口大小。
3.3.2 边缘约束策略
同一个物体表面的灰度在左右图像中是一致的, 窗口中新增加的点如果是同一个物体表面的像点, 用式(2)计算代价函数不会有明显变化, 那么就没必要对灰度差很小的点进行计算。
不同物体之间最有可能存在深度差异, 物体与物体之间往往具有明显的分界线。 因此, 图像中的边缘处是检测视差的重点, 可以利用边缘信息来提高窗口增长的速度。 策略描述如下:
a. 利用八方向检测算子获取图像的边缘信息且记录方向信息[12]。
b. 窗口增长一次性增长到最近边界处(不超过最大窗口边界), 横向增长到非水平边界, 纵向增长到非竖直边界。
c. 计算代价函数, 满足代价函数值变化量小于给定阈值则保留扩展窗口边界。 否则, 窗口扩展采用逐步增长策略。
那么算法时间复杂度可以减少到:
其中: 第1项为边缘检测消耗的时间; R为边缘检测掩模大小; Ir′为新的窗口平均增长步数。
4 实验结果
在Window2000平台上用VC6.0编制实验软件, 分别实现了本文提出的区域增长算法, 以及动态伸缩、 边界约束算法。 实验中取最大窗口为31× 31, 最小窗口为3×3。 由于在误差函数值相同的情况下, 才需比较窗口大小, 所以平均误差和方差构成了误差函数的主体。 故取α=1.2, β=1.0, γ=-2。 在动态伸缩算法为了要求第一次增长的步数一般在给定的点视差允许范围内, 同时增长的步数大于单步增长, 所以取τ=0.6, l0=5。 视差范围为0~16, 作为比较参考, 同时对文献[2]中提出自适应窗口和文献[3]提出的多窗口算法进行程序实现, 如图5所示。
从图5(f)中可以看出, 支持窗口的形状具有自适应的特点。 图5(g)~(j)提出的3个算法在边界区域获得的视差比图5(c)~(e)的算法更为准确。
对于视差图像的正确性, 这里采用文献[13]提出的错误检测方法来评价实验结果的准确程度。 定义视差错误率函数B[13]和正确度A:
式中: dc为计算得到的视差值, dt为真实视差图的视差值, δ为错误允许值, 这里取δ=1.0。
表 2 各方法视差正确度
Table 2 Accuracy of different algorithm
从表2可以看出, 本文提出的3种算法其视差的正确度都优于自适应窗口和多窗口算法。 动态伸缩的结果反而好于逐点增长算法的结果, 分析其原因可能是采用了视差采样而造成的局部视差一致的原因。
图 5 现有的各种算法和本文算法的视差结果图像
Fig. 5 Disparity results of existing algorithms and presented algorithms
与逐点区域增长算法相比, 采用动态伸缩算法和边缘约束算法的窗口增长策略明显提高了计算速度(见表3), 与自适应窗口和多窗口算法相比计算速度较快。
表 3 各方法实测计算时间
Table 3 Time consumption of different algorithm
5 结 论
a. 从自适应支持窗口选择入手,提出一种新的动态增长算法,解决了区域立体匹配视差计算中关于支持窗口自动生成的关键技术问题。由于这种算法可以动态调整窗口形态和大小,得到与立体图像对实际视差相适应的支持窗口,从而有效地克服了传统区域立体匹配算法中窗口不可调节而造成的视差估计精度不高的弱点。
b. 为了降低支持窗口自动生成算法的计算复杂度,进一步提出缩小视差搜索范围、核心窗口视差近似取值、动态调整窗口增长步距、利用边缘信息约束窗口增长等改进策略使该算法得以优化。试验结果表明,本文提出的算法和策略与传统方法对比,具有算法的视差计算精确度高、能大幅度降低时间复杂度等优点。特别适合于立体视觉实时性和视差准确性要求高的应用场合,如机器人双目视觉中用于探测周边环境获得前方纵深信息;在深海勘探集矿机中周边多幅立体视觉图像信息进行定位和测速。
c. 所提出的边界约束算法在指导窗口的增长综合了边缘与区域信息融合的优点,但它的不足之处在于较容易受噪声干扰,直接利用图像边缘检测结果,因边界断续较多,视差结果会出现毛刺。因此,要避免噪声干扰,需要良好的边缘算法或边缘检测结果进行断线自动连接处理。
参考文献:
[1]Anandan P. A computational framework and an algorithm for the measurement of visual motion[J]. International Journal of Computer Vision, 1989, 2(3): 283-310.
[2]Kanade T, Okutomi M. A stereo matching algorithm with an adaptive window: Theory and experiment[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 1994, 16(9): 920-932.
[3]Fusiello A, Roberto V. Efficient stereo with multiple windowing[A]. IEEE Conference on Computer Vision and Pattern Recognition[C]. San Juan, 1997: 858-863.
[4]Shimizu M, Okutomi M. Precise sub-pixel estimation on area-based matching[A]. 8th International Conference on Computer Vision[C]. Vancouver, 2001: 90-97.
[5]Veksler O. Fast variable window for stereo correspondence using integral images[A]. IEEE Computer Society Conference on Computer Vision and Pattern Recognition[C]. Madison, 2003: 556-561.
[6]Intille S, Bobick A. Disparity-space images and large occlusion stereo[A]. European Conference on ComputerVision[C]. Stockholm, 1994: 179-186.
[7]Belhumeur P N. A bayesian-approach to binocular stereopsis[J]. Computer Vision, 1996, 19(3): 237-260.
[8]Intille S, Bobick A. Incorporating intensity edges in the recovery of occlusion regions[A]. International Conference on Pattern Recognition[C]. Jerusalem, 1994: 674-677.
[9]Fua P. A parallel stereo algorithm that produces dense depth maps and preserves image features[J]. Machine Vision and Applications, 1993, 69(1): 35-49.
[10]SUN Chang-ming. Fast stereo matching using rectangular subregioning and 3D maximum-surface techniques[J]. International Journal of Computer Vision, 2002, 47(3): 99-117.
[11]Belhumeur P N. A bayesian-approach to binocular stereopsis[J]. International Journal of Compute Vision, 1996, 19(3): 237-260.
[12]罗三定, 沙莎, 沈德耀, 等. 棒材生产在线计数系统研究[J]. 小型微型计算机系统, 2004, 25(4): 671-675.
LUO San-ding, SHA Sha, SHEN De-yao, et al. On-line visual counting system for production of steel bar[J]. Mini- Micro Systems, 2004, 25(4): 671-675.
[13]Scharstein D, Szeliski R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J]. International Journal of Computer Vision, 2002, 47(1): 7-42.
收稿日期:2005-03-01
基金项目: 国际海底区域研究开发“十五”基金资助项目(DY-105-03-02-06)
作者简介: 罗三定(1955-), 男, 湖南浏阳人, 教授, 从事图像处理、 多媒体技术、 智能信息处理研究
论文联系人: 罗三定, 男, 教授; 电话: 0731-8830982(O); E-mail: sdluo@mail.csu.edu.cn
