Chen快速DCT实现.docx

Chen的快速DCT算法一、原始DCT变换原理一维DCT变换定义对于离散函数f(j),j=0,1…,N-1,(N=)一维离散余弦变换（1-D DCT）定义为：F(k)= ;K=0,1,…,N-1其逆变换公式（1-D IDCT）为：f(j)= ; （1） j=0,1,…,N-1其中：c(k)=通过直接计算，当N=8时，利用公式（4-1）进行DCT变化需要64次乘法和56次加法运算。二维DCT变换定义一维离散余弦变换的定义可推广到二维的情形，对于离散函数f(i,j),i=0,1,…,N-1;j=0,1,…,M-1,二维离散余弦变换（2-D DCT）定义为：F(u,v)= ; （2）u=0,1,…N-1;v=0,1,…,M-1,其中：c(u),c(v)=取N=M=8时，利用公式（4-3）进行直接计算需要4096次乘法和3584次加法，通常利用DCT的可分解的性质，先进行8行一维DCT变换，在进行8列一维DCT变换，可将计算量减少为直接计算的1/4，需要1024次乘法和896次加法。二、Chen的快速DCT原理离散余弦变换（DCT for Discrete Cosine Transform）是与傅立叶变换相关的一种变换，它类似于离散傅立叶变换（DFTforDiscrete Fourier Transform）,但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅立叶变换，这个离散傅立叶变换是对一个实偶函数进行的（因为一个实偶函数的傅立叶变换仍然是一个实偶函数），在有些变形里面需要将输入或者输出的位置移动半个单位(DCT有8种标准类型，其中4种是常见的)。离散余弦变换(DCT)已经成为数字信号处理和图像处理的一种重要手段，但是其直接算法的计算量太大，速度太慢。在Chen以前一般使用DFT来实现DCT，1977年，W.H,Chen等人根据变换矩阵具有对称性，第一次用稀疏矩阵分解法得到DCT的一种快速算法，计算速度优于其他算法，仅需较少的乘法和加法。稀疏矩阵是这样定义的：设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即sm×n)，则称A为稀疏矩阵。因为稀疏矩阵和DCT的系数有非常相近之处，都是只取很少一部分，因此利用稀疏矩阵分解法可以简化计算。以下是Chen的快速DCT（1D）算法原理的具体介绍：由公式（1）可知，对于N1数据矢量的DCT变换可表示为如下矩阵形式：其中; j,k=0,1,…,N-1,是变换后的N1的系数，Chen的快速算法正是基于对矩阵的分解，首先我们可以将其表示为如下的循环形式：当N=2 时，可以很容易得到一个22的DCT变换矩阵：公式（4）中，定义如下：是一个置换矩阵，用于将变换后的系数下标按照自然规律排序，矩阵可以分解为（2）个矩阵相乘的形式：这（2）个矩阵又可以分为四种类型：类型1：，表示第一个矩阵；类型2： ,表示最后一个矩阵；类型3：，表示第奇数个矩阵；类型4：，表示第偶数个矩阵；的定义如下：其中：表示一个阶数为N/2的单位对角阵表示一个阶数为N/2的单位对角阵====（8）当i下面我们来详细讨论组成矩阵的四种不同类型的矩阵：类型一：第一个矩阵的组成结构是主对角线上从左上方到中间用来填充，从中间到右下角用填充，然后在副对角线上，从右上角到中间用填充，最后从中间到左下角用填充。其中是按序倒置的，即=N/2+j-1，j=1,2,…,N/2-1。类型二：最后一个矩阵的结构是主对角线由、、和连接而成，副对角线由、、和连接而成。类型三：第奇数个矩阵主对角线上结构为从左上角到中间由、、和(i=N/(),j=1,2,…i/8)连接，右下角由、、和( j=i/8+1,…,i/4)连接。副对角线上，右上角由、、、连接，左下角则由、、、连接而成。类型四：第偶数个矩阵的构成是主对角线交替由和构成，其中l代表或者的阶数，。公式（9）是的通式表达式：特别的，当N=16时，可以得到的组成结构如下：要求计算的复杂度可以通过以下式子来得到：其中（11a）为所需加法的个数，（11b）为所需乘法的个数。对于的加法个数从式（9）中可以和容易得到为N-2个阶段的矩阵分解，乘法个数只由第奇数个矩阵的计算量决定，其中第一个为N,最后一个为N/4，其余的N-3个矩阵每一个为N/2，因此我们可以得到：对于N=2时，我们从式（5）中已知：由递归迭代算法，并将（12）带入（11），我们可以得到：对于一个8点的1D DCT可以计算出所需的加法数为26，乘法数为16 。与利用公式（4-1）进行DCT变化需要64次乘法和56次加法运算相比，有了很大的提高，尤其是在数据量急剧增加时，使DCT计算速度得到很大的提高。下图是仿FFT的跌形图，得到