整数DCT变换（精选6篇）
整数DCT变换 篇1
AVS是我国自主制定的具有自主知识产权的第二代信源编码标准[1],是《信息技术先进音视频编码》系列标准的简称,其视频编码标准采用与 H.264类似的技术框架,包括变换、量化、熵编码、帧内预测、帧间预测、环路滤波等。由于其编码算法复杂度较高,特别是随着高清、超清视频的普及,提高编解码速度成为目前要解决的重要问题之一。整数DCT变换在AVS编码中是调用频度高且比较耗时的部分,研究它的快速实现算法有利于编码器的实时编码实现。文献[1]提出了一种AVS整数DCT变换和量化的方法,采用的较低复杂度的4x4整数变换矩阵获得较高的编码效率,但是4x4整数DCT变换的去相关性不足。因此本文采用了去相关性更强的8x8整数DCT变换,在高清应用中获得更好的压缩性能和视觉效果。文献[2]提出了一种AVS整数DCT变换的快速变换算法并在DSP上实现,采用加法和移位操作代替乘法运算降低计算复杂度获得了4倍加速比。现在计算机普遍配置了高性能的图形卡,人们已在很多领域尝试利用图形处理器的计算能力来进行高性能计算。本文研究利用GPU(Graphic Processing Unit)的并行处理能力和CUDA(Compute Unified Device Architecture)的编程框架对AVS标准中的整数DCT变换算法进行了并行实现。
1 AVS标准及其视频部分的概述
AVS标准是信息技术先进音视频编码系列标准的简称,是我国具有自主知识产权的第二代信源编码标准,该标准包括系统、视频、音频、数字版权管理等四个主要技术标准和一致性测试等支撑标准,采用当前国际主流的视频编解码方案并加入了我国自主创新的技术成果。其中AVS第二部分(AVS1-P2)为AVS系列标准中最重要的视频部分,其中融合了可变块大小的运动补偿和预测、多方向空间预测、多参考帧、8x8的整数DCT变换和相应的量化策略、1/4像素插值、运动矢量预测、扫描、环路滤波、高效的熵编码等技术。AVS视频编码框图如图1所示。
AVS视频编码标准采用了与MPEG-2相似的基于块匹配的编码框架,使用更加复杂的运动估计、熵编码技术,使得压缩性能是MPEG-2的2-4倍,与同期制定的国际标准H.264/AVC相当。算法复杂度的提高加大了实现难度,图1中整数DCT变换在AVS视频编码中耗时较多,而且具有较高的并行性,所以可采用GPU来分担编码中整数DCT变换的计算任务,从而加快编码的速度。
2 GPU硬件架构和CUDA编程模型
近年来,图形处理器(GPU)取得了飞速的发展。典型的如NVIDIA公司推出的Tesla系列的GPU。为了实现基于GPU的通用计算,先后出现了若干编程模型如斯坦福大学的Brook,以及后来的Brook+和OpenCL。
但最具代表性的是NVIDIA公司推出的统一计算设备架构(CUDA),CUDA是一种将GPU作为数据并行计算设备的软硬件体系。与以往的GPU相比,支持CUDA的GPU在架构上有了显著地改进,这两项改进使CUDA架构更加适用于GPU通用计算。一是采用了统一处理架构,可以更有效地利用过去分布在顶点渲染器和像素渲染器的计算资源;二是引入了片内共享存储器,支持随机写入和线程间通信。
GPU的硬件架构如图2所示,上层是SPA(Scalable Streaming Processor Array)部分,下层是存储系统部分。两部分由一个片上互联网络连接,流处理器阵列和存储器系统都可以独立扩展,以实现高低不同的性能分级。如改变TPC 单元就改变了GPU 的计算核心数量,改变存储控制单元就改变了显卡的显存大小[3]。
在CUDA编程模型中[4],引入了主机、设备的概念。将CPU作为主机(Host),GPU作为设备(Device)。一个系统可以存在一个主机和若干个设备。一个完整的CUDA程序包括运行在主机上的部分和运行在设备上的部分,这两部分协同合作。CPU 负责逻辑性强的事物处理和串行计算,GPU则专注于执行高度线程化的并行处理任务。运行在设备端的CUDA并行计算函数称为“kernel”,是算法中运行在GPU上的并行部分。如图3所示,一个Kernel存在两个层次的并行,即Grid中Block间的并行和Block中Thread间并行,每个线程执行一次Kernel函数。
3 AVS整数DCT变换并行算法设计
离散余弦变换DCT(Discrete Cosine Transform)技术[5]是一种在数据压缩中常用的变换编码方法,它把正交矩阵的时序信号变为频率信号,是一种近似于傅立叶变换的正交变换。图像编码中所采用的编码技术可以去除图像信号在变换域上的相关性,比起直接对图像进行编码而言码率大大降低了。AVS中的DCT变换和传统的DCT变换最大的不同就是采用了整数正交变换。AVS 整数DCT变换采用的最小预测是8x8的块,变换矩阵如图4所示。
编码的本质就是对输入图像进行分块,将图像划分成若干个8x8的像素子图,然后对每个子图作同样地DCT变换。DCT变换的实质就是三个矩阵的相乘,如表达式F = T*f*TT,其中F是经过变换后的系数矩阵,T是图4的常数矩阵,TT是T的转置矩阵,f是8x8的像素矩阵。对单个子图作串行处理的时间开销较大,考虑到每个子图之间没有相关性,如果能够将所有子图同时做处理的话,时间上大大节省, 这与CUDA的编程模型非常相符。一个图像对应CUDA模型中的一个Grid,对单个图像尺寸进行8x8块大小的分割,每个块让CUDA模型中的对应Block来处理。根据矩阵的乘法规则,可以让block中的一个线程来计算对应系数矩阵的一个元素。这种对应关系如图5所示。
在利用CUDA编写并行程序时不需关心GPU底层实现,只要采用类C语言按照CUDA编程框架就可以实现并行算法。CUDA并行算法设计思路如图6所示。
4 AVS整数DCT变换算法的实现
利用CUDA实现的并行算法步骤及相关伪代码:
(1)为源图像像素矩阵和结果矩阵在GPU上分配内存,主机端的数据拷贝到设备端,因为GPU并不能直接存取主机内存,只能存取显卡上的显示内存。相关伪码如下:
cudaMalloc((void**)&d_image,sizeof(int)*Sizes*Sizes);
cudaMalloc((void**)&d_Dst,sizeof(int)*Sizes*Sizes);
cudaMemcpy(d_image,image,Sizes*Sizes*sizeof(int),
cudaMemcpyHostToDevice);
cudaMemcpy(d_Dst,Dst,Sizes*Sizes*sizeof(int),cudaMemcpyHostToDevice);
(2)设置CUDA启动的参数,设Grid为(Sizes/8,Sizes/8)的二维结构,Sizes为整个图像像素矩阵的尺寸,Block为(8,8)的二维结构,这样我们很容易看到Grid中的Sizes/8 * Sizes/8个Block分别对应图像的Sizes/8 * Sizes/8子图,Block中的8x8个线程对应每个子图的8x8的像素点,每个线程均有一个唯一标识ID,相关伪码如下:
dim3 Block(BLOCK_SIZE,BLOCK_SIZE);
dim3 Grid(Sizes/BLOCK_SIZE,Sizes/BLOCK_SIZE);
int tex_x = blockIdx.x*BLOCK_SIZE+threadIdx.x;
int tex_y = blockIdx.y*BLOCK_SIZE+threadIdx.y;
(3)将AVS整数DCT变换中所采用的8x8常数矩阵存放在常数存储器(Constance Memory)的数组中,Block中每个线程从图像中读取一个像素点,Block中8x8个线程就读取到8x8的块数据,将其放在共享存储器(share memory)中。使用同步函数__syncthreads()同步Block中的线程。相关伪码如下:
__constant__ int DCT8matrix[64]={T矩阵元素}
__shared__ int CurBlockLocal1[64];
__shared__ int CurBlockLocal2[64];
CurBlockLocal1[(threadIdx.y<<3)+threadIdx.x]=
d_image[tex_x+tex_y * Sizes];
__syncthreads();
(4)等到所有线程读取数据完毕之后进行整数DCT变换,这一步是耗时最大的一步,把计算结果的矩阵存放到一个共享存储器(share memory)中。再次使用同步函数同步线程,使得所有的线程计算完毕,最后把结果存在显存中的数组相应位置。相关伪码如下:
for (int i=0; i
DCTTranslate(DCT8matrix,CurBlockLocal1,CurBlockLocal2);
}
__syncthreads();
(5)将得到的系数矩阵从显卡的显示内存拷回到主机内存中,最后释放设备端分配的显示内存。相关伪码如下:
cudaMemcpy(Dst,d_Dst, Sizes*Sizes* sizeof(int),
cudaMemcpyDeviceToHost );
cudaFree(d_image);
cudaFree(d_Dst);
为了从直观上比较CPU和GPU在DCT变换问题上的计算能力,设计了DCT串行算法,此算法是通过多重循环实现的矩阵乘法。其核心算法如下:
clock_t start ,finish;
start = clock();
for(int i=0;i+BLOCK_SIZE-1
for(int j=0; j+BLOCK_SIZE-1
{
Mult8x8(DCT8matrix,BLOCK_SIZE,Src+i*Stride+j,
Stride, CurBlockLocal,BLOCK_SIZE);
}
finish = clock();
double duration=(double)(finish-start) / CLOCKS_PER_SEC;
5 实验及结果分析
5.1 算法测试环境平台1
5.2 算法测试及结果分析
用产生随机数的方法来模拟图像数据,随机数数组的大小模拟图像尺寸。对CPU串行算法和CUDA并行算法在平台1上分别执行10次,得到每次运行时间再取平均值作为其运行时间,得到平台1的串行时间和平台1的并行时间。改变数组的大小,重复测试。利用公式Sp=T1/Tp(T1代表串行时间,Tp代表并行时间)得到并行算法在平台1上的加速比。为了更好地分析CUDA并行算法的加速性能,我们又在平台2上对CUDA并行算法进行测试,得到在平台2上的并行时间,再用平台1串行时间比上平台2并行时间得到平台2加速比。最终得到的测试结果如表1所示。
根据表1的测试数据得到运行时间对比图7和加速比对比图8。
通过运行时间对比可以直观的发现,随着图像矩阵尺寸的增大,CPU串行算法耗时大幅度增加,而并行算法运行时间变化缓慢。通过加速比的对比,随着图像矩阵尺寸的增大,加速比也在不断地增大,说明GPU更适合处理大数据量的并行。从图中还可以发现平台2的加速比明显高于平台1的加速比,而平台2采用的GPU核心数为8个,平台1采用的核心数为两个,说明CUDA并行算法的执行时间还跟GPU中的核心数有关,核心数越多,Grid中Block间的并行度越高,执行时间越少。
6 结束语
本文论述了AVS视频编码中整数DCT变换以及GPU硬件架构和CUDA编程模型,并利用CUDA编程框架实现了整数DCT变换的并行算法。通过实验测试,与在CPU上运行的串行算法相比,获得较高的加速比,大大减少了AVS编码的时间。在未来的工作中将去挖掘AVS编码中存在的程序并行性,合理划分图像以充分利用GPU性能,更加合理利用CUDA模型中的各种存储空间来达到最大限度的提高程序运行的效率。
参考文献
[1]郑玉,刘文杰.AVS整数DCT变换和量化方法的设计与实现[J].淮海工学院学报,2006,(03):
[2]宋魏,张刚.AVS变换算法在C64x+DSP上的实现[J].微计算机信息,2009,(02):
[3]张舒,褚艳利.GPU高性能运算之CUDA[M].北京:中国水利水电出版社,2009:276.
[4]郭静,陈庆奎.基于CUDA的快速图像压缩[J].计算机工程与设计,2010,(14):
[5]苏飞,王兆华.一种快速DCT算法的研究[J].天津通信技术,2000,(04).
整数DCT变换 篇2
H.264[1,2]是由ITU-T的视频编码专家组(VCEG)和ISO/ISE的运动图像专家组(MPEG)共同制定的视频编码标准。同H.263或MPEG-4相比,在获得相同图像质量的情况下,H.264最多可以节约50%的码率[3],然而,H.264高效的编码效率是以高复杂性为代价的[4]。变换量化模块是H.264标准的重要模块之一,也是频繁调用、复杂耗时的模块之一,因此对于变换量化模块的研究[5,6]具有重要的意义。虽然H.264的编码复杂性比较大,但其底层的基本原理却十分简单,运算规则简单,使用的都是整数的加法、乘法和移位操作,因而十分适合用硬件来实现。而FPGA强大的并行运算能力和高速的运算速度非常适合这一要求,使其成为硬件实现H.264编码标准的理想平台。
1 整数DCT变换与量化的原理
1.1 整数DCT变换的原理
H.264视频编码标准中采用的是基于4×4块的变换编码,并且巧妙地将变换过程中的比例因子合并到量化过程中,使得变换过程只需要一些加法和移位运算就可以实现[6]。其核心变换如式(1)所示
式中:X为帧内或帧间预测后的4×4图像残差块,W为对应DCT变换后的4×4图像残差块,Cf为核心变换矩阵,如果将Cf中的2全部变成1,并保持符号不变,则为DC系数的Hadamard变换。H.264的整数DCT变换和Hadamard变换都是用2个矩阵的左右乘来实现的,如果直接用加乘法来实现矩阵的乘法操作,得到最终的结果需要经过大量计算,而采用蝶形变换[8],简化了计算的过程,只要用加法和移位的操作就可以实现矩阵的相乘,既可以节省计算的量,又可以减少硬件实现的成本。蝶形变换如图1所示。当r=1时,表示Hadamard变换的蝶形算法;当r=2时,表示DCT变换的蝶形算法。
1.2 量化的原理
H.264标准采用标量量化的原理[9],采用52个不同的量化步长,并将DCT变换中的尺度因子结合到量化过程中,具体的量化过程可以通过以下运算[10]来实现
式中:Zij表示量化后的残差系数,Wij表示DCT变换后的残差系数,MF为乘法因子,其值可根据Wij在矩阵中的不同位置和量化参数QP的不同查表得到,如表1所示,f是修正参数,对于帧内预测图像块f取2q/3,对于帧间预测图像块f取2q/6,“>>”为右移运算符,右移1次完成整数除以2的操作,q表示右移位数,sgn()为符号函数。
2 变换量化算法的硬件设计与实现
2.1 变换量化系统的硬件结构
H.264编码器中经过预测后的残差数据可以分为3类:普通4×4的残差块、帧内预测16×16模式亮度宏块的4×4 DC系数块以及色度宏块的2×2 DC系数块。对于普通的残差块,只需对其进行DCT变换、量化,然后至熵编码器,与此同时将量化后的残差进行反量化、反变换,以便得到重构残差数据作为下一帧图像的参考图像;对于帧内预测的16×16模式的亮度宏块,首先对16×16亮度宏块的16个4×4块进行DCT变换,然后将每个4×4块的DC系数提取出来组成4×4 DC块进行Hadamard变换,然后再量化,至熵编码器,重建路径的过程是将4×4 DC块进行反Hadamard变换反量化,并将其填入反量化后的4×4块的DC位置上,然后再进行反DCT变换;色度DC系数的变换量化过程同亮度。图2是变换量化系统的整体结构框图。
2.2 DCT算法的优化与实现
由于DCT算法只涉及到加法和移位操作,非常适合FPGA实现,而1次完整的DCT变换可以看作1次行变换和1次列变换,每次行变换或列变换对应于1次蝶形变换,即完成1次完整的DCT变换需要2次完整的蝶形变换。由图1可知,完成1次完整的蝶形变换需要进行2次计算,即需要2个时钟周期,而在设计中,可以通过代入法,把蝶形变换的中间变量a,b,c,d消除,从而减少1次变换,这样1次蝶形变换需要的时钟周期由2个变为1个,而1次完整的DCT变换需要的时钟周期由4个变成2个,从而实现了对DCT算法的优化。
2.3 量化模块的流水线设计与实现
由式(2)可知,量化的具体实现过程为:首先从缓存中读取DCT变换后的残差数据,对该残差数值进行取绝对值操作,根据残差在缓存中的地址及QP的值查找对应MF值,然后将残差的绝对值和MF相乘,接着将残差和MF的乘积加上偏移量f,进行移位操作,最后输出量化后的残差数据,这样处理1个残差的数据需要的时钟周期为6个,处理1个完整4×4块的残差数据需要96个时钟周期。由于设计中要根据读残差数据的地址确定MF值,本文提出了一种流水线的操作方法,即在查找完MF值后,接着读取下一个数据,而不是等全部处理完一个数据后再读取下一个数据,这样节省了2个时钟周期,处理完16个残差数据所需的时钟周期为65个,比之前减少了21个时钟周期,从而实现了对量化模块的优化。其时序图如图3所示,具体的量化实现框图如图4所示。
3 仿真验证与分析
本文以4×4残差块为例,通过Verilog编程语言实现H.264编码器的变换量化模块,使用Modelsim进行功能仿真,并在Xinlinx的Vertex2P系列的XC2VP30 FPGA上进行综合验证。对DCT算法进行了优化,并对量化模块采用流水线操作处理,使用ISE9.1对变换量化模块进行综合,综合后时钟最高频率可达到135.498 MHz,最长路径时间为7.380 ns。表2给出了本文设计的方法和没进行优化之前的对比,相比之下本文设计的方法处理速度更快,时钟频率更高。
图5给出了变换量化模块的功能仿真图,图中dct_in是经过DCT变换后输出并存储在缓存空间中的残差数据,quantise_out是经过量化后的输出结果,并且将其存储到缓存空间中,以备熵编码使用。本文给出的残差数据是5,11,8,10,9,8,4,12,1,10,11,4,19,6,15,7,经过DCT变换后的输出应为140,-1,-6,7,-19,-39,7,-92,22,17,8,31,-27,-32,-59,-21,经过量化后的输出应为17,0,-1,0,-1,-2,0,-5,3,1,1,2,-2,-1,-5,-1,由仿真图可以证明本文设计方法的正确性。
4 小结
本文充分利用了H.264的DCT算法和量化算法的整洁性以及FPGA强大的并行处理数据能力,首先对DCT的算法进行了优化处理,并对量化模块采用了一种流水线的操作方法,大大缩短了变换量化所需的时间,并且成功设计并实现了H.264变换量化模块的FPGA实现,相对于没有优化和流水线操作的设计方法,可以减少29个时钟周期,为H.264的硬件实现提供了参考,具有一定的应用价值和现实意义。
参考文献
[1]WIEGAND T,SULLIVAN G J,BJONTEGAARD G,et al.Overview oft he H.264/AVC video coding standard[J].IEEE Trans.Circuits andS ystems for Video Technology,2003,13(7):560-576.
[2]PURI A,CHEN Xuemin,LUTHRA A.Video coding using the H.264/M PEG-4AVC compression standard[EB/OL].[2010-08-31].http://w ww-ee.uta.edu/dip/courses/ee5351/h.264spic.pdf.
[3]宗怡.H.264视频压缩关键技术的研究与应用[D].太原:中北大学,2008.
[4]于小燕,赵不贿,郑博,等.基于FPGA的H.264帧内预测算法研究[J].电视技术,2010,34(5):40-43.
[5]KORAH R,PERINBAM J R P.FPGA implementation of integert ransform and quantizer for H.264encoder[J].Journal of SignalP rocessing Systems,2008,53(3):261-269.
[6]KORDASIEWICZ R,SHIRANI S.On hardware implementation of DCTa nd quantization blocks for H.264/AVC[J].Journal of VLSI SignalP rocessing,2007,47(3):189-199.
[7]毕厚杰.新一代视频压缩编码标准[M].北京:人民邮电出版社,2004:127-128.
[8]程丽.基于H.264/AVC中整数变换和量化的研究及VLSI设计[D].哈尔滨:哈尔滨工业大学,2006.
[9]刘峰.视频图像编码技术及国际标准[M].北京:北京邮电大学出版社,2005:55-57.
整数DCT变换 篇3
DCT即离散余弦变换, 是傅里叶变换的实数部分, 因其与傅里叶变换能达到相同功能, 数据量又不大而被广泛采用H.264是应用非常广泛的视频图像编码标准, 其频域图像预处理采用的是基于4×4图像块的整数DCT。本文研究了如何由4×4浮点DCT得到4×4整数DCT, 并设计了4×4整数DCT的蝶形算法, 比较了蝶形算法与普通算法的运算量。
1 4×4浮点DCT
二维N×N图像块的DCT可以理解为先对图像块的每行进行一维DCT, 然后对经行变换的块的每列再进行一维DCT。可以表示为:
式 (1) 中, Xij是图像块X中第i行第j列图像或其残差值, Ymn是变换结果矩阵Y相应频率点上的DCT系数。可以用矩阵表示:
其中, N×N变换矩阵A中的系数:
设相应的4×4浮点DCT变换矩阵A为:
由式 (3) 可得:
2 4×4整数DCT
对于实数的DCT, 由于解码端的浮点运算精度问题, 可能造成解码后数据的失配。为此, H.264采用整数DCT技术, 在不损失图像精度的情况下, 有效减少计算量。
A中的a、b和c是实数, 而图像块X中的元素是整数。为此, H.264对4×4DCT中的A进行了改造。式 (2) 可以等效为:
仍有:
式 (5) 中, 矩阵C是在矩阵A的第一行、第三行除以a, 然后在A的第二行、第四行除以b, 并且方便起见, 令。E是一个尺度因子, 也可以说是个比例缩放矩阵。E中元素的大小可以从A变成C的过程中得到。符号“”表示 (CXCT) 结果中的每个元素乘以矩阵E中对应位置上的系数的值。
为了简化计算, 取d=1/2, 相应地系数b、c也应该调整。由于当d=1/2时有:
根据变换的正交性, 应有的结果为单位矩阵, 所以可推出:
因此当d=1/2时, 同时有:
接下来将矩阵C中的第2行、第4行以及CT的第2列、第4列乘以2, 同时尺度因子矩阵E相应地缩小以给予补偿。最终得到的整数DCT正变换的公式:
在进行变换时, 只计算式 (10) 中的 (CfXCfT) , 因为H.264将“”的运算融合到后面的量化过程中, 从而降低了整个运算的乘法次数, 提高了运算速度。所以实际的4×4整数DCT为:
这样, 式 (11) 中只剩下整数的加法、减法和移位 (乘以2) 操作。
式 (11) 被称为4×4整数DCT变换, Cf是变换矩阵。整数DCT变换与传统的浮点DCT变换运算结果近似, 但因为b和d的值有所变化, 所以两者结果有差别。
3 4×4整数DCT的蝶形算法
可以将式 (11) 的二维变换改造成两个一维变换:先对需要做变换的块 (矩阵) 的每一列做一维变换, 再对其结果的每一行做一维变换。以第一步对输入矩阵X的每一列做一维整数变换为例, 输出矩阵Z的第一列如式 (12) 所示。
其中, x0, …, x3是输入矩阵X的第一列, 而z0, …, z3是输出矩阵Z的第一列。此次变换需要12次加法和4次左移。
从式 (12) 可以看出, 有很多计算重复, 例如 (x0-x3) 就同时被z1和z3使用。为了避免重复, 可以将每次一维整数变换采用蝶形快速算法以节省时间。4×4整数DCT的一维快速变换算法如图1所示。
从图1可以看出, 做一维快速变换需要做8次加法及2次左移, 利用了运算中的冗余, 降低了计算量。表1给出了4×4整数DCT普通算法和快速算法的计算量。
可以看出, 4×4整数DCT快速算法的计算量几乎只有普通算法的一半, 节省了计算空间, 大大提高了运算速度。
摘要：H.264是应用非常广泛的视频图像编码标准。其频域图像预处理采用的是基于4×4图像块的整数DCT。研究了如何由4×4浮点DCT得到4×4整数DCT, 并设计了4×4整数DCT的蝶形算法, 比较了蝶形算法与普通算法的运算量。
关键词：4×4浮点DCT,4×4整数DCT,蝶形算法
参考文献
[1]毕厚杰.新一代视频压缩编码标准——H.264/AVC[M].北京:人民邮电出版社, 2005.
[2]MALVAR H S.Low-complexity length-4transform and quanlization with l6-bit arithmetic.ITU-T SGI6Doc.VCEG-N44[R1].Santa Barbara, USA:[s.n.], 2001.
[3]张晓燕, 谢珺堂.H.264的整数DCT变换编码与量化过程[J].军民两用技术与产品, 2005 (5) :49-51.
[4]于娜, 沈庭芝.新一代视频压缩标准H.264中数据的变换和量化.现代电视技术[J].2005 (2) :15-17.
[5]李朝晖, 等.数字图像处理及应用[M].北京:机械工业出版社, 2007.
整数DCT变换 篇4
关键词：Walsh变换,DCT变换,峰值信噪比,Matlab
随着成像技术、计算机技术和信息技术的发展以及离散数学理论的不断完善, 使得图像处理技术得到了迅速发展。图像变换是图像处理的基础, 也是图像压缩编码中的关键环节, 其发展同样受到广泛关注。基于各种数学函数变换的图像变换技术有多种多样, 如傅里叶变换、拉普拉斯变换、z变换等, 这些变换的复杂程度和效果也不一样。文中将对Walsh和DCT两种变换原理进行简要分析, 并通过实验对比两种变换, 得出Walsh变换性能不亚于DCT变换, 它有着广泛的应用前景。
1 Walsh函数及其变换
沃尔什 (Walsh) 函数[1]是一个完备正交函数系, 其值只取+1和-1。沃尔什函数有三种不同的编号形式, 分别是Walsh编号、Paley编号和Hadamard编号, 并且定义的表达形式也有多种, 文中统一采用Rademacher 函数表达形式。由于这三种编号的沃尔什函数可以按照一定的关系相互转换, 所以, 本文仅将分析Walsh编号的沃尔什函数及其正交变换。
1.1 Walsh 函数
数学家Walsh将不完备的Rademacher 函数加以完备化, 形成了一组完备的正交矩形函数, 称为Walsh 函数。在归一化时, 即函数在正交区间[0, 1]内定义为:
undefined
式中:n=0, 1, 2, …, p是n的二进制编码位数, 指数gm则是n的格雷码 (Gray码) 的第m位数值。如n=6就叫第6号Walsh函数, 二进制为110, p就等于3。Walsh编号的Walsh函数指数形式为:
undefined
由式 (2) 所定义的函数是+1 或-1的连乘积, 其图形如图1所示。
从图1所示Walsh函数的前8个波形可以看出, 每一个波形的正负变更次数 (即过零点的次数) 正好为n。类似正弦信号中频率的概念, 定义过零点数的一半为列率。若n为奇数, 则定义等于 (n-1) /2。若将[0, 1) 区间分为N等分 (N=2p) , 然后在各个区间对波形取样, 便可得到一个离散函数值矩阵。对比图1按8等分区间取样结果的8×8矩阵为:
undefined
式中:记号Wal8表示8次取样的离散Walsh函数;参数T表示取样序号, 自左向右依次为0次, 1次, 2次, …, 第7次。连续Walsh 函数表达式wal (n, t) 与离散表达式WalN (n, T) 的参数有所不同, t是小于1 的时间参数, 其二进制表示也为小数, 位序号自左向右排;T是大于1 的整数, 其二进制表示位序号应自右向左排。离散Walsh函数的指数表达式为:
undefined
1.2 Walsh变换
离散Walsh 编号的函数定义由式 (4) 给出。Walsh 矩阵有如下性质 (为书写简便起见, 记为WalN (n, T) WN, N=2p) :对称性;正交性;与其逆矩阵成正比例。在这些性质的基础上, N维向量XT= (x1, x2, …, xN) 的Walsh变换为:
undefined
逆变换为:
undefined
二维空间的矩阵变换为:
undefined
逆变换为:
undefined
式中:X为数据矩阵;Y为变换后矩阵, 其运算只有加减法。例:对于均匀分布的二维图像信号:
undefined
做Walsh变换, 可得:
undefined
从上述来看, Walsh变换计算比较简单, 只涉及到加减运算, 电路实现起来比较容易。
2 DCT函数及其变换
离散余弦变换 (Discrete Cosine Tranform, DCT) [2,3]是一种与傅里叶变换[4]紧密相关的数学运算。在傅里叶级数展开式中, 如果被展开的函数式是偶函数, 那么其傅立叶级数中只包含余弦项, 再将其离散化可导出余弦变换。离散余弦变换是一种实数域变换。
2.1 DCT函数定义
如果以{X (m) }表示N 个有限的实值或复值信号序列的集合, m = 0, 1, 2, …, N -1, 则离散或有限傅里叶变换为:
undefined
式中:当k=0时, Y (0) 为实数, 表达式保留不变;当k为其他值时, 为了实现实数域运算, 需对式 (9) 做如下修改:
undefined
因为信号序列是中心对称的, X (i) =X (-i) , 并且sin (-a ) = -sin a, 可知式 (10) 指数展开并相加之后, 所有sin a项都抵消, 式 (10) 变为:
undefined
这就是离散余弦变换的变换关系。
2.2 DCT变换
用矩阵形式表示变换关系比较方便, 为此, 将式 (11) 展开:
undefined
上式中:等号左边可以写成Y的矢量, 右边可以写成X的矢量乘积, 即:
undefined
undefined
可以验证矩阵式 (12) 具有归一化正交持性, 因此, 其逆变换关系为:
undefined
从上面分析可知, DCT变换计算较为复杂, 涉及到加减乘除运算, 它对硬件的要求要比Walsh变换的要高, 其运算速度也要比Walsh变换的慢。经过DCT变换后的矩阵, 其非零元素主要集中于某一个区域, 通常是左上角, 而右下角大部分是零, 利用这一特点就可以实现图像压缩。在实际传输时, 可以仅取代表低频成份的左上角, 对其进行量化编码, 由于大多数图像的高频分量都较小, 相应于图像高频分量的系数经常为零, 加上人眼对高频成分的失真不太敏感, 所以, 右下角的高频成分可以去掉或少传, 反变换时, 把去掉部分填零处理, 这样就可达到图像压缩的目的。
3 PSNR质量评估
图像在经过压缩处理之后, 复原的图像都会在某种程度上与原始图像不一样。图像算法虽能确定图像的最优嵌入能量, 但给不出一个最佳量化的指标[5]。为了衡量经过处理后的图像质量, 通常会参考峰值信噪比即 (Peak Signal to Noise Ratio, PSNR) 值来确定某个处理方法是否令人满意。PSNR是一种评价图像质量的客观指标, 它代表峰值信号与噪声的比值, 单位为dB。PSNR值越大, 失真就越小。PSNR定义为:
undefined
式中:undefined分别表示原图像和变化后的图像。
4 图像量化及压缩编码
4.1 图像量化
经过取样的图像, 只是在空间上被离散为像素 (样本) 的阵列, 而每一个样本灰度值还是一个有无穷多个取值的连续变化量, 必须将其转化为有限个离散值赋于不同码字才能真正成为数字图像, 再由计算机或其他数字设备进行处理运算, 这样的转化过程称其为量化。将样本连续灰度值等间隔分级量化的方式称为均匀量化, 不等间隔分级量化方式称为非均匀量化[6]。量化是以有限个离散值来近似表示无限多个连续量, 因此量化会产生误差。对均匀量化来讲, 量化级数越多, 量化误差就越小, 但编码时占用比特数就越多。在一定比特数下, 为了减少量化误差, 往往需要采用非均匀量化, 如按图像灰度值出现的概率大小进行非均匀量化, 灰度值出现概率大的区域细量化, 反之进行粗量化。
4.2 图像压缩编码
在满足一定图像质量要求的前提下, 能获得减少数据量的编码称为压缩编码。数据压缩技术有多种不同的分类方法。一种是按压缩技术所依据和使用的数学理论和计算方法进行分类, 此种分类可分为统计编码、预测编码和变换编码三大类;另一种是根据压缩过程的可逆性进行分类, 通常分为熵压缩和冗余度压缩两种[7,8]。熵压缩是不可逆压缩, 即在其压缩过程中, 会丢失一部分信息, 因此熵压缩又称为有损压缩, 它是以丢失部分信息为代价而获得相应的压缩效果。冗余度压缩是可逆的压缩, 冗余度压缩的机理是完全除去或尽量除去原始数据中重复的部分, 不丢失其中任何有用信息, 从而保证被压缩数据还原后与压缩前数据完全一致, 因此可逆压缩又称为无损编码。图像数据的压缩编解码过程如图2所示。
5 Matlab实验对比分析
在取相同变换量的情况下, 用Matlab[9,10]分别对测试图像进行Walsh变换与DCT变换, 对所取得的数据进行对比分析, 求出相对应的PSNR, 同时, 在不同量化级下, 对测试图像也分别进行Walsh变换与DCT变换, 求出相对应的PSNR, 并进行比较, 如图3～图5所示。将测试图像分割成8×8块, 分别对每一块作变换, 如下:
从以上实验数据中可以看出, 当量化级数K=32时, 除阈值取0外, 其余取值的DCT变换的PSNR都要低于Walsh变换的PSNR, 而且都低于量化级为16的同类DCT变换。这表明在K=32时, DCT变换图像质量不理想, 在应用DCT变换时应尽量避开这一量化级。当K=64时, Walsh变换后图像的PSNR值较低, 大多都低于量化级为32的PSNR值, 即K=64时Walsh变换后图像质量不理想, 在应用Walsh变换时应尽量避免这一量化级数。在保留上三角的变换中, Walsh变换的图像质量比DCT变换的图像质量稍差 (K=32除外) 。在取阈值的变换中, 当K>128时, Walsh变换和DCT变换的PSNR值比较逼近。在K=1 024, 保留上三角54个数据时, Walsh变换和DCT变换的PSNR值都大于40, 可视为无损变换。
所有试验结果如下表1所示。
6 结 语
通过在不同量化等级下对两种变换结果的对比, 得出在量化级数K=32、保留上三角数据时的Walsh变换明显优于DCT变换, 可用Walsh变换代替DCT变换。这类图像变换可用于对图像质量要求不高的卫星定位、导弹指导等;在K=1 024, 保留上三角54个数据时, Walsh变换与DCT变换都可视为图像的无损变换, 这类图像变换可用于CT、核磁共振等医学图像分析和生物的细胞分析等。虽然在多数量化级上, Walsh变换的PSNR略逊于DCT变换的PSNR, 但比值已相当逼近。由于Walsh变换只有加减法运算, 它的运算比DCT变换的简单得多, 快得多, 硬件实现起来也比较容易, 图像的存储和处理所耗资源较少, 可以大大节约成本, 有着广泛的应用前景。
参考文献
[1]胡征, 樊昌信.沃尔什函数及其在通信中的应用[M].北京:人民邮电出版社, 1980.
[2]李春霞.基于二维DCT的图像压缩及其实现[J].现代电子技术, 2008, 31 (10) :157-159.
[3]陈东, 戢小亮, 朱旭花.一种简便快速的DCT算法及其硬件实现[J].现代电子技术, 2007, 30 (8) :98-100.
[4]章毓晋.图像处理和分析技术[M].2版.北京:高等教育出版社, 2008.
[5]WANG Z, BOVIK A C, EVANS B L.Blind measurementof blocking artifacts in images[C]//Proceedings of IEEE In-ternational Conference on Image Processing.Vancouver, Canada:IEEE, 2000, 3:981-984.
[6]黄贤武, 王加俊, 李家华.数字图像处理与压缩编码技术[M].成都:电子科技大学出版社, 2000.
[7]刘榴娣, 刘明奇, 党长民.实用数字图像处理[M].北京:北京理工大学出版社, 2003.
[8]冈萨雷斯.数字图像处理[M].阮秋琦, 译.2版.北京:电子工业出版社, 2007.
[9]周金萍, 王冉.Matlab 6实践与提高[M].北京:中国电力出版社, 2002.
整数DCT变换 篇5
离散余弦变换 (DCT) 是最接近KL变换的正交变换, 可有效地去除空间域的相关性并且可以使大部分的能量集中在直流及低频的部分。这些性质使得DCT被广泛应用于图像压缩, 语音压缩等技术中。但是由于DCT变换中涉及到浮点数的乘加运算, 大大影响了运算的精度和速度。本文以8*8二维DCT变换为例, 提出一种基于提升算法的二维DCT变换的FPGA实现。
二、DCT变换
一个8*8的一维DCT变换的定义为[1]:
其中g (k) 为系数
x (n) 为输入数据, X c (k) 为变换后的数据, n, k=0, 1, …, N-1。
三、提升
提升方法公式表示为[2]:
因此有:yi=xi+ci, jxj, yk=xk且j, k i。其中y, x均为1维列向量。由此可以看出, cij即使是一个浮点数, 也可以用一个近似的数来进行代替。为了硬件实现的方便, 这个替代的数应该是以2的n次幂为分母的。
四、一维8点整型DCT的算法改进
根据文献[3]的推导, 首先是将一维8点DCT变换分解成两个一维的4点的向量, 再分别对这两个4点的一维向量分别进行4点的DCT/IDCT变换, 然后再将得到的结果经过合并, 得到原一维的8点DCT变换的结果。
原算法中, 对4点的DCT/IDCT变换采用的是直接变换的方法, 从硬件实现的角度来看, 一方面, 乘法器的采用大大增加了电路所消耗的资源, 同时对运行速率也有很大影响, 耗能方面也相对较大, 因此运用提升结构, 可以将DCT算法中的这些乘法因子分离出来, 并利用DCT正变换和逆变换中乘法因子的倒数关系和对称性无损的舍去这些乘法因子, 以此来加快DCT算法。这种方法, 通过用加法和移位来实现逼近乘法, 实现了算法的无乘结构, 更有利于硬件的实现。于是可以得到图1的形式, 其中左侧为正变换, 右侧为逆变换:
并且由图1可以得到如下的DCT正变换和逆变换的
变换矩阵分别为:
通过对上式及文献[2]描述的算法中的各个系数进行适当分解, 如:3/8=1/4+1/8, 55/64=1/2+1/4+1/16+1/32+1/64, 便可以方便的把乘法运算转换成移位和加法运算。这样, 就可以完成一维4点无乘法DCT变换。
综上所述, 可以看出, 完成一维8点DCT正变换只通过移位和加法即可实现, 可大大节约FPGA的资源, 而且该算法在硬件实现时可采用多级流水线及并行处理的结构, 在少量增加电路面积的前提下, 大量提高硬件电路的运行速率。
五、2维8*8点DCT变换的实现
对于2维的8*8点DCT变换, 可以通过先对其进行逐行的1维8点DCT变换, 然后再逐列进行来完成。硬件实现方面, 可以通过2个相同的一维DCT变换模块加一个转置存储模块完成。硬件电路如图2所示。
精度方面, 输入为图像的灰度值, 因此取值应该是在0~255的范围内, 但由于转换的过程中, 涉及到右移8位的计算, 为了保证计算的精度, 取数据的宽度为14位。高8位为整数部分, 低6位为小数部分。
六、硬件电路实现及仿真结果
器件选用的是Xilinx Spartan3e系列的xc3s500e-4, FT256封装的。采用Verilog HDL, 根据上述的步骤, 对硬件电路进行了行为级描述, 使用Model Sim SE 6.2i进行仿真, Xilinx ISE 10.1进行综合布局布线。综合布线后, 使用实际图像对两种算法对图像的还原程度以及占用资源、运算速度等进行综合对比, 如图4所示:
其中A为源图像, B1、C1分别为文献3和本文的方法得到的图像结果, B2、C2分别文献3和本文逆变换后得到的图像与源图像的差。从恢复的图像对比来看, 与原算法相比, 效果是很相近的。但是从电路上来看, 本文所采用的改进算法布局布线后所用资源比原来算法所消耗的资源减少了近15%, 而且速率也提高了大约10%。
参考文献
[1]胡广书.数字信号处理[M].二版.清华大学出版社.
整数DCT变换 篇6
传统的加密技术[1],是把有意义的信息编码为伪随机性的乱码以保护信息的—门学科,经过加密的信息会变成混乱的数据.这样一来很容易引起攻击者的注意.信息隐藏提供了另外一种对秘密信息的保护方法,它通过将秘密信息嵌入到另外一幅有意义的并且不引人注意的图像中来隐藏和传送秘密信息.和加密技术相比,加密技术着重于保护秘密信息的内容,而信息隐藏着重于隐藏秘密信息的存在.
1 信息隐藏的可行性
信息隐藏[2]技术之所以能够实现是因为:
(1)多媒体信息本身存在很大的冗余性,从信息论的角度看,未压缩的多媒体信息的编码效率是很低的,所以将某些信息嵌入到多媒体信息中进行秘密传送是完全可行的,并不会影响多媒体信息本身的传送和使用.
(2)人的视觉和听觉本身具有某些特性为信息隐藏提供了条件,比如人眼的视觉惰性、暂留现象、阈值效应等,利用人的这些特点,可以很好的将有用信息隐藏而不被察觉. 目前的信息隐藏算法一般来讲可分2类:空间域的方法和变换域的方法[3],2种算法各有利弊,但都出于将消息嵌入载体冗余部分这一思想,信息发送流程如图1所示.
变换域技术,即把隐藏的信息嵌入到载体的一个变换空间(如频域)与空域方法相比,变换域方法的优点如下:
(1)在变换域中嵌入的信号能量可以分布到空域的所有像素上.
(2)在变换域中,人的感知系统的某些掩蔽特性可以更方便地结合到编码过程.
变换域方法可与数据压缩标准,如JPEG等兼容,常用的变换包括离散余弦(DCT)变换和小波变换.
2 信息隐藏的主要思想
信息隐藏的依据就是想方设法把信息隐藏到图像不敏感区域,或者说是视觉冗余空间,这样不会降低图像视觉质量引起人们的注意,同时也保证了信息传递的安全性[4].变换域的具体算法实现起来相对困难,下面给出一种基于DCT变换,由MATLAB为工具的图像隐藏方法.
2.1 DCT域的信息隐藏
二维DCT变换是目前使用的最著名的有损数字图像压缩系统——JPEG系统的核心.因此,在域中的信息隐藏,可以有效地抵抗JPEG有损压缩.DCT变换首先需要把图像分割成8×8的像素块,然后进行二维DCT变换,得到8×8的DCT系数,这些系数从低频到高频按照Zig-Zag次序排列,第一个值(左上角)为直流系数,其余为交流系数.DCT系数中,左上角部分为直流和低频系数,右下角部分为高频系数,中间区域为中频系数.低频代表图像像素之间慢变化,即图像框架部分,高频代表像素之间的快变化,即图像细节部分[5].因此,高频部分代表图像中的噪声部分,这些部分容易通过有损压缩或者滤波等处理被去掉.而中低频部分包含了图像的大部分能量,也可以说,对人的视觉最重要的信息部分,都集中在图像的中低频.一般图像的压缩和处理,为了保持图像的可视性,都保留了图像的中低频部分.而低频部分的改变有可能引起图像较大的变动,因此,为了将隐藏的信息与载体图像的视觉重要部分绑定,一般都将隐藏信息嵌入到载体的中高频部分,达到既不引起视觉变化,又不会被轻易破坏的目的.
给出实数列S的二维DCT变换公式
2.2 MATLAB实现步骤
通过MATLAB工具箱可以方便地实现信息隐藏的效果,需要注意的是在实现过程中各变量之间的转换,DCT变换后图像矩阵精度发生变化,在消除载体图像的高频分量后,经DCT变换后的信息图像矩阵叠加在载体图像矩阵的右下角即高频分量处,若矩阵的行列不规则,不能直接做加法处理,可以考虑将2幅图像的行列做补零的调整,使2幅图像可以直接相加,程序流程如图2.试验效果图如图3～图5.
3 实验分析
在信息隐藏技术中,峰值信噪比、均方根误差、图像特征相对误差是最重要的几个性能指标.下面对它们分别展开讨论:
(1)峰值信噪比PSNR常用来衡量嵌入隐藏信息后图像的质量,PSNR越高,表明信息嵌入后对原待嵌入信息的图像带来的噪声越小,也就是隐藏的效果越好.
PSNR定义如下
其中,f(i,j)是原来的待嵌入隐藏信息图像;f(i,j)′是嵌入信息后的图像;M、N是图像的尺寸.
(2)均方根误差RMSE可以较好地反映嵌入隐藏信息前后2幅图像的误差.RMSE越小,表明2幅图像越相似.
RMSE定义如下
实验中以不同的图像作为待嵌入隐藏信息图像,实验结果如表1所示.
(3)图像特征相对误差.众所周知,像素灰度是图像各离散点量测幅度的样本值,是最原始、最基本的特征数据.均值表示图像包含的平均能量,标准差表示像素灰度分布的分散程度,该值越小说明像素灰度分布越集中,越大说明像素灰度越分散.
实验结果如表2所示.
通过对以上特征数值分析并在MATLAB实现DCT域的信息隐藏实验可以看出,图3作为载体图像和图6的信息隐藏完成图像相比,图像的框架基本无变化,变化较多的是图像的细节部分,但是调整后这种细节部分的变化可以控制在人眼能够忍受的范围内,从而不易发现图5这个有用信息,达到信息隐藏的目的,图4为原始图像经DCT变换后的能量分布图,经过对DCT变换的特征分析,选用了载体图像的特定区域,即DCT系数中高频部分N个最大的DCT系数作为待隐藏图像的DCT系数,减少了对原图像视觉的影响.实验表明,嵌入隐藏信息后的两幅图像在视觉上人眼无法分辨,算法具有良好的隐秘性和较强的鲁棒性,可以有效地抵抗随机噪声、位置变换、变形、剪切等操作.
4 结 束 语
目前所采用的变换域信息隐藏方法有多种,由于DCT变换是最常用的有损数字压缩系统JPEG的核心,采用这种方法不仅适用范围广,可以推广到视频压缩等领域,而且信息隐藏的鲁棒性较好.给出的这种方法简单易行,但效果欠佳,可以通过对图像分块后,各子块分别采用DCT变换后再进行隐藏过程,并且在对完成效果要求较低的情况下还可对完成图像进行滤波,从而减少杂波噪声对图像的影响,这些方法在以后的实验中进行.
摘要：提出了一种基于二维DCT变换的图像信息隐藏方法,经过二维DCT变换后的图像能量集中在低频部分,考虑到人眼的视觉特性,图像的高频部分可视为视觉冗余部分,可以把有用信息隐藏在变换载体图像的高频部分,即以牺牲图像高频信息来达到信息隐藏的效果,通过MATLAB实现这一思想,对隐藏后的图像质量做了特征分析,并对下一步实验做出了设想.
关键词：信息隐藏,DCT变换,视觉特性
参考文献
[1]汪小帆,戴跃伟,毛耀斌.信息隐藏技术方法与应用[M].北京:机械工业出版社,2001.
[2]徐常勇,平西建,张涛.视频信息伪装技术综述[J].计算机应用研究,2006:8-11.
[3]张立和,周继军,陈伟,等.透视信息隐藏[M].北京:国防工业出版社,2007.
[4]Fabien AP Petitcolas,Rosa J Anderson,Markus G Kuhn.Information Hiding;A Storey[C]//Pmc.of the IEEE,1999:1062-1078.