Shannon-Fano-Elias编码的实现-数字图像处理

第5章图像编码与压缩知识要点•信息论中的有关概念：信息，信息量，信息熵，冗余度•统计编码•预测编码•变换编码•混合编码•静态图像压缩标准：–JPEG、JBIG、JPEG2000等5.1概述•数据编码的目的各异–信息保密–信息的压缩存储与传输等•数码相机图像编码与压缩技术成功的范例。•本章主要介绍静态图像压缩编码的原理、应用及有关的国际标准。5.1.1数据压缩的基本概念•数据压缩–以较少的数据量表示信源以原始形式所代表的信息–目的在于节省存储空间、传输时间、信号频带或发送能量等。数据压缩系统组成图熵（Entropy）•代表信源所含的平均信息量•若信源编码的熵大于信源的实际熵，则信源中的数据一定存在冗余度•冗余数据的去除不会减少信息量。•信息量与数据量的关系可由下式表示IDdu（5.1）5.1.2图像编码压缩的必要性•图像信号的数据量可表示为•Vw·h·d/8（5.2）–V、w、h、d分别表示图像数据量（字节，byte，B）、图像宽度（像素数，pel）、图像高度（像素数，pel）、图像深度（位，bit）。•图像的尺寸为w·h。典型图像的数据量图像种类图像参数数据量二值传真图像A4（210297mm）大小、172823762色分辨率501KB灰度图像512512，8bit灰度等级256KBVGA图像640480256色300KBCIF视频图像352288256色，亮度取样率为3MHz，亮度和两色差按4∶1∶1取样，亮色量化位数共12bit，帧频29.97，按1s计算4.3MBHDTV亮度信号1280720，量化位数为8bit，帧频30Hz，按1s计算52.7MB5.1.3图像编码压缩的可能性一般图像中存在着以下数据冗余因素:•编码冗余•像素间的相关性形成的冗余•视觉特性和显示设备引起的冗余5.1.4图像编码压缩的技术指标常用的图像压缩技术指标:•图像熵与平均码长•图像冗余度与编码效率•压缩比•客观评价SNR•主观评价图像质量的主观评价等级评分评价说明5优秀图像质量非常好4良好图像质量高,有很小的干扰但不影响观看3中等图像质量可接受,但有一些干扰,对观看稍有妨碍2差图像质量差,对观看有妨碍1很差,劣图像质量很差,无法观看图像编码主、客观评价的内在关系图像类型高分辨率广播电视普通数字广播电视数据库图像会议电视传输数码率客观评价SNR主观评价７４Mb/s≧48dB≧4.5分34Mb/s≧43dB≧4.0分识别图像≧３６dB≧３.0分６４kb/s≧３0dB≧2.5分压缩后图像5.1.5数据压缩方法的分类1.无损压缩（LosslessCompression）:•Huffman编码•Shannon编码•游程编码•算术编码•轮廓编码有损压缩（LossyCompression）•预测编码•变换编码•混合编码现代压缩编码方法：•分形编码•模型基（Model-based）编码5.2统计编码•统计编码–根据信源的概率分布特性，分配具有惟一可译性的可变长码字，降低平均码字长度，以提高信息的传输速度，节省存储空间。•基本原理–在信号概率分布情况已知的基础上，概率大的信号对应的码字短，概率小的信号对应的码字长，这样就降低了平均码字长度。5.2.1Huffman编码•1．前缀码（PrefixCode）4层树形结构的编码情况2．Huffman编码算法：•①将图像的灰度等级按概率大小进行升序排序。•②在灰度级集合中取两个最小概率相加，合成一个概率。•③新合成的概率与其他的概率成员组成新的概率集合。•④在新的概率集合中，仍然按照步骤②～③的规则，直至新的概率集合中只有一个概率为1的成员。这样的归并过程可以用二叉树描述。•⑤从根节点按前缀码的编码规则进行二进制编码。Huffman编码示意图•左图所示为建立码的过程•右图所示为从根开始，经各中间节点到叶节点的路径采用二进制编码的情况编码过程举例•第1行和第2行列举了一个信源的统计特性•结果如第三行所示符号集{xi}x1x2x3x4x5x6概率分布{pi}0.400.200.120.110.090.08Huffman编码1010000001011001113．Huffman编码的性能•优点：–实现Huffman编码的基础是统计源数据集中各信号的概率分布。–Huffman编码在无失真的编码方法中效率优于其他编码方法，是一种最佳变长码，其平均码长接近于熵值。•缺点：–当信源数据成分复杂时，庞大的信源集致使Huffman码表较大，码表生成的计算量增加，编译码速度相应变慢–不等长编码致使硬件译码电路实现困难。上述原因致使Huffman编码的实际应用受到限制。4．图像的Huffman编译码系统5.2.2Shannon编码与Fano编码•1.Shannon提出了将信源符号依其概率降序排列，用符号序列累积概率的二进制表示作为对信源的唯一可译编码。•其应用于图像编码的步骤如下：•（1）将N个灰度级xi按其概率递减进行排列。•（2）求概率分布pi的第i个灰度级的二进制位数ni。•(5.10)•（3）计算与pi相对应的累积概率Pi,把与Pi相对应的二进码和接下去与pk（ki）相应的码相比较，前面的ni位至少有一位以上的数字是不同的。1loglog22iiipnp【例5.2】由表5.3计算该信源的Shannon编码•平均码字长度为2.92，较Huffman编码为长。2.Fano编码步骤•（1）将图像灰度级xi其概率大小按递减顺序进行排序。•（2）将xi分成两组，使每组的概率和尽量接近。–给第一组灰度级分配代码“0”，第二组分配代码“1”。•（3）若每组还是由两个或以上的灰度级组成，重复上述步骤，直至每组只有一个灰度级为止。【例5.3】图5.6以表5.3的信源为例说明Fano编码。5.2.3算术编码•在信源各符号概率接近的条件下，算术编码是一种优于Huffman编码的方法。•算术编码又称Shannon-Fano-Elias香农-费诺-埃利斯编码•原理：•①累积分布函数，修正的累积分布函数为并把和用二进制表示。•②码长取为，码字表示取小数点后位二进制位。11kkiiFapaAaaki,kkiikapapaF2111Aaaki,kaFkaF1log1iilapaiiilaWFaiilaFaial•Shannon-Fano-Elias编码的实现•信源及累积概率表示•迭代计算初值•两个参数：区间宽度A＝，的区间宽度。区间左端点BNNNaFaFaFapapaPaaaX21212101aFiiiapaFaF1iapia•编码算法实现：proc-code•初始化：B＝=0；左端点•A＝1；初始化区间宽度为[0,1]•输入符号序列X＝（）•FORi=1Tokstep1•DO()；输入新的符号•B=:B+；确定新的左端点（左•端点调整）•A=:；确定新宽度（宽度压缩）•ENDDO•ENDFOR•输出W=(B+A/2)二取L位作为编码点值。•ENDproc-code1aF1apkixxxx21kiaxkaFAkaPA•解码算法实现：Proc-decode•whileB0•ForK=1toN-1STEP1•If•；搜索所在区间•Then•；•break；•End-If•B=:B-；确定新的码点值（左端点归零）。•B=:；宽度扩展为[0,1]（新码在[0,1]之间解码）•End-While•输出码序列EndProc-decode1iiaFBaFikaxikaxiaFiaPB•【例6-1】根据信源的概率分布进行算术编码。已知信源的概率分布为•求二进制序列01011的编码。535210X举例•解：步骤如下：•（1）二进制信源只有x1=0和x2=1两种符号，相应的概率为pc=2/5,pe=1-pc=3/5•（2）设s为区域左端起始位置，e为区域右端终止位置，l为子区的长度，则–符号“0”的子区为[0，2/5），子区长度为2/5;–符号“1”的子区为[2/5，1]，子区长度为3/5。（3）随着序列符号的出现，子区按下列公式减少长度:•新子区左端=前子区左端+当前子区左端×前子区长度•新子区长度=前子区长度×当前子区长度•设初始子区为[0，1]，步序为step，则编码过程参见实例。•可见，最后子区左端起始位置•最后子区长度0010016920.001110)3125s二进十进十进（）（0.2214）=（1080.17280.001001)625l二进十进十进（）（）（•最后子区右端终止位置•编码结果为子区起始位置与终止位置之中点=0.0100111。•x=01011的概率为p(x)=p2(0)p3(1)=(2/5)2(3/5)3,码长Lx=-log2p(x)=4.8548=5•所以，二进序列的算术编码为01001。6921080.39420.011001)3125625e二进十进十进（）（）（0.0011100.0110012算术编码算法的计算步骤实例stepxsl1002/5210+（2/5）×（2/5）=4/25（2/5）×（3/5）=6/25302/5+0×6/25=4/25（6/25）×（2/5）=12/125414/25+（2/5）×（12/125）=124/625（12/125）×（3/5）=36/62551124/625+（2/5）×（36/625）=692/3125（36/625）×（3/5）=108/6255.3预测编码预测编码的基本思想：•在某种模型的指导下，根据过去的样本序列推测当前的信号样本值，然后用实际值与预测值之间的误差值进行编码。•如果模型与实际情况符合得比较好且信号序列的相关性较强，则误差信号的幅度将远远小于样本信号。图像差值幅度的概率分布5.3.1预测编码基本原理•对实际值与预测值之间的误差值进行编码•差分脉冲编码调制–DifferentialPulseCodeModulation–DPCMDPCM系统的组成5.3.2线性自适应预测编码•假设经扫描后的图像信号x（t）是一个均值为零、方差为的平稳随机过程。线性预测就是选择ai（i1，2，…，N1）使预测值•并且使差值en的均方值为最小。•预测信号的均方误差（MSE）定义为E{en}=E{(xn-x′n)2}11nNiiixax设计最佳预测的系数ai，采用MMSE•最小均方误差准则。可以令•定义xi和xj的自相关函数R（i，j）=E{xi，xj}•写成矩阵形式为Yule-Walker方程组0}{2niaeE)1()2()1()0()3(2()3()0()1()2()1()0(1n21NRRRaaaRNRNRNRRRNRRR）)()(11ikRaiRNkk若R（i）已知，该方程组可以用递推算法来求解ai。通过分析可以得出以下结论：•图像的相关性越强，压缩效果越好。•当某个阶数已使E{eN,eN1}0时，即使再增加预测点数，压缩效果也不可能继续提高。•若{xi}是平稳m阶Markov过程序列，则m阶线性预测器就是在MMSE意义下的最佳预测器。当前像素与邻近像素的位置关系常用预测器方案•前值预测：用x0同一行的最近邻近像素来预测=x0•一维预测：如上图中的x1、x5。•二维预测：如上图中的x1、x2、x3、x4、x5、x6、x7等。•三维预测xˆ5.3.3自适应预测编码•自适应预测–预测参数根据信号的统计特性来确定，以达到最佳预测•预测编码的优点–直观快捷、便于实现•预测编码的缺点–压缩比不够高5.4变换编码5.4.1变换编码的基本原理•通过数学变换可以改变信号能量的分布，从而压缩信息量。•以傅里叶变换的概念说明合理的变换可以改变信号