3.5 预测编码

预测编码根据3.2节中介绍的原理，旨在去除相邻像素之间的冗余度，只对不能预测的信息进行编码。这里说的“相邻”可以指像素与它在同一帧图像内上、下、左、右的像素之间的空间相邻关系，也可以指该像素与相邻的前帧、后帧图像中对应于同一空间位置上的像素之间时间上的相邻关系。其中后者，即相邻帧图像中位于同一坐标位置上的像素，常称为该像素的同位（co-located）像素。人们在几十年之前就认识到，电视图像的相邻帧之间画面内容变化甚小，存在着大量的重复信息；另外，图像亮度、色度的空间分布多是渐变的，同一帧画面内相邻像素之间也存在着重复信息。但是，要降低像素间信息的冗余度，以降低对传输信道容量的要求，则只有在数字电视中才有了实际实现的可能。

3.5.1 差分脉冲编码调制（DPCM）

差分脉冲编码调制简称为DPCM（Differential PCM），它是预测编码的一种基本方式。图3-13为DPCM的原理方框图。

输入信号x（n）是取样后（没有量化以前）的图像信号的样值，虚线方框内的电路称为预测器，其中z－i（i＝1，…，N）为延时单元，其延迟时间为i个取样周期，a1，a2，…，aN为固定的加权系数，其数值在预测器设计中确定。预测器根据前几个邻近样值（数目为N）推算出当前样值的估计值。Q为量化器。发送端只对预测的误差信号[即当前的实际样值x（n）与估计值之差]e（n）进行量化编码、传送，而不是传送x（n）本身。

图3-13中预测器的输出为

式中，N称为预测器的阶数。由于等于各输入样值的线性叠加，该预测器称为线性预测器。

在解码器中有一个相同的预测器，收到的预测误差信号经解量化器DQ以后，与预测器的输出相加，从而恢复出原信号。由于在编码端预测误差信号已被量化，因此在解码端所恢复出的信号y（n）只是原信号x（n）的近似值。

由于电视画面在内容上的连续性，空间域相邻像素之间有很强的相关性，可以利用这些相关性对当前的像素进行预测。这通常称为空间域预测。在解码端，根据前几个样值所得到的预测值已经是已知的，如果当前值x（n）与相同，就不需要再传送新的数据给解码端了。因此，通过预测将x（n）转换成e（n），在很大程度上降低了信息源的冗余度，这便是利用DPCM进行数据压缩的基本原理。

在图3-14中，X表示被预测的像素，x1，x2，…，x5则是根据不同的预测方案有可能被选择用来对X进行预测的已知的像素。如果用作预测的样值与被预测的样值在同一行内（如图中的x1、x2与X），称为一维预测；当用作预测的样值位于相邻的不同行上时（如图中x3、x4与X）则称为二维预测。

一维预测利用了像素之间在水平方向上的相关性。对水平方向亮度变化缓慢的图像，有较好的预测效果。如果水平方向上亮度有突变，例如图3-14所示的图像是以x1和X为界的黑白条，那么一阶的一维预测为

会给出错误的预测数值。在这种情况下，采用下面的二维预测给出较好的预测值，即

下面考虑N阶预测器的设计问题。预测误差信号e（n）平方值的统计平均由下式表示：

式中〈 〉表示均值。显然，〈e2（n）〉最小时，表示在最小均方误差意义下，预测最准确，此时的预测器称为在最小均方误差MMSE（Minimum Mean Square Error）意义下的最佳预测器。最佳预测器的系数ai（i＝1，…，N）可以通过如下求〈e2（n）〉极小值的方法获得：

将上式用输入序列的自相关函数R来表示：

如果对需要压缩的某类图像的自相关函数已经做过测量的话，则可通过求解（3-40）式所表示的方程组，获得最佳预测器的系数值。此时的均方误差值则为

由（3-39）式可知，

于是（3-41）式可简化为

由上式可以看出，预测误差的平均功率比原信号的功率R（0）要小。在相同的均方量化误差下，e（n）比x（n）要求较少的量化级数，因此，传送e（n）比传送x（n）的数据率要低。

在图3-13所示的电路中，量化器处于预测差分环路之外。编码端利用原始信号为参考进行预测，而在解码端却是以量化后的信号为参考进行预测的，这种两端参考信号不相同的情况，称为失配，它导致重建信号y（n）与输入信号x（n）之间存在较大误差。图3-15给出了一个严格意义上的DPCM原理方框图，图中编码器的反馈环路模拟了解码端的结构：量化后的预测误差信号经解量化器后，与预测值相加构成预测器的输入信号，从而使解码端重建信号的误差降低。

3.5.2 序列图像中运动矢量的估值

1.运动矢量估值的必要性

电视图像是由在时间上相互间隔为帧周期（1/25s、或1/30s）的一帧帧图像组成的图像序列。可以想象，在拍摄同一场景时，时间上相邻的两幅图像之间在内容上差异不会太大，或者说后一帧的内容与前一帧重复的部分很多。用数学的术语来讲，二者是相关的。消除序列图像在时间上的相关性（冗余度），是视频信号压缩编码的一条重要途径。

序列图像在时间上的冗余情况可分为如下几种：①对于静止不动的场景，当前帧和前一帧的图像内容是完全相同的；②对于运动的物体，只要知道其运动规律，就可以从前一帧图像推算出它在当前帧中的位置来；③摄像镜头对着场景进行横向移动（称为滑镜头）、焦距变化等操作会引起整个图像的平移、放大或缩小，对于这种情况，只要摄像机的运动规律和镜头改变的参数已知，图像随时间所产生的变化也是可以推算出来的。由电视图像的这些特点我们可以想到，发送端不一定必须把每帧图像上所有的像素都传给接收端，而只要将物体（或摄像机）的运动信息告知收端，收端就可根据运动信息和前一帧图像的内容来更新当前帧图像，这比全部传送每帧图像的具体细节所需的数据量小得多。

要这样做，一个首先需要解决的问题是如何从序列图像中提取出有关物体运动的信息，这通常称为运动估值。本节讨论的内容就是运动估值的方法。摄像机的运动和参数变化影响到图像的每个像素，我们将这种由摄像机运动导致的像素位置变化称为全局运动。本节将不涉及全局运动估值问题，有兴趣的读者可以参考其他文献。

为了简单起见，本节介绍的物体运动估值方法基于如下的假设：

（1）物体是刚体，且只在与摄像机镜头的光轴（即穿过镜头球面中心和球心的轴）垂直的平面内移动。这就是说，物体的形变、旋转、镜头焦距的变更等因素不考虑在内；

（2）无论物体移动到任何位置，照明条件都不变，也就是说，同一物体在所有序列图像中亮度没有变化；

（3）被物体遮挡的背景和由于物体移开而新暴露出来的背景部分不做特殊考虑。在上述假设下，t时刻运动物体的像素bt可以用它在时间τ以前的值bt－τ表示出来，即

bt（z）＝bt－τ（z－D）　（3-44）

式中，b代表像素亮度值；z＝（x，y）T为位置矢量，T代表矢量的转置；D为在时间间隔τ内物体运动的位移矢量（Displacement Vector）。严格地讲，位移矢量与运动矢量（Motion Vector，MV），在概念上是有区别的，因为位移只是物体运动的一种方式，但由于在当前技术条件下，位移几乎是进行视频数据压缩时所考虑的唯一运动方式，因此在相关的文献中，常将D称为运动矢量。上式表示t时刻的图像是（t－τ）时刻的图像经适当移位后的结果。因此通过比较相距时间为τ的两帧图像可以估计出在这段时间间隔内物体的位移D。根据这一公式进行运动估值的方法主要分为两大类，分别称为块匹配方法和像素递归方法。由于块匹配方法是目前视频压缩编码广泛采用的方法，因此本节仅针对它进行讨论。

2.块匹配方法

按照一般的想法，运动估值应当首先将图像中的静止背景和运动物体区分开来，然后对运动物体的实际位移进行估值，但是从图像中分割出物体常常是一个困难的任务。为了回避这个困难，在块匹配方法中，将图像划分为许多互不重叠的块（如16×16），并假设块内所有像素的位移量都相同。这实际上意味着将每个块视为一个“运动物体”。假设在图像序列中，t时刻对应于第k帧图像，t－τ时刻对应于k－1帧图像。对于k帧中的一个块，在k－1帧中找与其最相似的块，称为匹配块，并认为该匹配块在k－1帧中的位置，就是k帧块位移前的位置，根据（3-44）式则可以得到该块的位移矢量D。此时，k－1帧称为k帧的参考帧。

为了节省计算量，在k－1帧中的匹配搜索只在一定范围内进行。假设在τ时间间隔内块的最大可能水平和垂直位移量为dm个像素，则搜索范围SR为

SR＝（M＋2dm）×（N＋2dm）　（3-45）

式中，M、N分别为块在水平和垂直方向上的像素数。图3-16给出了块与搜索范围的相对位置关系。显然，在块匹配方法中最重要的两个问题是：判别两个块匹配的准则和寻找匹配块的搜索方法。

对这两个问题的不同解决方案构成了不同的算法。

判断两个块相似程度的最直接的准则是归一化的二维互相关函数NCCF，其定义为

式中的时间和位置已用相应的离散量表示，分子为在第k帧中的块与在k－1帧中与该块对应位置相差i行、j列的块之间的互相关函数，分母中括号里的项分别代表这两个块各自的自相关函数的峰值。当NCCF为最大值时两个块匹配，此时对应的i、j值即构成位移矢量D。

在实际应用中，常常使用如下计算比较简单的判断块匹配的准则：

（1）块亮度的均方差值（MSE）

（2）块亮度差的绝对值均值（MAD）

（3）块亮度差的绝对值和（SAD）

SAD（i，j）＝MN·MAD（i，j） （3-49）

当MSE或MAD或SAD最小时，表示两个块匹配。

研究结果表明，匹配判别准则的不同对匹配的精度，也就是对位移矢量估值的精度影响不大。因此，（3-49）式所表示的不含有乘法和除法的SAD准则成为最常使用的匹配判别准则。

为了寻找最佳的匹配块，我们需要将k－1帧中对应的块在整个搜索区内沿水平和垂直方向逐个像素移动，每移动一次计算一次判决函数（如SAD）。总的移动次数（搜索点）Q为

Q＝（2dm＋1）2 （3-50）

这种搜索方式称为全搜索。全搜索的运算量是相当大的。使用SAD为准则时每个像素要进行三个基本运算（相减、求绝对值、求和），对一个块进行全搜索要求3×（2dm＋1）2×MN次运算。假设视频图像的分辨率为NW×NH，则每帧有（NW×NH）/MN个块，即使在dm＝7、[NW，NH]＝[352，288]和帧率f＝30时，所需的运算量也达到2.05千万次/秒。一般来说，运动估值的运算量通常占到现行标准下视频压缩编码的60%～80%。

3.块匹配的快速搜索方法

为了加快搜索过程，人们提出了许多不同的搜索方法。图3-17所示的三步法是早期提出的一个典型快速搜索算法。它通过降低搜索点的数目来降低算法的计算复杂度。其搜索过程为：第一步，以待匹配块中心的同位像素（即前一帧中与之位置相同的像素）为中心，在中心点和与其相距4个像素的8个邻域点上计算判决函数SAD值，取SAD值最小的点作为下一步搜索的中心；第二步，以该点为中心，对与中心相距2个像素的未搜索过的邻域点进行搜索；第三步，以上一步中SAD值最小的点为中心，对距离中心1个像素的未搜索过的邻域点进行搜索，最终找到最佳匹配位置。图中带有数字的圆圈代表每一步骤中的搜索点，带有数字的方块代表该步骤中SAD值最小的位置。本例中，在dm≤7的搜索范围内，通过三步找到最佳匹配位置（i＋7，j－2）。早期提出的其他算法，如二维对数法、共轭方向法等，与三步法相类似，只是每个步骤搜索点所构成的图形的形状和大小不同。

几乎所有的快速搜索算法都基于如下的假设：当偏离最佳匹配位置（运动矢量D＝Dopt）时，判决函数（匹配误差）值是单调上升的。因此无需搜索所有的点，只要沿着误差值减少的方向进行搜索，就能找到最佳匹配位置。图3-18给出了一维情况下沿误差曲线搜索的情况（如图实线上箭头所示）。但是当误差曲线非凸时（如图中虚线示），这种搜索方法则可能落入局部极值点，例如从图中A点左侧任意点沿误差减小方向的搜索将中止于A点，而不能搜索到最佳匹配位置（全局极小点）。

保证在任何情况下找到全局极值点是一个困难的问题，但是从另一个角度来考虑，在全局极值点的邻近区域，误差曲线（二维时为曲面）为凸的假设总是成立的，因此只要有一个搜索点落在全局极值点的附近，搜索到最佳匹配位置的概率就会很大。

根据上述想法，近年来人们提出了许多新的快速搜索算法，具有代表性的有MVFAST，APDZS和EPZS等，它们不仅大大提高了搜索的速度，而且具有与全搜索方法相当的性能。这些算法的基本策略可以概括如下。

（1）运动矢量预测

由于图像内容的连续性，相邻块的运动矢量一般是相近的，换句话说，运动矢量场（运动矢量的分布函数）在空间和时间上一般是平滑、渐变的，因此，我们可以根据已进行过运动估值的相邻块的运动矢量（假设它们的估值是正确的），对当前待匹配块的运动矢量进行预测，然后从预测位置开始进行搜索。如果预测得足够准确，那么预测点落在误差曲线的全局极值点附近，这不仅能够缩短搜索需要的时间，而且使搜索到全局极值点的概率增高。

在图3-19中，设k帧中灰色块为当前待匹配的块，它的MV的预测值可以选择为：（0，0），或当前块的左、上和右上三个空间邻域块的运动矢量MVL，MVT和MVTR，也可以选择为这三个MV的中值MVmed，或前一帧同位块的运动矢量MVC。其他预测值还可以考虑：前一帧同位块的上、下、左、右4个邻域块的MV、前2帧的“加速度”MV＝MVC＋（MVC－MVC2）（见图3-19），以及上述各预测值的线性组合等。我们将各个MV预测值所确定的一组点作为搜索的候选起始点，计算它们的SAD值，并选择SAD值最小的点作为最佳起始点；然后以该点为中心类似于三步法那样，计算规定的搜索图形上各搜索点的SAD值，并按SAD值减小的方向移动搜索图形，直至找到最佳匹配位置为止。由于搜索采用了多个候选起始点，所以使得因MV预测不准确而引起的起始点远离全局极值点的风险降低。

（2）搜索提前中止

所谓“提前中止”是指，在某个搜索点上如果匹配误差SAD小于预先设定的阈值T，则认为匹配已经足够好，搜索中止。人们通过研究发现，大多数图像块的运动矢量与空间邻块运动矢量的中值MVmed相关性最强，与（0，0）、MVL、MVT、MVTR和MVC的相关性次之，与其他MV预测值的相关性则小一些。显然，先搜索相关性强的预测点，可能较早满足提前中止的条件，从而提高搜索效率。

提前中止阈值T的选取是一个值得考虑的问题，阈值过小达不到提前中止的目的；过大则搜索不到最佳匹配位置。一般来说，针对不同情况可以设置不同的阈值，例如对相关性强的点，阈值严格一些，对相关性弱的点则宽松一些。除了固定阈值之外，还可以动态地选取阈值。考虑到待匹配块的SAD值与它的空间邻域（左、上和上右）和时间邻域（同位）块的SAD值之间也存在着相关性，一种动态阈值的选择方法为

T＝a·min（SADL，SADT，SADTR，SADc）＋b （3-51）

式中，a、b为预定的常数。

（3）紧凑的搜索图形

在三步法中，为了提高搜索速度，在开始时采用了大尺寸（隔4个像素）的矩形搜索图形；在搜索趋向于匹配点的过程中，搜索图形的尺寸逐步减小。由于近年提出的快速算法都进行了不同程度的运动矢量预测，搜索的起始点已经接近于匹配点，因此可以采用紧凑的搜索图形。图3-20给出了几个例子，其中（a）称为“大钻石”，在距离匹配点稍远处使用；（b）为“小钻石”，在匹配点附近使用。判断当前搜索点距离匹配点的远近可以有多种准则，一种常用的办法是检查搜索点SAD值的大小。SAD值小意味着接近匹配点，可以使用小尺寸图形。

上述三种基本策略的不同运用形成了不同的算法。图3-21给出了一个搜索过程的示例，其中带有数字的圆圈代表每一个步骤的搜索点，带有数字的方块代表该步骤中的SAD值最小的位置（见习题9）。搜索图形为小钻石。

3.5.3 具有运动补偿的帧间预测

1.前向预测

与消除图像中相邻像素间的空间冗余度一样，消除序列图像在时间上的相关性，也可以采用预测编码的办法，即不直接传送当前帧（即k帧）的像素值x[见图3-22（a）]，而传送x与前一帧（即k－1帧）同位像素x′之间的差值，这称为帧间预测。对隔行扫描的电视信号，也可以用前一场来预测当前场的像素（场间预测）。当图像中存在着运动物体时，简单的预测不能收到好的效果。例如图3-22（b）中，当前帧与前一帧的背景完全一样，只是小球平移了一个位置。如果简单地以k－1帧的同位像素值作为k帧像素的预测值，则在实线和虚线所示的圆内预测误差都不为零。如果已经知道了小球的位移矢量，可以从小球在k－1帧的位置推算出它在k帧中的位置来，而背景图像（不考虑被遮挡的部分）仍以前一帧的背景代替。将这种考虑了小球位移的k－1帧图像作为k帧的预测值，就比简单的预测准确得多，从而可以达到更高的数据压缩比。这种预测方法称为具有运动补偿的帧间预测。

从原理上讲，具有运动补偿的帧间预测应包括如下几个基本步骤：

（1）将图像分割成静止的背景和若干运动的物体，各个物体可能有不同的位移，但构成同一物体的所有像素的位移相同。通过运动估值得到每个物体的位移矢量；

（2）利用位移矢量计算经运动补偿后的预测值；

（3）除了对预测误差进行编码、传送以外，还需要传送位移矢量以及如何进行运动物体和静止背景分割等方面的附加信息。

图3-23给出了这种预测器的原理方框图。图中向下的虚线箭头标出分割的结果送进运动估值单元，以便针对不同物体进行位移估值。而向上的虚线箭头表示用估值的结果和分割的结果一起去控制预测器，以得到经运动补偿后的预测图像。编码器的最终输出为帧间预测误差、位移矢量和分割产生的地址信息等。

如前所述，将图像分割成静止区域和不同的运动区域是一项困难的工作，当要求实时地完成这项运算时就更加困难。一种简化的办法是将图像分割成块，每块看成是一个物体，按3.5.2节中讲的块匹配的方法估计每个块的位移矢量，将经过位移补偿的帧间预测误差（Displaced Frame Difference，DFD）和位移矢量D传送给接收端，接收端就可以按下式从已经收到的前一帧信息中恢复出该块：

bk（z）＝bk－1（z－D）＋DFD（z，D）　（3-52）

图3-24中表示出了k帧各块及它们在k－1帧中对应的匹配块之间的关系。从该块的预测误差和它的位移矢量所指向的k－1帧中的匹配块，可以恢复出k帧中的块来。显然，当一个块中的像素实际上属于位移量不同的物体时，这种对整个块用同一位移作的预测则不够准确，这将使预测误差DFD增加，从而影响数据压缩比的提高。

2.后向预测和双向预测

上面介绍的用k－1帧预测k帧图像的预测方式称为前向预测。如果待预测的块是在k帧，而搜索区域处于k＋1帧之内，也就是从后续的k＋1帧图像预测前面的k帧图像，这种方式称为后向预测。对于在k－1帧中被覆盖，而从k帧开始新暴露出的物体（或背景），使用后向预测可以得到更好的预测值。

第三种预测方式是采用前、后两帧来预测中间帧，这称为双向预测。如图3-25所示，对于k帧中的块（灰色块），先从k－1帧中找到它的最佳匹配块，从而得到该块从k－1到k帧的位移矢量D1，再利用后向预测得到它从k＋1到k帧的位移矢量D2，然后将经过运动补偿的前向预测值或后向预测值，或二者平均值作为k帧块的预测值（视哪种预测误差最小而定）。这样的做法与单纯的前向预测相比，可以进一步降低预测误差，从而提高数据压缩比。

双向预测所付出的代价是，对每一个图像块需要传送两个位移矢量给接收端，而且k帧的恢复必须等到k＋1帧解码之后才能进行。也就是说，输入序列的帧顺序是k－1、k、k＋1，编码和解码运算的帧顺序是k－1、k＋1、k，而图像显示的顺序又是k－1、k、k＋1。要保持处理和显示的连续性，在编码端和解码端分别需要引入一帧的延时。