, 崔新宇1, 王艇2, 李晓妮11. 吉林大学 通信工程学院, 吉林 长春 130022;
2. 淮安信息职业技术学院 电子工程学院, 江苏 淮安 223003
收稿日期：2016-04-20
基金项目：吉林省科技发展计划与国际科技合作项目(20140414013GH)；吉林省教育厅“十三五”科学技术项目(吉教科合字[2016]第427号)；国家自然科学基金资助项目(51171041)。
作者简介：桑爱军(1973-)，女，山东莱州人，吉林大学教授。
摘要：为了大幅降低多维数据在计算上所消耗的时间, 提高计算速度, 在2M维矢量矩阵DCT(2M-VMDCT)整数变换理论的基础上, 提出了将其进行并行处理的方法, 增大时间优越性.首先介绍了2M维矢量整数变换核矩阵的推导过程; 其次, 将这种多维整数变换算法应用到多视角视频的压缩编码中, 并与多维矢量离散余弦浮点变换进行能量集中性比较; 最后, 引入多核并行处理的思想, 进一步提高处理速度.仿真结果表明, 2M-VMDCT整数变换有着非常优越的能量集中性, 将其并行实现能使运算效率大幅提高.
关键词：2M维矢量矩阵并行DCT整数变换压缩编码
2M-dimensional Vector Matrix DCT Integer Transform and Parallel Implementation
SANG Ai-jun1
, CUI Xin-yu1, WANG Ting2, LI Xiao-ni11. College of Telecommunication Engineering, Jilin University, Changchun 130022, China;
2. College of Electronic Engineering, Huai'an College of Information Technology, Huai'an 223003, China
Corresponding author: SANG Ai-jun, professor, E-mail: sangaj@jlu.edu.cn
Abstract: In order to improve the efficiency of multi-dimensional data processing operations and reduce the computing time, a 2M-dimensional vector matrix DCT(2M-VMDCT) integer transform parallel processing method is presented, according to the 2M-dimensional vector matrix DCT integer transform theory. Firstly, the 2M-dimensional vector integer transform core matrix is introduced; Then, 2M-dimensional vector matrix integer DCT transform is applied to the video compression coding, and compared with the energy concentration of the multi-dimensional discrete cosine floating-point transform; Finally, by introducing the idea of multi-core parallel processing, the processing speed is improved. The simulation results show that 2M-dimensional vector matrix DCT integer transform has a better energy concentration and the parallel implementation improves its operation efficiency significantly.
Key Words: 2M-dimensional vector matrixparallelDCTinteger transformcompression coding
在科技飞速发展的今天, 对多媒体技术以及网络技术的要求越来越高, 其中需要处理的视频与图像数据存储量相应也变得巨大.因此, 各国学者将研究重点放在了保持视频[1-2]图像清晰度和降低存储量等方面上.对于上述两个问题, 主要的解决办法就是利用变换压缩编码, 目前大部分应用的是DCT压缩编码.
KLT(Karhunen-Loeve-transform)一直被认为是最佳变换, 但由于它自身一些局限, 使其应用范围受到了限制.而DCT是最接近KLT的准最佳变换, 它在传输时的抗干扰能力非常强, 但它相比其他算法数据量大, 每一个子块中要处理的数据要求相对平缓, 变换数据需要是二维的.这就要求多维数据在处理前需要先降低维度, 使得计算的复杂度相对提高, 增加运算时间.经2M-VMDCT整数变换后, 核矩阵中求出的数值全是整数, 且能量够集中, 同时降低了变换前后的精度误差, 在变换中可以利用移位和加法运算替代矩阵乘法运算, 从而提高运算速度, 因此本文选择用2M维矢量DCT整数变换并对其进行并行处理.
如今有了多核化的概念, 数据或任务能够并行处理[3-4], 大大提高了计算机处理问题的性能.针对上述处理速度较慢的问题, 本文应用一个多核化的平台来处理2M维DCT变换的并行运算.由于在处理多维矢量矩阵[5]的数据时, 需要固定在每一个分块内, 所以可实现并行, 本文提出了对多维数据运用并行处理的解决办法, 同时研究了并行处理时对于子块的选取.本文的实验仿真平台为OpenCL编程平台.经过实验仿真, 证实了本文所提并行处理算法是能够实现的, 并且处理速度优于串行.
1 多维矢量矩阵变换理论1.1 多维矢量矩阵定义F上的M×N的数据排列(ai1i2)称为二维矩阵, 其全体元素的集合记作MM×N, F上的K1×K2×…×Kr多维数据排列表(aK1×K2×…×Kr)称为多维矩阵, 其全体组成的集合记为MK1×K2×…×Kr.如果将多维矩阵的维数分为两组, 分别用两个矢量来表示, 例如M(I1×I2×…×Im)×(J1×J2×…×Jn), 将其简记为MΙJ, 其中I, J均为矢量, I=(I1, I2, …, Im), J=(J1, J2, …, Jn), 则称多维矩阵M为维数按照矢量I, J表示的多维矢量矩阵, 简称多维矢量矩阵[5].
1.2 2M维矢量DCT浮点与整数变换核矩阵整数变换公式是由浮点变换公式推导而来, 这里先定义2M-VMDCT几个参数:CIJ=(cu1u2…uMv1v2…vM).其中I=(u1, u2, …, uM), J=(v1, v2, …, vM).
则浮点型的变换核矩阵可以表示为
 | (1) |
 |
 | (2) |
 | (3) |
1.3 能量集中性图像在经DCT变换后的能量会尽量聚集在少数几个系数上, 可以很好地去除各个像素间的关联[6-8], 提高量化后进行编码过程中的压缩效率.而DCT的整数变换也是要尽可能地将能量集中.能量集中率(EPE)用来衡量能量集中性的好坏, 现将EPE定义为
 | (4) |
2 多视角视频分块与重组多视角视频源在进行DCT变换编码之前, 要先分块和重组, 然后进行后续的扫描、量化等过程, 提高压缩比, 最后将编码后的数据进行传输, 接收端进行对应的相反过程[9-11].
2.1 多视角视频分块一个格式的视频进行DCT变换前要对其分块处理, 分别提取出每一帧的Y, U, V三个分量, 并在Y, U, V块上分别扫描出4×4×4三维数据块亦或是8×8×8大小的三维数据子块.图 1为选取大小的分块方法.
图 1(Fig. 1)
 | 图 1 视频整体分块方法Fig.1 Video overall block method |
2.2 多视角视频重组多视角视频由多台摄像机同时拍摄, 得到的视频组是从不同角度拍摄到的画面, 与单一视角视频的拍摄方法不同.不同的视角拍摄的画面在同一时刻互相之间相关性极强, 为了充分利用这种极强的相关性, 需在变换前对每一组拍摄的数据先分块再用另一种方法组合, 组合方法如图 2所示.
图 2(Fig. 2)
 | 图 2 多视角视频重组示意图Fig.2 Multi-view video block recombined diagram |
图 2仅为Y分量的重组方法示意图, U，V分量与其原理相同.每一个视角按4×4×4大小进行分块, 再选取4个视角, 取每个视角的第1帧, 按1到4顺序排列, 接着取第2帧, 以此类推到第4帧, 即为图 2中重组后的4×4×4×4的四维子块.
按4×4×4×4分块重组后的数据可以进行DCT整数变换.随着计算机的不断发展, 计算时可以实现并行处理, 将闲置的CPU和GPU利用起来, 加快处理速度.因此, 本文选用在OpenCL(open computing language)平台上的并行算法来实现对数据的运算.
3 并行实现本文的并行算法主要是在OpenCL编译平台实现.OpenCL拥有比其他并行处理平台突出的优势, 其结构简单, 可连接多个处理器, 程序移植性强且适合异构的多样化平台.
将并行处理应用到2M-VMDCT整数变换中, 首先视频图像在经过分块处理后, 每个块之间是独立的, 所以适合作并行处理.将分块后的每一块数据都输入到OpenCL编译体系中, 然后根据CPU或GPU中的空闲处理单元的个数来决定要处理多少个数据块, 并对数据块同时进行DCT计算, 这就是并行处理.注意在并行处理时应该先进行Y′=CX的运算, 得到Y′的值, 在完成全部运算后才可以计算Y=Y′CT, 因为第二个运算要用到第一个运算的结果.以上就是DCT变换的并行实现方法.
4 仿真实验与结果4.1 整数与浮点变换对比为了验证DCT浮点变换与整数变换的操作算子的近似性, 本文维度选取的是四维, 块大小为4×4×4×4, 即4个像素长, 4个像素宽, 连续4帧图像以及4个视角.数值选取的是100~150之间的随机数, 分别进行了整数变换和浮点型变换.通过对比, 可以看到整数DCT变换是有效的, 与浮点变换误差极小.由于四维数据具有一定的特殊性, 所以表 1仅显示变换的部分数据.
表 1(Table 1)
 表 1 整数变换和浮点变换对比Table 1 Comparison of integer transform and floating point transform
| 表 1 整数变换和浮点变换对比 Table 1 Comparison of integer transform and floating point transform | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
通过表 1的数据, 可以看出在做了DCT整数变换后, 四维数据的能量主要集中在前几个数据上, 后面的数据都在0上下浮动, 这种特性有利于对其进行压缩编码.
为了进一步验证整数变换的能量集中性与浮点变换的相似性, 对不同数据进行了两种算法的比较, 验证了整数变换可以代替浮点变换来处理视频.表 2即为两者EPE值的对比结果.
表 2(Table 2)
表 2 EPE值比较Table 2 Comparison of EPE value
| 表 2 EPE值比较 Table 2 Comparison of EPE value |
从表 2的数据对比分析可以看出, 整型与浮点型的能量集中性可以认为几乎没有区别, 所以可以直接利用整型DCT对视频数据做变换, 不影响变换效果, 仅取前2个数据时, 能量集中率EPE值就已经高达98.67%, 具有非常好的集中效果.
4.2 并行实现通过上节的仿真实验结果可以看出, 2M维矢量DCT整数变换具有可行性, 且比浮点型变换具有更多的优势, 因此可以代替浮点型变换.所要处理的数据经2M维矢量DCT整数变换后, 块与块之间是相互独立的.而且现在的计算机都具备多核处理器, 这让实现并行DCT变换的想法成为可能, 同时也将大大减少运行时间, 提升变换效率.实验同样选取4×4×4×4的子块, 视频选取512×384标准视频图像.表 3为选取不同块数时, 串行和并行分别运行的时间.
表 3(Table 3)
表 3 串行和并行处理的时间Table 3 Time of serial and parallel processing
| 表 3 串行和并行处理的时间 Table 3 Time of serial and parallel processing | |||||||||||||||||||||||||||||||||||||||||||||||||||||||
从表 3可以看出, 当处理块数的数量很小时, 并行运算的总时间是远大于内核时间的.当块数逐渐增多时, 二者的运行时间比较接近.原因是当需要运算的数据fn很小时, 大部分时间都浪费在初始化程序、内存以及线程开销上, 而用于真正计算的时间非常少, 因此, 串并行所用时间非常接近, 上述这种处理少量数据的情况会干扰CPU大规模并行处理性能.数据量不断攀升时, 用于计算数据的时间开始增加, CPU的运算效率开始提高.当块数为1时, 串行与并行各自所花时间相差不多, 在数据块上升时, 并行的运算总时间有明显优势.当数据块上升到256时, 计算机CPU的并行运算性能达到最大化, 超过串行的15倍以上.当数据块超过256甚至更大时, CPU并行运算效率有所下降.原因是当数据量过大时, 存储器和计算单元受到限制, 导致数据拥塞, 因此在运行时, 所有数据不能同时完全被执行, 而是要进行排队等待执行, 所以并行运算的速度相对有所下降.为了更加清晰看出并行处理时所说的现象, 将表 3图示化如图 3所示.
图 3(Fig. 3)
 | 图 3 串行与并行时间比值Fig.3 Serial and parallel time ratio |
从图 3中曲线走势可以看出, 数据块达到256时, 比值达到最高点, 因此, 本文所提的并行实现是可行的, 且处理性能是串行计算的十多倍.将来着重学习和研究如何提高和优化并行运算的性能是有必要的.在OpenCL程序中很重要的一个因素是精度, 本文实验中采用的是单精度.多精度的实现需要根据不同生产厂家根据不同要求设计进行选择.
5 结论1) 验证了DCT整数变换的性能较浮点型更为优越, 并且验证了其能量集中在少数数据中, 实验数据表明, 整数变换的能量集中性效果仍然非常好, 与浮点型相似.
2) 在OpenCL编程平台上验证了2M维整数DCT变换并行运算的可行性, 通过对两视角标准视频的并行处理记录了变换的并行运算时间.2M维数据并行处理是可行的, 且速度大幅提升.若经过适当的算法优化或者设备改进将会远远优于串行运算.
参考文献
| [1] | 冯桂, 黄君婷. 多视点视频编码中宏块复杂度的研究[J].信号处理, 2015, 31(1): 73–79. ( Feng Gui, Huang Jun-ting. Research on macro blocks complexity in multi-view video encoding[J].Journal of Signal Processing, 2015, 31(1): 73–79.) |
| [2] | Kim H, Rhee C E, Lee H J. A low-power video recording system with multiple operation modes for H.264 and light-weight compression[J].IEEE Transactions on Multimedia, 2016, 18(4): 603–613.DOI:10.1109/TMM.2016.2525861 |
| [3] | Alvaro-Fernández J, Dolores-Moreno M. A block size optimization algorithm for parallel image processing[J].IEEE International Conference, 2014, 7: 138–144. |
| [4] | Chen S Y, Lai C F, Hwang R H, et al. A multimedia parallel processing approach on GPU map reduce framework[J].IEEE International Conference, 2014, 7: 154–159. |
| [5] | 吴杨. 基于多维矢量矩阵的DCT快速算法的研究[D]. 长春: 吉林大学, 2012. ( Wu Yang.Research of fast discrete cosine transform algorithm based on multi-dimensional vector matrix[D]. Changchun:Jilin University, 2012.http://cdmd.cnki.com.cn/Article/CDMD-10183-1012366462.htm) |
| [6] | Qin J, Liu L, Zhang Z X, et al. Compressive sequential learning for action similarity labeling[J].IEEE Transactions on Image Processing, 2016, 25(2): 756–769.DOI:10.1109/TIP.2015.2508600 |
| [7] | Daribo I, Florencio D, Cheung G. Arbitrarily shaped motion prediction for depth video compression using arithmetic edge coding[J].IEEE Transactions on Image Processing, 2014, 23(11): 4696–4708.DOI:10.1109/TIP.2014.2353817 |
| [8] | Sujatha K, Rao P V N, Rao A A, et al.Multicore parallel processing concepts for effective sorting and searching[C]// IEEE Conference Publications.Cuntur, 2015:162-166. |
| [9] | 贺江, 蒲宇亮, 李海波, 等. 一种基于OpenCL的高能效并行KNN算法及其GPU验证[J].电子技术应用, 2016, 42(2): 14–16. ( He Jiang, Pu Yu-liang, Li Hai-bo, et al. A energy efficient parallel KNN algorithm evaluated on GPU using OpenCL[J].Application of Electronic Technique, 2016, 42(2): 14–16.) |
| [10] | Stone J E, Gohara D, Guochun S. OpenCL a parallel programming standard for heterogeneous computing systems[J].Computing in Science & Engineering, 2010, 3(12): 66–73. |
| [11] | Kim C G, Choi Y S. A high performance parallel DCT with OpenCL on heterogeneous computing environment[J].Multimedia Tools and Applications, 2013, 2(64): 475–489. |
