2. 西北工业大学 计算机学院, 陕西 西安 710072
全局立体匹配是使用某个最优化方法或者迭代来计算视差。许多全局方法都是在能量最小化框架下构建, 因此在计算视差前需要构造一个能量函数。当能量函数定义好了之后, 许多算法能够用来搜寻能量最小值。比较传统且与正则化和马尔科夫随机场相关的方法有模拟退火、最高可信度优先和均值区域退火方法[1]。近来, Boykov等[2]提出的图割(graph cuts)方法能够解决一大类全局优化的问题, 与模拟退火算法相比, 这些算法效率更高, 匹配结果更好。另外循环置信传播(LBP, loopy belief propagation)也能够得到与之相配的结果[3]。而基于动态规划(DP, dynamic programming)的全局优化立体匹配方法[4]是一种与上述提到的全局方法不同的优化方法, 其能够分别在每一条扫描线上找到全局最小值, 是一个代价路径寻优的过程。郑志刚等[5]通过结合彩色图像分割和协同优化算法得到很好的结果。但图割立体匹配算法没有考虑图像结构, 针对其不足之处, 本文提出了基于区域一致性约束的图割立体匹配算法。
1 匹配代价的计算使用图割优化进行立体匹配, 首先要构造一个能量函数。在构造时一般有匹配代价约束和空间平滑约束2种, 基于此构造的能量函数如下如示
(1) |
式中, p表示图像中的像素点, P表示图像所有像素点集合, f:p→L(L表示离散的视差标号集), N(p)表示p的四邻域(即只考虑周围4个方向的连接)。匹配代价如(1)式所示。
由于灰度图像的动态范围是0~255之间的整数, 其区分能力很有限, 所以会出现很多歧义点, 就是一个像素点与多个像素点的相容度是一样的, 这样就会对匹配的结果造成影响。文章提出了基于区域一致性约束的图割立体匹配算法, 对于一个像素点如果能够整合周围像素的分布情况, 则在计算像素相似性测度的时候采用当前点兼顾其周围点分布情况来考虑的方法。像素本身的相似性测度采用如下方法:令参考图像中的一个像素点p(x, y)和一个视差f, 则对应的目标图像的点为p′=(x-f, y), 此时的相似性测度为Cnorm(p, f), 对于一个RGB图像来说I(p)表示p点彩色值, I′(p′)表示p′的彩色值, Cnorm(p, f)的计算如下所示
(2) |
式中, k表示某个彩色通道。这样表示明显优于直接使用灰度图像的亮度值得区分度。
为了兼顾当前像素点周围的像素分布, 文章利用了一个非参数变换Census变换, 在此需要的处理是将图像变换成灰度图像, 然后利用灰度图像值来计算匹配图像对的Census变换, 令Ce(p)和Ce′(p′)分别表示参考图像和目标图像经Census变换后对应点的值, Ccensus(p, f)表示相似测定, 形式如下所示
(3) |
令Cm表示匹配代价, 则对于点p视差为f的匹配代价为
(4) |
为了增加匹配的稳定性, 对奇异值能够抑制, 根据Scharstein和Szeliski的研究表明[6], 截断函数(truncated function)性质的匹配代价能够很好地满足上述稳健的匹配代价要求, 如图 1所示:
图中, λ表示截断函数的阈值, x表示拐点变量值, 当变量大于该值时, 输出的值在一个可控的范围内。因此, 在文中匹配代价的计算也引入λnorm和λcensus分别表示Cnorm(p, f)和 Ccensus(p, f)的截断阈值, 则此时匹配代价可以写为如下形式
(5) |
在视差匹配时, 根据自然图像的特点, 一般会建立一个视差图的模型, 由于空间区域一致性和色彩一致性, 视差的不连续一般都发生在色彩和空间不连续处。所谓的区域一致性, 就是同一目标物中视差是连续变化缓慢的。因此, 需要对匹配结果施加平滑约束, 这个平滑是指2个方向的平滑:源图像和视差图像的平滑, 分别用I和f表示。
平滑就要求与其空间相邻的像素点的关系是平缓变化的, 用N表示邻域, 像素的相邻表示为
(6) |
相互影响的邻域表示
(7) |
N1在这里表示的是四邻域连接, 像素p和p′为同一幅图像中的像素点, 有|p′x-px|+|p′y-py|=1, N2的定义类似。对于相邻像素点p和p′, 即|p′x-px|+|p′y-py|≤1, 则其相互影响的点为〈p, q, l〉和〈p′, q′, l′〉, 表示相邻的像素视差一致性, 对于N只要求相互影响点是在同一视差平面上的相邻点。
由上所述, 得到空间平滑函数
(8) |
在不需要考虑目标图像的情况下, 参考图像中的像素点亮度值所包含的信息已经能够影响视差的分布情况。对于2个相邻的p和p′像素如果已知I(p)≈I(p′)的情况下, 则可以推断2个像素的视差应该是相等的, 因此在需要用到图像中上下文内容的信息作为匹配平滑约束的条件, 结合参考图像像素信息值来定义u{p, p′}如下
(9) |
每一个u{p, p′}都表示了一个对于相邻的像素点p和p′分配不同像素点的惩罚值, 对于一对相邻点其差异越小, 分配不同的视差值时的惩罚应该越大, 也就是与|I(p)-I(p′)|成反比关系, 此处构建的函数如下
(10) |
(10)式就是一种Potts模型函数。其中, K是Potts模型参数。对(8)式引入区域一致性约束得到
(11) |
式中, Sp和Sp′分别表示分割后p和p′的区域标识, S表示图像分割后区域标识的集合, δ(Sp, Sp′)函数定义如下
(12) |
式中, δ是比例参数, 其取值范围为0, 1, 表示相邻像素的相关程度, 如果其值越大, 则说明相关性越大, 反之亦然。如果δ=1表示“一视同仁”, 此时平滑项就退化为无区域一致性约束的情况。
3 实验结果及其分析为了验证本算法的性能, 使用Middlebury匹配测试平台上的Tsukuba, Venus, Teddy和Cones 4个图像序列来完成算法验证工作, Tsukuba、Venus、Teddy和Cones图像编号分别为1、2、3和4, 这4组标准图像对都已经扫描线校正, 算法实现过程中使用到的参数如表 1所示, 在实验中得到4个图像对的实验结果视差图和错误视差图如图 2~图 5所示。
算法 | Tsukuba/% | Venus/% | Teddy/% | Cones/% | ||||||||
nonocc | all | disc | nonocc | all | disc | nonocc | all | disc | nonocc | all | disc | |
GCseg | 1.67 | 2.82 | 8.84 | 0.68 | 2.02 | 9.11 | 6.95 | 15.9 | 19.1 | 2.88 | 12.0 | 8.57 |
GC | 1.94 | 4.12 | 9.39 | 1.79 | 3.44 | 8.76 | 16.49 | 25.0 | 24.9 | 7.7 | 18.2 | 15.3 |
GCocc | 1.19 | 2.01 | 6.25 | 1.64 | 2.19 | 6.76 | 11.19 | 17.4 | 19.8 | 5.36 | 12.4 | 13.0 |
GCN | 1.27 | 1.99 | 6.48 | 2.78 | 3.13 | 3.59 | 12.0 | 17.6 | 22.0 | 4.89 | 11.8 | 12.1 |
为了验证本文算法跟同类算法的性能比较, 在实验时参数设置为λnorm=20, λcensus=25, δ=0.2, K=11。本文算法在表中用GCseg表示, GC表示文献[2]中算法, 引入了全局最小因子进行图割处理;GCocc表示文献[7]的算法, 针对遮挡视频进行了图割;CN表示文献[8]中算法, 能够减少遮挡的影响。其中, nonocc表示非遮挡区域, disc表示不连续区域,all表示平坦区域和半遮挡区域。从表格中可以看出, 增加了区域一致性约束的图割算法能够在性能上有很大提高。为了更形象地看出各个算法的性能, 把4种算法的误匹配率画成曲线进行比较, 如图 6所示。
4 结论文章中给出一种基于区域一致性的图割立体匹配方法, 与已有的几种基于图割方法进行了纵向比较, 发现算法能够相对优于其他3种算法, 从而验证了算法的有效性。
[1] | Geiger D and Girosi F. Parallel and Deterministic Algorithms for MRFs:Surface Reconstruction[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 1991, 13(5): 401–412. DOI:10.1109/34.134040 |
[2] | Boykov Y, Veksler O, Zabih R. Fast Approximate Energy Minimization via Graph Cuts[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2001, 23(11): 1222–1239. DOI:10.1109/34.969114 |
[3] | Sun J, Zheng N, Shum H. Stereo Matching Using Belief Propagation[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2003, 25(7): 787–800. DOI:10.1109/TPAMI.2003.1206509 |
[4] | Bobick Intille. Large Occlusion Stereo[J]. International Journal of Computer Vision, 1999, 33(3): 181–200. DOI:10.1023/A:1008150329890 |
[5] |
郑志刚, 汪增福.
基于区域间协同优化的立体匹配算法[J]. 自动化学报, 2009, 35 (5): 469–477.
Zheng Zhigang, Wang Zengfu. Stereo Matching Algorithm Based on Collaborative Optimization between Regions[J]. Automation Journal, 2009, 35(5): 469–477. (in Chinese) |
[6] | Scharstein Szeliski. A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms[J]. International Journal of Computer Vision, 2002, 47(1): 7–42. |
[7] | Kolmogorov Zabih. Computing Visual Correspondence with Occlusions Using Graph Cuts[C]//Proceedings of International Conference on Computer Vision, 2001 |
[8] | Kolmogorov Zabih. Multi-Camera Scene Reconstruction via Graph Cuts[C]//Proceedings of European Conference on Computer Vision, 2002 |
2. School of Computer Science, Northwestern Polytechnical University, Xi'an 710072, China