数论变换算法的拓展与在图像压缩中应用.PDFVIP

第1卷 第3期 中国科技论文在线 SCIENCEPAPER ONLINE 2006 年 10 月 197 数论变换算法的拓展与在图像压缩中应用 张 虹，刘 兵 （中国矿业大学计算机学院，江苏 徐州 221008） 摘 要：本文研究并利用了数论变换的性质、特点以及快速算法的优势，结合图象数据的特点以及二维序列与 变换系数之间的关系，拓展了数论变换算法，提出了数论变换转置定理和周期性二维序列与变换系数关系定理 并给予证明。使用 CCITT 推荐的 8 幅二值图像进行验证和分析，结果表明，数论变换快速算法及提出的两个 定理，用于对图像数据的压缩是可行的，且分块适当可提高运算速度，减少存储空间，提高压缩比。本文算法 在图象压缩中应用具有较大的理论意义和应用价值，为数论变换在图像压缩中的应用迈出了实际应用的第一 步。 关键词：数论变换;整型变换;图像压缩;快速算法 中图分类号：TP391 文献标识码：A 文章编号：1673－7180(2006)03－0197－5 0 引言 浮点变换基础上采用提升方法重新构造得到。 经典的无损压缩方法如霍夫曼编码、算术编码 20世纪70年代初，Rader，Agarwal，Burrus等人 等，没有考虑图像数据本身的特点，图像编码率很 提出了构造整数模M剩余类环ZM上的DFT，即数论 低，难以满足现代图像处理的要求。为了改善这些 变换（Number Theoretic Transform, NTT），把数论 不足，国内外专家纷纷研究如何在传统浮点变换的 方法引入到数字信号处理中。与DCT和小波变换相 基础上构造整型可逆变换，并将其应用于图像无损 比，NTT变换没有舍入误差，不需要存储三角函数， 压缩，此类方法已成为当前图像压缩领域的研究热 在相同变换长度下运算速度优于DCT[9]。更重要的是 点[1~5]。 NTT本身就是整型变换，无须进行提升操作就可以 Daubechies 在文献[6 ]中叙述了提升的方法。如 达到完全可逆的变换。本文在研究数论变换原理、 果变换矩阵可以分解成多个主对角线元素为1的三 性质和快速算法的基础上，利用了NTT整型变换的 角形矩阵的乘积，那么 只要对每一个三角形矩阵分 性质、特点以及变换核固定和快速算法的优势，结 别找到它所对应的可逆整型变换，并按其分解顺序 合图象数据本身的特点以及二维序列与变换系数之 依次变换，就可以构造出整个变换的整型变换。基 间的关系，为使数论变换应用于图象压缩，提出了 于提升方案的第二代小波变换实现了图像的整数到 二维数论变换转置定理和周期性二维序列与变换系 整数的变换，而且图像的恢复质量与变换时边界采 数关系定理，定理为数论变换开拓了新算法，并为 用何种延拓方式无关，克服了第一代小波的缺陷。 整型无损图像压缩奠定了理论和应用基础。 但是整数小波变换后数据的动态范围要比第一代小 1 一维、二维数论变换 波