3.4 序列图像中运动矢量的估计在线视频

这一节我们学习序列图像中

运动矢量的估计

视频信息是由时间上

相隔帧周期的一帧帧图像序列组成

那么帧周期

可以是25分之1秒

或者是30分之1秒

那么在序列图像之间

具有很强的相关性

那么我们可以看下面的这一些系列图

那么我们在对这样子的视频信息进行

编码传输的时候

如果前一帧的内容传输过去之后

后续的内容如果我们知道

它里面运动物体的一些运动特征的话

那么其实我们不需要把

所有后续帧的信息都传过去

那么我们只要把在后续帧中

物体的运动特性告知接收端

那么接收端就可以根据

已经接收到的前一些帧的内容

同时结合后续帧中物体的运动特性

把后续帧还原出来

那么如果是这样子的话

我们的传输的数据率就可以降低很多

想要实现这样子的一个结果

那么我们就要对于序列中

物体的运动特性做一个估计

也就是说我们要从序列图像中

提取有关物体的运动的相关信息

那么这就是我们这一节要讨论的问题

就是运动估计的问题

那么运动估计要想很容易的实现

我们需要做一些前提假设

那么我们来看一下

我们做运动估计的时候

需要假设一些什么样子的前提条件

首先我们假设物体是刚体

并且物体的运动只在于

摄像机轴垂直的平面内进行

也就是说物体只在

这个图像平面中做平移运动

这样我们最对于物体的这个运动特性

就可以只用它在

XY方向上的坐标值来描述

再有一个重要的假设是

物体在任何位置上的照明条件

假设是恒定不变的

这就是我们通常所说的恒亮度假设

也就是说

在一个拍摄环境中亮度是不改变的

这样就能保证在相应的

序列图像中相同的物体

它的亮度值是一致的

那么我们就可以根据

这样子的一致性来判定

这个物体在不同帧中的具体位置

那么同时我们假设

物体移动所造成的背景被遮挡

以及背景重新露出这种情况

我们不做考虑

那么在这一系列的前提假设下

我们后续给出运动估计的相应的方法

运动估计主要可以分成两大类

一类是基于特征的方法

一类是基于亮度的方法

那基于特征的方法主要用于目标跟踪

通过二维进行三维重建

那么基于亮度的方法呢

是我们用的比较多的一种方法

用来进行带运动补偿的帧间预测

那么在我们的视频编码中

大多数用的都是基于

亮度的运动估计的方法

那么对于

序列图像中进行运动矢量的估计

需要考虑三个重要的问题

第一个问题就是

如何进行运动场的表述

或者说如何描述运动场

第二个需要解决的问题是

用什么样的标准来

进行运动矢量的估计

或者运动参数的估计

再有就是如何去搜索运动参数

我们下面就对这三个问题进行分别的阐述

我们先来看一下运动场的表示

运动场的表示方式通常有四种

第一种就是基于块的运动场的表示

那么它是对于

基于区域的运动场表示一种简化方式

那我们先来看

基于区域的运动场的表示

这种运动场的表示方法

首先需要对图像中

运动区域和

背景禁止区域进行一个划分

也就是说要区分出

或者叫识别出运动区

以及后面不动的背景静态区域

在这个划分的基础上

为每一个运动的物体

估计出它的运动矢量或者是运动参数

那么

对于图像中的物体的划分

或者说物体区域的识别

并不是一件容易的事情

那么为了简化这样一个实现的过程

就有了基于块的运动场的描述方式

也就是我们把图像画分成

不重叠的一个一个图像块

那么我们就认为每一个图像块

对应着一个运动物体

这样我们为每一个块

估计出相应的运动参数

这就是基于块的运动场的表示

那么这种基于块的运动场的表示是

我们后续相应运动估计方法的一个

运动场的表示基础

除了这两种运动场的表示之外

还有基于像素的运动场的表示

也就是说

我们对于图像中的每一个像素点

都给出它对应的运动参数的估计

那么这是早期的一种运动场的表示方式

那么如果我们的运动是来自于

像摄像机的焦距的变化

或者说镜头的窑变

这类能够使所有场景中物体

都产生运动的这种全局运动的话

那么我们就可以用

全局运动的这个运动场来描述运动

那么我们再来看一下第二个问题

就是运动估计的准则问题

运动估计基于的准则有很多

我们这个地方主要列出三个准则

一个是基于位移帧差的准则

也叫DFD准则

那么我们在进行运动估计的时候

是通过使这个帧间的位移差最小

来获得最佳的运动矢量估计

也就是说

找到能够使这个DFD

这个位移帧差最小的那一组运动矢量

那么就是我们进行运动估计的结果

在这个表达式中

P等于1对应的是MAD的这个准则

也就是说平均绝对差的和

当p=2的时候

对应的就是我们通常所说的均方误差

那也就是说

我们在进行运动估计的时候

可以通过使均方误差最小来找到

最合理的或者最准确的

运动参数的估计结果

第二层常用的运动估计的准则

是基于光流方程的准则

那么这个准则是在光流方程的基础上

得到对应的代价函数

那么能够使这个代价函数

最小的运动矢量值就是我们

估计的运动矢量的结果

第三个运动估计的准则是贝叶斯准则

贝叶斯准则主要就是最大化后验概率

在相邻帧已知的情况下

通过最大化后验概率

来寻找我们的运动矢量

我们来看二维运动估计

我们的这个运动估计的方法是

基于亮度实现的

那么二维运动估计的主要方法有

基于块的运动估计

也就是块匹配法

我们后面会重点讨论

有基于像素的运动估计

像素递归法

这是早期的二维运动估计的方法

再有就是基于光流的运动估计

叫光流法

我们来看基于块的运动估计的方法

在这样子的一个

基于块的运动估计方法中

我们首先假设

图像被划分成互不重叠的块

也就是说

这种运动估计的方法是

基于块的运动场的描述来实现的

图像被划分成互不重叠的块

那么块中所有的像素

我们认为它经历了完全一样的运动

并且我们在运动估计的时候是对

每一块单独来进行运动参数的估计

那么在这样子的一个假设下

所实现的二维运动估计

它会产生一系列相应的问题

那么这也是我们基于这个方法

进行运动估计所需要解决的问题

因为所有的块单独进行运动

矢量运动参数的估计

对于一个物体如果被划分为

多个不同的块

那么块和块之间的运动

矢量的差别就会造成

最终我们运动矢量估计得一个误差

在这个假设下我们来看一下

运动估计的重要方法就是块匹配算法

块匹配算法是假设图像块只做平移运动

这样我们为每一个块

估计出一组运动参数

那么这一组运动参数就是由XY

两个方向上的位移量来表示的

我们又把这个运动参数叫运动矢量

或者叫位移矢量

典型的块匹配算法有穷尽块匹配算法

简称EBMA算法

还有快速搜索的块匹配算法

那么块匹配算法

是假设图像块只做简单的平移运动

所以说如果图像中

运动物体的运动比较复杂

比方说是出现

仿射性运动或者双线性运动的话

那么块匹配算法不能够很好的对

这些运动进行一个描述

在这个基础上

就有了可变形的块匹配的算法

可变形块匹配算法允许更复杂的运动

包括仿射性运动 双线性运动

这种匹配算法是对

简单的块匹配算法的一种改进

那么下面我们来看一下运动估计的

块匹配算法也就是BMA算法

块匹配指的是我们在

k当前帧的这个第k帧之前

来寻找跟当前第k帧中

某一块最相似的那个块

也就是说

我们为第k帧中某一个块

在它相邻的第k-1帧

或者说第k+1帧

在这相应的相邻帧中

找到跟它最相似的块

这样子的一个块

我们把它叫做是匹配块

也就是说

跟当前帧相邻的帧中

跟当前帧中这个块

最相似的那个图像块

块匹配的算法就是基于在相邻帧中

找到当前帧最相似的块来判定

当前这帧中某一块

它在两帧之间运动参数是怎样的

有了这样子的一个运动矢量

那么我们就可以

对于当前第k帧中

某一个区域或者叫某一个块上的像素

用它相应的参考帧中的

对应像素来进行一个表述

那么在这儿

bt(z)表示的是当前第k帧

z这个位置上的像素

那么它跟时间上在它前面t-τ时刻

也就是说

第前面第k-1帧中位置是z-D的

这个位置的这个像素是相同的

也就是说

当前帧中图像块里的像素可以用它前面一帧

考虑了运动估计参数

考虑了运动矢量之后的

那个像素之间是一个相等的关系

在这个表达式中

z代表的是位置矢量

D就是我们的位移矢量

那我们进行运动估计要估计的就是这个D

那么具体运动估计的块匹配算法

需要首先把图像能进行一个块的划分

假设每一个块中像素具有相同的位移

所以我们对每一个划分出来的图像块

通过运动估计

得到一个相应的运动参数

那么在进行运动估计的时候

我们要确定

搜索匹配块的搜索区域

假设在图像中我们认为

运动物体的这个运动距离是有限的

也就是说相邻两帧之间

物体的运动不会有太大的位移

那么我们假设

它在X和Y方向上的位移

最大值用dmax来表示

这样我们就可以对于

M·N大小的块来进行

搜索的时候的搜索区域是

(M+2dmax)·(N+2dmax)

也就是我们对于当前第k帧中的

某一个M·N的图像块在它的参考帧

假设这个参考帧是它前面的

相邻帧第k-1帧

那么在参考帧中的

虚线所包围的这个区里头

进行匹配块的搜索

那么在这样一个块匹配法中

我们需要解决两个重要的问题

一个是判断匹配的准则

也就是说怎么样

才算是两个块之间是匹配的

我们要给出判定匹配的匹配准则

在有要解决搜索匹配块的搜索方法

也就是说怎么样能够在搜索区域内

快速地找到跟这个

当前图像中的这个块匹配的匹配块

那么根据解决这两个

问题的这个方法不一样

我们就有相应的不同的

这个块匹配的算法

判断两个块相似程度最直接的方法

那就是计算规划的二维互相关函数

那么通过互相关函数的

大小来确定这两个块的相似度

那么在这样子的一个概念的基础下

不同的解决方案

那么就构成了不同的运动估计的

运动估计算法

我们来看一下匹配准则

那么我们以

均方差或者是绝对误差的和

也就是说以MSE MAD SAD

为准则 也就是当MSE

或者MAD SAD最小的时候

我们认为两个块是匹配的

那么具体的这个误差表达式

我们给出来了均方差的表达式

平均绝对差的表达式以及

平均绝对差的和的表达式

那么我们在实际中用的比较多的是

SAD的这个匹配准则

因为在这个准则的计算式子里头

没有除法也没有乘法

运算起来比较简洁

那么在这样一个准则下

我们要在搜索区域里头搜索匹配块

那么搜索的方式就

决定了我们的运算量的大小

最简单的也是最优的一种

这个搜索方式是全搜索

也就是在我们所限定的

这个搜索区域内每位移一个像素

做一次匹配计算也就是

计算一下对应的这个误差

基于误差的大小来确定

这个位置是不是最佳的匹配位置

那么在全搜索的这种搜索方法下

我们一定能够获得最佳的匹配位置

也就是说能够获得最优的结果

但是这种方法的运算量非常的大

那么根据我们刚才所设定的

这个搜索区域

在这个搜索区域里头进行全搜索

需要的总的位移数量

那么是(2dm+1)的平方

那么每移动一次

要做一次这个误差的计算

所以说这个运算量非常非常的大

那么因为这种搜索运算量很大

所以就有了一系列的研究

那么针对的就是

怎么样能够减小运算量

快速的找到匹配位置就有了一系列的

这个快速的搜索的算法

那我们看到

全搜索所需要的运算量非常大

虽然能够一定得到最佳的匹配位置

但是这个运算量经常在

实际应用中是没有办法承受

为了减小运算量

就需要找到更有效的快速匹配的算法

那么人们研究了

一系列的快速搜索匹配块的算法

最典型的快速算法就是三步法

那我们简单看一下

三步法实现的基本的原理

快速搜索的方法目标就是减小

搜索计算的步减小计算的运算量

三步法通过合理的搜索点的设计

能够使搜索点的数量减小到

只有25个

搜索步步骤只包含三步

三步法具体的实现方法是以

当前所要搜索匹配块的中心

在参考图像中

相同的位置以这个位置为中心

上下相距四个像素点构成的一个

九个点的位置上来进行

匹配误差的计算

也就是说

在这相应的九个点的位置上进行一个

亮度差的一个误差计算

那么在这个图中我们看到标号为1的

这些位置上对应的就是我们

第一步需要计算

匹配块之间的亮度差的这个计算位置

根据这位置上计算的误差值

我们选择能够获得最小误差的这个点

作为下一步进行搜索计算的起始点

在这个图中我们看到标红的1号

就是我们在第一步计算中获得的

一个能够使误差最小的一个位置点

那么在第二步计算中

以第一步得到的这个点为中心

上下各两个像素的位置

构成了我们第二步搜索的

需要计算的这个像素位置

那么经过这些位置点上误差的计算

得到最小误差的那个点

就是我们途中标红的那个2号点

它是我们第二步搜索的一个

最佳的一个匹配位置

那么以这一个点为中心

上下各相邻一个像素

那么对应就是标3的这些位置点上

再进行第三次的误差计算

那么能够得到最小误差的这个点

也就是我们现在标红的这个3号点

就是我们最终的最佳匹配位置

那么在我们这个图示中

这个最佳匹配位置的

这个具体的这个位移矢量

我们看一下

它相对于原始的这个中心点的位置

水平方向上有7个点的位移

垂直方向上有2个点的位移

那么这样我们就得到了位移矢量

那么跟三步法类似的快速搜索方法

由二维对数法和共轭方向法

那么这些方法的差别就在于

它们所搜索的这个点数不一样

以及所形成的这个图形有区别

但是最终的目的就是为了

能够在减小搜索的步骤的前提下

能够尽量准确的

找到这个最佳的匹配位置

快速搜索的方法

其实实质上就是我们要沿着

判决函数减小

也就是说误差减小这个方向

去寻找最佳的匹配位置

那么如果这个判决函数

是一个单调的函数的话

比方说单调下凸的函数

那么我们沿着判决函数减小的这个方向

一定能找到最佳的平衡位置

但是如果

这个判决函数是一个非凸的函数

那么我们有可能找到的

就不是最佳的匹配点

而是一个次优点

所以说判决函数如果是凸函数的话

我们沿着误差减小的方向

就一定能找到最佳的匹配位置

那么如果判决函数为非凸的时候

搜索有可能落入非极值点

所以说一些新的快速搜索方法的

基本思想就是

在全局极值点的附近区域开始搜索

这样一系列的方法是

基于这样一个假设就是

误差函数曲线在极值点附近

一般可以认为是凸函数

在这样一个假设下

只要有一个

搜索点落入全局极值点的附近

那么最终搜索得到最佳匹配

位置的概率就会大大地提升

所以说很多快速的算法

就是在这样一个思想的指导下

通过多个搜索点

最终找到最佳的匹配点

或者说大概率地获得最佳匹配位置

这些快速的搜索方法

我们可以做一个概括的介绍

一种改进的方法

就是运动矢量预测的方法

那么这种方法通过运动矢量估计

来得到搜索到候选起始点

那么视频图像序列的

运动一般是连贯的

相邻帧之间物体的运动

具有很大的相似性

所以通过运动矢量的估计

运动矢量的预测

我们可以为当前块的搜索

给出一个大致的一个搜索方向

也就是说基于相邻帧的

这些块的运动矢量来大致地给出

当前需要搜索运动矢量的这个块的

一个可能的一个运动矢量的一个值

那么以这样子的一个预测的

运动矢量值作为起始来进行匹配搜索

那么这样子

最终搜索到最佳匹配点的概率就会提升

那么运动矢量的估计可以有多种方式

可以是以相同帧已经

估计出运动矢量的这些块的运动矢量

作为当前这个块的预测值

也可以是以它前一帧

同位的块的运动矢量作为它的预测区

就是我们图中所标出的

以粉色块作为

当前要进行运动估计的这个块的

这个运动矢量预测的基础

那么也可以用多帧来进行一个

运动矢量的一个速度变化考量

然后基于这样一个加速度

来进行当前块的运动矢量的预测

根据预测的结果来决定搜索的起始点

搜索方法改进的

第二个方面是搜索提前终止

也就是我们在进行匹配计算的时候

在匹配误差SAD小于某一个值的时候

我们认为匹配足够好了

就可以停止搜索

这也是我们加快

搜索的一种有效的方式

那么在这样子的一个搜索方法里

停止搜索的阈值T

如何设置非常重要

那么阈值T的设置可以根据

当前块与它空间相邻的这些块

或者跟它同位的块的相关性的不同

来分别设置不同强度的终止

一直跟当前需要搜索的这个块

空间相邻的块以及同位块

它们之间的相关性是不同的

相关性越强

那么我们可以设置更高的这个阈值

相关性如果弱的话

那么我们的阈值可以设置小一点

通过不同阈值的设置

那么我们能够使这个最终的

匹配计算得到的位置

相对更准确

也就是说

更容易搜索到最佳的匹配位置

那么这个阈值的设计

也可以是动态地进行

我们可以根据已经运动估计完成的

上下或者是前一帧的这些匹配块的

匹配误差结果来确定终止的这个阈值

那么这样子的一种阈值设定

是属于动态的阈值设定

无论是哪一种阈值设定

我们的目标是为了

使搜索的这个速度能够提升

减小搜索运算的运算量

搜索方法改进的另外一种方式

是搜索图形的设定

在运动矢量预测的基础上

搜索图形的尺寸是可以减小的

形成更紧凑的图形

这样我们可以根据

运动物体的运动大小

来选择合适的搜索的图形

根据块匹配误差SAD值的大小

我们来判定

离匹配点的远近

那么如果SAD比较大

说明离匹配点比较远

那么我们可以选择大一点的搜索图形

如果SAD值比较小

说明离匹配点的位置比较近

那么我们可以选择小的搜索图形

常用的搜索图形有钻石型

正方形 对角线型和扫描栅格型

前两个搜索图形主要用于

离匹配点比较近的

匹配位置的这个搜索

后两个

常用于离匹配位置点比较远的搜索图形

那么在具体搜索过程中

可以根据离这个匹配位置的远近

调整这些搜索的图形

设定这些搜索图形

其实就是为了尽可能少地

进行这个点的计算

通过这些方式来减小

匹配搜索的运算量