小波变换与图像压缩课件.

1、 周三例会报告周三例会报告 26/11 /2014 上海大学上海大学 数字图像处理数字图像处理图像压缩图像压缩 OUTLINE:OUTLINE: 图像压缩图像压缩 1.香农信息论香农信息论 2.数据压缩原理数据压缩原理 3.数据冗余数据冗余 4.无损压缩无损压缩 5.有损压缩有损压缩 Wavelet Exchange图像压缩图像压缩为什么要图像压缩?减少表示数字图像时需要的数据量目的目的什么是图像压缩?24真彩色16色位256色位768kb128kb257kb图像压缩基础-香农信息论 说明：一个消息若能传达给我们许多原来未知的内容，我们就认为这个信息很有意义，信息量大；反之，一个消息传达给我们

2、的是已知确定的东西，则这个传达就失去了意义。 生活实例生活实例 第一句话：我有一个师兄叫“*”。 第二句话：我大学舍友是个男生。直观的感受一下这两句话所携带的未知信息量。 信息信息图像压缩基础-香农信息论-信息量在信息论中：信息使用不确定的度量来确定的，一个消息的可能性越小，其信息含量越大；消息的可能性越大，其信息含量越小。设某消息 发生的概率为 ，则该消息携载的信息量为： 1）当 时，则单位为比特（bit）； 2）当 时，则单位为奈特（nat）； 3）当 时，则单位为哈特（hat）。一般以2为底取对数，由此定义的信息量等于描述该信息所用的最少比特数。信息量信息量 logiiaI xp x i

3、p x2a ae10a 图像压缩基础-香农信息论-信息量在信息论中：信息使用不确定的度量来确定的，一个消息的可能性越小，其信息含量越大；消息的可能性越大，其信息含量越小。设某消息 发生的概率为 ，则该消息携载的信息量为： 1）当 时，则单位为比特（bit）； 2）当 时，则单位为奈特（nat）； 3）当 时，则单位为哈特（hat）。一般以2为底取对数，由此定义的信息量等于描述该信息所用的最少比特数。信息量信息量 logiiaI xp x ip x2a ae10a 图像压缩基础-香农信息论-信息熵信息熵信息熵 信息熵信息熵 若信源有 个字符，对应字符 的概率为 ，则该信源的平均信息量就称为信息熵

4、，既： 具体到数字图像中，称 为图像信息熵。它给出了描述一幅图像携载信息量的最少比特数。112200loglogiLLiiiiinnHpxpxnn nix ip xH图像压缩基础-香农信息论-图像编码图像编码图像编码 图像编码图像编码 码本：码本：编码所用符号的集合称为码本。 如 码字：码字：对每个码本的每个符号所赋的符号序列称为码字。如 码字长度：码字长度：每个码字里的符号个数称为码字长度。数字图像：码长 = 二进制数长度。0123456A,aaaaaaa001011a图像压缩基础-香农信息论-香农定理香农无失真香农无失真编码定理编码定理 Shannon Shannon无失真编码定理无失真编

5、码定理 基于图像信息熵，存在一种无失真的编码方法，使编码的平均码长与信息熵无限的接近。既：但以 为下限，既 。这就是Shannon的无失真编码定理。 无失真编码性能的几个指标： 1 1）编码效率）编码效率 2 2）冗余度）冗余度 或 3 3）压缩比）压缩比 n1：编码后的大小 n2：编码前的大小,0avgLHavgLHa v gHL1100%DR12RnCn11DRRC 图像压缩基础-图像压缩原理 1）数据压缩的对象是数据，大的数据量并不代表含有大的信息量。 2）图像压缩就是除去图像中多余的数据而对信息没有本质的影响。 3）图像压缩是以图像编码的形式实现的，用较少的比特数表示出现概率较大的灰度

6、级，用较多的比特数表示出现概率较小的灰度级，从而使平均码长更接近于信息熵。图像压缩基础-图像压缩质量评判标准压缩图像灰阶f(xf(xi i,y,yi i) )均方误差：均方误差：nimjjifjifmnMSE112),( ),(1规范化均方误差：规范化均方误差： , ,2fMSENMSEnimjfjifmn112),(1对数信噪比：对数信噪比：)(log10log102dBNMSEMSESNRf图像压缩基础-数据冗余 1)1)信息熵冗余：信息熵冗余：也称编码冗余，如果图像中平均比特数大于该图像的信息熵，则图像中存在冗余，这种冗余称为信息熵冗余。 2)2)空间冗余：空间冗余：也称为像素间冗余或几

7、何冗余，是图像内部相邻像素之间存在较强的相关性所造成的冗余。 3)3)时间冗余：时间冗余：视频图像序列中的不同帧之间的相关性所造成的冗余。 4)4)视觉冗余：视觉冗余：是指人眼不能感知或不敏感的那部分图像信息。 5)5)结构冗余：结构冗余：是指图像中存在很强的纹理结构或自相似性。 6) 6)知识冗余：知识冗余：是指有些图像还包含与某些先验知识有关的信息。 1)1)信息熵冗余：信息熵冗余：也称编码冗余，如果图像中平均比特数大于该图像的信息熵，则图像中存在冗余，这种冗余称为信息熵冗余。 2)2)空间冗余：空间冗余：也称为像素间冗余或几何冗余，是图像内部相邻像素之间存在较强的相关性所造成的冗余。 3

8、)3)时间冗余：时间冗余：视频图像序列中的不同帧之间的相关性所造成的冗余。 4)4)视觉冗余：视觉冗余：是指人眼不能感知或不敏感的那部分图像信息。 5)5)结构冗余：结构冗余：是指图像中存在很强的纹理结构或自相似性。 6) 6)知识冗余：知识冗余：是指有些图像还包含与某些先验知识有关的信息。有损压缩有损压缩无损压缩无损压缩图像压缩基础-图像压缩的类型标准量化和矢量量化编码预测编码行程编码模型法编码变换编码字典编码香农-范诺编码哈弗曼编码算术编码无损编码无损编码n图像压缩无损压缩-行程编码 行程行程：是指字符序列中各个字符连续重复出现而形成字符串的长度。 行程编码行程编码（游程编码）：就是将字符

9、串序列映射成字符串的长度和串的位子的标志序列。 例如例如：一个字符串00000000 111 888.888 1111 0000000000000000 111 888.888 1111 00000000 8 8个个 3 3个个 5050个个 4 4个个 8 8个个 行程编码：0 x08,0 x00,0 x03,0 x01,0 x50,0 x08,0 x04,0 x01,0 x08,0 x00 1020100000222220110201000002222201 行程编码：0 x01,0 x01,0 x01,0 x00,0 x01,0 x02,0 x01,0 x00, 0 x05,0 x00,

10、0 x05,0 x02,0 x01,0 x00,0 x01,0 x01 改进： 0 x01,0 x00,0 x02,0 x01,0 xFF,0 x05, 0 x00,0 xFF,0 x05,0 x02,0 x00,0 x01无损压缩-字典编码 基于字典编码方法是用以前处理过的数据来表示编码过程中遇到的重复部分，或者基于字典编码方法是用以前处理过的数据来表示编码过程中遇到的重复部分，或者从输入的数据中创建一个短语字典，表示在编码过程中再遇到该短语，则用字典中短从输入的数据中创建一个短语字典，表示在编码过程中再遇到该短语，则用字典中短语的语的“索引号索引号”来表示该短语。字典编码的算法有来表示该短

11、语。字典编码的算法有LZ77,LZSS,LZ78LZ77,LZSS,LZ78和和LZWLZW。无损压缩-香农-范诺编码 具体步骤如下： a）将信源符号按出现的概率 由大到小排列； b）将信源A分成两个子集并且保证 成立或差不多成立； c）给两个子集赋不同的码元值； d）重复（2）、（3），既对每个子集再一分为二，并赋予不同的码元值，直到每个子集仅含一个符号为止。 01k 12120112AAkknkkknaaaaaap ap ap ap ap ap a和01knijij kp ap a ip a 假设有一个信源为 ，其概率分布为：0123456A,a a a a a a a0a1a2a3a4a

12、5a6a无损压缩-香农-范诺编码010101111000010010111011101111011111香农-费诺编码示意图计算香农-费诺编码平均码长为：101 0.430.230.1630.1240.0650.0450.022.380NavgkkkLB P 无损压缩-霍夫曼（Huffman）编码 霍夫曼编码法是消除编码冗余最常用的方法。 假设有一个信源为A=A,B,C,D，其组成的字符串为AABCCDA,其概率分布为：无损压缩-霍夫曼（Huffman）编码A3/7B1/7C2/7D1/7A3/7C2/72/7BDA3/74/7CBA1A0D1B0C01 AABCCDA001101010111

13、0结果无损压缩-算术编码算术编码法和霍夫曼编码法都是一种变长变长编码。但霍夫曼编码必须分配整数位码字，而算数编码可以分配带有小数的比特数目信符，并且算术编码给整个信源符号序列分配一个单一的算术码字。假设有一信源为A=b,c,a,d,cA=b,c,a,d,c，信源中各符号出现的概率分别为： p(a)=0.2 p(b)=0.3 p(c)=0.4 p(d)=0.1p(a)=0.2 p(b)=0.3 p(c)=0.4 p(d)=0.1步骤 “当前区间”初始化0,1）1将“当前区间”分成子区间，该子区间的长度正比于符号的概率2对于输入信源中的每个符号，依次执行如下两个步骤： 选择下一个信符对应的子区间，

14、并使它成为新的“当前区间”3 在最后一个“当前区间”中任找一个数作为算数编码的输入码4无损压缩-算术编码算术编码示意图 输出区间0.3728,0.37376） 0.01011111011,0.01011111101） 取位数最少的一个数: 0.010111111 不考虑“0.”，则编码输出为:010111111 算数编码法： 霍夫曼编码法： 91.8/5avgL比特字符1.9/avgL比特 字符Ab,c,a,d,c有损压缩-变换编码变换编码是采用一种可逆线性变换（正交变换），把图像从空间域映射到变换域的系数集合，然后对这些变换系数进行量化和编码。变换编码方法编码、解码示意图有损压缩-变换编码

15、子图像分解子图像分解 将一副大小为MxN的输入图像分解成大小为nxn的子图像。如88 1616 原因： 距离远的像素之间的相关性比较差； 小块图像的变换比较容易。 量化量化 系数选择（滤波）：区域法和阈值法 量化：小数系数变成整数 编码编码 变长编码法 正交变换正交变换 将一副图像从空间域映射到变换域的系数集合。 正交变换的特点： 不会丢失信息； 去除部分相关性； 能量（信息）集中大的系数能量多低频小的系数能量小高频Wavelet Exchange小波变换小波变换小波变换用于图像压缩的理由基于DCT (Discrete Cosine TransformDiscrete Cosine Trans

16、form) 的压缩标准JPEGMPEG-1,MPEG-2, H.264DCT 压缩的优点是简单、 便于硬件实现DCT 压缩的缺点是：图像是分块处理沿块的边界方向相关性被破坏，出现 “blocking artifacts”小波变换用于图像压缩的理由傅里叶变换傅立叶分析是一种将基于时间的信号变换为基于频率的信号的数学方法。傅立叶分析能够很好的刻画信号的频率特性，但不能提供信号在时频上的任何局部信息。为解决以上问题，在变换中增加了一个用于时间局部化的窗口函数，称之为“短时傅里叶变换”。然而由测不准原则可知，窗口的面积不可能任意小。测不准原则：如果w（t）是一个窗口函数，则有：因此短时傅立叶变换是一种

17、恒分辨率分析。21小波变换的发展20世纪 80年代后期发展起来的小波变换理论它是继傅里叶分析后信号处理与分析的强大工具无论是对古老的自然学科还是对新兴的高新技术应用学科都产生了强烈冲击。小波理论是应用数学的一个新领域。要深入理解小波理论需要用到比较多的数学知识。小波变换的发展哈尔(Alfred Haar)对在函数空间中寻找一个与傅里叶类似的基非常感兴趣。1909年他发现了小波，1910年被命名为Haar wavelets最早发现和使用了小波的名称。小波变换的发展20世纪70年代，当时在法国石油公司工作的年轻的地球物理学家Jean Jean MorletMorlet提出了小波变换CWT (con

18、tinuous wavelet transform)的概念。法国科学家Y.MeyerY.Meyer创造性地构造出具有一定衰减性的光滑函数，用缩放(dilations)与平移(translations)均为 2的j次幂的倍数构造了平方可积的实空间L2(R)的规范正交基，使小波得到真正的发展.S . M a l l a tS . M a l l a t 于 1 9 8 8 年 在 构 造 正 交 小 波 基 时 提 出 了 多 分 辨 率 分 析(multiresolution analysis)的概念, 从空间上形象地说明了小波的多分辨率的特性,提出了正交小波的构造方法和快速算法，叫做Malla

19、t算法。 MallatMallat算法地位相当于快速傅里叶变换在傅里叶分析中的地位。 小波变换的发展1988年 Inrid Daubechies 最先揭示了小波变换和滤波器组(filter banks)之间的内在关系。20世纪90年代中期，Sweldens提出了小波变换提升方案-第二代小波变换，用于JPEG2000小波在信号(如声音信号，图像信号等)处理中得到极其广泛的应用。小波变换的特点小波变换具有在不同尺度下保持时频分析窗口面积不变性质自动调节对信号分析的时宽和带宽被誉为信号分析的显微镜 连续小波变换 continuous wavelet transform小波（Wavelet (A sm

20、all wave, a ripple) 就是小的波形，所谓小，就是它具有衰减性，是存在于一个较小区域的波。 连续小波变换 定义a = scale variable缩放因子(尺度参数)b= time shift 时间平移（位移参数）在CWT中，缩放和平移是连续变化的定义X(t)是平方可积函数(t)被称为基本小波或母小波函数连续小波变换连续小波变换连续小波变换用较小a对信号做高频分析时，实际是用高频小波对信号进行细致观察用较大a对信号做低频分析时，实际是用低频小波对信号进行概貌观察小波变换与窗口时域分析时间幅值频域分析时间频率短时傅里叶变换时间幅值小波分析时间尺度小波变换的性质线性性：一个多分量信

21、号之和的小波变换等于各个分量的小波变换之和。平移不变性：如果f(t)的小波变换为Wf(a,b),那么f(t-)的小波变换为Wf(a,b-)尺度共变形：如果f(t)的小波变换为Wf(a,b),那么f(ct)的小波变换为 （1/c）Wf(ca,cb),其中c0自相似性：对应不同尺度参数a和不同平移参数b的连续小波变换之间是 自相似的。子带编码SBC (subband coding)把信号的频率分成几个子带，然后对每个子带分别进行编码，并根据每个子带的重要性分配不同的位数来表示数据20世纪70年代，子带编码开始用于语音编码20世纪80年代中期开始在图像编码中使用离散小波变换只有离散，小波变换才能应用离散的方式有很多离散小波变换的多分辨率分析Mallat创立了多分辨率分析理论在多分辨率分析基础上，Mallat提出了基于滤波器组实现信号的小波正变换和反变换算法。执行离散小波变换的有效方法离散小波变换把连续小波变换中尺度参数a和平移参数b的离散化公式分别取为：a= (a0)m ,b=nb0 (a0)m得：这样离散小波变换可定义为最