学士学位论文
3 DCT编码算法
DCT是英语Discrete Cosine Transform的简称，是N.Ahmed等人在1974年提出的正交变换方法。DCT常被认为是对语音和图像信号进行变换的最佳方法，因此也是在数据压缩中常用的一种变换编码方法。在视频压缩中，最常用的变换方法是DCT，DCT被认为是性能接近KLT的准最佳变换，其变换编码的主要特点有：
（1）在变换域里视频图像要比空间域里简单；
（2）视频图像的相关性明显下降，信号的能量主要集中在少数几个变换系数上，采用量化和熵编码可有效地压缩其数据；
（3）具有较强的抗干扰能力，传输过程中的误码对图像质量的影响远小于预测编码。通常，对高质量的图像，DCT变换编码只要求信道误码率。
DCT并不是对整幅图像一次编码，而是将图像分成N×N（一般N＝8，即64个像素块）等若干个子图像块分别处理。这是因为：
（1）小块图像变换的计算更容易；
（2）距离较远的像素之间相关性比距离较近的像素之间的相关性小。
3.1 一维DCT
设?x?m??是M个有限值的一维实数信号序列集合，m?0,1,完备正交归一函数系是
M?1，余弦变换的
1??0,t????M? （3-1） ????0,t??2cos??2k?1?,t??0,T??M2T?对这些函数在?0,T?内取M个样值，即得离散余弦变换矩阵T的元为
??a0m????a?km??1M?2m?1?k?,k?1,2,2cosM2M （3-2）
,M?1;m?0,1,M?1离散余弦变换（DCT）形式为
7
学士学位论文
1??2?y0????y??cos2?1???2M??M????y?M?1???M?1???cos?2M其矢量形式为
123?cos2M3?M?1??cos2M1??2??x0??2M?1????x?cos??1?（3-3） 2M??????x?M?1?3?M?1????cos?2M?Y?TX （3-4）
其中
T?2M??2m?1?k??,k,m?0,1,2,Ckcos????2M??M?MM?1
以求和形式表示，一维DCT为
M?1?2m?1?k?,k?0,1,2Y?k??C?k??x?m?cosM2Mm?0,M?1 （3-5）
其中
?2k?0?C?k???2?1k?1,2,?DCT的反变换（IDCT）的形式为
,M?1M?1???cos????x0???x?2??1????M?????xM?1?????其矢量形式为
121212coscos?2M3?cos2M?2M?1??2M??2M??y0?3?M?1?????ycos1???（3-6） 2M??????y?M?1?2M?1??M?1?????cos?2M?Y?TTX （3-7）
其求和形式为
M?1?2m?1?k?,m?0,1,2x?m??C?k??Y?k?cosm2Mk?0,M?1 （3-8）
其中
?2k?0?C?k???2?1k?1,2,?
,M?1 8
学士学位论文
3.2 二维DCT
设图像数据是一个M?N的矩阵，每个数据用x?m,n?表示。为了减弱或去除图像数据的空间相关性，用二维DCT将图像从空间域，即mn平面，转换到DCT变换域，即KL平面。同一维DCT一样，二维m?n阶DCT的分量表示形式也可写成求和形式，即
M?1N?1?2m?1?K?cos?2n?1?L?2Y?K,L??C?K?C?L???x?m,n?cos （3-9） 2M2NMNm?0n?0K?0,1,2,,M?1;L?0,1,2,N?1其中
?2K?0?C?K???2?1K?1,2,?在式（3-9）中变换核为
?2L?0?;C?L???2?1L?1,2,,M?1?
,M?12M （3-10）
?2m?1?K?CLcos?2n?1?L? =C?K?cos??2M2M若令
g?m,n,K,L??C?K?C?L?cos?2m?1?K?cos?2n?1?L?2M2m?1?K???U?m,K??C?K?cos??2M ??Vn,L?CLcos?2n?1?L???????2M则式（3-10）可分离成
g?m,n,K,L??U?m,K?V?n,L?
因此，式（3-9）可改写成
Y?K,L??M?1?N?1?2n?1?L??cos?2m?1?K?22C?K???C?L??x?m,n?cos?（3-10） MN2N2Mm?0?n?0?K?0,1,2,,M?1;L?0,1,2,N?1令
x??m,L??则有
2N?1x?m,n?V?n,L? ?Nn?02?MM?1m?0Y?K,L??C?K??x??m,L?m?0M?12m?1?K??cos2M?x??m,L?U?m,K?
可以看出，二维DCT实际上可以分解成双重一维DCT，即
（1）先以n为变量，对图像x?m,n?逐行进行一维DCT，最终得到变换结果
9
学士学位论文
x??m,L???2m?1?L??2N?1xm,ncos???Nn?02N2N?1?x?m,n?V?n,L? Nn?0（2）再对中间结果x??m,L?以m为变量，逐列进行第二个一维DCT，最终得到变换结果为Y?K,L?。那么式（3-10）就可以写成矩阵形式的二维DCT：
Y?TXTT （3-11）
其中
T?2M??2m?1?K??,K,m?0,1,2,CKcos????2M??M?M2M2n?1?L????,L,n?0,1,2,?C?L?cos?2N??N?N,M?1
即为式（3-3）中的M?M方阵。而
T?TT?1?,N?1
即为式（3-6）中的N?N方阵。
二维IDCT的表达式为
?2m?1?K?cos?2n?1?L?2M?1N?1x?m,n??CKCLYK,Lcos???????? （3-12） 2M2NMNm?0n?0 m?0,1,2,,M?1;n?0,1,2,N?1显然，二维IDCT变换核也是可分离的。
二维IDCT的矩阵表达式或写为
X?TTYT
（0，0） N-1 n x?m,n?（0，0） N-1 n 行变换 M-1 n x??m,L?（0，0） N-1 n 列变换 M-1 n Y?K,L?M-1 n 图 3.1 二维DCT的行、列分离过程
由此可知，二维DCT和IDCT的计算过程可用图 3.1形象表示，即先后进行两次一维DCT和IDCT变换。此方法被称为行、列分离法。
行、列分离算法的优点是： （1）结构简单直观；
（2）可直接利用一维DCT快速算法程序和硬件结构实现； （3）运算为M?N点和N?M点的两次一维DCT。
3.3 一维DCT快速算法
虽然可以直接考虑二维DCT的快速算法，即将其分解为两次一维DCT算法来实现，这样可以使其运算量有所减少，但真正实现起来远不如分离一维计算简捷直观。一维快
10
学士学位论文
速DCT算法可以通过仿效FFT、从IDCT导出快速余弦变换（FDCT）以及代数分解等方法获得。
3.3.1 仿效FFT算法
由于DCT和FFT这两种算法很相似，根据FFT算法，可将式（3-5）改写为
Y?k?? ? ?M?12m?1?k??2C?k??x?m?cosM2Mm?0?jk??2m?1???2?M?1?2MC?k?Re??x?m?e?Mm?0???? （3-13）
?M?1?j2?km??2jk?2C?k?Re?eM?x?m?e2M?Mm?0??令W?e?j2?2M，代入式（3-13），得
M?1?k?22Y?k??C?k?Re?W?x?m?Wkm? （3-14）
M?m?0?于是一维DCT正交变换可以利用FFT实现。其反变换也可同理写出。
其实离散傅里叶变换指数项通过欧拉公式ejx?cosx?jsinx和e?jx?cosx?jsinx进行分解后，其傅里叶变换实数部分对应于余弦项，其虚数部分对应于正弦项，因此离散余弦变换就可以从离散傅里叶变换的实数部分求得。
3.3.2 从IDCT导出的快速余弦变换（FDCT）
虽然利用DFT求DCT算法，而且也可以通过FFT来提高计算效率，但它并没有利用DCT实系数的特点。由于DCT的实系数的特点，利用递推关系，由DCT的逆变换我们可以导出一种快速的余弦变换算法。
将IDCT的分量表达式（3-8）重写如下：
x?m??M?1?2m?1?k?,m?0,1,2,2C?k??Y?k?cosM2Mk?0,M?1?2 k?0?C?k???2? 1 1?k?M?1?（3-15）
比较式（3-5）和式（3-8），可以发现DCT和IDCT的变换核是相同的。为了方便起见，将式（3-15）改写成
?x?m???Y?k?C2Mk?0M?1?2m?1?k （3-16）
式中
11