（计算数学专业论文）基于特征分类的快速分形图像编码方法研究.pdf

陬l lf , j k 人学硕i j 论文 摘要 图像以其确切性、直观性、高效性和广泛适应性，已成为当今人类社会最 重要的一种信息来源。为了有效地利用计算机处理图像信息，人们首先需要将 图像数字化。然而山于数字化图像的时空特性，它所包含的数据量非常巨大， 这给它的存储和传输都带来了很大的困难，因此图像压缩势在必行。目前人们 已经提出了很多压缩方法，而分形图像压缩作为一种新的压缩方法，因其具有 压缩比高、解码速度快、解码图像与分辨率无关等优点，十余年来引起了众多 学者的关注和研究。但是，这种方法存在一个最大的问题：编码时问过长，主 要是因为编码时定义域块的搜索量非常可观。这实际上已成为了该方法走向高 效能实用化的最主要障碍，因此分形编码加速方法已成为了近些年来分形压缩 的一个研究热点。目前许多分形编码加速方法或者以牺牲解码图像质量为代价， 或者加速效果不明显。 本文在快速分形编码方面作了以下研究工作： 1 提出了一种基于分形维数特征分类的快速分形编码方法。把灰度图像看作是 某种分数布朗运动形成的( 分形) 灰度表面，并用这种灰度表面的分形维数来 刻面它的纹理粗糙程度。在分形编码时，用这个维数值来对图像块进行分类， 大大减少了编码时定义域块的搜索数目，达到了加速编码的目的。在理论【：， 山于这种维数具有很好的分类能力，使得这种方法可取得很大的加速比；山 于这种维数是连续量，还可通过改变分类数目来调节解码图像的质量。我们 做了大量的数值实验，结果表明，在压缩比相同的前提下，与全局搜索法相 比，将图像块分为2 5 类时，可取得约1 7 倍的加速比，而解码质量只相差 1 5 7 4 9 5 1 d b ：另外，与其他分类方法的比较实验表明，本方法有更好的加速 效果和解码质量。 2 提出了一种基于矩不变量特征分类的快速分形编码方法。由于在分形编码时 值域块实际上是与经过灰度仿射变换之后的定义域块进行比较，因此我们首 先提出了一种在灰度仿射变换下保持不变的图像矩不变量，它可看作是 m a r i o 特征的推广。在分形编码时，用该不变量来对图像块进行分类，极大 地减少了编码时定义域块的搜索数目，达到了加速编码的目的。理论匕，这 i 科，不变量具有很好的分类能力，因而使用这种方法可取得很大的加速比；这 种不变量也是连续量，因此还可通过改变分类数目来调节解码矧像的质量。 大量的数值实验表明，在压缩比相同的阿提下，与全局搜索法相比，将图像 块分为2 5 类时，可取得约2 0 倍的加速比，而解码质量只棚差2 0 8 ；另外， ，j 其他分类方法的比较实验表明，本方法有更好的加速效果和解码质量。 3 提出了一种结合多种加速技巧的快速分形编码方法。基于值域块与其最优匹 配块有着相似的灰度分布这一思想，先将图像块分为阴影块和非阴影块，排 除了一部分要编码的值域块和要搜索的定义域块；再将剩余块按其四分子二块 的狄度均值和均方差排列顺序进行分类，免去了同类之外的块比较计算：撮 后通过计算同类中定义域块到值域块应进行的反射一旋转变换，进一步将定 义域块的搜索复杂度降低到原来的1 8 。实验结果表明，通过这几种加速技 巧的有机结合，编码速度得到了极大的提高。例如，相对于未经加速的全局 搜索编码，在不考虑压缩比的情况下，对l e n n a 图，可取得9 0 倍的加速比， 对p e p p e r s 图，可取得6 6 倍的加速比。在压缩比与全局搜索基本一致的情 况下，对l e r m a 图，可取得3 9 倍的加速比，对p e p p e r s 图，可取得2 2 倍的 加速比。这些情况下的解码质量均好于全局搜索所对应的结果。 4 提出了一种基于分形压缩的i 虱像放大方法。利用分形图像压缩的解码图像与 分辨率无关这一特点，对需要放大的图像，利用前面提出的快速分形编码进 行快速编码，得到编码参数，再用这些参数快速解码出所需要的分辨率的图 像。实验结果表明，相对于传统的双线性插值法，该方法对灰度变化不是很 剧烈的图像( 如p e p p e r s ) ，取得了较好的放大效果，对那些灰度变化较快的 图像( 如l e n n a ) 。得到的放大图像有少量的白噪声，但无论哪种图像该方 法都能较好地保持图像( 尤其是边缘的) 的细节。 关键词：分形图像压缩，迭代函数系统，分形维数，图像矩，快速编码， 特征分类 i i 两北l 。业大学坝卜论殳 a b s t r a c t i m a g e s h a v eb e c o m et h em o s t i m p o r t a n t s o u r c ef o r p e o p l e t o a c q u i r e i n f o r m a t i o nf r o mo u t s i d ew o r l db e c a u s e o fi t s c e r t a i n l y ，v i s u a l i z a t i o n h i g h e f f i c i e n c ya n dw i d e a d a p t a t i o n t op r o c e s si m a g e sw i t hc o m p u t e r se f f c c t i v e l y ， i m a g e s n e e d sd i g i t a l i z a t i o n ，h o w e v e r , b e c a u s eo fi t s t i m e s p a c ec h a r a c t e r i s t i c s ， d i g i t a li m a g e sp o s s e s sal a r g ea n a o u n to fd a t a ，m a k i n gi tv e r yi n c o n v e n i e n tf o rt h e i r s t o r a g e a n d t r a n s m i s s i o n , w h i c hu r g e n t l y n e c e s s i t a t e c o m p r e s s i o n o f i m a g e s r e s e a r c h e r sh a v e d e v e l o p e dm a n ym e t h o d sf o ri m a g ec o m p r e s s i o n ，a n d f r a c t a l i m a g ec o m p r e s s i o n ，a san e ws c h e m eo fi m a g ec o m p r e s s i o n ，h a sr e c e i v e dag r e a t d e a lo fa t t e n t i o na n ds t u d yf r o mr e s e a r c h e r sa l lo v e rt h ew o r l di nt h ef i e l do f i m a g e c o m p r e s s i o nb e c a u s eo fi t s d e s i r a b l ep r o p e r t i e ss u c ha sf a s t d e c o d i n g ，r e s o l u t i o n i n d e p e n d e n c eo fd e c o d e di m a g ea n dh i g hc o m p r e s s i o nr a t i o h o w e v e r , t h e r e sa e s p e c i a l l yu n s a t i s f y i n gp r o b l e mi nt h i s m e t h o d ：t o ol o n ge n c o d i n gt i m e ，m a i n l y b e c a u s eo ft h ec o n s i d e r a b l en u m b e ro fd o m a i nb l o c k st oc o m p a r ew i t hf o re a c h r a n g eb l o c ki ne n c o d i n gp h a s e ，w h i c h ，i nf a c t ，p r e v e n tf r a c t a li m a g ec o m p r e s s i o n f r o mb e c o m i n gap r a c t i c a lm e t h o df o ri m a g ec o m p r e s s i o n ，h e n c ef a s te n c o d i n gh a s b e c o m eah o ti s s u ei nf r a c t a li m a g ec o m p r e s s i o n e x i s t e df a s te n c o d i n gm e t h o d sa r e o f t e na tt h ec o s to f i m a g eq u a l i t y , o r c a l lo n l yo b t a i np o o r s p e e d - u pr a t i o i nt h i sd i s s e r t a t i o n ，s e v e r a ls p e e d u pt e c h n i q u e sf o rf r a c t a l i m a g ee n c o d i n g a r ep r o p o s e d ，a sf o l l o w s ： 1af a s tm e t h o df o rf r a c t a l i m a g ec o d i n gb a s e do nf r a c t a l d i m e n s i o ni s p r o p o s e d b yt a k i n gt h ei m a g e t ob ec o m p r e s s e da sag r e y l e v e ls u r f a c eo f s o m ef r a c t a lb r o w n m o t i o n ，t h ef r a c t a ld i m e n s i o n o ft h i ss u r f a c eg i v e so u t ag o o d d e s c r i p t i o no f i t st e x t u r ec h a r a c t e r i s t i c s t h e nt h ef r a c t a ld i m e n s i o n c a nb eu s e dt oc l a s s i f y i n gt h eb l o c k si nt h ee n c o d i n gp h a s e ，r e s u l t i n gi na g r e a tr e d u c t i o n t on u m b e ro fd o m a i nb l o c k st os e a r c hf o r , h e n c es h o r t e n i n g t h e e n c o d i n g t i m e d r a m a t i c a l l y ，t h e o r e t i c a l l y , f r a c t a d i m e n s i o n h a s p o w e r f u la b i l i t yt oc l a s s i f yi m a g eb l o c k s ，w h i c hr e s u l t si nb i gs p e e d u p i i i 两北_ t 业人学硕l 论文 r a t i oi nf i a c t a le n c o d i n g ；a n df r a c t a ld i m e n s i o ni sac o n t i n u o u sv a l u e ， w h i c he n a b l e su st oa d j u s tt h eq u a l i t yo fd e c o d e di m a g e sb yc h a n g i n gt h e n u m b e ro fc l a s s e s o u re x p e r i m e n t a lr e s u l t ss h o wt h a t ，c o m p a r i n gw i t h e x h a u s t i v es e a r c h ，w h e nt h ec l a s sn u m b e ri s2 5 ，w eo b t a i n 17t i m e s s p e e d u pr a t i o ，w i t ho n l yi m a g ed e g e n e r a t i o no f1 5 7 4 9 5 ld b ，a tt h es a m e c o m p r e s s i o nr a t i o c o m p a r e d w i t ho t h e rc l a s s i f i c a t i o ns c h e m e s ，o u r m e t h o dc a np r o v i d em o r es p e e d - u pa n db e t t e rq u a l i t yo f d e c o d e di m a g e 2 af a s tm e t h o df o rf r a c t a li m a g ec o d i n gb a s e do nak i n do fq u a d r a t u r e n o t e t h a ti nf r a c t a l e n c o d i n g ，e a c hr a n g e b l o c ki st o c o m p a r ew i t hd o m a i n b l o c k s 礤e rs o m eg r e y - l e v e l 礤n em a p h e n c e w ef i r s tp u tf o r w a r dak i n d o f i m a g eq u a d r a t u r ei n v a r i a n to f a f f i n em a p sa b o v e ，w h i c hc a nb et h o u g h t o fag e n e r a l i z a t i o no fm a r i of e a t u r e t h e nt h i s q u a d r a t u r e i su s e dt o c l a s s i f y i n gt h eb l o c k si nt h ee n c o d i n gp h a s e ，r e s u l t i n gi nag r e a tr e d u c t i o n t on u m b e ro fd o m a i nb l o c k st os e a r c hf o r , h e n c es h o r t e n i n gt h ee n c o d i n g t i m ed r a m a t i c a l l y t h e o r e t i c a l l y , t h i sq u a d r a t u r ec a nc l a s s i f yi m a g eb l o c k s e f f e c t i v e l y ，w h i c hb r i n g o u tb i gs p e e d u pr a i oi nf r a e t a le n c o d i n g ；a n dt h i s f e a t u r ei sac o n t i n u o u sv a l u e ，w h i c he n a b l e su st oa d j u s tt h eq u a l i t yo f d e c o d e di m a g e sb yc h a n g i n gt h en u m b e ro fc l a s s e s o u re x p e r i m e n t a l r e s u l t ss h o wt h a t ，c o m p a r i n gw i t he x h a u s t i v es e a r c h ，w h e nt h e c l a s s n u m b e ri s2 5 w eo b t a i n2 0t i m e s s p e e d u p r a t i o w i t h o n l yi m a g e d e g e n e r a t i o no f2 0 8 d b a tt h es a m ec o m p r e s s i o nr a t i o c o m p a r e d w i t h o t h e rc l a s s i f i c a t i o ns c h e m e s ，o u rm e t h o dc a np r o v i d em o r es p e e d u pa n d b e t t e rq u a l i t yo f d e c o d e d i m a g e 3 af a s tm e t h o df o rf r a e t a l i m a g ec o d i n gc o m b i n i n g s e v e r a l s p e e d - u p t e c h n i q u e si sp r o p o s e d b a s e do nt h ep r i n c i p l e t h a tr a n g eb l o c ks h o u l d s h a r es i m i l a ri n t e n s i t yd i s t r i b u t i o nw i t hi t sb e s t m a t c hd o m a i nb l o c k ，w c f i r s t l yc l a s s i f y a l l i m a g eb l o c k si n t o s h a d eb l o c ka n dn o n s h a d eb l o c k ， w h i c hm a k e s m a n yc o m p a r i s o n s b e t w e e nd o m a i nb l o c k sa n dr a n g eb l o c k s u n n e c e s s a r y t h e na l l t h en o n s h a d eb l o c k sa r ec l a s s i f i e di n t od i f f e r e n t i v 两北i 一业大学硕l 。论文 c l a s s e sb a s e do nt h ep e r m u t a t i o no fi n t e n s i t ya v e r a g e sa n dv a r i a n c e so f f o u rc h i l db l o c k s f i n a l l yt h ei s o m e t r i ct r a n s f o r m a t i o nf r o md o m a i nt o r a n g ei n t h es a m ec l a s si sm a d eo u td i r e c t l yh e n c er e d u c i n gt h et i m e c o m p l e x i t yo fr a n g e d o m a i nc o m p a r i s o nb y 8t i m e s o u re x p e r i m e n t a l r e s u l t si n d i c a t et h eg r e a ti m p r o v e m e n ti ns p e e d u po ff r a c t a ie n c o d i n gb y c o m b i n i n g a l lt h e t e c h n i q u e s a b o v e f o r e x a m p l e ，c o m p a r i n g w i t h e x h a u s t i v e s e a r c h ，r e g a r d l e s s o fc o m p r e s s i o nr a t i o ，w eg e t9 0t i m e s s p e e d u pr a t i o f o rl e n n a ，a n d6 6f o rp e p p e r s ；w i t ht h es a m ec o m p r e s s i o n r a t i o w eg e t3 9t i m e ss p e e d u pr a t i of o rl e n n aa n d2 2f o rp e p p e r s i nb o t h s i t u a t i o nt h eq u a l i t yo fd e c o d e di m a g ea r eb e t t e rt h a ne x h a u s t i v es e a r c h s 4 as c h e m eo fi m a g es c a l i n gb a s e do nf f a c t a lc o m p r e s s i o ni sp r o p o s e d m a k i n g u s eo fr e s o l u t i o ni n d e p e n d e n c eo f d e c o d e di m a g ei nf r a c t a li m a g e c o m p r e s s i o n ，f o rt h ei m a g et ob es c a l e d ，w eu s et h ef a s t f r a c t a lc o d i n g m e t h o d s p r o p o s e d a b o v et oe n c o d ei t ，h e n c eg e r i n gt h ec o d i n gp a r a m e t e r s ， w h i c hc a r lt h e nb eu s e df o rd e c o d i n gt h ec o m p r e s s e df i l e a ta r b i t r a r y r e s o l u t i o no u re x p e r i m e n t a lr e s u l t ss h o wt h a tf o rt h o s ei m a g e sw h o s e i n t e n s i t yv a r yn o td r a m a t i c a l l y ( s u c ha sp e p p e r s ) ，o u rm e t h o d c a np r o v i d e g o o dp e r f o r m a n c eo fs c a l i n g a n df o rt h o s ei m a g e sw h o s ei n t e n s i t yv a r y d r a m a t i c a l l y ( s u c ha sl e n n a ) ，t h e r ea r es o m ew h i t en o i s ei ns c a l e di m a g e s i nb o t hc a s eo u rm e t h o dc a r le f f e c t i v e l yk c e pe s p e c i a l l ym a r g i n a ld e t a i l so f i m a g e s k e y w o r d s ：f r a c t a li m a g ec o m p r e s s i o n ，i t e r a t e df u n c t i o ns y s t e m ，f r a c t a ld i m e n s i o n ， i m a g eq u a d r a t u r e ，f a s te n c o d i n g ，f e a t u r e c l a s s i f i c a t i o n v 两北j 业大学坝l 论殳 第一章图像压缩概述 1 1 引言 我们生活在一个信息社会中。所谓信息，简单的说就是我们f | 常生活q 1 通 过使用信息载体如文字、声音、图像等信号来传递的消息内容或者知识内涵等。 可见，信号是信息的载体，信息是信号的内容。为了有效地利用信息，我们就 需要对信息的载体一一信号进行获取、表示、存储、传输等各种处理，这样就 形成了信号处理这样一门学科。 信号处理这门学科从一开始就是伴随着计算机的发展丽发展起来的。特别 是随着现在计算机的计算速度越来越快，储存量越来越大它逐渐成为了信号 处理的核心。但是计算机只能处理简单的两个离散信号：0 和1 ，而我们在现实 世界中所感知的物理信号却是连续的模拟量，因此，利用计算机进行信号处理 的基础是作为连续量的信息的离散化，也就是信息数字化，通常这需要一个采 样和量化的过程。 信号被数字化了以后，就存在一个如何有效地组织数字来表示信息的问题， 这就是所谓的编码问题，因为对于同一信息，不同的人、不同的场合、不同的 要求下可能有不同的编码方式。将一种编码方式改进，变成另外种更加高效 的编码方式使其已录信息的储存空间减小，而同时保证信息能够完整的或者基 本完整地保留不变，就称为信息压缩。通常，这些信息的编码是使用数字实现 的，对于数字编码而言，这就称为数据压缩。本文要讨论的是数据压缩和数掘 压缩中的图像压缩。 1 2 图像压缩的必要- i 生 “百闻不如一见”，在所有的信号中，图像信号是最重要的一种。项心理 学的测定表明，人们通过感觉媒体( 即俗称的五官) 从外部世界获取并进入人 西北1 业大学帧l 论文 类人腑总的信息量中，视觉信息占了6 0 7 0 ，而在大脑对各种感觉信息的接 受能力的测定中，视觉信息的大脑吸收率为8 3 ，为各种信息吸收率之最。然 而，数字化的图像其数据量是极其巨大的，因为图像在计算机中是代表“像素 点”的数据位的集合，这导致在实两i 应用中存在两大问题：一是存储，二是传 输。考虑幅1 0 2 4 1 0 2 4 、有3 个彩色平面( 每个彩色平面用8 b i t 表示) 的扫 描图像，在未压缩状态下将占用3 1 4 5 7 2 8 字节( 不带头信息) 。再考虑运动图像 即视频情形，以p a l 制式( 2 5 帧，秒) 连续播放】0 秒钾的视频信息，如果每帧 是具有中等分辨率( 6 4 0 x 4 8 0 个像素) 、真彩色( 2 4 b i t p e r p i x e l ) 的图像，则每 帧的数据量是7 7 3 m b i t 。播出2 5 1 0 = 2 5 0 帧静止图像画面，需要的硬盘存储量 近2 3 0 m e g a b y t e ，同时要求硬盘的传输速度大于每秒1 8 0 m b i t 。显然，这对前者 开销太大，而对后者还根本达不到。如此巨大的存储空间和传输速率要求对当 前兴起的“视频点播”( v i d e oo nd e m a n d ，v d b ) 也是一个巨大的挑战。因此， 如何高效而又实时地压缩图像数据是多媒体技术中最关键的技术。因为很显然： 存储量越大，花销也就越大；传输的数据量越大，所需时问也就越多。 1 3 图像压缩的可能性 对于图像压缩，应从压缩的客体( 信源，即图像本身) 和主体( 信宿，即 人类视觉系统) 两个方面来考虑压缩的可能性这基于对以下两类信息冗余即 图像本身具有的数据冗余和人类视觉系统存在的视觉冗余的分析。 1 3 1 数据冗余 数据冗余是指图像信息本身所固有的冗余。信息论的鼻祖c e s h a n n o n 早在 1 9 4 8 年创立信息论的奠基性论文“通信的数学原理”中就提出了可以把数据看 作是信息量和冗余度的组合这个基本原理。用j r 表示信息量，d 表示数据量， 凰表示冗余量，则它们的关系可由下式给出： l = d r t 西北丁业大学碗卜论史 冗余的消除或减少是数据压缩的一个基本依据和理沦基础。如何压缩幽像数捌 中的冗余是本文讨论的中心问题。具体说来，图像信息本身存在以下些冗余： 1 空间冗余 在同一幅图像中，规则物体或规则背景的表面物理特性具有相关性。相邻 像素之间，行与行之问，条带( s l i c e ) 之间都存在空间冗余。 2 时间冗余 活动图像存在着很大冗余。图像序列中前后两帧图像之间的时f b j $ e 1 关性很 大，这反映为时间冗余。对于视频图像来说，相邻帧之倒的时间间隔很小。伍 1 2 5 秒或1 3 0 秒的帧间间隔内，景物运动部分在画面上的位移量很小或当场景 交替时整幅景物切换的概率极小。大多数像素点的亮度及色度信号帧问变化很 小或基本上不变。帧差信号的统计特性是视频帧间压缩编码( 预测编码) 的基 本依掘。空间冗余和时间冗余是图像数据中广泛存在而最重要的冗余。 3 信息熵冗余 信息熵是信源的平均信息量。信源以等概率分布时，熵取到最大值。熵最 大值与非等概率分布时熵值之间的差值就是信源含有的冗余度，我们称之为信 息熵冗余。这种冗余度寓于信源符号的非等概率分布之中的特性是数据压缩的 基本途径和重要方法之一。设法改变信源的概率分布使其尽可能的不均匀以达 到数据压缩之目的，这是统计压缩编码的理论基础。 4 结构冗余 有些图像在较大的区域存在很强的纹理结构，如草席、纺织物的图案等。 如果已知这些纹理的分布模式，可通过某一过程生成图像。 5 知识冗余 对许多图像的理解、分析、综合与一些基础知识相关。对于某些图像内容 确定的特定场合，可由先验知识、背景知识一类规律化的结构，建立图像景物 模型。这类冗余称为知识冗余。例如模型基编码( m o d e l b a s e dc o d i n g ) 用计算 机视觉、计算机图形学的知识，按照可视电话中图像和景物的先验知识，建立 一定的模型，用图像分析的方法，提取景物的参数，通过图像综合，将参数和 模型结合，获得重建图像。根据已有知识，对某些图像所包含的物体，我们可 炳北t 业大学顺1 ：论文 以构造其基本模型，并建立埘应各种特征的图像。这时，图像的存储只需存储 。些特征参数( 例如人的头像) 。 6 局部相似性，几余 给定图像某一区域，往往可以在该区域附近找到一个更大的区域，两者在 仿射变换下相等或非常接近，我们称图像的这种特性为局部相似性。根据这种 局部相似性，我们可以通过记录变换来代替对每个像素值的记录，从而减少图 像的数据量。分形编码正是利用图像的这种特性来压缩数据的。 7 图像区域的相同性冗余 在图像中的两个或多个区域所对应的所有像素值相同或相近，从而产生的 数据重复性存储，这就是图像区域的相同性冗余。在上述情况下，记录了一个 区域中各像素的颜色值，则与其相同或相近的其他区域就不需再记录其中各像 素的值。向量量化( v e c t o rq u a n t i z a t i o n ) 方法就是针对这种冗余性的图像压缩编 码方法。 8 纹理的统计冗余 有些图像纹理尽管不严格服从某一分布规律，但是它在统计的意义上服从 该规律。利用这种性质也可以减少表示图像的数据量，所以我们称之为纹理的 统计冗余。 1 3 2 视觉冗余 通常人们总是假定视觉系统是线性的和均匀的，对于人眼视觉敏感和不敏 感部分都同等对待，这必然会有许多冗余信息。通过对人类视觉所进行的大_ ：i ! ： 实验，发现了人类的许多视觉特性。例如，对亮度敏感而对色彩度欠敏感，这 正是分类编码能节省大量频带或数据的依据。视觉冗余大致有以f 方面： 1 视觉系统对图像的亮度和色彩度的敏感性相差很大： 2 随着亮度的增加，视觉系统对量化误差的敏感度降低： 3 人类的视觉系统总是把视网膜上的图像分解成若干个空间有向的频率通道后 再进一步处理； 两北r ：业大学砸i 论史 4 在编码时，若把图像分解成符台这一视觉内在特性的频率通道，则可能获得 较大的压缩比。小波编码就是在一定程度上利用了这一特性； 5 视觉对较高和较低的空间频率信息的敏感度弱于对中等频率信息的敏感度： 6 人眼视觉还存在分辨能力的冗余； 7 人类视觉系统还存在着视觉掩盖效应和马赫带效应等； 视觉冗余的利用是图像压缩编码理论的极为重要的组成部分。有关人类视 觉系统的更详细资料请参考 1 。 1 4 已有的图像压缩编码方法及国际标准“2 1 1 4 1 图像压缩编码的基本方法 对图像信息中不同冗余的利用，产生了不同的图像压缩方法。根据解压后 数据与原始数据是否完全一致进行分类。图像压缩编码方法大体上可分为两类： 有失真压缩编码和无失真压缩编码。 1 无失真编码 无失真编码又叫熵编码( e n t r o p yc o d i n g ) 。它是根据信息出现概率的分布特 性而进行的压缩编码技术，解码后能无失真地恢复原始图像。其方法是：识别 一个给定的码流中出现概率最高的比特或者字节模式，并用比原始比特更少的 比特数来对其编码，也就是说，出现概率越低的模式，其编码的位数就越多， 出现概率越高的模式编码位数就越少。如果码流中所有模式出现的概率相等， 则平均信息量最大，信源没有冗余。但由于无失真压缩技术在原理上大多采用 概率统计编码，因而一般对在内容上重复较多的数据压缩倍数较大，而对役有 重复或重复较小的数据，压缩倍数就较低。由于受到信源本身熵的限制( 编码输 出码字的平均码长，只能大于等于信源熵) ，无失真编码不可能取得高的压缩比， 一般平均压缩比在2 ：l 5 ：1 之间。常见的无失真编码方法有： 1 ) 行程编码( r u nl e n g t hc o d i n g ) 行程编码主要用于量化后出现大量连续重复出现的相同数据的情形，利用 行程来表示连续相同的数据，可以降低表示连续相同数据的数据量。 j 两北丁业大学硕士论文 2 ) h u f f m a n 编码 霍夫曼于1 9 5 2 年提出了对统计独立信源能达到最小平均码长的编码方法， 即最佳码，各码字氏度严格按照所对应符号出现概率的大小逆序排列。最佳性 可从理论上证明。这利码具有即时性和唯一可译性。但霍夫曼编码很少能达到 8 ：1 的压缩比，这主要是因为霍夫曼编码依赖于信源的统计特性，必须先统计得 到信源的概率特性才能编码。此外，霍夫曼编码缺乏构造性，即它不能用某种 数学方法建立起消息和码字之问的一一一对应关系，而只能通过某种查找表的方 法建立起它们的对应关系。 3 ) 算术编码 算术编码是由j r i s s a n e n 在1 9 7 6 年提出的一种二元码的熵编码方法。它是 把一个信源集合表示为实数线上的0 到l 之间的一个区间。陔区i 剖的位置与输 入数据的概率分布有关。可以根据信源的统计特性来设计具体的编解码器，也 可以针对未知概型的信源设计能够自适应其概率分布的算术编解码器。由于算 术编码能够自适应地逼近信源的概率分布特性，因此在对未知概率分布的信源 编解码时，算术编码要优于h u f f m a n 编码，所以在实际中得到了广泛的应用。 2 有失真编码 有失真压缩编码方法主要是利用人的视觉特性使解压后的图像看起来与原 始图像一样，但实际上它们之间是存在一定差别的。有失真编码对熵进行了压 缩，从而减少了信息量，而这些损失的信息是不能再恢复的。因而这类编码技 术往往可以获得较大的压缩比。有失真编码可分为以下几类。 1 ) 预测编码 预测编码是根据图像在帧内和帧问的相关性以及人眼的视觉特性，利用前 面一个或多个像素值来预测当前值，然后对当前值与预测值之差进行编码。预 测编码分为无失真预测编码和有失真预测编码。前者是指不对预测误差进行量 化，不丢失任何有效信息；而后者则需对预测误差进行量化处理。差分脉冲编 码调制法( d p c m ) 是有失真预测编码的典型代表。 预测编码的不足之处是当传输过程中出现误码时，会导致解码图像中的大 片区域失真。因此预测编码要求可靠性很高的信道，一般要增加新的纠错编码， 6 两北丁业人学顺l 论义 为了防止误码的扩散，可以每隔一定时间将预测系数设为零。 2 ) 变换编码 变换编码是有失真编码的一种重要的编码类型。在变换编码中，原始数据 在初始空问或时间域中进行数学变换，使得信号中最重要的部分( 例如包含大 量能量的最重要的系数) 在变换域中易于识别，并且集中出现，可以重点处理； 相反使能量较小的部分较分散，可以进行粗处理。 数学家们已经构造了多种数学变换。例如离散傅里叶变换( d f t ) 、离散余弦 变换( d c t ) 、w a l s h h a d a m a r d 变换、k a r h u n e n l o e v e 变换( k l 变换) 和小波变换 ( w t ) 等。其中较为常用的是d c t 变换和小波变换。 在所有的正交变换中，k l 变换是最小均方误差意义下的最佳变换，但由 于k i 变换的基函数是与信源本身相关的，因此对每幅不同图像都需要重新计 算其基函数，因而其空间和时间开销很大，复杂度也最高。出于k - l 变换的压 缩率比较高，误差小，它通常作为各种变换编码压缩效果的比较标准。 d c t 是逼近于k l 变换的次最优变换，由于它具有快速算法，区i 而得阻广 泛的应用。目前国际上已经制定了基于d c t 的静态图像压缩标准j p e g 和运动 图像压缩标准m p e g 等。采用基于d c t 方法的压缩算法由于d c t 本身的限制 使得图像的压缩率有所限制，且没有很好地利用人眼的视觉特性来对图像进行 压缩，因而在图像压缩方法上还不是最优的。 基于小波变换的压缩方法本质上使用多尺度或多分辨率方法对图像进行分 解。分解后图像被分成了低频分量、水平分量、垂直方向以及对角方向的高频 分量，然后利用人眼对对角方向的高频分量、水平和垂直方向的高频分量、低 频分量的灵敏度的依次增加来对压缩图像。进行多级分辨率分解后，数据量的 取舍n j 。以逐渐增大。因此获得的压缩比会相应的增大。 由于小波变换本身的特性及其所具有的与人眼的视觉特性相结合的性质， 使得小波变换在很多方面超过了离散余弦变换。目前讵在推广的j p e g 2 0 0 0 和 m p e g 4 就将小波变换作为其内核技术之一。 3 ) 子带编码( s u b b a n dc o d i n g ，简称s b c ) 子带编码利用带通滤波器组把信号频带分割成若干子频带，然后分别处理。 ? 通过等效于单边带调幅的调制过程，将各子带搬移到零频率附近以得到低遁表 示后，再以奈奎斯特y q u i s t ) 速率对各子带输出取样，并对取样值进行通常的 数字编码。恢复时，将各予带信号解码并重新调制回其原始位置，再将所有子 带输出相加就可得到接近于原始信号的恢复波形。 4 ) 量化编码 量化法是一种基于语义的编码方法，是一种很有前景的方法。其基本思想 是采羽非线性量化器，即列空闯频率及能量分布较大的系数分配较多比特数， 也就是采用较小的量化步长；反之则分配较少的比特数，即采用较大的量化步 长，从而达到压缩的目的。 量化包括标量量化和矢量量化。s h a n n o n 率失真理论指出，即使对无记忆 信源，矢量量化编码总优于标量量化编码。但矢量量化编码的计算量较大，且 设计起来也较标量量化编码复杂。 5 ) 分形编码 分形编码是一种模型编码，它利用了分形几何中自相似的原理。首先刘图 像进行分块，然后再去寻找各块之间的相似性，这里自相似的描述主要是依靠 仿射变换来确定的，一旦找到了每块的仿射变换，于是就保存下这个仿射变换 的系数，由于每块的数据量远大于仿射变换的系数，因而图像得以大幅度的压 缩。其独特新颖的思想，已成为目前数据压缩领域的研究热点。它与经典的图 像压缩编码方法相比，在思想上有了重大的突破。其突出特点是高压缩t b 、解 码速度快和解码图像与分辨率无关等。 6 ) 模型编码 模型基图像编码首先由瑞典的f o r c h e i m e r 等人于1 9 8 3 年提出，经过近十 年的努力，已出了许多的技术方案。这些方案可以粗略的分为两类：第一类是 基于限定景物的模型基图像编码。景物里的物体三维模型为严格已知的，称为 “语义基”( s e m a n t i c b a s e d ) 图像编码，；而第二类则是针对未知物体的模型蜒 图像编码，需要实时构造物体的模型( 没有先验知识的) ，称为“物体基” ( o b j e c t b a s e d ) 图像编码。语义基方法可以有效的利用景物中已知物体的知识， 以实现非常高的压缩比，但它仅能处理已知物体，并需要较复杂的图像分析与 r 识别技术。物体基方法可以处理更一般的对象，已知的和未知的。闻为不需要 复杂的先验知识和模式识别技术，对于图像的分析要简单的多，可不受电视电 话中头肩图像的限制，因而预期有更广泛的应用前景，但因未能充分利用景物 的知识，或只能在低层次上运用物体知识，编码效率无法同语义基方法相比。 因此应根据实际需要来决定具体选用哪一类方法。 1 4 2 图像压缩编码的国际标准概述 目前有关图像压缩编码的国际标准有h 2 6 1 建议，j p e g 标准，m p e g 系列 标准，h 2 6 3 标准等。这些标准实际上都是博采各种编码