DVIP06 熵编码

门爱东教授menad,第06章熵编码EntropyCoding,2,内容提要Outline,熵编码原理Huffman编码算术编码视频信号的熵预测器用于冗余减少,3,其中U0是无记忆信源的消息集,由多个消息ak构成（k=1,2,K），出现的概率分别为Pj（j=1,2,K）。Y是输出集，由多个码字yk构成（k=1,2,K），yk与ak一一对应。Sm是符号集，由m个码元si构成(i=1,2,M)，符号集中的码元组成输出码字。,熵编码原理-信息量和信息熵,4,熵编码原理-信息量和信息熵,信息：是用不确定性的量度定义的信息量：从N个可能事件中选出一个事件所需要的信息度量或含量。上述消息“ak”的信息量定义为：,熵:如果将信源所有可能事件信息量进行平均就得到信息的熵(熵就是平均信息量)，单位是bits/Symbol。,熵的特性:,5,信源含有的平均信息量(熵)H(U0)，就是对符号U0进行可解码的变字长编码的平均码长Iav的下限，即无失真编码的理论极限。相反，如果有足够大的符号块进行联合编码，平均码长Iav可以逼近H(U0)。码的冗余定义为：信源中或多或少的含有自然冗余。,熵编码原理-信息量和信息熵,如果每个码字长度等于则码字的平均码长等于它的熵，没有冗余，即,对于二进制码字，概率将都是二进制分数：,6,熵编码原理-信息量和信息熵,例,对于等字长码，要表示4个事件，需要2bit，其平均码长为2bit/符号，冗余为0.25。,对于变字长码,7,熵编码原理变字长编码定理,在变字长编码中，对于出现概率大的信息符号，赋予短字长的码，对于出现概率小的信息符号，赋予长字长的码。如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长度一定小于按任何其它符号顺序排列方式得到的码字长度。最佳的平均码字长度：其中：P(ak)是信源符号ak出现的概率；Ik是符号ak的编码长度。根据编码方法定义规定：如果P(ai)P(as)，则IiIs如果将ai的码字与as的码字互换，则:,8,Huffman编码,Huffman于1952发明了整数码的最佳变字长编码，利用了上述熵、熵编码和变字长编码概念。所谓的整数码是指每个符号所对应的码字的位数都是整数。Huffman码码树形成步骤合并：把信源符号按概率大小顺序排列，出现概率最小的两个符号的概率相加，得到一个新的合并概率。置换：把这个合并概率看成是一个新组合符号的概率。类推：重复上述做法直到最后只剩下两个符号概率为止。赋值和反推：把上述码树转换为前缀码。完成以上概率顺序排列后，再反过来逐步向前进行编码，每一步有两个分支各赋予一个二进制码，可以对概率大的赋为“1”，概率小的赋为“0”。,9,Huffman编码,比特数,2,2,3,3,4,4,4,4,0,1,0,1,0,1,0,1,0,1,0,1,0,1,10,例：信源有四个符号：Xa1a2a3a41/21/41/81/8信息熵：,Huffman编码,Huffman（二进制编码）a1a2a3a4010110111平均码长：Iav=(1/2)1+(1/4)2+(1/8)6=1.75bit/字符编码效率：=1.75/1.75=100%编码冗余：R=0,11,4个符号的等长码：B=log24=2bita1a2a3a400011011L=2Pi=2编码效率：=H(X)/L=1.75/2=87.5%码表,Huffman编码,此例子中的码表,Huffman编码举例：原信源输出序列：a1a2a1a3a2a1a1a4.编码后的序列：01001101000111.,12,Huffman码解码,Huffman码是非歧义的，在解码过程中，对某个码字的解释是唯一的。原信源输出序列：a1a2a1a3a2a1a1a4.，编码后的序列：01001101000111.当接收端收到码流01001101000111时，按照码表，以0开头的码字只有0，因此，解出第1个符号为a1；去掉已解码的0后，码流剩下1001101000111，以1开头，第2比特是0，因此，码字是10，因此，解出第2个符号为a2；.顺着码树解码，树根树干树枝树叶,13,Huffman编码的应用,在实际应用中，Huffman编码通常与其他编码技术一起使用例：无损图像压缩Grayimages(0255),Imagesize:256*256,Sena,Earth,Sensin,Omaha,14,Huffman编码在图像压缩中的应用,压缩率不是很高，平均每个像素约减少1比特更实用的技术：与预测模型一起使用,直接对像素用Huffman编码进行压缩,15,Huffman编码在音频压缩中的应用,CD质量的音频：采样频率：44.1kHz；每个样本16比特数据量巨大,对16比特的CD质量音频用Huffman编码进行压缩,16,Huffman码特点,Huffman编码字长参差不齐，是变字长整数码，输出码率是变化的。因此，对于恒定码率信道，需要增加输出缓存器来平滑。Huffman编码在信源编码概率分布不均匀时效率高，所以概率比较均匀时，Huffman码性能不好。Huffman编码表缺省，好处是对称性，降低编码时间。实际概率模型和Huffman编码时假设的概率模型有差异时，编码效率会下降。编码方法不惟一，码长方差较小的编码更好。对同一个信源所构成的Huffman码不是唯一的，但它的平均码长是一样。因为一个节点的上下两个分支既可以赋0（或1），也可以赋1（或0）；同时，对概率相同的两个事件的排列顺序也是随便选择的。Huffman码是非歧义的，即在解码过程中，对某个码字的解释是唯一的。,17,算术编码,原理：算术编码是另一种常用的变字长编码，它也是利用信源概率分布特性、能够趋近熵极限的编码方法。它与Huffman一样，也是对出现概率大的符号赋予短码，对概率小的符号赋予长码。但它的编码过程与Huffman编码却不相同，而且在信源概率分布比较均匀的情况下其编码效率高于Huffman编码。它和Huffman编码最大的区别在于它不是使用整数码。Huffman码是用整数长度的码字来编码的最佳方法，而算法编码是一种并不局限于整数长度码字的最佳编码方法。算术编码是把各符号出现的概率表示在单位概率0，1区间之中，区间的宽度代表概率值的大小。符号出现的概率越大对应于区间愈宽，可用较短码字表示；符号出现概率越小对应于区间愈窄，需要较长码字表示。,18,算术编码原理,符号序列S3S3S2S4为例,在算术编码中通常采用二进制分数表示概率，每个符号所对应的概率区间都是半开区间，即该区间包括左端点，而不包括右端点，如S1对应0,0.001)，S2对应0.001,0.01)等。,19,算术编码原理,符号序列S3S3S2S4的第一个符号S3用指向第3个子区间的指针来代表，可以用这个区间内的任意一个小数来表示这个指针，这里约定这个区间的左端点代表这个指针，因此得到第一个码字.011。后续的编码将在前面编码指向的子区间内进行，将.011,.111区间再按概率大小划分为4份，第二个符号S3指向.1001(S3区间的左端），输出码字变为.1001。然后，S3对应的子区间又被划分为4份，开始对第三个符号S2进行编码，.,算术编码产生的码字实际上是一个二进制数值的指针，指向所编的符号对应的概率区间。,20,算术编码基本法则,两个参量：编码点（指针所指处）C和区间宽度A。初始状态编码点（指针所指处）C=0区间宽度A=1.0新编码点C=原编码点C原区间APi新区间A=原区间Api序列S3S3S2S4的编码过程：第1个符号(S3):C=0+1.011=.011A=1.1=.1第2个符号(S3):C=.011+.1.011=.1001A=.1.1=.01第3个符号(S2):C=.1001+.01.001=.10011A=.01.01=.0001第4个符号(S4):C=.10011+.0001.111=.1010011（输出的码字）A=.0001.001=.0000001,符号Si对应的累积概率,符号Si对应的概率,最后区间的一个数输出,21,算术编码解码,算法解码采取与编码过程相反的步骤把接收到的码字串指向其对应的子区间，得到此子区间对应的符号，即为解码后的符号。即从码字串中减去已解码符号的子区间的左端点的数值（累积概率），并将差值除以该子区间的宽度（概率值），得到新的码字串。上述例子当收到字码串(.1010011)时，其指向子区间.011,.111，对应于S3，因此，得到第1个符号为S3。新码字串：（.1010011-.011)(.1)=0.100011，新码字串仍然指向子区间.011,.111，因此，第2个符号仍为S3。其它符号依次类推注意：算术编码中的进位在Huffman编码中，后续符号产生的码字只是简单地附加到先前的码字串之后，并不改变已有的码字串。在算术编码中，由于新编码点C表达式中相加运算而产生进位，从而与Huffman不同。例如上述的第3个符号后码字串为.10011，但第4个符号后码字串变为.1010011，,22,二进制算术编码,二进制算术编码输入的字符只有两种，如果信源字符集内包含有多个字符，则先将这些字符经过一系列的二进判决，变成二进制字符串。这两个符号构成的序列的编码与算术编码原理相同，仍是不断划分概率子区间的递归过程。在两个输入字符中，出现概率较大的为MPS(MoreProbableSymbol)，MPS的概率为Pe；出现概率较小的为LPS(LessProbableSymbol)，LPS的概率为Qe，Pe=1-Qe。编码初始化子区间为0，1，MPS与LPS分配如图所示：,23,编码时，设置两个专用寄存器（C，A）C寄存器的值为编码点（指针所指处）A寄存器的值为子区间的宽度(该宽度恰好是已输入符号串的概率)初始化时：C=0A=1随着被编码数据源输入，C和A的内容按以下编码规则修正：当低概率符号LPS到来时：(LPS的概率为Qe，累积概率为0)C=CA=AQe当高概率符号MPS到来时：(LPS的概率为Pe，累积概率为Qe)C=C+AQeA=Ape=A（1-Qe）,二进制算术编码编码规则,算术编码的基本法则：新编码点C=原编码点C原区间APi新区间A=原区间Api,符号Si对应的累积概率,符号Si对应的概率,24,第1个符号1为MPSC=C+AQe=0+10.001=0.001A=APe=10.111=0.111,0.001,0.111,二进制算术编码编码举例,例:信源符号序列110111110为LPSQe=1/8=（0.001）b1为MPSPe=7/8=（0.111）b初始状态：C=0(子区间起始位置)A=1（子区间宽度）,第2个符号1仍为MPSC=C+AQe=0.001+0.1110.001=0.001111A=APe=0.1110.111=0.110001,0.001111,0.110001,0,1,25,第3个符号0为LPSC=C=0.001111A=AQe=0.1100010.001=0.000110001继续下去.最后得C=0.010001111110111100000001A=0.000011001001000010111111结果,二进制算术编码编码举例,0.001111,0.000110001,头C,A,尾,头0.010001111110111100000001（C）+0.000011001001000010111111（A）尾0.010101000111111111000000,头0.0101尾传送码字为0101,编码输出可以是最后一个编码区间中的任意数值，但为了取得最好的编码效率，选择的小数应有最短的比特长度。,26,二进制算术编码编码举例,上述算术编码过程,27,解码：按Qe、Pe分成两个子区间，判断被解码的码字落在哪个区间，并赋予对应符号。设c=（0.0101)b是被解码的值，初始值A=1Qe=0.001,二进制算术编码解码,当c落在QeAA之间，解码符号为D=1C=C-QeAA=A（1-Qe）,当c落在0QeA之间，解码符号为D=0C=CA=QeA,c=0.0101落在QeA-A之间，解码符号为D=1c=c-QeA=0.0101-0.001=0.0011A=A（1-Qe）=0.111,c=0.0011落在QeA-A之间，解码符号为D=1c=c-QeA=0.0011-0.000111=0.000101A=A（1-Qe）=0.1110.111=0.110001,c=0.000101落在0-QeA之间，解码符号为D=0c=c=0.000101A=AQe=0.1100010.001=0.000110001,28,二进制算术编码解码,29,算术编码在图像压缩中的应用,Sena,Earth,Sensin,Omaha,30,算术编码的特点,不需要码表，直接对序列进行编码(不是码字的串联):非分组码可证明是唯一可译码；渐近接近熵界；对不均衡的分布，比Huffman更有效。在Huffman码中，最短的码字为1bit；而在二进制算术编码中，对LPS编码不增加已编好的码字串的长度（C=C)。只产生必要的码字允许将建模和编码分开，容易与自适应模型和上下文模型结合算术编码应用的越来越广泛：JPEG、MPEGx、H.26x。注意：在概率子区间不断划分的过程中，区间宽度A越来越小，因此，用来表示A的数字的位数则需要越来越多。但是实现更复杂，成本高对错误很敏感，如果有一位发生错误就会导致整个消息译码错误,31,算术编码参考资料,Theideaofencodingbyusingcumulativeprobabilityinsomeordering,anddecodingbycomparisonofmagnitudeofbinaryfractionwasintroducedinShannonscelebratedpaper1948.TherecursiveimplementationofarithmeticcodingwasdevisedbyElias(anothermemberinFanosfirstinformationtheoryclassatMIT).ThisunpublishedresultwasfirstintroducedbyAbramsonasanoteinhisbookoninformationtheoryandcoding1963.TheresultwasfurtherdevelopedbyJelinekinhisbookoninformationtheory1968.Thegrowingprecisionproblempreventedarithmeticcodingfrompracticalusage,however.TheproposalofusingfiniteprecisionarithmeticwasmadeindependentlybyPasco1976andRissanen1976.,32,算术编码参考资料,PracticalarithmeticcodingwasdevelopedbyseveralindependentgroupsRissanen1979,Rubin1979,Guazzo1980.Awell-knowntutorialpaperonarithmeticcodingappearedinLangdon1984.ThetremendouseffortsmadeinIBMleadtoanewformofadaptivebinaryarithmeticcodingknownastheQ-coderPennebaker1988.BasedontheQ-coder,theactivitiesofJPEGandJBIGcombinedthebestfeaturesofthevariousexistingarithmeticcodersanddevelopedthebinaryarithmeticcodingprocedureknownastheQM-coderpennebaker1992.,33,算术编码参考资料,W.B.Pennebaker,J.L.Mitchell,G.G.Langdon,Jr.,R.B.Arps,“AnoverviewofthebasicprinciplesoftheQ-Coderadaptivebinaryarithmeticcoder,”IBMJ.Res.Develop.,vol.32,no.6,November1988.Witten,Radford,Neal,Cleary,“ArithmeticCodingforDataCompression”CommunicationsoftheACM,vol.30,no.6,pp.520-540,June1987.Moffat,Neal,Witten,“ArithmeticCodingRevisited,”ACMTransactionsonInformationSystems,vol.16,vo.3,pp.256294,July1998.,34,亮度信号Y的概率密度函数和熵,图象：3个EBU测试图，3个SMPTE测试图，用256级均匀量化（8bit/象素）。,图象最低的熵：,图象最大的熵：,35,色差信号R-Y、B-Y的概率密度函数和熵,36,联合信源,联合信源同时产生N个符号，通过对这些符号进行联合编码，可以获得编码增益。此时，平均码字长度的下限是联合熵（共熵）：,通常,如果U1,U2,.,UN是统计独立的，则上式相等。,37,视频分量Y、R-Y、B-Y之间的统计相关性,数据：3个EBU和SMPTE测试图，每个分量用64级均匀量化（6bits/pel)。,RGB分量之间的统计相关性更强,38,Markov过程,视频信号相邻象素不是统计独立的“有记忆信源”,有记忆信源的模型采用Markov随机过程。N阶Markov信源中符号UT的条件概率为：,T时刻Markov信源的状态,39,有记忆信源的熵,N阶Markov信源：条件熵,（无记忆信源时相等）,4