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

《数论变换算法的拓展与在图像压缩中应用new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn数论变换算法的拓展与在图像压缩中应用11张虹，刘兵1（中国矿业大学计算机学院，江苏，徐州221008）hongzh@cumt.edu.cn摘要:本文研究并利用了数论变换的性质、特点以及快速算法的优势，结合图象数据的特点以及二维序列与变换系数之间的关系，拓展了数论变换算法，提出了数论变换转置定理和周期性二维序列与变换系数关系定理并给予证明。使用CCITT推荐的8幅二值图像进行验证和分析，结果表明，数论变换快速算法及提出的两个定理，用于对图像数据的压缩是可行的，且分块适当可提高运算速度，减少存储

2、空间，提高压缩比。本文算法在图象压缩中应用具有较大的理论意义和应用价值，为数论变换在图像压缩中的应用迈出了实际应用的第一步。关键词:数论变换;整型变换;图像压缩;快速算法中图分类号:TP3911引言经典的无损压缩方法如霍夫曼编码、算术编码等，没有考虑图像数据本身的特点，图像编码率很低，难于满足现代图像处理的要求。为了改善这些不足，国内外专家纷纷研究如何在传统浮点变换的基础上构造整型可逆变换，并将其应用于图像无损压缩，此类方法成为当[1~5]前图像压缩领域的研究热点。Daubechies在文献[6]中叙述了提升的方法。如果变换矩阵可以分解

3、成多个主对角线元素为1的三角形矩阵的乘积，那么只要对每一个三角形矩阵分别找到它所对应的可逆整型变换，并按其分解顺序依次变换，就可以构造出整个变换的整型变换。基于提升方案的第二代小波变换实现了图像的整数到整数的变换，而且图像的恢复质量与变换时边界采用何种延拓方式无关，克服了第一代小波的缺陷。但是整数小波变换后数据的动态范围要比第一代小波变换后数据的动态范围广，这在一定程度上影响了数据的压缩效果。文献[7]使用提升方法，利用FFT的蝶型构造完成了DCT的从整数到整数的变换。文献[8]利用对变换矩阵分解的方法计算得到整型DCT变换矩阵。可见，

4、当前整型可逆变换大多是在传统浮点变换基础上采用提升方法重新构造得到。七十年代初，Rader，Agarwal，Burrus等人提出了构造整数模M剩余类环ZM上的DFT，即数论变换（NumberTheoreticTransform,NTT），把数论方法引入到数字信号处理中。与DCT和小波变换相比，NTT变换没有舍入误差，不需要存储三角函数，在相同变换长度下运[9]算速度优于DCT。更重要的是NTT本身就是整型变换，无须进行提升操作就可以达到完全可逆的变换。本文在研究数论变换原理、性质和快速算法的基础上，利用了NTT整型变换的性质、特点以及变

5、换核固定和快速算法的优势，结合图象数据本身的特点以及二维序列与变换系数之间的关系，为使数论变换应用于图象压缩，提出了二维数论变换转置定理和周期性二维序列与变换系数关系定理，定理为数论变换开拓了新算法，并为整型无损图像压缩奠定了理论和应用基础。2一维、二维数论变换数论变换是在以正整数M为模的整数环Z上定义的线性正交变换，所用的运算法则是M数论中的同余运算，它在ZM上具有循环卷积特性，基本函数由整数的方幂构成。2.1一维数论变换设在以正整数M为模的环ZM上有xiZM，i0,1,,N1。如果作用在序列-1-http://www.pap

6、er.edu.cnx,x,,x上的一个变换01N1N1nkXkxn(modM)，ZM，k0,1,,N1(1)n0有如下形式的逆变换N1xN1Xnk（modM），n0,1,,N1(2)nkk0且具有循环卷积性质，则称变换式(1)为ZM上一个长为N的数论变换。可以表示为：XTxmodM其中1111N1T(modM)N1N121txx,x,,x，xZn0,1,2,,N1，Z。01N1nMM[10,11]可以推导

7、出数论变换的性质：⑴线性性；⑵正交性；⑶周期性；⑷对称性；⑸位移定理；⑹循环卷积特性。2.2二维数论变换若p为正整数，以p为模的整数环Zp：Zp0,1,2,,p1设x(n,m)Zp(n0,1,,N1;m0,1,,M1)，则二维NTT为：N1M1rnsmX(r,s)x(n,m)(modp)(3)n0m0s0,1,,M1；r0,1,,N1N1M1x(n,m)N1M1X(r,s)rnsm(modp)(4)r0s0m0,1,,M1；n0,1,,N1其中变

8、换具有循环卷积特性，二维数论变换的矩阵表示形式如下[13]：XTxT(modp)NM11xTNXTM(modp)若N，M中有一个为1，则为一维变换，本文的讨论均设N>1，M>1。2.3快速算法NTT