http://www.paper.edu.cnDCT原理及其在视频压缩编码中的实现孙娟北京邮电大学电信工程学院，北京（100876）E-mail:sunjuan1983@gmail.com摘要：本文以视频压缩编码为背景，从DCT的基本原理入手，介绍了DCT在压缩编码实现过程中的快速算法：LLM算法、提升格式的快速DCT算法。详细介绍了基于提升格式的BinDCT的实现原理和特性，并对各种算法性能进行比较和分析。关键词：DCT；提升格式；旋转矩阵1.引言在图像数据压缩技术中，正交变换编码是一种基本而有效的编码方法，它极大的利用了图像数据的空间相关性，使图像数据的压缩能够达到很高的比率。它主要是利用数学变换的方法，使用极少量的离散信号来表示大量的时域连续信号。常用的数学变换有很多种，比如离散傅立叶变换（DisperseFourierTransfer）、沃尔什变换、哈尔变换、斜变换、离散余弦变换（DiscreteCosineTransform）、离散正弦变换（DiscreteSineTransform）、K-L变换等。其中，K-L变换为理想状态下的最佳变换方法。但是，由于K-L变换没有快速的变换算法，而DCT、DFT和DST都具有与K-L变换近似的良好性质,尤其是当一阶马尔可夫过程相邻元素相关系数ρ逼近1时，DCT的近似性能远远优于其它两者。因此，图像压缩标准中，使用DCT变换来实现纹理编码。由于DCT变换在各种编码标准中要被反复调用，因此，其代码执行效率对实时视频压缩起着至关重要的作用。实际应用中，如何实现DCT变换的编码及如何用硬件电路实现这种编码变换是使用者关心的问题。为减少二维DCT的计算复杂度，人们提出了各种快速算法。1989年Loeffler便构造出仅有11个乘法和29个加法的DCT算法(LLM),被称之为“最终解决方案”。但是算法中乘法运算，无论是在硬件实现中还是在软件实现中都是耗费巨大的。尽管随着新的数字信号处理器和芯片的发展，快速DCT算法变得更加有效，但是并没有从根本上解决制约速度的关键问题。直到1998年T.Tran受提升结构启发，运用三步提升结构和紧缩提升结构，改造W-Chen在1977提出的以旋转矩阵为基础结构的快速DCT算法，最终实现了一种没有乘法的快速DCT算法(BinDCT)，在速度上获得了重大突破。本文首先介绍DCT变换的基本原理，介绍现有的快速DCT算法的实现及其特点，然后给出这些算法的综合性能比较。2.DCT变换原理2.1DCT变换的图像压缩原理图像信息一般都具有高度的相关性，因此任何压缩机制的目的在于除去数据中存在的相关性。相关性就是根据给出的一部份数据来判断出其相邻的数据，在实际中存在很多数据相关性，常见的有：空间相关性、频率相关性、时间相关性等[6]。在图像压缩编码中，减少空间相关性的主要方法是正交变换。图像经过正交变换后，能够实现图像数据压缩的物理本质在于经过多维坐标系中的适当的坐标旋转和变换，能够把散布在各个坐标轴上的原始图像数据，在新的坐标系中集中到少数坐标轴上，因而能够用较少的编码比特数来表示一幅图像，实现图像的压缩编码。从数学上看，用于图像压缩编码的正交变换有很多种，如：K-L变换、DCT变换、Fourier变换、Walsh变换等。根据均方差最小准则，K-L具有最佳变换特性，DCT变换次之。但是-1-http://www.paper.edu.cnK-L变换实现起来计算量很大，因此常用DCT变换替代。图像数据经过DCT变换，可实现用一个和原来不同的数学基来表示数据，其数据的相关性能够显露出来或被拆开。在这种新基下，大部分的系数都接近于零，可以忽略，于是可以将余下的信息存储在一个较小的数据包里。由此，实现了图像的压缩。2.2一维DCT变换原理设{Xm()|m=−0,1,...,N1}是对带宽有限信号x(t)取样得到的数据序列，共N个样值，其一维离散余弦变换（1D-DCT）定义为[1]：2(21)N−1mu+πYu()=Cu()∑Xm()cos,u=1,2,…,N-1(公式1)NNm=02⎪⎧1/2,u=0其中Cu()=⎨⎩⎪1,其他一维离散余弦的逆变换（1D-IDCT）定义为[1]：2(21)N−1mu+πXm()=∑Cu()Y(u)cos，m=1,2,…,N-1(公式2)NNm=02两者的变换核都是[1]:2(21)mu+πaum(,)=Cu()cos,{aum(,)|u=0,1,...,N−1}(公式3)NN22.3二维DCT变换原理一维离散余弦变换的定义可推广到二维离散预弦变换（2D-DCT）。设{Xmn(,)|m=−=−0,1,