《数字图像处理》课件10上海交大-(全)

1上海交通大学图像通信与信息处理研究所电子信息与电气工程学院电子工程系2010年度春季上海交通大学图像通信与信息处理研究所电子信息与电气工程学院电子工程系2010年度春季第六章图像数据压缩编码§§11图像编码概述图像编码概述§§22图像压缩编码的理论基础图像压缩编码的理论基础§§33熵编码熵编码§§44预测编码预测编码§§55变换编码变换编码§§66图像编码国际标准简介图像编码国际标准简介§§77小波变换编码小波变换编码2上海交通大学图像通信与信息处理研究所电子信息与电气工程学院电子工程系2010年度春季§§33熵编码熵编码A.A.霍夫曼码霍夫曼码B.B.可逆变长码和通用变长码可逆变长码和通用变长码C.C.算术码算术码数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季C.算术码(ArithmeticCoding)•不是分组码•算术码可分为二进制算术码（BAC）和多进制算术码•二进制算术码：输入为0/1构成的比特流•BAC应用于许多图像压缩标准中•编码效率略高于Huffman码，但抗干扰性更差3数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季1.算术码概述•什么是算术码？算术码是将输入的整个符号序列映射为实数轴上[0，1）区间内的某个子区间，再在该子区间内选择一个代表性的二进制小数作为实际的编码输出的编码方法•特点：无失真，熵编码，不是分组码•缺点：抗干扰能力差•很早就被提出（Shannon，1948年），1987年后才进入实用•二进制算术码（BAC）数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季2.二进制算术码原理•如何通过码区间的递归划分把输入序列映射为某个码区间设输入二进制符号序列为010，且已知0和1出现的概率和，可通过下述步骤实现映射：①在未读入输入序列前，取为初始码区间并可按概率、将其分为左、右二个子区间②读入第一个符号，现读入的第一个符号为0，故选择与对应的左边子区间，丢掉右边的子区间③再读入第二个符号1，则按递归划分的原则，取上次取中的区间的右半部，即④再读入第三个符号0，取上次选中区间的左半个子区间即可实现输入符号串与码区间的映射对应关系[)0,10p1p[)00,p0p[)00,p[)000,pppi[)0000010,ppppppp+iiii0p1p4数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季说明：1）输入010后得到的码区间长度为2）若输入的三个符号不是010而是其他串xxx，可找到8个不同长短、位置的码区间与之对应，即：不同的输入对应不同的码区间，其互相之间没有重叠，所有码区间的总和覆盖了整个[0，1）区间3）各子区间的长度为其中，是输入串中“0”符号的个数，是“1”的个数即：子区间长度与输入串中0/1的先后位次序无关，而与0/1的个数有关；而子区间的位置和输入串中0/1出现的先后次序有关010pppii(0)N(0)(1)01NNPP⋅(1)N5数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季二进制自然码其实就是在时的码区间的划分010.5pp==00000101001110010111011100000111101xxxx010xxx••••••••••底部码含义对应的码区间：（例）数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季•当时，可以用二进制自然码来表示选中的码区间——没有压缩•一般情况下，，如果能够用某种方式表示选中了哪个子区间，并且这种表示所需的平均比特数小于输入的二进制符号的长度——实现压缩•两点说明：①所有与不同输入符号串对应的子区间都不重叠，且其总和覆盖了全部区间，按子区间位置与长度来推断输入符号串不会产生二义性②在确定了头几个输入符号，从而对作了初步划分之后，再输入任何尾串，则对应的码区间总是落在已选定的码区间内部•精确地表示选中码区间的底部和长度将花费很多bit，不能达到压缩目的•策略：在选中的码区间内找一个最大的二进制自然码区间来作“近似”，输出此“近似”区间的底部位置，由底部位置码的“位数”来反映码区间的长度010.5pp==01pp≠[)0,1[)0,16数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季•用110表示选中的码区间-若少用1个比特，用11表示的范围大于-若多用1比特，用1100或1101，虽然落入子区间，但浪费了1bit[),AB[),AB[),AB数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季3.BAC编码过程(1)编码公式和步骤：•先推导码区间分割的递推公式7数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季•设在以往分析了输入的前面几个符号构成的符号串之后，选定的码区间底部（左部）为，宽度为•再输入一个符号，若它为0，则码区间底部应改为，宽度应改为，若输入符号为1，则应改为和•若输入符号0的概率为，符号为1的概率为，则有下列递推关系式当输入为0时当输入为1时•如果把初始状态记作以前分析的符号串为空串，此时，作为初始状态；则后面只要根据输入符号为0或1，递归地用上述公式来修正码区间的底部和宽度，即可实现输入符号串到码区间的映射s()Cs()As()0Cs()0As()1Cs()1As0p101pp=−()()0CsCs=()()00AsAsp=i()()()01CsCsAsp=+i()()11AsAsp=iλ()0Cλ=()1Aλ=()Cs()As数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季(2)数字实例输入串为010，，时00.4p=10.6p=算术编码器的输出为0011（课堂练习）8数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季4.BAC解码过程•解码也是递归进行的•把收到的比特流看成二进制小数，记作，把它和比，若，则第一个符号必为0；反之，若，则可解出第一个符号为1•递归解码步骤：以表示已被解码的字符串，则判决下一个符号的过程为：①若则判下一个符号若则判下一个符号②根据解出符号对和作相应修正，以“模拟”编码端的码区间分割情况S()Cs()0A()()0CsA()()0CsA≥'s()()'0CsAs0x=()()'0CsAs≥1x=()Cs()'As上海交通大学图像通信与信息处理研究所电子信息与电气工程学院电子工程系2010年度春季第六章图像数据压缩编码§§11图像编码概述图像编码概述§§22图像压缩编码的理论基础图像压缩编码的理论基础§§33熵编码熵编码§§44预测编码预测编码§§55变换编码变换编码§§66图像编码国际标准简介图像编码国际标准简介§§77小波变换编码小波变换编码9上海交通大学图像通信与信息处理研究所电子信息与电气工程学院电子工程系2010年度春季§§33预测编码预测编码A.A.预测编码原理预测编码原理B.B.线性预测线性预测C.C.运动补偿和帧间预测运动补偿和帧间预测数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季图像压缩编码的一般框图10数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季A.预测编码原理•预测本身不引入误差•既可用于无失真编码，也可用于限失真编码•无失真编码：预测+VLC——JPEG•限失真编码：DPCM——预测编码的典型应用•预测应与量化和熵编码相结合数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季1.预测编码框图及其工作过程nxˆnxˆnxˆ11数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季要点：1)量化器必须放在预测环内——DPCM的关键若放在预测环外，则会发生漂移，使整个系统无法正常工作2)发端必须有一个和解码端完全一样的“本地解码器”3)对的预测只能依据来进行，而不能依据来进行1,,nnmxx−−''1,,nnmxx−−nx数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季B.线性预测1.一维情况如果是的线性组合，则称为线性预测，即其中，为预测参数，为预测阶数。求线性最优预测就是求，使为最小问题成为：求m个系数使最小设：为广义平稳随机过程，且（不失一般性）由线性预测预测差的公式，得令{}()0Exn=1,,nnmxx−−2neσ1ˆˆ()()()()mnnkkeenxxnxnaxnk=≡=−=−−∑{}()()2221nmenkkEeExnaxnkσ=⎧⎫⎡⎤⎪⎪==−−⎨⎬⎢⎥⎣⎦⎪⎪⎩⎭∑ˆnx1ˆˆ()()mnkkxxnaxnk=≡=−∑(1...)kakm=kamka2neσ()xn20neiaσ∂=∂12数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季对联立求解上式，写成矩阵形式，即可以用Levinson算法解出最优线性预测器的各系数可以证明，对最优线性预测（均方误差最小），预测差的方差为：(1,...,)iaim=()()()2120nmekkiExnixnaxnkaσ=∂⎧⎫⎡⎤=−−−−=⎨⎬⎢⎥∂⎣⎦⎩⎭∑()()101,2,,mkkRiaRkiim=−−==∑()()()()()()()()()()()()11011111102222120mkmaRRRMRiiRRRMRaRMRMRRMmm=⎛−⎞⎛⎞==⎛⎞⎜⎟⎜⎟⎜⎟−⎜⎟⎜⎟⎜⎟=⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟−−⎝⎠⎝⎠⎝⎠()()210nmekkRaRkσ==−∑1,,im=…数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季说明：原信号的方差：（因为设的期望为0）1)若原信号的各符号间不相关，即（对都成立）则——即信号无相关性时，预测没有压缩效果2)一般总是大于0（原信号有相关性），则且相关性越大，越小，即压缩比可越大3)预测项数的选择可以证明，对阶平稳马尔可夫过程，用阶线性预测是最好的（最小）()20nxRσ=1k≥()220nnexRσσ==22nnexσσ2neσ2neσmm()0Rk=()xn()Rkm()()210nmekkRaRkσ==−∑13数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季2.二维情况•趋势与一维时一致•要注意预测器的参考序列的因果性（可实现性）•实用上不一定先估计出各，再解方程求各系数•帧内预测器的实现方法：1)用预定的预测系数2)自适应地在多种预测方式中，选一种使预测差最小的方式kla(,)Rij1/81/41/81/2•1/41/41/2•数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季•帧内预测器ˆ(,)0.75(,1)0.75(1,)0.5(1,1)fxyfxyfxyfxy=−+−−−−ˆ(,)0.97(,1)fxyfxy=−ˆ(,)0.5(,1)0.5(1,)fxyfxyfxy=−+−0.97(,1)ˆ(,)0.97(1,)fxyifhvfxyfxyotherwise−≤⎧=⎨−⎩14数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季数字图像处理（DigitalImageProcessing）上海交通大学2010年度春季C.运动补偿和帧间预测•帧间预测-利用帧间相关性消除时间冗余度，以提高压缩比-关键：得到尽可能小的帧间差（背景区，运动区）•运动补偿（MotionCompensation）-找出运动物体在前一帧的区域位置，这样求出的预测