数字压缩技术

第六章数据压缩技术I信息的数据量和压缩的必要性数字化了的图像、视频、音频等信息数据量很大。数据压缩的可能性原始信源数据存在很大冗余度视觉掩盖效应(对亮度敏感,对边缘急剧人的生理特性变化不敏感)听觉：对部分频率信号不敏感压缩——去掉冗余信息和一些不敏感信息。无损压缩：源——压缩——存储传输——解压——目的（源与目的信息一模一样。）有损压缩：源与目的信息有差别。数据冗余的概念和分类（1）冗余的基本概念信息量与数据量的关系可由下式给出:I=D-duI:信息量D:数据量du:冗余量例:读一篇文稿,每分钟180字,一个汉字占两个字节（内码）,每分钟文本数据量360b；若对语言直接录音,4K×2×8=64Kb/s(8b)每分钟数据量:480Kb（2）数据冗余的类别①空间冗余规则物体和规则背景的表面物理特性具有相关性。②时间冗余连续播放的画面，前后几帧背景基本无变化。例如：小车行驶，外型无变化。（只需小车运动矢量）。③统计冗余。空间、时间冗余，把图象信号看作概率信号时所反映出的统计特性。④结构冗余。物体表面纹理等结构。（规则图形，冗余量大）⑤信息熵冗余。熵定义：1k0i2PilogPiEiP：在S中出现的概率，表示包含在中的信息量，也就是编码所需要的位数。但{}难预估，取位数为最多信息所需位数，带来信息熵冗余。i2PLOGiSiSiS1K0PP⑥视觉冗余人类视觉系统特点：对图象场的注意是非均匀和非线性的。a.对亮度比对色度敏感b.并非图象任何变化均能感知。分辨能力：灰度等级一般图象量化采用灰度等级6282⑦知识冗余。人有先验知识：图象的结构等，但在计算机存储时未考虑。⑧其他冗余。图象的空间非定常特性带来的冗余。数据压缩的编码方法1、数据压缩方法的分类编码过程：对原始数据经过编码进行压缩解码过程：对编码数据进行解码、还原压缩处理过程（1）可逆编码（无损压缩）信息非丢失型编码无损压缩解码图象与原始图象严格相同。基于信息熵原理，如哈夫曼编码、算术编码、游程编码。压缩能力：与所处理图象的信息熵有关，压缩比不太大。应用：要求不丢失信息（医疗、卫星图象通信系统等）。（2）不可逆编码（有损压缩）信息丢失型编码还原图象与原始图象存在一定误差。(3)对称压缩压缩算法与解压算法一样收发双方以同一种速度操作，适用于实时应用场合2、常用的压缩编码①预测编码：以相邻的且已被编码的点对目前点进行预测估计。基础：同帧图象的相邻像素点之间相关性比较强。(4)不对称压缩压缩与解压缩速率不同如：视频ＤＶＤ光盘针对统计冗余进行的压缩。②变换编码：将图象光强矩阵(时域信号)系数空间(频域)上进行处理。针对统计冗余进行的压缩。变换④信息熵编码：概率大的信息用短码字表示。概率小的信息用长码字表示。⑤分频带编码：时域频域，按频率分带，用不同的量化器进行量化。③量化与向量量化编码：模拟数字，量化。一次量化多个点：向量量化。⑥结构编码：结构特征抽取（边界、轮廓、纹理），保存参数。⑦基于知识的编码：利用人的知识形成规则库，用参数描述，实现图象编码和解码。某一事件信息量定义：0＜Pi≤1Pi为第i个事件的概率i2iPLOGI22LOGNiiILOGP2、信源S的熵的定义一、香农-范诺编码1、熵的概念熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，也就是概率越小。特例：某信息源有N个事件，且任一事件概率均相等，为1/N，则：所传输的消息量是其出现概率的单调下降函数。例：如果从256个数中猜一个数，最少提问几次一定可以猜到？第一次，“是否大于128？”消去一半可能…………共8次也就是说，每次提问会得到1b的信息量。因此，在256个数中选定某一个数所需要的信息量为：b8256log2信息量是指从N个相等可能事件中选出一个事件所需要的信息度量或含量，也就是在辨识N个事件中特定的一个事件的过程中所需提问“是或否”的最少次数。根据香农理论，信源S的熵的定义：是在S中出现的概率。是包含在中的信息量，也是编码所需位数。例1：一幅图象用256级灰度表示，若每一个像素点灰度概率为：则编码每个像素点需要8位。)P/1(LOGi2iSiS2561)(iSPNiiiNiiiNiiiSPLOGSPPLOGPPLOGPSH121212)()()/1()()(iSPiS例2、一幅灰度图象有40个像素组成，灰度共5级，分别用符号A、B、C、D、E表示，40个像素中出现灰度A的像素数有15个，灰度B的有7个，C的有7个，D的有6个，E的有5个，若用3位表示5个等级的灰度值，编码这幅图象总共需要120位，用香农理论，图象熵为：)7/40(LOG)40/7()15/40(LOG)40/15()X(H22196.2)5/40(LOG)40/5(2若平均每个灰度用2.196位表示,则图象总共需要87.84位。用香农——范诺算法编码：首先，将灰度概率从大到小排列出现次数（）分配的代码需要的位数A15（0.375)1.41500030B7(0.175)2.51450114C7(0.175)2.51451014D6(0.150)2.736911018E5（0.125)3.000011115总位数:91iP压缩比：1.3:1ABCDE00111100)P/1(LOGi2二、霍夫曼编码以前举的例2：一幅图象5个灰度等级，40个像素。代码出现次数位数A01515B100721C101721D110618E111515共90位（1）霍夫曼编码步骤P.234100.275概率A0.375B0.175C0.175D0.150E0.12500.35001101压缩比：1.33:1（2）霍夫曼编码特点①码不唯一。②码字变长（硬件实现不大方便）,但不需要另外附加同步代码。（在压缩文件中查找或调用内容困难）。③概率分布不同，编码效率不同。（效率比香农-范诺编码高）（概率分布不均匀,效率高；概率分布均匀,效率低，一般不用）④Huffman编码表解码要用传输要考虑编码表所占比特率数若编码基于大量概率统计，传输可省去Huffman编码表使用缺省的Huffman编码表⑤霍夫曼码没有错误保护功能三、算术编码在图象数据压缩标准（JPEG等）中扮演重要角色。消息：用0~1之间实数进行编码。算术编码参数：符号的概率和它的编码间隔。（1）例：假设信源符号为{00,01,10,11}其相应概率分别为{0.1,0.4,0.2,0.3}根据概率把间隔[0,1)分成[0，0.10），[0.1，0.5），[0.5，0.7），[0.7，1）4个子间隔。符号概率初始编码间隔000.1[0,0.1)010.4[0.1,0.5)100.2[0.5,0.7)110.3[0.7,1)二进制消息序列10001100101101.第一个符号为10,它的编码范围:[0.5,0.7)第二个符号为00,它的编码范围:[0,0.1),它的间隔取[0.5,0.7)的第一个十分之一作为新间隔[0.5,0.52)第三个符号为11,它的编码范围:[0.7,1),它的间隔取[0.5,0.52)的最后三个的1/10,新间隔[0.514,0.52)0.02×0.7=0.0140.02×0.7+0.50.2×0.1+(0.2×0.1)依次类推…输出的消息编码：最后一个间隔中的任意数。从[0.5143876,0.514402)中,选一个数作为输出。取0.5143876译码过程译码符号间隔0.5143876在间隔[0.5,0.7)10[0.5,0.7)0.5143876在间隔[0.5,0.7)的第一个1/1000[0.5,0.52)0.5143676在间隔[0.5,0.52)的第7个1/1011[0.514,0.52)…………….译码消息:10001100101101(2)编码算法:一个有M个符号(i=1,2,3…,M)的字符集,假定概率ianX输入符号用表示,第n个子间隔范围用以下公式表示:,)(iiPaP1PPP)a(PM21iM1iii1ii1ni1i1i1n1nnnnPdlPdl[rl[I），），1-n且和表示间隔左边界的值，表示间隔右边界的值，表示间隔长度。则编码按以下步骤进行：①首先在1和0之间给每个符号分配一个初始间隔，子间隔的长度等于它的概率。初始子间隔的范围用右式表示：令，L=和R=1d,0l00,0P0nlnrnnnlrd)PP[)r,l[Ii1ii1ii,1i111111lrd1l1r②L和R的二进制表达式分别表示为：1u若，不发送任何数据，转到步骤③。若=，就发送二进制符号。1kkk2uL和1kkk2vR其中和等于“0”或“1”。kukv比较和1u1u1v1u1v1v≠2u2v2uinaX若，不发送任何数据，转到步骤③若，就发送二进制符号……比较直到两个符号不相同，然后转入步骤③③n+1，读下一个符号。假设第n个输入符号为，按照以前的步骤把这个间隔分成如下子间隔：令，，然后转到步骤②例：输入序列：，，……i1ii1n1ni1i1i1n1nn,nn)PdI,PdI[)rl[InlLnrRnnlrdnX2a1a3a比较和22vu22vu输入的第一个符号:,则i=2,定义初始间隔：符号概率初始编码间隔=0.5[0,0.5)=0.25[0.5,0.75)=0.125[0.75,0.875)=0.125[0.875,1)1a2a3a4a1p2p3p4p21axi1ii1ii1i1,11),75.0,5.0[)p,p[)rl[I则知。25.0d1左、右边界二进制表示：L=0.5=0.1(B)R=0.75=0.11(B)。按步骤②，，发送1，转到步骤③22vu11vu输入第三个字符：，i=3,子间隔：33axi1ii1ii111i112,22),625.0,5.0[)pdl,pdl[)rl[I得。125.0d2L=0.5=0.100(B)R=0.625=0.101(B)。发送0，转到步骤③0vu2233vu输入第二个字符：，i=1,子间隔：12axi1ii1ii221i22333),609375.0,59375.0[)pdl,pdl[)r,l[I015625.0d3L=0.59375=0.10011(B)R=0.609375=0.100111(B)。发送0，，发送1，发送1，，转到步骤③…….0vu3366vu1vu441vu55发送编码:10011……+结束符。特点:1)对整个消息只产生一个码字([0，1）中的一个实数），译码器需接收所有位才能译码。2）对错误敏感。一位错，整个消息译错。3）精度问题。不可能无限长。12位、32位、64位精度，比例缩放。四、行程编码（Runlengthencoding，RLE）长度编码，游程编码。（无损压缩）相同灰度值相邻像元长度为：“行程”。如：一幅灰度图象，第n行像素11552200000735238用RLE编码方法得到代码70315253180变长行程编码（070031525031080定长行程编码）编码前：73个代码，编码后：11个代码。压缩比：7：1。压缩比主要取决于图象本身特点。图象中相同颜色图象块越大，压缩比越高，反之，压缩比越小。对颜色丰富的图象，一行上具有相同连续像素很少，若仍用RLE编码，则可能图象数据反而更大。解决方法：与其它压缩编码技术联合应用。RLE对差错敏感（一位符号出错会改变行程编码的长度，从而使整个图象出现偏移）。解决方法：加行同步，列同步。五、词典编码（无损压缩）dictionaryencoding有些场合，开始事先不一定知道数据统计特性对这些数据压缩通用编码技术词典编码无损压缩（1）词典编码的思想根据：数据包含重复代码（文本文件等）两种想法：①查找正在压缩的字符序列在以前输入的数据中是否出现过，若已出现