一、引言
DCT变换是数字图像处理中重要的变换，很多重要的图像算法、图像应用都是基于DCT变换的，如JPEG图像编码方式。对于大尺寸的二维数值矩阵，倘若采用普通的DCT变换来进行，其所花费的时间将是让人难以忍受甚至无法达到实用。而要克服这一难点，DCT变换的快速算法无非是非常吸引人的。
就目前而言，DCT变换的快速算法无非有以下两种方式：
1．由于FFT算法的普便采用，直接利用FFT来实现DCT变换的快速算法相比来说就相对容易。但是此种方法也有不足：计算过程会涉及到复数的运算。由于DCT变换前后的数据都是实数，计算过程中引入复数，而一对复数的加法相当于两对实数的加法，一对复数的乘法相当于四对实数的乘法和两对实数的加法，显然是增加了运算量，也给硬件存储提出了更高的要求。
2．直接在实数域进行DCT快速变换。显然，这种方法相比于前一种而言，计算量和硬件要求都要优于前者。
鉴于此，本文采用第二种方法来实现DCT变换的快速算法。
二、理论推导
限于篇幅，在此不能罗列，具体推导过程可参见《DCT快速新算法及滤波器结构研究与子波变换域图像降噪研究》华南理工大学博士论文。
三、程序实现
DCT快速变换
考虑到DCT变换中的系数要重复计算，可使用查找表来提高运行的效率，只要开始DCT变换之前计算一次，DCT变换中就可以只查找而无需计算系数。
void initDCTParam(int deg)
{
// deg 为DCT变换数据长度的幂
if(bHasInit)
{
return; //不用再计算查找表
}
int total, halftotal, i, group, endstart, factor;
total = 1 << deg;
if(C != NULL) delete []C;
C = (double *)new double[total];
halftotal = total >> 1;
for(i=0; i < halftotal; i++)
C[total-i-1]=(double)(2*i+1);
for(group=0; group < deg-1; group++)
{
endstart=1 << (deg-1-group);
int len = endstart >> 1;
factor=1 << (group+1);
for(int j = 0;j < len; j++)
C[endstart-j-1] = factor*C[total-j-1];
}
for(i=1; i < total; i++)
C[i] = 2.0*cos(C[i]*PI/(total << 1)); ///C[0]空着，没使用
bHasInit=true;
}
DCT变换过程可分为两部分：前向追底和后向回根
void dct_forward(double *f,int deg)
{
// f中存储DCT数据
int i_deg, i_halfwing, total, wing, wings, winglen, halfwing;
double temp1,temp2;
total = 1 << deg;
for(i_deg = 0; i_deg < deg; i_deg++)
{
wings = 1 << i_deg;
winglen = total >> i_deg;
halfwing = winglen >> 1;
for(wing = 0; wing < wings; wing++)
{
for(i_halfwing = 0; i_halfwing < halfwing; i_halfwing++)
{
temp1 = f[wing*winglen+i_halfwing];
temp2 = f[(wing+1)*winglen-1-i_halfwing];
if(wing%2)
swap(temp1,temp2); // 交换temp1与temp2的值
f[wing*winglen+i_halfwing] = temp1+temp2;
f[(wing+1)*winglen-1-i_halfwing] =
(temp1-temp2)*C[winglen-1-i_halfwing];
}
}
}
}
后向回根：
void dct_backward(double *f,int deg)
{
// f中存储DCT数据
int total,i_deg,wing,wings,halfwing,winglen,i_halfwing,temp1,temp2;
total = 1 << deg;
for(i_deg = deg-1; i_deg >= 0; i_deg--)
{
wings = 1 << i_deg;
winglen = 1 << (deg-i_deg);
halfwing = winglen >> 1;
for(wing = 0; wing < wings; wing++)
{
for(i_halfwing = 0; i_halfwing < halfwing; i_halfwing++)
{
//f[i_halfwing+wing*winglen] = f[i_halfwing+wing*winglen];
if(i_halfwing == 0)
{
f[halfwing+wing*winglen+i_halfwing] =
0.5*f[halfwing+wing*winglen+i_halfwing];
}
else
{
temp1=bitrev(i_halfwing,deg-i_deg-1); // bitrev为位反序
temp2=bitrev(i_halfwing-1,deg-i_deg-1); // 第一参数为要变换的数
// 第二参数为二进制长度
f[halfwing+wing*winglen+temp1] =
f[halfwing+wing*winglen+temp1]-f[halfwing+wing*winglen+temp2];
}
}
}
}
}
位反序函数如下：
int bitrev(int bi,int deg)
{
int j = 1, temp = 0, degnum, halfnum;
degnum = deg;
//if(deg<0) return 0;
if(deg == 0) return bi;
halfnum = 1 << (deg-1);
while(halfnum)
{
if(halfnum&bi)
temp += j;
j<<=1;
halfnum >>= 1;
}
return temp;
}
完整实现一维DCT变换：
void fdct_1D_no_param(double *f,int deg)
{
initDCTParam(deg);
dct_forward(f,deg);
dct_backward(f,deg);
fbitrev(f,deg); // 实现位反序排列
f[0] = 1/(sqrt(2.0))*f[0];
}
void fdct_1D(double *f,int deg)
{
fdct_1D_no_param(f,deg);
int total = 1 << deg;
double param = sqrt(2.0/total);
for(int i = 0; i < total; i++)
f[i] = param*f[i];
}
利用一维DCT变换来实现二维DCT变换：
void fdct_2D(double *f,int deg_row,int deg_col)
{
int rows,cols,i_row,i_col;
double two_div_sqrtcolrow;
rows=1 << deg_row;
cols=1 << deg_col;
init2D_Param(rows,cols);
two_div_sqrtcolrow = 2.0/(sqrt(double(rows*cols)));
for(i_row = 0; i_row < rows; i_row++)
{
fdct_1D_no_param(f+i_row*cols,deg_col);
}
for(i_col = 0; i_col < cols; i_col++)
{
for(i_row = 0; i_row < rows; i_row++)
{
temp_2D[i_row] = f[i_row*cols+i_col];
}
fdct_1D_no_param(temp_2D, deg_row);
for(i_row = 0; i_row < rows; i_row++)
{
f[i_row*cols+i_col] = temp_2D[i_row]*two_div_sqrtcolrow;
}
}
bHasInit = false;
}
IDCT快速变换
IDCT快速变换
初始化查找表：
void initIDCTParam(int deg)
{
if(bHasInit)
return; //不用再计算查找表
int total, halftotal, i, group, endstart, factor;
total = 1 << deg;
// if(C!=NULL) delete []C;
// C=(double *)new double[total];
// 由于正变换已经为C申请了空间，所以逆变换就需再申请空间了！
halftotal = total >> 1;
for(i = 0; i < halftotal; i )
C[total-i-1] = (double)(2*i 1);
for(group = 0; group < deg-1; group )
{
endstart = 1 << (deg-1-group);
int len = endstart>>1;
factor = 1 << (group 1);
for(int j = 0; j < len; j )
C[endstart-j-1] = factor*C[total-j-1];
}
for(i = 1; i < total; i )
C[i] = 1.0/(2.0*cos(C[i]*PI/(total << 1))); // C[0]空着没用
bHasInit=true;
}
IDCT变换过程也可分为两部分：前向追底和后向回根
逆风者
前向追底
void idct_forward(double *F,int deg)
{
int total,i_deg,wing,wings,halfwing,winglen,i_halfwing,temp1,temp2;
total = 1 << deg;
for(i_deg = 0; i_deg < deg; i_deg )
{
wings = 1 << i_deg;
winglen = 1 << (deg-i_deg);
halfwing = winglen >> 1;
for(wing = 0; wing < wings; wing )
{
for(i_halfwing = halfwing-1; i_halfwing >= 0; i_halfwing--)
{
if(i_halfwing == 0)
{
F[halfwing wing*winglen i_halfwing] =
2.0*F[halfwing wing*winglen i_halfwing];
}
else
{
temp1 = bitrev(i_halfwing,deg-i_deg-1);
temp2 = bitrev(i_halfwing-1,deg-i_deg-1);
F[halfwing wing*winglen temp1] = F[halfwing wing*winglen temp1]
F[halfwing wing*winglen temp2];
}
}
}
}
}
后向回根
void idct_backward(double *F, int deg)
{
int i_deg,i_halfwing,total,wing,wings,winglen,halfwing;
double temp1, temp2;
total = 1 << deg;
for(i_deg = deg-1; i_deg >= 0; i_deg--)
{
wings = 1 << i_deg;
winglen = total >> i_deg;
halfwing = winglen >> 1;
for(wing = 0; wing < wings; wing )
{
for(i_halfwing = 0; i_halfwing < halfwing; i_halfwing )
{
temp1 = F[wing*winglen i_halfwing];
temp2 = F[(wing 1)*winglen-1-i_halfwing]*C[winglen-1-i_halfwing];
if(wing % 2)
{
F[wing*winglen i_halfwing] = (temp1-temp2)*0.5;
F[(wing 1)*winglen-1-i_halfwing] = (temp1 temp2)*0.5;
}
else
{
F[wing*winglen i_halfwing] = (temp1 temp2)*0.5;
F[(wing 1)*winglen-1-i_halfwing] = (temp1-temp2)*0.5;
}
}
}
}
}
完整实现一维IDCT变换：
void fidct_1D_no_param(double *F, int deg)
{
initIDCTParam(deg);
F[0] = F[0]*sqrt(2.0);
fbitrev(F, deg);
idct_forward(F, deg);
idct_backward(F, deg);
}
void fdct_1D(double *f, int deg)
{
fdct_1D_no_param(f, deg);
int total = 1 << deg;
double param = sqrt(2.0/total);
for(int i = 0; i < total; i )
f[i] = param*f[i];
}
利用一维IDCT变换来实现二维IDCT变换：
void fidct_2D(double *F, int deg_row, int deg_col)
{
int rows,cols,i_row,i_col;
double sqrtcolrow_div_two;
rows = 1 << deg_row;
cols = 1 << deg_col;
init2D_Param(rows,cols);
sqrtcolrow_div_two = (sqrt(double(rows*cols)))/2.0;
for(i_row = 0; i_row < rows; i_row )
{
fidct_1D_no_param(F i_row*cols,deg_col);
}
for(i_col = 0; i_col < cols; i_col )
{
for(i_row = 0; i_row < rows; i_row )
{
temp_2D[i_row] = F[i_row*cols i_col];
}
fidct_1D_no_param(temp_2D, deg_row);
for(i_row = 0; i_row < rows; i_row )
{
F[i_row*cols i_col] = temp_2D[i_row]*sqrtcolrow_div_two;
}
}
bHasInit=false;
}
多线程的考量由于DCT变换要花费一定的时间，特别是在数据矩阵尺寸比较大的时候。此时，如果没有增加一个线程来执行DCT变换，操作界面可能因程序忙于DCT变换的计算而失去响应，所以，增加一个用来进行DCT变换的线程是十分必要的。
首先定义一个结构
typedef struct
{
int row;
int col;
double *data;
//double *data2;
//double *data3; // 在计算彩色图象的数据矩阵时，彩色图象用RGB三个分量
bool m_bfinished;
DWORD m_start,m_end; //以毫秒计，用来计算DCT变换所用的时间;
}RUNINFO;
DCT变换进程函数：
UINT ThreadProcfastDct(LPVOID pParam)
{
RUNINFO *pinfo = (RUNINFO*)pParam;
pinfo->m_start = ::GetTickCount();
fdct_2D((double *)pinfo->data, GetTwoIndex(pinfo->row), GetTwoIndex(pinfo->col));
pinfo->m_end = ::GetTickCount();
pinfo->m_bfinished = true;
return 1;
}
IDCT变换进程函数：
UINT ThreadProcfastIDct(LPVOID pParam)
{
RUNINFO *pinfo = (RUNINFO*)pParam;
pinfo->m_start = ::GetTickCount();
fidct_2D((double *)pinfo->data, GetTwoIndex(pinfo->row), GetTwoIndex(pinfo->col));
pinfo->m_end = ::GetTickCount();
pinfo->m_bfinished = true;
return 1;
}
四、程序运行
图1 普通DCT变换
图2 快速DCT变换
图3 快速IDCT变换
从以上可以看出，采用上述快速DCT变换对一幅256灰度的256＊256的图像进行DCT正变换只需94ms,IDCT逆变换也只需94ms，而如果采用普通DCT变换，所需时间要575172ms。由此可见，DCT快速变换的巨大的优势，计算速度快，效率高。
相关推荐
在VS2013环境下，我们需要首先安装并配置OpenCV库，然后才能使用其提供的函数进行DCT变换。 `DCT.cpp`和`DCT.h`文件很可能是包含这两个关键函数的源代码文件。在C++中，通常`.cpp`文件包含了函数的实现，而`.h`文件...
3. **8x8点DCT变换**：使用定义好的DCT矩阵，通过逐行逐列的点乘运算实现DCT变换。在MATLAB中，可以使用嵌套循环或向量化操作实现这一过程。 4. **乘加实现**：描述中提到的“通过乘加实现”指的是在计算过程中，仅...
在C++中实现DCT变换，首先需要理解二维DCT的计算过程，它分为两步：水平方向的DCT和垂直方向的DCT。具体步骤如下： 1. **水平方向DCT**： - 将8x8的图像矩阵拆分成8个1x8的行向量。 - 对每个行向量应用一维DCT...
DCT变换特别适用于具有对称性的信号，因为在这种情况下，其傅里叶变换仅包含余弦分量，这使得DCT具有直观的物理意义，并且在实际应用中更为高效。 ### DCT的矩阵乘法实现 在数字图像处理中，DCT通常应用于8x8或更...
本文将深入探讨如何利用MATLAB进行DCT变换，滤除高频分量并保留低频分量，以及查看处理后的图像结果。 首先，DCT变换是一种线性正交变换，它可以将图像从像素域转换到频率域。在频率域中，图像的信息被分解为不同的...
本话题将深入探讨如何在MATLAB环境下实现彩色图像的DCT变换。MATLAB是一个强大的数值计算软件，拥有丰富的图像处理函数库，非常适合进行此类操作。 一、DCT基本概念 DCT是一种线性正交变换，能够将图像数据从空间域...
3. **执行DCT变换：**调用`cvDCT`函数对整个图像进行DCT变换。这一步将原始图像从空间域转换到了频率域。 4. **提取8×8块：**为了进一步处理，需要从变换后的矩阵中提取8×8像素的子块。 ### 量化过程 量化是压缩...
5. `subtractor.v`和`adder.v`：这些模块分别实现了减法和加法操作，用于处理DCT变换过程中所需的并行计算。 6. `dct_2d.m`和`init.m`：这两个文件可能是MATLAB脚本，用于生成测试输入和验证Verilog实现的正确性。`...
2. 定义接口：DLL应提供一组函数或方法供其他程序调用，比如一个`DCT2D`函数接受二维数据数组并返回DCT变换后的结果。 3. 调用DLL函数：在需要进行DCT变换的地方，调用DLL提供的函数，并传递相应的参数。 4. 错误...
【数字图像处理中的DCT变换】 在图像处理领域，离散余弦变换（DCT）是一种广泛应用的技术，尤其在图像压缩中，如JPEG格式。相比傅里叶变换，DCT在计算效率上有显著优势，因为它仅涉及加法运算，而傅里叶变换则需要...
提供的仿真操作录像将指导用户一步步完成MATLAB环境中的实际操作，包括图像读取、分块、DCT变换、量化、编码、解码、反DCT变换以及图像显示等步骤，这对于初学者来说是一份宝贵的实践教程。 8. **适用人群**： 该...
这个压缩包包含了实现DCT变换的C++源代码，覆盖了1维和2维的变换，同时提供了逆变换功能。下面我们将详细探讨DCT变换及其在实际应用中的重要性。 **一、离散余弦变换** DCT是一种线性正交变换，它可以将一个信号或...
**基于DCT变换的图像压缩**是一种常见的数字图像处理技术，广泛应用于图像存储、传输和显示。在Matlab环境中，可以有效地实现这一过程。本文将详细介绍如何使用Matlab进行DCT（离散余弦变换）图像压缩，以及相关的...
### 基于DCT变换实现的图像数字编码 #### 一、引言 随着信息技术的发展，图像处理技术在各个领域发挥着越来越重要的作用。在众多图像处理技术中，基于离散余弦变换（Discrete Cosine Transform, DCT）的图像编码...
### DCT变换C代码解析与理解 #### 一、DCT变换原理简介 离散余弦变换（Discrete Cosine Transform, DCT）是一种广泛应用于图像处理和视频压缩技术中的数学变换方法。它将信号从空间域转换到频域，通过这种变换可以...
生成DCT变换矩阵，对8*8的变换矩阵产生基图像
【数字图像DCT变换课程设计】是一门针对数字图像处理领域的实践性教学活动，旨在让学生通过使用MATLAB软件深入理解DCT变换及其在图像压缩中的应用。在这个课程设计中，学生将不仅熟悉MATLAB仿真工具，还能掌握数字...
在描述中提到的"DCT变换及攻击检测代码"，这很可能是一个MATLAB程序，用于演示DCT变换的基本原理，并可能包含对图像篡改或攻击的检测算法。MATLAB是一种强大的数学计算环境，特别适合进行这种类型的数据处理和分析。...
在DCT文件夹中，你可能会找到一系列与DCT变换相关的Matlab脚本，包括图像的预处理、DCT变换、系数处理和后处理等步骤。而在DFT文件夹中，同样会有相应的脚本，演示如何用DFT进行图像分析和压缩。 通过这两个文件夹...
DCT变换是信号处理中的一个重要概念，特别是在图像压缩如JPEG格式中起到核心作用。它通过将图像的每个8x8像素块转化为系数矩阵，这些系数表示了图像在不同频率成分上的分布。 DCT变换的基本过程可以这样理解：原始...