搜索
第3章数据压缩的基本技术数据压缩处理一般由两个过程组成：编码过程：对原始数据进行编码压缩，以便存储和传输；解码过程：对压缩的数据进行解压，恢复成可用的数据。根据解压后数据的保真度，数据压缩技术可分为无损压缩编码：解码后的数据与原始数据完全相同，无任何偏差。这种编码通常基于信息熵原理，常用的编码有哈夫曼编码、算术编码、行程编码等。压缩比比较低，一般在2:1-5:1。主要用于要求数据无损压缩存储和传输的场合，如传真机有损压缩编码：解码后的数据与原始数据相比有一定的偏差，但仍可保持一定的视听质量和效果。它主要是在保持一定保真度下对数据进行压缩，其压缩比可达100:1。压缩比越高，其解压缩后的视、音频质量就越低。分类：a第一代图像压缩编码方法基于香农理论，80年代初趋于成熟，主要降低数据之间的相关性，去除冗余。b第二代图像压缩编码方法基于人类视觉特性的压缩方法，其核心思想是力图发现人眼是根据哪些关键特征来识别图像、或图像序列的，然后根据这些特征来构造图像模型。•例如，根据人眼对物体的轮廓比对物体内部细节更为敏感的特点，可以利用物体(而不是像素)的集合来表示图像。3.2数据压缩的理论依据3.2数据压缩的理论依据•数据压缩的理论基础为Shannon信息论。它一方面给出了数据压缩的理论极限，另一方面又指明了数据压缩的技术途径。•Shannon理论认为：信源中所含有的平均信息量（熵）是进行无失真压缩编码的理论极限。•无记忆信源：如果设计的编码方法的码字平均长度最接近熵，则说明该编码方法是最佳的。的下限。熵值是平均码长。稍大于最佳编码不可能；编码；时，有冗余，不是最佳NXHNXHNXHNXHN))(()()()(香农三大定理是信息论的基础理论。香农三大定理是存在性定理，虽然并没有提供具体的编码实现方法，但为通信信息的研究指明了方向。第一定理：可变长无失真信源编码定理采用无失真最佳信源编码可使得用于每个信源符号的编码位数尽可能的少，但它的极限是原始信号源的熵；超过了这一极限就不可能实现无失真的译码。第二定理：有噪信道编码定理若在信息传输率R不大于信道容量C时，则存在一种编码，当码长n足够大时，它可以使信道输出端的错误概率任意小，而信息传输率无限接近C；如果RC，则不能找到一种编码，使输出端错误概率任意小。第三定理：第三定理：保真度准则下的信源编码定理，或称有损信源编码定理只要码长足够长，总可以找到一种信源编码，使编码后的信息传输率R（单位：bit/信源符号）略大于率失真函数R(D)，而码的平均失真度不大于给定的允许失真度，即D‘=D设R(D)为一离散无记忆信源的信息率失真函数，并且有有限的失真度D，以及任意长的码长N，ε0,一定存在一种码字个数为M≥2N[R(D)+ε]的信源编码，使编码后的平均失真度D‘=D3.2.3信源的相关性与序列熵的关系•3.3信息率-失真理论•率失真函数R(D)：p32,(3-21)在一定允许失真D条件下的最低平均互信息量。•从信源编码的角度看：率失真函数是在允许失真不大于D时，信源编码给出的平均互信息的下界。即对信源信息率压缩的极限。•从接收端看，就是在满足失真不大于D的情况下，能够再现信源信息所必须获得的最低平均信息量。•限失真信源编码定理1设离散无记忆信源U的率失真函数为R(D),给定允许失真D，则当信息率RR(D),只要信源序列长度L足够长，一定存在一种编码方法其译码平均失真小于或等于D+ε逆定理：当RR(D)时,无论采用什么编译码方法，平均失真总是大于D。实际中解决的方法通常采用相反的思路，及给定信息率R，通过改变编码方法寻找尽可能小的平均失真。例如：在最佳量化器的设计中，其中量化的分层数N给定，（相当于信息熵给定）根据一定的误差准则，如均方误差最小，可以设计出相应的最佳量化器。•3.5预测编码•目的：去除相邻像素之间的冗余度，减小图像信息在时间上和空间上的相关性来达到数据压缩的目的。•“相邻”，可以指像素与它在同一帧图像内上、下、左、右的像素之间的空间相邻关系；也可以指该像素与相邻的前帧、后帧图像中对应于同一空间位置上的像素(同位像素）之间时间上的相邻关系。具体如下：对于一个图像信源，首先根据某一模型，并利用以往的样值对新样值进行预测，得出预测值，然后将预测值与实际样值相减，得到误差值，最后对误差值进行量化、编码、传输3.5.1差分脉冲编码调制DPCM的简化原理方框图+-编码压缩图像输入图像enxnxn量化器ên预测器++解码预测器解压缩图像压缩图像ynxnên通过预测和差分，将x(n)转化为差分信息e(n),降低了信息冗余•图中预测器的输出：N为预测器所采用的样值数，也称为预测器的阶数。•等于各输入样值的线性组合，本预测器称为线性预测器。•在解码器中有一个相同的预测器，收到的预测误差信号经解量化器DQ以后，与预测其的输出相加，从而恢复出原信号。由于预测误差的量化，解码输出的y(n)是x(n)的近似值。1()()Niixnaxni()xn修正后的预测编码器•在前面的预测器中，编码端利用原始信号为参考进行预测，而在解码端确是利用量化后的信号进行预测，这种不匹配的情况导致重建信号有y(n)与输入信号x(n)之间存在较大误差。修正：编码器反馈环模拟了解码端结构。•增加一个反馈环，将量化误差和过去预测函数相加，作为新的预测函数符号编码压缩图像+-en输入图像xnQ-DQên预测器xn++•xn•^xn=ên+xn•几个概念：•一维预测：被预测的样值与用作预测的样值在同一行内•二维预测：用作预测的样值位于相邻的不同行上一维预测利用像素之间在水平方向上的相关性。在水平方向亮度变化缓慢的图像，有较好的预测效果。•如果水平方向上亮度有突变，那么一阶的一维预测经常会给出错误的预测数值。在这种情况下，采用下面的二维预测，会有较好的预测值。10()xx黑电平451122xxxx图3-14对应于图像黑白边界处的几个像素•N阶预测器的设计问题•在最小均方误差下的最佳预测器。•下式表示预测误差信号e(n)平方值的统计平均。•若上式最小时，表示在最小均方误差意义下，预测最准确，此时色预测器称为在最小均方误差意义下的最佳预测器。•最佳预测器的系数ai可以通过求极小值的方法求得。2221()[()()][()()]Niienxnxnxnaxni211Nkk=1()2()()0(1,2,)()()[()()][()]()()()()0(3.42)R()-a()0(1,2,)iiNkkiNkkeneneniNaaenenxnaxnkxniaxnxniaxnkxniRiRikiN用输入序列的自相关函数表示：如果对所需要压缩的某类图像的自相关函数已经作过测量的话，则可通过求解上式所表示的方程组，获得最佳预测器的系数值。•另一个事实2min12min111()()[()()]()()()()0()()[()()]()()[()()]()(0)()NkkiNkkNkkNkkenenxnaxnkenxnienenaenenxnaxnkenxnxnaxnkxnRaRk而由（3.42）所以•预测误差的平均功率比原信号的功率R(0)要小。在相同的均方量化误差下，e(n)比x(n)要求较少的量化级数，因此，传送e(n)比传送x(n)的数据率要低。•3.5.2序列图像中运动矢量的估值•1.运动矢量估值的必要性•序列图像在时间上的冗余情况可分如下几种：•(1)对于静止不动的场景，当前帧和前一帧的图像内容是完全相同的；•(2)对于运动的物体，只要知道其运动规律，就可以从前一帧图像推算出它在当前帧中的位置；•(3)摄像镜头对着场景横向移动(称为滑镜头)、焦距变化等操作会引起整个图像的平移、放大或缩小。对于这种情况，只要摄像机的运动规律和镜头改变的参数已知，图像随时间所产生的变化也是可以推算出来的。•由电视图像的相关性特点，可知：•发送端不一定必须把每帧图像上所有的像素都传给收端，而只要将物体(或摄像机)的运动信息告知接收端，收端就可根据运动信息和前一帧图像的内容来更新当前帧图像，这比全部传送每帧图像的具体细节所需的数据量要小得多。•首先要做的是从图像序列中提取运动物体的信息－－运动估值。•为了简单起见，做出如下假设：•(1)物体是刚体．只在与摄像机镜头的光轴垂直的平面内移动。即：物体的形变、旋转、镜头焦距的变更等因素不考虑在内；•(2)无论物体移动到任何位置，照明条件都不变，即：同一物体在所有序列图像中亮度没有变化；•(3)被物体遮挡的背景和由于物体移开而新暴露出来的背景部分都未不作特殊考虑。•t时刻运动物体的象素值bt可用它在时间以前的值bt-τ表示：•含义：t时刻的图像是t-τ时刻的图像经适当位移D后的结果。•运动估值的分类：a块匹配方法b像素递归方法()()ttbzbzD•2.块匹配方法•方法描述：•a.将图像划分为许多互不重叠的子块，并认为子块内所有像素的位移量都相同。（每个子块视为一个“运动物体”）•b.寻找匹配块假设在图像序列中，t时刻对应于第k帧图像，t-τ时刻对应于k-1帧图像。对于k帧中的一个子块，在k-1帧中寻找与其最相似的子块，称为匹配块。K-1帧称为K帧的参考帧•c.寻找位移矢量认为匹配块在k-1帧中的位置就是k帧块位移前的位置，根据(3-44)式则可以得到该子块的位移矢量D。•块匹配方法中最重要的问题：(1)判别两个子块匹配的准则；(2)寻找匹配块搜索的方法。准则a:归一化的二维互相关函数（NCCF）•当NCCF为最大值时2个子块匹配，对应的i，j值即构成位移矢量D。11121221211111(,)(,)(,)[(,)][(,)]MNkkmnMNMNkkmnmnbmnbminjNCCFijbmnbminj•准则b•求2帧子块亮度的均方差值MSE：•当MSE最小时．表示2个子块匹配。21111(,)[(,)(,)](,)MNkkmnmmMSEijbmnbminjMNdijd•c.MAD准则•求帧间子块亮度差的绝对值的均值MAD：•当MAD最小时．表示2个子块匹配。1111(,)(,)(,)(,)MNkkmnmmMADijbmnbminjMNdijd•d.计算块亮度差的绝对值和SAD：•SAD(I,j)=MN*MAD(i,j)•当SAD最小时．表示2个子块匹配。•此准则较常使用。•研究结果表明，匹配判别准则的不同对匹配精度，也即是对位移适量估值的精度影响不大。•（2）搜索方法：为了节省计算量，在k-1帧中的匹配搜索只在一定范围内进行。假设在τ时间间隔内最大可能的水平和垂直位移量为dm个像素，则搜索范围SR为•SR＝（M+2dm）*（N+2dm）1)全搜索:寻找最佳的匹配块，需要将k-1帧中对应的子块在整个搜索区内沿水平和垂直方向逐个像素移动，每移动一次计算一次判决函数。总的移动次数Q为•Q＝（2dm+1）2•此种搜索方法运算量非常大。2)块匹配的快速搜索方法：举例：三步法搜索过程：1）以待匹配块中心的同位像素为中心，在中心点和与其距离4个像素的8个邻域上计算判决函数SAD,取SAD最小的点作为下一步搜索的中心2）以该点为中心，对于中心相距2个像素的未搜索过的邻域点进行搜索3）以上一步中SAD最小的点为中心，对距离中心1个像素的未搜索过的邻域点进行搜索，最终找到最佳匹配位置。几乎所有的快速搜索算法都基于如下的假设：当偏离最佳匹配位置时，判决函数（匹配误差）值是单调上升的。因此无需搜索所有点，只要沿着误差值减少的方向进行搜索，就能找到最佳匹配位置。保证任何情况下找到全局极值点是困难的。近几年来人们提出了许多新的快速搜索算法，这些算法的搜索策略概括如下：1）运动矢量预测：根据图像内容的连续性，相邻块的运动矢量一般是相近的。2）搜索提前中止：预先设定匹配误差阈