维运动估计之一.ppt

第三章 二维运动估计,运动估计涉及: 图像平面运动(二维运动) 和空间物体运动(三维运动),运动分析与估计是数字视频处理的基本问题之一, 也是数字视频处理的难点和热点。 运动分析与估计广泛应用于计算机视觉、目标跟踪、工业监视和视频压缩等场合 不同应用场合对运动估计要求不同，有如下区分： 真实运动估计：要求估计获得的物体运动和实际运动基本一致。如计算机视觉、目标跟踪、工业监视。 非真实运动估计：在不被察觉的情况下允许有估计误差，从而最大限度降低信息量和传输带宽。如广播电视中的视频压缩。,几个基本概念,1.时间序列图像：随时间而变化的一系列图像称为时间序列图像或运动图像。 2.运动物体特征：指物体形状或表面特征，如尖锐点、边缘线等。 可以通过运动物体的特征来观察分析物体的运动。 3.运动估计的基本问题 运动估计研究的是视频序列图像中投影坐标在像平面上的变化，获取运动参数，但是投影会造成信息丢失（不可逆），导致估计误差。,特征对应：运动物体上的特征与其在二维平面上的投影坐标的对应关系。见下图示：,设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。即像平面上对应的二维运动矢量di(xi,t1;t2)。,4.运动分析方法：主要有两种 .根据时间相邻的两幅或多幅图像求解物体的运动参数和三维结构信息。 图像序列的光流分析法。 运动信息包括：物体的一阶（位移）、二阶（速度）、三阶（加速度）等。 研究内容包括：运动目标检测与分割、运动参数估计等。 光流：指视觉观察到的图像中产生的光强变化。它一般对应物体的运动，但也有不一致的情况。 换句话说，在视频图像序列运动估计中，观察到的二维运动叫光流。 或定义：视频序列空间坐标关于时间的变化率称为光流，即(vx,vy)T=(dx/dt,dy/dt)T,其对应于像素的瞬时速度矢量。,纲要,2-D 运动和光流 光流方程解决运动估计的一般方法 运动表示 运动场参数化 最优化准则的公式化 寻找最优化参数 运动估计算法 基于光流的运动估计 基于像素的运动估计 基于块的运动估计（EBMA）,3-D运动 - 2-D运动,3-D MV,2-D MV,2.1 2-D 运动 vs. 光流,2-D 运动: 3-D 运动的投影, 取决于3D 物体运动和投影操作。 光流: 观测的或表现的二维运动。 不仅可以由物体运动引起，还可以由摄像机运动或照明条件变化引起。注：不等同于真实的二维运动。,左边是一个具有均匀平坦表面的球在恒定的环境光下转动。每一个点都反射相同的彩色，人们感觉不到球的任何变化，认为球是静止的。 右边是一个静止的球，被一个绕着球转动的点光源照明。光源的运动引起球上反射光点的运动，人眼认为球在运动。,光流方程,如果照明条件未知，那么所能得到的最精确估计就是光流。 恒定亮度假设 光流方程,又运用泰勒展开式，当dx,dy,dt很小时，,比较上面两个式子，得到光流方程：,空间梯度矢量,其中： 为图像空间梯度方向 上的单位矢量,光流v的分解 将光流v分解为两个正交的分量：,为切线方向上的单位矢量,只能确定图像空间梯度方向上的分量（法向流） 即：孔径问题,光流方程,图6.3 运动估计中的孔径（用一个恒定亮度假设的小窗口）问题: 在x1 处估计运动使用孔径1，但是不可能确定运动是向上的还是垂直于边缘的，因为在这个孔径中只有一个空间梯度方向。可以准确地估计x2的运动，因为在孔径2中，图像有两个不同方向的梯度。,运动估计中的不确定问题,孔径问题：光流方程只确定了法向的投影vn，在切线的投影是不确定的，任何vt 的值都满足光流方程。 一个方程有两未知数要施加附加条件：最通常的约束是流矢量在空间平滑变化。使我们可以利用x周围一个小的邻域亮度变化去估计x处的运动。 运动估计仅在有亮度变化区域可靠。,参考帧： 1(x, t1) 当前帧: 2(x, t2) 前向运动估计 /后向运动估计： t2 t1 / t2 t1 运动场： d(x, a), x 映射函数： w(x, a) = x + d(x, a) , x 运动参数矢量: a 存在问题：遮挡,2.2 运动估计的一般方法,2.2 运动估计的一般方法,两种主要的方法: 基于特征（常用在物体跟踪上，从2D构建出3D） 基于亮度（基于恒定亮度假设或光流方程，常用在运动补偿预测，视频编码和插值方面） - 重点 三个关键问题： Q1：怎样将运动场参数化 Q2：用什么样的准则来估计这些参数 Q3：怎样搜索这些最优参数,2.2.1 运动表示法（Q1）,整体（全局）: 整体运动由若干整体参数表示。 基于块： 把图像域固定分成许多小的方块，每个块用一个简单的模型表征。,基于像素： 每个象素都指定运动矢量,基于区域： 将图像帧分为多个区域，每个区域用一个参数化模型表征。,2.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) 图像 使 最小的必要条件是它的梯度=0,2.2.2 运动估计准则2： 基于光流方程准则,光流方程,如果 dt 很小，令,这个光流方程的离散形式更经常用在数字视频的运动估计中，求解符合方程的x问题可以转化成用以下目标函数（EOF）表示的最小化问题：,运动估计是一个不适定（病态）问题 恒定亮度假定不总是成立 在平面纹理区域，不同运动估计可以满足恒定亮度假设或光流方程。 在严格数学意义上，我们不可能对不适定问题进行求解并得到答案，只能通过先验知识找到近似解。 正则化过程：即用一组与原不适定问题相近的适定问题去逼近原问题的解。 在基于像素和基于块运动估计中很重要。,2.2.2 运动估计准则3 平滑约束正则化,2.2.2 运动估计准则3 平滑约束正则化,常用的正则化方法是增加一个表示平滑变化的代价项来测量邻近像素MV的差： 总的最小化准则写成：,不同准则之间的关系,基于光流方程准则OF 只有当运动比较小的时候效果较好。 当p=2时最小值函数是MV的二次函数。如果运动参数关于MV线性，则函数具有唯一的最小值，容易求解。 当运动比较大，可以对基于光流方程准则OF进行迭代求解，以满足基于位移帧差（DFD）准则。,2.2.3 优化方法（对误差函数进行最小化）Q3,穷尽搜索 通常用在DFD准则中当p=1(MAD)的情况 保证全局最优 计算量太大 快速算法可以得到次优解。 基于梯度搜索 通常用在 DFD 或 OF 准则，当 p=2 (MSE)的情况 可以计算出梯度 运用OF准则时应该可以获得一个闭合解析式。 通过先验知识获得一个好的初始解，搜索出局部最优的点 多分辨率搜索 从粗分辨率搜索到细分辨率，比穷尽搜索快。 避免陷入局部最优,2.3 基于光流的运动估计,光流方程 亮度守恒假设：运动物体点的亮度（或色度）在其运动轨迹上保持不变，变化的是物体的位置。,或,其中 为空间梯度向量， 为光流场。,图像梯度的计算,光流方程的要求：亮度函数可微 数字视频：有限差分法近似,m,n,m+1,n,m,n+1,m+1,n+1,2.3.1 多点邻域约束,光流方程 一个方程，两个未知数 多点邻域约束 假设 的邻域 内所有像素具有相同的光流矢量，光流方程在领域 上的误差定义为：,其中 为分配给 的权重。令 可得：,多点邻域约束,则光流矢量的估计值为：,2.3.1 多点邻域约束,2.3.2 运动平滑约束,运动场的平滑性,运动平滑约束 由Horn和Schunck提出，对整个运动场或局部窗施加全局平滑约束。 目标误差函数为：,其中 为运动估计的定义域，可以是整幅图像或一个局部窗。,为光流空间梯度的平方函数，它反映了光流矢量随像素变化的快慢程度,为光流方程误差的平方函数,2.3.2 运动平滑约束,对 求关于 和 的偏微分，并令其为0，可得：,运动平滑约束 最小化 施加光流约束 最小化 施加运动平滑约束,表示对像素邻域（不包括当前像素）求平均。 表示迭代次数，初始光流矢量 可设为零。,2.3.2 运动平滑约束,2.4 基于像素的运动估计,最优化方法1：多邻域方法 假设像素xn 周围的小范围内各个像素的运动向量（MV）一致。 最小化邻域上的预测误差。 最优化方法2：像素递归方法 当前像素的MV是在已经编码的邻近像素的MV上更新的。根据同样的更新规则，MV不用编码。 应用在较早几代的视频编码器中。,准则平滑约束正则化：Horn-Schunck 方法 光流方程准则 + 运动平滑准则,2.4 基于像素的运动估计,与光流法一样，估计每个像素的运动矢量 位移帧差 像素x从t1时刻到t1+dt时刻的位移帧差为：,为x处的位移矢量,由亮度守恒假设 ，即：,两边同时除以dt，可得：,（光流方程）,多点邻域约束 假设 的邻域 内所有像素具有相同的运动矢量，领域 上的误差函数为：,其中，w(x)为分配给x的权重。误差函数关于运动矢量di的梯度为：,使用基于一阶梯度下降的方法求解运动矢量di：,为更新步长。,也可以使用穷尽搜索法寻找di。,2.4.1 多点邻域约束,像素递归法 沿图像扫描方向逐个估计像素的运动矢量。 新像素的运动矢量由已估计像素的运动矢量进行预测 使用基于位移帧差函数最小化的方法更新运动矢量 像素的位移矢量无需编码 解码器端使用同样的预测更新机制 估计精度较低，预测误差较大,局部平滑约束,光流约束,2.4.2 像素递归法,基于梯度下降的算法,基于梯度下降的算法(Netravali-Robbins) 最小化位移帧差函数 迭代方程： 为更新步长； 为关于d的梯度。 关于位移矢量的梯度计算关于图像梯度的计算 终止迭代条件：更新项或位移帧差小于某阈值 收敛速度取决于 的选取 同样存在孔径问题,多点邻域约束的像素递归法,使用多点邻域约束的像素递归法 目标误差函数为：,1,2,3,4,5,6,x,16为已经估计的像素 x为当前像素,将图像分成一个个规则的图像块，对每个块进行运动估计。 广泛应用于各种视频压缩编码标准中。 块运动模型 块平移模型 假定每个块只做平移运动 优点：实现简单 缺点：1、不能表征旋转、缩放和局部变形；2、物体边界和块边界通常不一致，导致块失真；3、同一块可能包含多个运动物体。 可变形块模型 可以对物体的旋转、缩放、变形建模 三种模型：投影运动、仿射运动、双线性运动 方法：相位相关法、块匹配法,2.5 基于块的运动估计,块平移模型,a) 非重叠块,b) 重叠块,6.4 基于块的运动估计,2.5 基于块的运动估计（块匹配算法）,假设把图像域分割成互不重叠的小区域（块），每个块内像素运动一致。每个块的运动参数可独立搜索。 块匹配算法 (BMA): 假设块进行平移运动，每个块规定一个向量 穷尽块匹配算法 (EBMA) 快速算法 可变形块匹配算法(DBMA): 允许更多复杂的运动（仿射，双线性）,2.5 基于块的运动估计,基本思路： 假设块内各个像素都进行平移运动，用一个 MV表示 用最小化块的位移帧差DFD来独立估计每个块的运动向量 最小化函数,最优化方法： 穷尽搜索法 (适用于一次搜索一个运动矢量的情况，p=1的MAD准则) 快速算法 整数 vs.分数精度搜索,穷尽块匹配算法 (EBMA),整数像素精度 EBMA的复杂度,假设 图像尺寸: MM 块尺寸: NN 每个方向的搜索范围: (-R,R) 搜索步长: 1 pixel (假设整数MV) 运算次数 (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无关 如： M=512, N=16, R=16, 30 fps（帧率） 总的运算量： 2.85108 /frame =8.55109/second 结构规整，可用模块化设计，有利于VLSI设计应用 纯软件实现有难度,6.4.2 分数精度 EBMA,现实的运动矢量不一定是整数像素倍数。为了更精确的运动表示，需要分数像素精度。 半像素精度搜索：步长=1/2 像素 难点： 目标帧只有整数像素 解决方法: 为了实现1/2像素步长，目标帧必须先进行2倍内插。 通常使用双线性插值法 复杂度： 搜索点总数等于整数像素精度搜索的四倍，加上内插所需的额外运算量，复杂性大于4倍 快速算法： 先用整像素精度搜索，然后用半像素精度在小范围内细化。,真实运动未必是整数值 分数精度搜索可提高运动估计的精度 半像素精度 MPEG-1、 MPEG-2、H.263 1/4和1/8像素精度 MPEG-4、H.264,分数精度 EBMA,分数精度,原始参考图像,线性内插,内插后的参考图像,M,N,2M,2N,EBMA的优缺点,块效应(块边界不连续) 块位移模型不精确 解决方法：可变形块匹配算法 运动域是随机的 块和块之间的运动矢量估计是独立的 解决方法1: 基于网格的运动估计 解决方法2：提高正则化的光滑约束 平滑区域产生错误的MV 当光梯度接近0时无法估计出运动。 基于块的运动估计广泛应用在视频编码中 基于它的简单性和预测误差最小化,BMA快速算法,基本想法： 减小搜索候选块的个数： 只搜索那些有可能产生误差的块 基于前期搜索结果，预测剩下的候选块。 简化差错度量(DFD) ，以减小计算量。 经典的快速算法 二维对数搜索法 三步搜索法 新三步搜索法 菱形搜索法 更多的快速搜索算法 有些是针对软件应用的，有些针对VLSI应用。,二维对数搜索法,从零位移的位置开始搜索 每一步搜索5个菱形排列的点。 下一步，把中心移到前一步找到的最佳匹配点并重复菱形搜索。 当最佳匹配点是中心点或是在最大搜索区域的边界上时，就减小搜索步长（菱形的半径），否则步长不变。 当步长减小到一个像素时，达到最后一步，检验9个搜索点。 初始步长一般为最大搜索区域的一半。,n denotes a search point of step n,三步搜索法,搜索的步长从等于或者略大于最大搜索范围的一半开始 在每一步中比较9个搜索点 每一步以后搜索步长减小一半，至搜索步长为1个像素时结束搜索。 在新的搜索步中，搜索中心点移到