多视角视频图像深度搜索方法及深度估计方法

摘要

本发明涉及多视角视频图像处理技术，本发明提出一种搜索步长的自适应确定方法与一种基于自适应搜索步长的深度估计方法。多视角视频图像深度搜索方法，在深度搜索范围内每一步的搜索步长根据当前深度值动态调整，使得每一步的搜索步长对应于相同的像素搜索精度；多视角视频图像的深度估计方法，在利用基于深度的视图合成和基于块配的深度搜索中，在深度搜索范围内，每一步的搜索步长根据当前深度值动态调整；本发明技术方案适用于多视角视频的深度搜索与深度估计，本发明的深度搜索性能上高于固定搜索步长，深度估计中合成的图像块与参考图像块的绝对差小，错误估计少，且计算量或深度搜索次数少。

说明书

技术领域

本发明涉及多视角视频图像处理技术。

背景技术

近年来，研究者们逐渐认识到，未来先进三维电视和任意视角视频应用系统(FVV，Free Viewpoint Video System)中应该利用计算机视觉、视频处理和基于深度图像的场景合成等技术，把视频的获取和显示设置分离开来，即观看视角与获取视频的照相机方位相互不受限制，从而提供高度的灵活性、交互性和可操作性。欧洲的立体电视项目采用了视频加深度的数据格式(“基于深度图像的合成、压缩和传输的三维电视新方法”，立体显示和虚拟现实系统SPIE会议，2004.C.Fehn，“Depth-image-based rendering(DIBR)，compression and transmi ssion for a new approach on 3D-TV，”in Proc.SPIE Conf.Stereoscopic Displays and Virtual Reality Systems XI，vol.5291，CA，U.S.A.Jan.2004，pp.93-104.)，即图像的每个像素对应一个深度值；利用基于深度图像的视图合成方法(DIBR：Depth Image Based Rendering)：接收端解码器根据显示设置和观看视角生成立体图像对，从而使观看视角与获取视频的照相机方位相互不受限制。2007年4月JVT会议提案(“先进三维视频系统的多视角视频加深度的数据格式”；A.Smolic and K.Mueller，et al.“Multi-View Video plus Depth(MVD)Format for Advanced 3DVideo Systems”，ISO/IEC JTC1/SC29/WG11，Doc.JVT W100，San Jose，USA，April2007.)把视频加深度推广到多视角视频，提出了视频家深度的多视角编码数据格式MVD(Multi-view video plus depth)。由于MVD能够满足先进三维视频或任意视角视频应用的一个本质需求，即能够在解码端生成一定范围内的连续的任意视角的视图，而不是数量有限的离散的视图，所以视频加深度的MVD方案已经被JVT采纳，被确定为今后的发展方向。

所以，如何从不同视角的两幅或多幅视图获取场景的深度信息成为多视角视频处理中的重要问题之一。

目前的深度搜索方式为：在固定搜索范围内采用固定搜索步长(uniform depth-grid)进行深度搜索。使用固定搜索步长时，若在较小深度值处给定的搜索步长对应于1个像素的偏移量，则在较大深度值处，该搜索步长对应的像素偏移量将小于1个像素。假设在给定的深度值下投影到非整数像素时，取最近邻的像素点作为投影点，则深度搜索时将在多个不同的深度值处搜索到同一像素点，即出现了重复搜索。反过来，若给定的搜索步长在较大深度值处对应于1个像素的偏移量，则在较小深度值处该搜索步长对应的像素偏移量将大于1个像素，即相邻两个深度值将搜索到两个非相邻的像素点，从而使得有些像素点漏检，产生搜索不全。所以，本来期望在搜索范围[z_min，z_max]内搜索N个像素点，但由于产生了像素点重复搜索或漏搜索，实际搜索到的有效搜索点要少于N。为了保证搜索范围包含场景真实深度值的所有可能取值，通常把搜索范围设得足够大，而为了保证一定的搜索精度，把搜索步长设得较小，这大大增加了搜索次数和相应的计算量，并且由于漏搜索和重复搜索的存在，搜索效果并不好。

迄今，已有很多与深度估计相关的研究和估计算法，但大多数通过对校正的、平行立体图像对先进行视差估计，再根据视差与深度的关系计算深度信息。例如，平行相机系统中两幅图像之间只存在水平视差，利用基于特征或块匹配的方法先估计视差，然后根据深度与视差成反比的关系计算出深度信息；而对于非平行相机系统，则要经过图像对校正、视差匹配、深度计算和反校正等一系列处理才能得到原始视图对应的深度图。该类深度估计问题本质上就是进行视差估计，其性能主要由视差估计算法决定。众所周知，视差估计或立体匹配是计算机视觉中的经典问题，虽然至今已有大量的研究工作和成果，但纹理信息缺乏或遮挡所引起的匹配模糊性或不确定性使得视差匹配问题仍旧是计算机视觉中的研究热点和难点。

2006年，JVT会议提案(“多视角视频编码核心实验3报告”；S.Yea，J.Oh，S.Ince，E.Martinian and A.Vetro，“Report on Core Experiment CE3 of MultiviewCoding”，ISO/IEC JTC1/SC29/WG11，Doc.JVT-T123，Klagenfurt，Austria，July2006.)提出了利用照相机内外部参数和基于深度的视图合成，在某一指定的深度搜索范围内用给定的搜索步长，搜索使得合成视图与实际视图之间的误差最小的深度作为估计值。M.Okutom等人提出了多基线立体系统的立体匹配方法(A multiple-baseline stereo)，该方法利用深度与视差的反比关系，把视差估计转化为深度求解问题，并且消除了视差匹配中的不确定性难题(“多基线立体系统”，模式识别与机器智能IEEE学报；M.Okutomi and K.Kanade，“A multiple-baseline stereo”，IEEE Trans.on Pattern Analysis andMachine Intelligence 15(4)：353-363，1993.)。N.Kim等人提出了在距离/深度空间直接进行深度搜索、匹配和视图合成操作(“一般的多基线立体系统和利用深度空间搜索、匹配和合成的直接视图合成”，计算机视觉国际期刊；N.Kim，M.Trivedi and H.Ishiguro，“Generalized multiple baseline stereo and direct view synthesis usingrange-space search，match，and render”，International Journal of ComputerVision 47(1/2/3)：131-148，2002.)：在深度空间直接进行深度搜索，不需要视差匹配，图像校正处理直接在深度搜索过程中完成，并且深度值是连续值，其精度不像视差向量那样受图像像素分辨率的限制。但是实际求解中，需要指定深度搜索范围和搜索步长，根据某一代价函数求最优解，而搜索范围和步长的取值是否合适对估计性能至关重要。

视差匹配中，视差搜索范围通常根据图像性质直观确定，而深度搜索中，特别是在非平行相机系统中，由于深度变化与图像像素偏移的关系并不显而易见，所以其搜索范围难以合理确定。

所以，对给定的多视角视图如何确定合适的深度搜索区间和步长成为有效估计深度信息的关键。

JVT-W059(“视图合成预测核心实验6报告”；S.Yea and A.Vetro，“Report ofCE6 on View Synthesis Prediction”，ISO/IEC JTC1/SC29/WG11，Doc.JVT W059，SanJose，USA，April 2007.)提出利用两幅视图的匹配特征点对，从若干组备选的深度搜索的最小值、最大值和搜索步长中选取使得匹配特征点对之间的误差最小的一组作为深度搜索范围和步长，该方法需要用KLT(Kanade Lucas-Tomasi)算法(“特征点的检测和跟踪”，卡内基梅隆大学技术报告；C.Tomasi，and T.Kanade，“Detection and tracking ofpoint features”，Technical Report CMU-CS-91-132，Carnegie Mellon University，1991.)进行特征提取匹配，性能依赖于特征匹配的正确性。

M.Okutom和N.Kim等人提到用最长基线的参考视图的1个像素偏移量所对应的深度变化值作为搜索步长，从而保证在所有其他参考视图中的像素偏移量小于1个像素。

上述两种方法都是使用固定的搜索步长，没有根据图像内容或场景的变化自适应地调整步长。

发明内容

本发明所要解决的技术问题是，提出一种搜索步长的自适应确定方法，能避免像素点重复搜索或漏搜索。另外，本发明还提出了一种基于自适应搜索步长的深度估计方法。

本发明为解决上述技术问题所采用的技术方案是，多视角视频图像深度搜索方法，其特征在于，在深度搜索范围内每一步的搜索步长根据当前深度值动态调整，当前深度值越小，采用的搜索步长越小；当前深度值越大，采用的搜索步长越大，使得每一步的搜索步长对应于相同的像素搜索精度；

根据深度变化值和像素偏移向量的关系，把所述深度搜索范围和搜索步长的确定转化为像素搜索范围和像素搜索精度的确定；所述像素搜索精度等于搜索中每一次像素偏移向量的长度；所述像素搜索精度可以为分像素精度如二分之一个像素，四分之一个像素，或整像素精度，如一个像素，两个像素；所述搜索步长等于搜索中每一次像素偏移向量所对应的深度变化值；

目标视图的搜索步长由目标视图中当前深度值、参考视图中的像素偏移向量和视图对应的照相机内外部参数确定，目标视图中每一步的搜索步长在参考视图中对应于相同长度的像素偏移向量。所述的目标视图是指当前需要估计深度的图像，所述的参考视图是指多视角视频系统中的其他图像。参考视图可以在深度搜索过程中自动选择或由用户指定；

搜索步长由以下公式得到：

$\mathrm{\Delta z}=\frac{{(z{b}_3^{T}P+c_3^T\Delta t_r)}^2{\left|\right|\Delta P_r\left|\right|}^2}{\Delta P_r^T(b_3^{T}P{C}_r\Delta t_r-c_3^T\Delta t_r{B}_{r}P)-(z{b}_3^{T}P+c_3^T\Delta t_r)\left(b_3^{T}P\right){\left|\right|\Delta P_r\left|\right|}^2}$

其中：P是目标视图中待深度估计的像素点，z为像素点P的当前深度值，Δz为像素点P的深度变化值即搜索步长，ΔP_r为目标视图中像素点P的深度变化值Δz在参考视图r中对应的像素偏移向量，‖ΔP_r‖²＝ΔP_r^T·ΔP_r，；B_r＝A_rR_r^-1RA^-1和C_r＝A_rR_r^-1是3×3的矩阵，Δt_r＝t-t_r是三维向量；其中，R为目标视角的相机坐标系相对于世界坐标系的三维旋转矩阵；t为目标视角的相机坐标系相对于世界坐标系的平移向量；A为目标视角的相机内部参数矩阵；R_r为参考视角的相机坐标系相对于世界坐标系的三维旋转矩阵；t_r为参考视角的相机坐标系相对于世界坐标系的平移向量；A_r为参考视角的相机内部参数矩阵；b₃和c₃分别是矩阵B_r和C_r的第三行向量。对于平行相机系统，所述深度变化值与当前深度值的平方成正比。

所述参考视图中的像素偏移向量满足目标视角和参考视角的极线约束方程：

$\Delta P_r^T(C_r\Delta t_r\times B_r)P=0,$其中，P是目标视图中的像素点，ΔP_r为参考视图中的像素偏移向量。存在两个互为相反方向的所述像素偏移向量ΔP_r满足所述的极线约束方程，所述2个像素偏移向量分别对应深度值增大方向、深度值减小方向；深度值增大方向的偏移向量所对应的深度变化值大于深度值减小方向的偏移向量所对应的深度变化值。

多视角视频图像的深度估计方法，在利用基于深度的视图合成和基于块配的深度搜索中，目标视图的深度搜索范围和搜索步长由参考视图的像素搜索范围和像素搜索精度决定；在深度搜索范围内，每一步的搜索步长根据当前深度值动态调整，当前深度值越小，采用的搜索步长越小；当前深度值越大，采用的搜索步长越大，使得每一步的搜索步长对应于相同的像素搜索精度；

所述深度搜索步长由目标视图中当前深度值、参考视图中的像素偏移向量和视图对应的照相机内外部参数确定，目标视图中每一步的搜索步长在参考视图中对应于相同长度的像素偏移向量；

所述的基于深度的视图合成，是指给定目标视图的像素点和深度值，根据目标视角和参考视角的相机内外部参数，把该像素点反投影到三维场景空间点，再把该空间点重新投影到参考视角的图像平面的方法，得到目标视图在该参考视角的合成视图；

所述基于深度的视图合成和基于块配的深度搜索具体为，利用当前深度值进行视图合成，并计算合成视图的像素块与参考视图的像素块之间的误差；采用最小误差对应的深度值为目标视图的深度估计值；

多视角视频图像的深度估计方法具体包括以下步骤：

步骤1估计目标视图中的深度搜索初始值z_k＝0；

步骤2确定深度搜索对应于参考视图中的像素搜索范围和像素搜索精度，根据像素搜索精度得到参考视图中像素偏移向量ΔP_r；

步骤3根据当前深度值z_k和像素偏移向量ΔP_r，得到对应的深度变化值Δz，所述深度变化值Δz即为下一步搜索步长；

步骤4利用当前深度值z_k进行视图合成，并计算合成视图的像素块与参考视图的像素块之间的误差e_k；

步骤4更新当前深度值z_k＝z_k+Δz；k＝k+1；

步骤5判断是否超过给定的像素搜索范围，如是进入步骤6，如否，进入步骤3；

步骤6以误差e_k(k＝0，……，N-1，N为搜索总步数)中最小误差对应的深度值为估计值。所述搜索步长由以下公式得到：

$\mathrm{\Delta z}=\frac{{(z{b}_3^{T}P+c_3^T\Delta t_r)}^2{\left|\right|\Delta P_r\left|\right|}^2}{\Delta P_r^T(b_3^{T}P{C}_r\Delta t_r-c_3^T\Delta t_r{B}_{r}P)-(z{b}_3^{T}P+c_3^T\Delta t_r)\left(b_3^{T}P\right){\left|\right|\Delta P_r\left|\right|}^2}$

其中：P是目标视图中待深度估计的像素点，z为像素点P的当前深度值，Δz为像素点P的深度变化值即搜索步长，ΔP_r为目标视图中像素点P的深度变化值Δz在参考视图r中对应的像素偏移向量，‖ΔP_r‖²＝ΔP_r^T·ΔP_r，；B_r＝A_rR_r^-1RA^-1和C_r＝A_rR_r^-1是3×3的矩阵，Δt_r＝t-t_r是三维向量；其中，R为目标视角的相机坐标系相对于世界坐标系的三维旋转矩阵；  t为目标视角的相机坐标系相对于世界坐标系的平移向量；A为目标视角的相机内部参数矩阵；R_r为参考视角的相机坐标系相对于世界坐标系的三维旋转矩阵；t_r为参考视角的相机坐标系相对于世界坐标系的平移向量；A_r为参考视角的相机内部参数矩阵；b₃和c₃分别是矩阵B_r和C_r的第三行向量。对于平行相机系统，所述当前深度值的平方与深度变化值成正比。所述参考视图中的像素偏移向量满足目标视角和参考视角的极线约束方程：

$\Delta P_r^T(C_r\Delta t_r\times B_r)P=0,$其中，P是目标视图中的像素点，ΔP_r为参考视图中的像素偏移向量。

本发明的有益效果是，自适应搜索步长的深度搜索不会出现像素漏搜索与重复搜索，深度估计中合成的图像块与参考图像块的绝对差小，错误估计少，且计算量或深度搜索次数少。

附图说明

图1为多视角视频系统中的坐标系设置示意图；

图2为基于深度的视图合成示意图；

图3(a)Uli测试序列中第7相机的视频序列的初始时刻的视图；

图3(b)Uli测试序列中第7相机的视频序列的初始时刻的视图；

图3(c)为图2(a)的局部示意图，16个示意点表明的区域为像素点[527，430]至[590，493]的图像区域；

图4为深度变化值与深度值平方的关系示意图；

图5为本发明深度变化值与像素偏移向量的示意图；

图6为深度值较小时的像素漏搜索的示意图；

图7为深度值较大时的像素重复搜索的示意图；

图8为本发明自适应调整深度搜索步长的示意图；

图9为采用本发明自适应的变长搜索步长搜索到像素点的分布示意图；

图10采用固定搜索步长和本发明自适应步长的深度搜索性能示意图。

具体实施方式

本发明提出了一种深度搜索步长的自适应确定方法，利用相机内外部参数和透视投影关系，首先推导出像素点深度值、深度变化值以及深度变化引起的投影点在合成视图中的像素偏移量之间的关系，根据推导出的深度变化值与相应像素偏移量之间的关系式，把深度搜索范围的确定转化为像素搜索范围的确定，像素偏移量在图像中有直观意义，容易合理确定；并且根据像素偏移量与深度值的关系，即深度值越大，相同的深度变化值引起的像素偏移量就越小，动态地调整搜索步长，使得每一个搜索步长对应着相同的像素搜索精度，避免了像素点重复搜索或漏搜索，从而提高了搜索效率和性能。另外，本发明还提出了一种简单有效的初始深度估计方法，该方法通过求解汇聚相机系统中相机光轴的汇聚点，并把该点看作场景缩影点，从而得到场景深度的一个大概估计。

在多视角视频中通常需要三个类型的坐标系来描述场景及其图像位置信息，它们分别是场景所在的世界坐标系、相机坐标系和像素坐标系，如图1所示。其中，相机坐标系以相机中心为原点、光轴为z轴，xy平面与图像平面平行；像素坐标系则以图像左上角为坐标原点，水平和垂直坐标为u，v。

设相机c_i(i＝1，……，m)的相机坐标系o_i-x_iy_iz_i相对于世界坐标系o-xyz的位置用三维旋转矩阵R_i和平移向量t_i表示，其中m为相机个数。场景中一点在世界坐标系下的坐标用向量p＝[x，y，z]表示，在相机坐标系o_i-x_iy_iz_i中的坐标用向量p_i＝[x_i，y_i，z_i]表示，则根据空间几何和坐标变换，有如下关系：

p＝R_ip_i+t_i                        (1)

根据计算机视觉透视投影原理，相机坐标系下的坐标p_i与其在图像平面的齐次像素坐标P_i＝[u_i，v_i，1]满足以下关系：

z_ip_i＝A_ip_i                        (2)

其中，A_i为参考视角的相机c_i内部参数矩阵，主要包括相机焦距、中心和变形系数等参数。

本发明在深度空间进行基于块匹配的深度搜索，即利用照相机内外部参数和基于深度的视图合成，在深度搜索范围内用搜索步长搜索使得合成视图的像素块与对应的实际参考视图的像素块之间的误差最小的深度值，并把该深度值作为目标视图的像素点的深度估计值。目标视图和目标视角是指当前需要估计深度的图像和对应的视角，参考视图和参考视角是指多视角视频系统中的其他图像和视角。参考视图和参考视角可以在深度搜索过程中自动选择或由用户指定。

当视图中像素点的深度值给定时，根据相机内外部参数可以把该像素点反投影(backproject)到场景空间中得到一空间点，再把该空间点重新投影(re project)到所需视角方向的图像平面，得到该视角的合成视图，这就是基于深度的视图合成技术，如图2所示。

考虑两个视图的情形，设视图1为目标视图，视图2为参考视图。视图1中的像素点P₁在其相机c₁坐标系下的深度值为z₁，该点在视图2中的对应像素点为P₂，在其相机c₂坐标系下的深度值为z₂，根据公式(1)(2)可推导得到

$z_1{R}_1{A}_1^{-1}{P}_1+t_1=z_2{R}_2{A}_2^{-1}{P}_2+t_2---\left(3\right)$

由式(3)得到：

$A_2{R}_2^{-1}(z_1{R}_1{A}_1^{-1}{P}_1+t_1-t_2)=z_2{P}_2---\left(4\right)$

为方便描述，记：

$C=A_2{R}_2^{-1},B=A_2{R}_2^{-1}{R}_1{A}_1^{-1}={\mathrm{CR}}_1{A}_1^{-1},t=t_1-t_2---\left(5\right)$

则(4)式变为：

z₁BP₁+Ct＝z₂P₂                         (6)

其中B，C是三维矩阵，t是两个相机之间的平移向量。由于P₁，P₂是齐次坐标，可消去(6)中的z₂，得到像素点P₁在视图2中的像素齐次坐标为：

$P_2=\frac{z_2{P}_2}{z_2}=\frac{z_1{\mathrm{BP}}_1+\mathrm{Ct}}{z_1{b}_3^T{P}_1+c_3^{T}t}\widehat{=}{f}_2(z_1,P_1)---\left(7\right)$

其中b₃和c₃分别是矩阵B和C的第三行向量；

由式(9)可得出：在相机c₁与c₂内外部参数已知的情况下，视图2的像素点值是关于视图1中的像素点值及其深度值的函数。利用公式(7)进行视图1在参考视角2中的视图合成。

视图1中的像素点P₁，在给定的深度z下通过反投影和重投影得到其在相机c₂的视角中的合成视图2的像素点P₂，$P_2\widehat{=}{f}_2(z,P_1),$根据计算机视觉中的常用假设，同一场景点在不同视角的视图中的对应像素点具有相同的亮度色度值，则在深度值z下视图1的像素点P₁在视角2的合成视图2中的像素点P₂的亮度色度值为：

Synthesized_I₂(P₂)＝Synthesized_I₂(f₂(z，P₁))＝I₁(P₁)    (8)

I₁为视图1，I₂为视图2，Synthesized_I₂为视图1在参考相机视角2中的合成视图2。上述说明是以两个相机组成的相机系统为例，同样可以进一步得出由m个相机组成的相机系统可以适用于上述原理。

假设在以像素点P为中心的局部窗口W内的像素点P_j具有相同的场景深度值，则在窗口W内视图1的合成视图2与相机在视角2实际拍摄得到的参考视图2的绝对差为：

$\mathrm{SAD}(z,P)=\underset{P_j\in W}{\Sigma }\left|\right|\mathrm{Synthesised}\_I_2(f(z,P_j)-I_2(f(z,P_j))\left|\right|$

$=\underset{P_j\in W}{\Sigma }\left|\right|I_1\left(P_j\right)-I_2\left(f(z,P_j)\right)\left|\right|---\left(9\right)$

由于合成视图2是利用参考视图2对应的照相机参数计算得到，所以理论上真实场景深度值下的合成视图2与参考视图2具有相同的亮度色度值。因此，视图1在像素点P的深度值求解可以转化为以下问题：

$\underset{z\in \{\mathrm{depth><mo>\}</mo>}}{\min }\mathrm{SAD}(z,P)---\left(10\right)$

即在给定深度搜索范围(depth range)内，把使得合成视图与参考视图的绝对差最小的深度z作为最终的深度估计值。

这种在深度空间直接进行深度搜索的方法，不需要视差匹配，图像校正处理直接在深度搜索过程中完成，并且深度值是连续值，其精度不像视差向量那样受图像像素分辨率的限制

从公式(7)知道，在相机内外部参数已知的情况下，合成视图2的像素点是关于视图1中的像素点及其深度值的函数。若视图1中的像素点P1对应的深度值变化Δz，则其在合成视图2中的像素坐标为：

$P_2^{\prime }=\frac{(z_1+\mathrm{\Delta z}){\mathrm{BP}}_1+\mathrm{Ct}}{(z_1+\mathrm{\Delta z})b_3^T{P}_1+c_3^{T}t}---\left(11\right)$

所以，视图1中的像素点P₁的深度值变化Δz引起其在合成视图2中的像素偏移向量为：

$\mathrm{\Delta P}=P_2-P_2^{\prime }=\left(\begin{array}{c}\mathrm{\Delta u}\\ \mathrm{\Delta v}\\ 0\end{array}\right)=\frac{z_1{\mathrm{BP}}_1+\mathrm{Ct}}{z_1{b}_3^T{P}_1+c_3^{T}t}-\frac{(z_1+\mathrm{\Delta z}){\mathrm{BP}}_1+\mathrm{Ct}}{(z_1+\mathrm{\Delta z})b_3^T{P}_1+c_3^{T}t}---\left(12\right)$

由式(12)可以推导出视图1中的像素点的深度值变化Δz和合成视图2中的相应像素点偏移向量ΔP的关系为：

$\mathrm{\Delta z}(b_3^T{P}_1\mathrm{Ct}-c_3^{T}t{\mathrm{BP}}_1-(z_1{b}_3^T{P}_1+c_3^{T}t)b_3^T{P}_1\mathrm{\Delta P})={(z_1{b}_3^T{P}_1+c_3^{T}t)}^2\mathrm{\Delta P}---\left(13\right)$

用ΔP^T左乘(13)的两边，得到：

$\mathrm{\Delta z}=\frac{{(z_1{b}_3^T{P}_1+c_3^{T}t)}^2{\left|\right|\mathrm{\Delta P}\left|\right|}^2}{\Delta P^T(b_3^T{P}_1\mathrm{Ct}-c_3^{T}t{\mathrm{BP}}_1)-(z_1{b}_3^T{P}_1+c_3^{T}t)\left(b_3^T{P}_1\right){\left|\right|\mathrm{\Delta P}\left|\right|}^2}---\left(14\right)$

其中，‖ΔP‖²＝ΔP^TΔP是像素偏移向量ΔP的模的平方。所以，当相机参数已知时通过(14)可求得在深度z₁处像素偏移向量ΔP所对应的深度变化值Δz。

另外，由式(6)可得到两幅视图的对应像素点该满足如下极线约束方程：

P₂^T(Ct×B)P₁＝0                       (15)

P₂′^T(Ct×B)P₁＝0                     (16)

其中×是向量的又乘。所以，式(15)减去式(16)得到像素偏移向量ΔP也应该满足极线约束方程：

ΔP^T(Ct×B)P₁＝0    (17)

给定相机参数和像素点P₁的情况下，式(17)是关于像素偏移向量ΔP的两个分量Δu和Δv的齐次线性方程。

对于平行相机系统，同一场景点在两幅视图中的视差d与其深度成反比，即

$d=\frac{\mathrm{fB}}{z}---\left(18\right)$

其中d和z分别是视差和深度，f和B分别是相机的焦距和基线长度。则视图1中的像素点P₁的深度值由z₁变化到z₂时，它在合成视图2中的对应投影点的像素偏移量为

$\left|\right|\mathrm{\Delta P}\left|\right|=|d_1-d_2|=\mathrm{fB}\frac{|z_1-z_2|}{z_1{z}_2}\approx \mathrm{fB}\frac{\left|\mathrm{\Delta z}\right|}{{z_1}^2}---\left(19\right)$

根据(19)知道，深度变化值与像素偏移量成正比，与深度值的平方成反比。对于相同的像素偏移量，当所处的深度值越大，对应的深度变化值就越大，当所处的深度值越小，对应的深度变化值就越小。对于汇聚相机系统，当两个相机的角度不是很大时，从式(12)也可以看出，深度变化值、像素偏移量和深度值之间有近似的关系。

为了验证该结论，我们用如图3所示的Uli测试序列(该该多视角视频数据由德国的Heinrich-Hertz-Institut(HHI)提供，可以从https://www.3dtv-research.org/3dav_CfP_FhG_HHI/https://www.3dtv-research.org/3dav_CfP_FhG_HHI/下载得到。该视频序列采用由8台以汇聚方式排列的摄像机拍摄得到，视频格式为1024x768，25fps)本文采用第7和第8台相机的视频序列的初始时刻的视图)的第7和第8台相机的参数，根据公式(14)和(17)计算在视图7(如图3(a))中的像素点P＝[526，429]处(对应于衬衣领子右边的扣子)，深度变化值、深度值平方和像素偏移量之间的关系。给定满足极线约束(17)的单位像素偏移向量，即‖ΔP‖＝1，根据(14)计算得到不同的深度值对应的深度变化值，它们之间的关系如图4所示，其中横坐标为深度值的平方，纵坐标为深度变化值。图4表明，当合成视图中的像素偏移量给定时，深度变化值与深度值的平方近似成线性关系，这意味着在不同深度值处，视图1中像素点的相同量的深度变化值在合成视图中引起不同的像素偏移量。

值得注意的是，由于(17)是关于像素偏移向量ΔP的齐次线性方程，所以ΔP存在互为相反方向的两种情形ΔP₊和ΔP_-，把它们代入(14)可求得一正一负的两个深度变化值Δz₊和Δz_-，即ΔP₊和ΔP_-分别对应于深度值增大和深度值减小所引起的像素偏移向量。由前面分析知道，像素偏移量给定时，深度变化值与深度值的平方近似成正比关系，所以相同大小不同方向的两个像素偏移向量ΔP对应的深度变化值并不相同，即深度值减小量|Δz_-|小于深度值增大量|Δz₊|，如图5所示。例如，取Uli视图7(如图3(a)所示)中的像素点P＝[526，429]，深度值3172mm，像素偏移量为64个像素，即‖ΔP‖＝64，根据(14)(17)求得两个相反方向的像素偏移向量对应的深度变化值分别为Δz₊＝930和Δz_-＝-593。

根据以上分析知道，相同像素偏移量的情况下，深度变化值与深度值的平方近似成正比关系。所以使用固定搜索步长时，若在较小深度值处给定的搜索步长对应于1个像素的偏移量，则在较大深度值处，该搜索步长对应的像素偏移量将小于1个像素。假设在给定的深度值下投影到非整数像素时，取最近邻的像素点作为投影点，则深度搜索时将在多个不同的深度值处搜索到同一像素点，即出现了重复搜索。反过来，若给定的搜索步长在较大深度值处对应于1个像素的偏移量，则在较小深度值处该搜索步长对应的像素偏移量将大于1个像素，即相邻两个深度值将搜索到两个非相邻的像素点，从而使得有些像素点漏检，产生搜索不全。所以，本来期望在搜索范围[z_min，z_max]内搜索N个像素点，但由于产生了像素点重复搜索或漏搜索，实际搜索到的有效搜索点要少于N。

例如，我们对Uli视图7中的像素点P＝[526，429]，在[2000，4500]的范围内，以10mm的固定步长进行深度搜索。如图6所示，当深度值较小时，例如在2090处搜索到的像素点u坐标为661，而在深度值2080处搜索到的像素点的u坐标为663，中间有像素点跳过而没有被搜索到；而如图7所示，当深度值较大时，例如两个不同的深度值4450和4460处搜索到了u坐标为437的同一个像素点，即像素点进行了重复搜索。由于10mm的搜索步长在真实深度值3170局部范围内对应于1个像素的搜索精度，所以本来我们期望在[2000，4500]的范围内搜索到250个不同的像素，但由于发生了像素漏搜索和重复搜索，实际计算发现只搜索了200个像素 。

为了使深度搜索过程中，搜索步长对应于参考视图中相同的像素搜索精度，即搜索步长始终对应于参考视图中固定个像素的偏移量，必须根据深度变化值与深度值之间的关系动态调整搜索步长，并确定相应的搜索范围。假设视图1中的像素点P₁的初始搜索深度值为z₀，则根据式(14)可方便地求得在深度z₀下，参考视图2中的像素偏移量ΔP对应的视图1中的深度变化值Δz。当初始深度值z₀与真实深度值相差不是很大的情况下，像素点P₁在参考视图2中的真实对应像素点与深度z₀下求得的像素点之间的像素偏移量通常局限于某一范围内。下面给出在像素搜索范围N内，如何根据深度值自适应确定搜索步长，使得搜索步长始终对应固定个像素的偏移量。

给定像素点P₁和相机参数，根据像素偏移向量的极线约束方程(16)，很容易求解得到像素偏移量‖ΔP‖对应的两个互为相反方向的偏移向量ΔP₊和ΔP_-，然后根据(14)计算出对应的两个深度变化值Δz₊和Δz_-，把它们作为下一步深度值变小和变大方向的搜索步长，如图8所示，

z_-1＝z₀+Δz₊₁             (20)

z₁＝z₀+Δz₁

接看，在深度值Δz_-1和偏移向量ΔP_-下，利用(14)计算出对应的深度变化值Δz_-2，在深度值z₁和偏移向量ΔP₊下，利用(14)计算出对应的深度变化值Δz₊₂，并把它们分别作为下一步的搜索步长，即

z_-2＝z_-1+Δz_-2

z₂＝z₁+Δz₂               (21)

以此类推，可得到第n步的搜索深度和步长为：

z_-n＝z_-(n-1)+Δz_-n

z_n＝z_(n-1)+Δz_n           (22)

其中，搜索步数n根据搜索范围N和搜索精度确定，即n满足n·Δ≤N。

所以确定了搜索范围和初始深度值z₀后，利用以上方法就可以求得随着深度值变化而自适应调整的变长搜索步长，使得深度搜索过程中保持相同的像素搜索精度，克服了固定搜索步长中像素重复搜索或漏搜索的缺陷。由于深度搜索范围通过搜索步长的累加得到，因而也随着深度值的变化而自适应地调整，深度值变大时，相同的像素偏移量‖ΔP‖对应的深度搜索范围相应地变大；当深度值变小时，相同的像素偏移量‖ΔP‖对应的深度搜索范围也相应地变小。另外，我们还可以很方便地通过像素精度Δ控制深度搜索精度，如Δ＝1对应于单位像素的搜索精度，而Δ＝1/2对应于半像素的搜索精度。

所以，有了深度值变化和像素偏移向量之间的关系，如式(14)，就可以通过确定像素搜索精度的方法来确定相应的深度搜索步长，深度搜索范围的确定也转化为相应的像素偏移量的确定。像素偏移量和搜索精度的确定类似于视差估计中搜索范围和精度的确定，具有直观意义，容易确定，并且可根据图像内容或应用需求，通过调整像素偏移量和搜索精度，动态确定相应的深度搜索范围和步长。

在深度估计过程中，需要给定一个深度初始值z₀，该初始值的取值好坏影响着深度搜索性能和效果。当z₀与真实深度值的偏差较小时，可以使用较小的像素偏移量即搜索范围可以小一些，从而减小搜索量过高搜索速度；当z₀与真实深度值的偏差较大时，则要使用相对较大的像素偏移量，以保证搜索到真实深度值，因而计算量较大。虽然差的深度初始值可通过设定大范围的搜索范围和高精度的搜索步长来改善搜索性能，但是良好的深度初始值可以确定小范围的搜索范围和合适的步长，从而提高深度搜索的效率和性能。所以，在深度估计过程中深度初始值的估计和确定也非常重要。

视频序列图像的初始深度值的确定可分为两种情形，初始时刻的图像和后续图像。初始时刻图像的深度初始值的确定又分为两种，即第一个像素和其它像素。对于第一个像素，由于还未对任何像素进行过深度搜索，因此没有任何已知的场景深度信息，此时需要考虑如何从图像特征和相机参数等信息中获得场景深度的大概值作为初始值；对于后续其他像素，则可以根据图像内邻近像素点的深度估计值确定其初始深度。对于后续的图像，由于同一视角的视频序列图像的深度值有很强的相关性，静止不动的背景区域的深度保持不变，而只有少数的运动区域的深度发生变化，所以可以把前一时刻图像的同一像素点位置的深度值作为初始值。所以，初始深度值的确定中，关键在于获得初始时刻图像的场景深度信息，为第一个像素提供较好的深度初始值。

多视角视频中，不同视图的图像之间的差异或照相机的位置信息通常包含着有关场景深度的信息。下面针对汇聚相机系统和平行相机系统两种情形，给出在没有任何已知深度信息的情况下，根据照相机参数或图像信息进行场景深度的初始估计。

多视角视频的主要目标是在多个角度拍摄同一场景的信息，所以相机通常呈圆弧形放置，并且相机光轴汇聚于一点，即汇聚系统。实际应用中，虽然相机可能不严格汇聚于一点，但总可以找到一个与各相机光轴距离最近的一个点，这个点被认为汇聚点。汇聚点通常都是场景所在的位置，可以认为是场景的一个缩影点，所以通过求得汇聚点的位置就可以求得场景深度的一个大概值，并把该值作为深度搜索中的初始值。

设汇聚点在世界坐标系中的坐标为Mc＝[x_c，y_c，z_c]，该点位于每个相机的光轴上，所以该点在以光轴为z轴的相机坐标系中可以表示为：

M₁＝[0，0，z_r1]

M₂＝[0，0，z_r2]

  ------                                        (23)

M_m＝[0，0，z_rm]

其中z_ri是汇聚点在相机c_i坐标系中的深度。根据世界坐标与相机坐标的关系，有以下式子：

M_c＝R₁M₁+t₁

M_c＝R₂M₂+t₂

  ------                               (24)

M_c＝R_mM_m+t_m

消去Mc得到：

R₁[0，0，z_r1]+t₁＝R₂[0，0，z_r2]+t₂

R₁[0，0，z_r1]+t₁＝R₃[0，0，z_r3]+t₃

  ------                               (25)

R₁[0，0，Z_r1]+t₁＝R_m[0，0，z_rm]+t_m

式(25)是关于深度z_r1，z_r2，---，z_rm的3(m-1)个线性方程。用线性最小二乘法求解方程组(25)，可得到汇聚点在各相机坐标系中的深度值z_r1，z_r2，---，z_rm，它们是场景深度的一个大概值，可作为深度搜索中的深度初始值。

平行相机系统中不存在汇聚点，不能用以上方法求深度信息，但此时视差与深度有简单的反比关系(18)，所以可通过计算两幅视图之间的全局视差的方法得到深度信息。

全局视差可定义为使两视图的绝对差最小的像素偏移量，即通过以下方法求得：

$g_x=\underset{x}{\min }\left[\frac{\underset{i,j\in R}{\Sigma }\left|\right|I_1(i,j)-I_2(i+x,j)\left|\right|}{R}\right]---\left(26\right)$

其中，R是视图1和2的重叠区域的像素个数。由于对全局视差的估计精度要求不高，所以式(26)中像素偏移量x的搜索单位可以设得大一点，譬如8个像素或16个像素，从而可以大大减少计算量。求得全局视差后，根据深度与视差成反比的关系式(18)，即可求得深度初始值。

利用Uli视频序列参数文档提供的一个场景点：眼镜左边的高亮度点的真实世界坐标[35.07，433.93，-1189.78](单位mm)，并根据世界坐标和相机坐标的关系式(1)可得到该场景点在相机坐标系下的坐标和真实深度信息；再利用上述求两个相机汇聚点的方法，即通过求解线性方程组(26)得到汇聚点在相机7和相机8中的坐标系下的深度值，计算结果如表1所示。根据人眼观测判断，Uli场景的景深变化不大，而表1中深度初始估计值与场景点的真实深度信息相差不大，说明了深度初始估计值较为有效合理，为深度估计提供了良好的初始值。

(坐标单位mm)相机7坐标系下的深度值相机8坐标系下的深度值真实深度值3076.23163.7深度初始估计值2871.22955.7

表1

如图3(c)所示的Uli视图从像素点[527，430]至[590，493]的64x64图像区域。对该区域内每隔15个像素的像素点，共16个像素点，用固定步长和自适应步长分别进行深度搜索。在固定搜索范围[2000，5000]内进行三次采用固定搜索步长的搜索，步长分别为20，35，50。自适应搜索步长的确定中，初始深度为2817，像素偏移量设为32个像素，搜索精度为1个像素，后续像素点的深度初始值设为邻近像素点的深度估计值。根据本发明自适应搜索步长的确定方法，可得到像素点[527，430]在偏离初始搜索像素点32个像素的搜索范围内，每单位像素的搜索精度所对应的搜索步长，如表2所示，按这些搜索步长搜索到像素点如图9所示。表2说明，沿着深度值减小方向的步长为负值，并且随着像素偏移量的增大、深度值的减小，步长的绝对值逐渐减小；而沿着深度值增大方向的步长为正值，并且随着像素偏移量的增大、深度值的增大，步长的绝对值逐渐增大。图9表明，用表2的变长搜索步长进行深度搜索时，对应的像素搜索精度确保持不变，始终是1个像素。

  像素偏  移量  步长(深度值  增大方向)  步长(深度值  减小方向)  像素  偏移  量  步长(深度值  增大方向)  步长(深度值  减小方向)  1  11.4877  -11.2503  17  12.8909  -10.1000  2  11.5686  -11.1728  18  12.9870  -10.0340  3  11.6502  -11.0960  19  13.0842  -9.9687  4  11.7328  -11.0201  20  13.1824  -9.9041  5  11.8162  -10.9450  21  13.2818  -9.8400  6  11.9005  -10.8706  22  13.3823  -9.7766  7  11.9858  -10.7969  23  13.4840  -9.7138  8  12.0719  -10.7240  24  13.5868  -9.6515  9  12.1590  -10.6519  25  13.6908  -9.5899  10  12.2470  -10.5805  26  13.7961  -9.5289  11  12.3360  -10.5098  27  13.9025  -9.4684  12  12.4260  -10.4397  28  14.0101  -9.4086  13  12.5169  -10.3704  29  14.1191  -9.3493  14  12.6089  -10.3018  30  14.2293  -9.2905  15  12.7018  -10.2339  31  14.3407  -9.2323  16  12.7958  -10.1666  32  14.4535  -9.1746

表2

利用基于块匹配的方法进行深度估计，深度搜索结果图10所示，图中每个点表示搜索得到的深度值下的合成块与实际块之间的绝对差，该值越小通常代表深度估计值越精确。采用固定搜索步长时，由于步长越小表示搜索的精度越高，所以深度估计的效果越好，如步长20mm搜索得到的深度值下得到的绝对差小于步长35mm的绝对差，而35mm的绝对差小于50mm。但是，自适应的搜索步长下搜索得到的深度值结果最好，其对应的绝对差最小。

图3(c)为视图2(a)中像素点[527，430]至[590，493]的图像区域内进行深度估计的16个像素点，分别采用自适应搜索步长，固定步长20，35，50进行搜索。表3表明，采用自适应搜索步长时，16个像素点都搜索到了正确的深度值，而采用固定步长时存在错误的深度估计。这是由于这几个像素点处于纹理缺乏的区域，在大范围的固定搜索范围内，搜索得到的绝对差最小点并不对应于正确的像素点。而采用自适应的搜索步长时，由于初始值根据邻近信息确定，像素偏移量可以设得较小，即在相对较小的局部范围内进行搜索，降低了搜索到错误像素点的几率，并且在保证了一定的深度光滑性。表3列出了使用自适应搜索步长和固定搜索步长时的深度估计结果、深度搜索次数和错误估计个数，表中有边框的数据为错误数据。表3结果说明自适应搜索步长搜索时搜索次数少且没有错误估计，而固定搜索步长搜索时搜索次数多且还存在错误估计。例如32个像素偏移量的自适应深度搜索中只要搜索64个深度值，而20mm的固定搜索步长在[2000，5000]的搜索范围内需要搜索150个深度值。

表3

通过表3和图10的结果，得出结论：自适应搜索步长的深度搜索性能上高于固定搜索步长，即利用估计的深度值合成的图像块与参考图像块的绝对差小，错误估计少，且计算量或深度搜索次数少。