求DCT算法的快速算法？
除了利用FFT的那种，还有什么快速算法？ 问题点数：0、回复次数：12Top
1 楼bezero（）回复于 2005-04-04 12:46:15 得分 0
upTop
2 楼qiangqiang1112（强强）回复于 2005-04-05 09:48:51 得分 0
好象就是fft那种，
或者fft中，全部使用整数做计算……浮点数计算很浪费时间的
当然效果肯定很烂了Top
3 楼bezero（）回复于 2005-04-09 12:17:07 得分 0
upTop
4 楼Darnshong（旋风）回复于 2005-04-10 16:47:20 得分 0
本科毕业设计作的就是这个，采用FFT方法要涉及到复数，比较慢，可以直接在实数或中进行，比较快！Top
5 楼Darnshong（旋风）回复于 2005-04-10 16:51:52 得分 0
附1.1 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;
//to delete []C;
}
Top
6 楼Darnshong（旋风）回复于 2005-04-10 16:52:35 得分 0
IDCT就不贴啦，反着进行就可以啦！Top
7 楼gamedragon（gamedragon）回复于 2005-04-11 10:00:37 得分 0
不出意外，Intel的网站上就应该有，而且是用SSE指令的，速度绝对可以保证。Top
8 楼bezero（）回复于 2005-04-11 12:25:45 得分 0
Intel的DCT优化算法不能在ARM上用吧？
我要在ARM实现jpeg软压缩。Top
9 楼gamedragon（gamedragon）回复于 2005-04-11 18:46:23 得分 0
用ARM？ARM处理这种数据密集型的计算能不能满足需要啊？
我们的东西也将要在ARM上面作，这种大量的数据运算全交给DSP去做了。Top
10 楼dsgsos（阿光）回复于 2005-04-30 00:31:56 得分 0
upTop
11 楼stonesky（流星雨）回复于 2005-04-30 11:41:17 得分 0
MARKTop
12 楼alenwelkin（助人~~~为乐）回复于 2005-05-05 13:56:36 得分 0
我们做固定/移动终端，现在用过的DSP只能解baseline4:4:1及4:2:2格式的JPEG，再去搞个DSP去解JPEG不现实，但用CPU去解又比较慢，感觉还是libjpeg效率不高，据我所知，目前libjpeg所使用的IDCT算法复杂度是12步乘法&32步加法，有谁研究过比这更快的算法？请不吝赐教。
Email：alenwelkin@126.com
QQ:6279759Top
