基于多项式变换的二维整型离散余弦变换快速算法

第２６卷第７期　计算机应用　Ｖｏ１．２６　Ｎｏ．７　２００６年７月　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｊｕｌｙ　２００６　文章编号：１００１—９０８１（２００６）０７—１６２０—０３　基于多项式变换的二维整型离散余弦变换快速算法　李艳辉，李军　（暨南大学珠海学院计算机系，广东珠海５１９０７０）　（ｆｌｌｊｙｈ＠ｊｎｕ．ｅｄｕ．ｃｎ）　摘要：提出了一种基于多项式变换的二维整型离散余弦变换（ＤＣＴ）快速算法，利用多项式变换　将二维ＤＣＴ变换的计算转化为一系列一维ＤＣＴ变换及其变换系数的求和运算，减少了乘法和加法　的计算量；利用提升矩阵，实现了整型ＤＣＴ变换，进一步提高了运算效率的同时，使信号可精确重构。　关键词：视频压缩；多项式变换；离散余弦变换　中图分类号：ＴＰ３９１．４１　文献标识码：Ａ　Ｆａｓｔ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｉｎｔｅｇｅｒ　２Ｄ－ＤＣＴ　ｂａｓｅｄ　ｏｎ　ｐｏｌｙｎｏｍｉａｌ　ｔｒａｎｓｆｏｒｍ　ＬＩ　Ｙａｎ—ｈｕｉ，ＬＩ　Ｊｕｎ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ，Ｚｈｕｈａｉ　Ｓｃｈｏｏｌ　ｆｏＪｉｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｕｈａｉ　Ｇｕａｎｇｄｏｎｇ　５１９０７０，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａ　ｐｏｌｙｎｏｍｉａｌ　ｔｒａｎｓｆｏｒｍ—ｂａｓｅｄ　ｆａｓｔ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｉｎｔｅｇｅｒ　２Ｄ　Ｄｉｓｃｒｅｔｅ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｍｒ（２Ｄ—ＤＣＴ）Ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅ　２Ｄ—ＤＣＴ　Ｗａｓ　ｔｒａｎｓｆｏｒｍｅｄ　ｔｏ　ｓｏｍｅ　１Ｄ—ＤＣＴ　ａｎｄ　ｓｕｍｍｉｎｇ　ｃａｌｃｕｌａｔｉｏｎ　ｂｙ　ｐｏｌｙｎｏｍｉａｌ　ｔｒａｎｓｆｏｒｍ，　ＳＯ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ　Ｗａｓ　ｒｅｄｕｃｅｄ．Ｔｈｅ　ｉｎｔｅｇｅｒ　ＤＣＴ　Ｗａｓ　ｉｍｐｌｅｍｅｎｔｅｄ　ｂｙ　ｌｉｆｔｉｎｇ　ｍａｔｒｉｘ　ｔｏ　ｐｒｏｍｏｔｅ　ｅｆｆｉｃｉｅｎｃｙ，ａｎｄ　ｔｈｅ　ｔｒａｎｓｆｏｒｍｅｄ　ｓｉｇｎａｌ　ｃｏｕｌｄ　ｂｅ　ｒｅｃｏｎｓｔｒｕｃｔｅｄ　ｃｏｍｐｌｅｔｅｌｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｖｉｄｅｏ　ｃｏｍｐｒｅｓｓｉｏｎ；ｐｏｌｙｎｏｍｉｌａ　ｔｒａｎｓｆｏｒｍ；Ｄｉｓｃｒｅｔｅ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｒｍ（ＤＣＴ）　０　引言　ＤＣＴ变换的计算可以转化为，ｖ个一维ＤＣＴ变换及其变换系　数的求和运算，其中求和运算可以通过多项式变换计算　］，　对高清晰度、高压缩率的视频需求正在高速增长，离散余　减少了加法运算量。一维ＤＣＴ矩阵可以分解为若干个旋转　弦变换作为视频压缩技术的重要组成部分，起到了关键作用。　矩阵，进一步可转化为提升矩阵，实现了整型ＤＣＴ变换　］。　这一方面是因为对于真实图像而言，ＤＣＴ变换是最接近Ｋ－Ｌ　整型ＤＣＴ变换能够完全重构，同时由于定点数的运算比浮点　变换的正交变换，去相关的效果良好；另一方面ＤＣＴ变换算　数的运算快得多，整型ＤＣＴ比浮点ＤＣＴ的运算速度快，具有　法简单，编码效率高，易于硬件实现。因此，ＤＣＴ算法成为很　很好的适用性。　多图像和视频国际标准（ＪＰＥＧ，Ｈ．２６Ｘ，ＭＰＥＧ．１／２／４等）的核　在求解２Ｄ—ＤＣＴ的过程中仅含有加法和提升矩阵的运算，　心算法。　所以在有限字长运算时，２Ｄ－ＤＣＴ反变换可精确重构输入信号。　由于计算机用有限字长表示浮点数，浮点ＤＣＴ算法在运　为了叙述和推导的方便，若不加说明，所提到的ＤＣＴ变换都是　算过程中产生舍入误差，因此是不可逆的，这限制了它在数据　非归一化的。所得到的变换结果乘以归一化因子，可以得到正　无损压缩中的应用。另外，在不同的机器上对同一数据进行　交归一的变换结果；特别地，如果ＤＣＴ变换的结果需要量化处　ＤＣＴ变换，其结果有微小的差异，造成同一视频在不同的设备　理，则归一化因子与量化步长合并以减少计算量　］。　上的显示效果有差异。这些都不利于高清晰度视频的压缩。　综Ｅ所述，二维整型ＤＣＴ快速算法的步骤为：１）对输入的，ｖ　因为ＤＣＴ是视频编码器的重要组成部分，ＤＣＴ算法的性　×Ｎ矩阵，按照重新排列的顺序执行，ｖ个１Ｄ—ＤＣＴ变换；２）进行　能对整个视频编码器的效率具有重要影响，因此，提出了一种　多项式变换；３）根据变换后多项式的系数进行２Ｄ．ＤＣＴ。　基于多项式变换的二维整型ＤＣＴ快速算法，既能实现信号的　２　二维ＤＣＴ算法的转换　完全重构，同时也提高了计算效率。　（：）　１　算法设计　（ｚ）　使ＤＣＴ矩阵乘以适当的放大因子，然后用整型数代替浮　（：）　点型的矩阵元素，可以实现整型ＤＣＴ变换。近年来，通过分解　（ｚ）　ＤＣＴ矩阵，然后用提升矩阵乘积来构造整型ＤＣＴ的方法逐渐　（ｚ）　成为研究热点ｕ　Ｊ，与过去的方法相比，这种方法除了具有完　０）　全重构的特点外，计算效率得到了提高，同时易于硬件实现。　（ｚ）　在图像和视频处理应用中主要使用二维ＤＣＴ变换，一般　０）　一　一　地，通过一维整型ＤＣＴ变换和行列算法可以实现二维整型　图ｌ　快速多项式变换算法流程　ＤＣＴ变换。根据二维ＤＣＴ矩阵元素的规律性，二维（Ｎ×Ｎ）　利用多项式变换可将二维ＤＣＴ算法转换成一系列一维　收稿日期：２００６－０２—１３；修订日期：２００６一ｏ４－２１　基金项目：暨南大学引进人才基金资助项目（ＩＭＪＺＫＹ００４）　作者简介：李艳辉（１９７９一），女，湖南邵阳人，硕士，主要研究方向：图像处理、ＣＡＤ；李军（１９７３一），男，内蒙古赤峰人，讲师，博士。主要研　究方向：视频信号处理、编译理论．　维普资讯 http://www.cqvip.com

第７期　李艳辉等：基于多项式变换的二维整型离散余弦变换快速算法　ＤＣＴ算法转换成一系列一维的ＤＣＴ变换。　１６２１　的ＤＣＴ变换，与行列法不同的是可以更有效地减少计算量。　二维ＤＣＴ算法可表示为：　通过多项式变换的方法，可以减少求Ａ（　，ｚ）和Ｂ（ｋ，ｚ）　ｘ（ｋ’ｆｚ）：芝芝　＇）＝∑∑　（ｎ，ｍ）…ｓｍ）…ｓ　　，０　＝　０　…　．’　（１）　所需的加法运算次数。由Ａ（ｋ，ｚ），Ｂ（ｋ，ｚ）为系数生成多项式：　Ｎ一１　２Ⅳ一１　‰　ｃ。ｓｃｏ　‘＿　—一　　ｋ，ｌ：０　１一，ｕ，，…，　一　Ⅳ一１（　）＝∑Ｂ（ｋ，　一∑Ａ（ｋ，２Ｎ一　ｌ＝０　一ｆ＝Ｎ　１　２Ｎ一１　若将输入ｘ（ｎ，ｍ）重新排列为：　Ｙ（ｎ，ｍ）＝ｘ（２ｎ，２ｍ）　Ｙ（Ｎ—ｎ一１，ｒｔｌ，）＝ｘ（２ｎ＋１，２ｍ）　Ｙ（ｎ，Ｎ—ＩＴＩ，一１）＝ｘ（２ｎ，２ｍ＋１）　Ｙ（Ｎ—ｎ一１，　Ⅳ一ｍ一１）＝ｘ（２ｎ＋１，２ｍ＋１）　ｍｏｄｚ２　＋１＝Ｄ　Ｕ　ｌ　Ｕ　＝∑∑Ｄｅ［（４ｐ＋１）．ｉ｝一　ｍｏｄ　＋ｚ　＋１　２　一ｌ　Ｃｋ（ｚ）ｚｋ　ｏｏｄ　ｒ（５）　其中Ｃｋ（　）＝　（　）　ｍｏｄ　Ｚ２　＋１，　（　）＝∑Ｄ　（　）　‘　，　＝０，１，…，Ｎ一１。注意到ＣＮ一＾（　）＝Ｃｋ（　Ｉ１）ｒｏｏｄ　其中：ｍ，ｎ＝０，１，…，Ｎ／２—１　则Ｘ（　，１）可表示为：　ｘ（ｋ＇ｆ）：　，ｍ）－ｃｏｓ　ｚ）＝∑∑），（ｎ，ｍ）－ｃｏｓ　，…＝　…　＋１，根据该对称性和多项式变换的快速算法，多项式变换　．‘　一，Ⅳ一１　（　）的计算流程如图１所示，其中虚线是不需要实际计算的　步骤。这样，计算多项式变换　（　）从而得到　（　），然后通过　（　）的系数，可以求得二维ＤＣＴ变换的结果Ｘ（ｋ，ｚ）。　０　０　ｃ。ｓ　＝０，　３　整型ＤＣＴ变换的实现　设Ｐ（ｍ）＝［（４ｐ＋１）－／ｔ＇ｌ，　Ｐ］ｒｏｏｄ　Ｎ则：　一Ｘ（ｋ，１）＝［Ａ（ｋ，Ｉ）＋Ｂ（　，ｆ）］／２　其中：　Ａ（　，１）＝　Ｎ－Ｉ　Ｎ－Ｉ维整型ＤＣＴ变换是实现二维整型ＤＣＴ变换的基础，好　的一维ＤＣＴ算法可以有效地提升二维ＤＣＴ的性能。对Ⅳ（Ⅳ　＝２　，ｉ≥２）点ＤＣＴ变换，可以用迭代算法分解为２　Ｘ２的旋　ｙ（ｐ（ｍ）’ｍ）ｃｏｓ　业业　（２）　（３）　转矩阵运算和蝶型运算，其算法复杂度约为倍长ＤＦＩ＂算法的　１／６。设ｌＤ．ＤＣＴ变换为：　Ｂ（ｋ，Ｚ）＝　［Ｘ］＝［Ａ　］［ｘ］　［Ａ　］＝［Ｃ（ｋ）－ｃｏｓ（２ｉ＋１）ｋ￣／（２Ｎ）］　∑∑ｙ（ｐ（ｍ），ｍ）ｃ。ｓ　ｎ＝０　＝０　ｉ，ｋ＝０，１，…，｜，ｖ一１　（６）　ｊ｝＝１，２，…，Ｎ一１　令：　㈤令：　（　）＝∑）），（ｐ（ｍ），ｍ）ｃｏｓ　Ｐ，ｉ＝０，１，…，Ⅳ一１　：　Ｎ－Ｉ其中：ｃ（．ｉ｝）：』１／４￣－，　＝０　Ｌ１，　则：Ａ（．｝ｉ，ｚ）＝∑Ｄ　［（和＋１）．ｉ｝＋ｚ］，　口　Ｕ　一如果将［Ａ　］的行序按照位反转的次序重排位　，则　［Ａ　］可以写成迭代形式：　Ｉ　Ｂ（ｋ，ｚ）＝∑　［（和＋１）　一ｚ］　［ＡＮ　（上下）反转矩阵：　ｉ，　＝０，１，…，Ｎ／２—１　【Ｕ。Ｎ／２　乏　】　］　墨　若重新排列ｙ（ｐ（ｍ），Ｉ１＂７，）为），（２ｍ）＝），（ｐ（ｍ），ｍ），ｙ（２ｍ＋　１）＝ｙ（ｐ（Ｎ—ｍ一１），＾ｆ—ｍ一１１，ｍ＝ｏ，１，…，５Ｉ／２—１，则：　其中Ｐ，为行交换矩阵，　为单位矩阵，　为　的左右　［　］＝　）…ｓ堕　）＝鬟ｙ（ｍ）ｃｏｓ　，ｍ．０　，一’Ⅳ－１（４）　式（４）表示一维ＤＣＴ变换。这样，就将式（１）的二维　图２用８点ＤＣＴ变换为例说明了ＤＣＴ矩阵的因子化过程。　Ｃ１／４　＼　／　一　．　＼／　一　一　＼　／一　一　Ｖ　Ｖ　八　／＼　＼／　＼／一　一　／＼　一一　人入入　Ｖ　＼／　．　．　Ｖ　八ＳＳ１／４　Ｉ一．一ＣＣ３／１８／４．　Ｉ　　Ｖ￥八一３￥／３８／　８　Ｃ３１８　Ｃ７／１６　八／＼一一一　－Ｃｌ／４＿×＼／　ｎ　一ｃ　／＼一一　／＼一一．八　：：×　×　－。Ｓ３ｎ／６１６　／　＼　一　一　一　一Ｃ１／４一Ｖ／＾＼／＼一／＼Ｓ７／１一６Ｃ　３／１６－　．　．Ｃ７／１６　图２　１Ｄ－ＤＣＴ矩阵的因子化　麟转矩阵可以分解为提升矩阵：　［　卜［　【　【　，　维普资讯 http://www.cqvip.com