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

第三章二维运动估计之二目录EBMA的问题可变形块匹配算法(DBMA)–基于节点的运动模型基于网格的运动估计基于区域的运动估计全局运动估计–直接估计法–间接估计法多分辨率运动估计–分层块匹配算法(HBMA)小结EBMA的问题（1）块效应(块边界不连续)–块位移模型不精确–真实的块内运动有可能比简单的位移复杂得多–解决方法：可变形块匹配算法在一个块中有可能有多个物体的不同运动–解决方法1:自适应的网格运动估计–解决方法2：基于区域的运动估计亮度变化产生的光照效应–要先对光照效应进行补偿，然后再进行恒定光强度假设。EBMA的问题（2）运动域是随机的–块和块之间的运动矢量估计是独立的–解决方法1：加入光滑性约束，调整预测误差项和平滑项的权重。–解决方法2：多分辨率方法–解决方法3：基于网格的运动估计光滑区域产生错误的MV–当光梯度接近0时无法估计出运动。–解决方法：基于区域的运动估计非常大的运算量–解决方法1：快速算法，牺牲部分精度–解决方法2：多分辨率运动估计目录EBMA的问题可变形块匹配算法(DBMA)–基于节点的运动模型基于网格的运动估计基于区域的运动估计全局运动估计–直接估计法–间接估计法多分辨率运动估计–分层块匹配算法(HBMA)小结可变形块匹配算法过程：1.将锚定帧分割成多个规整的块2.对每个块采用较复杂的运动模型（如仿射，双线性或投影映射）3.对每个块进行独立的运动参数估计xm,3xm,2Bmxm,4xm,1B’m6.5可变形块匹配算法仍然不能解决块内存在多个运动的问题，块效应和光照效应等问题。仿射(6个参数):–三角形映射ybxbbyaxaayxdyxdyx210210),(),(xybybxbbxyayaxaayxdyxdyx32103210),(),(双线性(8个参数):–四边形映射6.5.1基于节点的运动表示假设–在块中选择若干个控制节点，这些节点能够自由运动–而且任何中间点的位移可以通过节点的位移内插得到。令K表示控制节点数，dm,k表示Bm中控制节点的运动矢量，则块的运动函数可以表示为：mkmkmKkmBddxx,)(,,1mkmKkkmBxxx,1)(1)(0,,1,其中的贡献期望值个控制点对中第取决于内插核xk)(,mkmBx6.5.1基于节点的运动表示控制点举例：块角点其他点的运动通过角点dm,k的运动矢量插值得到。控制点的运动矢量可以是整数像素精度或者半像素精度，所有控制点的运动参数同等重要。平移，仿射，双线性是这个模型的特例。mkmkmKkmBddxx,)(,,1内插公式K=1，退化为平移模型K=3，对应于仿射运动模型K=4，对应于双线性运动模型Kkkk1)()(dxxd第k个节点对像素x的贡献，称内插核6.5.2基于节点模型的运动估计搜索方法:–穷尽搜索法:•实际中要同步搜索K个节点的运动矢量，搜索维度高，不可行。–梯度下降法:•牛顿-拉夫森搜索算法•搜索的结果依赖于初始解。好的初始解可通过EBMA得到。212)]())(([21xxxdxE匹配函数:Kkkk1)()(dxxd其中DBMA的问题块边界会产生运动的不连续性，是由于节点的运动矢量是从每个块中独立预测得到的。–解决方法：基于网格的运动估计当块内有多物体运动或者因照明产生变化时，DBMA效果不好–三模型法：•先对每个块实行EBMA•EBMA误差小的块具有平移运动•EBMA误差大的块具有非平移运动–对这些块运用DBMA目录EBMA的问题可变形块匹配算法(DBMA)–基于节点的运动模型基于网格的运动估计基于区域的运动估计全局运动估计–直接估计法–间接估计法多分辨率运动估计–分层块匹配算法(HBMA)小结基于网格的运动估计(a)使用三角形网格(b)使用四边形网格当前帧被分割为不重叠的多边形单元（网格），运动估计为网格的每个节点在参考帧找到对应点（即得到其运动矢量），其余点的位移矢量由节点的运动矢量插值得到。基于网格的运动估计(a)基于块匹配的运动估计(b)基于网格的运动估计(c)基于网格的运动跟踪基于网格的运动估计单元内像素的运动由节点的运动矢量内插得到•每个网格节点只有一个运动矢量，与其相邻的所有多边形单元共享此运动矢量mKkkmnkmmDmxdxxd,)()(1),(,基于网格的运动估计主要步骤–建立网格•规则网格•自适应网格复杂运动的区域节点密集，简单运动的区域节点稀疏–节点运动估计•最小化位移帧差函数–二阶梯度迭代•先后顺序–光栅扫描–根据节点处图像梯度值–分组自适应三角形网格的建立图像梯度较大：区域运动较复杂预测误差较大：此区域的运动模型建模失效SG（x,y）和PPE（x,y）非零时：网格节点密集图像梯度预测误差)1,(~)1,(~),1(~),1(~),(2222yxyxyxyxyxSG0),(),(yxSGTyxSGSG),(ˆ),(~),(22yxyxyxPPE0),(),(yxPPETyxPPEPPE如果如果:),(~2yx重建图像:),(ˆ2yx运动补偿图像节点运动估计更新第n个节点的运动矢量时，其余节点的运动矢量保持不变S(n)表示与第n个节点相连接的多边形单元的误差函数•全搜索法•基于梯度下降的方法2,2,212121,(,)2111[(())()]21[(())()]2mmmMmmKMmknmkmkExxxdxxxxdx)(minarg)()()1(nnSlnlnEnuddu)(221)(,2)](~))(([21nSmmnSmxExxxd节点运动估计步骤–节点运动估计初始值：块匹配法–按顺序迭代估计每个节点•给定某个节点，固定其他节点•在不改变拓扑结构的范围内移动该节点，计算误差函数•最小化误差函数更新的运动矢量–满足某条件，终止迭代每个节点的更新过程–全搜索–梯度下降基于网格的运动估计基于网格全搜索块匹配(半像素精度)参考帧当前帧预测图像基于网格的运动估计与块匹配法的比较网格–当前帧可以分成规则的或不规则的网格–参考帧中的不规则网格是不重叠的–每个节点只有一个运动矢量可变形块–当前帧分成规则的网格–参考帧中的不规则网格是重叠的–每个节点有多个运动矢量不可变形块–当前帧分成规则的网格–参考帧中的规则网格是重叠的目录EBMA的问题可变形块匹配算法(DBMA)–基于节点的运动模型基于网格的运动估计基于区域的运动估计全局运动估计–直接估计法–间接估计法多分辨率运动估计–分层块匹配算法(HBMA)小结基于区域的运动估计将视频图像分割为多个区域，每个区域对应一个特定的运动，然后为每个区域估计运动参数区域分割：力图区域内的所有像素的运动具有一致性，可以由一个运动模型表示运动模型：仿射模型、双线性模型、投影模型方法分类–区域优先–运动优先–联合区域分割和运动估计基于区域的运动估计区域优先的方法–基于当前帧的纹理、边缘信息进行区域分割•局部区域的直方图•区域连接增长–为每个区域估计运动参数2211[((;))]()]2nnRExxdxax);(naxd表示当前帧第n个区域Rn中像素x的运动矢量区域误差函数：na表示Rn的运动参数矢量可以是仿射、双线性、投影运动模型中的任意一种基于区域的运动估计运动优先的方法–首先估计整个运动场•光流、像素、块、网格等方法–运动场分割•聚类：将具有相似运动矢量的像素进行聚合，形成区域。•分层：分成主导运动和次主导运动，从占主导的区域开始，剔除误差较大的区域，得到第一层；然后进一步剔除区域，直到没有剔除区域。基于区域的运动估计联合区域分割和运动估计的方法–区域分割和运动估计相互依赖，相辅相成。–可交替进行区域分割和运动估计目录EBMA的问题可变形块匹配算法(DBMA)–基于节点的运动模型基于网格的运动估计基于区域的运动估计全局运动估计–直接估计法–间接估计法多分辨率运动估计–分层块匹配算法(HBMA)小结全局运动估计整幅图像的运动可以用单一的运动模型表示通常指摄像机相对于静止场景运动产生的运动整个场景作为一个整体运动（很少发生）。方法–直接估计法–间接估计法全局运动估计直接估计法–误差函数：2211()[((;))]()]2Ewxxxdxaxa表示全局运动参数矢量可以是仿射、双线性、投影运动模型中的任意一种)(xw为权值系数，调节可减小与全局运动不匹配的像素对误差函数的影响。)(xw是的线性函数，即全局运动估计间接估计法–假设已经得到一些特征点的运动矢量–匹配误差函数：2]);()[(21nnnnwEdaxdanxnd);(axdnaxAaxd)();(nn对上式求偏导并令其为零，可得运动参数：nnTnnnTnnwnwdxAxAxAa)]()[()]([)]()[(1目录EBMA的问题可变形块匹配算法(DBMA)–基于节点的运动模型基于网格的运动估计基于区域的运动估计全局运动估计–直接估计法–间接估计法多分辨率运动估计–分层块匹配算法(HBMA)小结多分辨率运动估计前面介绍的运动估计方法存在的问题–最小化误差函数可能收敛到局部最小值–最小化误差函数过程的计算量很大多分辨率运动估计可有效解决这两个问题–首先在最小分辨率层（由空间低通滤波和欠取样获得）进行运动估计，并把结果作为下一层的初始解。–然后每层依次进行运动估计，每层的运动估计结果都将作为下一层的初始解–每层的运动估计可使用前面介绍的方法，如基于光流、像素、块、网格等运动估计方法多分辨率运动估计分辨率增加层1层2层3可由空间低通滤波和欠取样得到多分辨率运动估计优点–运动场接近最优解的概率更大•较小分辨率层上，误差函数可以接近全局最小值，通过插值，获得高分辨率上的初始解，最后到达最大分辨率时，误差函数接近全局最小值的可能性更大。–计算量比直接在最大分辨率上进行运动估计时要小•较小分辨率层上，搜索范围限制在较小的范围。多分辨率运动估计分层块匹配法当前帧参考帧多分辨率运动估计分层块匹配法当前帧参考帧多分辨率运动估计分层块匹配法多分辨率运动估计分层块匹配法的计算量–假设图像大小为MxM，块尺寸为NxN，所有层都使用的搜索范围–第l层的块数为，每个块进行全搜索的运算量为–总运算量：–直接在最大分辨率上总运算量：–计算量降低倍数LLLLllLLMsMsMs2221221122144)41(34]1)2/(2[3]2/[]1)2/(2[334)12(32222MsMs12/Ls)3(12)2(3432LLL2)]2/([lLNM221]1)2/(2[3NsL总结基于光流的运动估计–光流方程；平滑约束基于像素的运动估计–像素递归法基于块的运动估计–块匹配•快速算法–可变形块基于网格的运动估计基于区域的运动估计全局运动估计多分辨率运动估计作业Assignment–Prob.6.9,6.10