基于多项式运算的无累积误差LoefflerDCT算法.docx

Ｃｕｍｕｌａｔｉｖｅｅｒｒｏｒ－ｆｒｅｅＬｏｅｆｆｌｅｒＤＣＴａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｐｏｌｙｎｏｍｉａｌｃａｌｃｕｌａｔｉｏｎｓ基于多项式运算的无累积误差ＬｏｅｆｆｌｅｒＤＣＴ算法沈永珞１，章媛２，杨迪威３，李璇１（１．广东财经大学信息学院，广东广州５１０３２０；２．国家知识产权局专利局专利审查协作广东中心，广东广州５１０５３０；３．中国地质大学（武汉）数学与物理学院，湖北武汉４３００７４）摘要：为避免离散余弦变换（ＤＣＴ）中的乘法操作以及运算过程中的累积误差，提出一种基于多项式运算的ＬｏｅｆｆｌｅｒＤＣＴ算法。将传统ＬｏｅｆｆｌｅｒＤＣＴ算法的流程分成３个模块：常规数值运算模块、多项式运算模块和结果再生模块；通过多项式运算，ＤＣＴ算法中涉及到的无理数乘法操作被分解成简单的整数加减及移位运算。分析和实验结果表明，该算法能完全避免乘法操作，且由于无计算累积误差，在图像处理过程中能保证较高的图像质量。关键词：离散余弦变换；多项式运算；无乘法ＤＣＴ；累积误差；算法设计中图法分类号：ＴＮ９１１．７３文献标识号：Ａ文章编号：１０００－７０２４（２０１４）１１－３８５５－０４ＳＨＥＮＹｏｎｇ－ｌｕｏ１，ＺＨＡＮＧＹｕａｎ２，ＹＡＮＧＤｉ－ｗｅｉ３，ＬＩＸｕａｎ１（１．ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｃｓ，ＧｕａｎｇｄｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＦｉｎａｎｃｅａｎｄＥｃｏｎｏｍｉｃｓ，Ｇｕａｎｇｚｈｏｕ５１０３２０，Ｃｈｉｎａ；２．ＰａｔｅｎｔＥｘａｍｉｎａｔｉｏｎＣｏｏｐｅｒａｔｉｏｎＣｅｎｔｅｒｏｆｔｈｅＰａｔｅｎｔＯｆｆｉｃｅ，Ｇｕａｎｇｚｈｏｕ５１０５３０，Ｃｈｉｎａ；３．ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓａｎｄＰｈｙｓｉｃｓ，ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＧｅｏｓｃｉｅｎｃｅｓ，Ｗｕｈａｎ４３００７４，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｏａｖｏｉｄｍｕｌｔｉｐｌｉｃａｔｉｏｎｓａｎｄｃｕｍｕｌａｔｉｖｅｅｒｒｏｒｓｄｕｒｉｎｇｔｈｅｄｉｓｃｒｅｔｅｃｏｓｉｎｅｔｒａｎｓｆｏｒｍ，ａｍｕｌｔｉｐｌｉｃａｔｉｏｎ－ｆｒｅｅＬｏｅｆｆｌｅｒＤＣＴａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｐｏｌｙｎｏｍｉａｌｃａｌｃｕｌａｔｉｏｎｓｗａｓｐｒｅｓｅｎｔｅｄ．Ｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｃｏｎｓｉｓｔｅｄｏｆｔｈｒｅｅｍｏｄｕｌｅｓｉｎｃｌｕｄｉｎｇｔｈｅｎｏｒ－ｍａｌｉｎｔｅｇｅｒｃａｌｃｕｌａｔｉｏｎｍｏｄｕｌｅ，ｔｈｅｐｏｌｙｎｏｍｉａｌｃａｌｃｕｌａｔｉｏｎｍｏｄｕｌｅａｎｄｔｈｅｆｉｎａｌｒｅｓｕｌｔｒｅｃｏｎｓｔｒｕｃｔｉｏｎｍｏｄｕｌｅ．Ａｔｔｈｅｍｅａｎｗｈｉｌｅ，ｔｈｅｍｕｌｔｉｐｌｉｃａｔｉｏｎｓｗｉｔｈｉｒｒａｔｉｏｎａｌｃｏｎｓｔａｎｔｖａｌｕｅｓｉｎｔｈｅＤＣＴｃａｌｃｕｌａｔｉｏｎｓｗｅｒｅｒｅｐｌａｃｅｄｂｙｔｈｅｉｎｔｅｇｅｒａｄｄｉｎｇａｎｄｓｈｉｆｔｏｐｅｒａｔｉｏｎｓｔｈｒｏｕｇｈｐｏｌｙｎｏｍｉａｌｔｒａｎｓｆｏｒｍｓ．Ｔｈｅａｎａｌｙｓｉｓａｎｄｅｘｐｅｒｉｍｅｎｔｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｍｕｌｔｉｐｌｉｃａｔｉｏｎｓｃａｎｂｅａｖｏｉｄｅｄａｎｄｔｈｅｈｉｇｈｉｍａｇｅｑｕａｌｉｔｙｃａｎｂｅａｃｈｉｅｖｅｄｄｕｅｔｏｎｏｎｅｃｕｍｕｌａｔｉｖｅｅｒｒｏｒｓｕｓｉｎｇｔｈｉｓｍｅｔｈｏｄ．Ｋｅｙｗｏｒｄｓ：ＤＣＴ；ｐｏｌｙｎｏｍｉａｌｃａｌｃｕｌａｔｉｏｎ；ｍｕｌｔｉｐｌｉｃａｔｉｏｎ－ｆｒｅｅＤＣＴ；ｃｕｍｕｌａｔｉｖｅｅｒｒｏｒ；ａｌｇｏｒｉｔｈｍｄｅｓｉｇｎ引言０１ＬｏｅｆｆｌｅｒＤＣＴ算法简介离散余弦变换（ＤＣＴ）被广泛应用于图像和视频编ＬｏｅｆｆｌｅｒＤＣＴ算法最早提出于１９８９年，和其他快速算法相比，该算法实现８点一维ＤＣＴ变换只需要１１次乘法和２９次加法运算，其乘法器的使用数量降到了理论的极值。完整的ＬｏｅｆｆｌｅｒＤＣＴ算法由４个阶段组成，其信号运算流程如图１所示，符号解释见表１。其中，涉及到乘法操作的分别位于Ｓｔａｇｅ－２和Ｓｔａｇｅ－３中的ｋｃｎ模块以及ｓｔａｇｅ－４中的倍乘因子运算。对于ＬｏｅｆｆｌｅｒＤＣＴ算法的研究一直是国内外研究的热点。文献［５］发表了一种基于Ｌｏｅｆｆｌｅｒ算法的１６点快速码、特征提取和恢复等领域，并已有大量的研究通过蝶形算法及整数运算等方法，致力于提高其运算速度并降低其运算复杂度［１－４］。但是，在大数据量以及高图像质量要求的应用中，比如ＨＥＶＣ等，整数ＤＣＴ运算的精度影响着编解码后视频图像的质量，其原因在于运算过程中无理数参与的运算产生的累积误差。因此，设计高效算法，实现无乘法、无运算误差累积的ＤＣＴ运算具有极其重要的意义。收稿日期：２０１３－１１－２８；修订日期：２０１４－０２－２０基金项目：国家自然科学基金青年科学基