李 涛, 孙 建, 王鹏博

( 1.西安邮电大学 电子工程学院, 陕西 西安 710121； 2.西安邮电大学 计算机学院， 陕西 西安 710121)

基于PAAG的OpenVX核心库函数并行化实现

李 涛1, 孙 建2, 王鹏博2

( 1.西安邮电大学 电子工程学院, 陕西 西安 710121； 2.西安邮电大学 计算机学院， 陕西 西安 710121)

针对OpenVX1.0标准中的核心库函数，在新型多态同构阵列处理器平台上实现基于该标准的Kernel函数算法的并行化。以Gaussian Filter、Color Convert、Sobel3×3等kernel函数组成的节点构造图像边缘检测的OpenVX图执行模型，将该执行模型映射到阵列机上实现了并行加速。实验结果证明，PAAG阵列机能实现高复杂度算法的并行实现，并且能获得线性增长的加速比，执行效率更高。

图像处理；OpenVX；边缘检测；多态同构阵列机；并行计算

近年来，各类计算机以及嵌入式终端电子设备已经深入到社会生活的方方面面，尽管计算机视觉[1]和图像处理技术日趋成熟，但是人们对于高质量的视觉感受，流畅的视觉画面的不断追求使得图形图像处理器[2]设计以及基于加快图像数据处理速度的计算机视觉算法优化不断面临新的挑战。

并行计算[3]是提高计算处理速度，降低处理器功耗，解决大数据量、高复杂度等算法问题的重要途径。目前，业界已提出了很多基于并行计算的面向多核和众核[4]的编程模型，推动了并行计算的应用和发展。典型的并行编程模型中，OpenMP和MPI分别适用于集中式共享内存和分布式共享内存编程模型[5]，但是对于当前GPU众核架构[5]，两者所支持的并行编程模式显得较单一。新型多态阵列处理器[6](Polymorphic Array Architecture for Graphics and Image processing，PAAG)是一种适用于图形和图像处理的高效并行的阵列机结构，它支持SIMD和MIMD等[7]多种编程模式，并且兼有可编程器件的灵活性和接近专用集成电路[8](ASIC)的处理性能，可以为实现OpenVX1.0标准[9]中核心库函数的并行化提供很好的平台。Open VX是由Khronos发布的开放的、跨平台的计算机视觉应用底层加速标准。它为计算性能优化以及计算机视觉处理的功耗减少等方面提供了有力的支持，在诸如图像、生物特征提取，智能视频监控，视觉检测，对象场景构建等方面应用广泛。

本文选取OpenVX1.0标准中的Gaussian Filter、Color Convert、Sobel3×3等kernel函数构造实现图像边缘检测应用[10-11]的各个结点，通过连接各个结点实现该应用的OpenVX图执行模型，将该图执行模型映射到PAAG阵列机上进行并行加速。

1 OpenVX中kernel函数

OpenVX计算视觉标准支持最基本的视觉函数。OpenVX中多数kernel函数是针对图像的像素级进行处理，这些kernel函数构成了一个适用于硬件加速的函数子集[9]，包含图像像素迭代处理的加权累加(Accumulate Weighted)算法；图像色系变换(Color Convert)算法；图像局部处理高斯滤波(Gaussian Filter)算法、和Sobel3×3图像滤波算法；图像位深变换(Convert Bit Depth)算法等核心库函数，具体算法描述如下。

(1)图像加权累加(Accumulate Weighted)算法。即将输入图像像素和原始图像像素分别与对应权值相乘，进行累加操作，以得到新的像素值[9]，

accum(x,y)=(1-α)×accum(x,y)+α×input(x,y)。

(2)积分图像(Integral Image)算法。计算图像积分，将该点原始像素值与其左侧和上方的像素点求和之后与其左上方的像素值作差，得到该点积分后的像素值[9]

sum(x,y)=in(x,y)+sum(x-1,y)+sum(x,y-1)-sum(x-1,y-1)。

(3)色系变换算法是将图像从一种模式转换成另一种模式，比如将现有的彩色图像转换成灰度图像。

(4)高斯滤波对已有的输入图像进行高斯卷积计算，使用的卷积矩阵[9]为

(5)Sobel3×3图像滤波算法通过Sobel卷积算子进行卷积运算求解图像沿x和y方向的梯度。

(6)图像位深变换用于改变图像像素分量在存储和显示时在内存中所占的比特数。

2 图像边缘检测的OpenVX实现

对于基于OpenVX相关应用的实现，标准中提出了基于OpenVX的图(gragh)执行模型，根据所要实现的应用功能，选取OpenVX标准中一个或多个kernel函数构造其所需要结点，将这些结点用于基于该应用的OpenVX的图执行模型。通过选取图像高斯滤波算法、图像色系变换(ColorConvert)算法、Sobel3×3图像滤波算法、图像位深变换(ConvertBitDepth)、图像像素加权累加(AccumulateWeighted)算法，构造实现图像边缘检测的基于OpenVX的图执行模型。该应用的执行流程如图1所示。

图1 图像边缘检测的OpenVX实现

在图1中，图像边缘检测基于OpenVX的图执行模型是由各节点根据其相互依赖关系串联而成的。首先对输入图像用Gaussian Filter算法构造节点进行初步线性平滑处理，消除了高斯噪声；得到处理后的图像经过色系变换转换成RGBA格式的灰度图像；使用3×3的Sobel卷积核对得到的灰度图像的x、y方向求卷积，分别得到图像x、y方向的梯度；在图像位深变换(Convert Bit Depth)中将每个得到的16位像素信息转换成8位像素信息；将x、y方向图像像素信息进行加权累加(Accumulate Weighted)得到最终处理结果。

3 并行化设计及实验结果

3.1 并行化设计

用PAAG多态阵列机仿真平台对算法进行并行处理前，使用数据并行(Data Level Parallel, DLP)和操作并行(Operation Level Parallel,OPL)方法对所有的算法进行并行化设计。数据并行以SIMD为基础，主要用于算法层的并行；操作并行[12]主要是指FPGA和ASIC类[8]的计算方法。

(1)数据并行设计

对图像进行数据并行化设计，首先进行图像数据分块[13]，即将较大的图像像素数据集分解为多个子像素数据集，在图像分块后，每个处理器又以单指令多数据(SIMD)方式对各个像素数据子集执行相同的操作，以达到对较大像素数据集进行并行处理目的。在OpenVX中像素的算术运算，逻辑运算等算法中这种方法优势明显。此外，在数据分块中，采用边界复制法、边界补零法等对图像的边界像素进行处理。边界复制法是将分块后图像子集的真实边界像素复制一份作为新的像素块的边界，将新的像素块存放到各自的共享存储中，这样在PE从共享存储中读取像素值进行计算处理的时候，尤其是在卷积等运算的时候就能保证真实图像的每个像素点都被处理；而边界补零的方法，即将所有的图像子集的真实边界外的每个点都赋值为零作为各自新的边界。对图像边缘检测中的高斯滤波算法，为实现数据并行，将图像进行分块，同时通过边界补零的方法对边界进行处理以避免后续的卷积运算中对原有像素点的处理有遗漏的情况发生。总之，对大量数据分块后进行并行数据处理，节约算法执行时间，提高计算效率。

(2)操作并行设计

针对操作并行方法，将算法分解为若干个独立执行的部分，利用中值滤波算法[14]求出每个邻域窗口的中值。采用3×3的窗口，将9个像素分成3个小组，每个小组3个像素，每次对同一组的3个像素值进行比较，取第一组的最大值，第二组的中间值和第三组的最小值，再对这3个值进行排序，排序后的中值即为9个像素的中值。该方法每次只对3个像素值进行排序，节省了处理时间和减少了内存消耗。

对于高斯滤波算法，如图2所示，在进行数据分块后，将高斯卷积核按列分别加载到PE0、PE1和PE2上，执行计算时候，按行从图像块中取3个数据加载到对应的PE中，进行乘积和加法操作。用此方法每次取9个像素值分别映射到9个PE上执行卷积操作。这样就将算法进行分解实现操作级并行。

图2 阵列处理器基本簇结构

流水线处理[15]，是实现操作并行的另一种方法，PAAG提供的PE之间的阻塞通信模式为流水线处理提供了灵活的支持，通过PAAG中的邻接通信共享存储将阵列机中的PE以Z形串联起来，将各个串行链接的节点与簇中的PE一一映射，通过邻接通信共享存储实现握手协议。例如将基于OpenVX图执行模型映射到阵列机上的PE0、PE1、PE3、PE4后，在PE0处理完首节点之前，其他PE处于阻塞状态，当该节点处理完后，将数据发送到PE1，此时PE0可以继续接收接下来的图像数据，依次类推，形成整个图像处理流水线，可提高对于多帧图像处理的效率。

根据图像边缘检测的OpenVX图执行模型中各个节点的相互依赖关系，将各处理节点一一映射到对应的PE上，实现对图像边缘检测流水线式处理。考虑到各个节点中算法的复杂度不同，为使负载达到相对平衡，对复杂度高的算法在映射时适当增加处理器个数，从而实现更高的PE利用率，节约资源，提高并行效率。优化后的图像边缘检测处理流水线如图3所示。

图3 优化后图像边缘检测流水线

3.2 实验结果

PAAG提供给了一套完整的软件仿真系统，在仿真环境中，将算法的汇编语言程序、图像数据以像素二进制的形式加载到仿真平台上，程序和数据在阵列机上完成映射后，经过编译、运行，可得到实验结果数据，以及并行处理后的图像，并在终端显示器上显示。

表1给出了图像检测基于OpenVX图执行模型的相关算法的并行化加速比结果，其中Si表示使用i个PE处理后所得到的加速比。实验后得到的图像处理结果如图4所示。

表1 图像相关算法加速比统计表

(a) 原图像

(b) 处理后的图像

图4 图像边缘检测处理结果

从表1可以看出，OpenVX核函数在PAAG并行阵列机上能基本实现线性加速，提高了算法的计算效率，由图4可以看出，PAAG上执行基于OpenVX的图像边缘检测的图执行模型之后，得到了能清晰显示图像边缘轮廓的处理后图像。

4 结束语

对国际标准组织Khronos提出的最新计算机视觉标准OpenVX1.0进行分析，并在新型多态同构阵列处理器PAAG平台上并行实现其核心库函数，构造了OpenVX的图执行模型。以图像边缘检测为应用为例，采用数据并行和操作并行相结合的并行方法，实现了该执行模型在PAAG上的映射。实验结果证明，针对高复杂度的算法，PAAG在并行实现加速方面优势明显，可实现加速比线性增长，执行效率较串行处理明显提高。

[1] 许志杰，王晶，刘颖，范九伦.计算机视觉核心技术现状与展望[J].西安邮电学院学报，2012,17(6):1-8.

[2] 韩俊刚, 刘有耀, 张晓.图形处理器的历史现状和发展趋势[J]. 西安邮电学院学报，2011,16(3):61-64.

[3] 帕切克.并行程序设计导论[M].邓倩妮，译.北京：机械工业出版社，2012:23-48.

[4] 洪春涛. 众核处理器编程模式关键技术研究[D].北京:清华大学，2011:4-13.

[5] 许牧.可重构众核流处理器体系结构关键技术研究[D].合肥：中国科学技术大学，2012:5-25.

[6] 李涛，肖灵芝.面向图形和图像处理的轻核阵列机结构[J].西安邮电学院学报，2012，17(3)：41-47.

[7] Boyd C. Data-parallel computing[J]. Queue-GPU Computing, 2008, 6(2): 30-39.

[8] 史密斯.专用集成电路[M].虞惠华，译.北京：电子工业出版社，2007:34-68.

[9] Erik Rainey,Susheel Gautam. r26495, The OpenVXTM[Provisional] Specification Version1.0[S]. USA:Khronos Vision Working Group, 2014.

[10] Gonzalaz R C,Woods R E. 数字图像处理[M].阮秋琦，阮宇智，译.北京：电子工业出版社，2011:45-77.

[11] Marr D,Hildreth E. Theory of edge detection [M].London: Proceedings of the Royal Society, 1980：187-217.

[12] 卢风顺，宋军强.CPU/GPU协同并行计算研究综述[J]. 计算机科学，2011,38(3):5-9.

[13] Kato S, Lakshmanan K, Rajkumar R，et al. TimeGraph: GPU scheduling for real-time multi-tasking environments[C]//Proceedings of the 2011 USENIX Annual Technical Conference.USA: USENIX Association,2011:2.

[14] Dong Fu-guo, Li Yi-ling. Study on fast algorithm of median filtering based on DC and ICS method[C]//Wireless Communications & Signal Processing.Nanjing:IEEE WCSP ,2009:1-5.

[15] Harshad B， Prajapati D，Sanjay K V. Analytical study of parallel and distributed image processing[C]//Image Information Processing (ICIIP) International Conference onc .Shimla: IEEE ICIIP,2011:3-5.

[责任编辑:祝剑]

Parallel implementation of kernels of OpenVX based on PAAG

LI Tao1, SUN Jian2, WANG Pengbo2

( 1.School of Electronic Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China;2.School of Computer Science, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In the view of kernel functions of OpenVX1.0 standard,this paper presents a parallel implementation method for the kernels of the standard on a new platform, Polymorphic Array Architecture for Graphics and image processing(PAAG).Meanwhile,parallel implementation of an application, Image Edge Detection based on OpenVX graph mode which is constructed by nodes,Gaussian Filter、Color Convert、Sobel3×3 and so on ,is realized in this paper.The execution mode is mapped to the array to implement the parallel acceleration. The experimental results show that, the PAAG array can realize parallel implement of highly complex algorithms,and speedup the algorithms linearly and the efficiency of the execution is higher.

image processing, OpenVX, image edge detection, polymorphic array processor, parallel computing

2014-12-16

国家自然科学基金重大项目(61136002)

李涛(1964-)，男，博士，教授，从事计算机体系结构、集成电路设计等研究。E-mail:litao@xupt.edu.cn 孙建(1988-)，男，硕士研究生，研究方向为计算机系统结构与VLSI。E-mail: sunjiansj88@163.com

10.13682/j.issn.2095-6533.2015.02.002

TP702

A

2095-6533(2015)02-0007-04