三维视频中深度信息估计算法

2011-06-12 06:08王龙海

武汉工程大学学报 2011年9期

程浩,王龙海

(武汉工程大学电气信息学院,湖北武汉 430205)

0 引言

立体视频因具有使用户能体验立体视觉感知的特点,在通信、电视、医疗、监控、教育、军事和国防等领域受到重视,许多学者和科研机构也展开了对立体视频系统及其相关技术细致的探讨和研究[1-4].通过对立体视频采集、编码、传输、立体视图描述生成、显示等方面的研究,已研究出了双目立体视频(stereo video)、多视点视频(multi-view video)、单视点视频+深度(single video plus depth)、多视点视频+深度(multi-view deo plus depth)[5]等立体视频方案.其中“多视点视频+深度”技术方案具有视频数据处理量小,能自由选择观看视点,终端重构的图像质量高等优点,受到业界的广泛关注,显示出巨大的应用前景.该方案是利用在多个稀疏视点位置用摄像机拍摄得到的多个视点的视频和与之对应的深度图像序列来表示三维场景信息[37],其关键技术是如何估计深度信息的.本文将分析目前各种深度信息提取方法的优点和不足之处,并对需要进一步研究和解决的问题进行讨论.

1 深度信息提取

对深度信息的估计目前主流的方法是:一种是利用人眼视差原理的立体匹配(stereo matching)算法估计深度信息,另一种是利用深度摄像机硬件设备获取深度图.从实用性来看,立体匹配算法估计深度才是我们研究的重点.

1.1 硬件设备提取深度信息

硬件设备估计深度信息是采用一种被称为“Zcam”[6]的深度摄像机的欧洲ATTEST系统框架,它是直接通过硬件设备获取深度信息图.这种硬件系统构架由:普通RGB摄像机、物体深度感光片(DCam Sensor)、光源前端三个部分组成.利用硬件设备获取深度信息的原理如下:首先通过光源前端发射的红外光线,红外光线在遇到物体后反射,在接收端接收,接着通过计算红外光往返路程的时间来确定物体深度,最后将这种物体深度与时间的关系映射到物体深度感光片上成像,最终得到深度信息图.这种直接通过硬件设备获取深度信息图的方法缺陷明显:因为光源前端精度是有限的,所以在物体深度过大(物体与成像设备较远时,红外线反射时间会很长)、深度过小(物体与成像设备较近时,红外线反射时间会很短)和有漫反射(反射光线不能被接收器接收)时,得到深度信息的质量并不高,或者根本无法获得深度信息.

1.2 软件算法获取视差信息

软件算法先是通过计算出两幅图像的视差,然后通过视差与深度的关系转换得到深度信息.视差与深度关系如图1所示.图中Ol、Or分别为左右摄像机的光心,f为摄像机的焦距,Z为物体的深度,B为基线.

xl、xr为X点在左右视图中成像的位置.根据相似三角形公式可得出

(1)

变换得

(2)

像素的深度与视差d成反比,与摄像机的焦距f、基线宽度T成正比,因此,只要我们通过适当的算法得出视差d,再根据摄像机的配置及参数,就可得出像素的深度信息.近年来,这些问题已经成为了重要的研究内容,并且取得相当进展,而且出现了许多经典的算法.

图1 视差与深度关系图

根据匹配生成视差图,分为稀疏视差匹配算法和稠密的视差匹配算法[7].三维视频系统要求的深度图必须是稠密深度图,才能合成出准确的虚拟视点,所以获取稠密深度图才是研究的重点.获取稠密深度图有基于区域(local-based algorithms)和基于全局(global-based algorithms)两种算法.

1.2.1 局部算法局部算法主要是采用局部优化方法进行视差值估计,局部立体匹配算法主要有SAD[8],SSD[8],NCC[9]等算法.SAD算法的思想如下.

先构造一个小窗口,然后用窗口覆盖左图像,选择出窗口区域内的所有像素点,再同样用这个窗口覆盖右图像并选择出覆盖区域的像素点,接着将左边覆盖区域减去右边覆盖区域,并求出所有像素点差的绝对值的和,移动右边图像的窗口,重复前二个的动作,求出这个范围内SAD值最小的窗口,即找到了左边图像的最佳匹配的像素块.

I2(x+i,y+j+d)|

(3)

基于SAD算法的思想,出现了SSD算法,它用两图像像素点平方和求视差.

I2(x+i,y+j+d)]2

(4)

NCC算法是在SSD算法的基础上发展而来:

(5)

其中:

(6)

(7)

随着局部匹配算法研究的深入,Yong Seok Heo等人[9]将颜色不变信息(Color-Invariantion Formation)[21-23]这个概念引入到NCC算法中,并采用了自适应NCC算法,很好解决了反射变化的问题.颜色不变信息和自适应NCC公式:

(8)

(9)

Nils Einecke和Julian Eggert[17]采用总结归一交叉相关(the summed normalized cross-correlation (SNCC)):

(10)

其设计思想是:分两个阶段完成获取视差:首先以3×3或5×5的窗口进行NCC处理,然而对相关NCC结果进行聚集.它通过选择一个自适应形状区域(Shape-Adaptive regions)克服了深度信息的模糊和不连续问题,并且采用了正交积分图像技术提高了NCC算法的效率.

1.2.2 全局算法全局算法主要是采用了全局的优化理论方法估计视差,建立全局能量函数,通过最小化全局能量函数得到最优视差值.主要的算法有图割(GraphCut:GC)[10]、动态规划(Dynamic Programming:DP)[11]、信念传播(Belief Propagation:BP)[12-14]等算法.全局立体匹配算法是通过能量最小化方法进行视差估计,在其建立的能量函数中,除了数据项之外,还有平滑项或者遮挡处理项.数据项主要是测量像素之间的相似性问题,而平滑项(遮挡处理项)则是描绘平滑像素之间的视差关系,保证相邻像素之间视差的平滑性.

动态规划(DP)算法是沿两条对极线上的点集的全局最优匹配搜索,使最终匹配在各点的相似性与相容性达到总体最优.给定一对校准后的左右图像,代价函数(Data Cost)通过比较像素灰度值的差异来度量某一行的像素间的相似性,对像素p(x,y),代价函数为

Dx(Δ)=|I1(x,y)-I2(x,y)| 1≤x≤M

(11)

令f(x)为对应于图像(x,y)处的视差,则能量函数(energy function)为

(12)

文献[26]提出基于图像分割的算法,利用图像分割域内像素视差的约束关系,得到更多的GCP点域,将分割域信息加入到DP算法里的能量项约束中,在一定程度上克服了传统基于DP立体匹配算法对行间约束的不足.文献[27]提出了一种以区域为处理单元的动态规划算法,该算法是利用基于区域的匹配算法处理稀疏纹理的能力强、动态规划匹配算法视差计算效率高的特点,克服遮挡处理不足的弱点.Shi Wanli和Wang Hongyong[28]提出算法是利用成对序列对准算法(pair-wise sequence alignment algorithm)完成稠密视差的获取.Ming Zhao等人[29]提出的DP改进算法是利用一种自适应权重窗口方法.

w(p,q)=exp[-(Δcpq/γq)+Δgpq/γp]

(13)

进行代价函数的计算,这种算法可以满足克服全局算法实时性不好的缺点.

Jun Xiao等人[30]采用了图像分割的思想,将参考图像分割,进行匹配,提高了匹配速度.

置信传播算法(BP)算法是在立体匹配中应用了最大积BP算法求取图像MRF中能量函数最小化问题.一般MRF的能量为

(14)

式(14)中Dp(fp)表示将编号fp赋给p的代价,V(fp-fq)表示将编号fp和fq同时赋给两个邻居节点p和q的代价.P是马尔可夫随机场中全部的节点,N表示邻居,如图2所示.

图2 标示p到q的迭代

4邻域图中箭头表示消息q到p的传递,8邻域图中像素q包含了其相邻区域消息p的集合传递.在BP算法中Max-Product的方法节点之间传送的消息的公式为.

(15)

其中m即为传递的消息,t是迭代的次数,l为像素q的一个可能编号,h为像素p的一个可能编号.在经过消息传播t遍后,就可以计算每个节点p的信任向量了,计算公式如下.

(16)

文献[15]讨论了图像中不同几何面对视差限制的BP算法,考虑到相邻像素在不在同一分割面这个问题,对能量函数中平滑函数细化,确定了不同情况下的最小化能量函数.相邻像素不在同一分割面时平滑函数.

V(dp,dq)=|dp-dq-aq(uq-up)-b(vq-vp)|*

(17)

相邻像素在同一分割面时平滑函数:

V(dp,dq)=|dp-dq-aq(uq-up)-b(vq-vp)|

(18)

Quanquan Gu和Jie Zhou[16]利用了黎曼几何标准中的结构张量优化BP算法并使其得到最优的能量函数.改进的BP算法如下:

(19)

Intae Na Junghun和Choi Hong Jeong[18]先是将NCC算法与BP算法相结合,在数据函数中引用NCC算法:

D(dp)=min(Cd(1-|NCC|),Kd)

(20)

得到一种快速的BP算法,实现既克服了光照不连续带来的匹配误差,又能满足实时性的高效匹配要求.Chia-Kai Liang等人[31]采用分层减少视差搜索的范围的思想,减少BP算法消息传递的次数,达到减小计算的复杂度,提高匹配速度的目的,并且不会消耗大量的内存.Narendra Ahuja等人[32]在他的文章中提出了tile-based belief propagation和快速建立消息算法两种技术.第一种技术是为了减少内存和带宽的消耗;第二种技术是为了减少消息的迭代计算量.Yen-Chieh Lai等人[33]提出了一种有效的消息传递作:

Mcon(lq)=Mprc(n)+λ*min(|l(n)-lq|,Ts)

(21)

实现减少内存和带宽的消耗.文献[34]考虑到信念传播的分层性和遮挡处理问题,提出了一种新的新秩序的信息传递代替信息的扫描传递,此方法解决了病态问题，提高了弱纹理区的匹配效率.

图割(GC)算法是将图像中空间相邻、像素值相近的点聚类的过程.通过对图像分割,可去除图像中不必要的细节信息而保留主要信息.图割算法的思路为:把图像中的像素点视为构造图中的节点,而像素之间的关系视为构造图的边,根据这些节点和像素之间的关系,构建能量函数,求取能力函数的最小值,即构造图的最小割,这样就可以获取最终的深度信息.能量函数的一般数学表达式可以用数据约束和平滑约束表示.匹配的能量函数可构造如下:

(22)

文献[19]在基于GC算法的基础上,针对稀疏特征匹配结果,提出采用三角剖分的算法,对原始图像进行区域划分,每个区内的视差搜索范围由三角形的三个顶点视差控制.能够进一步提高弱纹理区域的匹配准确率.Limin Shi等人[25]才用权重自适应窗口方法得到稳定的代价函数(权重函数如下),然后优化能量函数,使其能最小.

(23)

文献[35]先利用公式:

(24)

求取彩色图像分割区域的平面模板参数,以减少遮挡区域和低纹理区域对计算带来的误差.然后构造一个全局能量函数,把初视差范围作为全局能函数的一个参考项,缩小视差搜索范围,减少计算量,提高效率.Ayman Zureiki等人[36]只选取一些潜在范围内的像素点求取视差的局部匹配算法得出的像素差作为限制项:

V{p,q}(fp,fq)=u{p,q}|fp-fq|

(25)

去除大量不相关节点和边缘,减少计算量,缩短匹配时间.

Lei Yu等人[38]将Kernel Density Estimation(KDE):

(26)

和GC算法结合得到的代价函数为

Edata=-KDE(fp)=

(27)

求取视差.

2 总结与展望

深度估计技术是计算机视觉中的基本问题,又是难点问题;它是MVD方案的首要阶段,是自由视点视频系统中虚拟视点合成的重要课题.为此学者和科研究机构做出了长期的努力,发表了大量文献,提出许多深度估计的有效方法以及对深度信息估计的评价方法.

从实用性上来看,利用深度摄像机获取深度不太现实,因为要在每个摄像机中架上这样的一个深度摄像机,不仅需要大量的资金,而且这种大型设备要占据相当的空间,而且比较笨重,并不适合商用,所以该系统一直只用于实验室中求取单试点深度,并未得到商业的广泛推广.

局部算法求取视差的优点是效率高,速度比较快,能满足实时性要求,占内存少.但是其获取的视差准确度不高,噪声较敏感,对无纹理区域、视差不连续区域和遮挡区域匹配效果不理想.这是因为此类算法都是基于一个共同的假设,既对应的像素有类似的颜色值,所以实际获取的深度图像会有辐射变化(radiometric change);虽然NCC算法能克服一定的辐射变化,但是该算法获取的深度信息的模糊和不连续.

全局匹配算法比起局部匹配算法匹配精度就高很多,但是它有两大缺点.第一，它的算法复杂而巨大,实时性不好;第二,目前先进的全局匹配算法没有考虑到光照不连续问题.所以未来的工作需要考虑如何抑制不同视点在不同光照下对深度估计影响,可以考虑深度估计算法的优化,使深度估计不受光线等外部环境的影响.

许多匹配算法能很好的估计出深度信息来,深度图的客观质量能满足实际需求,但是在自由视点视频中,不仅对深度信息的质量要求很高,而且对深度估计的计算速度也有很高的要求,所以在未来研究中一方面可以从遮挡问题、弱纹理问题、视差不连续[20]等匹配问题进行研究改进;更重要的是如何利用算法更好更快的实时估计深度,以满足自由视点视频的应用.

参考文献：

[1] Sang-Beom Lee，Yo-Sung Ho. View-Consistent Multi-View Depth Estimation for Three-Dimensional Viedo Generation[C].The True Vision - Capture, Transmission and Display of 3D Video, 2010：340-344.

[2] Feldmann N, Atzpadin O,Schreer J,et al. Multi-View Depth Estimation Based on Visual-Hull enhanced Hybrid R ecursive Matching for 3D Video Conference Systems[C].In IEEE Internomational Conference on Image Processing, 2009：745-749.

[3] Yannick Morvan, Dirk Farin,Peter H.N. et al. System Architecture for Free-Viewpoint Video and 3D-TV[C].In IEEE Transactions on Consumer Electronics,2008：925-932

[4] 杨海涛,常义林,霍俊彦，等.应用于多视点视频编码的基于深度特征的图像区域分割与区域视差估计[J].光学学报,2008,28(6):1073-1078.

[5] Cheng Chia-Ming,su Xiao-an Lai Shang-Hong. A Novel Structure-from-Motion Strategy for Refining Depth Map Estimation and Multi-View Synthesis in 3DTV[C]. In IEEE International Conference on Multimedia and Expo,2010：944-949.

[6] Kuk-Jin Yoon, In-So Kweon.Support aggregation via non-linear diffusion with disparity-dependent support-weight for stereo matching[C].In Assian conference on computer vision, 2009：1000-1003.

[7] Wang Zeng-Fu, Zheng Zhi-Gang. A Region Based Stereo Matching Algorithm Using Cooperative Optimization[C].Computer Vision and Pattern Recognition, 2008,287-291.

[8] Hirschmüller H, Scharstein D. Evaluation of cost functions for stereo matching[C]. Computer Vision and Pattern Recognition, 2007:1-8.

[9] Yong Seok Heo, Kyoung Mu Lee, Sang Uk Lee. Robust Stereo Matching Using Adaptive Normalized Cross-Correlation[C]. Pattern Analysis and Machine Intelligence, 2010:807-821.

[10] Pedro F. Felzenszwalb， Ramin Zabih. Dynamic Programming and Graph Cut Algorithms in Computer Vision[J]. Transactions on Pattern Analysis and Machine Intelligence,2011(4):721-740.

[11] Deng Y， Lin X. A fast line segment based dense stereo algorithm using tree dynamic programming[J]. Lecture Notes in Computer Science, 2006(3):201-212.

[12] Kuk-Jin Yoon, In-So Kweon.Support aggregation via non-linear diffusion with disparity-dependent support-weight for stereo matching[C].In Assian conference on computer vision,2009:1000-1003.

[13] Yang Q, Wang L, Yang R, et al.Stereo matching with color-weighted correlation, hierarchical belief propagation, and occlusion handling[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008(31):492-504.

[14] Banno A, Ikeuchi K. Disparity map refinement and 3d surface smoothing via directed anisotropic diffusion[J]. in 3-D Digital Imaging and Modeling, 2009:1870-1877.

[15] Wang Fu-zhi, Huang Da-gui, Ge Sen.Belief Propagation Stereo Matching Based on Differential Geometry Constraint of Disparity[C].Digital Manufacturing and automation, 2010:324-327.

[16] Gu Quanquan, Zhou Jie.Belief Propagation on Riemannian Manifold for Stereo Matching[C]. In IEEE Internomational Conference on Image Processing,2009:1788-1791.

[17] Nils Einecke,Julian Eggert.A Two-Stage Correlation Method for Stereoscopic Depth Estimation[J].Transactions on Pattern Analysis and Machine Intelligence, 2010:277-234.

[18] Intae Na, Junghun Choi, Hong Jeong. Robust Fast Belief Propagation for Real-time Stereo Matching[C].In Advanced Communication Technology, 2009,11th International Conference, 2009:1175-1178.

[19] Gao Hongwei, Chen Liang， Liu Xiaoyang，et al. Research of an Improved Dense Matching Algorithm Based on Graph Cuts[C].In World Congress on Intelligent Control and Automation, 2010:6053-6057.

[20] Yuan Hui, Chang Yilin, Lu Zhaoyang，et al.Improved Depth Estimation Algorithm for Preserving Depth Edge and Temporal Consistency[C].In IEEE Conference on Industrial Electronics and Applicationsis,2010:1671-1676.

[21] Funt B, Ciurea F, McCann J.“Retinex in Matlab,” Proc. Eighth Color Imaging Conf[C]. Color Science Systems and Applications,2000:1233-1238.

[22] Kimmel R., Elad M., Shaked，D. et al. A Variational Framework for Retinex[J]. Int’l J. Computer Vision,2003, 52(1):7-23.

[23] Finlayson G D, Hordley S D, Hubel P M. Color by Correlation: A Simple, Unifying Framework for Color Constancy[J]. IEEE Trans. Pattern Analysis and Machine Intelligence,2001, 23(11):1209-1221.

[24] Zhang Ke,Lu Jiangbo,Gauthier Lafruit,et al.Robust Stereo Matching with Fast Normalized Cross-Correlation over Shape-adaptive Regions[C]. In IEEE International Conference on Image Processing, 2009:2357-2361.

[25] Shi Limin, Guo Fusheng,Gao Wei,et al.Stereo Matching with Adaptive Support-Weight correlation and Graph Cuts[C]. Systems Man and Cybernetics， 2010 IEEE International Conference, 2010:3575-3579.

[26] 李立武,汪增福.一种基于图像分割的动态规划立体匹配算法[J]. 电子技术研发.2010,37(10)：30-32.

[27] 刘赫伟,汪增福.一种沿区域边界的动态规划立体匹配算法[J]. 模式识别与人工智能,2010,23(1)：38-44.

[28] Shi Wanli, Wang Hongyong.An Approach for Stereo Matching Using Pair-wise Sequence Alignment Algorithm Based on Dynamic Programming[C].In International Conference on Challenges in Environmental Science and Computer Engineering,2010:511-514.

[29] Zhao Ming, Li Xiao-bai, Lang Rong-ling.Improved Adaptive Stereo Matching Using Double Dynamic Programming with Correlation of Row and Column[J].In International Conference on Signal Processing Systems, 2010(3):95-102.

[30] XiaoJu,Xia Linyuan, Lin Liqun.Segment-based Stereo Matching Using Edge Dynamic Programming[C].In International Congress on Image and Signal Processing，2010:1676-1679.

[31] Liang Chia-Kai, Cheng Chao-Chung,Lai Yen-Chieh, et al. Hardware-Efficient Belief Propagation[C].In IEEE Conference on Computer Vision and Pattern Recognition，2011:80-86.

[32] Yang Qingxiong, Wang Liang, Narendra Ahuja.A Constant-Space Belief Propagation Algorithm for Stereo Matching[C]. In IEEE Conference on Computer Vision and Pattern Recognition, 2010:1458-1465.

[33] Lai Yen-chieh, Cheng Chao-chung, Liang Chia-Kai, et al. Efficient Message Reduction Algorithm for Stereo Matching Using Belief Propagation[C].In International Conference on Image Processing,2010:2977-2981.

[34] Sumit Srivastava,Seong Jong Ha,Sang Hwa Lee,et al.Stereo Matching Using Hierarchical Belief Propagation Along Ambiguity Gradient[C]. In International Conference on Image Processing, 2009:2085-2088.

[35] 朱程辉,任冉冉.一种基于图割理论的快速立体匹配算法[J].微型机与应用,2010, 29(10):34-38.

[36] Anman Zureiki,Michel Devy,Raja Chatila.Stereo Matching Using Reduced-Graph Cuts[C].In International Conference on Image Processing,2009:237-240.

[37] 杨海涛.三维视频编码技术研究[D].西安电子科技大学，2010.