第三章二维运动估计之一课件

第三章二维运动估计第三章二维运动估计1运动估计涉及:图像平面运动(二维运动)和空间物体运动(三维运动),运动分析与估计是数字视频处理的基本问题之一,也是数字视频处理的难点和热点。

运动分析与估计广泛应用于计算机视觉、目标跟踪、工业监视和视频压缩等场合不同应用场合对运动估计要求不同，有如下区分：真实运动估计：要求估计获得的物体运动和实际运动基本一致。如计算机视觉、目标跟踪、工业监视。非真实运动估计：在不被察觉的情况下允许有估计误差，从而最大限度降低信息量和传输带宽。如广播电视中的视频压缩。运动估计涉及:图像平面运动(二维运动)和空间物体运动(三2几个基本概念1.时间序列图像：随时间而变化的一系列图像称为时间序列图像或运动图像。2.运动物体特征：指物体形状或表面特征，如尖锐点、边缘线等。可以通过运动物体的特征来观察分析物体的运动。3.运动估计的基本问题运动估计研究的是视频序列图像中投影坐标在像平面上的变化，获取运动参数，但是投影会造成信息丢失（不可逆），导致估计误差。几个基本概念1.时间序列图像：随时间而变化的一系列图像称为时3特征对应：运动物体上的特征与其在二维平面上的投影坐标的对应关系。见下图示：设t1→t2时，物体由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,…。特征对应：运动物体上的特征与其在二维平面上的投影坐标的对应关4运动估计的基本问题是估计运动前后相邻两帧图像上对应点的坐标pi(xi,yi)和pi’(xi’,yi’)，i=1,2,3…。即像平面上对应的二维运动矢量di(xi,t1;t2)。

运动估计的基本问题是估计运动前后相邻两帧图像上对应点的坐标p54.运动分析方法：主要有两种①.根据时间相邻的两幅或多幅图像求解物体的运动参数和三维结构信息。②图像序列的光流分析法。运动信息包括：物体的一阶（位移）、二阶（速度）、三阶（加速度）等。研究内容包括：运动目标检测与分割、运动参数估计等。光流：指视觉观察到的图像中产生的光强变化。它一般对应物体的运动，但也有不一致的情况。换句话说，在视频图像序列运动估计中，观察到的二维运动叫光流。或定义：视频序列空间坐标关于时间的变化率称为光流，即(vx,vy)T=(dx/dt,dy/dt)T,其对应于像素的瞬时速度矢量。4.运动分析方法：主要有两种6纲要2-D运动和光流光流方程解决运动估计的一般方法运动表示运动场参数化最优化准则的公式化寻找最优化参数运动估计算法基于光流的运动估计基于像素的运动估计基于块的运动估计（EBMA）纲要2-D运动和光流73-D运动->2-D运动3-DMV2-DMV3-D运动->2-D运动3-D2-D82.12-D运动vs.光流2-D运动:3-D运动的投影,取决于3D物体运动和投影操作。光流:观测的或表现的二维运动。不仅可以由物体运动引起，还可以由摄像机运动或照明条件变化引起。注：不等同于真实的二维运动。左边是一个具有均匀平坦表面的球在恒定的环境光下转动。每一个点都反射相同的彩色，人们感觉不到球的任何变化，认为球是静止的。右边是一个静止的球，被一个绕着球转动的点光源照明。光源的运动引起球上反射光点的运动，人眼认为球在运动。2.12-D运动vs.光流2-D运动:3-D9光流方程如果照明条件未知，那么所能得到的最精确估计就是光流。恒定亮度假设光流方程又运用泰勒展开式，当dx,dy,dt很小时，比较上面两个式子，得到光流方程：空间梯度矢量光流方程如果照明条件未知，那么所能得到的最精确估计就是光流。10其中：为图像空间梯度方向上的单位矢量光流v的分解将光流v分解为两个正交的分量：为切线方向上的单位矢量只能确定图像空间梯度方向上的分量（法向流）即：孔径问题光流方程其中：为图像空间梯度方向光流v的分解为切线方向上11 图6.3运动估计中的孔径（用一个恒定亮度假设的小窗口）问题:在x1处估计运动使用孔径1，但是不可能确定运动是向上的还是垂直于边缘的，因为在这个孔径中只有一个空间梯度方向。可以准确地估计x2的运动，因为在孔径2中，图像有两个不同方向的梯度。 图6.3运动估计中的孔径（用一个恒定亮度假设的小窗口）问12运动估计中的不确定问题孔径问题：光流方程只确定了法向的投影vn，在切线的投影是不确定的，任何vt的值都满足光流方程。一个方程有两未知数——要施加附加条件：最通常的约束是流矢量在空间平滑变化。使我们可以利用x周围一个小的邻域亮度变化去估计x处的运动。运动估计仅在有亮度变化区域可靠。运动估计中的不确定问题孔径问题：光流方程只确定了法向的投影v13参考帧：1(x,t1)当前帧:2(x,t2)前向运动估计/后向运动估计：t2>t1/t2<t1运动场：d(x,a),x映射函数：w(x,a)=x+d(x,a),x运动参数矢量:a存在问题：遮挡后向运动估计Timet-td(x,t-t)x当前帧Timet+tTimetd(x,t+t)xx参考帧当前帧前向运动估计2.2运动估计的一般方法参考帧：1(x,t1)后向运动估计Timet-14第三章二维运动估计之一ppt课件152.2运动估计的一般方法两种主要的方法:基于特征（常用在物体跟踪上，从2D构建出3D）基于亮度（基于恒定亮度假设或光流方程，常用在运动补偿预测，视频编码和插值方面）->重点三个关键问题：Q1：怎样将运动场参数化Q2：用什么样的准则来估计这些参数Q3：怎样搜索这些最优参数2.2运动估计的一般方法两种主要的方法:162.2.1运动表示法（Q1）整体（全局）:整体运动由若干整体参数表示。

基于块：把图像域固定分成许多小的方块，每个块用一个简单的模型表征。基于像素：每个象素都指定运动矢量基于区域：将图像帧分为多个区域，每个区域用一个参数化模型表征。2.2.1运动表示法（Q1）整体（全局）:基于172.2.2运动估计准则1：（Q2）

基于位移帧差准则最常用的运动估计准则是参考帧1与当前帧2之间每个对应点对之间亮度值之差的和。回忆1中的x移动到2中的w(x;a)，则目标函数写为：p是一个正数，当p=1,上面的误差称为平均绝对差(MAD),当p=2,称为均方差(MSE)误差图像e(x;a)=2(w(x,a))-1(x)一般称为位移帧差(DFD)图像使最小的必要条件是它的梯度=02.2.2运动估计准则1：（Q2）

基于位移帧差准则最182.2.2运动估计准则2：

基于光流方程准则光流方程如果dt很小，令这个光流方程的离散形式更经常用在数字视频的运动估计中，求解符合方程的x问题可以转化成用以下目标函数（EOF）表示的最小化问题：2.2.2运动估计准则2：

基于光流方程准则光流方程如果19运动估计是一个不适定（病态）问题恒定亮度假定不总是成立在平面纹理区域，不同运动估计可以满足恒定亮度假设或光流方程。在严格数学意义上，我们不可能对不适定问题进行求解并得到答案，只能通过先验知识找到近似解。正则化过程：即用一组与原不适定问题相近的适定问题去逼近原问题的解。在基于像素和基于块运动估计中很重要。2.2.2运动估计准则3

平滑约束正则化运动估计是一个不适定（病态）问题2.2.2运动估计准则3

202.2.2运动估计准则3

平滑约束正则化常用的正则化方法是增加一个表示平滑变化的代价项来测量邻近像素MV的差：总的最小化准则写成：2.2.2运动估计准则3

平滑约束正则化常用的正则化方法21不同准则之间的关系基于光流方程准则OF只有当运动比较小的时候效果较好。当p=2时最小值函数是MV的二次函数。如果运动参数关于MV线性，则函数具有唯一的最小值，容易求解。当运动比较大，可以对基于光流方程准则OF进行迭代求解，以满足基于位移帧差（DFD）准则。不同准则之间的关系基于光流方程准则OF222.2.3优化方法（对误差函数进行最小化）Q3穷尽搜索通常用在DFD准则中当p=1(MAD)的情况保证全局最优计算量太大快速算法可以得到次优解。基于梯度搜索通常用在DFD或OF准则，当p=2(MSE)的情况可以计算出梯度运用OF准则时应该可以获得一个闭合解析式。通过先验知识获得一个好的初始解，搜索出局部最优的点多分辨率搜索从粗分辨率搜索到细分辨率，比穷尽搜索快。避免陷入局部最优2.2.3优化方法（对误差函数进行最小化）Q3穷尽搜索232.3基于光流的运动估计光流方程亮度守恒假设：运动物体点的亮度（或色度）在其运动轨迹上保持不变，变化的是物体的位置。或其中为空间梯度向量，为光流场。2.3基于光流的运动估计光流方程或其中24图像梯度的计算光流方程的要求：亮度函数可微数字视频：有限差分法近似m,nm+1,nm,n+1m+1,n+1图像梯度的计算光流方程的要求：亮度函数可微m,nm+1,nm252.3.1多点邻域约束光流方程一个方程，两个未知数多点邻域约束假设的邻域内所有像素具有相同的光流矢量，光流方程在领域上的误差定义为：其中为分配给

的权重。令可得：2.3.1多点邻域约束光流方程26多点邻域约束则光流矢量的估计值为：2.3.1多点邻域约束多点邻域约束则光流矢量的估计值为：2.3.1多点邻域约束272.3.2运动平滑约束运动场的平滑性2.3.2运动平滑约束运动场的平滑性28运动平滑约束由Horn和Schunck提出，对整个运动场或局部窗施加全局平滑约束。目标误差函数为：其中为运动估计的定义域，可以是整幅图像或一个局部窗。为光流空间梯度的平方函数，它反映了光流矢量随像素变化的快慢程度为光流方程误差的平方函数2.3.2运动平滑约束运动平滑约束其中为运动估计的定义域，可以是整幅图像29对求关于和的偏微分，并令其为0，可得：运动平滑约束最小化施加光流约束最小化施加运动平滑约束表示对像素邻域（不包括当前像素）求平均。表示迭代次数，初始光流矢量可设为零。2.3.2运动平滑约束对求关于和的偏微分，并302.4基于像素的运动估计最优化方法1：多邻域方法假设像素xn周围的小范围内各个像素的运动向量（MV）一致。最小化邻域上的预测误差。最优化方法2：像素递归方法当前像素的MV是在已经编码的邻近像素的MV上更新的。根据同样的更新规则，MV不用编码。应用在较早几代的视频编码器中。准则——平滑约束正则化：Horn-Schunck方法光流方程准则+运动平滑准则2.4基于像素的运动估计准则——平滑约束正则化：Horn-312.4基于像素的运动估计与光流法一样，估计每个像素的运动矢量位移帧差像素x从t1时刻到t1+dt时刻的位移帧差为：为x处的位移矢量由亮度守恒假设，即：两边同时除以dt，可得：（光流方程）2.4基于像素的运动估计与光流法一样，估计每个像素的运动矢32多点邻域约束假设的邻域内所有像素具有相同的运动矢量，领域上的误差函数为：其中，w(x)为分配给x的权重。误差函数关于运动矢量di的梯度为：使用基于一阶梯度下降的方法求解运动矢量di：为更新步长。也可以使用穷尽搜索法寻找di。2.4.1多点邻域约束多点邻域约束其中，w(x)为分配给x的权重。误差函数关于运动33像素递归法沿图像扫描方向逐个估计像素的运动矢量。新像素的运动矢量由已估计像素的运动矢量进行预测使用基于位移帧差函数最小化的方法更新运动矢量像素的位移矢量无需编码解码器端使用同样的预测更新机制估计精度较低，预测误差较大局部平滑约束光流约束2.4.2像素递归法像素递归法局部平滑约束光流约束2.4.2像素递归法34基于梯度下降的算法基于梯度下降的算法(Netravali-Robbins)最小化位移帧差函数迭代方程：为更新步长；为关于d的梯度。关于位移矢量的梯度计算关于图像梯度的计算终止迭代条件：更新项或位移帧差小于某阈值收敛速度取决于的选取同样存在孔径问题基于梯度下降的算法基于梯度下降的算法(Netravali-R35多点邻域约束的像素递归法使用多点邻域约束的像素递归法目标误差函数为：123456x1~6为已经估计的像素x为当前像素多点邻域约束的像素递归法使用多点邻域约束的像素递归法123436将图像分成一个个规则的图像块，对每个块进行运动估计。广泛应用于各种视频压缩编码标准中。块运动模型块平移模型假定每个块只做平移运动优点：实现简单缺点：1、不能表征旋转、缩放和局部变形；2、物体边界和块边界通常不一致，导致块失真；3、同一块可能包含多个运动物体。可变形块模型可以对物体的旋转、缩放、变形建模三种模型：投影运动、仿射运动、双线性运动方法：相位相关法、块匹配法2.5基于块的运动估计将图像分成一个个规则的图像块，对每个块进行运动估计。2.537块平移模型a)非重叠块b)重叠块6.4基于块的运动估计块平移模型a)非重叠块b)重叠块6.4基于块的运动估计382.5基于块的运动估计（块匹配算法）假设把图像域分割成互不重叠的小区域（块），每个块内像素运动一致。每个块的运动参数可独立搜索。块匹配算法(BMA):假设块进行平移运动，每个块规定一个向量穷尽块匹配算法(EBMA)快速算法可变形块匹配算法(DBMA):允许更多复杂的运动（仿射，双线性）2.5基于块的运动估计（块匹配算法）假设把图像域分割成互不392.5基于块的运动估计基本思路：假设块内各个像素都进行平移运动，用一个MV表示用最小化块的位移帧差DFD来独立估计每个块的运动向量最小化函数最优化方法：穷尽搜索法(适用于一次搜索一个运动矢量的情况，p=1的MAD准则)快速算法整数vs.分数精度搜索2.5基于块的运动估计基本思路：最优化方法：40穷尽块匹配算法(EBMA)穷尽块匹配算法(EBMA)41整数像素精度EBMA的复杂度假设图像尺寸:MM块尺寸:NN每个方向的搜索范围:(-R,R)搜索步长:1pixel(假设整数MV)运算次数(1次运算=1“-”,1“+”,1“||”):每个块的候选匹配块总数：(2R+1)2

每个候选估计的MAD运算数：N2估计每个块的MV运算数：(2R+1)2

N2整个帧的MV运算数：(M/N)2(2R+1)2N2=M2(2R+1)2和块的大小N无关如：M=512,N=16,R=16,30fps（帧率）总的运算量：2.85108/frame=8.55109/second结构规整，可用模块化设计，有利于VLSI设计应用纯软件实现有难度整数像素精度EBMA的复杂度假设426.4.2分数精度EBMA现实的运动矢量不一定是整数像素倍数。为了更精确的运动表示，需要分数像素精度。半像素精度搜索：步长=1/2像素难点：目标帧只有整数像素解决方法:为了实现1/2像素步长，目标帧必须先进行2倍内插。通常使用双线性插值法复杂度：搜索点总数等于整数像素精度搜索的四倍，加上内插所需的额外运算量，复杂性大于4倍快速算法：先用整像素精度搜索，然后用半像素精度在小范围内细化。6.4.2分数精度EBMA现实的运动矢量不一定是整数像素43真实运动未必是整数值分数精度搜索可提高运动估计的精度半像素精度MPEG-1、MPEG-2、H.2631/4和1/8像素精度MPEG-4、H.264分数精度EBMA真实运动未必是整数值分数精度EBMA44分数精度原始参考图像线性内插内插后的参考图像MN2M2N分数精度原始参考图像线性内插内插后的参考图像MN2M2N45第三章二维运动估计之一ppt课件46EBMA的优缺点块效应(块边界不连续)块位移模型不精确解决方法：可变形块匹配算法运动域是随机的块和块之间的运动矢量估计是独立的解决方法1:基于网格的运动估计解决方法2：提高正则化的光滑约束平滑区域产生错误的MV当光梯度接近0时无法估计出运动。基于块的运动估计广泛应用在视频编码中基于它的简单性和预测误差最小化EBMA的优缺点块效应(块边界不连续)47BMA快速算法基本想法：减小搜索候选块的个数：只搜索那些有可能产生误差的块基于前期搜索结果，预测剩下的候选块。简化差错度量(DFD)，以减小计算量。经典的快速算法二维对数搜索法三步搜索法新三步搜索法菱形搜索法更多的快速搜索算法有些是针对软件应用的，有些针对VLSI应用。BMA快速算法基本想法：48二维对数搜索法从零位移的位置开始搜索每一步搜索5个菱形排列的点。下一步，把中心移到前一步找到的最佳匹配点并重复菱形搜索。当最佳匹配点是中心点或是在最大搜索区域的边界上时，就减小搜索步长（菱形的半径），否则步长不变。当步长减小到一个像素时，达到最后一步，检验9个搜索点。初始步长一般为最大搜索区域的一半。•n

denotesasearchpointofstepn二维对数搜索法从零位移的位置开始搜索•ndenotesa49三步搜索法搜索的步长从等于或者略大于最大搜索范围的一半开始在每一