（计算机应用技术专业论文）自适应方向提升小波变换及应用.pdf

摘要 摘要 随着计算机的普及，互联网的迅速发展和各种数字设备的出现，数字图像 在许多领域都得到了广泛的应用。因此如何有效的表示和编码数字图像成为了 人们研究的焦点。人们对编码方案的效率的要求也逐渐提高，而且对编码技术 的功能也提出了更多要求。小波，作为一种具有良好的时频局域性和多分辨率 分析能力的变换方法，在静止图像压缩方面得到充分的认可与应用。基于小波 的j p e g 2 0 0 0 除了在压缩性能上大大超过基于d c t 的传统压缩标准，还提供了 多帧率、多分辨率，清晰度渐进等多种可伸缩性的解码如何进一步改进基于小 波变换的编码性能成为了研究焦点。 本文先提出了自适应方向提升小波变换并将其应用到图像编码中。自适应 方向提升小波变换将提升框架中的预测操作沿着局部窗口图像相关性最强的方 向进行，而不是和传统小波一样总是沿着水平或垂直的方向进行。这样自适应 方向提升小波变换可以更好的适应于图像局部窗口的方向性。自适应方向提升 小波变换将全局性的小波变换与图像的局部的方向性无缝的结合起来了。该方 法将预测和更新操作的精度提高到了1 4 像素，来获得更精细的预测方向。方 向提升小波变换的预测和更新操作只会选择整数像素位置的值作为参考点，保 证了变换的可完全重构性。为了进一步的提升方向提升小波变换的编码性能， 我们提出了码率一失真最优化的图像分割方案。该方案根据图像局部特性用四叉 树把图像分成纹理和边缘方向一致的图像块。实验结果显示自适应方向提升小 波变换在图像的主观和客观质量上都可以取得优于j p e g 2 0 0 0 的结果。在图像含 有丰富的方向性的纹理的情况下，自适应方向提升小波变换可以取得高达2 d b 的编码增益。 本文进一步分析和比较了几种典型的方向变换应用于图像编码的效率。方 向变换已经被研究了很长时间。很少有学者分析和比较它们在图像编码中的性 能。本文选取了三种最典型的方向变换：c o n t o u r l e t 变换，方向滤波器组和自 适应方向提升小波变换，并对其在编码上的性能了理论分析和数值比较。本文 采用了一个二维的各向异性的图像模型来计算各种方向变换的变换增益。分析 结果显示在比较的方向变换的方案中自适应方向提升小波变换可以取得最好的 图像编码性能。所有的方向变换的方案都可以在含有丰富的斜条纹的图像上取 得优于小波变换的编码性能。 本文还将自适应方向提升小波变换拓展到三维，设计针对医学图像的三维 提升方向小波编码。三维方向提升小波变换编码利用了医学图像在三维空间的 相关性来更好地处理图像中的边缘和纹理。结合3 d e b c o t 。该编码方案可以生 l 摘要 成嵌入式码流并同时支持有损压缩和无损压缩。和三维小波变换相比，三维方 向提升小波变换可以取的更好的编码效率，并可以取得高达2 d b 的编码增益。 在主观质量上，三维方向提升小波变换可以有效的减少图像边缘的振铃效应。 关键词：小波变换小波编码提升小波变换增益可伸缩图像编码方向预测 自适应编码码率失真最优化方向变换 i l a b s t r a c t a b s t r a c t w i t ht h ew i d e l ys p r e a do fc o m p u t e r , f a s td e v e l o p m e n to fi n t e m e ta n d e m e r g e n c eo fa l lk i n d so fd i g i t a le q u i p m e n t s ，d i g i t a li m a g e sh a v eb e e nu s e di nm a n y a p p l i c a t i o n s h o wt or e p r e s e n ta n dc o m p r e s sd i g i t a li m a g e se f f i c i e n t l yb e c o m e sa h o tr e s e a r c ht o p i c r e s e a r c h e r sh a v eb e e nd e v e l o p i n gi m a g ec o m p r e s s i o ns c h e m e s w i t hb e t t e rc o d i n gp e r f o r m a n c ea n dm o r ef e a t u r e s t h ew a v e l e tb a s e ds t a t e - o f - a r t i m a g ec o m p r e s s i o ns t a n d a r dj p e g 2 0 0 0a c h i e v e sm u c hb e t t e rc o d i n gp e r f o r m a n c e t h a nd c tb a s e ds c h e m ej p e g j p e g 2 0 0 0a l s oo f f e r sm u c hf u n c t i o n a l i t ys u c ha s s p a t i a ls c a l a b i l i t y , s n rs c a l a b i l i t y , r o ia n ds o o n h o wt oi m p r o v et h ec o d i n g p e r f o r m a n c eo fw a v e l e tb e c o m e sa h o tr e s e a r c ht o p i cd u r i n gt h ep a s tf e wy e a r s w ef i r s t p r e s e n tan o v e lt w o d i m e n s i o n a l w a v e l e tt r a n s f o r ms c h e m eo f a d a p t i v ed i r e c t i o n a ll i f t i n g ( a d l ) i ni m a g ec o d i n g i n s t e a do fa l t e r n a t e l ya p p l y i n g h o r i z o n t a la n dv e r t i c a ll i f t i n ga si np r e s e n tp r a c t i c e ，a d lp e r f o r m sl i f t i n g b a s e d p r e d i c t i o ni nl o c a lw i n d o w si nt h ed i r e c t i o no fh i g hp i x e lc o r r e l a t i o n h e n c e ，i t a d a p t sf a rb e t t e rt ot h ei m a g eo r i e n t a t i o nf e a t u r e si n l o c a lw i n d o w s t h ea d l t r a n s f o r mi sa c h i e v e db ye x i s t i n go n e d i m e n s i o n a lw a v e l e t sa n di ss e a m l e s s l y i n t e g r a t e di n t ot h eg l o b a lw a v e l e tt r a n s f o r m t h ep r e d i c t i n ga n du p d a t i n gs i g n a l so f a d lc a nb ed e r i v e de v e na tt h ef r a c t i o n a lp i x e lp r e c i s i o nl e v e lt oa c h i e v eh i g h d i r e c t i o n a lr e s o l u t i o n ，w h i l es t i l lm a i n t a i n i n gp e r f e c tr e c o n s t m c - - e d o n t oe n h a n c et h e a d l p e r f o r m a n c e ，ar a t e d i s t o r t i o no p t i m i z e dd i r e c t i o n a ls e g m e n t a t i o ns c h e m ei s a l s op r o p o s e dt of o r ma n dc o d eah i e r a r c h i c a li m a g ep a r t i t i o na d a p t i n gt o l o c a l f e a t u r e s e x p e r i m e n t a li e s u l t s s h o wt h a tt h ep r o p o s e da d l - b a s e di m a g ec o d i n g t e c t m i q u eo u t p e r f o r m s j p e g2 0 0 0i nb o t hp s n ra n dv i s u a lq u a l i t y , w i t ht h e i m p r o v e m e n tu p t o2 0d bo ni m a g e sw i t hr i c ho r i e n t a t i o nf e a t u r e s d i r e c t i o n a lt r a n s f o r m sh a v eb e e ns t u d i e df o rm a n yy e a r s h o w e v e lt h e i r p e r f o r m a n c e so ni m a g ec o d i n ga r e s e l d o ma n a l y z e da n dc o m p a r e d i nt h i sp a p e r , w e c h o o s et h r e er e p r e s e n t a t i v et r a n s f o r m s ：c o n t o u r l e t ，d i r e c t i o n a lf i l t e rb a n k s ( d f b ) a n da d a p t i v ed i r e c t i o n a ll i f t i n g ( a d l ) t oc o m p a r et h e i rp e r f o r m a n c e sf o ri m a g e c o d i n gi nt e r m so fb o t ht h e o r e t i ca n a l y s e sa n dn u m e r i ce x p e r i m e n t s f o r au n i f o r m e v a l u a t i o nf r a m e w o r k ，w ea d o p ta2 da n i s o t r o p i ci m a g em o d e la n dc o m p a r et h e c o d i n gg a i no fd i f f e r e n tt r a n s f o r m s o nt h em o d e l t h ea n a l y s e ss h o wt h a ta d l g e n e r a l l yp e r f o r m st h e b e s ta m o n g s tt h ec o m p a r e dt r a n s f o r m s a n dd i r e c t i o n a l 1 1 1 a b s t r a c t t r a n s f o m l sh a v eb e t t e rp e r f o r m a n c et h a nt r a d i t i o n a lw a v e l e to ni m a g e sw i t hr i c h d i a g o n a lt e x t u r e w ea l s od e v e l o pad i r e c t i o n a ll i f t i n g - b a s e d3 dw a v e l e tt r a n s f o r mf o rv o l u m e t r i c m e d i c a ld a t a s e t s t h ep r o p o s e dw a v e l e tt r a n s f o r me x p l o i t so r i e n t a t i o nf e a t u r e so f v o l u m e t r i cd a t a s e t sb yp e r f o r m i n gt h et r a n s f o r ma l o n gt h ed i r e c t i o no fs t r o n g c o r r e l a t i o ni nl o c a la r e a w h e nc o u p l e dw i t h3 d e b c o t , t h ep r o p o s e ds c h e m ec a r l g e n e r a t ee m b e d d e db i ts t r e a ma n dp r e s e n td e c o d e dq u a l i t yf r o ml o s s yt ol o s s l e s s t h ee x p e r i m e n t a lr e s u l t so nv a r i o u sm e d i c a lv o l u m e t r i cd a t a s e t ss h o wt h a tt h e i n t r o d u c t i o no fd i r e c t i o n a l3 dw a v e l e tt r a n s f o r mi m p r o v e st h ei m a g eq u a l i t yi nt e r m s o fb o t hv i s u a lq u a l i t ya n dp s n ra n dv i s u a lq u a l i t yw i t hu pt o2 d bg a i nc o m p a r e d w i t ht r a d i t i o n a l3 dw a v e l e t t h er i n ge f f e c t sa r t i f a c t sa r o u n de d g e sa r ea l s or e d u c e d s i g n i f i c a n t l y k e yw o r d s ：w a v e l e t ，a d a p t i v ed i r e c t i o n a ll i f t i n g ，d i r e c t i o n a lp r e d i c t i o n ，c o d i n gg a i n ， s c a l a b l e i m a g ec o d i n g ，r a t e d i s t o r t i o no p t i m i z a t i o n ，d i r e c t i o n a l t r a n s f 0 1 t n i v 图目录 图目录 1 1d p c m 编码的基本结构2 1 2 二维d c t 变换的基函数s 1 3 标量量化6 1 4 二维的矢量量化7 1 5h u f f m a n 编码例子1 0 1 6 基于变换的图像编码框架1 2 1 7j p e g 编码过程1 3 1 8 量化矩阵数据1 4 1 9 小波分解树1 5 1 1 0j p e g 2 0 0 0 编解码系统的过程图1 6 1 1 1h 2 6 4 a v ci n t r a4 x 4 帧内预测1 7 1 1 2i n t r a4 x 4 方向预测模式1 7 1 1 3 混合图像编码的基本框架1 8 1 1 4 基于视觉的图像编码1 9 2 1 沿着方向o ，的预测和更新过程2 7 2 2 一维a d l 变换2 8 2 3 用a d l 变换分解的各个子带2 9 2 4 用5 3 小波变换分解的各个子带：3 0 2 5s i n g 插值的参考点3 1 2 6s i n g 插值的亚像素点3 l 2 7 变换角度的预测编码3 3 2 8 图像的四叉树分割和a d l 变换的方向3 5 2 9 每个编码块的嵌入式码流3 8 2 1 0 按照幅值排序的系数的二进制表示4 0 2 1 1 空间方向树的父子关系4 2 2 1 2 一次变换时j p e g 2 0 0 和a d l 变换的各个子带系数的幅值4 7 2 1 3 图b a b a r a 主观质量的比较4 8 2 1 4j p e g 2 0 0 0 和a d l 的性能可伸缩性比较5 1 3 1 方向性变换对频域的划分5 3 3 2 级联q f b 来生成方向滤波器组。5 5 3 3q u r n c t m x 下采样的采样点5 5 3 4q u i n c u n x 滤波器组5 6 3 5q u i n c u n x 滤波器组的频率划分5 6 3 6l a p l a c i a n 金字塔5 7 3 7c o u t o u r l e t 变换框架s 7 3 8c o n t o u r l e t 的频率划分5 8 3 9 编码增益比较：= 2 蚺6 8 3 1 0 编码增益比较：t o a = 4 t a r 6 8 3 1 1 编码增益比较：；8 t a r 6 9 v n 图目录 4 1 一维空间的小波变换7 3 4 2 二维空间的小波变换7 3 4 3 三维空间中z 轴方向的小波变换7 4 4 4 变换角度的预测编码7 4 4 53 d e s c o t 的相邻系数7 6 4 6 三维方向小波变换和三维小波变换的码率失真比较8 1 4 7 三维方向小波变换和三维小波变换p s n r 的比较8 1 4 8 三维方向小波变换和三维小波变换主观质量的比较8 2 v i i i 表目录 表目录 1 1 常见的视频图像的未压缩码率1 1 2 符号集和概率1 1 1 3 符号的分配区域1 1 1 4 算术编码器的编码过程l l 2 1s r n c 插值权重。3 1 2 2z c 编码的9 个上下文。3 6 2 3s c 编码的5 个上下文3 7 2 4 两种方案中l h ，h l 和h h 子带系数的比较。4 5 2 5a d l 变换和j p e g 2 0 0 0 的编码效率的比较4 9 2 6a d l 变换和s p i h t 的编码效率的比较5 0 3 1 图像模型参数6 8 4 1 不同分解顺序的高频子带的能量比较7 5 4 2z c 编码的上下文映射7 7 4 3s c 编码的上下文映射。7 7 4 4 用三维方向小波和三维小波变换的高频子带能量的比较8 0 4 5 所有图像编码性能的比较8 0 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导卜进行研岁芒工作所取得的 成果。除已特另0 加咀标注和致谢的地方外，沦文中不包含任f k r f 也人已经发表或 撰写过的研究成果。与我一同工作的同忐对本研究所做的贞献均已在沦文中作 了明确的说口月。 作者签名：丘邋签字口划：) 。型 中国科学技术大学学位论文授权使用声明 作为申请学位的条f ，f ：之，学位论文著作权洲自者授十义中幽科学技术人学 拥有学位论文的部分使j f j 权，即：学校有权按有关规定i 柚国家有关部门或机构 送交论文的复e r 】, i ：t - - 和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采刖影印、缩印或扫描等复制手段保存、7 i ：编学位论 文。本人提父的电子文档的内容和纸质论文的内容相一致。 保密的学付论文袖：解宓1 1 1 后也遵! ：此规定。 函公歼口保衔( 年) 作者签名：卫b f i 兮一 导师签名： 签字h 期：鱼竺删 勋l 辨悯：撕芦手 第1 章绪论 第1 章绪论 1 1 引言 人类从自然界获取的信息中最重要的是视觉信息。每时每刻人们都会获取大 量的视觉信息。随着自然图像的成像技术的成熟，越来越多的图像保留下来。随 着数码相机和计算机的广泛应用和普及，大量的图像以数字的形式保存下来。存 储和传输这些数字图像需要巨大的存储空间和带宽。存储高分辨率的图像时间序 列所需的空间更是巨大的。表1 1 是几种常见的视频图像格式未压缩时的码率。 为了减少图像存储和传输的代价，研究人员开始研究各种图像压缩算法。通过过 去几十年的研究，图像压缩算法特别是图像标准j p e g 被广泛应用到了各种应用 中。 表1 1 ：常见的视频图像的未压缩码率 视频格式帧率分辨率 码率m b p s v c r2 53 5 2 x 2 8 83 1 n t s c3 0 7 2 0 x 4 8 01 2 5 p a l2 5 7 2 0 x 5 7 61 2 5 h d t v3 019 2 0 x 1 0 8 01 0 0 0 1 2 编码基础技术介绍 图像编码的目的是去除图像中的冗余信息和不重要的信息，用更少的码率来 表示原有的图像。图像编码技术按照图像是否可以完全重构可以分为有损编码和 无损编码 7 1 。无损图像压缩技术只利用图像的冗余性来减少图像的码率。无损 图像编码的压缩率是有限的，因此它更多的应用在医学图像等对图像质量要求很 高的应用中。有损图像压缩技术同时利用图像的冗余性和信息中的视觉不重要性， 因此可以获得更好的压缩效率满足更多应用的需求。研究人员的主要研究内容也 是有损图像压缩。 有损图像压缩的图像压缩的评判方法有两种：主观质量和客观质量。主观质 量的评测一般是让一组评测人员对压缩的图像进行打分，将所有的分数的平均作 为主观质量分。主管质量的打分会受到观察环境，灯光，评测人员的影响。主管 质量的打分过程也是比较耗时的。所以一般只在评测图像和视频编码标准时才采 用主观质量作为评测标准。研究人员更多的使用客观质量来衡量图像编码的效果。 峰值信噪比( p s n r ) 是使用最为广泛的客观评价准则。它的定义如下 f p z p s n r = 1 0 2 。目1 。瓦丽丽z - j l , i j 而铲 其中p 表示图像的最大值，r ( f ，j ) 表示重建图像的像素值，d ( f ，) 表示原始图像的 像素值。对于用8 比特表示的灰度图像，一般取p = 2 5 5 。p s n r 的值越大表示 第1 章绪论 编码图像和原始图像之间的差别越小，图像的质量也就越好。评价图像压缩算法 的好坏的一个重要的值是压缩比。它是指在相同的主观或客观质量时，原始图像 的码率和编码图像的码率之间的比值。 在过去的几十年中，研究人员设计出了各种不同的图像压缩方法。预测编码 方案被最早应用于图像编码中。预测编码通过前面已编码的像素的值来预测当前 的像素从而去除像素间的相关性。后来基于变换的图像编码方案成为了最主要的 图像编码的研究内容。变换编码利用变换去除像素间的相关性并把图像的能量集 中到少数几个系数中。相比于预测编码，变换编码可以取得更好的压缩效果。因 此基于变换的图像编码的方案特别是j p e g 得到了广泛的应用。到2 0 世纪9 0 年 代初，研究人员提出了一种新的变换：小波变换。小波变换用多尺度的方法渐近 的逼近原信号从而获得了更好的压缩效果。基于小波变换的图像研究也慢慢成了 研究的重点。 1 2 1 预测编码 预测编码是最早提出的一种图像编码方案 7 1 】。图像的相邻像素之间存在很 强的相关性，因此可以用前面的像素来预测后面的像素。预测后的序列的均值为 零，方差远小于原始图像的方差，因此更容易编码。 差分脉冲编码( d p c m ) 是最主要的预测编码方案。图1 1 是d p c m 的编码 器和解码器的框图。d p c m 由预测器，量化器和熵编码组成。预测器用过去的信 号值s ( n 一1 ) ，s ( n 一2 ) ，s ( n p ) 来预测当前信号s ( n ) 的值。p 是预测器的阶数。 如果使用线性预测那么预测值为 p 弋1 ( n ) = a k s ( n k ) j 一 k = l 其中e ( n ) = s ( n ) 一( n ) 是预测误差，s ( n ) = 夸( n ) + e 7 ( n ) 是重构信号的值。重建 信号的误差为 ( n ) 一s ( n ) = e t ( n ) 一e ( n ) 。 删p l l l 图1 1d p c m 编码的基本结构。 2 憎 d叩!蜘 第1 章绪论 如果信号是平稳随机序列而且信号的相关函数为r ) = e s ( n ) s ( n 一恐) 】已 知，那么在均方意义下最优的线性预测器可以由w i e n e r - h o p f 方程推导得出。方 程 尺a = ，_ 的解就是最优的线性预测器。其中4 = 【口l ，口2 ，a k 】7 ，且 rr ( o ) r ( 1 )r p 一1 ) 1 r = 一“孙圳 i ： 7 一i 上jl 【r ( p 一1 ) r ( 1 ) r ( o ) j 由于真实的图像不是一个平稳的随机过程，所以不存在一个全局最优的线性 最优预测器。因此要获得更好的预测效果就需要使用自适应的d p c m 编码方案。 自适应的d p c m 可以动态的调整线性预测器的预测滤波器的值从而得到更好的 预测结果。 使用d p c m 编码的图像有这样的一些特点。在图像的平坦区域编码噪声是 随机的。在图像的边缘部分。d p c m 编码会造成吉布森振铃效应而且会模糊高对 比度的边缘。 1 2 2 变换编码 变换编码是目前最主要的图像编码方案，它得到了最广泛的应用。图像编码 所采用的变换是线性变换。目前图像编码中使用的二维变换都是用两个一维变换 组合得来。一个一维的线性变换可以写成 y = a x 其中x 是表示原始信号的n 维矢量x = 【x ( o ) x ( 1 ) x ( 讥) 】r ，y 是表示变换后系数 的n 维矢量y = i y ( o ) y ( 1 ) y ( n ) 丁，a 是n x n 的变换矩阵。一般a 是一个正 交归一的变换，即 a a h = i 该变换的逆变换为 x = a - 1 v = a y 原始信号x 是a t 表示的基函数的线性组合。把矩阵a 的第k 行，第九列写成 a ( k ，n ) = n 足( n ) ，把a t 的第七列记为a ：= 【口；( o ) ，口；( 1 ) ，a * k ( n 一1 ) 】丁。那么变 换矩阵可以写成 一1 气1 y ( 七) = 吼( 咒) z ( n ) = j 一 n = o 有上式可知y ( k ) 是矢量x 在a ：上的投影。y ( k ) 表示x 中包含a i 分量的大小。我们把 a ：称为变换的基函数。 常见的变换有d f t ，h a d a m a r d 变换，h a a r 变换，s l a n t 变换，d c t 变换和 k l t 变换。这些变换有着不同的基函数。 d f t 芟揆? d f t 的基函数为 第1 章绪论 口i c ( n ) = e 啊砒 基函数a ：是不同频率的函数。d f t 变换可以得到信号在不同频率的分量的大小。 h a d a m a r d 曼诶? h a d a m a r d 变换的变换矩阵是递归定义的。对于长度为 n = 2 n 的h a d a m a r d 变换矩阵定义为 h n = 了1 2 h n 一- 。x h h n n - 一x 。】 初始矩阵为 ”击【i 二1 1 】h ，= 覆嵯一1 j n = g 时，h a d a m a r d 变换的变换矩阵为 1111 1 11 1 11 。一1 1 l111 111一l 1111 h 。= i 三- 1 1 - 1 1 至一：二 二i 一1 1 11111111 111 1 1 111 11111111 h a a r 曼谈? h a a r 变换可以看成长度为2 的h a d a m a r d 变换或长度为2 的d c t 变 换。它也可以看成一个一组正交的小波变换基函数。它的变换矩阵为 盯= 批匀 ，o 上工o s l a n t 芟攒js l a n t 变换矩阵也是递推定义的。对于长度为= 2 n 的s l a n t 变换 矩阵定义为 r c 一1nf s n 一1 o n 一1 1 js n = 疆q “琵s = j k 爿三二】 其中o n 是大d , y 92 n 2 n 变换矩阵，q n 为其核矩阵。 长度为4 的s l a n t 矩阵为 s 2 = d c t 雯谈，离散余玄变换( d c t ) 特别是d c t - i i 被广泛应用到了图像和信 号处理中，比如有损图像压缩中。d c t 变换具有能量集中的特性，变换后信号 的能量倾向于集中到少数几个低频分量中。d c t 变换对于马尔可夫过程的信号 是逼近最优线性变换k l t 的。d c t 和d f t 变换是相关的。d c t 变换把信号用 一组不同频率和幅度的余玄函数来表示。和d f t 一样，d c t 变换的基函数也 是定义在离散采样点上。不同的是d c t 变换的基函数是余玄函数，而d f t 是正 4 l以一循1 o 一据 1 o 一据4 3 一垢 1 3一以0七一循 1 3一垢1 1 一据 第1 章绪论 玄函数和余玄函数的组合。 d c t 变换有四类它们的变换矩阵的定义分别如下。假设信号长度为n ，z 为 输入信号序列，y 为输出信号序列。d c t - i 的定义为 n - 2 y ( 岫i 1 ) + ( - 1 ) - 1 ) ) + z nr 1 ) c 。s 寿洲 d c t - i i 的定义为 一1 y = 咖) c o s 晤( n + 扣 d c t - 1 i i 的定义为 ，( k ) = ；x ( o ) + z ( n ) c 。s 爵( k + 勃n 】 d c t - i v 的定义为 y = z ( n ) c o s 晤( n + 尹1 ( k + _ ) 1 n = o d c t - i i v 都是d f t 的实部偶数相位分量的对应。 二二维d c t 变换的定义和一维d c t 的定义类似：它可咀用不同维度方向的一维 d c 变换组合得到。例如，维的d c t - i i 的变换为 y ( k 小z ) = 咖m ) c 。s 晤( n + 多吣i 。s 晤( m + 多蚓 二维d c t 变换的逆变换和正变换一样可以用行方向的对应的逆变换和列方向对 应的逆变换组成。图1 2 显示的是8 x 8 的二维d c t 的水平频率分量和垂直频率 分量的组合。从左往右和从上往下每块的频率逐步增加。最上角的是最低频分量 最下角是最高频分量。 一l l l | i | i l 川 霸留编w 惴盟 = 麓筒烈m 脯艚 = 记基酸蟛礅凇；戳 兰銎薹龉麓；噼| 黼 三嚣瑟鹱嚣潜蕊辩 耋蠹薹蒋蠹簿瓣瓣 薰囊麓簇舞缀拣瓣 圈1 2 二维d c t 变挟的基函数。 d c t 变换可以直接通过矩阵乘法来计算，计算的复杂度为0 ( 2 ) 。d c t 变 第1 章绪论 换存在计算复杂度为o ( n l o g n ) 的快速算法。该方法和快速f f t 一样把d c t 的 变换矩阵进行分解。d c t 变换也可以用快速f f t 和d ( ) 的后处理来计算得到。 k l t 雯淡jk l t 变换( k a r h u n e n _ l o e v et r a n s f o r m ) 又被称为p c a 变换。k l t 变换是最小均方误差意义下的最优变换。它把高维空间的的矢量压缩到低维空间 并重建原矢量。k l t 变换有下面的一些特点。k l t 变换假设信号序列是一组基 函数的线性组合。k l t 变换是基于信号统计上的均值和相关矩阵推导出来的。它 用相关矩阵的特征向量作为它的基函数。 1 2 3 量化技术 真实世界中的图像在空间和强度上都是连续的。为了用数字设备来保存这些 图像必须先将其离散化。为了进一步用更少的空间来表示一幅图像，我们需要用 有限的状态数来逼近原图像。量化技术用来减少表示图像所需的空间。量化过程 会产生误差。为了减少量化过程中引入的误差，我们需要设计好的量化算法。 粝：量量纪j 标量量化算法对每个采样点进行独立的量化操作。图1 3 是一个 简单的标量量化的例子。图1 3 ( 左) 中将连续的x 量化到集合 一2 ，一1 ，o ，一1 ，2 。 图1 3 ( 右) 将量化了的系数反量化，用每个量化段的中心值代表原来信号的值。 常见的标量量化方法有均匀量化，非均匀量化和带死亡区的均匀量化。均匀量化 中量化步长是固定。非均匀量化中的量化步长是可变的，在不同的区间取不同的 值。带死亡区的均匀量化的量化步长除了零区域外也是不变的。当输入的值在给 定的范围内时- - 6 x 6 ，x 会被量化为零。一般量化为零的区域的步长要大于 其它区域的步长。 l 。 - _ 一 jl r x 一 - b芝ly oy 1y 2 x 图1 3 标量量化。 矢量量兜? 矢量量化将多个采样点当成一个矢量进行统一量化。图1 4 中显 示的是一个二维的矢量量化的例子。红色的点表示码本。所有的待编码矢量称为 训练矢量。蓝色的边分割出来的区域表示编码区域。所有的编码区域称为对空间 的一个划分。 6 第1 章绪论 图1 4 二维的矢量量化。 矢量量化的目标就是找到一组码本对空间进行划分，然后将每个矢量映射到 一个码字。具体的，矢量的量化的问题可以如下定义。假设有一组统计信息已知 的矢量，给定码本的大小，给定误差衡量的标准，那么矢量量化找到一组码本和 空间划分方案使得整体的平均误差最小。设用于生成码本的矢量集合为 t = ( x 1 ，x 2 ，x m 对于图像编码该矢量集合可以把图像分成固定大小的块，把每个块当成一个矢量 来得到。我们假设m 足够大，该矢量集合可以描述信号源的所有统计特性。设矢 量是k 维的，即 x m = ，1 2 k 】r 设为码本的大小，目标码本为 e = ( c 1 ，c 2 ，j c ，) 码本中的每个码字矢量为 c n = x n ，1x n 2 x n ，n n = 1 , 2 ，j 设s n 表示每个码字c n 对应的编码区域且 p = s l ，s z ，乳) 表示对整个矢量空间的一个划分。如果待编码的矢量x m 落在编码区域s n 内，那 么x m 被量化成c n ： q ( x m ) = c n ，如果x m 品 如果用平方误差来衡量误差大小，那么平均误差为 m 1t 1 j j i = 赤艺i i x m q ( x m ) 1 2 其中每个矢量的量化误差为l l e l l 2 = e i + e ；+ + e 未。那么矢量量化的问题可以 第1 章绪论 陈述为，给定丁和n ，找到使得瓦最小化的e 和p 。 如果e 和p 是上述问题的一个最优解，那么它们需要满足下面两个条件： 最近邻准则： s n = ( x ：l i x c n i l 2 0 x c n ，1 1 2 ) n = 1 , 2 ，n 该条件指出编码空间s n 必须由邻近c n 的矢量组成。如果一个矢量在编码空间 的边缘线上那么，它可以量化到任意一个编码空间所对应的码字。 中心原则： c n = 耳a x m e $ n x m 该条件指出码字c n 必须是编码空间s n 所包含的所有训练矢量的平均矢量。实 验时，我们需要保证每个编码区间至少包含一个训练矢量。 矢量量化有很多种算法，其中最著名的矢量量化算法为l b g 7 1 。l b g 矢 量量化算法是迭代算法，该算法交替的优化上述两个准则。l b g 算法需要一个 初始化码本e o 。初始化的码本可以通过分裂算法获得。该分裂算法将整个训练 矢量的平均值作为最初的码字。然后再将该码字分裂成两个。接着整个迭代算法 以这两个码字作为码本进行优化。最后将得到的两个码字进一步分裂成四个码字。 整个过程一直进行到生成给定大小的码本。该算法的描述如下： l b g 算法 1 给定丁和 0 ，是个很小的数 2 设n = 1 且 m 1r 1 c i2 面乙x m 计算 珑坩= 去l i x m 叫1 1 2 3 分裂码字：对于i = 1 , 2 ，n ，设置 c ；o ) = ( 1 + ) c ： c 艘i = ( 1 一) c ： 设置n = 2 n 4 迭代：设d 观= d 品日。设迭代的索引为i = 0 i 对m = l ，2 m ，找到下式的最小值 f l x m 一酬2 其中n = 1 ，2 ，j 。假设n 使得上式取得最小值，那么设 q ( x m ) = c i i 对n = 1 , 2 ，更新码字： 8 第1 章绪论 i i i 设置i = i + 1 i v 计算 c烨丽o(xm)_-c(o x m m d ( o = 去l i x m q ( x m ) 1 1 2 v 如果( d 。( i 叼- 1 ) 一d 。( i 叫) 、，d 。( i 叫- 1 ) ，转到步骤i v i 设置d ；妒口= 一d n ( o 叼。对n = 1 , 2 ，n 设置 c 二= c 作为最后的码字。 5 不断进行步骤3 和4 的操作直到码字的数目达到预定的值。 1 2 4 熵编码技术 熵编码的理论基础是s h a n n o n 提出的信息论。这些理论给出了对给定统计特 性的信号进行有损和无损编码的所需最少比特数的下界。 假设一个无记忆的信号源所它的符号集为( 口o ，a 1 ，a 2 ，a k - 1 ) 。每个符号对 应的概率为 p ( a