离散余弦变换(DCT for Discrete Cosine Transform)是与傅里叶变换相关的一种变换，它类似于离散傅里叶变换(DFT for Discrete Fourier Transform),但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的(因为一个实偶函数的傅里叶变换仍然是一个实偶函数)，在有些变形里面需要将输入或者输出的位置移动半个单位(DCT有8种标准类型，其中4种是常见的)。

最常用的一种离散余弦变换的类型是下面给出的第二种类型，通常我们所说的离散余弦变换指的就是这种。它的逆，也就是下面给出的第三种类型，通常相应的被称为"反离散余弦变换"，"逆离散余弦变换"或者"IDCT"。

有两个相关的变换，一个是离散正弦变换(DST for Discrete Sine Transform),它相当于一个长度大概是它两倍的实奇函数的离散傅里叶变换；另一个是改进的离散余弦变换(MDCT for Modified Discrete Cosine Transform),它相当于对交叠的数据进行离散余弦变换。

应用

离散余弦变换，尤其是它的第二种类型，经常被信号处理和图像处理使用，用于对信号和图像(包括静止图像和运动图像)进行有损数据压缩。这是由于离散余弦变换具有很强的"能量集中"特性:大多数的自然信号(包括声音和图像)的能量都集中在离散余弦变换后的低频部分，而且当信号具有接近马尔科夫过程(Markov processes)的统计特性时，离散余弦变换的去相关性接近于K-L变换(Karhunen-Loève 变换--它具有最优的去相关性)的性能。

例如，在静止图像编码标准JPEG中，在运动图像编码标准MJPEG和MPEG的各个标准中都使用了离散余弦变换。在这些标准制中都使用了二维的第二种类型离散余弦变换，并将结果进行量化之后进行熵编码。这时对应第二种类型离散余弦变换中的n通常是8，并用该公式对每个8x8块的每行进行变换，然后每列进行变换。得到的是一个8x8的变换系数矩阵。其中(0,0)位置的元素就是直流分量，矩阵中的其他元素根据其位置表示不同频率的交流分类。

一个类似的变换, 改进的离散余弦变换被用在高级音频编码(AAC for Advanced Audio Coding)，Vorbis 和 MP3 音频压缩当中。

离散余弦变换也经常被用来使用谱方法来接偏微分方程，这时候离散余弦变换的不同的变量对应着数组两端不同的奇/偶边界条件。

计算

尽管直接使用公式进行变换需要进行O(n2)次操作，但是和快速傅里叶变换类似，我们有复杂度为O(nlog(n))的快速算法，这就是常常被称做蝶形变换的一种分解算法。另外一种方法是通过快速傅里叶变换来计算DCT，这时候需要O(n)的预操作和后操作。

参考

K. R. Rao and P. Yip, 离散余弦变换 : 算法、优点和应用 (Discrete Cosine Transform: Algorithms, Advantages, Applications) (Academic Press, Boston, 1990).

A. V. Oppenheim, R. W. Schafer, and J. R. Buck, 时间离散信号处理 (Discrete-Time Signal Processing), second edition (Prentice-Hall, New Jersey, 1999).

S. A. Martucci, 对称卷积和离散正弦余弦变换 (Symmetric convolution and the discrete sine and cosine transforms), IEEE Trans. Sig. ProcessingSP-42, 1038-1051 (1994).

Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/. 一个免费的C语言库GPL，可以计算DCT-I~IV的1维到多维的任意大小的变换

M. Frigo and S. G. Johnson, "FFTW3的设计和实现," Proceedings of the IEEE93 (2), 216–231 (2005). [编辑本段]改进的离散余弦变换改进的离散余弦变换（Modified Discrete Cosine Transform, MDCT）是一种与傅立叶变换相关的变换，以第四型离散余弦变换（DCT-IV）为基础，重叠性质如下：它是应用于处理较大的资料集合，当连续的资料区块中，当前的资料区块跟后续的资料区块有重叠到的情形；即当前资料区块的后半段与下一个资料区块的前半段为重叠的状态。这样的重叠情形，除了具有离散余弦变换（Discrete Cosine Transform, DCT）的能量压缩特性外，也使这种变换在应用于信号压缩时更引人注目。因为它有助于避免由于资料区块边界所产生的多余资料。因此，这种变换可应用于MP3，AC-3， ogg vorbis，和AAC的音频压缩等方面。

改进的离散余弦变换是由Princen，Johnson和Bradley承接早前（1986年）Princen和Bradley所提出关于时域混叠消除法（Time-Domain Aliasing Cancellation, TDAC ）的改进的离散余弦变换基本定理，于1987年所提出，详述如下。至于其他类似的变换还有如以离散正弦变换为基础的改进的离散正弦变换（Modified Discrete Sine Transform, MDST）。以及其他较少使用的变换，例如以其他不同类型的DCT或DCT/DST的组合为基础的改进的离散余弦变换。

在MP3的应用上，改进的离散余弦变换，并不适用于直接处理音频信号，而适用于处理32波段多相正交滤波器（Polyphase quadrature filter, PQF）阵列的输出端信号。这样的改进的离散余弦变换输出是由一个混叠削减公式作后置处理，用以减少多相正交滤波器阵列的特殊混叠。这样的改进的离散余弦变换与滤波器阵列组合，被称作混合滤波器阵列或子带改进的离散余弦变换 。相反地，AAC通常使用一个纯粹的改进的离散余弦变换；仅Sony公司使用的MPEG – 4 AAC - SSR技术采用了运用改进的离散余弦变换的四波段多相正交滤波器阵列（但也是很少使用）。自适应听觉变换编码（Adaptive TRansfeorm Acoustic Coding, ATRAC）利用运用改进的离散余弦变换的堆叠型正交镜像滤波器（Quadrature Mirror Filter, QMF）。

在基于DCT变换的图像压缩编码方法中,对DCT系数必须做量化处理。量化过程是一个多对一的映射,例如对一个8×8块的64个DCT变换系数分别除以量化步长后取整。由于大多数DCT变换系数量化后变为零,因而达到压缩的目的。由于在量化过程中用到除法,因此通常需要进行浮点运算。

但是,可进行浮点运算的数字信号处理器（DSP）芯片结构比定点DSP芯片复杂,价格一般也比定点DSP芯片高很多。所以数字图像处理系统中通常采用定点DSP芯片来完成图像压缩运算,这种方法已经成为数字图像处理技术的的一个趋势。

可用于数字图像处理的比较好的定点DSP芯片有德州仪器公司新一代高性能定点DSP芯片TMS320C6200系列。它具有VLIW（Very Long Instruction Word）结构,由8个可并行运行的执行单元构成。这些单元使得该系列芯片在单周期内可以并行执行多条指令,例如在单周期内并行完成2个16位×16位乘法和2个移位操作。它还具有流水线结构,使得若干条指令的不同执行阶段可以并行执行。这些设计使得TMS320C6200系列芯片程序执行速度更快、性能更高。如200MHx时钟的TMS320C6201峰值性能可以达到1600MIPS。

在定点DSP上完成除法,通常的办法是调用库函数。但是调用库函数,势必会打破循环中的流水线操作,严重影响量化的完成速度。所以提高量化过程速度的关键就在于避免任何函数调用、跳转等操作。

本文以TMS320C6200系列定点DSP为例,提出一种用定点乘法和移位运算来代替量化过程中除法和饱和运算的方法,从而极大地提高了量化过程的运行速度。该方法也同样适用于其它各种定点微处理器。

1 MPEG-4标准中采用的量化技术及程序优化

MPEG-4标准中定义了两种量化方式：H.263量化方式和MPEG-4量化方式。这里为简单起见,只介绍TMN2.0编码器所用到的一种量化策略：AC系数和帧间宏块的DC系数用H.263量化方式,而帧内宏块的DC系数用MPEG-4量化方式中的DC系数非线性量化方式。

1.1 H.263量化方式

量化参数QP可以取值[1,3],量化步长为2QP。则量化公式为：

对于帧内宏块,LEVEL= COF /(2QP)

对于帧间宏块,LEVEL=( COF -QP/2)/(2QP)式中,COF表示即将被量化的DCT变换系数,LEVEL表示量化结果的绝对值。

1.2 MPEG-4DC系数非线性量化方法

量化公式为：LEVEL=DC_COF//dc_scaler

式中,DC_COF表示即将被量化的DCT变换DC系数LEVEL表示量化结果//表示先进行除法运算,然后对结果四舍五入取整。

在内部宏块内,定义亮度块为类型 1块,色差块为类型2块,类型1块的C系数由类型1的非线性标尺量化类型2的DC系数由类型2的非线性标尺量化。

表1为定义DC非线性量化标尺dc_scaler。

表1 帧内宏块DC系数标尺

类 型 量化参数（QP）范围内的dc_scaler

1～4 5～8 9～24 25～31

亮度：Type1 8 2QP QP+8 2QP-16

色度：Type2 8 (QP+12)/2 QP-6

从表1中可以看到亮度块和色差块的DC系数有独立的量化标尺,亮度块具有较大的标尺而色度块具有较小的标尺。这种分段线性的非线性量化策略是一种高效的量化方式,它在保证图像质量的基础上提高了压缩效率。

1.3 将量化除法改定点乘法的方式

以内部宏块的AC系数量化公式为例,将其改写为：

LEVEL= COF /2QP= COF （2 n/2QP）/2 n

定义量化参数ac_cocff=[2n/2QP],[x]表示对x截尾取整,则：

LEVEL= COF ×ac_coeff/2n

在QP的取值都范围[1,31]内,要使截尾取整后的每一个2 n/2QP的值都能够用量化参数ac_coeff一一对应地表示,n必须足够大。通过计算得出：当n≥11时满足要求。

取n=11得到ac_coeff的计算公式为：

ac_coeff=[2 11/2QP]

其实质就是用一个字（32 bit）的低11位（0Q11）来表示1/2QP的小数部分。

由于QP在[1,31]之间,可以用上述公式计算出对应于帧内宏块AC系数量化的量化系数的查找表：ac_coeff=AcQConff[QP]。用C语言表示为（假设QP=0时ac_coeff=0）：

const short int AcQConeff[32]=

{0x000,0x400,0x200,0x155,0x100,0x0cc,0x0aa,0x092,

0x080,0x071,0x066,0x05d,0x055,0x04e,0x049,0x044,

0x040,0x03c,0x038,0x035,0x033,0x030,0x02e,0x02c,

0x02a,0x028,0x027,0x025,0x024,0x023,0x022,0x021}

计算表明,AC系数量化系数、亮度块DC系数量化系数和色差块DC量化系数都可以统一用一个字的低11位（0Q11）来表示。这样就可以分别计算出它们的量化系数的查找表,从而实现用乘法运算代替除法运算。

而除以2 n的操作可以用右移n位的办法来完成。

对于8bit无符号二进制数表示的象素值,在经过DCT变换后,其DCT变换系数的值域为[-2048,2047],最大有12位二进制数。同时,由上述分析可知量化系数最大有11位。所以DCT变换系数与量化系数相乘的结果最大将有11+12共23位。由于TMS320C62xDSP芯片中集成的乘法器是16位×16位的乘法器,乘法运算结果存放到32位的寄存器中。所以用本文方法计算出的量化系数与DCT变换系数相乘后,结果不会溢出。

根据MPEG-4 Visual标准TMN 2.0的要求,量化后AC系数值要饱和到[-2048,2047]之间。这可以利用TMS320C62x芯片指令集中的饱和左移指令SSHL来实现,只需两条指令即可完成饱和运算,无需使用比较指令和跳转指令。

下面给出内部宏块量化的TMS320C62x线性汇编程序：

cmpeq type,1 //type定义的是当前块的类型

[type] ldh *+DcLumQCoeff[QP],dc_coeff //得到类型1的DC系数的量化参数

[!type] ldh *+DcChromQCoeff[QP],dc_coeff //得到类型2的DC系数的量化参数

lde *coeff[0],level //取出DCT变换DC系数

mpy level,dc_coeff,level //用乘法进行量化

addk 0x400,level //加 0x400,对结果进行四舍五入

shr level,11,level //右移11位

cmpgt level,maxDC,tmp //对量化后的DC系数进行饱和运算

[tmp] mv maxDC,level //将其限制在[1,maxDC]之间cmplt level,1,tmp

[tmp] mvk 1,level

ldh *+AcQcoeff[QP],ac_coeff //得到AC系数的量化参数

mvk 63,cntr //63次循环,只对AC系数进行量化

loop: .trip 63 ldh *coeff++[1],cof //取出DCT变换AC系数

abs cof,level

mpy level,ac_coeff,level //对AC系数绝对值用乘法进行量化

shru level,11,level //右移11位

cmplt cof,0,tmp

[tmp] neg level,result

[!tmp] mv level,result

sshl result,20,result //将量化后的AC系数值进行饱和运算,

shru result,20,result //将结果限制在[-2048,2047]之间

sth result,*qcoeff++[1]

[cntr] sub cntr,1,cotr

[cntr] b loop

由该程序可以看到,程序中没有任何会影响流水线的的跳转语句及函数调用。因此将该程序编译后会发现,此循环被优化构成软件流水。如果再使用其它一些优化手段,比如合并程序中的移位指令,合作字访问指令一次处理两个短型数据等,该程序的效率将会更高。我们用TMS320C62x软件仿真器测试表明,原来使用除法的量化函数需要4871个周期,而运用上述优化办法进行优化后的量化函数只需275个周期即可完成,效率提高约18倍。

DCT/IDCT变换及量化过程是视频图像压缩系统中的关键模块。该模块的执行速率对整个系统的处理流度影响很大,因此将量化过程中的浮点运算转换为定点运行,提高该模块在定点DSP芯片上的执行速度,其意义显得尤为重要。同时由于目前绝大多数数字通讯系统都基于定点DSP芯片,如果用定点芯片完成视频图像处理将会有易于与数字通讯系统集成的优点。我们的这一方法为在定点芯片上完成图像处理进行了有益的尝试,为后续的研发工作打下了一个良好的基础。

一.JPEG压缩过程

JPEG压缩分四个步骤实现：

1.颜色模式转换及采样；

2.DCT变换；

3.量化；

4.编码。

二.

1．颜色模式转换及采样RGB色彩系统是我们最常用的表示颜色的方式。JPEG采用的是YCbCr色彩系统。想要用JPEG基本压缩法处理全彩色图像，得先把RGB颜色模式图像数据，转换为YCbCr颜色模式的数据。Y代表亮度，Cb和Cr则代表色度、饱和度。通过下列计算公式可完成数据转换。 Y=0.2990R+0.5870G+0.1140BCb=-0.1687R-0.3313G+0.5000B+128 Cr=0.5000R-0.4187G-0.0813B＋128人类的眼晴对低频的数据比对高频的数据具有更高的敏感度，事实上，人类的眼睛对亮度的改变也比对色彩的改变要敏感得多，也就是说Y成份的数据是比较重要的。既然Cb成份和Cr成份的数据比较相对不重要，就可以只取部分数据来处理。以增加压缩的比例。JPEG通常有两种采样方式：YUV411和YUV422，它们所代表的意义是Y、Cb和Cr三个成份的数据取样比例。

2.DCT变换 DCT变换的全称是离散余弦变换(Discrete Cosine Transform)，是指将一组光强数据转换成频率数据，以便得知强度变化的情形。若对高频的数据做些修饰，再转回原来形式的数据时，显然与原始数据有些差异，但是人类的眼睛却是不容易辨认出来。压缩时，将原始图像数据分成8*8数据单元矩阵，例如亮度值的第一个矩阵内容如下：

JPEG将整个亮度矩阵与色度Cb矩阵，饱和度Cr矩阵，视为一个基本单元称作MCU。每个MCU所包含的矩阵数量不得超过10个。例如，行和列采样的比例皆为4:2:2，则每个MCU将包含四个亮度矩阵，一个色度矩阵及一个饱和度矩阵。当图像数据分成一个8*8矩阵后，还必须将每个数值减去128，然后一一代入DCT变换公式中，即可达到DCT变换的目的。图像数据值必须减去128，是因为DCT转换公式所接受的数字范围是在-128到+127之间。DCT变换公式：

x,y代表图像数据矩阵内某个数值的坐标位置f(x,y)代表图像数据矩阵内的数个数值u,v代表DCT变换后矩阵内某个数值的坐标位置F(u,v)代表DCT变换后矩阵内的某个数值u=0 且 v=0 c(u)c(v)=1/1.414u>0 或 v>0 c(u)c(v)=1经过DCT变换后的矩阵数据自然数为频率系数，这些系数以F（0，0）的值最大，称为DC，其余的63个频率系数则多半是一些接近于0的正负浮点数，一概称之为AC。

3、量化图像数据转换为频率系数后，还得接受一项量化程序，才能进入编码阶段。量化阶段需要两个8*8矩阵数据，一个是专门处理亮度的频率系数，另一个则是针对色度的频率系数，将频率系数除以量化矩阵的值，取得与商数最近的整数，即完成量化。当频率系数经过量化后，将频率系数由浮点数转变为整数，这才便于执行最后的编码。不过，经过量化阶段后，所有数据只保留整数近似值，也就再度损失了一些数据内容，JPEG提供的量化表如下：

4、编码Huffman编码无专利权问题，成为JPEG最常用的编码方式，Huffman编码通常是以完整的MCU来进行的。编码时，每个矩阵数据的DC值与63个AC值，将分别使用不同的Huffman编码表，而亮度与色度也需要不同的Huffman编码表，所以一共需要四个编码表，才能顺利地完成JPEG编码工作。DC编码DC是彩采用差值脉冲编码调制的差值编码法，也就是在同一个图像分量中取得每个DC值与前一个DC值的差值来编码。DC采用差值脉冲编码的主要原因是由于在连续色调的图像中，其差值多半比原值小，对差值进行编码所需的位数，会比对原值进行编码所需的位数少许多。例如差值为5，它的二进制表示值为101，如果差值为-5，则先改为正整数5，再将其二进制转换成1的补数即可。所谓1的补数，就是将每个Bit若值为0，便改成1；Bit为1，则变成0。差值5应保留的位数为3，下表即列出差值所应保留的Bit数与差值内容的对照。

在差值前端另外加入一些差值的霍夫曼码值，例如亮度差值为5（101）的位数为3，则霍夫曼码值应该是100，两者连接在一起即为100101。下列两份表格分别是亮度和色度DC差值的编码表。根据这两份表格内容，即可为DC差值加上霍夫曼码值，完成DC的编码工作。

AC编码AC编码方式与DC略有不同，在AC编码之前，首先得将63个AC值按Zig-zag排序，即按照下图箭头所指示的顺序串联起来。

63个AC值排列好的，将AC系数转换成中间符号，中间符号表示为RRRR/SSSS，RRRR是指第非零的AC之前，其值为0的AC个数，SSSS是指AC值所需的位数，AC系数的范围与SSSS的对应关系与DC差值Bits数与差值内容对照表相似。如果连续为0的AC个数大于15，则用15/0来表示连续的16个0，15/0称为ZRL（Zero Rum Length），而（0/0）称为EOB（Enel of Block）用来表示其后所剩余的AC系数皆等于0，以中间符号值作为索引值，从相应的AC编码表中找出适当的霍夫曼码值，再与AC值相连即可。例如某一组亮度的中间符为5/3，AC值为4，首先以5/3为索引值，从亮度AC的Huffman编码表中找到1111111110011110霍夫曼码值，于是加上原来100（4）即是用来取[5，4]的Huffman编码1111111110011110100，[5，4]表示AC值为4的前面有5个零。由于亮度AC，色度AC霍夫曼编码表比较长，在此省略去，有兴趣者可参阅相关书籍。实现上述四个步骤，即完成一幅图像的JPEG压缩。参考资料[1] 林福宗 《图像文件格式（上）——Windows 编程》，清华大学出版社，1996年[2] 李振辉、李仁各编著，《探索图像文件的奥秘》，清华大学出版社，1996年[3] 黎洪松、成实译《JPEG静止数据压缩标准》，学苑出版社，1996年

希望有点帮助

---