可重构结构下合成视点失真变化算法并行设计与实现

蒋 林，施佳琪，李远成

（西安科技大学计算机科学与技术学院，西安 710600）

（∗通信作者电子邮箱s1007236623@163.com）

0 引言

随着数字视频技术日趋成熟和图像图形技术、计算机视觉技术的快速发展，三维（Three-dimensional，3D）视频以其真实的视觉体验受到了人们的广泛关注，但其庞大的数据量给视频的传输和存储带来了极大的压力。高效视频编码（High Efficiency Video Coding，HEVC）框架主要用于视点纹理图及深度图编码［1］，三维高效视频编码（3D High Efficiency Video Coding，3D-HEVC）是将深度图和纹理图信息用于虚拟合成视点，采用多视点+深度图（Multi-view Video plus Depth maps，MVD）的编码格式，根据数据间关系，引入帧间预测技术降低视频冗余，达到高效视频压缩的目的。

在3D-HEVC 中，编码纹理图造成的图像失真会直接导致合成的虚拟视点失真，如果仍选用标准视频编码器进行编码，视频就会存在失真。这时，该如何描述合成后图像的失真程度，对选择合适的虚拟视点合成（Virtual View Synthesis，VVS）方法有极大的帮助。图像失真程度一般采用失真值描述，合成视点失真变化（Synthesized View Distortion Change，SVDC）算法是通过计算深度图与纹理图信息，获取合成后图像的失真值［2］，即缩短SVDC 算法的执行时间，从而高效描述合成后图像失真程度。

SVDC 算法以整幅图像作为输入，随着图像尺寸的增大，SVDC 算法时间复杂度会大幅增加，失真值将难以计算［3］。文献［4］进行算法分析时，发现在失真值计算过程中:当视差矢量为0，失真值也等于0。根据此特点，采用自适应分段跳过规则视点合成方法，在SVDC 算法计算过程中，降低了计算图像失真程度的时间复杂度。

SVDC 算法以矩阵形式参与运算，运算步骤相对独立，计算过程中数据依赖性低，具有较高的并行性，适合可重构阵列处理器进行并行计算。一种典型的可重构阵列处理器系统结构如图1 所示，其中，图1（a）为可重构阵列处理器系统，由主处理器、全局指令存储器、输入/输出存储器、可重构阵列处理器和接口控制器等部分组成。主处理器通过接口控制器调度可重构阵列处理器，全局指令存储器用于存储可重构阵列处理器操作和调用指令，输入/输出存储器用于存储阵列处理器需要处理的数据，可重构阵列处理器用于完成主处理器分配的任务。

图1 可重构阵列处理器系统结构Fig.1 Architecture of reconfigurable array processor system

与通用处理器相比，可重构阵列处理器由主控制器和可重构处理单元阵列组成。主控制器控制整个结构执行，可重构处理单元阵列由多个处理单元（Process Element，PE）构成，每个PE 包含算术逻辑单元（Arithmetic Logical Unit，ALU）、寄存器、存储器，根据配置不同PE 可以执行常见操作（如加法、减法、与、或、非等）。在编译方式上，与通用编译为单一目标处理器的汇编指令不同，可重构编译通过软硬件划分，将划分结果分别生成主控制器的控制码以及配置阵列处理器上的配置信息。此外，可重构阵列处理的执行方式是通过主处理器将任务下发给可重构阵列处理器执行，采用主控制器选择片上配置存储器中的信息，将信息下发给处理簇（Process Element Group，PEG）执行，每个簇再通过片上配置存储器将存储的可重构配置信息［5］分配到PE中进行运算。

综上所述，本文基于可重构阵列结构（基于现场可编程逻辑门阵列（Field Programmable Gate Array，FPGA）实现的BEE4 平台），设计并实现了一种混合粒度SVDC 算法，以有效缩短SVDC 算法执行时间。通过分析虚拟视点合成过程中深度图与纹理图的关系，利用失真值计算过程中图像失真值等于像素点失真值累加的特点，发挥可重构阵列结构优势，设计并实现了SVDC算法并行化映射方法。

1 SVDC算法的并行性分析

SVDC算法是计算虚拟视点合成失真值的方法，但是随着图像尺寸的增大，将难以在有限时间内计算虚拟视点合成失真值。因此，将SVDC 算法分为三部分:初始化、重渲染和失真值计算，其计算过程如图2所示。

图2 SVDC算法流程Fig.2 Flow chart of SVDC algorithm

由图2 可以看出，SVDC 算法三部分的具体内容如下:1）初始化部分:已编码的深度图像D'与已编码纹理图像T'。2）重渲染部分:已编码的深度图像D"与未编码纹理图像T"，分别进行虚拟视点合成，用V'和V"表示，然后将原始纹理图T与原始深度图D合成参考视点V。3）失真值计算:V与V'的差值平方和SSD'和V与V"的差值平方和SSD"的差值表示为虚拟视点合成的失真值。

1.1 SVDC算法计算阶段确定

由图2 中SVDC 的计算过程，可得SVDC 算法主要有两个模块:虚拟视点合成和失真值计算，其计算阶段划分如图3 所示。图3 中:最左侧为将原始图像分割成大小是8×8 的待处理块，通过虚拟视点合成获得合成后的图像；失真值计算获得合成后的失真值。

图3 SVDC算法计算阶段示意图Fig.3 Schematic diagram of SVDC algorithm calculation stages

由于SVDC 算法计算模式不同，所以，在可重构阵列结构处理器上，增加配置信息去映射不同的PEG。

1.2 虚拟视点合成并行分析

虚拟视点合成作为SVDC 算法的第一个模块，包括三个部分:边界掩模、3D warping 和空洞填充。这三个部分的输入单位是像素块，本文使用的像素块大小是m×m，具体内容如下:

1）边界掩模:依据像素点的纹理图和深度图信息判断物体边界是否遮蔽以及遮蔽后的处理方法。

2）3D warping:依据深度图信息与纹理图信息的叠加找到合成后视点的映射规则。在执行边界掩膜和3D warping 时，需要对整块区域进行处理。

3）空洞填充:空洞是前景参照物遮挡到后景区域产生的，使得合成视频较原景象出现较大的偏差，一般通过低通滤波器对深度图进行预处理减小空洞区域，在视点合成过程中需要空洞填充以保证视频图像的准确性。

虚拟视点合成的三个部分，虽然在自身内部计算时不能并行化，但在进行虚拟视点合成时都相对独立，可以采用流水线与重构方式进行加速计算［6］。

1.3 失真值计算并行分析

SVDC算法的第二个模块是失真值计算，失真值计算主要分为图像失真值计算和像素点失真值计算，计算已编码区和未编码区分别与参考图平方和的差值，如式（1）所示。

其中:I为图像处理块，ΔD为I的失真值；为I的初始化纹理图为I的重渲染纹理图为I的参考纹理图；()x，y为I的像素点坐标。

1.3.1 图像失真值计算分析——任务级

失真值计算的流程如图4 所示，其中，Dx1是第一个循环读取初始化图像与参考图像像素值E1、E2后，差值平方的累加值；Dx2是第二个循环读取重渲染图像与参考图像像素值E3、E4后，差值平方的累加值。

图4 失真值计算流程Fig.4 Flow chart of distortion value calculation

分析这两个循环可得失真值计算是整个区域块内部中所有像素点失真值的累加，两个循环中每次循环都相对独立且具有相同的计算过程［7］，因此，失真值计算具备并行性。

1.3.2 像素点失真值计算分析——指令级

由1.3.1 节可知，图像失真值计算是像素点失真值计算的累加。像素点失真值计算如图5 所示，图中a1、a2、a3分别是初始化纹理图、参考纹理图、重渲染纹理图的像素点。

图5 像素点失真值计算Fig.5 Calculation of pixel distortion value

整个计算过程分解为两个部分:1）A，计算a1与a2差值平方a6的过程；2）B，计算a3与a2差值平方a7的过程。将A、B 两部分的结果相减得到最终结果，可得像素点的失真值，两部分计算过程一致，数据依赖性低，具有并行性［8］。

综上所述，SVDC 算法的优化主要分为两个部分:1）虚拟视点合成部分采用流水线方式加速；2）失真值计算部分采用两级（任务级、指令级）划分加速。

2 混合粒度划分方法

首先，提出了混合粒度划分方法的基本思想。然后，根据SVDC 算法的特点，对虚拟视点合成部分，设计流水线划分策略缩短虚拟视点合成部分时间；对失真值计算部分，比较像素点以及计算过程对其执行时间的加速程度。最后，选择合适的方法缩短SVDC 算法的执行时间，并给出SVDC 算法的重构配置信息。

2.1 混合粒度划分的基本思想

混合粒度划分为两个部分:虚拟视点合成和失真值计算。虚拟视点合成采用流水线作业的方式加速。失真值计算采用两级划分加速:任务级——像素块与像素点的依赖关系；指令级——像素点内部计算过程中的依赖关系。

混合粒度划分方法，通过虚拟视点合成得到合成图像，计算失真值。并行化过程使用addparallel 方法实现。通过判断singal状态选择并行或同步处理，若为false 则表示计算未结束需要同步等待；反之，需要并行计算，其具体计算步骤如下。

其中，通过VVS 方法实现虚拟视点合成，失真值计算过程中，通过imagedivide方法实现任务级划分策略，即将像素块均匀分配给指定数目的处理单元运算；通过get_Set_SVDC 方法实现指令级划分策略，将任务级划分的结果作为输入，对每个结果采用指令级方法，获取失真值，将失真值结果累加，即可获得图像的失真情况。

2.2 虚拟视点合成划分

根据1.2 节分析可知，虚拟视点合成分为边界掩模、3D warping 和空洞填充三个部分。由于这三个部分各自不能并行，所以使用如图6所示的流水线方式进行加速。

图6 虚拟视点合成时空间流水线作业Fig.6 Spatio-temporal pipelining of virtual view synthesis

图6 中，将深度图和纹理图像素块通过边界掩模、3D warping 和空洞填充这三个部分进行虚拟视点合成。当第一个像素块边界掩膜完成后，第二个像素块开始边界掩膜。因此，采用流水线方式能够缩短虚拟视点合成阶段的执行时间。虚拟视点合成采用流水线方式加速的设计方法，以边界掩膜为例，具体算法如下。

其中addparallel（“boder”，1）询问处理单元是否处于freedom状态，对于繁忙状态则需要等待，进行线程同步；反之，直接运算。3D warping和空洞填充使用相同的判断方法。

2.3 失真值计算基础划分方法性能对比

根据1.3 节对失真值计算的分析可得两类划分策略:1）按照任务级划分，如1.3.1 节所述，将像素块中像素点单独计算，累加求和；2）按照指令级划分，如1.3.2 节所述，使用两个处理单元计算初始化失真和重渲染失真结果，两者相减，累加求和。两种划分方法的性能对比如表1所示。

表1 SVDC失真值计算方法性能对比Tab.1 Performance comparison of SVDC distortion value calculation methods

一方面，从表1 中的数据中可得，当处理问题规模不同（像素块大小不同）时，划分方法的计算性能提升也不同。问题规模较大时，任务级划分方法的性能提升较好；而指令级划分方法对单一点有更好的性能提升。

另一方面，分析表1 中的数据可知，任务级划分方法能合理使用有限的资源，指令级划分对单一点加速性能更好。但是从1.3 节可知，图像的失真值是像素点失真值的累加，然而指令级划分是对像素点失真值计算的优化。所以，在不考虑处理单元数目时，将任务级和指令级划分方法混合能够得到更优的性能［9］。而处理单元数目有限时，任务级划分方法能够得到更好的性能提升。

2.4 像素块-像素点划分（任务级）

在像素块-像素点划分中，由失真值计算式（1）分析可得，像素块内失真值等于像素点失真值的累加。对失真值计算分析可得，图像失真值等于像素块失真值之和，即图像的失真值等于像素点失真值的累加，由此提出任务级方法［10］。

如图7 所示，以4 个PE 为例，首先PE00 读取的是初始化纹理图St、重渲染纹理图、参考纹理图Stf中的第0号像素值，而PE01、PE02、PE03 分别读取的是三幅图中第1、2、3 号像素值。然后读取4×当前PE 已读取像素点数（如:a为PE00 已读取像素点数），最后将计算结果在PE03处累加得到失真值。

图7 像素块-像素点划分框图Fig.7 Block diagram of pixel block-pixel point division

像素块-像素点划分方法是将像素块均匀分配到每个处理单元计算失真值，具体算法如下。

通过计算像素点与处理单元的模值，即通过i取process_num模分配像素点到对应的处理单元计算失真值，并将分配后的点写入process_point_set中进行失真值计算。

2.5 像素点-计算过程划分（指令级）

像素点-计算过程划分是将每个像素点失真值计算过程进行划分。由1.3 节对失真值计算的分析可得每一个像素点都具有相同的计算过程，可以并行化。因此，将失真值计算的式（1）分解为式（2），整个计算式分为三个部分。

式（2）中，前半部分是初始化像素点差值的平方，后半部分是重渲染像素点差值的平方。该方法能保证负载上的均衡，提升整体计算性能［11］，像素点内部计算过程的任务执行如图8所示。图8中，S1代表计算初始化像素与参考图像素点差值的平方，S2代表计算重渲染像素与参考图差值的平方，将两者的计算结果通过PE30相减，得到失真值。

图8 像素点-计算过程划分框图Fig.8 Block diagram of pixel-calculation division

像素点-计算过程的划分中，通过addparallel 方法将计算初始化和重渲染像素点差值平方进行并行化处理。通过addparallel（“ST1”，1）、addparallel（“ST2”，2）判断计算完成情况，如果完成，则将结果相减得到最终失真值；反之等待，具体步骤如下。

2.6 重构信息配置

重构配置信息执行示意图如图9 所示。首先，通过分析SVDC 算法与可重构阵列结构的关系得到SVDC 算法的配置信息:虚拟视点合成和失真值计算。然后，将配置信息载入到片上配置存储器，在可重构计算阵列执行时，载入PEG［12-13］。最后，PEG00 载入虚拟视点合成配置信息后重复执行Nt次虚拟视点合成，将每次计算结果写入PEG01，PEG01重复执行Nt次失真值计算，并将每次计算结果累加，求得图像失真值。

图9 可重构配置信息执行示意图Fig.9 Schematic diagram of reconfigurable configuration information execution

3 实验与结果分析

为了验证混合粒度划分方法的计算性能，本文基于Beecube 公司BEE4 型号的FPGA 开发板进行实验。可重构阵列处理器结构是由1 024个PE邻接互连成的动态可编程可重构阵列结构。该阵列结构包含64个簇，每个簇包含16个PE，每个PE 包含大小为512×32 的指令存储单元、大小为512×16 的数据存储单元、12 个本地寄存器（R1～R7，R12～R15）和4个共享寄存器（RE、RS、RW、RN），各个PE 之间通过4 个共享寄存器进行数据交互。每个PE 采用load/store 模式的精简指令集计算机（Reduced Instruction Set Computer，RISC）架构，按照取指、译码、执行、写返回4 级流水线结构进行执行整个过程。

3.1 实验方案

为了验证混合粒度划分方法在阵列结构上的适用性，本文将以3D-HEVC 的参考模型HTM 作为参照［14］。依据可重构阵列结构的设计原理，在Questasim 10.1d 仿真平台上进行实验，时钟周期为20 ns，读取数据仿真时间为200 ns，合并数据仿真时间为134 ns。

针对大小为8×8 的编码单元进行仿真。测试用例分别为Balloons（1024×768）、GTFly（1920×1088）、PoznanStreet（1920×1088）、UndoDancer（1920×1088），测试用例的视点为双视点，分别对应两对深度序列。首先，采用共享存储并行编程（Open Multi-Processing，OpenMP）工具在SVDC 算法可并行的代码段中添加标记［15］。然后，使用底层虚拟机（Low Level Virtual Machine，LLVM）并行编译器执行SVDC 算法的代码。最后，由于SVDC 算法中失真值计算部分的并行性较高，采用像素点划分和本文划分的方法，分别验证处理单元数目和像素块大小对失真值计算的加速性能。

3.1.1 SVDC算法性能仿真

四个测试序列分别采用上述四类方法（本文方法、OpenMP、LLVM 和HTM），针对四个处理单元，像素块大小为8×8 的执行时间对比如图10 所示。根据阿姆达尔定律可得混合粒度划分方法的加速比约为2.11。

图10 不同平台上SVDC算法执行时间对比Fig.10 Comparison of SVDC algorithm execution time on different platforms

LLVM 与OpenMP 并行编程方法，都是采用显式并行策略:一方面通过操作系统进行调度会额外增加调度开销；另一方面采取保守方式挖掘算法并行性。本文方法是在可重构结构的基础上挖掘多粒度并行性，减少了额外开销，具有更好的并行性能。

针对不同的视频图像，经计算可得，本文方法与LLVM 并行编译方法相比计算性能提升了18.56%，与OpenMP 编程模型相比计算性能提升了21.93%。这也表明混合粒度划分方法对于SVDC算法性能提升更优，尤其序列2更为明显。

3.1.2 失真值计算性能仿真

由第1.3 节分析可得，失真值计算部分更适合并行执行。分析2.3 节可知，当处理单元有限时，任务级划分方法会获得更优的加速性能。而当处理单元数目足够时，本文方法的性能更优。

因此，实验对序列2 分别通过PE 数目（2、4、8、16、32、64、128）和像素块大小（1×1、2×2、4×4、8×8）这两个因素，设计分别使用任务级划分方法与本文的混合粒度划分方法，分析这两种方法对失真值计算部分加速性能的影响，结果如图11所示。

由图11 可以看出，在像素块大小一致、处理单元数目大于像素块大小时，本文划分方法相较像素点划分方法，加速性能有显著的提升，并且随着像素块扩大，本文划分方法在PE数目足够时，加速性能的提升依旧显著。

3.2 混合粒度划分方法性能分析

混合粒度划分方法分为两步:1）将像素块分解为若干像素点失真值计算的累加；2）将像素点内部失真值计算过程分解为A、B 两个过程。对混合粒度方法进行理论分析，得到混合粒度划分方法执行时间，进行实验验证。

假设原图为On1×n2，使用的像素块为Gm×m，则需要处理块的数目block_num=

首先，对虚拟视点合成而言，假设T1、T2、T3分别为虚拟视点合成的三个部分边界掩膜、3D warping 和空洞填充的执行时间。那么，虚拟视点合成串行算法的时间TVVS=T1+T2+T3。而采用流水线方式进行计算，结合2.2 节视点合成流水线时空图和相应的算法，得出并行算法的执行时间TVVSp=max｛T1，T2，T3｝。

其次，对失真值计算而言，设Cm×m中每个元素为像素块中每个点失真值计算的时间，则串行时间TSSD=C11+C12+…+Cmm。而对于混合粒度方法中的失真值计算，包括将像素块划分为均匀等分的像素点集划分数量num=m2/S。

根据像素点-计算过程的划分，设Cc1、Cc2分别为像素点的SSD'与SSD"计算时间，则每个像素点失真值计算的时间Tc=2×max｛Cc1，Cc2｝+t1。

因此，失真值计算并行执行时间TSSDp=num×（Tc）+m2×t2。

其中，S为可使用的核数，t1为处理单元数据合并时间，t2为像素点失真值累加时间。

最后，经理论推算本文方法的加速比为:

由上述分析可得，本文方法对于SVDC 算法的性能提升体现在:1）虚拟视点合成采用流水线方式加速；2）失真值计算采用任务级+指令级进行加速。本文方法进一步提升了算法性能的主要因素是处理器数目与问题规模的关系，只有选择合适的处理器数目，才能有效缩短算法的执行时间。

4 结语

SVDC算法是虚拟视点合成中的关键环节，而算法的执行效率对图像视点合成质量非常重要。因此，本文提出了一种在可重构结构下基于混合粒度的SVDC 算法并行化方法。该方法将算法原有的三个部分（初始化、重渲染和失真值计算）转变为两个部分:虚拟视点合成和失真值计算。其中，第一个部分虚拟视点合成采用流水线方法进行优化；第二个部分将失真值计算分为两个过程:像素块-像素点、像素点-计算过程。实验结果表明，在处理单元数目为4、像素块大小为8×8时，本文划分方法与基于LLVM 和OpenMP 的SVDC 算法相比，计算时间分别缩短了18.56%、21.93%。针对SVDC 计算过程中并行度高的失真值计算部分，通过实验得到当处理单元数目为128时，失真值计算的性能可提升55.23倍。在接下来的研究中，将把硬件结构作为侧重点，包括循环迭代过程中免数据验证、增加数据传输带宽等，都是提升算法性能的可行性方法。