DCT快速变换
2010-07-25 20:45:40 来源:WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閻愵剙鍔ょ紓宥咃躬瀵鎮㈤崗灏栨嫽闁诲酣娼ф竟濠偽i鍓х<闁绘劦鍓欓崝銈囩磽瀹ュ拑韬€殿喖顭烽幃銏ゅ礂鐏忔牗瀚介梺璇查叄濞佳勭珶婵犲伣锝夘敊閸撗咃紲闂佽鍨庨崘锝嗗瘱闂備胶顢婂▍鏇㈠箲閸ヮ剙鐏抽柡鍐ㄧ墕缁€鍐┿亜韫囧海顦﹀ù婊堢畺閺屻劌鈹戦崱娆忓毈缂備降鍔庣划顖炲Φ閸曨垰绠抽悗锝庝簽娴犻箖姊洪棃娑欐悙閻庢矮鍗抽悰顕€宕堕澶嬫櫖濠殿噯绲剧€笛囧箲閸ヮ剙钃熼柣鏂挎憸閻熷綊鏌涢…鎴濇灈妞ゎ剙鐗嗛—鍐Χ鎼粹€茬凹缂備緡鍠楅幐鎼佹偩閻戣棄纭€闁绘劕绉靛Λ鍐春閳ь剚銇勯幒鎴濐伀鐎规挷绀侀埞鎴︽偐閹绘帩浼€缂佹儳褰炵划娆撳蓟濞戞矮娌柟瑙勫姇椤ユ繈姊洪柅鐐茶嫰婢т即鏌熼搹顐e磳闁挎繄鍋涢埞鎴犫偓锝庘偓顓涙櫊閺屽秵娼幏灞藉帯闂佹眹鍊曢幊鎰閹惧瓨濯撮柛鎾村絻閸撳崬顪冮妶鍡楃仸闁荤啿鏅涢悾鐑藉Ψ瑜夐崑鎾绘晲鎼粹剝鐏嶉梺缁樻尰濞叉﹢濡甸崟顖氱疀闂傚牊绋愮花鑲╃磽娴h棄鐓愭慨妯稿妿濡叉劙骞樼拠鑼槰闂佸啿鎼崐濠毸囬弶搴撴斀妞ゆ梻銆嬪銉︺亜椤撶偛妲婚柣锝囧厴楠炴帡骞嬮弮鈧悗濠氭⒑鐟欏嫭鍎楅柛妯衡偓鐔插徍濠电姷鏁告慨鐑藉极閸涘﹥鍙忔い鎾卞灩绾惧鏌熼崜褏甯涢柍閿嬪灦閵囧嫰骞掗崱妞惧缂傚倷绀侀ˇ閬嶅极婵犳氨宓侀柛鈩冪⊕閸婄兘鏌涘┑鍡楊伀妞ゆ梹鍔曢埞鎴︽倻閸モ晝校闂佸憡鎸婚悷锔界┍婵犲洦鍤冮柍鍝勫暟閿涙粓姊鸿ぐ鎺戜喊闁告瑥楠搁埢鎾斥堪閸喓鍘搁柣蹇曞仧绾爼宕戦幘璇茬疀濞达絽鎲¢崐顖炴⒑绾懎浜归悶娑栧劦閸┾偓妞ゆ帒鍟惃娲煛娴e湱澧柍瑙勫灴閹瑩寮堕幋鐘辨闂備礁婀辨灙闁硅姤绮庨崚鎺楀籍閸喎浠虹紓浣割儓椤曟娊鏁冮崒娑氬幈闂佸搫娲㈤崝宀勬倶閻樼粯鐓曢柟鑸妼娴滄儳鈹戦敍鍕杭闁稿﹥鐗犲畷婵嬫晝閳ь剟鈥﹂崸妤€鐒垫い鎺嶈兌缁犲墽鈧厜鍋撳┑鐘辩窔閸嬫鈹戦纭烽練婵炲拑绲垮Σ鎰板箳閹冲磭鍠撻幏鐘绘嚑閼稿灚姣愰梻鍌氬€烽懗鑸电仚濠电偛顕崗妯侯嚕椤愩倖瀚氱€瑰壊鍠栧▓銊︾節閻㈤潧校缁炬澘绉瑰鏌ュ箵閹烘繄鍞甸柣鐘烘鐏忋劌顔忛妷褉鍋撶憴鍕碍婵☆偅绻傞~蹇涙惞閸︻厾锛滃┑鈽嗗灠閹碱偊锝炲鍥╃=濞达綁顥撻崝宥夋煙缁嬪灝鏆遍柣锝囧厴楠炲鏁冮埀顒傜不婵犳碍鍋i柛銉戝啰楠囬悗瑙勬尭缁夋挳鈥旈崘顔嘉ч柛鈩兠棄宥囩磽娴e壊鍎愰柛銊ュ缁顓兼径瀣偓閿嬨亜閹哄秶顦︾€殿喖鐏濋埞鎴﹀煡閸℃浠梺鍛婎焼閸曨収娲告俊銈忕到閸燁垶宕愰崹顐e弿婵☆垳鍘ф禍楣冩倵濮樼偓瀚�

一、引言
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;
}
更多精彩
赞助商链接