数论变换在图像压缩技术中的应用.pdf

中国矿业大学学报990 519 中国矿业大学学报 JO U RNA L O F CH I NA U NI VERSI T Y O F M I NI NG 当k l ≥p 时，k l k l -p . 乘法k l r ，其中k l q p r ，0 ≤r p ，q 为正整数. 这样的加法和乘法可表示为 k l ≡k l -p m o d p f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 2 ／12 页）2 0 10 -3-2 3 15 58 2 6 中国矿业大学学报990 519 k l ≡r m o d p . 上述定义中，我们不难验证Zp上定义的加法和乘法满足交换律、结合律和分配 律，并且Zp对于加法和乘法是封闭的. 故Zp是一个数环，称之为以p 为模的整数环. 定义4 设α是Zp中的非零元素，如果存在正整数n ，使αn≡1 m o d p ，则称α是 Zp中的n 次单位根. 如果n 是使上式成立的最小正整数，即αn≡1 m o d p ，αl1 l 1, 2 , ⋯, n -1 m o d p 则称α是对模p 的n 阶本原单位根，而称n 是α对模p 的阶数. 1. 2 一维数论变换 设在以正整数p 为模的环Zp上有 X x 0, x1, ⋯, xn -1 T , 作变换 Y≡T X m o d p , 其中 即设x i ∈Zp i 0 , 1, 2 , ⋯, n -1 ，则 可以推导出数论变换（NT T ）有如下性质［5，6 ］1） 线性性；2 ） 正交性；3） 周期性；4） 对称性；5） 位移性；6 ） 循环卷积特性. 1. 3 二维数论变换 设p 为正整数，以p 为模的整数环 Zp { 0 , 1, 2 , ⋯, p -1} , f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 3／12 页）2 0 10 -3-2 3 15 58 2 6 中国矿业大学学报990 519 设x i , j ∈Zp i 0 , 1, ⋯, n -1; j 0 , 1, ⋯, m -1 ，则 为二维数论变换. 二维数论变换的矩阵表示形式如下 Y≡T n XT m m o d p , X≡T -1n YT -1m m o d p , 其中 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 4／12 页）2 0 10 -3-2 3 15 58 2 6 中国矿业大学学报990 519 1. 4 数论变换的快速算法 快速算法的推导过程与FFT ［2 ］相同，但有两点不同第一是以α代替FFT 中的 W n ，由于α是一正整数，不象FFT 那样要预先存储基W n ；第二是每一步运算都要判别 一下中间量是否超过p ，如果超过p ，就应该取小于p 的同余值，以防溢出. 设m , n 8 ，α，x i ∈Zp i 0 , 1, ⋯, n -1 于是 交换行次序变换如下 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 5／12 页）2 0 10 -3-2 3 15 58 2 6 中国矿业大学学报990 519 又α8≡1 m o d p , α4≡-1 m o d p . ，则上述变换矩阵T 变为 故可将T 分解为如下两个矩阵的乘积 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 6 ／12 页）2 0 10 -3-2 3 15 58 2 6 中国矿业大学学报990 519 因此得到快速算法的流程图如图1所示. f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 7 ／12 页）2 0 10 -3-2 3 15 58 2 6 中国矿业大学学报990 519 图1 NT T 快速算法流程图 Fi g . 1 NT T q u i c k c a l c u l a t i o n f l o w 图1的图例表示y x 3α3 x7 -α3 ，这相当于FFT 的按频率抽取的算法. 上述快速算法 可将n 2次乘法降为n l b n 次乘法. 如果α是2 或2 的幂，就只需n l b n 次移位操作. 2 数论变换在图像压缩中的应用 2 . 1 NT T 系统结构与设计思想 数论变换是以正整数p 为模的整数环Zp上定义的线性正交变换. 基本数是由数2 的方 幂构成，变换长度为n 2 p ，构造了具有FFT 类型的快速算法，且在二进制计算机上NT T 变换不必使用乘法，仅用移位操作. 又由于该算法是模运算，所以不存在舍入误差，也 不需要存储基本函数. NT T 系统结构如图2 所示. 图2 NT T 系统结构图 Fi g . 2 Sy s t e m s t r u c t u r e o f NT T 图2 中，NT T 与I NT T 互为逆变换. 编码方式采用哈夫曼编码. 由于解码、编码的功能 相反，为使解码准确，编码器和解码器所使用的表（量化表，编码表）是一致的. 2 . 2 NT T 系统的实现 2 . 2 . 1 f 的分块 为了使设计的系统具有完整性、模块性和可行性，必须考虑二维NT T 所处理的数 据块的尺寸. 设原图像的尺寸为m m ，有2 种分块方式1）1个m m 的尺寸；2 ）k 2个n n 的 块方式1）至少有两方面的支持，足够的存储容量和允许较长时间的运算. 此时NT T 所需的移位操作次数为m 2l b m ；方式2 ）其存储空间可节省k2倍，而运算时间 也可减少为倍，因此选择的k 越大所需的时间和空间改进越多，而且对多 处理器并行结构的支持也越大，但当n 小到一定程度时，采用变换可能造成“边界效 应”的不连续点，故选择n ≥8 . 2 . 2 . 2 比特分配与自适应区域模式的选择 基于对多幅有代表性图像的分析，我们在系统设计时，保留区域模式的选择由自 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 8 ／12 页）2 0 10 -3-2 3 15 58 2 6 中国矿业大学学报990 519 适应来确定，即每次在选择保留区域时，先进行按各规定保留区域模式进行，选择其 中最大能量对应的区域模式为保留区. 为了能够让系数块在流动中可以被识别出采用何种模式，还需给每个系数块增加 2 b i t 的标识域. 从而每个系数块必须要附加2 b i t 的开销. 2 . 2 . 3 向量量化的块划分及其比特分配 1 向量分割 对于不同的保留区模式均采用最优比特分配的向量分割方法. 2 VQ 比特分配 现定义向量Vq的归一化系数为NFq，其中σq u是V第q 个分量的方差. 为了方便起 见，归一化系数使用了几何均值，而非算术均值. 在指定的压缩率ν的条件下，分配给向量Vq q 1, 2 , ⋯ 多少个比特是最佳的，这是 向量量化器设计中多种向量和多码本量化器的比特分配问题，分配的原则是总量化失 真最小. 单位向量的量化失真D 由下式给定 或为 式中n 为码本尺寸. 不妨设p x 为k 阶独立的La p l a c e 分布，积分后D 可化为 式中σq为向量的第q 个分量对应的方差；b 令则上式化简为 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 9／12 页）2 0 10 -3-2 3 15 58 2 6 中国矿业大学学报990 519 其分量表达式可写为 D q , k j 为第q 类k j 维向量Vj q 的失真，从而总失真为 式中 m 为向量数. 将Vj的归一化系数NFj q 代入上式有 显然b j q j 与ν具有关系 从而使失真D 最小的b j q 为 式中 利用上式就可以确定向量量化的最优比特分配. f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 10 ／12 页）2 0 10 -3-2 3 15 58 2 6 中国矿业大学学报990 519 3 几种正交变换的比较 使用变换编码，首先应选择一种合适的正交变换. 从实用意义上考虑，必须从去除 相关性与能量集中性以及实现的难易程度来综合选择. 在性能满足要求的条件下，尽量 选择简单的变换，对常见的几种变换来说，实现的难易顺序由难到易［7 ］为K L， D CT ，NT T . 实例对一个16 16 的子图作变换. 下面将NT T 算法与资料及D CT 算法进行比较， 表1给出了比较结果. 从表1中可以看出，本算法的运算次数只是D CT 变换算法的乘法次数的一半，而且 是移位操作. 若本文中的NT T 算法与D CT 算法所使用的编码方法一样，则由NT T 快速算 法可以看出NT T 在压缩与解压缩过程中无舍入误差，而D CT 快速算法［2 ］在压缩过程 中使用三角函数，这必然存在舍入误差，因此NT T 比D CT 有更好的保真度. 同样，可以 论证在相同的编码方法的前提条件下NT T 算法比D CT 算法有更高的压缩比. 表1 不同算法的比较结果 T a b l e 1 Co m p a r e c o n s e q u e n c e o f v a r y i n g c a l c u l a t i o n D CT 算法 资料*NT T 算法 乘法 44 8 8 16 16 32 192 1 0 2 4 2 4 144 7 6 8 16 96 512 加法 44 8 8 16 16 7 2 46 4 2 592 7 2 46 4 2 592 7 4 46 6 2 530 4 结 论 本文提出了以数论变换为理论基础的数据压缩算法. 证明了在以正整数p 为模的整 数环Zp上NT T 变换是线形正交变换，在Zp上NT T 具有循环卷积等特性. 因为NT T 变换的 基本函数是由整数的方幂构成，特别是由2 的方幂构成. 因此，在二进制计算机上， NT T 的运算不使用乘法，仅用移位操作，且不需要存储基本函数，从而提高了变换速 度. 又由于是模运算，不存在舍入误差，可以提高变换精度. 可见，NT T 算法可得到比较 好的压缩效果. 本算法设计出了具有FFT 类型的快速算法，证明本算法的实施性. 当然，NT T 变换尚有许多问题需要解决. 比如物理解释问题、误差估计问题等等， 都有待进一步解决. *煤炭科学基金资助项目（96 电10 10 3） 第一作者简介 张 虹，女，1942 年生，副教授 作者单位中国矿业大学计算机科学与技术系 江苏徐州 2 2 10 0 8 参 考 文 献 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 11／12 页）2 0 10 -3-2 3 15 58 2 6 中国矿业大学学报990 519 1 ［美］托马斯 林奇. 数据压缩技术及应用. 吴家安译. 北京人民邮电出版 社, 198 9. 10 6 ～133 2 高 文. 多媒体数据压缩技术. 北京电子工业出版社, 1994. 47 ～7 4 3 W a l l c e C K . T h e JPEG s t i l l p i c t u r e c o m p r e s s i o n s t a n d a r d . Co m m a n A CM , 1991, 34 4 30 ～ 45 4 华罗庚. 数论导论. 北京科学出版社, 1957 . 10 ～2 5 5 数 丁. 数论变换. 数学的实践与认识，197 7 3 45～52 6 数 丁. 数论变换. 数学的实践与认识，197 7 4 47 ～56 7 汪 洋. 数论变换在多媒体数据压缩中应用的研究. ［学位论文］. 江苏徐州中国矿 业大学计算机科学与技术系, 1997 收稿日期1999-0 3-0 4 f i l e / / / E| / q k / z g k y d x x b / z g k y 99/ z g k y 990 5/ 990 519. h t m （第 12 ／12 页）2 0 10 -3-2 3 15 58 2 6