首页资源分类电子电路模拟及混合电路 > 基于查表的无乘法DCT快速算法

基于查表的无乘法DCT快速算法

已有 445109个资源

下载专区

上传者其他资源

    电子电路热门资源

    本周本月全部

    文档信息举报收藏

    标    签:DCTJPEG

    分    享:

    文档简介

    Jpeg压缩算法中的DCT快速算法

    文档预览

    第30卷 第20期 Vol.30 № 20 计 算 机 工 程 Computer Engineering 2004年10月 October 2004 ·多媒体技术及应用 · 文章编号:1000—3428(2004)20 —0159—02 文献标识码:A 中图分类号: TP301.6 基于查表的无乘法DCT快速算法 杜相文1,陈贺新1,赵 岩2 (1.吉林大学南岭校区通信工程学院测控技术与仪器系,长春 130025;2.吉林大学通信工程学院通信工程系,长春 130012) 摘 要:为提高离散余弦变换(DCT)的运算速度,提出了一种高效、快速的无乘法DCT算法。该算法在不引入移位运算的前提下,利用查表 法去除了在DCT变换中所需的乘法运算,只需要有限步加法即可完成DCT,运算速度比JPEG中的传统算法提高了1.5倍多。所得到的数据 精 度与原始的DCT算法完全相同。该算法特别适用于图像信号的处理。 关键词:无乘法;查表;快速离散余弦变换 Multiplierless Fast DCT Algorithm Based on Look-up-table DU Xiangwen1, CHEN Hexin1, ZHAO Yan2 (1.Department of Survey and Control Technology and Equipment, College of Communication Engineering, Nanling Campus, Jilin University, Changchun 130025; 2. Department of Communication Engineering, College of Communication Engineering, Jilin University, Changchun 130012) 【 Abstract】A new efficient and fast multiplierless discrete cosine transform (DCT) algorithm is presented in order to increase the speed of DCT. Without shifting operation, the multiplierless method finishes DCT only by using addition. The computing speed of the method is more than 1.5 times faster than that of the classical algorithm used in JPEG. Furthermore, the precision of the transformed results is same as that of general DCT. This algorithm is especially suitable to image processing. 【Key words】Multiplierless; Look-up-table; Fast DCT 自从 Ahmed等 人第一 次提出 离散余弦 变换 (DCT)以来 , 它已被广泛应用于滤波、图像处理、数据压缩和其他一些领 域。在选取均方差准则下,KL变换对于一阶马尔科夫过程 来说是一种最优变换, 但其要求有关数据样本的统计资料, 且 无快速算法。而DCT不依赖于信号,它的性能与KL变换十 分接近,而且它有快速算法。因此,静止图像与活动图像编 码的国际标准(JPEG、MPEG-1和MPEG-2)中采用了DCT, 也使 DCT快速算法的研究愈发显得意义重大。 由于常规的DCT算法用到了较多的乘法和加法,因 此 DCT的快速算法都是以减少乘法和加法的运算次数为目的, 尤其是减少乘法的次数,因为在计算机运算中,做一次乘法 所耗机时要比加法多得多。在20世纪80年代至90年代初期, 人们对DCT快速算法的研究较多,并且取得了巨大的成功。 早在1977年,Chen[1]根据变换矩阵具有对称性,利用稀疏矩 阵分解法第一次提出了DCT的快速算法。1984年B.G.Lee[2]提 出了一种使用余割因子的DCT矩阵分解方法,得到 CooleyTukey式的简单结构,受到广泛重视。在文献[3]中Duhamel 将DCT看成是一种基于循环卷积的算法,并证明,对于一维 的8点DCT, 其乘法的理论下限值是11次,C. Loeffler[4]具体 实现了这种11步乘法的算法。从此以后,一维DCT快速算法 的研究进展缓慢。2000年,Trac. D. Tran[5]提出了一种DCT 的近似快速算法,在算法中也没有用到乘法,但使用了移位 运算。在国内,赵耀等人[6]也提出了一种“基于矩阵分解的 DCT快速算法”,但在该方法中也用到了12次乘法。 本文通过分析DCT中的余弦函数值,利用余弦函数的周 期性及对称性,并结合数字图像信号所有的取值都在0~255 之间的特点,提出了一种基于查表的没有乘法运算和移位运 算的快速DCT算法,使DCT只需有限步的加法运算即 可 完成。 1 基于查表的无乘法DCT(LBMDCT)算法 N 个 点 的 一 维 DCT 定 义 如 下 : 将 给 定 数 据 序 列 { f ( n ), n = 0 ,1 , Λ , N } 通过公式(1)变换为输出序列 {F (u), u = 0,1,Λ , N }。 F (u ) = ∑ 2 N −1 c ( u ) f ( n ) cos( π (2 n + 1)u )   (1) N n=0 2N 其中 c (u ) = ⎪⎧1 / ⎪⎩⎨1, 2, 当 u = 0; 其他 , u = 0,1,Λ , N −1 。 暂且抛开公式(1)前面的系数,取N=8,将求和符号后面 的所有余弦项展开如下所示: ⎧ n = 0 n =1 n = 2Λ Λ ⎪ ⎪ 1, 1, 1,Λ Λ , ⎪ ⎪ ⎪ cos( π ), 16 cos( 3π ), 16 cos( 5π ),Λ Λ , 16 ⎨ ⎪ ⎪ cos( 2π ), 16 cos( 6π ), cos(10π ),Λ Λ , 16 16 ⎪ ΛΛ ΛΛ ⎪ ⎪ cos( 7π ), cos( 21π ), cos( 35π ),Λ Λ , ⎩ 16 16 16 n =7 1 cos(15π ) 16 cos( 30π ) 16 cos(105π ) 16 u =0 u =1 u =2 u =7 令 Ci = cos( iπ ) 16 (2) 利用余弦函数的周期性,以及公式(3)所示的性质,得 到的一维8点DCT结果如公式(4)所示。 cos(π − iπ ) = − cos( iπ ) (3) 16 16 基金项目:国家自然科学基金资助项目(60172046) 作者简介:杜相文(1975-),男,博士生,主研方向:多维信号处 理,图像处理等; 陈贺新,博士、教授、博导;赵 岩,博士、讲 师 收稿日期:2003-10-08 E-mail:judxw@email.jlu.edu.cn —159— ⎧ ⎪ ⎪ 1 [f (0) + 22 f (1) + f ( 2 ) + Λ Λ + f ( 7 ) ] u = 0 ⎪ ⎪ ⎪ 1 2 [C 1 f (0) + C 3 f (1) + C 5 f (2) + Λ Λ − C1 f (7) ] u =1 ⎪ ⎪ ⎪ 1 [C 2 f ( 0 ) + C 6 f (1) − C 6 f ( 2 ) − Λ 2 Λ + C 2 f (7) ] u =2 F (u ) = ⎪ ⎨ 1 [C 3 f (0) − C 7 f (1) − C1 f (2) − Λ Λ − C 3 f (7)] u = 3 (4) ⎪2 ⎪ ⎪ ⎪ 1 2 [C 4 f (0) − C 4 f (1) − C 4 f (2) + Λ Λ + C 4 f (7) ] u =4 ⎪ ΛΛ ΛΛ ⎪ ⎪ 1 [C 7 f (0) − C 5 f (1) + C 3 f (2) − Λ Λ − C 7 f (7) ] u =7 ⎪2 ⎪⎩ 从公式(4)中可以看出,当u=4时,每一项前面的系数都 是 1 2 C4,所以可以提取公因子。为了简化计算,本文采取 与文献[4]相同的方法,即将最终结果F(u)( u=0,1, 2,…,7)都 放大为原来的 2 2 倍,这也与JPEG编码中所采用的方法 一致。F(u)的最终结果如公式(5)所示。这样,当u=0和u=4 时,可 以直接利用 加减法计算 出F(u)。为 了减少加法 的 次 数,本文采用了如图1、图2所示的方法。由于数字图像信号 具有一定的特殊性,即所有的取值都在0~255之间,这样就 可以把f(n)之前的系数预先进行计算并存成一个规模较小的 表以达到避开复杂乘法运算的目的。 ⎧ f (0) + f (1) + f (2) +Λ Λ + f (7) ⎪ ⎪ 2C1 f (0) + 2C3 f (1) + 2C5 f (2) + Λ Λ − 2C1 f (7) ⎪ F (u) = ⎪⎪ ⎨ 2C2 f (0) + 2C3 f (0) − 2C6 f (1) − 2C7 f (1) − 2C6 f (2) −Λ Λ + 2C1 f (2) −Λ Λ − 2C2 f (7) 2C3 f (7) ⎪ ⎪ f (0) − f (1) − f (2) + Λ Λ + f (7) ⎪ ΛΛ ΛΛ ⎪ ⎪⎩ 2C7 f (0) − 2C5 f (1) + 2C3 f (2) −Λ Λ − 2C7 f (7) u =0 u =1 u =2 u = 3 (5) u =4 u =7 f(0) f(7) F(0) f(3) f(4) f(2) f(5) F(4) f(1) f(6) 图1 F(0), F(4)快速求解方法图解 I(0) I(0) O(0) O(0) I(1) I(1) O(1) O(1)=I(0)+I(1) O(1)=I(0)-I(1) 图2 对图1中的运算单元进行说明 为了在查表时避免引入额外的乘法运算,提高查表速 度,针对每一个Ci (i=1,2,3, 5,6,7)建立一个对应的表Ti (i=1,2, 3,5,6,7)。这样,可以用f(n)作为表的索引,利用有限次加法 快速完成DCT运算。表的构造方法如公式(6)所示。 Ti[k] = k × Ci (6) 其中,i=1,2,3,5,6,7;k=0,1,2,…,255。 2 实验与性能比较 在DCT中所用的乘法次数和加法次数,尤其是乘法的次 数,是衡量DCT快速算法性能好坏的一个重要指标。在本文 的算法中,共用了50步加法来完成DCT。作为比较,将文献 中各算法及本文算法的运算量列于表1中。 —160— 算法 Loeffler[4] *Tran[5] 赵[6] LBMDCT 表1 各种算法的运算量比较 乘法(次数) 移位(次数) 11 —— —— 19 12 —— —— —— 加法(次数) 29 36 34 50 *文献[5]中的结果是一种近似结果 为了能够进行比较直观的比较,本文用文献[4]中的 算 法和本文的算法在奔腾4的计算机上进行了实验,实验结果 如表2所示。在实验过程中,将实验分为两类来做。第1类是 实现整型DCT;第2类是双精度浮点型DCT。 表2 算法的运行时间比较 数值类型 算法 运行时间(10-7s) 整型 Loeffler[4] LBMDCT 1.822 1.241 浮点型 Loeffler[4] LBMDCT 4.386 1.752 需要说明一点,在进行整型DCT时,为了保证运算 精 度,无论是使用文献[4]中的算法,还是使用本文的算法, 都要进行移位运算。即使如此,其运行速度仍然要比浮点型 快得多。从表2中可以看出,在进行整型DCT时,本文算 法 的运行速度比文献[4]中算法的运行速度提高了46.82%; 而 完成双精度浮点型DCT,本文算法的运行速度比文献[4] 提 高了1.5倍多。 3 结论 本 文 提 出 了 一 种 基 于 查 表 的 无 乘 法 DCT 快 速 算 法 (LBMDCT),它没有引入任何乘法运算和移位运算,只用了 50 次 加法 即完 成8 点的 一维 DCT 。 本算 法既 可以 实现 整 型 DCT,又可以实现浮点型DCT。而且,本文所设计的表较 小,大小只有256×6,所以对它的存储不是问题。本算法为 图像压缩和硬件设计提供了新的思路。 当然,本算法存在一定的局限性,就是它只能用来对离 散图像信号(或类似信号)做第一次DCT变换。然而,这丝毫 不影响它在图像压缩编码中的应用。基于查表的无乘法DCT 快速 算法可 以和文献 [4]中 的算法 相结合 应用于 JPEG 和 MPEG编码中来提高图像压缩编码的速度。 参考文献 1 Chen W A, Harrison C, Fralick S C. A Fast Computational Algorithm for the Discrete Cosine Transform.IEEE Transactions on Communications,1977,COM-25(9):1004-1011 2 Lee B G. A New Algorithm to Compute the Discrete Cosine Transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, 1984,ASSP-32(6): 1243-1245 3 Duhamel P, H'Mida H. New 2n DCT Algorithms Suitable for VLSI Implementation. Proceeding of IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP-87, Dallas, 1987- 04:1805-1808 4 Loeffler C, Ligtenberg A, Moschytz G.Practical Fast 1-D DCT Algorithms with 11 Multiplications. Proc. of Intl. Conf. on Acoustics, Speech, and Signal Processing, ICASSP '89,1989: 988-991 5 Tran T D. The BinDCT: Fast Multiplierless Approximation of the DCT. IEEE Signal Processing Letters, 2000, 7(6):141-144 6 赵 耀,季文铎,袁保宗. 一种基于矩阵分解的DCT快速算法. 北 方交通大学学报, 1994, 18(2):182-189

    Top_arrow
    回到顶部
    EEWORLD下载中心所有资源均来自网友分享,如有侵权,请发送举报邮件到客服邮箱bbs_service@eeworld.com.cn 或通过站内短信息或QQ:273568022联系管理员 高进,我们会尽快处理。