适用于DIBR的匹配误差校正算法*

张玲 邰国钦 刘然 谢辉 许小艳

(1.重庆大学 通信工程学院，重庆400044;2.重庆大学 计算机学院，重庆400044)

基于深度图像绘制(DIBR)技术是三维(3D)电视系统中的关键技术，引起了越来越多研究机构的关注［1-3］.传统的3D视频信号传输时需要传送左眼和右眼两路视频流，而基于DIBR技术的3D电视系统仅需要传输一路视频流及对应的深度信息，从而可以减少传输带宽［3-4］.DIBR技术利用参考图像及其对应的每个像素的深度信息来合成场景中虚拟视点视图(称为目标图像)，可以避免由传统视图生成方法所带来的三维空间变换的计算复杂性［3］.正因为如此，DIBR技术在3D电视立体图像对生成中得到了广泛应用.

然而，由于可见性变化、深度图像中深度值的不连续及计算的不精确等原因，由DIBR技术生成的目标图像中可能包含着两种伪像:空洞和匹配误差［5］.空洞是由于深度图像中深度值的不连续所引起的，而匹配误差则是不符合顺序匹配约束的像素点.伪像会严重降低立体图像对的质量，造成极不舒服的感觉，因此，如何去除伪像是DIBR技术中的一个重要问题.

研究者们已提出了很多处理立体匹配中空洞的方法［5-9］.刘占伟等［10-11］提出了采用预处理深度图像和图像融合相结合的方法，即生成两幅目标图像进行融合填充空洞.骆凯等［12］提出了基于图像修复的校正方法.然而，较少有人讨论DIBR系统中匹配误差的校正方法.文献［6］虽然提出对DIBR合成的视图进行匹配误差校正，但没有详细阐述校正方法，也未对如何处理空洞点等情况进行详细讨论.文中提出了一种适用于DIBR的匹配误差校正算法.该算法实现了匹配误差的检测与校正，并且与DIBR的三维图像变换过程无关，可以作为附加的匹配误差校正算法应用于DIBR的后处理过程中.

1 顺序匹配约束及其性质

1.1 顺序匹配约束

定义 参考图像中深度相似的物体表面上的像素点，在重投影到目标图像后，仍将保持其在参考图像中的相对顺序.

设Il为参考图像，Ir是通过DIBR技术由Il生成的目标图像.Ol、Or分别对应两幅图像的成像中心，tx表示基线长度.世界坐标系XwYwZw的中心与Ol重合.pr(xr，p，yr，p)，qr(xr，q，yr，q) 分别是目标图像Ir上的深度相似的任意两点，P(xw，yw，zw)、Q(x'w，y'w，z'w)分别为pr、qr投射到在空间中的对应点，其在参考图像Il上的映射点分别为pl(xl，p，yl，p)、ql(xl，q，yl，q)，对应的三维变换如图1所示.如果像素点水平坐标之间满足

则称像素点pr、qr满足顺序匹配约束.

图1 顺序匹配约束说明图Fig.1 Illustration of order matching constraint

1.2 顺序匹配约束性质

顺序匹配约束有许多优良的性质.利用这些性质，可以简化DIBR系统中的匹配误差校正过程.

性质1(顺序匹配约束传递性) 设ur，j(ur，j，v)是目标图像Ir第v行的非空洞点;ur，i(ur，i，v)是与ur，j的深度值相似且与ur，j最近的前一个非空洞点(ur，i＜ur，j)，并且ur，i与v行中前面具有相似深度值的任一非空洞点ur，x(ur，x，v) 都满足顺序匹配约束(ur，x＜ur，i).如果ur，j与ur，i满足顺序匹配约束，那么ur，j与ur，x也满足顺序匹配约束，即顺序匹配约束具有传递性.

性质2(顺序匹配约束存在性) 如图2所示，设ur，j(ur，j，v)是目标图像Ir第v行的非空洞点，它对应的视差值为d(ur，j，v)，ur，j(ur，j，v) 在参考图像Il中的对应匹配点为ul，j(ul，j，v);v行中ur，j前面的任意非空洞点ur，x(ur，x，v) 都满足约束(ur，x＜ur，j).现执行如下操作:

(1)寻找与ur，j深度值相似且最近的前一个非空洞点ur，i(ur，i≤ur，j)，ur，i在参考图像Il中的对应匹配点为ul，i(ul，i，v);

(2) 检测ur，i与ur，j是否满足约束，如果满足则停止;否则将ur，j的匹配点修正为ul，i，视差值修正为d(ur，j，v)=ur，j－ul，i，转至步骤(1).

图2 顺序匹配约束存在性说明Fig.2 Illustration of the existence of order matching constraint

则有限次重复上述步骤之后，必存在某个非空洞点ur，y，使得ur，y与ur，j满足约束.顺序匹配约束的这一性质称之为顺序匹配约束存在性.

证明 如图2所示，设d1，d2，…，dn为所有可能的视差值，则ur，j当前的视差值为

设ur，i(ur，i，v)是与ur，j深度值相似且最近的前一个非空洞点，并且它们不满足约束，即

则经过步骤(2)后，ur，j的匹配点会被修正为ul，i，视差值修正为d'(ur，j，v)=ur，j－ul，i.

假设ur，x(ur，x，v)是与ur，j深度值相似且最近的前一个非空洞点，它与ur，j不满足约束且ur，x(ur，x，v)的匹配点ul，x(ul，x，v)恰好为ul，j(ul，j，v)，则有但这与式(2) 中ul，i＞ul，j矛盾，因此如果ur，x与ur，j不满足约束，ur，x的匹配点一定大于ul，j，从而ur，j的匹配点不可能被修正为前面循环时的匹配点，因此步骤(1)和(2)不会产生在两个匹配点之间反复修正的情况，从而每次修正，ur，j的视差值都不相同.

假设重复步骤(1)和(2)n－1次之后，还没有找到与ur，j满足约束的一个非空洞点，设此时ur，j的视差值为d″(ur，j，v).由于已经重复了n－1，根据每次修正ur，j的视差值都不相同的结论，此时ur，j的视差值已经取遍了所有可能的n个视差值.当再重复步骤(1)时，会找到一个与ur，j的视差值d″(ur，j，v)相等且最近的前一个非空洞点ur，y(ur，y，v)，如果ur，y与ur，j仍不满足约束，则执行步骤(2) 时一定会将d″(ur，j，v)修正到某个前面已经出现过的视差值，这是因为只有n个不同的视差值.这样就会与每次修正ur，j的视差值都不相同的结论矛盾，因此ur，y与ur，j满足约束.证毕.

2 零交叉校正算法

2.1 算法说明

文中提出的零交叉(Zero-Cross Correction，ZCC)算法侧重于校正前景中一个整体的对象中夹杂着一些背景像素的匹配误差，其基本思想是:通过遍历一行的像素点，找出连续不满足约束的点所构成的区域(匹配误差区域)，然后对于像素点小于等于5的匹配误差区域，将区域内所有点的匹配点都赋值成起始点的匹配点.在一行中，匹配误差区域一般不会以连续超过5个像素点的形式出现.如果出现连续5个像素都不满足约束的情形，则认为当前像素处于前景和背景的边界，不做校正.这种赋值方法是一种安全保守的方法.由于所有点的匹配点都相同，根据顺序匹配约束的传递性，这些点显然相互之间都满足约束.

2.2 算法描述

文中提出的零交叉校正算法完成目标图像(右视图)的匹配误差检测与校正功能，其中目标图像是通过DIBR技术由一幅参考图像(左视图)及其深度图像生成的.

输入:参考图像Il，目标图像Ir(含有空洞)及其视差图d，它们的分辨率都是Wi×Hi;

输出:校正后的目标图像I'r及视差图d';

算法描述:

(1)如图3所示，设us指示匹配误差区域的起点，ue指示匹配误差区域的终点.按行从左至右遍历目标图像Ir第v行中的点ur，j(ur，j，v).如果ur，j是空洞点，则读取下一点，直到ur，j是非空洞点;

(2)读取ur，j的下一点ur，j+1.若ur，j+1是空洞点，则将ur，j标识为匹配误差区域的终点ue，转步骤(3);否则，检测ur，j和ur，j+1是否满足约束.设ur，j和ur，j+1在参考图像Il中的对应匹配点分别为ul，j(ul，j，v) 、ul，j+1(ul，j+1，v) ，则

其中d(·)表示视差图d中相应点的视差值;如果ur，j和ur，j+1不满足顺序匹配约束

则将点ur，j标识为匹配误差区域的起点us;从点ur，j下一个点继续重复上述检测，直到检测到像素点ur，j+m+1匹配点的坐标不小于ul，j或ur，j+m+1为空洞点为止，将ur，j+m作为匹配误差区域的终点ue，转步骤(3);否则将搜索起点更新为ur，j+1，重复步骤(2);

(3)匹配误差校正.如图4所示，设ur，j是匹配误差区域的起点us，ur，j+m是终点ue，如果m≤5，则将匹配误差区域的所有点的匹配点ur，i修正为ul，j，视差值修正为d(ur，i，v)=ur，i－ul，j(ur，j＜ui≤ur，j+m)，将ur，j+m标识为新搜索起点，转步骤(1);否则，将ur，j+m+1标识为新搜索起点，转步骤(1);

图3 匹配点计算Fig.3 Calculation of matching points

图4 匹配误差校正Fig.4 Correction of matching error

(4)如果处理完一行内所有点，则转到下一行，转步骤(1);否则直接转步骤(1).

(5)如果处理完目标图像Ir内所有行，则停止，否则转步骤(4).

3 实验

文中采用“Ballet”序列及其相应定标参数进行误差校正实验.“Ballet”序列的摄制方法参见文献［7］.图5描述了匹配误差对目标图像的影响，其中图5(a)为基线长度为30 cm时DIBR技术生成的目标图像，记为Ir;图5(b)是对图5(a)的部分放大，突出了目标图像中存在的匹配误差.由图5(b)可以看出，图像中含有许多匹配误差(白色斑点，黑色区域表示空洞，可以通过空洞填充算法来消除)，严重降低了图像的质量.

图5 匹配误差对目标图像的影响Fig.5 Influence of matching error on destination image

针对该实例，零交叉校正算法的校正流程如下:

(1)从每一行第一个像素点开始，执行零交叉校正算法的步骤(1)和(2)，由视差图求得各像素点ur，j的对应匹配点ul，j，通过分析目标图像像素点和参考图像匹配点之间的映射关系，找出不满足顺序匹配约束的像素点，标记为交叉区域的起点us.

(2)从该起点继续检测，直到某像素点对应匹配点的横坐标大于ul，j，将该像素点前一个非空洞像素点定义为交叉区域的终点，标记为ue.

(3)执行零交叉校正算法步骤(3)来进行误差校正.如果匹配误差区域内像素点的个数小于5，则将区域内像素点的视差值修正为d(ur，i，v)=ur，i－ul，j，同时，将参考图像ul，j处的像素值复制到区域内的每个像素点处，完成对该交叉区域的校正.

图6是校正后的“Ballet”虚拟视图，比较图5(b)和6(b)可以看出，该算法可以有效地去除目标图像中的匹配误差，提高目标图像的整体质量.

图6 文中算法的校正结果Fig.6 Correction result of the proposed algorithm

4 结语

文中提出了一种适用于DIBR系统的匹配误差检测与校正算法——零交叉校正算法.该算法的特点是:在顺序匹配约束的基础上，将匹配误差区域内所有点的匹配点都赋值成起始点的匹配点，从而达到匹配误差校正的目的.将该算法应用于实例中，校正由DIBR产生的目标图像中的匹配误差.结果表明，文中算法可以有效地消除匹配误差，提高图像的质量.但是，该算法的时间复杂度较高，笔者将针对此问题进行下一步的研究.

［1］Fehn C.Depth-image-based rendering(DIBR)，compression and transmission for a new approach on 3D-TV［C］∥Stereoscopic Displays and Virtual Reality Systems XI.San Jose:SPIE，2004:93-104.

［2］Fehn C.A 3DTV approach using depth-image-based rendering(DIBR) ［C］∥Proceedings of the Visualization，Imaging，and Image Processing.San Francisco:PCS-Tektronix，Inc，2003:482-487.

［3］Zhang Liang，Tam Wa James.Stereoscopic image generation based on depth images for 3D TV ［J］.IEEE Transactions on Broadcasting，2005，51(2):191-199.

［4］刘然，巫英坚，许小艳，等.一种用于DIBR的去隔行算法［J］.计算机应用研究，2011，15(4):63-65，79.Liu Ran，Wu Ying-jian，Xu Xiao-yan，et al.De-interlacing algorithm for DIBR ［J］.Application Research of Computers，2011，15(4):63-65，79.

［5］贾波，章毓晋，林行刚.视差图误差检测与校正的通用快速算法［J］.清华大学学报:自然科学版，2000，40(1):28-31.Jia Bo，Zhang Yu-jin，Lin Xing-gang.General and fast algorithm for disparity error detection and correction［J］.Journal of Tsinghua University:Science and Technology，2000，40(1):28-31.

［6］戴琼海，徐秀兵.一种基于深度图的快速图像绘制方法:中国，CN101271583［P］.2008-09-24.

［7］Mohan R，Medioni G.Stereo error detection，correction，and evaluation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1989，11(2):113-120.

［8］Zitnick C L，Kang S B，Uyttendaele M，et al.High-quality video view interpolation using a layered representation［C］∥ACM Siggraph and ACM Transactions on Graphics.Los Angeles:Association for Computing Machinery，2004:600-608.

［9］Lee Pei-jun，Effendi.Adaptive edge-oriented depth image smoothing approach for depth image based rendering［C］∥IEEE International Symposium on Broadband Multimedia Systems and Broadcasting 2010.Shanghai:IEEE Computer Society，2010:1-5.

［10］刘占伟，安平，刘苏醒.基于DIBR和图像融合的任意视点绘制［J］.中国图象图形学报，2007，12(10):371-376.Liu Zhan-wei，An Ping，Liu Su-xing.Arbitrary view rendering based on DIBR and image mergence［J］.Journal of Image and Graphics，2007，12(10):371-376.

［11］Liu Zhan-wei，An Ping，Liu Su-xing，et al.Arbitrary view generation based on DIBR［C］∥Proceedings of the International Symposium on Intelligent Signal Processing and Communication Systems.Xiamen:Institute of Electrical and Electronics Engineers Inc，2007:168-171.

［12］骆凯，李东晓，冯雅美，等.基于DIBR和图像修复的任意视点绘制 ［J］.中国图象图形学报，2010，15(3):443-449.Luo Kai，Li Dong-xiao，Feng Ya-mei，et al.Arbitrary view generation based on DIBR and depth-aided image inpainting［J］.Journal of Image and Graphics，2010，15(3):443-449.