近年来，3D视频技术^[1]备受人们的青睐。它的一个主要发展方向是基于彩色加深度的自由视点视频系统(FVV)^[2]。目前，基于深度图的绘制(DIBR)^[3-4]技术是实现该系统的一个关键。在该系统中，只需要在发送端编码并传输少量的几个视点及对应的深度图，在解码端解码后通过DIBR技术绘制出任意位置的视点。DIBR技术不但节省了大量的传输带宽，而且实现了在任意位置进行视点间切换的功能，使得观众在任意视角都能够感受到逼真的立体视觉效果。

然而，当前的DIBR技术具有较高的计算复杂度，很难应用于实时的3D视频系统。DIBR技术主要包括3D-Warping、像素插值、虚拟视点融合^[5]和空洞填补^[6-7]等环节，其中，3D-Warping环节的时间消耗占据了整个绘制过程的90%以上。目前很多DIBR的算法都是针对于这些环节所进行的改进，但只是单纯地提高绘制的主、客观质量，没有在质量和速度二者之间做出较好的权衡。文献[8]提出了一种分层的空洞填补算法，有效地解决了伪影问题，但由于该算法需要递归地进行上、下采样操作，消耗了大量的绘制时间。Li等人^[9]提出了一种混合像素块的像素插值方法，在一定程度上提高了像素插值的精度，但由于该算法需要迭代地进行像素区间的交、并和补集操作，复杂度较高。文章[10-11]提出了基于GPU并行编程的实时虚拟视点绘制方法，提高了绘制的速度，但是这对系统的硬件配置提出了比较高的要求。文献[12]提出了一种分离查找表技术，加快了3D-Warping的速度，但是没有考虑到3D-Warping之后的像素插值精度问题，绘制的客观质量有待提高。

DIBR技术主要适用于两种不同的相机系统：水平设置相机系统和汇聚设置相机系统。其中，前者应用更为广泛。本文纯粹从软件角度出发，针对水平设置相机系统中DIBR技术所存在的问题，提出了一种基于快速3D-Warping的虚拟视点绘制算法。它是通过深度—视差映射表和基于像素块的3D-Warping等两项技术来加快绘制速度的。深度—视差映射表是一张由量化深度到视差之间的映射表。通过查表操作可以避免重复地进行视差求解，节省了视差求取的时间。基于像素块的3D-Warping技术充分利用了深度图的空间相关性。因为深度图的纹理结构相对平坦，在某个特定中心点周围存在着很多深度值相似的像素点。参考视点中深度值相同的相邻像素点经过3D-Warping以后，在虚拟视点的相对位置不会发生变化。根据这个原理，可以对深度图进行固定像素块分割，并且对深度值相同的像素块进行基于块的3D-Warping。对于每个特定块而言，只需要进行一次映射关系的计算，减少了3D-Warping的计算量，加快了绘制速度。除此之外，还提出了一种改进的像素插值算法，有效地提高了插值的精度，非常适用于实时性的像素插值。实验结果表明，本文算法不但提高了绘制的速度，而且改善了绘制的客观质量。

DIBR技术是通过利用左、右两个参考视点以及对应的深度图像来产生中间虚拟视点的。它主要包括两个环节：3D-Warping和虚拟视点融合。

3D-Warping操作是为了将参考视点图像空间中的像素点映射到虚拟视点图像空间中。它首先将参考视点中的坐标位置为(u_r,v_r)的像素点映射到世界坐标系，方程为

$ \left( \begin{array}{l} {X_{\rm{w}}}\\ {Y_{\rm{w}}}\\ {Z_{\rm{w}}} \end{array} \right){\rm{ = }}R_{\rm{r}}^{{\rm{ - }}1} \cdot \left( {{z_{\rm{r}}}K_{\rm{r}}^{{\rm{ - }}1}\left( \begin{array}{l} {u_{\rm{r}}}\\ {v_{\rm{r}}}\\ 1 \end{array} \right){\rm{ - }}{T_{\rm{r}}}} \right) $

(1)

然后将该点从世界坐标系映射到虚拟视点图像坐标系中的(u_v,v_v)处，方程为

$ {z_{\rm{v}}}\left( \begin{array}{l} {u_{\rm{v}}}\\ {v_{\rm{v}}}\\ 1 \end{array} \right){\rm{ = }}{K_{\rm{v}}}({R_{\rm{v}}}\left( \begin{array}{l} {X_{\rm{w}}}\\ {Y_{\rm{w}}}\\ {Z_{\rm{w}}} \end{array} \right) + {T_{\rm{v}}} $

(2)

式中，R、T和K分别表示旋转矩阵、平移矩阵和相机的内参矩阵。X_w，Y_w和Z_w分别表示世界坐标系中的3个分量。

在分别对左、右参考视点进行3D-Warping和像素插值之后，即可以得到左、右参考虚拟视点图像。为了产生最终的虚拟视点图像，需要对这两幅图像进行融合，融合函数为

$ \begin{array}{l} {I_{\rm{v}}}(u,v) = \\ \left\{ {\begin{array}{*{20}{l}} {(l - \alpha ){I_l}({u_l},{v_l}) + \;\;({u_l},{v_l}) \ne {\rm{Hole}}且}\\ {\alpha {I_{\rm{r}}}({u_{\rm{r}}},{v_{\rm{r}}})\;\;\;\;\;\;\;\;\;\;\;({u_{\rm{r}}},{v_{\rm{r}}}) \ne {\rm{Hole}}}\\ {{I_l}({u_l},{v_l})\;\;\;\;\;\;\;\;\;\;\;\;\;({u_l},{v_l}) \ne {\rm{Hole}}}\\ {{I_{\rm{r}}}({u_{\rm{r}}},{v_{\rm{r}}})\;\;\;\;\;\;\;\;\;\;\;\;\;({u_{\rm{r}}},{v_{\rm{r}}}) \ne {\rm{Hole}}}\\ {0\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;其他} \end{array}} \right. \end{array} $

(3)

$ \alpha = \frac{{\left| {{t_{\rm{v}}} - {t_l}} \right|}}{{\left| {{t_{\rm{v}}} - {t_l}} \right| + \left| {{t_{\rm{v}}} - {t_{\rm{r}}}} \right|}} $

(4)

即，当(u_l,v_l)和(u_r,v_r)均不为空洞(Hole)时，利用加权系数α对它们进行线性加权操作；当有且仅有一个像素点不为空洞时，则采用非空洞像素点；否则，将(u,v)置为空洞点。其中，I_l(u_l,v_l)和I_r(u_r,v_r)分别表示左、右参考虚拟视点中(u_l,v_l)和(u_r,v_r)位置处的像素值。

以提高绘制速度为主要目的，提出了新的3D-Warping的算法，主要包括3个部分：深度—视差映射表、基于像素块的3D-Warping和改进的像素插值方法。根据插值对象的不同，改进的像素插值方法分为基于像素点的像素插值和基于像素块的像素插值。本文算法的流程如图 1所示。首先，在绘制开始之前，建立深度—视差映射表。其次，需要对深度图像按照固定大小块进行分割，并以像素块为单位计算它的深度纹理复杂度。如果该像素块为深度平坦块，则对该像素块进行基于块的3D-Warping；如果该像素块为非平坦块，则对该像素块中的像素点进行逐像素点的3D-Warping。然后，查找深度—视差映射表以求取视差，计算出映射像素块或映射像素点在虚拟视点图像中的位置。最后，根据像素块和像素点的不同，执行相应的像素插值操作。

文献[12]提出了一种分离查找表技术来加速3D-Warping过程。受文献[12]启发，建立了一种适用于水平设置相机系统的深度—视差映射表来加速3D-Warping过程。在水平设置相机系统中，3D-Warping过程一般是以视差为桥梁的，视差表示了映射过程中参考视点和虚拟视点之间相对位置的偏移量，假设参考视点图像空间内坐标为(x_i,y_i)的像素点的视差为D_i，经过3D-Warping，被映射到虚拟视点图像空间中(x′_i,y′_i)处。由于水平相机只存在水平方向的视差，即

$ \begin{array}{l} {I_v}(x{'_i},y{'_i}) - = {I_r}({x_i},{y_i})\\ x{'_i} = {x_i} - {D_i} \end{array} $

(5)

求取每一个像素点的视差D需要经过两个步骤：根据量化后的深度v求取反量化后的深度Z，根据Z求取视差D。其中，实际深度Z的求解公式为

$ Z = \frac{{1.0}}{{\frac{v}{{255.0}}\left( {\frac{1}{{{Z_{{\rm{near}}}}}} - \frac{1}{{{Z_{{\rm{far}}}}}}} \right) + \frac{1}{{{Z_{{\rm{far}}}}}}}} $

(6)

视差D的求解公式为

$ D = \frac{{Bf}}{Z} $

(7)

式中，Z_near、Z_far分别表示实际场景距离相机的最近、最远距离，B是指参考视点到虚拟视点间的基线距离，f代表相机焦距，v表示量化后的深度。

为了加速3D-Warping，可以将式(6)(7)进行合并，得

$ D = \frac{{vBf}}{{255}}\left( {\frac{1}{{{Z_{{\rm{near}}}}}} - \frac{1}{{{Z_{{\rm{far}}}}}}} \right) + \frac{{Bf}}{{{Z_{{\rm{far}}}}}} $

(8)

在式(8)中，除了变量v=0~255，其余参数均为常量。令

$ P = \frac{{Bf}}{{255}}\left( {\frac{1}{{{Z_{{\rm{near}}}}}} - \frac{1}{{{Z_{{\rm{far}}}}}}} \right) $

(9)

$ Q = \frac{{Bf}}{{{Z_{{\rm{far}}}}}} $

(10)

那么

$ D = Pv + Q $

(11)

由于P，Q均为常数。所以，要想建立从量化后的深度v到视差D之间的映射表，需要进行256次乘法和256次加法操作。在建立深度—视差映射表之后，不必每次都按照式(6)(7)来求取视差，只需要从映射表中查找v所对应的视差D，并将视差D代入式(5)进行计算即可。查表的方法避免了重复的视差求取操作，加快了3D-Warping速度。

首先，对深度图以固定大小的块进行分割；然后，判断该像素块是否为平坦块，如果是深度平坦块，则直接采用基于像素块的3D-Warping，否则，采用基于像素点的3D-Warping。通常，可以通过计算深度图像中像素块的深度值方差来判定它是否为深度平坦块，但方差的计算量相对较大。本文为了加快绘制速度，采取了其一阶范式的形式，即

$ E = \frac{1}{{p \times q}}\sum\limits_{(x,y) \in C} {\left| {{D_t}(x,y) - {D_{{\rm{avg}}}}} \right|} $

(12)

$ {D_{{\rm{avg}}}} = \frac{1}{{p \times q}}\sum\limits_{(x,y) \in C} {{D_t}(x,y)} $

(13)

式中，D_t表示第t帧的深度图，C为当前块，p、q分别为像素块的长和宽。

基于像素块的3D-Warping如图 2所示。如果参考视点的当前像素块经式(12)(13)判断为深度平坦块，则选取该当前块中的一个像素点(x_c,y_c)，利用3D-Warping方法计算出该像素点在虚拟视点图像中的坐标(x′_c,y′_c)，从而建立了从参考视点图像中像素坐标位置到虚拟视点图像中的坐标位置的映射关系。因为块内所有像素点深度值相同(视差相同)，也即在3D-Warping前后，块内所有像素点的相对位置不变；所以对于该像素块中的其他像素点，只需要根据相对位置关系，进行线性平移即可。对于深度非平坦块，块内像素点的深度值存在差异，因而在3D-Warping过程中块内的像素点的相对位置将会发生变化。如果强行采取基于像素块的3D-Warping，则会引入绘制失真。基于块的3D-Warping减少了需要进行3D-Warping的像素点数，降低了3D-Warping过程的计算时间开销。

在3D-Warping操作之后，映射的像素块或像素点不一定与整像素点对齐，为了将它们对应到整像素位置上，需要进行像素插值操作。像素插值的精确程度直接影响了绘制的主、客观质量。为了在提高绘制的速度的同时，保证绘制质量不下降，本文对像素插值算法进行了改进。与两种3D-Warping方法相对应的插值算法也有两种：基于像素块的像素插值和基于像素点的像素插值。由于这二者之间存在一定的差别，分别对它们进行阐述。

根据映射像素块与待插值像素块之间距离的不同，对映射像素块采取了两种不同的插值策略。如果映射像素块与待插值像素块的距离dist小于阈值th₁，则对块中所有像素点采取紧邻插值^[13]；否则，对像素块内部的像素点采取线性插值，对像素块边缘像素点向外扩充。

基于像素块的紧邻插值法如图 3所示，由灰色圆点标记的3×3的投影块a_i,j,(i=0~2,j=0~2)与待插值尺寸相同的像素块(P(1,0)~P(3,2))之间的距离小于水平阈值th₁，所以，对该像素块内的所有像素点采取紧邻插值法，插值方向如箭头所示。

基于像素块的线性插值法如图 4所示，由于P(1,0)到a_0,0和a_1,0之间的最小距离dist大于阈值th₁，所以对于映射块内部的待插值的像素点(P(1,0~2)和P(2,0~2))，利用左、右相邻的映射像素点进行线性插值，插值方向如箭头所示；对映射块边缘像素点(a_0,0~a_0,2和a_2,0~a_2,2)，向外扩充。如果不向外扩充，可能会在相邻像素块之间产生条纹状的空洞，图 5(a)为未进行边缘扩充的绘制效果图，图中存在大量的条纹状空洞；图 5(b)为对映射像素块的边缘进行扩充之后的绘制效果图，图中的条纹状空洞得到了消除。

改进的基于像素点的插值算法在水平方向上和深度方向上均作了相应的改进，下面从这两个角度展开论述。

由于投影像素点不一定正好落在虚拟视点的整像素位置上，所以需要利用周边的非整像素点对整像素点位置进行像素插值，传统的插值方法有两种：紧邻插值法和线性插值法。由于深度图失真较为严重，像素点在3D-Warping过程中往往会发生不同程度的偏移。为了抑制深度失真对像素插值精度的影响，对上述两种插值算法进行了折中，具体策略为：如果投影像素点与最近像素点的距离小于阈值th₁，则采用紧邻插值；否则，采用Splatting插值法^[14]。

在基于像素块和像素点的3D-Warping过程中会产生遮挡现象，即多个投影像素点插到同一个整像素位置处。标准方案采取了Z-Buffer^[15]技术来解决遮挡问题，即只采取了深度值最大的投影像素点进行插值操作。由于深度图失真，这样的做法可能会引入绘制失真，对Z-Buffer技术进行了改进。如果在插值过程中，发现有新的映射点插到该位置，则将当前深度值D_v(x)与新映射点的深度值d进行判断：$\left| {{D_{\rm{v}}}(x) - d} \right| > t{h_2}$。如果该条件成立，则采取Z-Buffer技术；否则，更新像素点的像素值的公式为

$ I{'_{\rm{v}}}(x) = \frac{{({D_{\rm{v}}}(x) + 1){I_{\rm{v}}}(x) + (d + 1)I}}{{{D_{\rm{v}}}(x) + d + 2}} $

(14)

更新像素点的深度值为

$ D{'_{\rm{v}}}(x) = max\{ {D_{\rm{v}}}(x),d\} $

(15)

式中，I_v(x)、I′_v(x)分别表示更新前、后的像素值，D_v(x)和D′_v(x)分别表示更新前、后的深度值，I表示当前映射点的像素值，阈值为

$ t{h_2} = \frac{{255\Delta D}}{{Bf}}\frac{1}{{\frac{1}{{{Z_{{\rm{near}}}}}} - \frac{1}{{{Z_{{\rm{far}}}}}}}} $

(16)

由于一般超过3个像素宽度的偏移会引入严重的绘制失真，所以通常取ΔD=3以求得阈值th₂。

改进后的插值算法不需要进行上、下采样操作，也不需要保存任何的中间数据。在遇到多个投影像素点插到同一个像素位置时，只需要按照式(14)(15)执行更新操作即可。改进的插值方法不但提高了插值的精度，而且不会增加时间复杂度。

为了验证本文算法的性能，通过虚拟视点绘制实验，并从绘制虚拟视点的绘制时间和客观质量等角度出发，和标准绘制方案VSRS(view synthesis reference software)以及文献[12]的算法进行了对比分析。实验的硬件环境如下：主频为3.40 GHz的i3-2130处理器，4.00 GB内存。实验的软件环境如下：64位Win7操作系统，VSRS3.5标准绘制平台以及在此平台的整像素精度绘制方案的基础上修改、添加本文算法之后的绘制平台。实验所采用的测试序列如下：Nagoya提供的Dog、Kendo序列；GIST提供的Newspaper序列；HHI提供的Book Arrival、Door Flowers、Alt-Moabit和Leave Laptop序列，各序列对应的分辨率以及参考视点和目标视点的选取如表 1所示。实验包含的基本功能模块：3D-Warping、虚拟视点融合和空洞填补。本文算法的参数设置如下：像素块尺寸为4×4像素，深度平坦块的判定阈值为0(完全平坦)。VSRS算法的参数设置如下：所有参数均采用默认值。另外，由于标准绘制方案VSRS主要有半像素和整像素精度等两种配置。其中，半像素精度绘制质量较高，但速度较慢；整像素精度绘制质量较低，但速度较快。为了充分体现本文算法的性能，在时间对比的时候，主要与整像素精度进行对比分析，在客观质量对比的时候，主要与半像素精度进行对比分析。

为了验证本文算法的时间复杂度，在其他基本绘制环节不变的条件下，将文献[12]算法、深度—视差映射表和本文算法与标准绘制方案的整像素精度进行时间上的对比实验。测试结果如表 2所示，T_ori1、T_DPT、T_warp和T_pro分别对应着原始标准绘制方案的整像素精度、深度—视差映射表算法、改进的3D-Warping算法和本文算法绘制一帧图像所消耗的时间，ΔT_LUT和ΔT_pro分别表示深度—视差映射表算法和本文算法与VSRS算法相比，绘制一帧图像的时间节省百分比。实验结果表明，深度—视差映射表算法比VSRS算法平均节省绘制时间33.34%，本文算法比VSRS算法平均节省绘制时间72.05%。这说明了本文算法能够有效地提高绘制的速度，其中，改进的3D-Warping算法性能略高于深度—视差映射表算法。与深度—视差映射表算法相比，文献[12]消耗的时间略长，这主要是由于文献[12]引入了改进的图像融合算法，增加了一定的时间复杂度。与文献[12]相比，本文算法节省了59.70%的绘制时间。这主要是由于本文引入的基于像素块3D-Warping算法所做出的贡献。

从表 2中还可以发现，改进之前，3D-Warping占据了整个绘制过程的90%以上的绘制时间，这说明3D-Warping环节是影响绘制速度的最主要环节。本文所提出的快速3D-Warping算法的时间复杂度为VSRS算法的32.75%。这说明了本文算法在绘制复杂度上具有较高的性能。

为了分析基于像素块的3D-Warping和基于像素点的3D-Warping的绘制时间比例情况，对这两种映射方式进行了统计实验，表 3给出了部分测试序列的统计结果。表 3中N_f和N_c分别表示平坦像素块和复杂像素块的个数，其中，前者是采用基于像素块的3D-Warping，后者是采用基于像素点的3D-Warping；T_f和T_c分别表示绘制平坦像素块和复杂像素块消耗的时间总量；T_avgf和T_avgc为它们的平均值；R表示平坦块和复杂块绘制时间的比例。统计结果表明，在其他条件相同的情况下，基于像素块的3D-Warping时间消耗是基于像素点的3D-Warping的30%左右。因此，本文提出的基于像素块的3D-Warping可以极大地提高绘制速度，特别是对于深度平坦区域较多的深度序列效果尤为突出。

为了确定水平阈值th₁的准确取值，在size=4，阈值th₁分别为0.1、0.2、0.25、0.3、0.4和0.45等条件下测试了各测试序列的PSNR和SSIM两项指标。如表 4所示，在th₁≤0.3时，随着阈值的增大，测试序列的PSNR和SSIM整体呈上升趋势；在0.3<th₁<0.45时，随着阈值的增大，测试序列的PSNR和SSIM整体呈下降趋势。这说明了th₁=0.3时，各个测试序列能够取得较为理想的客观绘制效果。

在水平阈值th₁=0.3，其他参数如前文所述的条件下，各测试序列的PSNR和SSIM的对比实验结果如表 5所示，其中，VSRS₁，VSRS₂分别表示在标准准绘制方案的整像素精度和半像素精度条件下的绘制结果。由表 5可知：本文算法的所有测试序列的性能明显优于文献[12]算法；与标准方案的整像素精度相比，本文算法的两项指标有了显著的提高；与标准方案的半像素精度相比，本文算法测试序列的平均PSNR提高了0.355 dB，平均SSIM提高了0.001 15。由于不同测试序列的性质(如深度图失真程度、纹理复杂度等)不同，不同测试序列的改善程度可能有所不同，如Alt-Moabit序列改善相对比较明显，Door Flowers序列稍微有所下降，这都属于正常情况。对于大多数序列，本文插值算法性能较稳定。

图 6为Book Arrival序列第8视点的第48帧绘制图像的局部放大图。红色方框标记出了衣服边缘局部放大图，该方框中包含了16×16个像素点。局部放大图右边的数字阵列中的数字为各个像素点与原始图像的绝对差值，代表了绘制失真的大小，其中，数字越大说明失真越大。图 6中的像素块本应为衣服的黑色，但由于参考视点深度图失真，与衣服边缘邻近的墙面处深度值大于实际深度值(超过了衣服处的深度值)。由传统的Z-Buffer技术插值之后，像素块的左半部分会被左边灰色的墙面所覆盖。在其他3种算法的绘制视点中，该像素块的左半部分失真总体偏大，如图 6(c)(d)(e)所示。本文的像素插值算法克服了Z-Buffer算法的局限性，没有完全舍弃该位置处深度值较小的映射像素点，而是在一定的深度范围内对其进行加权操作，如式(14)(15)。与图 6(c)(d)(e)相比，图 6(f)的数字总体偏小，这证明了本文的像素插值算法可以提高像素插值精度，减少绘制失真。

需要说明的是，前、背景边缘部位失真对客观质量(如PSNR)尤为显著，本文插值算法尤其能够改善这种前、背景边缘失真，图 7为桌子边缘处的局部放大图，图 7(b)(c)(d)中桌子边缘含有明显的毛刺，图 7(e)中的毛刺得到消除。

提出了一种基于像素块3D-Warping的快速绘制算法。它通过引入深度—视差映射表和基于像素块的3D-Warping来加速3D-Warping过程，在很大程度上加快了绘制的速度。在基于像素块的3D-Warping过程中，还充分地考虑到插值的准确度问题，对像素插值算法进行了改进，提高了绘制的客观质量。实验结果表明，与标准绘制方案的整像素精度相比，本文算法节省了72.05%的绘制时间；与标准绘制方案的半像素精度相比，PSNR平均提高了0.355 dB，SSIM平均提高了0.001 15。本文算法对平坦区域较多的深度视频用于虚拟视点绘制时特别有效。然而，本算法只适用于水平设置相机系统的虚拟视点绘制。会聚相机系统中DIBR技术的计算复杂度过高的问题将是今后的研究方向。