第三章二维运动估计之一

1、第三章二维运动估计之一第三章二维运动估计之一 第三章第三章 二维运动估计二维运动估计 第三章二维运动估计之一第三章二维运动估计之一 运动估计涉及运动估计涉及: 图像平面运动图像平面运动(二维运动二维运动) 和空间物体运动和空间物体运动(三维运动三维运动),运运 动分析与估计是数字视频处理的基本问题之一动分析与估计是数字视频处理的基本问题之一, 也是数字视频处理的难也是数字视频处理的难 点和热点。点和热点。 运动分析与估计广泛应用于计算机视觉、目标跟踪、工业监视和视频运动分析与估计广泛应用于计算机视觉、目标跟踪、工业监视和视频 压缩等场合压缩等场合 不同应用场合对运动估计要求不同，有如下区分：不

2、同应用场合对运动估计要求不同，有如下区分： 真实运动估计：要求估计获得的物体运动和实际运动基本真实运动估计：要求估计获得的物体运动和实际运动基本 一致。如计算机视觉、目标跟踪、工业监视。一致。如计算机视觉、目标跟踪、工业监视。 非真实运动估计：在不被察觉的情况下允许有估计误差，非真实运动估计：在不被察觉的情况下允许有估计误差， 从而最大限度降低信息量和传输带宽。如广播电视中的视从而最大限度降低信息量和传输带宽。如广播电视中的视 频压缩。频压缩。 第三章二维运动估计之一第三章二维运动估计之一 几个基本概念几个基本概念 1.时间序列图像：随时间而变化的一系列图像称为时间序列图像或运动时间序列图像：

3、随时间而变化的一系列图像称为时间序列图像或运动 图像。图像。 2.运动物体特征：指物体形状或表面特征，如尖锐点、边缘线等。运动物体特征：指物体形状或表面特征，如尖锐点、边缘线等。 可以通过运动物体的特征来观察分析物体的运动。可以通过运动物体的特征来观察分析物体的运动。 3.运动估计的基本问题运动估计的基本问题 运动估计研究的是视频序列图像中投影坐标在像平面上的变化，获取运动估计研究的是视频序列图像中投影坐标在像平面上的变化，获取 运动参数，但是投影会造成信息丢失（不可逆），导致估计误差。运动参数，但是投影会造成信息丢失（不可逆），导致估计误差。 第三章二维运动估计之一第三章二维运动估计之一 特

4、征对应：运动物体上的特征与其在二维平面上的投影坐标的对应关特征对应：运动物体上的特征与其在二维平面上的投影坐标的对应关 系。见下图示：系。见下图示： 设t1t2时，物体由P运动至P，即： 空空 间间：P(X,Y,Z) P(X,Y,Z) 像平面像平面： p(x,y) p(x,y) 二维位移（x, y ）称为二维运动矢 量，标记为d(x,t1;t2)。 对于一组点，二维空间位移记为 d(xi,t1;t2),i=1,2,。 第三章二维运动估计之一第三章二维运动估计之一 运动估计的基本问题基本问题 是估计运动前后相邻 两帧图像上对应点的 坐标pi(xi,yi)和pi (xi,yi)， i=1,2,3。

5、即像平面 上对应的二维运动矢 量di(xi,t1;t2)。 第三章二维运动估计之一第三章二维运动估计之一 4.运动分析方法：主要有两种运动分析方法：主要有两种 .根据时间相邻的两幅或多幅图像求解物体的运动参数和三维结构信息。根据时间相邻的两幅或多幅图像求解物体的运动参数和三维结构信息。 图像序列的光流分析法。图像序列的光流分析法。 运动信息包括：物体的一阶（位移）、二阶（速度）、三阶（加速度）等。运动信息包括：物体的一阶（位移）、二阶（速度）、三阶（加速度）等。 研究内容包括：运动目标检测与分割、运动参数估计等。研究内容包括：运动目标检测与分割、运动参数估计等。 光流：指视觉观察到的图像中产生

6、的光强变化。它一般对应物体的运动，但也光流：指视觉观察到的图像中产生的光强变化。它一般对应物体的运动，但也 有不一致的情况。有不一致的情况。 换句话说，在视频图像序列运动估计中，观察到的二维运动叫光流。换句话说，在视频图像序列运动估计中，观察到的二维运动叫光流。 或定义：视频序列空间坐标关于时间的变化率称为光流，即或定义：视频序列空间坐标关于时间的变化率称为光流，即 (vx,vy)T=(dx/dt,dy/dt)T,其对应于像素的瞬时速度矢量。其对应于像素的瞬时速度矢量。 第三章二维运动估计之一第三章二维运动估计之一 纲要 v2-D 运动和光流运动和光流 v光流方程解决运动估计的一般方法光流方程

7、解决运动估计的一般方法 运动表示运动表示 运动场参数化运动场参数化 最优化准则的公式化最优化准则的公式化 寻找最优化参数寻找最优化参数 v运动估计算法运动估计算法 基于光流的运动估计基于光流的运动估计 基于像素的运动估计基于像素的运动估计 基于块的运动估计（基于块的运动估计（EBMA） 第三章二维运动估计之一第三章二维运动估计之一 3-D运动运动 - 2-D运动运动 3-D MV 2-D MV 第三章二维运动估计之一第三章二维运动估计之一 2.1 2-D 运动运动 vs. 光流光流 v2-D 运动运动: 3-D 运动的投影运动的投影, 取决于取决于3D 物体运动和投影物体运动和投影 操作。操作

8、。 v光流光流: 观测的或表现的二维运动。观测的或表现的二维运动。 不仅可以由物体运动引起，还可以由摄像机运动或照明条件不仅可以由物体运动引起，还可以由摄像机运动或照明条件 变化引起。注：不等同于真实的二维运动。变化引起。注：不等同于真实的二维运动。 v左边是一个具有均匀平坦表面 的球在恒定的环境光下转动。 每一个点都反射相同的彩色， 人们感觉不到球的任何变化， 认为球是静止的。 v右边是一个静止的球，被一个 绕着球转动的点光源照明。光 源的运动引起球上反射光点的 运动，人眼认为球在运动。 第三章二维运动估计之一第三章二维运动估计之一 光流方程光流方程 v如果照明条件未知，那么所能得到的最精确

9、估如果照明条件未知，那么所能得到的最精确估 计就是光流。计就是光流。 v恒定亮度假设恒定亮度假设 光流方程光流方程 又运用泰勒展开式，当又运用泰勒展开式，当dx,dy,dt很小时，很小时， 比较上面两个式子，得到光流方程：比较上面两个式子，得到光流方程： ),(),(tyxdtdydx tyx tyxtyx d t d y d x tyxdtdydx ),(),( 000 tt v y v x d t d y d x T yxtyx v T yx , 其中 空间梯度矢量空间梯度矢量 第三章二维运动估计之一第三章二维运动估计之一 其中： 为图像空间梯度方向 上的单位矢量 v光流v的分解 将光流v

10、分解为两个正交的分量： n e 0 t v T tn eev tn vv 为切线方向上的单位矢量 t e 0 t vn n e n v t e t v v 只能确定图像空间梯度方向上的分量（法向流） 即：孔径问题 n v 光流方程光流方程 第三章二维运动估计之一第三章二维运动估计之一 图图6.3 运动估计中的孔径（用一个恒定亮度假设的小窗口）运动估计中的孔径（用一个恒定亮度假设的小窗口） 问题问题: 在在x1 处估计运动使用孔径处估计运动使用孔径1，但是不可能确定运动，但是不可能确定运动 是向上的还是垂直于边缘的，因为在这个孔径中只有一是向上的还是垂直于边缘的，因为在这个孔径中只有一 个空间梯

11、度方向。可以准确地估计个空间梯度方向。可以准确地估计x2的运动，因为在孔径的运动，因为在孔径 2中，图像有两个不同方向的梯度。中，图像有两个不同方向的梯度。 第三章二维运动估计之一第三章二维运动估计之一 运动估计中的不确定问题运动估计中的不确定问题 v孔径问题：光流方程只确孔径问题：光流方程只确 定了法向的投影定了法向的投影vn， ，在切线 在切线 的投影是不确定的，任何的投影是不确定的，任何 vt 的值都满足光流方程。的值都满足光流方程。 v一个方程有两未知数一个方程有两未知数 要施加附加条件：最通常要施加附加条件：最通常 的约束是流矢量在空间平的约束是流矢量在空间平 滑变化。使我们可以利用

12、滑变化。使我们可以利用 x周围一个小的邻域亮度周围一个小的邻域亮度 变化去估计变化去估计x处的运动。处的运动。 v运动估计仅在有亮度变化运动估计仅在有亮度变化 区域可靠。区域可靠。 0| t v vv n ttnn eev 第三章二维运动估计之一第三章二维运动估计之一 v参考帧：参考帧： 1(x, t1) v当前帧当前帧: 2(x, t2) v前向运动估计前向运动估计 /后向运动估计：后向运动估计： t2 t1 / t2 重点重点 v三个关键问题：三个关键问题： Q1：怎样将运动场参数化：怎样将运动场参数化 Q2：用什么样的准则来估计这些参数：用什么样的准则来估计这些参数 Q3：怎样搜索这些最

13、优参数：怎样搜索这些最优参数 第三章二维运动估计之一第三章二维运动估计之一 2.2.1 运动表示法（运动表示法（Q1） 整体（全整体（全 局）局）: 整体运动整体运动 由若干整由若干整 体参数表体参数表 示。示。 基于块：基于块： 把图像域把图像域 固定分成固定分成 许多小的许多小的 方块，每方块，每 个块用一个块用一 个简单的个简单的 模型表征。模型表征。 基于像素：基于像素： 每个象素都每个象素都 指定运动矢指定运动矢 量量 基于区域：基于区域： 将图像帧分将图像帧分 为多个区域，为多个区域， 每个区域用每个区域用 一个参数化一个参数化 模型表征。模型表征。 第三章二维运动估计之一第三章二

14、维运动估计之一 2.2.2 运动估计准则运动估计准则1： （Q2） 基于位移帧差准则基于位移帧差准则 v最常用的运动估计准则是参考帧最常用的运动估计准则是参考帧 1与当前帧与当前帧 2 之间每个对应点对之间亮度值之差的和。之间每个对应点对之间亮度值之差的和。 v回忆回忆 1中的中的x移动到移动到 2 中的中的w(x; a) ，则目标函，则目标函 数写为：数写为： min| )();(|)( 12 p DFD wExaxa x vp 是一个正数，当是一个正数，当 p = 1, 上面的误差称为平均上面的误差称为平均 绝对差绝对差 (MAD), 当当p = 2,称为均方差称为均方差(MSE) v误差

15、图像误差图像e(x; a) = 2(w(x, a) ) - 1(x) 一般称为一般称为 位移帧差位移帧差(DFD) 图像图像 v使使 最小的必要条件是它的梯度最小的必要条件是它的梯度=0 )(a DFD E 第三章二维运动估计之一第三章二维运动估计之一 2.2.2 运动估计准则运动估计准则2： 基于光流方程准则基于光流方程准则 min| )()();()( |)( 121 p Ax T OF Exxaxdxa v光流方程光流方程 0 tyx d t d y d x v如果如果 dt 很小，令很小，令 )()( 12 xxd t t 0, 0 12112 11 dord y d x T yx v

16、这个光流方程的离散形式更经常用在数字视频的运动估这个光流方程的离散形式更经常用在数字视频的运动估 计中，求解符合方程的计中，求解符合方程的x问题可以转化成用以下目标函数问题可以转化成用以下目标函数 （EOF）表示的最小化问题：）表示的最小化问题： 第三章二维运动估计之一第三章二维运动估计之一 v运动估计是一个不适定（病态）问题运动估计是一个不适定（病态）问题 恒定亮度假定不总是成立恒定亮度假定不总是成立 在平面纹理区域，不同运动估计可以满足恒定亮度在平面纹理区域，不同运动估计可以满足恒定亮度 假设或光流方程。假设或光流方程。 v在严格数学意义上，我们不可能对不适定问题进行求在严格数学意义上，我

17、们不可能对不适定问题进行求 解并得到答案，只能通过先验知识找到近似解。解并得到答案，只能通过先验知识找到近似解。 v正则化过程：即用一组与原不适定问题相近的适定问正则化过程：即用一组与原不适定问题相近的适定问 题去逼近原问题的解。题去逼近原问题的解。 v在基于像素和基于块运动估计中很重要。在基于像素和基于块运动估计中很重要。 2.2.2 运动估计准则运动估计准则3 平滑约束正则化平滑约束正则化 第三章二维运动估计之一第三章二维运动估计之一 2.2.2 运动估计准则运动估计准则3 平滑约束正则化平滑约束正则化 v常用的正则化方法是增加一个表示平滑变化的常用的正则化方法是增加一个表示平滑变化的 代

18、价项来测量邻近像素代价项来测量邻近像素MV的差：的差： v总的最小化准则写成：总的最小化准则写成： AxNy s x aydaxdaE 2 );();()( min)()(aEwaEE ssDFD 。以免模糊系数应该减小来选择，物体边界的权 运动平滑的重要性根据与预测误差有关的权系数 )( s w 第三章二维运动估计之一第三章二维运动估计之一 不同准则之间的关系 v基于光流方程准则基于光流方程准则OF 只有当运动比较小的时候效果较好。只有当运动比较小的时候效果较好。 当当p=2时最小值函数是时最小值函数是MV的二次函数。如果运动参的二次函数。如果运动参 数关于数关于MV线性，则函数具有唯一的最

19、小值，容易线性，则函数具有唯一的最小值，容易 求解。求解。 v当运动比较大，可以对基于光流方程准则当运动比较大，可以对基于光流方程准则OF 进行迭代求解，以满足基于位移帧差（进行迭代求解，以满足基于位移帧差（DFD） 准则。准则。 第三章二维运动估计之一第三章二维运动估计之一 2.2.3 优化方法（对误差函数进行最小化）优化方法（对误差函数进行最小化） Q3 v穷尽搜索穷尽搜索 通常用在通常用在DFD准则中当准则中当p=1(MAD)的情况的情况 保证全局最优保证全局最优 计算量太大计算量太大 快速算法可以得到次优解。快速算法可以得到次优解。 v基于梯度搜索基于梯度搜索 通常用在通常用在 DFD

20、 或或 OF 准则，当准则，当 p=2 (MSE)的情况的情况 可以计算出梯度可以计算出梯度 运用运用OF准则时应该可以获得一个闭合解析式。准则时应该可以获得一个闭合解析式。 通过先验知识获得一个好的初始解，搜索出局部最优的点通过先验知识获得一个好的初始解，搜索出局部最优的点 v多分辨率搜索多分辨率搜索 从粗分辨率搜索到细分辨率，比穷尽搜索快。从粗分辨率搜索到细分辨率，比穷尽搜索快。 避免陷入局部最优避免陷入局部最优 第三章二维运动估计之一第三章二维运动估计之一 2.3 基于光流的运动估计基于光流的运动估计 v光流方程 亮度守恒假设：运动物体点的亮度（或色度）在其运 动轨迹上保持不变，变化的是

21、物体的位置。 ),(),( tyx dtdydxtyx tyxtyx d t d y d x tyxdtdydx ),(),( 0 tyx d t d y d x 0 t v y v x yx 或0 t v T 其中 为空间梯度向量， 为光流场。 T yx ,),( yx vvv 第三章二维运动估计之一第三章二维运动估计之一 图像梯度的计算 v光流方程的要求：亮度函数可微 v数字视频：有限差分法近似 m,nm+1,n m,n+1m+1,n+1 )1, 1,() 1, 1, 1( ) 1,() 1, 1(), 1,( ), 1, 1(),(), 1( 4 1 knmknm knmknmknm k

22、nmknmknm x )1, 1() 1, 1, 1( ) 1,() 1, 1,(), 1( ), 1, 1(),(), 1,( 4 1 knmknm knmknmknm knmknmknm y ), 1, 1() 1, 1, 1( ), 1,() 1, 1,(), 1( ) 1, 1(),() 1,( 4 1 knmknm knmknmknm knmknmknm t 第三章二维运动估计之一第三章二维运动估计之一 2.3.1 多点邻域约束 v光流方程 一个方程，两个未 知数 v多点邻域约束 假设 的邻域 内所有像素具有相同的光流矢量，光流 方程在领域 上的误差定义为： )( i x 2 )(

23、Bx yx t v y v x wE x i x 其中 为分配给 的权重。令 可得： )( i x )(xwx0 yx v E v E 0)( xt v y v x xw Bx yx 0)( yt v y v x xw Bx yx 0 t v y v x yx 第三章二维运动估计之一第三章二维运动估计之一 v多点邻域约束 则光流矢量的估计值为： Bx Bx BxBx BxBx y x ty xw tx xw yy xw yx xw yx xw xx xw v v )( )( )()( )()( 1 2.3.1 多点邻域约束 第三章二维运动估计之一第三章二维运动估计之一 2.3.2 运动平滑约束

24、 运动场的平滑性 第三章二维运动估计之一第三章二维运动估计之一 v运动平滑约束 由Horn和Schunck提出，对整个运动场或局部窗施加全局 平滑约束。 目标误差函数为： x ssof dxeweE)()()( 22 vvv 其中 为运动估计的定义域，可以是整幅图像或一个局部窗。 2 2 )( t v y v x e yxof v 222 2 2 2 2 )( y v x v y v x v vve yy xx yxs v )( 2 v s e为光流空间梯度光流空间梯度的平方函数，它反映了光流矢量随像素 变化的快慢程度 为光流方程误差的平方函数 2.3.2 运动平滑约束 第三章二维运动估计之一

25、第三章二维运动估计之一 对 求关于 和 的偏微 分，并令其为0，可得： )(vE x v y v v运动平滑约束 最小化 施加光流 约束 最小化 施加运动 平滑约束 )( 2 v of e ty vwv y wv yx tx vwv yx v x w ysysx xsyxs 2 2 )( 2 v s e 2 2 )()( )()1( 2 2 )()( )()1( yx w t v y v x y vv yx w t v y v x x vv s l y l x l y l y s l y l x l x l x 表示对像素邻域（不包括当 前像素）求平均。 表示迭代次数，初始光流矢 量 可设为零

26、。 )0( v l v 2.3.2 运动平滑约束 第三章二维运动估计之一第三章二维运动估计之一 2.4 基于像素的运动估计基于像素的运动估计 v最优化方法最优化方法1：多邻域方法：多邻域方法 假设像素假设像素xn 周围的小范围内各个像素的运动向量（周围的小范围内各个像素的运动向量（MV）一致。）一致。 最小化邻域上的预测误差。最小化邻域上的预测误差。 v最优化方法最优化方法2：像素递归方法：像素递归方法 当前像素的当前像素的MV是在已经编码的邻近像素的是在已经编码的邻近像素的MV上更新的。根上更新的。根 据同样的更新规则，据同样的更新规则，MV不用编码。不用编码。 应用在较早几代的视频编码器中

27、。应用在较早几代的视频编码器中。 v准则准则平滑约束正则化：平滑约束正则化：Horn-Schunck 方方 法法 光流方程准则光流方程准则 + 运动平滑准则运动平滑准则 )()()( 2 2 2 yxsyx A vvw t v y v x vE x x 第三章二维运动估计之一第三章二维运动估计之一 2.4 基于像素的运动估计基于像素的运动估计 v与光流法一样，估计每个像素的运动矢量 v位移帧差 像素x从t1时刻到t1+dt时刻的位移帧差为： ),(),(),( 11 tdte t xdxdx T yx dd,d 为为x处的位移矢量处的位移矢量 tyxt d t d y d x tdt ),()

28、,( 11 xdx tyx d t d y d x e ),(dx 由亮度守恒假设由亮度守恒假设 ，即：，即：0),(dxe 0 tyx d t d y d x 两边同时除以两边同时除以dt，可得：，可得：0 t v y v x yx （光流方程）（光流方程） 第三章二维运动估计之一第三章二维运动估计之一 多点邻域约束 l假设 的邻域 内所有像素具有相同的运动矢量， 领域 上的误差函数为： 2 )( 12 )()()( 2 1 )( i Bx ii wE x xdxxd )( 2 )(),()()( i Bx ii i i ew E E x xd dxdxx d d )( i x )( i x

29、 i x 其中，w(x)为分配给x的权重。误差函数关于运动矢量di的 梯度为： 使用基于一阶梯度下降一阶梯度下降的方法求解运动矢量di： )( )()1( i l i l i E ddd d 为更新步长。 也可以使用穷尽搜索法寻找di。 2.4.1 多点邻域约束多点邻域约束 第三章二维运动估计之一第三章二维运动估计之一 像素递归法 l沿图像扫描方向逐个估计像素的运动矢量。 l新像素的运动矢量由已估计像素的运动矢量进行预测 l使用基于位移帧差函数最小化的方法更新运动矢量 l像素的位移矢量无需编码 解码器端使用同样的预测更新机制 l估计精度较低，预测误差较大 );,();,();,( ttpt d

30、tdtdtxuxdxd 局部平滑约束 光流约束 2.4.2 像素递归法像素递归法 第三章二维运动估计之一第三章二维运动估计之一 基于梯度下降的算法 v基于梯度下降的算法(Netravali-Robbins) 最小化位移帧差函数 迭代方程： 为更新步长； 为关于d的梯度。 关于位移矢量的梯度计算关于图像梯度的计算 终止迭代条件：更新项或位移帧差小于某阈值 收敛速度取决于 的选取 同样存在孔径问题 2 12 2 )()(),(),(xdxdxdx i eE ),(),( )()()() 1(llll eedxdxdd d ),( )(l edx d )(),( )( 2 )()()1(llll e

31、dxdxdd x 第三章二维运动估计之一第三章二维运动估计之一 多点邻域约束的像素递归法 v使用多点邻域约束的像素递归法 目标误差函数为： xx xdxdxdx 2 12 2 )()(),(),(eE 1234 56x 16为已经估计的像素 x为当前像素 第三章二维运动估计之一第三章二维运动估计之一 v将图像分成一个个规则的图像块，对每个块进行运动估计。 v广泛应用于各种视频压缩编码标准中。 v块运动模型 块平移模型 假定每个块只做平移运动 优点：实现简单 缺点：1、不能表征旋转、缩放和局部变形；2、物体边界和块边界通常 不一致，导致块失真；3、同一块可能包含多个运动物体。 可变形块模型 可以

32、对物体的旋转、缩放、变形建模 三种模型：投影运动、仿射运动、双线性运动 v方法：相位相关法、块匹配法 2.5 基于块的运动估计基于块的运动估计 第三章二维运动估计之一第三章二维运动估计之一 块平移模型 a) 非重叠块 b) 重叠块 6.4 基于块的运动估计基于块的运动估计 第三章二维运动估计之一第三章二维运动估计之一 2.5 基于块的运动估计（块匹配算法）基于块的运动估计（块匹配算法） v假设把图像域分割成互不重叠的小区域（块），假设把图像域分割成互不重叠的小区域（块）， 每个块内像素运动一致。每个块的运动参数可每个块内像素运动一致。每个块的运动参数可 独立搜索。独立搜索。 v块匹配算法块匹配

33、算法 (BMA): 假设块进行平移运动，每假设块进行平移运动，每 个块规定一个向量个块规定一个向量 穷尽块匹配算法穷尽块匹配算法 (EBMA) 快速算法快速算法 v可变形块匹配算法可变形块匹配算法(DBMA): 允许更多复杂的运允许更多复杂的运 动（仿射，双线性）动（仿射，双线性） 第三章二维运动估计之一第三章二维运动估计之一 2.5 基于块的运动估计基于块的运动估计 v基本思路：基本思路： 假设块内各个像素都进行平移运动，用一个假设块内各个像素都进行平移运动，用一个 MV表表 示示 用最小化块的位移帧差用最小化块的位移帧差DFD来独立估计每个块的运来独立估计每个块的运 动向量动向量 v最小化

34、函数最小化函数 v 最优化方法：最优化方法： 穷尽搜索法穷尽搜索法 (适用于一次搜索一个运动矢量的情况，适用于一次搜索一个运动矢量的情况， p=1的的MAD准则准则) 快速算法快速算法 整数整数 vs.分数精度搜索分数精度搜索 min| )()(|)( 12 p m B mDFD m Exdxd x 第三章二维运动估计之一第三章二维运动估计之一 穷尽块匹配算法穷尽块匹配算法 (EBMA) 第三章二维运动估计之一第三章二维运动估计之一 整数像素精度整数像素精度 EBMA的复杂度的复杂度 v假设假设 图像尺寸图像尺寸: M M 块尺寸块尺寸: N N 每个方向的搜索范围每个方向的搜索范围: (-R

35、,R) 搜索步长搜索步长: 1 pixel (假设整数假设整数MV) v运算次数运算次数 (1 次运算次运算=1 “-”, 1 “+”, 1 “| |”): 每个块的候选匹配块总数：每个块的候选匹配块总数： (2R+1)2 每个候选估计的每个候选估计的MAD运算数：运算数：N2 估计每个块的估计每个块的MV运算数：运算数： (2R+1)2 N2 整个帧整个帧 的的MV运算数：运算数：(M/N)2(2R+1)2 N2 = M2(2R+1)2 和块的大小和块的大小N无关无关 v如：如： M=512, N=16, R=16, 30 fps（帧率）（帧率） 总的运算量：总的运算量： 2.85 108

36、/frame =8.55 109/second v结构规整，可用模块化设计，有利于结构规整，可用模块化设计，有利于VLSI设计应用设计应用 v纯软件实现有难度纯软件实现有难度 第三章二维运动估计之一第三章二维运动估计之一 6.4.2 分数精度分数精度 EBMA v现实的运动矢量不一定是整数像素倍数。为了更精确现实的运动矢量不一定是整数像素倍数。为了更精确 的运动表示，需要分数像素精度。的运动表示，需要分数像素精度。 v半像素精度搜索：步长半像素精度搜索：步长=1/2 像素像素 v难点：难点： 目标帧只有整数像素目标帧只有整数像素 v解决方法解决方法: 为了实现为了实现1/2像素步长，目标帧必须

37、先进行像素步长，目标帧必须先进行2倍内插。倍内插。 通常使用双线性插值法通常使用双线性插值法 v复杂度：复杂度： 搜索点总数等于整数像素精度搜索的四倍，加上内插所需的搜索点总数等于整数像素精度搜索的四倍，加上内插所需的 额外运算量，复杂性大于额外运算量，复杂性大于4倍倍 v快速算法：快速算法： 先用整像素精度搜索，然后用半像素精度在小范围内细化。先用整像素精度搜索，然后用半像素精度在小范围内细化。 第三章二维运动估计之一第三章二维运动估计之一 v真实运动未必是整 数值 v分数精度搜索可提 高运动估计的精度 v半像素精度 MPEG- 1、 MPEG-2、 H.263 v1/4和1/8像素精度 M

38、PEG-4、H.264 分数精度分数精度 EBMA 第三章二维运动估计之一第三章二维运动估计之一 分数精度 原始参考图像 线性内插 内插后的参考图像 M N 2M 2N 第三章二维运动估计之一第三章二维运动估计之一 第三章二维运动估计之一第三章二维运动估计之一 EBMA的优缺点的优缺点 v块效应块效应(块边界不连续块边界不连续) 块位移模型不精确块位移模型不精确 解决方法：可变形块匹配算法解决方法：可变形块匹配算法 v运动域是随机的运动域是随机的 块和块之间的运动矢量估计是独立的块和块之间的运动矢量估计是独立的 解决方法解决方法1: 基于网格的运动估计基于网格的运动估计 解决方法解决方法2：提

39、高正则化的光滑约束：提高正则化的光滑约束 v平滑区域产生错误的平滑区域产生错误的MV 当光梯度接近当光梯度接近0时无法估计出运动。时无法估计出运动。 v基于块的运动估计广泛应用在视频编码中基于块的运动估计广泛应用在视频编码中 基于它的简单性和预测误差最小化基于它的简单性和预测误差最小化 第三章二维运动估计之一第三章二维运动估计之一 BMA快速算法快速算法 v基本想法：基本想法： 减小搜索候选块的个数：减小搜索候选块的个数： 只搜索那些有可能产生误差的块只搜索那些有可能产生误差的块 基于前期搜索结果，预测剩下的候选块。基于前期搜索结果，预测剩下的候选块。 简化差错度量简化差错度量(DFD) ，以

40、减小计算量。，以减小计算量。 v经典的快速算法经典的快速算法 二维对数搜索法二维对数搜索法 三步搜索法三步搜索法 新三步搜索法新三步搜索法 菱形搜索法菱形搜索法 v更多的快速搜索算法更多的快速搜索算法 有些是针对软件应用的，有些针对有些是针对软件应用的，有些针对VLSI应用。应用。 第三章二维运动估计之一第三章二维运动估计之一 二维对数搜索法二维对数搜索法 v从零位移的位置开从零位移的位置开 始搜索始搜索 v每一步搜索每一步搜索5个菱形个菱形 排列的点。排列的点。 v下一步，把中心移下一步，把中心移 到前一步找到的最到前一步找到的最 佳匹配点并重复菱佳匹配点并重复菱 形搜索。形搜索。 v当最佳匹配点是中当最佳匹配点是中 心点或是在最大搜心点或是在最大搜 索区域的边界上时，索区域的边