资源描述
图像压缩基本概念图像压缩模型信息论基础无损压缩有损压缩图像压缩标准视频压缩标准图像压缩基本概念1图像压缩基本概念概述数据冗余编码冗余像素间冗余心理视觉冗余图像保真度和质量图像压缩基本概念概述编码冗余像素间冗余2图像压缩的必要性为什么要压缩为什么要压缩?计算机图像处理中的数字图像其灰度多数用计算机图像处理中的数字图像其灰度多数用8bit来量化,一幅最简单的黑来量化,一幅最简单的黑白照片白照片,若按若按512512点阵取样点阵取样,表示这幅图像的二进制数据量表示这幅图像的二进制数据量 5125128=2048Kbit=2Mbit=256KB而医学图像处理和其他科研应用的图像的灰度量化可用到而医学图像处理和其他科研应用的图像的灰度量化可用到12bit以上,因而以上,因而所需数据量太大。所需数据量太大。10241024 12=12Mbit=1536KB=1.5MB遥感图像如遥感图像如SAR图像用图像用8bit量化,量化,100公里公里*100公里,公里,10m分辨率的图像的分辨率的图像的大小为大小为1000010000。这样一个地区的图像需。这样一个地区的图像需108B=100MB以上。这无疑对以上。这无疑对图象的图象的存储存储、处理处理、传送传送带来很大的困难。带来很大的困难。动态视频数据量非常大。动态视频数据量非常大。数字高清:数字高清:1080i/50Hz1080i/50Hz1920*1080*24*50=2 488 320 000=2.5Gb/s1920*1080*24*50=2 488 320 000=2.5Gb/s视频信号的传输率约为视频信号的传输率约为2.5GB/s2.5GB/s这样大的数据量不仅超出了计算机的存储和处理能力,更是当前通信信道的传这样大的数据量不仅超出了计算机的存储和处理能力,更是当前通信信道的传输速率所不及的。因此,为了存储、处理和传输这些数据,必须进行压缩。输速率所不及的。因此,为了存储、处理和传输这些数据,必须进行压缩。图像压缩的必要性为什么要压缩?动态视频数据量非常大。3传输 存储压缩解压介质压缩解压信道主要目的主要目的传输压缩解压介质压缩解压信道主要目的4图像压缩图像压缩的方法消除冗余数据,从数学角度看,将原始图像转化为从统计角度统计角度看尽可能不相关的数据集一般分为两类:无损压缩无损压缩:在压缩和解压缩过程中没有信息损失有损压缩有损压缩:能取得较高的压缩率,但压缩后不能通过解压缩恢复原状其它:如根据需要,即可进行无损,也可进行有损压缩的技术;准无损技术图像压缩图像压缩的方法 消除冗余数据,从数学角度看5图像压缩图像压缩的理论基础信息论图像处理的概念和技术压缩方法预测编码方法(对应空域方法)变换编码方法(对应频域方法)图像压缩信息论压缩方法6图像压缩的可能性8.1 数据冗余的概念数据是用来表示信息的。如果不同的方法为表表表表示等量的信息使用了不同的数据量示等量的信息使用了不同的数据量示等量的信息使用了不同的数据量示等量的信息使用了不同的数据量,那么使用较多数据量的方法中,有些数据必然是代表了无用的信息,或者是重复地表示了其它数据已表示的信息,这就是数据冗余的概念。图像压缩的可能性8.1数据冗余的概念数据是用来表示信息7图像压缩的可能性相对数据冗余的定义(续)如果n1和n2代表两个表示相同信息的数据集合中所携载信息单元的数量,则n1表示的数据集合的相对数据冗余相对数据冗余相对数据冗余相对数据冗余R RD D定义为:R D 1 1C RCR称为压缩率压缩率压缩率压缩率,定义为C R n1n 2图像压缩的可能性RD11CR称为压缩率8图像压缩的可能性相对数据冗余和压缩率的一些特例n1相对于n2n1 =n2CR1RD0对应的情况第1种表达相对第2种表达不含冗余数据n1 n2 1 第1种数据集合包含相当多的冗余数据n1 n2 0 第2种数据集合包含相当多的冗余数据图像压缩的可能性n1相对于n2CRRD对应的情况余数据9图像压缩的可能性三种基本的数据冗余8.1.1编码冗余8.1.2像素间冗余8.1.3心理视觉冗余如果能减少或消除上述三种冗余的1种或多种冗余,就能取得数据压缩的效果图像压缩的可能性8.1.1编码冗余8.1.3心10图像压缩什么是编码冗余?如果一个图像的灰度级编码灰度级编码灰度级编码灰度级编码,使用了多于实际需要的编码符号,就称该图像包含了编码冗余黑白二值图像编码如果用8位表示该图像的像素,我们就说该图像存在编码冗余,因为该图像的像素只有两个灰度,用一位即可表示。图像压缩什么是编码冗余?如果一个图像的灰度级编码,使用11nk,8.1.1 编码冗余图像直方图的定义pr rk k 0,1 2,.,L 1nnk是第k个灰度级在图像中出现的次数,n是图像中的像素总数,L是灰度级数。如果用于表示每个rk值的比特数为l(rk),则表达每个像素所需的平均比特数每个像素所需的平均比特数为:Lavg L 1 l rk p r rk k 0表示不同的灰度级值的平均码字长度.对MN的图像进行编码所需的比特数为MNL avg参考page 328的例8.1nk,8.1.1编码冗余LavgL128.1.2 像素间冗余什么是像素间冗余?反映图像中像素之间的相互关系因为任何给定像素的值可以根据与这个像素相邻的像素进行预测,所以单个像素携带的信息相对较少对于一幅图像,很多单个像素对视觉的贡献是冗余的。它的值可以通过与它相邻的像素值通过与它相邻的像素值通过与它相邻的像素值通过与它相邻的像素值为基础进行预测为基础进行预测为基础进行预测为基础进行预测例:原图像数据:234 223 231 238 235压缩后数据:234 -1187-38.1.2像素间冗余压缩后数据:234-1113 像素间冗余像素间冗余有直方图特征可知,可以用有直方图特征可知,可以用变长编码减少编码冗余。但变长编码减少编码冗余。但编码处理不会改变图像像素编码处理不会改变图像像素之间的相关性级别。也就是之间的相关性级别。也就是说用于表示每幅图像的灰度说用于表示每幅图像的灰度级的编码与像素之间的相关级的编码与像素之间的相关性无关,这些性无关,这些相关相关来自于图来自于图像中对象之间的像中对象之间的结构结构或或几何几何关系关系。相关性反映了图像中像素间相关性反映了图像中像素间的直接关系。的直接关系。a)、b)两幅图像c)、d)灰度直方图e)、f)沿着某一条线计算的自相关函数像素间冗余有直方图特征可知,可以用变长编码减少编码冗余。14第八章图像压缩课件158.1.3 心理视觉冗余什么是心理视觉冗余?人眼感觉到的图像区域亮度不仅取决于该区域的反射光,例如根据马赫带效应,在灰度值为常数的区域也能感觉到灰度值的变化这是由于眼睛对眼睛对眼睛对眼睛对所有视觉信息感受的灵敏度视觉信息感受的灵敏度视觉信息感受的灵敏度视觉信息感受的灵敏度不同不同不同不同。在正常视觉处理过程中各种信息的相对重要程度不同有些信息在通常的视觉过程中与另外一些信息相比并不那么重要不那么重要不那么重要不那么重要,这些信息被认为是心理信息被认为是心理信息被认为是心理信息被认为是心理视觉冗余的视觉冗余的视觉冗余的视觉冗余的,去除这些信息并不会明显降低图像质量8.1.3心理视觉冗余什么是心理视觉冗余?人眼感16心理视觉冗余什么是心理视觉冗余?(续)由于消除心理视觉冗余数据会导致一定量信息的丢失,所以这一过程通常称为量化量化量化量化心理视觉冗余压缩是不可恢复的,它表示从一个范围很宽的输入集合到一个有限个输出值的集合的映射,这种映射是不可逆的,这种映射是不可逆的,这种映射是不可逆的,这种映射是不可逆的,所以结果导致了数据的有损压缩。有损压缩。有损压缩。有损压缩。33K15K心理视觉冗余33K15K17心理视觉冗余心理视觉冗余a)256灰度级原图像b)量化为16级后图像c)利用人类视觉特性进行量化后图像原来原来8bit/像素像素压缩后压缩后4bit/像素像素压缩率为压缩率为2:1存在假轮廓效应存在假轮廓效应心理视觉冗余a)256灰度级原图像原来8bit/像素18改进的灰度级(改进的灰度级(IGS)量化方法)量化方法IGS量化过程:先由当前的量化过程:先由当前的8位灰度级值位灰度级值(GrayLevel)与前一个与前一个sum(初始值为零)的低(初始值为零)的低4位相加。如果当前值的高位相加。如果当前值的高4位是位是11112,则用则用00002与其相加,保持其不变。将得到的和的高与其相加,保持其不变。将得到的和的高4位的值作为位的值作为编码像素值。编码像素值。IGS利用眼睛对边缘固有的敏感性,通过一个伪随机数加到每利用眼睛对边缘固有的敏感性,通过一个伪随机数加到每个像素上将这些边缘拆散。这个伪随机数是在对结果进行量化个像素上将这些边缘拆散。这个伪随机数是在对结果进行量化之前,根据表示相邻像素灰度级的原编码的低位生成的。由于之前,根据表示相邻像素灰度级的原编码的低位生成的。由于低位完全是随机的,所以这样做等于增加了通常与伪轮廓相关低位完全是随机的,所以这样做等于增加了通常与伪轮廓相关的人工边缘随机性的灰度级。的人工边缘随机性的灰度级。改进的灰度级(IGS)量化方法IGS量化过程:先由当前的8位198.1.4 保真度准则保真度准则图像压缩可能会导致信息损失,如去除心理视觉冗余数据需要评价信息损失的测度评价信息损失的测度评价信息损失的测度评价信息损失的测度以描述解码图像相对于原始图像的偏离程度,这些测度称为保真保真保真保真度准则度准则度准则度准则常用保真度准则分为两大类:客观保真度准则主观保真度准则8.1.4保真度准则保真度准则图像压缩可能会导20保真度准则客观保真度准则当所损失的信息量可以用编码输入图像与编码输出图像的函数表示时,它就是基于客观保真度准则的常用的两种客观保真度准则均方根误差均方信噪比保真度准则均方根误差21客观保真度准则输入图和输出图之间的均方根误差 令 f x,y 代表输入图,f x,y 代表对 f x,y 先压缩后解压缩后得到的 f x,y 的近似,则 f x,y 和f x,y 之间的误差定义为ex,y f x,y f x,y 如两幅图像尺寸均为MN,则它们的总误差为M 1 N 1 f x,y f x,y x 0 y 0客观保真度准则输入图和输出图之间的均方根误差令22客观保真度准则客观保真度准则输入图和输出图之间的均方根误差这样 f x,y和 f x,y 之间的均方根误差均方根误差均方根误差均方根误差为输出图的均方信噪比 如果将 f x,y 看作原始图 f x,y 和噪声信号 ex,y的和,那么输出图的均方信噪比均方信噪比均方信噪比均方信噪比 SNR ms为均方根信噪比均方根信噪比均方根信噪比均方根信噪比 SNR rms为客观保真度准则均方根信噪比SNRrms为2346主观保真度准则主观保真度准则评分1235评价优秀良好可用刚可看差不能用说明图像质量非常好,如同人想象出的最好质量图像质量高,观看舒服,有干扰但不影响观看图像质量可接受,有干扰但不太影响观看图像质量差,干扰有些妨碍观看,希望改进图像质量很差,妨碍观看的干扰始终存在,几乎无法观看图像质量极差,不能使用46主观保真度准则评分 评价说明248.2 图像压缩模型f x,y信源编码信道编码信道信道解码信源解码f x,y编码器解码器一个图像压缩系统包括两个不同的一个图像压缩系统包括两个不同的模块:模块:编码器编码器编码器编码器和和解码器解码器解码器解码器一般来讲如果输出图像是输入的准一般来讲如果输出图像是输入的准确复制,系统就是确复制,系统就是无误差无误差的或具有的或具有信息保持编码的系统信息保持编码的系统。编码器由一个消除输入冗余的编码器由一个消除输入冗余的信源编码器信源编码器和一个用于增强信和一个用于增强信源编码器输出的抗噪能力的源编码器输出的抗噪能力的信道编码器信道编码器构成。构成。如果编码器和解码器之间的信道是无噪的,则信道编解码器如果编码器和解码器之间的信道是无噪的,则信道编解码器可以省去。可以省去。8.2图像压缩模型fx,y信源信道信道信道信源25图像压缩模型信源编码器f x,y转换器量化器符号编码器信道信源编码器信源编码器:减少或消除输入图像中的编码冗余、像素间冗余及心理视觉冗余转换器:减少像素间冗余量化器:减少心理视觉冗余,该步操作是不可逆的该步操作是不可逆的该步操作是不可逆的该步操作是不可逆的符号编码器:减少编码冗余并不是每个图像压缩系统都必须包含这3种操作,如进行无误差压缩时,必须去掉量化器图像压缩模型fx,y转换器量化器符号编码26图像压缩模型信源解码器信道符号解码器反向转换器f x,y信源解码器符号解码器:进行符号编码的逆操作反向转换器:进行转换器的逆操作为什么没有反向量化器?图像压缩模型信道符号解码器反向转换器fx,y27图像压缩模型8.2.2信道编码器和信道解码器在有噪声的或易产生误差时,信道编码器和信道解码器对整个编解码过程非常重要信道编码器和解码器通过向信源编码数据中插入预制插入预制插入预制插入预制的冗余数据的冗余数据的冗余数据的冗余数据来减少信道噪声的影响。由于信源编码器几乎不包含冗余,所以如果没有附加这种预制的冗余,它对噪声传送会有很高的敏感性。因此,信道编码是解决可靠性问题解决可靠性问题解决可靠性问题解决可靠性问题,尽量使处理过的信号在传输过程中不出错或少出错,即使出错也要有能力尽量纠正错误。信道编码技术:比如汉明(Hamming)编码。在编了码的码字后面增加足够的比特位以保证各个正确的码字之间至少有一定数量的比特位不相同图像压缩模型8.2.2信道编码器和信道解码器在有噪声28图像压缩模型8.3 信息论基础显示一幅图像需要多大的数据量?有没有描述一幅图像且没有信息丢失的最小数据量?信息测量对一个随机事件E,如果它的出现概率是P(E),那么它包含的信息:I E log1PE log PE I(E)称为E的自信息自信息自信息自信息。如果P(E)=1(即事件总发生),那么I(E)=0图像压缩模型信息测量IElog129图像压缩模型8.3.2 信息信道信 源信 道信 宿信道是连接信源和用户的物理媒介。它可以是电话线、无线传播、导线或internet图像压缩模型8.3.2信息信道信源信道信宿信30JT信息论基础信源A=a1,a2,aJ称为信源字母表信源字母表信源字母表信源字母表信源产生符号aj的事件概率是P(aj),且一个J1向量 P a j 1j 1z P a1 ,P a2 ,.,P aJ 用于表示所有信源符号的概率集合有限总体集合(A,z)完全描述了信源信源JT信息论基础信源一个J1向量Paj31考虑无记忆信源考虑无记忆信源考虑无记忆信源考虑无记忆信源Z Z,某个信源符号某个信源符号某个信源符号某个信源符号a a j j,如果它出现的概率是如果它出现的概率是如果它出现的概率是如果它出现的概率是p p(a a j j )信源熵信源熵信源熵信源熵H(z)H(z)a a的自信息量的自信息量的自信息量的自信息量 信息理论基础信息理论基础直观地理解自信息量的概念直观地理解自信息量的概念:一个概率小的符号出现将带来更大的信息量一个概率小的符号出现将带来更大的信息量.每个符号的平均自信息量每个符号的平均自信息量单位单位:比特比特/符号符号一般来讲,事件一般来讲,事件E的自信息量与的自信息量与E的概率的关系是反向的。如果的概率的关系是反向的。如果P(E)=1,则,则I(E)=0。因为:。因为:(a)越不可能出现的字符,它的出现对于消息的信息量的贡献越大。越不可能出现的字符,它的出现对于消息的信息量的贡献越大。(b)整个消息的信息量是构成它的那些字符中对于信息量有贡献的那部整个消息的信息量是构成它的那些字符中对于信息量有贡献的那部分之和。分之和。考虑无记忆信源Z,某个信源符号aj,如果它出现的概率是p(32JJ信息论基础信源(续)如果产生k个信源符号,则大数定律保证对于一个充分大的k,符号aj将平均被输出k P(aj)次。因此,输出得到的平均自信息是 k P aj logP aj j 1每个信源输出的平均信息每个信源输出的平均信息,也称为信源的熵信源的熵信源的熵信源的熵为H z P a j log P a j j 1如果信源符号的出现是等可能性的,则上述熵被最如果信源符号的出现是等可能性的,则上述熵被最大化,此时信源提供最大信息量大化,此时信源提供最大信息量JJ信息论基础如果产生k个信源符号,则大数定律保证对33Jk信息论基础信道输出B=b1,b2,bk称为信道字母表信道字母表信道字母表信道字母表提交给用户的字符bk的概率是P(bk)有限集合(B,v)(B,v)完整描述了信道信道信道信道输出和用户收到的信息,v Pb1,Pb2,.,PbK 给定信道输出概率P(bK)和信源符号概率 P(aJ),它们由下式相联系P bk P bj 1|a j P a j Jk信息论基础信道输出PbkPb34信息论基础信道输出(续)将上式中的条件概率放入一个KJ的正向信道传递矩阵Q,其元素qkj=P(bk|aj)为条件概率则输出符号集的概率分布由下式计算v Qz信息论基础信道输出(续)将上式中的条件概率放入一个K35P a ,b JKjkP a P b P b|a P a JKkjjP a P b JKki信息论基础z和v的互信息的另外一种表达I z,v P a j,bk logj 1 k 1 j k P bk|a j P a j logj 1 k 1 j k P a j qj 1 k 1kjlogq kjP bk J Kj 1 k 1P a j q kj logJ P bi 1q kjk|a i P a i J Kj 1 k 1P a j q kj logq kjJ P a i qi 1Pa,bJKjkPaPb39信息论基础基本编码定理无噪声编码定理噪声编码定理(自学)信源编码定理(自学)信息论基础基本编码定理无噪声编码定理噪声编码定理(自41无噪声编码定理无噪声编码定理香香香香农农农农第第第第一一一一定定定定理理理理:当当当当信信信信道道道道和和和和通通通通信信信信系系系系统统统统中中中中不不不不存存存存在在在在噪噪噪噪声声声声的的的的时时时时候候候候,通通通通信信信信系系系系统统统统的的的的主主主主要要要要功功功功能能能能是是是是用用用用尽尽尽尽可可可可能能能能简简简简洁洁洁洁的的的的方方方方法法法法表表表表示示示示信信信信源源源源,在在在在这这这这种种种种情情情情况况况况下下下下无无无无噪噪噪噪声声声声编编编编码码码码定理定义了可以达到的每个信源符号的最小定理定义了可以达到的每个信源符号的最小定理定义了可以达到的每个信源符号的最小定理定义了可以达到的每个信源符号的最小平均码字长度平均码字长度。这一定理说明了通过对无限扩充的信源进行编码可以令这一定理说明了通过对无限扩充的信源进行编码可以令这一定理说明了通过对无限扩充的信源进行编码可以令这一定理说明了通过对无限扩充的信源进行编码可以令无限接近无限接近无限接近无限接近H(z)H(z)H(z)H(z)。任何编码策略的任何编码策略的任何编码策略的任何编码策略的编码效率编码效率编码效率编码效率可以定义为:可以定义为:可以定义为:可以定义为:表示对应于非扩充信源的第表示对应于非扩充信源的第表示对应于非扩充信源的第表示对应于非扩充信源的第n n n n次扩充的编码平均码长次扩充的编码平均码长次扩充的编码平均码长次扩充的编码平均码长信源输出信源输出ai是用一个码字表示的,码字的长度为不小于其自信息量的最小整数是用一个码字表示的,码字的长度为不小于其自信息量的最小整数无噪声编码定理香农第一定理:当信道和通信系统中不存在噪声的时42图像压缩编码的分类图像压缩编码的分类图像压缩编码图像压缩编码有损压缩有损压缩无损压缩无损压缩哈夫曼编码哈夫曼编码算术编码算术编码LZW编码编码位平面编码位平面编码行程编码行程编码无损预测编码无损预测编码有损预测编码有损预测编码变换编码变换编码K.L变换变换Haar变换变换Walsh.Hadamard变换变换离散余弦变换离散余弦变换离散傅立叶变换离散傅立叶变换斜变换斜变换小波变换小波变换消除编码冗余消除编码冗余消除象素间冗余消除象素间冗余图像压缩编码的分类图像压缩编码有损压缩无损压缩哈夫曼编码有43信息论基础8.4 无损压缩变长编码霍夫曼(Huffman)编码其它变长编码算术编码LZW编码位平面编码无损预测编码信息论基础变长编码算术编码LZW编码44无误差压缩无误差压缩的必要性在医疗或商业文件的归档,有损压缩因为法律原因而被禁止卫星成像的收集,考虑数据使用和所花费用,不希望有任何数据损失X光拍片,信息的丢失会导致诊断的正确性无损压缩的压缩率一般为无损压缩的压缩率一般为2-10无误差压缩技术减少像素间冗余减少像素间冗余:建立一种可替代的图像表达方式建立一种可替代的图像表达方式减少编码冗余减少编码冗余:对这种表达方式进行编码对这种表达方式进行编码无误差压缩无损压缩的压缩率一般为2-10无误458.4.1 变长编码变长编码无无误误差差图图像像压压缩缩的的最最简简单单方方法法就就是是减减少少仅仅有有的的编编码码冗冗余余。编编码码冗冗余余通通常常存存在在于于表表示示图图像像灰灰度度级级的的自自然然二二进进制制编编码码过过程程中中。它它可可以以对对灰灰度度级级进进行行编编码码,使使表表示示一一个个像像素素的的码码字字的的平平均均比比特特数数最最小小来来消消除除编编码码冗冗余余。这这样样做做需需要要变变长长编编码码结结构构,通通常常将最短的码字赋予出现概率最大的灰度级。将最短的码字赋予出现概率最大的灰度级。8.4.1变长编码无误差图像压缩的最简单方法就是减少仅461.2.无误差压缩变长编码减少编码冗余变长编码,即把最短的码字赋予出现概率最大的灰度级霍夫曼编码将需要考虑的符号概率排序,并将最低概率的符号联结为一个单一符号对每个化简后的信源进行编码,从最小的信源开始,一直编码到原始的信源1.2.无误差压缩变长编码47霍夫曼编码霍夫曼编码(一)(一)霍夫曼编码信源化简步骤:霍夫曼编码信源化简步骤:设信源设信源有有个符号个符号(消息消息),1.把信源中的消息按概率从大到小顺序排列,把信源中的消息按概率从大到小顺序排列,2.把最后两个出现概率最小的消息合并成一个消息把最后两个出现概率最小的消息合并成一个消息,从而从而使信源的消息数减少,并同时再按信源符号(消息)出使信源的消息数减少,并同时再按信源符号(消息)出现的概率从大到小排列;现的概率从大到小排列;3.重复上述重复上述2步骤步骤,直到信源最后为直到信源最后为为止;为止;4.将被合并的消息分别赋予将被合并的消息分别赋予1和和0,并对最后的两个消息也,并对最后的两个消息也相应的赋予相应的赋予1和和0;通过上述步骤就可构成最优变长码通过上述步骤就可构成最优变长码(HuffmanCodes)。霍夫曼编码(一)霍夫曼编码信源化简步骤:48霍夫曼编码霍夫曼编码霍夫曼编码信源化简霍夫曼编码信源化简霍夫曼编码霍夫曼编码信源化简49霍夫曼编码霍夫曼编码(二)霍夫曼化简后的信源编码(二)霍夫曼化简后的信源编码编码的平均长度:编码的平均长度:其其 信信 源源 熵熵 为为2.14bit/符号。符号。编码的效率:编码的效率:霍夫曼编码(二)霍夫曼化简后的信源编码编码的平均长度:其信源50霍夫曼编码霍夫曼解码解码通过查询表查询表查询表查询表的方式完成例:编码串010100111100 a3 a1 a2a2a6对编码串对编码串010100111100解码,其解码唯一:解码,其解码唯一:a3a1a2a2a6霍夫曼编码霍夫曼解码解码通过查询表的方式完成a351霍夫曼编码其它接近最佳的变长编码:为什么需要?当对大量符号进行编码,构造霍夫曼编码比较复杂对J个信源符号,需要进行J-2次信源化简和J-2次编码分配对256个灰度级图像,需要256-2=254次信源化简和254次编码分配考虑牺牲编码效率以减少编码构造的复杂性霍夫曼编码其它接近最佳的变长编码:为什么需要?当对52几种变长编码几种变长编码截取霍夫曼编码霍夫曼编码二进制编码B2编码二值移位编码霍夫曼移位编码几种变长编码截取霍夫曼编码霍夫曼编码二进制编码B2编码二值移53算术编码算术编码算算术术编编码码生生成成的的是是非非块块码码,在在信信源源符符号号和和码码字字之之间间不不存存在在一一一一对对应应的的关关系系。算算术术编编码码是是给给整整个个符符号号序序列列分分配配一一个个单单一一的的算算术术码码字字,这这个个码码字字本本身身定定义义了了一一个个介介于于0和和1之之间间的的实实数数间间隔隔。当当消消息息中中的的符符号号数数目目增增加加时时,用用于于描描述述消消息息的的间间隔隔变变的的更更小小,而而表表示示间间隔隔所所需需要要的的信信息息单单元元的的数数目目就就变变得得更多了。更多了。消消息息的的每每个个符符号号根根据据符符号号出出现现的的概概率率减减小小间间隔隔的的大大小小,这这种种技技术术不不象象霍霍夫夫曼曼方方法法那那样样要要求求每每次次对对一一个个符符号号进进行行编编码码,所所以以理理论论上上达达到到了了无无噪噪声声编编码准则确定的界限。码准则确定的界限。算术编码算术编码生成的是非块码,在信源符号和码字之间不存在一54算术编码算术编码0.080.20.040.04=0+(0.2-0)/510.08=0+(0.2-0)/520.056=0.04+(0.08-0.04)/520.072=0.04+(0.08-0.04)/54=0.04+0.032一个五个符号的序列一个五个符号的序列a1,a2,a3,a3,a4来自一个四符号信源。来自一个四符号信源。经过算术编码后,区间被确定为经过算术编码后,区间被确定为0.06752,0.0688),这个区间的这个区间的任何数字都可以用来表示这个消任何数字都可以用来表示这个消息(比如息(比如0.068)。算术编码0.20.040.04=0+(0.2-0)/51558.4.2 LZW编码编码LZW编码:消除像素间冗余像素间冗余的无误差编码方法是由Lemple和Ziv最早提出,然后由Welch充实的有专利保护的LZW算法.Lempel-Ziv-Welch(LZW)编码编码对信源符号的对信源符号的可变长度序列可变长度序列可变长度序列可变长度序列分配固定长度码字,不需要分配固定长度码字,不需要了解有关被编码符号的出现概率的知识。了解有关被编码符号的出现概率的知识。LZWLZW编码的原理:编码的原理:在在编编码码处处理理的的开开始始阶阶段段,先先构构造造一一个个对对信信源源符符号号进进行行编编码码的的编编码码本本(字字典典)。对对于于8 8位位单单色色图图像像,字字典典中中前前256256个个字字被被分分配配给给灰灰度度值值0-2550-255。当当编编码码器器顺顺序序地地分分析析图图像像像像素素的的时时候候,字字典典中中没没有有包包括括的灰度级序列由算法决定其出现的位置。的灰度级序列由算法决定其出现的位置。使用使用LZW的文件格式包括的文件格式包括GIF,TIFF和和PDF等等。8.4.2LZW编码LZW编码:消除像素间冗余的无误56字典位置index条目0125525651101255LZWLZWLZWLZW编码基本思想是这样的编码基本思想是这样的编码基本思想是这样的编码基本思想是这样的:以以8 8位(位(256256个灰度级)图像为例个灰度级)图像为例.1.1.准备一个数据字典准备一个数据字典(可以看做一个数组可以看做一个数组).).数组的前数组的前256256项初始化为项初始化为0,1,2,.,255,0,1,2,.,255,后面的项为空白后面的项为空白.为方便起见为方便起见,我我们管字典中的每一项叫们管字典中的每一项叫“条目条目”.”.2.2.开始对图像文件编码开始对图像文件编码,图像文件从左向右、从上到下扫描图像文件从左向右、从上到下扫描,把扫描得到的灰把扫描得到的灰度级数据与字典中的条目进行比较度级数据与字典中的条目进行比较.如果相同如果相同,就把这个就把这个 条目条目 的的index(index(在在数组中的位置数组中的位置)作为码字输出作为码字输出.如果在字典中找不到与之匹配的条目如果在字典中找不到与之匹配的条目,则在字典中创建一个新的条目则在字典中创建一个新的条目(从从第第256256项开始项开始).).一个一个512字节的字典字节的字典一个一个44、8位图像位图像3546353946784639679078126353334126字典位置index条目00LZW编码基本思想是这样57示例示例原始码流原始码流354667354678903335467834开始编码开始编码:因为第一个数字是因为第一个数字是35,我们必然可以从字典中找到与之匹配的条目我们必然可以从字典中找到与之匹配的条目(也就是第也就是第35个个),但我们不急着用第但我们不急着用第35个条目与之匹配个条目与之匹配,先看看第二个数字是先看看第二个数字是46,希望在字典中希望在字典中能找到一个更长的模式能找到一个更长的模式“3546”这样的条目这样的条目,与之匹配与之匹配,但不幸的是我们没有找到但不幸的是我们没有找到,所以只对第一个数字所以只对第一个数字35编码编码,结果输出结果输出35;同时把同时把“3546”加入字典的第加入字典的第256项项,希望以后能碰到它希望以后能碰到它.同理同理,对对46编码编码,输出输出46,同时把同时把“4667”加入字典的第加入字典的第257项项.同理同理,对对67编码编码,输出输出67,同时把同时把“6735”加入字典的第加入字典的第258项项.这时注意了这时注意了:对对35编码编码,是不是现在还输出是不是现在还输出35呢呢?当然不是当然不是,我们发现我们发现35后面跟后面跟着着46,扫描字典扫描字典,可以发现第可以发现第256个模式与之匹配个模式与之匹配,输出输出256.同时同时,将模式将模式“354678“加入到加入到字典的第字典的第259项项.同理同理,接下来输出接下来输出78,90,33,259,34.所以输出的码流为所以输出的码流为35466725678903325934.对上面的过程归纳一下对上面的过程归纳一下:在编码的过程中生成字典在编码的过程中生成字典;一边从字典中选择长一边从字典中选择长度尽量长的度尽量长的 模式模式 与原始码流匹配与原始码流匹配.示例原始码流3558LZW编码例子编码例子Appear39-39126-12639-3939-39-126126-3939-126LZW编码例子Appear39-39126-12639-39598.4.3位平面编码位平面编码:消除像素间冗余消除像素间冗余将一幅图像分解为一系列二值图像并通过二值图像压缩方法对每幅二值图像进行压缩位平面编码过程可以分成两步:位平面编码过程可以分成两步:一是位平面分解一是位平面分解二是二值图像压缩二是二值图像压缩二值图像位平面灰度编码位平面位平面分解的两种方法8.4.3位平面编码位平面编码:消除像素间冗余将一60 位平面分解位平面分解二值图像位平面二值图像位平面一幅一幅m比特的灰度图像具有的灰度级表示如下比特的灰度图像具有的灰度级表示如下am 1 2 m 1 am 2 2 m 2 .a1 21 a0 2 0零级位平面是通过收集每个像素的零级位平面是通过收集每个像素的a0位生位生成,第成,第(m-1)级位平面包含级位平面包含am-1位位缺点:图像在灰度级上稍有变化就会对位平缺点:图像在灰度级上稍有变化就会对位平面的复杂性产生显著影响,如亮度面的复杂性产生显著影响,如亮度127(01111111)和亮度和亮度128(10000000)的转换的转换位平面分解二值图像位平面一幅m比特的灰度图像具有的灰61 位平面分解位平面分解灰度编码位平面灰度编码位平面图像的灰度编码根据下列方法得到:图像的灰度编码根据下列方法得到:g m 1 am 1g i ai ai 10 i m-2避免二值图像位平面的问题,避免二值图像位平面的问题,连续码字只在连续码字只在1位位置上不同位位置上不同,如亮度如亮度127(01000000)和亮度和亮度128(11000000)的转换的转换位平面分解giaiai1062位平面分界例8比特单色图像二值图像位平面分界例8比特单色图像二值图像63位平面分解例二值图像位平面灰度编码位平面采用不同分层编码方采用不同分层编码方法处理的图像。法处理的图像。左侧是第一种方法分左侧是第一种方法分层编码的高层编码的高4位位图位位图右侧是第二种方法编右侧是第二种方法编码的高码的高4位位图位位图高阶平面比低阶部分高阶平面比低阶部分要简单,高比特位平要简单,高比特位平面包含大块的均匀区面包含大块的均匀区域,图像细节较少。域,图像细节较少。灰度编码位平面比二灰度编码位平面比二值位平面复杂性较少值位平面复杂性较少位平面分解例二灰采用不同分层编码方法处理的图像。64位平面分解例二值图像位平面灰度编码位平面位平面分解例二灰65二值图编码二值图编码常数值区域编码常数值区域编码CAC一维行程编码一维行程编码二维行程编码二维行程编码常数块编码常数块编码用专门的码字表达全是用专门的码字表达全是0或或1的连通区域的连通区域将图像分成全黑,全白或混合的pq尺寸的块。出现频率最高的类赋予1位码字0,其它2类分别赋予2位码字10和11压缩二值图或位平面的一种简单有效的方法是使用指定的码压缩二值图或位平面的一种简单有效的方法是使用指定的码字识别大片连续的字识别大片连续的1 1或或0 0区域。这样的方法称为区域。这样的方法称为区域编码区域编码(CAC)(CAC)二值图编码常数值区域编码CAC常数块编码用专门的码字表66常数块编码(续)常数块编码(续)当需压缩的图像主要由白色部分组成时(如文档),可将白色区域编为0,其它块用1接上该块的位模式编码WBS编码编码另一种办法:将二值图或位平面迭代地分解成尺寸越来越小的子块。如果子块不是全白,继续分解,直至某个事先确定的子块尺寸。如果最后子块全白,就编为0,反之编为1加上该块的位模式由于原来需用pq比特表示的常数块现在只用1位或2位表示,这样就达到了压缩的目的赋予混合块的码只是作为前缀,后面还需跟上该块的用pq位表示的模式常数块编码(续)当需压缩的图像主要由白色部分组成时(如67WBS编编码码(WhiteBlockSkipping):大大多多数数二二值值图图像像中中的的黑黑象象素素只只占占图图像像象象数数总总数数很很少少的的一一部部分分。因因此此若若能能跳跳过过白白色色区区域域,对对黑黑色色像像素素编编码码这这样样表表示示这这些些图图像像的的比比特特数数将将减减少,每个像素平均比特数也就可以减少少,每个像素平均比特数也就可以减少 1)一维一维WBS编码编码 将将图图像像的的每每条条扫扫描描线线分分成成若若干干段段,每每段段有有N个个像像素素。对对全全部部是是白白色色的的像像素素用用lbit“0”表表示示。对对于于至至少少有有一一个个黑黑色色像像素素的的像像素素段段采采用用N十十1个个比比特特编编码码即即第第一一个个比比特特人人为为地地规规定定为为1其其余余的的N比比特特采采用用直直接接编编码码(白色为白色为“0”黑色为黑色为“1”码字码字)。跳过白色块编码跳过白色块编码WBS编码(WhiteBlockSkipping):大多68 一维一维WBS编码平均码字长度为编码平均码字长度为 PN:段段长长为为N的的全全全全白白白白像像像像素素素素段段段段出出出出现现现现的的的的概概概概率率率率。b41.25-P4。全全白白概概率率必须大于必须大于14才可能获得压缩效果。才可能获得压缩效果。段段长长N不不同同,全全白白概概率率也也不不同同。为为了了获获得得最最小小的的平平均均码码字字长长度度,对对给给定定的的一一幅幅二二值值图图像像应应有有一一个个最最佳佳N值值,不不同同图像的最佳段长图像的最佳段长N值不同。值不同。分成五段:段长N400000010000001000000编码0100100101000一维WBS编码平均码字长度为分成五段:段长N4000692)二二维维WBS编码编码 一一维维WBS编码编码可以方便地推广到二可以方便地推广到二维维。一一维维的像素段的像素段 二二维维中像素中像素块块 假假设设像像素素块块尺尺寸寸为为MN,全全部部为为白白色色的的像像素素块块用用“0”表表示示,非非全全白白像像素素块块用用(MN+1)个个比比特特码码表示。其中第一个比特表示。其中第一个比特为为“1”。其余。其余MN个比特采用直接个比特采用直接编码编码。0000000010000101000000000100100010101000最终获得的编码:最终获得的编码:01001000101010002)二维WBS编码00000101000001001101070 位平面编码位平面编码一维行程编码一维行程编码在一个逐行存储的图象中,在一个逐行存储的图象中,具有相同灰度值的一些象素组具有相同灰度值的一些象素组成的序列称为成的序列称为一个行程一个行程一个行程一个行程。在编码时,对于每个行程只存储一。在编码时,对于每个行程只存储一个灰度值的码,再紧跟着存储这个行程的长度。这种按照行个灰度值的码,再紧跟着存储这个行程的长度。这种按照行程进行的编码被称为程进行的编码被称为行程编码行程编码行程编码行程编码(Run Length EncodingRun Length Encoding)。)。是传真编码的标准压缩方法是传真编码的标准压缩方法对从左到右扫描一行时所遇到的对从左到右扫描一行时所遇到的1 1或或0 0的连接组,使用的连接组,使用这些连接组的长度进行编码这些连接组的长度进行编码决定行程长度值的常用方法:决定行程长度值的常用方法:指定每一行第一次行程的值指定每一行第一次行程的值假设每一行从白色行程开始,这次行程的长度可假设每一行从白色行程开始,这次行程的长度可能为能为0 0位平面编码一维行程编码在一个逐行存储的图象中,71一维行程编码一维行程编码见见p332图图8.3尽管行程长度编码本尽管行程长度编码本身是一种压缩图像的身是一种压缩图像的有效方法,但其它的有效方法,但其它的压缩方法通常可以通压缩方法通常可以通过对行程长度本身进过对行程长度本身进行变长编码实现。这行变长编码实现。这些变长编码是根据他些变长编码是根据他们自身的统计数据特们自身的统计数据特殊制定的。殊制定的。一维行程编码见p332图8.3尽管行程长度编码本身是一种压缩72分析:分析:对于有大面积色块的图像,压缩效果很好对于有大面积色块的图像,压缩效果很好对于纷杂的图像,压缩效果不好,最坏情况下,会加倍图像对于纷杂的图像,压缩效果不好,最坏情况下,会加倍图像行程编码行程编码分析:行程编码738.4.4无损预测编码预测编码的基本思想通过仅提取每个像素中的新信息并对新信息编码对新信息编码对新信息编码对新信息编码来消除像素间的冗余消除像素间的冗余一个像素的新信息定义为新信息定义为新信息定义为新信息定义为:该像素的当前值与预测值的差正是由于像素间有相关性,所以才使预测成为可能大多数情况下,是通过m个以前像素的线性组合来生成的8.4.4无损预测编码预测编码的基本思想通过仅提取每74无损预测编码无损预测编解码系统无损预测编码无损预测编解码系统75无损预测编码当输入图像的像素序列fn逐个进入编码器,预测器根据过去的输入产生当前输入像素的估计值。预测器的输出舍入成最近的整数 f n 并被用来计算预测误差e n f n f n该误差用符号编码器借助变长码进行编码该误差用符号编码器借助变长码进行编码以产生压缩数据流的下一个元素。然后解码器根据接收到的变长码字重建en,并执行下列操作f n e n f n无损预测编码当输入图像的像素序列fn逐个进入编码器,预测76
展开阅读全文