一种基于建模的图像渲染算法的并行实现﹡

于昊，郭 立，刘 鹏，王成彰

（中国科学技术大学 电子科学与技术系，安徽 合肥 230027）

0 引言

随着多媒体技术的不断发展，传统的二维视频已不能满足人们的生活工作的需要。相对于二维视频，三维视频增添了视觉效果的现实感，并且能够让用户自由选择视角，是一种交互性很强的媒体。三维视频技术还可以广泛应用于数字电视，远程教育，远程工业控制，三维视频会议系统，和虚拟现实系统等方面。

三维视频技术[1]的关键在于3D渲染方法。传统的3D渲染方法有，基于图像的建模技术（IBM）和基于图像的渲染技术（IBR）。

IBM是传统的图形学立体成像方法。通过计算场景的精细模型和拍摄少量的环绕视点图像，借助空间坐标系与屏幕坐标系间的映射规则进行采样与投影，继而获得很好的渲染效果。其优点是纹理数据量小。然而由于渲染结果的好坏受到重建模型的精确度的影响，所以对模型的精确度要求较高，对于简单场景可实现实时渲染，但在处理复杂场景时则将大量时间耗费在场景建模部分上，不利于实时渲染。

IBR根据已知的图像来合成新视图，其优点是无需对场景进行建模，计算量与场景复杂度无关，而且渲染结果具有照片级的逼真效果。1996年，M.Levoy和P.Hanrahan首次提出了基于Light field[2]的渲染方法；2006年，清华大学设计了一个8×8CCD传感器阵列作为光场采集系统[3]，使用Light field算法实现了实时交互式动态光场的传输系统。由于这种方法没有几何模型作为约束，为避免模糊现象，导致采样过于密集，表面光场数据量大，不利于光场数据的存储与传输。

结合以上两种算法的优点，在此提出了一种基于建模的图像渲染技术IBMR[4]，采用传统的Light field方法，通过增加粗糙模型信息来减少视点采样。

近年来，多核计算机发展迅速，半导体厂商们正致力于在单个基片上集成更多的执行核，而不是提高处理器的主频，四核和八核的计算机已进入市市场。随着多核计算机的应用推广，基于多核的算法并行设计逐渐成为研究热点[5-7]。对于3D渲染算法中涉及的大量计算，可通过多核并行设计实现。1997年，OpenMP标准形成[8]，它是一种用于编写可移植的多线程应用程序的API，其优点是在不影响实验结果的前提下，通过多核处理器加速串行程序。由此采用OpenMP对IBMR算法进行了并行化分析改进[9]。实验表明，本算法可以获得比较满意的渲染效果，而且算法的关键部分在双核处理器上平均加速比可以达到1.70。

1 光场模型Light field

Light field的思想就是建立一个光场函数以记录目标的表面光场信息，即目标的表面颜色信息。

1.1 光场信息的获取

采用环绕场景目标拍摄的方式设置相机，拍摄不同视点下的目标图像，然后通过三维立体重构计算目标的三维网格模型，根据相机的定标参数，确定目标与相机的投影关系。

1.2 光场信息分割

假设光线在空间中传播辐照度不变，那么七维的全光函数可以简化为四维P(r,s,θ, φ) ,其中(r, s) 表示目标表面上一点，(θ, φ)表示视线方向。由于采用的是三维网格模型，所以将目标表面光场信息分割到所在三角面的顶点上，如式（1），PΔ(r, s,θ, φ)为三角面上像素的光场信息，vj为三角面的顶点:

2 算法流程

算法流程图如图1所示。

图1 算法流程

算法分为编码和解码2个部分。编码部分生成表面光场信息，即表面纹理和视点纹理；解码部分则是生成新视点视图。

2.1 编码部分

由于采用的3D模型是三角面网格模型,为了避免渲染结果出现颜色过渡不连续的现象,所以编码部分选用的采样单元是模型顶点的三角面环。

首先计算每个顶点的可见视点列表，三角面环的采样在可见视点图像中进行。然后建立世界坐标系与视点屏幕坐标系间的映射关系，计算投影矩阵M。按照 OpenCV的标准，可以设置模型视点矩阵Mmodelview和视锥体投影矩阵Mproj，根据这2个矩阵可以完成世界坐标系到视点屏幕坐标系的投影。对于每个可见视点图像，将 3D模型投影到可见视点屏幕坐标系中，以三角面环为单位进行采样。

由于要进行自由视点观测，所以要生成虚拟视点以及虚拟视点下的采样信息。采用 Delaunay三角剖分法来实现虚拟视点的生成。虚拟视点下的采样信息则通过真实视点的采样信息插值产生，生成顶点的光场矩阵 Pvj，如式（2），M为三角面环采样点数，N为可见视点数，其中包括可见虚拟视点。

由于矩阵Pvj的冗余度高，不利于数据传输，需要提取Pvj的主导成分。采用矩阵分解[10]的方式，如式（3）所示，其中称gk(r, s)为表面纹理，称hk(θ, φ)为视点纹理:

矩阵分解完成后，可采用一些经典的压缩算法对结果进行进一步压缩处理，如S3TC等。

2.2 解码部分

首先对压缩码流进行预处理，完成坐标变换，投影，屏幕映射等操作。

然后以三角面为单元，以3个顶点的局部坐标系作为参考系，先分别计算三角面内像素的纹理坐标，从表面纹理中读取相应的纹理值，(rm,sm)，再计算3个顶点局部坐标系下视点的m m纹理坐标，从视点纹理中读取视点纹理，hvj(θn,φn)，通过式(4)可得到三角面内像素的值:

3 算法的并行实现

并行实现方式有任务分解和数据分解。任务分解是将一个算法分为若干个任务模块，根据模块间的独立性来判别是否可以并发执行，由于是在串行算法上进行并行优化，各模块有严格的执行顺序，所以不满足任务分解的条件；数据分解则是对待处理数据集进行分组，要求各组数据是相互独立的，可通过派生线程完成数据的并行处理。数据分解是一种比较普遍的并行实现方式。

通过对算法的分析，编码部分的关键在于顶点光场矩阵的生成，因为顶点光场矩阵的分解压缩可采用一些经典的高效压缩算法，所以矩阵压缩部分可不作并行考虑；解码部分则是计算三角面像素的坐标以及检索表面纹理和视点纹理，这部分的耗时要远小于编码部分，所以解码部分也不需并行实现。

由图1可知，顶点光场矩阵的生成可分为顶点可见性计算及采样和虚拟视点生成及采样，实验中采用双核处理器实现。

3.1 顶点可见性计算及采样的并行实现

根据摄像机标定，先计算摄像机中心在世界坐标系中的坐标 O=(XC，YC，ZC）。假设三角面的3个顶点的世界坐标为X1,X2,X3，三角面中心坐标为→)/3，归一化的三角面法向量 N。计算与N的夹角θ的余弦值以判定三角面的可见性:若cosθ大于0，则认为可见，反之，则认为不可见。顶点的可见性判别:顶点的三角面环中只要有一个三角面被认为是不可见的，则该顶点被认为不可见。由此，得出每个顶点的可见视点列表。

顶点采样。对于一个真实视点图像，根据摄像机标定，将 3D模型投影到视点的屏幕坐标系中，将屏幕坐标系中的投影三角面与二维平面上的等腰直角三角形对应，如图2所示。采用基于重心坐标权重的颜色采样计算每个采样点 x的颜色值。

图2 三角面与等腰直角三角形的对应关系

由于各顶点的计算任务都是独立的，所以采用数据分解的并行化方式。如果将每个顶点的可见性计算及采样看作一个任务，各任务相互独立，所以可采用数据分解的方式实现。解决方案如图3所示，假设有3000个待处理的顶点，平均分为2组由2个核执行完成。

图3 顶点计算任务分配

顶点可见性计算及采样的并行伪代码如下。

3.2 虚拟视点生成及采样的并行实现

虚拟视点生成。首先建立顶点的局部坐标系:以顶点的法向量N作为局部坐标系的Z轴，然后再空间中任选一垂直于N的向量S作为X轴，以S×N作为Y轴，将所求得的向量单位化，即得到顶点的局部坐标系。

将可见的参考视点投影到顶点局部坐标系中,采用Delaunay三角剖分法，如图4所示。将单位圆内的虚拟视点加入到顶点的可见视点列表。

采用基于重心坐标的权重插值法计算虚拟视点与真实视点的权重，由真实视点的采样值插值产生虚拟视点的采样值。

图4 虚拟视点的生成

虚拟视点生成及采样的并行位代码如下。

4 实验结果与分析

表1为实验数据，采用的实验平台是 Intel Core2 T5450@1.66GHz，1.67 GHz。程序用 C++编译,用OpenMP2.0实现并行部分。

表1 实验数据包

表2为顶点光场矩阵生成的加速比，从实验数据可知，两个模块的并行计算均达到了比较满意的加速效果。双核平台上的加速比的理论值为2.0，然而由于线程的创建和销毁，以及线程间的同步开销，读写锁操作等原因，不能达到理论值。另一个制约加速比的因素是计算负载均衡的问题。由于OpenMP的线程创建与调度都是操作系统随机分配完成的，所以会产生负载不均的情况。在顶点的可见性计算及采样模块的并行中，每个顶点的三角面环的采样点数目不同，两个核所承载的计算量无法均衡，从而降低了加速比；在虚拟视点生成的模块中，由于各顶点的可见视点数量不均，导致在Delaunay三角剖分时的计算复杂度有较大的差异，所以这一模块受负载不均的影响较大，加速比较比前一模块要低。

表2 顶点光场矩阵生成的加速比 ms

算法渲染的结果如图5所示,图5(a)与图5 (c)为原始视图，图5(b)与图5 (d)为渲染结果。从实验结果可知，算法的渲染结果还是另人满意的。

图5 渲染结果对比

5 结语

提出了一种基于建模的图像渲染技术的并行实现方法。在已知目标的三维网格模型和环绕视点图像的前提下，对顶点的三角面环进行采样，获得目标的表面光场信息，并通过三角剖分法生成虚拟视点，从而达到在自由视点下观测和漫游目标的目的。为加快程序的运行速度，对算法的关键部分进行了并行化分析和改进，实验表明，并行部分的平均加速比达到了 1.70。下一步工作是对矩阵压缩部分进行并行化分析及加速[11]，以及探讨本算法在行为检测方面上的应用。

[1]沈燕飞,代锋,张勇东.交互式三维视频技术[J].信息技术快报,2005,3(08):13-31.

[2]LEVOY M, HANRAHAN P.Light Field Rendering[C]//Proc. SIGGRAPH’96. New Orleans:ACM SIGGRAPH,1996:31-42.

[3]LIN Y,DAI Q,XU W. A Real Time Interactive Dynamic Light Field Transmission System[C]//Multimedia and Expo, 2006 IEEE International Conference.Toronto:IEEE Conference Publications,2006:2173-2176.

[4]CHEN Wei-Chao, CHU M H. Light Field Mapping:Efficient Representation and Hardware Rendering of Surface Light Fields[C]// SIGGRAPH’2002.San Antonio:ACM SIGGRAPH,2002: 447-456.

[5]李金奎,郭立,池凌鸿,等. 一种分层置信传播立体匹配并行算法[J].通信技术,2012,45(07):57-61.

[6]LI Hongyu.Summarization of Program Development in Multi-core Environment[J].Computer and Information Science,2009,1(03):135-139.

[7]PAOLIERI M, QUINONES E, CAZORLA F J, et al.A Software-Pipelined Approach to Multicore Execution of Timing Predictable Multi-Threaded Hard Real-Time Tasks[C]//14th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing.Newport Beach, CA:IEEE Confernce Publications,2011:233-240.

[8]多核系列教材编写组编著.多核程序设计[M].北京:清华大学出版社,2007.

[9]REN G,CHEN G.A Parallel Processing of View-Dependent Visual Hull Texture Mapping[C]//2011 International Conference on Virtual Reality and Visualization.[s.l.]:VRV,2011:225-230.

[10]张贤达.矩阵分析与应用[M].清华:清华大学出版社,2006.

[11]王蓟翔,张扬.基于矩阵分解的压缩感知算法研究[J].通信技术,2011,44(06):138-140.