第三章_二维运动估计之二

1、第三章第三章 二维运动估计之二二维运动估计之二目录目录vEBMA的问题的问题v可变形块匹配算法可变形块匹配算法 (DBMA) 基于节点的运动模型基于节点的运动模型v基于网格的运动估计基于网格的运动估计v基于区域的运动估计基于区域的运动估计v全局运动估计全局运动估计 直接估计法直接估计法 间接估计法间接估计法v多分辨率运动估计多分辨率运动估计 分层块匹配算法分层块匹配算法(HBMA)v小结小结EBMA的问题（的问题（1）v块效应块效应(块边界不连续块边界不连续) 块位移模型不精确块位移模型不精确 真实的块内运动有可能比简单的位移复杂得多真实的块内运动有可能比简单的位移复杂得多 解决方法：可变形块

2、匹配算法解决方法：可变形块匹配算法v在一个块中有可能有多个物体的不同运动在一个块中有可能有多个物体的不同运动 解决方法解决方法1: 自适应的网格运动估计自适应的网格运动估计 解决方法解决方法2：基于区域的运动估计：基于区域的运动估计v亮度变化产生的光照效应亮度变化产生的光照效应 要先对光照效应进行补偿，然后再进行恒定光强度要先对光照效应进行补偿，然后再进行恒定光强度假设。假设。EBMA的问题的问题 （2）v运动域是随机的运动域是随机的 块和块之间的运动矢量估计是独立的块和块之间的运动矢量估计是独立的 解决方法解决方法1：加入光滑性约束，调整预测误差项和平：加入光滑性约束，调整预测误差项和平滑项

3、的权重。滑项的权重。 解决方法解决方法2：多分辨率方法：多分辨率方法 解决方法解决方法3：基于网格的运动估计：基于网格的运动估计v光滑区域产生错误的光滑区域产生错误的MV 当光梯度接近当光梯度接近0时无法估计出运动。时无法估计出运动。 解决方法：基于区域的运动估计解决方法：基于区域的运动估计v非常大的运算量非常大的运算量 解决方法解决方法1：快速算法，牺牲部分精度：快速算法，牺牲部分精度 解决方法解决方法2：多分辨率运动估计：多分辨率运动估计目录目录vEBMA的问题的问题v可变形块匹配算法可变形块匹配算法 (DBMA) 基于节点的运动模型基于节点的运动模型v基于网格的运动估计基于网格的运动估计

4、v基于区域的运动估计基于区域的运动估计v全局运动估计全局运动估计 直接估计法直接估计法 间接估计法间接估计法v多分辨率运动估计多分辨率运动估计 分层块匹配算法分层块匹配算法(HBMA)v小结小结可变形块匹配算法可变形块匹配算法v过程：过程：1.将锚定将锚定帧分割成多个规整的块帧分割成多个规整的块2.对每个块采用较复杂的运动模型对每个块采用较复杂的运动模型（如仿射，双线性或投影映射）（如仿射，双线性或投影映射）3.对每个块进行独立的运动参数估计对每个块进行独立的运动参数估计xm,3 xm,2Bmxm,4 xm,1Bm6.5 可变形块匹配算法可变形块匹配算法v仍然不能解决块内存在多个运动的问题，块

5、效应和光照效应等问题。仿射 (6 个参数): 三角形映射ybxbbyaxaayxdyxdyx210210),(),(xybybxbbxyayaxaayxdyxdyx32103210),(),(双线性 (8个参数) : 四边形映射6.5.1 基于节点的运动表示基于节点的运动表示v假设假设 在块中选择若干个控制节点，这些节点能够自由运在块中选择若干个控制节点，这些节点能够自由运动动而且任何中间点的位移可以通过节点的位移内插得而且任何中间点的位移可以通过节点的位移内插得到。到。 v令令K K 表示控制节点数，表示控制节点数， d dm,km,k 表示表示B Bm m 中控制节中控制节点的运动矢量，则

6、块的运动函数可以表示为：点的运动矢量，则块的运动函数可以表示为：mkmkmKkmBddxx,)(,1mkmKkkmBxxx, 1)(1)(0,1,其中的贡献期望值个控制点对中第取决于内插核xk)(,mkmBx6.5.1 基于节点的运动表示基于节点的运动表示v控制点举例：块角控制点举例：块角点点v其他点其他点的运动通过的运动通过角点角点dm,km,k 的运动矢的运动矢量量插值插值得到。得到。v控制点的运动矢量控制点的运动矢量可以是整数像素精可以是整数像素精度或者半像素精度，度或者半像素精度，所有控制点的运动所有控制点的运动参数参数同等重要同等重要。v平移，仿射，双线平移，仿射，双线性是这个模型的

7、特性是这个模型的特例。例。mkmkmKkmBddxx,)(,1内插公式lK=1，退化为平移模型lK=3，对应于仿射运动模型lK=4，对应于双线性运动模型Kkkk1)()(dxxd第k个节点对像素x的贡献，称内插核6.5.2 基于节点模型的运动估计基于节点模型的运动估计v搜索方法搜索方法: 穷尽搜索法穷尽搜索法: 实际中要同步搜索实际中要同步搜索K个节点的运动矢量，搜索维度高，不可个节点的运动矢量，搜索维度高，不可行。行。 梯度下降法梯度下降法: 牛顿牛顿-拉夫森搜索算法拉夫森搜索算法 搜索的结果依赖于搜索的结果依赖于初始解初始解。好的初始解可通过。好的初始解可通过EBMA得到。得到。212)(

8、)(21xxxdxEv匹配函数匹配函数:Kkkk1)()(dxxd其中其中DBMA的问题v块边界会产生运动的不连续性，是由于节点的运块边界会产生运动的不连续性，是由于节点的运动矢量是从每个块中独立预测得到的。动矢量是从每个块中独立预测得到的。解决方法：基于网格的运动估计解决方法：基于网格的运动估计v当块内有多物体运动或者因照明产生变化时，当块内有多物体运动或者因照明产生变化时，DBMADBMA效果不好效果不好三模型法：三模型法： 先对每个块实行先对每个块实行EBMAEBMA EBMAEBMA误差小的块具有平移运动误差小的块具有平移运动 EBMAEBMA误差大的块具有非平移运动误差大的块具有非平

9、移运动对这些块运用对这些块运用 DBMADBMA目录目录vEBMA的问题的问题v可变形块匹配算法可变形块匹配算法 (DBMA) 基于节点的运动模型基于节点的运动模型v基于网格的运动估计基于网格的运动估计v基于区域的运动估计基于区域的运动估计v全局运动估计全局运动估计 直接估计法直接估计法 间接估计法间接估计法v多分辨率运动估计多分辨率运动估计 分层块匹配算法分层块匹配算法(HBMA)v小结小结基于网格的运动估计(a) 使用三角形网格(b) 使用四边形网格当前帧被分割为不重叠的多边形单元（网格），运动估计为网格的每个节点在参考帧找到对应点（即得到其运动矢量），其余点的位移矢量由节点的运动矢量插值

10、得到。基于网格的运动估计(a) 基于块匹配的运动估计(b) 基于网格的运动估计(c) 基于网格的运动跟踪基于网格的运动估计单元内像素的运动由节点的运动矢量内插得到每个网格节点只有一个运动矢量，与其相邻的所有多边形单元共享此运动矢量mKkkmnkmmDmxdxxd,)()(1),(,基于网格的运动估计v主要步骤 建立网格 规则网格 自适应网格 复杂运动的区域节点密集，简单运动的区域节点稀疏 节点运动估计 最小化位移帧差函数 二阶梯度迭代 先后顺序 光栅扫描 根据节点处图像梯度值 分组自适应三角形网格的建立图像梯度较大：区域运动较复杂预测误差较大：此区域的运动模型建模失效SG（x,y）和PPE（x

11、,y）非零时：网格节点密集图像梯度预测误差) 1,() 1,(), 1(), 1(),(2222yxyxyxyxyxSG0),(),(yxSGTyxSGSG),(),(),(22yxyxyxPPE0),(),(yxPPETyxPPEPPE如果如果: ),(2yx重建图像: ),(2yx运动补偿图像节点运动估计更新第n个节点的运动矢量时，其余节点的运动矢量保持不变S(n)表示与第n个节点相连接的多边形单元的误差函数全搜索法基于梯度下降的方法2,2,212121,(, )2111( )( )21( )( )2mmmMmmKMm kn m kmkE xxxdxxxx dx)(minarg)()()1

12、(nnSlnlnEnuddu )(221)(,2)()(21nSmmnSmxExxxd节点运动估计v步骤 节点运动估计初始值：块匹配法 按顺序迭代估计每个节点 给定某个节点，固定其他节点 在不改变拓扑结构的范围内移动该节点，计算误差函数 最小化误差函数更新的运动矢量 满足某条件，终止迭代v每个节点的更新过程 全搜索 梯度下降基于网格的运动估计基于网格全搜索块匹配 (半像素精度) 参考帧当前帧预测图像基于网格的运动估计与块匹配法的比较v网格 当前帧可以分成规则的或不规则的网格 参考帧中的不规则网格是不重叠的 每个节点只有一个运动矢量v可变形块 当前帧分成规则的网格 参考帧中的不规则网格是重叠的

13、每个节点有多个运动矢量v不可变形块 当前帧分成规则的网格 参考帧中的规则网格是重叠的目录目录vEBMA的问题的问题v可变形块匹配算法可变形块匹配算法 (DBMA) 基于节点的运动模型基于节点的运动模型v基于网格的运动估计基于网格的运动估计v基于区域的运动估计基于区域的运动估计v全局运动估计全局运动估计 直接估计法直接估计法 间接估计法间接估计法v多分辨率运动估计多分辨率运动估计 分层块匹配算法分层块匹配算法(HBMA)v小结小结基于区域的运动估计v将视频图像分割为多个区域，每个区域对应一个特定的运动，然后为每个区域估计运动参数v区域分割：力图区域内的所有像素的运动具有一致性，可以由一个运动模型

14、表示v运动模型：仿射模型、双线性模型、投影模型v方法分类 区域优先 运动优先 联合区域分割和运动估计基于区域的运动估计v区域优先的方法 基于当前帧的纹理、边缘信息进行区域分割 局部区域的直方图 区域连接增长 为每个区域估计运动参数2211( ;)( )2nnRExxd x ax);(naxd表示当前帧第n个区域Rn中像素x的运动矢量区域误差函数：na表示Rn的运动参数矢量可以是仿射、双线性、投影运动模型中的任意一种基于区域的运动估计v运动优先的方法 首先估计整个运动场 光流、像素、块、网格等方法 运动场分割 聚类： 将具有相似运动矢量的像素进行聚合，形成区域。 分层：分成主导运动和次主导运动，

15、从占主导的区域开始，剔除误差较大的区域，得到第一层；然后进一步剔除区域，直到没有剔除区域。基于区域的运动估计v联合区域分割和运动估计的方法 区域分割和运动估计相互依赖，相辅相成。 可交替进行区域分割和运动估计目录目录vEBMA的问题的问题v可变形块匹配算法可变形块匹配算法 (DBMA) 基于节点的运动模型基于节点的运动模型v基于网格的运动估计基于网格的运动估计v基于区域的运动估计基于区域的运动估计v全局运动估计全局运动估计 直接估计法直接估计法 间接估计法间接估计法v多分辨率运动估计多分辨率运动估计 分层块匹配算法分层块匹配算法(HBMA)v小结小结全局运动估计v整幅图像的运动可以用单一的运动

16、模型表示v通常指摄像机相对于静止场景运动产生的运动v整个场景作为一个整体运动（很少发生）。v方法 直接估计法 间接估计法全局运动估计v直接估计法 误差函数：2211( )( ; )( )2Ewxxxd x axa表示全局运动参数矢量可以是仿射、双线性、投影运动模型中的任意一种)(xw为权值系数，调节 可减小与全局运动不匹配的像素对误差函数的影响。)(xw是 的线性函数，即全局运动估计v间接估计法 假设已经得到一些特征点 的运动矢量 匹配误差函数：2);()(21nnnnwEdaxdanxnd);(axdnaxAaxd)();(nn对上式求偏导并令其为零，可得运动参数：nnTnnnTnnwnwd

17、xAxAxAa)()()()()(1目录目录vEBMA的问题的问题v可变形块匹配算法可变形块匹配算法 (DBMA) 基于节点的运动模型基于节点的运动模型v基于网格的运动估计基于网格的运动估计v基于区域的运动估计基于区域的运动估计v全局运动估计全局运动估计 直接估计法直接估计法 间接估计法间接估计法v多分辨率运动估计多分辨率运动估计 分层块匹配算法分层块匹配算法(HBMA)v小结小结多分辨率运动估计v前面介绍的运动估计方法存在的问题 最小化误差函数可能收敛到局部最小值 最小化误差函数过程的计算量很大v多分辨率运动估计可有效解决这两个问题 首先在最小分辨率层（由空间低通滤波和欠取样获得）进行运动估

18、计，并把结果作为下一层的初始解。 然后每层依次进行运动估计，每层的运动估计结果都将作为下一层的初始解 每层的运动估计可使用前面介绍的方法，如基于光流、像素、块、网格等运动估计方法多分辨率运动估计分辨率增加层1层2层3可由空间低通滤波和欠取样得到可由空间低通滤波和欠取样得到多分辨率运动估计v优点 运动场接近最优解的概率更大 较小分辨率层上，误差函数可以接近全局最小值，通过插值，获得高分辨率上的初始解，最后到达最大分辨率时，误差函数接近全局最小值的可能性更大。 计算量比直接在最大分辨率上进行运动估计时要小 较小分辨率层上，搜索范围限制在较小的范围。多分辨率运动估计v分层块匹配法当前帧参考帧多分辨率运动估计v分层块匹配法当前帧参考帧多分辨率运动估计v分层块匹配法多分辨率运动估计v分层块匹配法的计算量 假设图像大小为MxM，块尺寸为NxN，所有层都使用 的 搜索范围 第l层的块