（计算数学专业论文）快速分形图像编码及高压缩比纹理压缩方法研究.pdf

摘要 分形图像压缩作为一种新的压缩方法， 因其具有压缩比高、 解码速度快、 解 码图像与分辨率无关等优点，卜 余年来引起了众多学者的关注和研究。 但是， 这 种方法存在一个最大的问题: 编码时间过长， 主要是因为编码时定义域块的搜索 量非常可观。 这实际上已成为了该方法走向高效能实用化的最主要障碍， 因此分 形 编码 加 速方 法已 成 为了 近些 年 来分 形 压 缩的 一 个 研究 热点。 目 前 许多 分形 编 码 加速方法或者以牺牲解码图像质量为代价， 或者加速效果不明显。 本文提出了一 种混合的快速分形编码方法， 将分形编码的父块库看作向量空间， 通过正交特征 量化将子块和父块的匹配转化为欧式空间的最小距离问题， 在分类的基础上， 将 向 量子空间建立成k d - t r e e ， 匹配问 题进一步转化为在树结构上的 最近邻居查找问 题， 再引入( 1 + 动 最近邻居查找进一步加速， 可达到实时编码。 试验结果表明 ， 同 以 往的方法相比， 本方法在基本保证解码质量的基础上， 可以极大地提高分形编码 速度. 同不加速分形编码相比 ， 混合方法带旋转反射变换编码速度可以提高 6 6倍， 不带旋转反射变换可以 提高6 5 3 倍. 纹理是图像处理， 图像真实感造型领域的很重要的概念， 其自 身有很多独特 的性质使其可获得高压缩比。 将纹理看成是图像本身的局部性质， 就可将纹理压 缩与传统压缩方法结合起来弥补后者的不足。 成熟的纹理压缩方法都是荃于硬件 的， 纹理压缩的高压缩比潜力并没有充分被发挥出来。 矢量量化技术的码书训练 原理与纹理的纹元重复特性刚好一致， 并且纹理合成方法的成熟发展为纹理的纯 算法压缩提供了方向。 本文提出了新的纹理压缩方法， 将纹理进行采样， 用矢量 量化技术从中训练出码书， 与传统矢量量化不同， 不再进行键集编码， 而是以码 书作为编码结果， 这就是高压缩比的关键，以 此码书作为纹理合成的“ 样图” ， 利用纹理合成技术作为解码过程。 如果是块采样， 则用基于块的纹理合成， 如果 是象素采样， 则用基于象素的纹理合成。 试验结果表明本方法保证解码质量的基 础上可以获得很高的压缩比， 而且可以 根据图像的质量控制压缩比， 由于纹理合 成的 优势， 还可以 解码出任意尺寸的图像，在保证逼真度的 基础上，可以 获得 3 2 : 1 或更高的压缩比。 x. ia : 分形图像压缩 迭代函数系统 快速编码 特征分类 k d 树 矢量 量化 纹理合成纹理压缩 ab s t r a c t f r a c t a l i m a g e c o m p r e s s i o n , a s a n e w s c h e m e o f i m a g e c o m p r e s s i o n , h a s r e c e i v e d a g r e a t d e a l o f a t t e n t i o n a n d s t u d y f r o m r e s e a r c h e r s a l l o v e r t h e w o r l d i n t h e f i e ld o f i m a g e c o m p r e s s i o n b e c a u s e o f i t s d e s ir a b l e p r o p e rt i e s s u c h a s f 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 e o f d e c o d e d i m a g e a n d h i g h c o m p r e s s i o n r a t i o . h o w e v e r , t h e r e i s a e s p e c i a l l y u n s a t i s f y i n g p r o b l e m i n t h i s m e t h o d : t o o l o n g e n c o d i n g t i m e , m a in l y b e c a u s e o f t h e c o n s i d e r a b l e n u m b e r o f d o m a i n b l o c k s t o c o m p a r e w i t h f o r e a c h r a n g e b l o c k i n e n c o d i n g p h a s e , w h i c h , i n f a c t , p r e v e n t f r a c t a l i m a g e c o m p r e s s i o n f r o m b e c o m i n g a p r a c t i c a l m e t h o d f o r i m a g e c o m p r e s s i o n , h e n c e f a s t e n c o d i n g h a s b e c o m e a h o t i s s u e i n f r a c t a l i m a g e c o m p r e s s i o n . e x i s t e d f a s t e n c o d i n g m e t h o d s a r e o f t e n a t t h e c o s t o f im a g e q u a l i t y , o r c a n o n l y o b t a i n p o o r s p e e d - u p r a t i o . i n t h i s w e g i v e a h y b r i d o f f r a c t a l c o d i n g f r a c t a l i m a g e e n c o d i n g t e c h n i q u e , w h i c h t a k e s o n t h e d o m a i n p a p e r , b l o c k s i s a v e c t o r s p a c e , t r a n s f o r m s t h e m a t c h o f t h e r a n g e b l o c k a n d t h e d o m a i n b l o c k i n t o t h e m i n i m i z e d d i s t a n c e p r o b l e m o f t h e e u c l i d s p a c e , e s t a b l i s h e s k d - t r e e f o r e a c h s u b - s p a c e a t b a s i s o f c l a s s i f y i n g , f u r th e r t r a n s l a t e s t h e m a t c h p r o b l e m i n t o t h e n e a r e s t n e i g h b o r s e a r c h o n t r e e s t r u c t u r e a n d i n t r o d u c e s i + s n e a r e s t n e i g h b o r s e a r c h t o m o r e s p e e d u p . i t c a n r e a c h r u n - t i m e c o d i n g . t h e e x p e r i m e n t s i n d i c a t e t h a t c o m p a r e d t o t h e o l d m e t h o d , o u r m e t h o d c a n s p e e d u p t h e f r a c t a l e n c o d i n g p e r f e c t l y . c o m p a r e d w i t h n o s p e e d i n g - u p c o d i n g , w h e n e = 1 4 , t h e h y b r id f r a c t a l .i m a g e c o d i n g c a n i m p r o v e 6 6 t i m e s w i t h r o t a t i o n a n d r e fl e c t i o n t r a n s f o r m a t i o n s , a n d c a n i m p r o v e 6 5 3 t i m e s w i t h o u t r o t a t i o n a n d r e fl e c t i o n t r a n s f o r m a t i o n s . t e x t u r e i s a n i m p o rt a n t c o n c e p t o f t h e i m a g e p r o c e s s i n g a n d i m a g e t h i r d d i m e n s i o n s c u l p t i n g w h o s e m a n y s p e c i a l p r o p e r t i e s m a k e i t o b t a i n h i g h c o m p r e s s i o n r a t i o . t a k i n g t e x t u r e a s t h e l o c a l p r o p e rt y o f i m a g e s w e c a n c o m b i n e t h e t e x t u r e c o m p r e s s i o n a n d t r a d i t i o n a l c o m p r e s s io n m e t h o d s t o o ff s e t t h e d i s a d v a n t a g e o f t h e l a t t e r . t h e a d v a n c e d t e x t u r e c o m p r e s s i o n m e t h o d s a r e a l l b a s e d o n h a r d w a r e , s o t h e p o t e n t i a l o f h i g h c o m p r e s s r a t i o c o u l d n t s h o w e d c o m p l e t e l y . t h e t h e o r y o f t r a i n i n g c o d e b o o k o f v e c t o r q u a n t i z a t i o n a c c o r d s w i t h t h e r e p e t i t io n p r o p e rt y o f t h e t e x t o n , a n d t h e d e v e l o p m e n t o f t h e s y n t h e s i s m e t h o d s g i v e t h e t e x t u r e c o m p r e s s i o n t h e n e w w a y . i n t h i s p a p e r , w e g i v e a n e w t e x t u r e c o m p r e s s i o n m e t h o d , w h i c h s a m p l e s t h e t e x t u r e , t h e n t r a i n s t h e c o d e b o o k b y v e c t o r q u a n t i z a t i o n a n d t a k e s t h e c o d e b o o k a s a r e s u l t o f c o d i n g , a s i s d i ff e r e n t f o r m c o n v e n t i o n a l v e c t o r q u a n t i z a t i o n . t h e c o d e b o o k i s t a k e n o n a s t h e s a m p l e t e x t u r e o f t e x t u r e s y n t h e s i s , a n d t h e d e c o d i n g j u s t i s t e x t u r e s y n t h e s i s . i f u s i n g b l o c k s s a m p l i n g , t h e d e c o d i n g p r o c e s s i s t e x t u r e s y n t h e s i s b a s e d o n b l o c k s . a n d i n s t e a d o f p i x e l s s a m p l i n g , t h e o n e i s b a s e d o n p i x e l s . t h e e x p e r im e n t s i n d i c a t e t h a t w h e n i n s u r i n g t h e q u a l i t y w e c a n a tt a i n h i g h c o m p r e s s i o n r a t i o , c o n t r o l i t , a n d g e t d e c o d i n g i m a g e o f r a n d o m s i z e . g u a r a n t e e i n g t h e f i d e l i t y , w e c a n g e t a r a t i o o f 3 2 : 1 o r m o r e . k e y w o r d s : f r a c t a l i m a g e c o m p r e s s i o n f u n c t i o n i t e r a t e d s y s t e m . r a p i d c o d i n g f e a t u r e c l a s s i f y i n g k d - t r e e v e c t o r q u a n t i z a t i o n t e x t u r e s y n t h e s i s t e x t u r e c o mp r e s s i o n nt 西北工业大学硕士论文 第一章 图像压缩概述 1 . 1引言 在日 常生活中， 人们总是不断的借助电话、电视、 广播电台、因特网等方式 获取或发送信息， 其目的就是借助一定形式的信号进行交流。 古代中国利用烽火 传送边疆报警， 希腊人借助火炬位置表示字母符号， 这就是最原始的光通信系统。 利用击鼓鸣金来报送时刻或传达命令， 这就是声信号通讯方式。1 9世纪以 来， 人们开始采用电信号传送信息，如1 8 3 7 年莫尔斯发明了电报，用点， 划，空的 适当组合表示数字和字母。1 8 7 6年贝尔发明了电话，直接将声信号变为电信号 沿导线传输。1 9世纪末赫兹等人致力于用电 磁波传送无线信号，从而使电 信号 的 通讯方式得到广泛的 应用和迅速发展如今，人们可方便地利用电 话、 寻呼机、 移动电 话以至卫星和计算机互联网 进行语音， 图像和数据等各种信号的传输。 可 见人们在不断追求利用信号进行信息的交流和传送。 信号是信息的载体， 信息是 信号的内容。 人们不断的寻找更合适的方式来加工和处理信号以便更有效地利用 信息， 这样就形成了信号处理这样一门学科。 在文献中， 常常会碰到 “ 信号” 和数据这两个词， 通常意义上， 信号是指大 小随时间变化的物理量。 从广义上讲， 信号是时间或空间变量的函数， 可以是离 散的或连续的， 信号可以描述一维的语音信号也可用来描述二维的图像信号。 数 据常常是离散时间信号。 近年来数据常常与数字信号联系在一起即离散时间离散 幅度的信号。 相比具有连续时间和连续幅度的模拟信号，数字信号的明显优点是便于传 输， 存储， 交换， 加密和处理等。 数字信号存在一个如何有效地组织来表示信息 的问题， 这就是所谓的编码问题， 因为对于同一信息， 不同的编码方式并不影响 人们的理解。 将一种编码方式改进， 变成另外一种更加高效的编码方式使其记录 信息的储存空间减小， 而同时保证信息能够完整的或者基本完整地保留不变， 就 称为信息压缩。通常，这些信息的编码是使用数字实现的，对于数字编码而言， 这就称为数据压缩。本文要讨论的是数据压缩中的图像压缩。 一一一一一一一一一一一n j l t 0 : 竺 i t 1 . 2图像压缩的必要性 “ 百闻不如一见” ，在所有的信号中，图像信号是最重要的一种。一项心理 学的测定表明， 人们通过感觉媒体 ( 即俗称的五官) 从外部世界获取并进入人类 大脑总的信息量中，视觉信息占了 6 0 % a - 7 0 %，而在大脑对各种感觉信息的接受 能力的测定中，视觉信息的大脑吸收率为8 3 %，为各种信息吸收率之最。然而， 数字化的图像其数据量是极其巨大的，因为图像在计算机中是代表“ 像素点” 的 数据位的集合， 这导致在实际应用中 存在两大问 题: 一是存储， 二是传输。 考虑 一幅1 0 2 4 x 1 0 2 4 、有3 个彩色平面 ( 每个彩色平面用8 b i t 表示)的 扫描图 像， 在未压缩状态下将占 用3 1 4 5 7 2 8 字节 ( 不带头信息) 。再考虑运动图 像即视频情 形，以p a l制式 ( 2 5 帧 / 秒) 连续播放1 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 ，播出公x 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 o o n d 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年创立信息论的莫基性论文 “ 通信的数学原理”中就提出了可以把数据看 作是信息量和冗余度的组合这个基本原理。 用i 表示信息量， d表示数据量， r e 一一一一一一一一一一一n j l t 0 : 竺 i t 1 . 2图像压缩的必要性 “ 百闻不如一见” ，在所有的信号中，图像信号是最重要的一种。一项心理 学的测定表明， 人们通过感觉媒体 ( 即俗称的五官) 从外部世界获取并进入人类 大脑总的信息量中，视觉信息占了 6 0 % a - 7 0 %，而在大脑对各种感觉信息的接受 能力的测定中，视觉信息的大脑吸收率为8 3 %，为各种信息吸收率之最。然而， 数字化的图像其数据量是极其巨大的，因为图像在计算机中是代表“ 像素点” 的 数据位的集合， 这导致在实际应用中 存在两大问 题: 一是存储， 二是传输。 考虑 一幅1 0 2 4 x 1 0 2 4 、有3 个彩色平面 ( 每个彩色平面用8 b i t 表示)的 扫描图 像， 在未压缩状态下将占 用3 1 4 5 7 2 8 字节 ( 不带头信息) 。再考虑运动图 像即视频情 形，以p a l制式 ( 2 5 帧 / 秒) 连续播放1 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 ，播出公x 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 o o n d 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年创立信息论的莫基性论文 “ 通信的数学原理”中就提出了可以把数据看 作是信息量和冗余度的组合这个基本原理。 用i 表示信息量， d表示数据量， r e 西北工业大学硕 t 论文 表示冗余量，则它们的关系可由下式给出: 冗余的消除或减少是数据压缩的一个基本依据和理论基础。 如何压缩图像数据中 的冗余是本文讨论的中心问题。具体说来，图像信息本身存在以下一些冗余: 1 .空间冗余 在同一幅图像中， 规则物体或规则背景的表面物理特性具有相关性。 相邻像 素之间， 行与行之间， 条带( s l i c e ) 之间都存在空间冗余。 2 .时间冗余 活动图像存在着很大冗余。图像序列中前后两帧图像之间的时间相关性很 大，这反映为时间冗余。对于视频图像来说，相邻帧之间的时间间隔很小。在 1 / 2 5秒或 1 / 3 0秒的帧间间隔内，景物运动部分在画面上的位移量很小或当场景 交替时整幅景物切换的概率极小。 大多数像素点的亮度及色度信号帧间变化很小 .a 基 本 上不 变。 帧差 信号 的 统计 特性 是 视 频 帧间 压缩 编码( 预 测 编码) 的 基 本依 据。空间冗余和时间冗余是图像数据中广泛存在而最重要的冗余。 3 . 信息墒冗余 信息嫡是信源的平均信息量。 信源以 等概率分布时， 嫡取到最大值。 墒最大 值与非等概率分布时嫡值之间的差值就是信源含有的冗余度， 我们称之为信息嫡 冗余。 这种冗余度寓于信源符号的非等概率分布之中的特性是数据压缩的基本途 径和重要方法之一。 设法改变信源的概率分布使其尽可能的不均匀以达到数据压 缩之目的，这是统计压缩编码的理论基础。 4 .结构冗余 有些图像在较大的区域存在很强的纹理结构， 如草席、 纺织物的图案等。 如 果己知这些纹理的分布模式，可通过某一过程生成图像。 5 知识冗余 对许多图像的理解、 分析、 综合与一些基础知识相关。 对于某些图像内容确 定的特定场合， 可由先验知识、 背景知识一类规律化的结构， 建立图像景物模型。 这类冗 余称为知识 冗余。 例如模型基编码( m o d e l - b a s e d c o d i n g ) 用计算机 视觉、 计算机图形学的知识， 按照可视电 话中图 像和景物的先验知识， 建立一定的 模型， 用图 像分析的方法， 提取景物的参数， 通过图像综合， 将参数和模型结合， 获得 西北工业大学硕士论文 重建图像。 根据已 有知识， 对某些图 像所包含的物体， 我们可以 构造其基本模型， 并建立对应各种特征的图像。 这时，图像的存储只需存储一些特征参数 ( 例如人 的头像) 。 6 .局部相似性冗余 给定图像某一区域， 往往可以在该区域附近找到一个更大的区域， 两者在仿 射变换下相等或非常接近， 我们称图 像的这种特性为局部相似性。 根据这种 局部 相似性， 我们可以通过记录变换来代替对每个像素值的记录， 从而减少图 像的数 据量。分形编码正是利用图像的这种特性来压缩数据的。 7 .图像区域的相同性冗余 在图像中的两个或多个区域所对应的所有像素值相同或相近， 从而产生的数 据重复性存储， 这就是图像区域的相同性冗余。 在上述情况下， 记录了一个区域 中各像素的颜色值，则与其相同或相近的其他区域就不需再记录其中各像素的 值。向 量量化( v e c t o r q u a n t i z a t i o n ) 方法就是针对这种冗余性的图像压缩编码方 法。 8 .纹理的统计冗余 有些图像纹理尽管不严格服从某一分布规律， 但是它在统计的意义上服从该 规律。 利用这种性质也可以减少表示图像的数据量， 所以我们称之为纹理的统计 冗余。 1 . 3 . 2 视觉冗余 通常人们总是假定视觉系统是线性的和均匀的， 对于人眼视觉敏感和不敏感 部分都同等对待， 这必然会有许多冗余信息。 通过对人类视觉所进行的大量实验， 发现了人类的许多视觉特性。 例如， 对亮度敏感而对色彩度欠敏感， 这正是分类 编码能节省大量频带或数据的依据。 视觉冗余大致有以 下方面: 1 . 视觉系统对图像的亮度和色彩度的敏感性相差很大: 2 .随着亮度的增加，视觉系统对量化误差的敏感度降低; 3 .人类的视觉系统总是把视网膜上的图像分解成若干个空间 有向的频率通道后 再进一步处理; 4 . 在编码时，若把图像分解成符合这一视觉内在特性的频率通道，则可能获得 较大的压缩比。小波编码就是在一定程度上利用了 这一特性; 西北j 一 业大学硕 卜 论文 5 .视觉对较高和较低的空间频率信息的 敏感度弱于对中等频率信息的敏感度; 6 .人眼视觉还存在分辨能力的冗余; 7 .人类视觉系统还存在着视觉掩盖效应和马赫带效应等; 视觉兀余的利用是图像压缩编码理论的极为重要的组成部分。 有关人类视觉 系统的更详细资料请参考 1 0 妇. 4 已有的图像压缩编码方法及国际标准， 1 (2 1 . 4 . 1 图像压缩编码的基本方法 对图像信息中不同冗余的利用， 产生了不同的图像压缩方法。 根据解压后数 据与原始数据是否完全一致进行分类， 图像压缩编码方法大体上可分为两类: 有 失真压缩编码和无失真压缩编码。 1 .无失真编码 无失真编码又叫嫡编码( e n t r o p y c o d i n g ) 。 它是根据信息出 现概率的分布特性 而进行的压缩编码技术， 解码后能无失真地恢复原始图像。 其方法是: 识别一个 给定的码流中出现概率最高的比 特或者字节模式， 并用比原始比 特更少的比 特数 来对其编码， 也就是说，出 现概率越低的模式， 其编码的位数就越多，出 现概率 越高的模式编码位数就越少。 如果码流中所有模式出 现的概率相等， 则平均信息 量最大， 信源没有冗余。 但由于无失真压缩技术在原理上大多采用概率统计编码， 因而一般对在内容上重复较多的数据压缩倍数较大， 而对没有重复或重复较小的 数据， 压缩倍数就较低。由 于受到信源本身嫡的限制( 编码输出 码字的平均码长， 只能 大于 等于 信源嫡) ， 无失 真编 码不可能 取得高的 压缩比， 一 般平 均压缩比 在 2 : 15 : 1 之间。常见的无失真编码方法有: 1 ) 行程编码( r u n l e n g t h c o d i n g ) 行程编码主要用于量化后出 现大量连续重复出 现的相同数据的情形， 利用行 程来表示连续相同的数据，可以降低表示连续相同数据的数据量。 2 ) h u ff m a n 编码 霍夫曼于 1 9 5 2 年提出了对统计独立信源能达到最小平均码长的编码方法， 即最佳码， 各码字长度严格按照所对应符号出 现概率的大小逆序排列。 最佳性可 西北j 一 业大学硕 卜 论文 5 .视觉对较高和较低的空间频率信息的 敏感度弱于对中等频率信息的敏感度; 6 .人眼视觉还存在分辨能力的冗余; 7 .人类视觉系统还存在着视觉掩盖效应和马赫带效应等; 视觉兀余的利用是图像压缩编码理论的极为重要的组成部分。 有关人类视觉 系统的更详细资料请参考 1 0 妇. 4 已有的图像压缩编码方法及国际标准， 1 (2 1 . 4 . 1 图像压缩编码的基本方法 对图像信息中不同冗余的利用， 产生了不同的图像压缩方法。 根据解压后数 据与原始数据是否完全一致进行分类， 图像压缩编码方法大体上可分为两类: 有 失真压缩编码和无失真压缩编码。 1 .无失真编码 无失真编码又叫嫡编码( e n t r o p y c o d i n g ) 。 它是根据信息出 现概率的分布特性 而进行的压缩编码技术， 解码后能无失真地恢复原始图像。 其方法是: 识别一个 给定的码流中出现概率最高的比 特或者字节模式， 并用比原始比 特更少的比 特数 来对其编码， 也就是说，出 现概率越低的模式， 其编码的位数就越多，出 现概率 越高的模式编码位数就越少。 如果码流中所有模式出 现的概率相等， 则平均信息 量最大， 信源没有冗余。 但由于无失真压缩技术在原理上大多采用概率统计编码， 因而一般对在内容上重复较多的数据压缩倍数较大， 而对没有重复或重复较小的 数据， 压缩倍数就较低。由 于受到信源本身嫡的限制( 编码输出 码字的平均码长， 只能 大于 等于 信源嫡) ， 无失 真编 码不可能 取得高的 压缩比， 一 般平 均压缩比 在 2 : 15 : 1 之间。常见的无失真编码方法有: 1 ) 行程编码( r u n l e n g t h c o d i n g ) 行程编码主要用于量化后出 现大量连续重复出 现的相同数据的情形， 利用行 程来表示连续相同的数据，可以降低表示连续相同数据的数据量。 2 ) h u ff m a n 编码 霍夫曼于 1 9 5 2 年提出了对统计独立信源能达到最小平均码长的编码方法， 即最佳码， 各码字长度严格按照所对应符号出 现概率的大小逆序排列。 最佳性可 西北工业大学硕 i - 论文 从理论上证明。这种码具有即时性和唯一可译性。但霍夫曼编码很少能达到8 : 1 的压缩比， 这主要是因为霍夫曼编码依赖于信源的统计特性， 必须先统计得到信 源的概率特性才能编码。 此外， 霍夫曼编码缺乏构造性， 即它不能用某种数学方 法建立起消息和码字之间的一一对应关系， 而只能通过某种查找表的方法建立起 它们的对应关系。 3 ) 算术编码 算术编码是由j .r i s s a n e n 在 1 9 7 6 年提出的一种二元码的嫡编码方法。它是 把一个信源集合表示为实数线上的0 到1 之间的一个区间。 该区间的位置与输入 数据的概率分布有关。 可以根据信源的统计特性来设计具体的编解码器， 也可以 针对未知概型的信源设计能够自 适应其概率分布的算术编解码器。 由于算术编码 能够自 适应地逼近信源的概率分布特性，因此在对未知概率分布的信源编解码 时，算术编码要优于h u f f m a n 编码，所以在实际中得到了广泛的应用。 2 .有失真编码 有失真压缩编码方法主要是利用人的视觉特性使解压后的图像看起来与原 始图像一样， 但实际上它们之间是存在一定差别的。 有失真编码对嫡进行了 压缩， 从而减少了信息量， 而这些损失的信息是不能再恢复的， 因而这类编码技术往往 可以获得较大的压缩比。有失真编码可分为以 下几类。 1 7预测编码 预测编码是根据图像在帧内和帧间的相关性以及人眼的视觉特性， 利用前面 一个或多个像素值来预测当前值， 然后对当前值与预测值之差进行编码。 预测编 码分为无失真预测编码和有失真预测编码。 前者是指不对预测误差进行量化， 不 丢失任何有效信息; 而后者则需对预测误差进行量化处理。 差分脉冲编码调制法 c d p c m)是有失真预测编码的典型代表。 预测编码的不足之处是当传输过程中出现误码时， 会导致解码图像中的大片 区域失真。 因此预测编码要求可靠性很高的信道， 一般要增加新的纠错编码， 为 了防止误码的扩散，可以每隔一定时间将预测系数设为零。 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 变换 ) 和小波变 换 ( wt ) 等。 其中较为常用的是d c t 变换和小波变换。 在所有的正交变换中， k - l变换是最小均方误差意义下的最佳变换， 但由 于 k - l 变换的基函数是与信源本身相关的， 因此对每幅不同图像都需要重新计算其 基函数，因而其空间和时间开销很大，复杂度也最高。由于 k - l变换的压缩率 比较高，误差小，它通常作为各种变换编码压缩效果的比较标准。 d c t是逼近于k - l变换的次最优变换，由于它具有快速算法，因而得以 广 泛的 应用。目 前国际上已经制定了基于d c t的静态图像压缩标准j p e g和运动 图像压缩标准m p e g等。采用基于d c t方法的压缩算法由于d c t本身的限制 使得图 像的压缩率有所限 制， 且没有很好地利用人眼的视觉特性来对图像进行压 缩，因而在图像压缩方法上还不是最优的。 基于小波变换的压缩方法本质上使用多尺度或多分辨率方法对图像进行分 解。 分解后图像被分成了 低频分量、 水平分量、 垂直方向以及对角方向的高频分 量， 然后利用人眼对对角方向的高频分量、 水平和垂直方向的高频分量、 低频分 量的灵敏度的依次增加来对压缩图像。 进行多级分辨率分解后， 数据量的取舍可 以 逐渐增大，因此获得的压缩比会相应的增大。 由于小波变换本身的特性及其所具有的与人眼的视觉特性相结合的性质， 使 得小波变换在很多方面超过了离散余弦变换。目前正在推广的 j p e g 2 0 0 0和 m p e g - 4 就将小波变换作为其内核技术之一。 3 ) 子带编码( s u b b a n d c o d i n g ， 简称s b c ) 子带编码利用带通滤波器组把信号频带分割成若干子频带， 然后分别处理。 通过等效于单边带调幅的调制过程， 将各子带搬移到零频率附近以 得到低通表示 后， 再以 奈奎斯特( n y q u i s t ) 速率对各子带输出取样， 并对取样值进行通常的 数字 编码。 恢复时， 将各子带信号解码并重新调制回其原始位置， 再将所有子带输出 相加就可得到接近于原始信号的恢复波形。 4 )量化编码 西北工业大学硕 论文 量化法是一种基于语义的编码方法， 是一种很有前景的方法。 其基本思想是 采用非线性量化器， 即对空间频率及能量分布较大的系数分配较多比特数， 也就 是采用较小的量化步长; 反之则分配较少的比特数，即采用较大的量化步长， 从 而达到压缩的目的。 量化包括标量量化和矢量量化。 s h a n n o n 率失真理论指出，即使对无记 忆信 源， 矢量量化编码总优于标量量化编码。 但矢量量化编码的计算量较大， 且设计 起来也较标量量化编码复杂。 5 )分形编码 分形编码是一种模型编码， 它利用了分形几何中自 相似的原理。 首先对图 像 进行分块， 然后再去寻找各块之间的 相似性， 这里自 相似的描述主要是依靠仿射 变换来确定的， 一旦找到了每块的仿射变换， 于是就保存下这个仿射变换的系数， 由于每块的数据量远大于仿射变换的系数， 因而图像得以大幅度的压缩。 其独特 新颖的思想， 己 成为目 前数据压缩领域的研究热点。 它与经典的图像压缩编码方 法相比， 在思想上有了重大的突破。 其突出 特点是高压缩比、 解码速度快和解码 图像与分辨率无关等。 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 ) 图 像编码。 语义基方法可以有效的利用景物中己知物体的知识， 以实现非常高的压 缩比， 但它仅能处理已 知物体， 并需要较复杂的图像分析与识别技术。 物体基方 法可以处理更一般的对象， 已知的和未知的。 因为不需要复杂的先验知识和模式 识 别 技 术， 对 于 图 像 的 分 析 要 简 单 的 多 ， 可 不 受电 视电 话 中 头 肩图 像 的 限 制， 因 而预期有更 广泛的 应用前景， 但因未能 充分利用景 物的知识， 或只能在低层次上 运用物体知识， 编码效率无法同语义基方法相比。 因此应根据实际需要来决定具 体选用哪一类方法。 西北工业大学硕 论文 1 . 4 . 2图像压缩编码的国际标准概述 目 前有关图像压缩编码的国际标准有h .2 6 1 建议， j p e g标准，mp e g系列 标准， h .2 6 3 标准等。 这些标准实际上都是博采各种编码方法之长的优化组合的 混合编码系统。 它们是4 0 余年尤其是近 1 0 年来图像编码理论与技术丰硕的成果 和经验的总结与集成。 1 . h .2 6 1 建议 h .2 6 1 建 议是c c i t t ( i t u - t 的 前身 ) 于1 9 9 0 年1 2 月 通过的 有关图 像( 视 频 ) 压缩编码的第一个国际化标准建议。 它采用了预测、 变换、 嫡编码， 集中了各自 优势， 充分利用视觉特性， 是一种成功的高效而实用的混合编码方案。 它对图像 格式， 视频数据流的层次化结构， 彩色空间的选定等一系列问题做出了规定， 这 些也是其他有关标准共同的规定 h .2 6 1 的制定，主要对象是m x 6 4 k b p s 和n x 3 8 4 k b p s 两类码率。 当时i s d n蓬勃发展，考虑到i s d n的定义以及网络接口等技术动向 这是因为 。h . 2 6 1 最 初的设想是作为 h .3 2 0 主要组成部分， 主要用于可视电话和会议电视， 其图像质 量的要求不很高， 能在i s d n的p x 6 4 k b p s ( 1 _ p o ，3 n ：d ( x 。，x 。) p ，v n ，m n 定义2 2 2 4 ( 完备度量空间) 度量空间( x ，d ) 被称为是完备的( c o m p l e t e ) ，如 果z 中的每一c a u c h y 列都收敛到x 中的一点。 定义2 2 2 5 ( 紧性)度量空间( x ，d ) 称为是紧的( c o m p a c t ) 当且仅当它是闭 的( c l o s e d ) 且全有界的( b o u n d e d ) 。 2 2 3 分形空间 从严格的数学观点分析，分形集一般是( 矗”，d ) 或( 0 ，d ) 空间上的紧子集，这 一 翌i ! 三些查兰堡主丝兰 些空间常用( ，d ) 表示。要研究分形，必然要考察( ，d ) 上的非空紧子集构成的 空间f ( x 1 。 定义2 2 3 1设( 工，矗) 是完备度量空间， x x ，b f ( ) ， 称 d ( x ，b ) 2 r a 。i n d ( x ，y ) 为点x 到口的距离。 由于b 的紧性，所以这个定义中的最小值是存在的。 定义2 2 3 2 如果_ f ( x ) 是度量空间( x ，d ) 的子集，则a 的万一平行体是与 ( x ，d ) 的距离小于占的点的闭集，即 乓= x x ，d ( x ，4 ) 艿 定义2 2 3 3 ( h a u s d o r f f 度量) 设( x ，d ) 是完备度量空间，a ，b f ( x ) ，则称 h a a ，b ) = i n f 3 ：a c 岛且b c 呜 为a ，b 间的h a u s d o r f f 度量。 容易验证，九是空间，( ) 上的一个度量，它能被用来测量任意两幅图像之 间的“距离”。若( ，d ) 是一个完备的度量空间，则如果在x 的非空紧子集空间 f ( ) 上赋予度量，( f ( x ) ，) 就是一个度量空间，我们称之为“分形空间”。 所有对分形的研究都以此空间为舞台，因此进一步了解分形空