（计算机科学与技术专业论文）基于基元图学习的低码率图像压缩.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 一 ， 士哆导师签名： 谩一土 摘要 摘要 日益增多的多媒体应用产生的海量数字图像对存储和传输都产生了巨大的 压力，因此，对高效的数字图像压缩编码技术的研究具有重要意义。原始图像 数据中存在着各种冗余，图像压缩的目的就是要去除这些冗余。传统的图像压 缩方法以信息论为指导，从信号处理的角度出发去除图像中的各种冗余，并取 得了较好的效果，如广泛使用的基于离散余弦变换( d c t ) 的j p e g 图像压缩标准 和基于离散小波变换( d w t ) 的j p e g 2 0 0 0 标准。但是在受终端设备处理和存储 能力以及传输带宽的限制而产生的低码率图像压缩应用场景中，传统图像压缩 方法受其固有特性的影响会产生块效应和振铃效应，严重影响了图像质量。 针对这一问题，本文从计算机视觉的角度出发，利用人类视觉系统的特点 以及图像基元图信息的可复用性，提出了一个基于图像基元图学习的低码率图 像压缩方案。 该方案针对人眼更敏感的边缘区域进行处理，从一组训练图像中提取出通 用的可在低码率压缩图像之间复用的基元图信息，并以非参数化表示的形式将 其保存在库中。在图像编码端只需要压缩下采样之后的低分辨率图像，其丢失 的高频信息就可以在解码端利用库中的基元图信息近似地恢复出来。因此在相 同的码率下能获得更好的图像重建质量。其中用基于优化的方法提高了基元图 复用时映射的准确程度，用基于块拼接的方法来保证基元图映射时相邻块之间 的一致性。 在此基础上，利用信号的稀疏表示方法对上述方案进行了改进。超完备冗 余表示和信号稀疏表示的最新研究成果表明：一个信号可由超完备字典稀疏表 示；由于高分辨率图像和对应低分辨率图像之间具有的几何相似性，高分辨率 图像块的几何特征可以从对应低分辨率图像块获得。将这一思想用于基元图映 射，即对每一个低质量基元图块求出其用超完备字典的稀疏表示，则对应的高 质量基元图块可以通过这些稀疏系数与字典中对应的高质量基元图块组合得 到。该问题可以用1 范式最优化的方式描述并求解，并且把相邻块之间的一致 性作为一个约束条件加入该问题的求解以进一步增强基元图映射时相邻块之间 的一致性。 实验结果表明，在低码率下，采用本文中的图像编码方案重建的图像的主 客观质量均优于j p e g 和j p e g 2 0 0 0 。 关键词图像压缩；低码率编码；基元图；稀疏表示 北京工业大学工学硕士学位论文 i i a b s t r a c t a b s t r a c t h u g ea m o u n to fd i g i t a li m a g e sp r o d u c e d f r o mt h ei n c r e a s i n gm u l t i m e d i a a p p l i c a t i o n sh a v em a d eg r e a tp r e s s u r et os t o r a g ea n dt r a n s p o r t s o i ti so fg r e a t i m p o r t a n c et or e s e a r c h o nt h et e c h n o l o g i e so fd i g i t a li m a g ec o m p r e s s i o n t h e r e e x i s t sm a n yk i n d so fr e d u n d a n c ei nt h eo r i g i n a li m a g ed a t a , a n dt h et a r g e tf o ri m a g e c o m p r e s s i o ni st or e m o v e t h e s er e d u n d a n c e t r a d i t i o n a li m a g ec o m p r e s s i o nm e t h o d s ， s u c ha st h ew i d e l yu s e ds t i l li m a g ec o m p r e s ss t a n d a r dd i s c r e t ec o s i n et r a n s f o r i l l ( d c t ) b a s e dj p e ga n di t s s u c c e s s i o nd i s c r e t ew a v e l e tt r a n s f o r m ( d w t ) b a s e d j p e g 2 0 0 0 ，a r ea l lb a s e do ni n f o r m a t i o nt h e o r y , a n dt h e yr e m o v et h er e d u n d a n c ei n t h ei m a g ef r o mt h ev i e wo fs i g n a lp r o c e s s i n g ，a n dt h e ya c h i e v eg r e a tc o m p r e s s i o n r e s u l t h o w e v e r , w h e nc o m e st ot h ea p p l i c a t i o n so fl o wb i t r a t ei m a g ec o m p r e s s i o n d u et ot h e l i m i to fc a p a b i l i t yo fp r o c e s s i n ga n ds t o r a g ef o rt e r m i n a ld e v i c ea n d b a n d w i d t hf o rt r a n s p o r t ，t h et r a d i t i o n a li m a g ec o m p r e s s i o nm e t h o d sw i l lp r o d u c e a n n o y i n ga r t i f a c t ss u c ha sb l o c ke f f e c ta n dr i n g r i n ge f f e c tf o rt h e i ri n h e r e n tn a t u r e ， w h i c hg r e a t l yd e g r a d e si m a g eq u a l i t y t os o l v et h i sp r o b l e m ，f r o mt h ev i e wo fc o m p u t e rv i s i o n , i nt h i sp a p e rw e p r o p o s ean o v e ll o wb i t r a t ei m a g ec o m p r e s s i o ns c h e m eb a s e do nt h el e a r n i n go f p r i m a ls k e t c h ，w h i c ht a k ef u l l u s eo ft h ef e a t u r eo fh u m a nv i s u a ls y s t e ma n dt h e r e u s eo fp r i m a ls k e t c hi n f o r m a t i o ni ni m a g e s i nt h es c h e m ew ep r o c e s so ne d g ea r e a si ni m a g e sw h i c ha r em o r es e n s i t i v et o h u m a ne y e s w ee x t r a c tt h eg e n e r a lp r i m a ls k e t c hi n f o r m a t i o nw h i c hc a nb er e u s e d a m o n gl o wb i t r a t ec o m p r e s s e di m a g e sf r o mas e to ft r a i n i n gi m a g e s ，a n dt h e nw e s t o r et h e mi nan o n p a r a m e t r i cw a yi nt h ec o d e b o o k s ot h ee n c o d e ro n l yn e e d st o c o m p r e s s t h e d o w n - s a m p l e dl o w r e s o l u t i o ni m a g e ，t h e nt h eh i g l lf r e q u e n c y i n f o r m a t i o nl o s tc a nb er e s t o r e da tt h ed e c o d e r 、析mt h eh e l po fp r i m a ls k e t c h i n f o r m a t i o ni nt h ec o d e b o o k f o rt h i sr e a s o n ，w ec a ng e tb e t t e rr e c o n s t r u c t i o ni m a g e q u a l i t ya t t h es a m eb i t r a t e s p e c i f i c a l l y , i nt h es c h e m ea l lo p t i m i z a t i o nb a s e d m e t h o di su s e dt oi m p r o v et h em a p p i n ga c c u r a c yi np r i m a ls k e t c hi n f o r m a t i o nr e u s e ， a n da ni m a g eq u i l t i n gm e t h o di su t i l i z e dt og u a r a n t e et h ec o m p a t i b i l i t yo fc u r r e n t b l o c ka n dn e i g h b o r i n gb l o c k si np r i m i t i v em a p p i n g b a s e do nt h i s ，as i g n a ls p a r s er e p r e s e n t a t i o nb a s e dm e t h o di su t i l i z e dt of u r t h e r i m p r o v e t h es c h e m e t h er e c e n tr e s e a r c h o n o v e r c o m p l e t er e d u n d a n c y r e p r e s e n t a t i o na n ds i g n a ls p a r s er e p r e s e n t a t i o nd e m o n s t r a t et h a t ，as i g n a lc a nb e s p a r s e l yr e p r e s e n t e db ya no v e r c o m p l e t ed i c t i o n a r y , a n dt h eg e o m e t r i c a lf e a t u r eo f i i i 北京工q k 大学t 学硕十学位论文 h i 曲r e s o l u t i o ni m a g ep a t c h c a l lb ei n f e r r e df r o mi t sc o u n t e r p a r ti nt h ec o r r e s p o n d i n g l o wr e s o l u t i o ni m a g eb e c a u s eo ft h eg e o m e t r i c a ls i m i l a r i t yb e t w e e nah i 曲r e s o l u t i o n i m a g ei t sl o wr e s o l u t i o nc o u n t e r p a r t w ea p p l yt h i st h e o r yi nt h ep r i m i t i v em a p p i n g p r o c e s s ，s p e c i f i c a l l y , w eg e t t h es p a r s er e p r e s e n t a t i o no fe a c hl o wq u a l i t yp a t c hw i t h a no v e r c o m p l e t ed i c t i o n a r y , a n di t sc o r r e s p o n d i n gh i g hq u a l i t yp a t c hc a l lb ei n f e r r e d b yc o m b i n i n gt h eh i g hq u a l i t yp r i m a ls k e t c hp a t c h e s i nt h ed i c t i o n a r yw i t ht h e s e s p a r s ec o e f f i c i e n t s t h ep r o b l e mc a l l b ef o r m u l a t e da n ds o l v e db yt h e11 一n o r m o p t i m i z a t i o n ，a n dt h ec o m p a t i b i l i t yo fn e i g h b o r i n gp a t c h e sc a nb ef o r m u l a t e d a sa c o n s t r a i n tt ot h ep r o b l e mt of u r t h e ri m p r o v et h ec o m p a t i b i l i t yo fn e i g h b o r i n gp a t c h e s d u r i n gp r i m i t i v em a p p i n g e x p e r i m e n t a lr e s u l t sd e m o n s t r a t e st h a ta tl o wb i t r a t e ，o u rs c h e m eo u t p e r f o r m s b o t hj p e ga n dj p e g 2 0 0 0i nt e r m so fb o t hs u b j e c t i v eq u a l i t ya n do b j e c t i v eq u a l i t y k e y w o r d si m a g ec o m p r e s s i o n ；l o w b i t - r a t e c o d i n g ；p r i m a ls k e t c h ；s p a r s e r e p r e s e n t a t i o n i v 摘要i a b s tr a c t i i i 第1 章绪论1 1 1 研究意义。l 1 2 国内外研究现状2 1 3 研究内容3 1 4 本文的内容安排和组织结构一4 第2 章数字图像压缩原理及其标准5 2 1 引言5 2 2 数字图像压缩的基础5 2 3 图像压缩分类及其基本编码方式6 2 3 1 无损压缩6 2 3 2 有损压缩8 2 4 图像压缩效果的评价1l 2 5 现有图像压缩标准1 2 2 5 1j p e g 图像压缩标准1 2 2 5 2j p e g 2 0 0 0 图像压缩标准1 4 2 6 本章小结15 第3 章基于基元图学习的低码率图像压缩1 7 3 1 引言。1 7 3 2 方案总体框架1 7 3 3 基元图表示的有效性1 8 3 4 基元图学习2 0 3 4 1 图像插值2 2 3 4 2 图像边缘检测2 5 3 5 基元图映射3 2 3 5 1 基于最d x - - 乘法的最优块匹配3 3 3 5 2 基于图像拼接的基元图块映射3 4 3 6 实验结果与分析3 7 3 7 本章小结4 5 第4 章基于基元图稀疏表示的低码率图像压缩4 7 4 1 引言。4 7 4 2 基于稀疏表示的基元图映射4 7 4 - 3 基元图码本优化5 0 4 4 实验结果与分析5 2 4 5 本章小结5 6 结论5 9 参考文献6 1 攻读硕士学位期间取得的研究成果6 5 v 北京丁业大学t 学硕士学位论文 致谢6 7 第1 章绪论 1 1 研究意义 第1 章绪论 随着信息技术和计算机互联网的飞速发展，人们面临着海量的数字图像信 号。图像的数字化表示使得图像信号可以方便并且高质量地传输，并便于图像 的检索、分析、处理和存储。但是受到目前终端存储设备和网络带宽的限制， 图像的数字化产生的大量数据对存储和传输都产生了巨大的压力。因此，高效 的数字图像压缩编码成为以数字化存储和传输为核心的多媒体应用中亟待解决 的基础科学问题之一。特别是高分辨率图像数据需要更大的存储和传输能力， 因此数字图像高效压缩编码的研究备受关注。 数字图像压缩的出发点就在于图像信息中存在着很大的冗余，数据之间存 在着紧密的相关性。通常在图像中存在着空间冗余、结构冗余、信息熵冗余以 及视觉冗余等，图像压缩的目的就是在一定的约束条件下除去这些冗余i z j ，寻 找最高效的信息表达方式。 一直以来，以信息论为指导的图像压缩方法，多是从信号处理的角度出发， 把图像作为一种信号变换到另一种去相关的表示，再利用人类视觉系统的特性 对不同成分进行不同精细程序的量化来去除其空间冗余和视觉冗余，进而编码 其变换系数来去除统计冗余【3 】。这样的编码框架在压缩效率和图像质量恢复上 已经取得了很好的成果，并产生了基于离散余弦变换的j p e g 4 1 和基于离散小波 变换的j p e g 2 0 0 0 1 5 j 图像压缩标准。目前j p e g 标准得到了广泛的应用，据统计 现在网络上百分之八十的图像压缩都是采用的j p e g 标准，并且它还广泛应用 于数码相机、打印机等各个方面。j p e g 2 0 0 0 作为j p e g 的替代标准，更是表现 出了优异的压缩性能以及其他的新特性。 但是在现今很多应用场合，受到终端设备处理存储能力和网络带宽的限制， 需要把低码率压缩的图像显示在高分辨率的终端屏幕上，或者放大部分细节进 行深入观察。典型的应用场景之一就是将处理能力有限的移动终端拍摄的低码 率图像显示在高分辨率的屏幕上。传统的压缩算法在低码率情况下，由于受到 变换量化等固有性质的影响，存在不同程度的块效应和振铃效应。在低码率情 况下，这些失真经过放大之后就会非常明显，严重影响图像的主观质量。 为了解决这类低码率图像压缩的问题，本文从计算机视觉的角度出发，充 分利用人类视觉系统对图像中基元图区域更敏感的特点以及基元图先验知识的 可重用性进行低码率图像压缩，并获得在同等码率下优于传统压缩方法的主客 观质量。 北京丁业大学工学硕十学位论文 1 2 国内外研究现状 z e n g 等较早尝试首先对原图像下采样后的低分辨率的图像作压缩，然后用 内插方法在解码端进行恢复，以适应低码率下图像编解码质量的提高【6 j 【7 1 1 8 i tj ，并 取得了不错的效果，但是这些基于图像处理本身的内插的恢复方案都还可以有 更大的提升空间。 d a v i dm a r r 在其著作l 倦o n 中从视觉计算理论出发，提出了视觉表示框架 的三个阶段，提出了“基元图”( p r i m a r ys k e t c h ) 的概念【9 j ：基元图由二维图像 中的边缘点、直线段、曲线、顶点、纹理等几何元素或特征组成，并将其作为 视觉表示框架中的一个中间阶段，如图1 - 1 所示： l 2 5 d 草图 下 l基元图 l 下 图像 图卜1m a r r 的图像视觉表示三阶段 f i g u r e1 - 1t h et h r e ep h a s e so fi m a g ev i s u a lr e p r e s e n t a t i o ni nm a r r st h e o r y 图像的基元图类似于绘画中素描图的轮廓，基元图的范例如图1 - 2 所示： a ) 原图 a ) o r i g i n a li m a g e 图1 - 2 基元图范例 f i g u r e1 - 2a ne x a m p l eo fp r i m a ls k e t c h b ) 基元图 b ) p r i m a ls k e t c h 第1 章绪论 基于基元图描述的图像首先要做的是边缘提取。作为这个思想的延伸，x r a n 等提出了利用一个三元的图像模型来进行图像编码【lo j i ，根据视觉特性将 图像分为基元图、平滑区域和纹理三部分。 为了能解决这类在高分辨率设备上显示输出低分辨率图像的问题，比较经 典的方法是把图像划分为边缘信息和纹理信息【1 2 1 1 3 】【1 4 l ，并对其分别处理。 f r e e m a n 等较早提出了用基于学习的方法来估计图像中的场景信息用于解决低 层次视觉问题。他们用马尔科夫网络来对图像建模，并从样本中学习网络的参 数。对于给定图像可以用b p 算法有效地找出场景的局部最大后验概率 1 5 1 0 l i uc e 等在人脸合成算法中利用大量高清晰人脸图像作样本集，从低分辨率人脸图像 合成出高分辨率人脸图俐怕j 。但是这种方法仅针对人脸图像，不具有一般性。 l i ud o n g 等提出了一种提高视觉质量的i n p a i n t i n g 图像压缩框架。源图像在编 码端被分析并且部分图像块被去除，从这些图像块中提取出某些信息作为辅助 信息传送到解码端。解码端利用这些辅助信息来指导去除区域的i n p a i n t i n g 恢复 1 1 7 】 o 在计算机视觉领域，人们已经就此展开了较深入的研究。h e r t z m a n 等提出 了一种称为图像类推的用样本来处理图像的新框架，新框架基于简单的多尺度 自回归，包括一个设计阶段和一个应用阶段【l 引。在自然图像统计意义下，人们 发现图像基元图的先验知识可以很好地用样本来表示。在此基础上，s u nj i a n 等提出了一种基于贝叶斯( b a y e s i a n ) 的方法用于图像超分辨率合成 ( h a l l u c i n a t i o n ) 1 9 l 。该方案证明了图像边缘特征的可重用性，并且对于任意低分 辨率图像，利用一组训练图像都可以合成( h a l l u c i n a t i o n ) 出- - 个高分辨率图像， 并且基元图先验信息可以从训练图像中获取以提高高分辨率图像的质量。w u f e n g 等则将这种基元图先验知识的思想结合到图像矢量量化中，与传统的图像 矢量量化中直接针对原图像块的做法不同，新方法中针对图像的视觉特征区域 也就是基元图区域以获得更好的效果【2 0 1 。在m al i n 等人的基于学习的压缩图像 修复方案中，借助于从训练图像集中学习的先验知识实现了去除图像压缩缺陷 并恢复图像的高频分量【2 1 i 。l iy a n g 等人则将基于基元图学习的方法与主流图像 压缩框架结合起来用于恢复图像在压缩过程中损失的高频信息田j 。这些来自计 算机视觉领域的思想为图像压缩开拓了新的思路。 1 3 研究内容 本课题属于国家8 6 3 计划课题“基于视频多维描述空间的视频自适应技术 研究 ( 2 0 0 6 a a 0 1 2 3 1 7 ) 子课题。本课题的研究内容是将图像的基元图先验知识 用于低码率图像压缩，具体是将其以何种形式组织以及如何对其复用以恢复图 较新的基于模型、基于小波分析和分形理论的图像压缩方法，并对现有的图像 压缩标准j p e g 和j p e g2 0 0 0 的关键技术和特性进行了细致分析。 第三章基于基元图学习的低码率图像压缩。在本章提出了一个基于基元图 学习的低码率图像压缩方案，并对方案的理论基础以及关键技术进行了详细的 分析，在此基础上给出了详尽的实验结果，说明了本方案在重建图像的主观和 客观质量方面都优于传统的图像压缩方法。 第四章基于基元图稀疏表示的低码率图像压缩。为了进一步提高基元图复 用时的映射准确度，本章采用基于超完备冗余字典稀疏表示的方法来求解最佳 映射。此外，为了减少压缩过程中产生的噪声对码本中训练样本的影响，利用 双边滤波器进行滤波处理。实验结果表明上述方法对方案有一定的改进。 最后，概括总结了本文的工作，并对未来的研究工作作了展望。 第2 章数字图像压缩原理及其标准 2 1 引言 第2 章数字图像压缩原理及其标准 视觉是人类获取知识和了解世界的主要途径和重要形式，人类大约有8 0 的 信息是通过视觉获得。随着信息技术发展，人们获取到了海量的数字图像信号， 数字图像信号已经成为通讯和计算机技术的一个重要的处理对象。由于计算机 处理能力和传输带宽以及存储空问的限制，对图像信号进行高效的压缩显得尤 为突出，图像信号的压缩编码已成为多媒体技术中的一个热门研究领域。目前 最主流的图像编码方法是基于变换的，通常通过变换、量化和熵编码来实现压 缩目的【2 3 l 。利用正交变换去除信号间的相关性，更加紧致地表达原信号，然后 进一步利用量化去除对视觉不重要的细节信息，最后进行熵编码消除统计冗余。 2 2 数字图像压缩的基础 从信号处理的角度理解，数字图像压缩就是对离散的图像信号进行某种变 换。借助这种变换，图像信号的表达更高效，从而更有利于存储和传输。从信 息论的角度理解，图像信息可以用各种形式来表示，但是不同表示形式的效率 并不相同，因此存在着信息冗余。图像压缩的目的就是在一定的约束条件下除 去冗余，寻找最高效的信息表达方式。数字图像压缩的出发点就在于图像信息 中存在着很大的冗余，数据之间存在着紧密的相关性，例如相邻像素之间亮度 值或颜色的相关性等。数字图像中存在的冗余信息主要有以下几种【2 4 j ： 1 空间冗余。空间冗余是指图像中相邻像素、相邻区域之间存在的较强的 空间相关性。通常在一幅图像中存在着若干个区域，区域内的像素具有相似的 亮度值。一般除了边缘点以外，相邻像素点之间的灰度值差值很小，而且有一 定的变化规律。 2 时间冗余。时间冗余是指动态图像中相邻图像之间存在的较强时域的相 关性。因为相邻图像之间的时间间隔很短，此外图像中的背景多为静止不变的， 只有前景中存在运动变化，所以相邻图像之间的差别很小。 3 结构冗余。在有些纹理图像或普通图像中的部分区域内存在着比较强的 纹理特征，或者是图像中的各个部分之间存在着比如自相似性等的某种关系， 这种相关性称为结构冗余。 4 知识冗余。在有些图像中包含的信息与某些先验知识有很强的相关性， 比如图像中特定的背景环境或者图像的结构等信息，这类规律性的信息可由先 验知识和背景知识得到。这种就是知识冗余。根据已有的知识，对某些图像中 北京t 业大掌工学硕l j 学位论文 所包含的物体构造出描述模型，并创建对应的各种特征的图像库，进行图像的 存储只需要保存一些特征参数，从而可大大减少数据量。知识冗余是模型编码 主要利用的特征。 5 信息熵冗余( 编码冗余) 。信息熵是指一组数据所携带的平均信息量。一 般图像中各像素点亮度值并不是等概率分布的，即各亮度值数据的信息熵是不 同的。由信息论相关理论可知，为了表示图像数据的一个像素点，只需要按照 其信息熵的大小相应地分配比特数即可。但是实际中对于图像数据中的每个像 素很难得到它的信息熵。所以在数字化一幅图像时，对每个像素都是使用相同 的比特数来表示，这样必然存在着冗余，即信息熵冗余。 6 视觉冗余。人类视觉系统对图像的处理是非均匀和非线性的，比如人眼 对亮度的敏感性远远高于色彩度，以及人眼的辨别能力与物体周围的背景亮度 成反比等。然而在用设备记录原始图像数据时，通常假设视觉系统是线性和均 匀的，对视觉敏感和不敏感的部分同等对待，从而产生了冗余的数据。人眼对 图像中的许多信息并不敏感，此外人类视觉系统并不能感知图像中的任何细微 变化，这些人眼对其不敏感或不能感知的信息就是视觉冗余信息。 图像压缩编码的基础在于图像信息的基本特性、信息理论( 信源) 和人眼视 觉特性( 信宿) 。图像压缩的目的就是要除去这些图像数据中的冗余信息，各种 图像压缩技术就是研究如何去除这些冗余信息以减少数据量。 2 3 图像压缩分类及其基本编码方式 数字图像压缩可以按图像质量是否有损失分为两类基本方法：无损压缩和 有损压缩。 2 3 1 无损压缩 无损压缩是指将图像中相同的或相似的数据或数据特征归类，从而使用较 少的数据量来描述原始数据，以达到压缩数据的目的。无损压缩也称为信息保 持编码，或叫做熵保持编码1 2 引。无损压缩可以无损失地恢复原始数据，但是通 常不能获得很高的压缩比。常用的无损压缩方法具体有如下几种： 1 、游程编码( r l e ) 游程编码( r u n 1 e n g t he n c o d i n g ) 是压缩一个文件最简单的方法之一，它适合 于信息源字符较少或者某些字符重复出现概率很高的情况。对于数字图像而言 就是不需要存储每一个像素的亮度值，而仅仅存储一个像素的亮度值以及具有 相同亮度的像素数目。游程编码就是把一系列的重复值( 例如图像中像素的亮度 第2 章数字图像压缩原理及只标准 值或色度值) 用一个单独的值再加上一个计数值来取代1 2 6 。例如有字符串 a a a b b c c c c d d d d d d d d ，它对应的游程编码就是3 a 2 b 4 c 8 d 。游程编码方式便于实现， 而且对于具有大量重复值的串压缩编码效果很好。例如对于有大面积的连续相 | 一的亮度或者颜色区域的图像，町以取得很好的压缩效果。实际应用中很多位 图文件格式都使用游程编码，例如t i f f 、p c x 和g e m 等。 2 、l z w 编码 l z w 编码是一种字典压缩算法，其压缩效率比较高，压缩速度较快。l z w 是由三个发明人名字的缩写( l e m p e l ，z i v ，w e l c h ) 组成，其原理是将每一个字 节的值与下一个字节的值配成一个字符对，并为这样的每个字符对设定一个代 码。当相同的一个字符对再次出现时，就用设定的代码代替这个字符对，然后 再用这个代码与下个字符配对。l z w 编码原理的一个重要特征是：代码不仅仅 能取代一串具有相同值的数据，也能够用来代替一串具有不同值的数据。具体 而言，在图像数据中若有某些不同值的数据经常重复出现，则也能找到一个代 码来代替表示这些数据串【2 7 1 。因此从原理上来讲，l z w 编码是优于游程编码的。 但是如果原始图像是带有随机变化的噪声图像实际中获取的图像往往都带 有不同程度的噪声，则很难利用l z w 算法进行压缩。当前广泛使用的g i f 、 t i f f 等图像格式都采用这种压缩方法。l z w 编码方法广泛用于文本数据和指 纹图像、医学图像等特殊应用场合的图像数据的压缩。 3 、霍夫曼编码 在对数据进行编码时，可对那些频繁出现的数据指定较少的比特数表示， 而那些不常出现的数据则用较多的比特数表示。有别于对所有数据使用相同长 度的比特数表示，用这种方法得到的代码的码长就是不固定的，故称为变长编 码。霍夫曼( h u f f m a n ) 在1 9 5 2 年根据香农( s h a n n o n ) 和范若( f a n o ) 阐述的这种编 码思想提出了一种根据数据出现概率变长编码的方法，也称霍夫曼编码 ( h u f f m a ne n c o d i n g ) 2 s 1 。霍夫曼编码是通过使用不固定长度的编码代替原始数 据来实现的。霍夫曼编码最初是为了应用于文本文件压缩而建立的，迄今已经 出现了很多变体。霍夫曼编码的基本方法是首先对图像数据扫描一遍，计算出 各个亮度值的像素出现的概率，然后按概率的大小指定不固定长度的唯一码字， 由此得到图像的霍夫曼码表。它的基本思想是对出现频率越高的值，其对应的 编码长度越短，反之对出现频率越低的值，其对应的编码长度越长。霍夫曼编 码是完全根据数据出现概率来构造编码的平均长度最短的码字，所以又称为最 佳编码。 霍夫曼编码很少能达到8 ：1 及更高的压缩比，此外它还有以下两个不足： ( 1 ) 、霍夫曼编码必须精确地统计出原始图像中每个像素值的出现频率，如果没 有这个精确统计，则压缩的效果就会很差，甚至根本达不到压缩的目的。霍夫 北京丁业大学工学硒! ：学何论文 曼编码通常要遍历两次原始图像，第一次进行概率统计，第二次才产生编码， 所以编码的过程很慢。另外由于变长编码的解码过程也比定长编码的解码过程 复杂的，因此霍夫曼解码过程也比较慢。( 2 ) 、霍夫曼编码对于编码中位的增删 很敏感。由于霍大曼编码的所有比特位都是合在一起，而不考虑字节的分位， 因此增加一位或者减少一位都会使解码结果产生巨大的变化。 4 、算术编码 算术编码和哈夫曼编码不同，它不采用一个码字代表一个输入信息符号的 方法，而是利用一个浮点数来代替一串输入符号。原始数据经算术编码后输出 一个小于l 大于或等于0 的浮点数，在解码端被正确地唯一地解码，从而恢复 原数据序列1 2 9 。由于算术编码可以对编码对象的概率分布进行自适应，其效率 要高于霍夫曼编码，现在正得到广泛的应用。 2 3 2 有损压缩 由于压缩比较低的限制，仅使用无损压缩方法不可能很好地解决数字图像 的存储和传输问题。有损压缩是有利用人眼的视觉特性有针对性地去除或者简 化人日艮察觉不到或者不敏感的数据，以达到减少总数据量的目的。有损压缩算 法常见的主要是预测编码、矢量量化编码和变换编码等。 1 、预测及内插编码 一般在图像中( 运动图像之间) 某些局部区域的像素是高度相关的，因此可 以用相邻的或者先前的像素亮度值来对当前像素的亮度进行预计，然后只需要 对较小的残差编码，这就是预测编码。预测编码法中最重要的一种是线性预测 法，通常也称为“差分脉冲编码调制 ( d p c m ) 。d p c m 编码的基本思想是用 反馈的方法预测估计值。内插编码就是根据先前( 帧) 的和后来( 帧) 的像素的亮 度值来预测当前( 帧) 像素的亮度值。如果预测和内插结果较为准确，则不必对 每一个像素的亮度值都进行编码，而是把预测值与实际像素值之间的差值经过 嫡编码后发送到接收端。在接收端通过预测值加上差值信号的方式来获得原像 素亮度值的重建 2 4 1 。 预测编码通常可以获得比较高的编码质量，并且实现简单，因而被广泛应 用于图像压缩编码系统。但是它的压缩比并不高，而且准确的预测依赖于图像 自身特性的大量先验知识，此外还必须做大量的非线性运算，因此预测编码一 般不单独使用，而是与其它编码方法结合起来。例如在j p e g 中使用预测编码 对d c t 变换直流系数进行编码，而对交流系数则综合使用了量化、游程编码和 霍夫曼编码的编码方法。 2 、矢量量化编码 第2 章数字图像压缩原理及其标准 矢量量化编码利用图像中相邻数据间的高度相关性，将输入图像数据分组， 每组m 个数据构成一个m 维矢量，对r f l 个数据一起进行编码，即一次对多个 像素点进行量化。根据香农率失真理论，对于无记忆信源矢量量化编码总是优 于标量量化编码。 在进行矢量量化编码前，先通过大量图像样本的训练或自组织特征映射神 经网络方法，从而得到一系列标准图像模式。其中每个图像模式就称为码字或 码矢，将这些码字或码矢组合在一起就称为码书( c o d e b o o k ) ，码书实际上就是 一个存放不同图像模式的库。输入图像块按照某种方式形成一个输入矢量，编 码时用这个输入矢量与码j b 中所有码字计算某种度量下的距离，找到距离最近 的码字即找到对应码本中的最佳匹配图像块。将该块的索引输出作为编码结果。 解码过程与之对应，根据编码结果中的索引从相同的码书中找到索引对应的码 字，从而获得解码结果【3 州。矢量量化的基本思想是用一组矢量的“质心 来近 似表示这一组矢量以达到压缩的目的，因此矢量量化编码是有损压缩。目前使 用较多的矢量量化编码方法主要是随机矢量量化，包括变换域矢量量化、有限 状态矢量量化、地址矢量量化、分类矢量量化等。 3 、变换编码 变换编码就是从信号处理的角度将图像亮度矩阵( 时域信号) 变换到某个系 数空间( 频域信号) 后再进行处理的方法。其依据是在空域具有强相关的信号， 变换到频域后能量的分布往往更集中，或者是变换系数矩阵的分布具有明显的 规律，即利用变换去除信号之间的相关性。我们可以利用这些规律根据人眼视 觉特性对频域内不同区域的系数进行不同处理以达到压缩的目的。由于正交变 换的变换矩阵是可逆的，并且其逆矩阵与转置矩阵相同，这就使对应的解码运 算是有解的且运算方便，因此运算矩阵总是选用正交变换来做。 常用的变换编码有k l 变换编码和d c t 编码。变换编码中理论上最佳的是 k - l 变换，其去相关最彻底，但k - l 变换目前尚无快速算法，并且其变换矩阵 随数据集变化因而不能广泛应用。而离散余弦变换( d c t ) 是一种实变换，去相 关能力仅次于k l 变换，性能最接近k l 变换，并且压缩效果好，有多种快速 算法，易于硬件实现【3 。 4 、模型编码 上述预测编码、矢量量化编码以及变换编码方法都属于波形编码，其理论 基础是信号处理理论和信息论，它们将图像信号看作是一种不规则的统计信号， 从像素亮度值之间的强相关性这种信号统计模型出发来设计编码器。而模型编 码则是从计算机视觉和计算机图形学的角度出发对图像信号进行分析与合成。 基于模型的图像编码技术是近几年发展起来的一种很有前途的编码方法。 它利用了计算机视觉和计算机图形学中的方法和理论，其出发点是在编码、解 北京t 业大学t 学硕上学位论文 码端分别建立起相同的模型，在编码端针对输入的图像提取模型参数如运动参 数、形状参数等，在解码端根据模型参数和已知模型重建图像。模型编码方法 的核心是对图像建立合适的模型和提取模型参数，其中模型的选取、描述和建 立是决定模型编码质量的关键因素。为了埘图像数据建模，一般要求对输入图 像要有某些先验知识。由于模型编码的对象是较少的特征参数而不是原始图像， 因此有可能实现比较高的压缩比瞄j 。然而在模型编码方法的研究中还存在如下 问题： l 、模型编码需要先验知识，不适合一般的应用； 2 、对不同的应用需要建立不同的模型； 3 、在线框模型中控制点的个数不易确定，还未找到有效的方法能根据图像 内容来选取； 4 、利用模型编码压缩后重建图像的大部分是用图形学的方法产生的，因此 看起来不够自然； 5 、传统的图像压缩误差评估准则不适合用于对模型编码的评价。 有损压缩方法利用了人类视觉系统对图像中的某些成分不敏感的特性，允 许图像在压缩过程中有一定的损失，这部分损失的信息对图像的影响不大，属 于可以接受的范围，因此