2<i>M</i>维矢量矩阵DCT整数变换及并行实现

引用本文 [复制中英文]

桑爱军, 崔新宇, 王艇, 李晓妮. 2M维矢量矩阵DCT整数变换及并行实现[J]. 东北大学学报:自然科学版, 2017, 38(11): 1543-1547.

SANG Ai-jun, CUI Xin-yu, WANG Ting, LI Xiao-ni. 2M-dimensional Vector Matrix DCT Integer Transform and Parallel Implementation[J]. Journal of Northeastern University Nature Science, 2017, 38(11): 1543-1547. DOI: 10.12068/j.issn.1005-3026.2017.11.006.

[复制英文]

基金项目

吉林省科技发展计划与国际科技合作项目(20140414013GH)；吉林省教育厅“十三五”科学技术项目(吉教科合字[2016]第427号)；国家自然科学基金资助项目(51171041)

作者简介

桑爱军(1973-)，女，山东莱州人，吉林大学教授。

文章历史

收稿日期：2016-04-20

Contents Abstract Full text Figures/Tables PDF

2M维矢量矩阵DCT整数变换及并行实现

桑爱军¹, 崔新宇¹, 王艇², 李晓妮¹

1. 吉林大学通信工程学院, 吉林长春 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-jun¹, CUI Xin-yu¹, WANG Ting², LI Xiao-ni¹

1. 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 matrix parallel DCT integer transform compression 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的数据排列(a_i₁i₂)称为二维矩阵, 其全体元素的集合记作M_M×N, F上的K₁×K₂×…×K_r多维数据排列表(a_{K₁×K₂×…×K_r})称为多维矩阵, 其全体组成的集合记为M_{K₁×K₂×…×K_r}.如果将多维矩阵的维数分为两组, 分别用两个矢量来表示, 例如M_{(I₁×I₂×…×I_m)×(J₁×J₂×…×J_n)}, 将其简记为M_ΙJ, 其中I, J均为矢量, I=(I₁, I₂, …, I_m), J=(J₁, J₂, …, J_n), 则称多维矩阵M为维数按照矢量I, J表示的多维矢量矩阵, 简称多维矢量矩阵^[5].

1.2 2M维矢量DCT浮点与整数变换核矩阵

整数变换公式是由浮点变换公式推导而来, 这里先定义2M-VMDCT几个参数:C_IJ=(c_{u₁u₂…u_Mv₁v₂…v_M}).其中I=(u₁, u₂, …, u_M), J=(v₁, v₂, …, v_M).

则浮点型的变换核矩阵可以表示为

(1)

其中,

将式(1)变形处理可导出整数变换的变换核:

(2)

将式(2)与式(1)对比可以看出, 浮点型核矩阵与构造公式的关系:

(3)

因此, 在构造2M-VMDCT整数变换核矩阵前, 需先求出c_u₁v₁, c_u₂v₂, …, c_{u_Mv_M}的值, 这些值便是二维4阶或二维8阶的核矩阵中的系数, 因此利用前面所述的推导过程可求出2M维整数变换核矩阵的C_2M.

1.3 能量集中性

图像在经DCT变换后的能量会尽量聚集在少数几个系数上, 可以很好地去除各个像素间的关联^[6-8], 提高量化后进行编码过程中的压缩效率.而DCT的整数变换也是要尽可能地将能量集中.能量集中率(EPE)用来衡量能量集中性的好坏, 现将EPE定义为

(4)

式中, 前M₀个系数占总的M个变换系数能量的百分比.利用EPE值的大小就可以直观地检验DCT整数变换所具有的能量集中性能.

2 多视角视频分块与重组

多视角视频源在进行DCT变换编码之前, 要先分块和重组, 然后进行后续的扫描、量化等过程, 提高压缩比, 最后将编码后的数据进行传输, 接收端进行对应的相反过程^[9-11].

2.1 多视角视频分块

一个格式的视频进行DCT变换前要对其分块处理, 分别提取出每一帧的Y, U, V三个分量, 并在Y, U, V块上分别扫描出4×4×4三维数据块亦或是8×8×8大小的三维数据子块.图 1为选取大小的分块方法.

图 1 视频整体分块方法 Fig.1 Video overall block method

2.2 多视角视频重组

多视角视频由多台摄像机同时拍摄, 得到的视频组是从不同角度拍摄到的画面, 与单一视角视频的拍摄方法不同.不同的视角拍摄的画面在同一时刻互相之间相关性极强, 为了充分利用这种极强的相关性, 需在变换前对每一组拍摄的数据先分块再用另一种方法组合, 组合方法如图 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′C^T, 因为第二个运算要用到第一个运算的结果.以上就是DCT变换的并行实现方法.

4 仿真实验与结果 4.1 整数与浮点变换对比

为了验证DCT浮点变换与整数变换的操作算子的近似性, 本文维度选取的是四维, 块大小为4×4×4×4, 即4个像素长, 4个像素宽, 连续4帧图像以及4个视角.数值选取的是100~150之间的随机数, 分别进行了整数变换和浮点型变换.通过对比, 可以看到整数DCT变换是有效的, 与浮点变换误差极小.由于四维数据具有一定的特殊性, 所以表 1仅显示变换的部分数据.

表 1 整数变换和浮点变换对比 Table 1 Comparison of integer transform and floating point transform

整数变换				浮点变换				两者变换误差
2 008.19	2.65	-17.94	-17.55	2008.19	1.40	-17.94	-17.69	0.0	-1.25	0.0	-0.14
-9.49	-7.05	-3.64	8.10	-8.50	-6.48	-4.86	9.11	0.99	0.57	-1.22	1.01
21.69	-9.84	-3.94	16.92	21.69	-8.62	-3.94	17.57	0.0	1.22	0.0	0.65
13.64	-1.03	-17.43	7.80	14.28	-0.01	-17.13	7.23	0.64	1.02	0.3	-0.57
13.83	-11.93	9.64	0.73	13.00	-11.21	9.98	1.71	-0.83	0.72	0.34	0.98
-9.03	-25.20	6.88	16.02	-8.89	-23.68	6.75	16.90	0.14	1.52	-0.13	0.88
-12.81	15.98	-1.50	3.18	-14.76	17.15	-1.61	1.96	-1.95	1.17	-0.11	-1.22
-4.83	-15.45	7.13	21.41	-4.52	-12.18	5.61	21.38	0.31	3.27	-1.52	-0.03
4.69	-11.82	-1.19	3.08	4.69	-11.57	-1.19	3.91	0.0	0.25	0.0	0.83
11.46	-18.25	24.27	-1.25	10.58	-17.23	23.70	2.28	-0.88	1.02	-0.57	3.53
5.44	-16.09	22.06	-19.21	5.44	-17.41	22.06	-18.02	0.0	-1.32	0.0	1.19
-12.06	12.13	-7.23	32.50	-12.84	15.66	-8.94	31.48	-0.78	3.53	-1.71	-1.02
-11.27	8.35	5.02	2.68	-12.22	9.34	4.32	1.96	-0.95	0.99	-0.7	-0.72
6.43	19.10	-7.38	-32.27	6.73	18.47	-8.89	-34.61	0.3	-0.63	-1.51	-2.34
-27.95	14.55	-1.54	0.03	-26.97	13.33	-1.43	-1.15	0.98	-1.22	0.11	-1.18
-4.60	0.22	-14.50	1.93	-4.74	0.03	-14.37	2.77	-0.14	-0.19	0.13	0.84

表 1 整数变换和浮点变换对比 Table 1 Comparison of integer transform and floating point transform

通过表 1的数据, 可以看出在做了DCT整数变换后, 四维数据的能量主要集中在前几个数据上, 后面的数据都在0上下浮动, 这种特性有利于对其进行压缩编码.

为了进一步验证整数变换的能量集中性与浮点变换的相似性, 对不同数据进行了两种算法的比较, 验证了整数变换可以代替浮点变换来处理视频.表 2即为两者EPE值的对比结果.

表 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 Time of serial and parallel processing

从表 3可以看出, 当处理块数的数量很小时, 并行运算的总时间是远大于内核时间的.当块数逐渐增多时, 二者的运行时间比较接近.原因是当需要运算的数据fn很小时, 大部分时间都浪费在初始化程序、内存以及线程开销上, 而用于真正计算的时间非常少, 因此, 串并行所用时间非常接近, 上述这种处理少量数据的情况会干扰CPU大规模并行处理性能.数据量不断攀升时, 用于计算数据的时间开始增加, CPU的运算效率开始提高.当块数为1时, 串行与并行各自所花时间相差不多, 在数据块上升时, 并行的运算总时间有明显优势.当数据块上升到256时, 计算机CPU的并行运算性能达到最大化, 超过串行的15倍以上.当数据块超过256甚至更大时, CPU并行运算效率有所下降.原因是当数据量过大时, 存储器和计算单元受到限制, 导致数据拥塞, 因此在运行时, 所有数据不能同时完全被执行, 而是要进行排队等待执行, 所以并行运算的速度相对有所下降.为了更加清晰看出并行处理时所说的现象, 将表 3图示化如图 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.