运动估计算法比较

《运动估计算法比较》由会员分享，可在线阅读，更多相关《运动估计算法比较（10页珍藏版）》请在金锄头文库上搜索。

1、 大作业 几种运动估计算法比较 一 实验内容 简要介绍各种运动估计算法 并比较不同运动估计算法的性能 主要考虑各算法的运算 速度和精度 二 实验背景 视频原始图像中存在着大量的信息冗余 如时间冗余 空间冗余 信息熵冗余 谱间冗 余 几何结构冗余 视觉冗余和知识冗余等等 运动估计是视频压缩编码中的核心技术之一 采用运动估计和运动补偿技术可以消除视频信号的时间冗余以提高编码效率 如何提高运动 估计的效率 使运动估计算法的搜索过程更健壮 更快速 更高效成为目前研究的热点 运动估计的基本思想是尽可能准确地获得序列图像帧间的运动位移 即运动矢量 因为 运动估计越准确 预测补偿的图像质量越高 补偿的残差就

2、越小 补偿编码所需位数越少 需要传输的比特率就越小 利用得到的运动矢量在帧间进行运动补偿 补偿残差经过变换 量化 编码后与运动矢量一起经过熵编码 然后以比特流形式发送出去 运动估计算法多种多样 大体上可以把它们分成四类 块匹配法 递归估计法 贝叶斯 估计法和光流法 其中块匹配运动估计算法因其具有算法简单 便于 VLSI 实现等优点得到 广泛应用 所以本文将重点介绍块匹配运动估计算法 并对各种块匹配算法在计算速度和估 计精度上进行简单比较 三 实验原理 一 像素递归技术 像素递归技术是基于递归思想 在连续帧中像素数据的变化是因为物体的移位引起的 郑么如果沿着梯度方向在某个像素周圈的若干像素作迭代

3、运算 运算会最后收敛于一个固定 的运动估计矢量 从而预测该像素的位移 二 块匹配运动估计 块匹配运动估计是把图像帧划分为若干互不重叠的块 并以块为单位寻找目标帧中每块 在参考帧 上一帧或者其它帧 中最优匹配的块的相对位置 假设图像中每块的大小为 M N dxmax 为参考块水平方向可搜索最大位移而 dymax 为参考块垂直方向可搜索最大位移 那么基于块匹配的运动估计就是在参考帧 或者其它上一帧 的 M 2dxmax N 2dymax 候选区搜索窗口中找到和目标帧的当前大小为 M N 的块的最匹配的块则参考块的运动矢 量可用如下的数学公式描述 R 表示相关性评价函数 f m n 表示目标或当前帧

4、图像的灰度值 满足 R 为最大时的 X Y 为运动矢量 用 MV 表示 块匹配估计准则是判断块相似程度的依据 因此匹配准则的好坏直接影响了运动估计的 精度 另一方面 匹配运算复杂度 数据读取复杂度和内存管理复杂度在很大程度上取决于 所采用的块匹配准则 我们这里用到的块匹配准则是 平均绝对误差函数 Mean of Absolute Error MAE 有些文献中 MAD 演变为绝对差和 在上述匹配准则中 由于 SAD 只采用了加法和绝对值计算 便于计算和硬件实现而且 它的匹配精度与 MAD 相差不大 此外搜索精度还与块的大小 搜索窗的大小 搜索步长有关 块匹配的方法主要有 三步法 TSS 和二维

5、对数法 TDL 新三步法 NTSS 四步法 FSS 基于菱形的搜索算法 DS 和基于六边形的搜索算法 HEXBS 等 其中全搜索算法是简单也是效 果最好的一种匹配算法 通过的全搜索匹配得到的结果是全局最优的 但由于计算量很大 我们在编解码中往往不采用这种方法 而只把他作为与其他算法的一种比较 为了兼顾估算 精度和运算速度 人们提出了一系列的快速算法 快速算法通过限制搜索位置的数目来减小 计算复杂度 但不利于估计小的运动且搜索容易陷入局部最优 下面我们将详细介绍各种基 于块的匹配算法 快速算法基于一下假设 认为误差函数在整个搜索区域内有唯一极小值点 并假设误差 函数曲面值随偏离最小值点距离是单调

6、递增的 另外运动矢量还满足中心偏执性 即块的运动矢量基本上都是在一个中心位置集中了绝 大部分运动矢量 而且随着运动矢量的位置远离中心其数逐渐减少 通过对常用视频序列的 运动矢量分布作了更为详细的统计分析发现 运动矢量以不同的比例集中分布在中心附近的 特定区域内 如下图 有大约 81 80 的运动矢量分布在中心附近范围 2 的正方形区域内 25 个点 大约 77 52 的运动矢量分布在中心附近范围 2 的菱形区域内 13 个点 更有大约 74 76 的矢量集中分布在中心附近范围 2 的十字形区域内 9 个点 1 全搜索运动估计 FS 全搜索法 Full Search Method FS 也称为穷

7、尽搜索法 是对 M 2dx N 2dy 搜索范围内所有可能的候选位置计算 MAD i j 值 从中找出最小 MAD 其对应偏移量即为 所求运动矢量 此算法虽计算量大 但最简单 可靠 找到的必为全局最优点 FS 算法描述如下 从原点出发 按顺时针螺旋方向由近及远 在逐个像素处计算 MAD 值 直到遍历搜索范围内听有的点 然后在计算的所有点的 MAD 中找到最小值 该点所在 位置即对应最佳运动矢量 但是正因为它是穷尽搜索因此会产生巨大的计算量如 7 7 的搜索区间每个宏块 16 16 需计算 225 个 MAD 值 这就直接制约了编码的实时实现 快速算法本质上是一种穷尽搜索 法其计算量仍是相当巨大

8、的 全搜索算法是简单也是效果最好的一种匹配算法 通过的全搜索匹配得到的结果是全局 最优的 但由于计算量很大 我们在编解码中往往不采用这种方法 而只把他作为与其他算 法的一种比较 2 快速匹配算法 运动矢量的中心偏执性 1 三步法 三步法是应用得相当广泛的一种次优的运动估计搜索算法它的搜索区间一般为 7 7 即在候选区中与编码块相同坐标位置处为原点 将参考块在其上下左右距离为 7 的范围内按 照一定规律移动移到一个位置就做匹配计算它总共进行了三步搜索在下一次搜索时步长减 半以前一步搜索得到的最优点为中心 下图为三步法的搜索示意图 算法的中心思想是 采用一种由粗到 细的搜索模式 从原点开始 按一定

9、步长 取周围 8 个点构成每次搜索的点群 然后 进行匹配计算 利用上一步搜索得到的最 小块误差 MBD 点作为当前搜索的中心位 置 每做一步 搜索的步长减 1 步搜索算法搜索窗选取 7 7 最多 只需要做 25 个位置的匹配计算 相对于全 搜索来比 大大减少了匹配运算的复杂度 而且数据读取比较规则 2 新三步法 TSS 假定运动矢量分布特点是在搜索窗口中均匀分布 但事实证明运动矢量是偏置中 心的 Renxiang Li 等人在 TSS 的基础上提出了一种增强运动矢量中心偏置搜索和减小补偿误 差的新三步法 NTSS 是对 TSS 的一个改进 对运动量比较小的视频序列如可视电话序列有比较好的性 能

10、 对于绝大多数的视频序列 运动矢量的分布都是在中心位置上的概率最大 随着与中心 位置的距离的增大 概率会急剧地下降 这也就是前面所说的运动矢量的中心偏移 特性 运动量比较小的视频序列的这一特 性会更加明显 NTSS 算法在最好的情况下只需要做 17 个点的匹配 在最坏的情况下需要做 33 个点的匹配 由于运动矢量中心偏置在现 实视频序列中是普遍存在的 在通常情况 下 NTSS 算法需要做 33 点匹配的概率比 三步法 TSS 搜索示意图 新三步法 NTSS 搜索示意图 较小 因此 在低速率视频应用中 如视频电话或视频会议中 NTSS 算法的优点可以得到 较好的发挥 3 四步法 四步法 Four

11、 Step Search 4SS 由 Po Lai man Ma Wing chung 等人提出 FSS 也是基于视频 序列图像的运动矢量的中心偏置特征 以原点为中心 在 5 5 大小的正方形中构造 9 个检测 点的搜索模型 每一步将搜索模型的中心移向 MBD 点处 且后两步搜索模式取决于 MBD 点的位置 与 NTSS 一样 当运动较小时 FSS 也会很快结束搜索过程 只需要 2 到 3 步即 可 新三步搜索法考虑了块矢量中心偏置 的特性 在初步搜索时对中心周围的位置同 时做了匹配运算 在物体做小范围运动时 这种改进很见效 可以大大减少运算量 然 而 在物体做大范围运动时 这种改进却带 来了

12、额外的运算量 因为新三步算法最多需 要做 33 次运算 而三步算法最多只需要做 25 次运算 四步搜索法考虑到了块的中心 匹配的特性 同时兼顾了物体的大范围运动 这种改进在物体既有小范围运动又有大范围运 动时可以得到较好的性能 实验的结果表明 4SS 算法比 TSS 算法有更好的性能 与 NTSS 算 法有相似的性能 但在物体大范图运动时 4SS 算法有更强的鲁棒性 4 菱形搜索法 菱形搜索 DS 算法于 2000 年被提出 经过多次改进 已成为目前快速块匹配运动估计 算法中性能最好的算法之一 搜索模板的形状和大小不但影响整个 算法的运行速度 而且也影响它的性能 块 匹配的误差实际上是在搜索范

13、围内建立了 误差表面函数 全局最小点即对应着最佳运 动矢量 由于这个误差表面通常并不是单调 的 所以搜索窗口太小 就容易陷入局部最 优 例如 BBGDS 算法 其搜索窗口仅为 3 四步法 TSS 搜索算法 菱形 DS 搜索法 3 而搜索窗口太大 又容易产生错误的搜索路径 像 TSS 算法的第一步 另外 统计数 据表明 视频图像进行运动估计时 最优点通常在零矢量周围 当物体相对静止 运动矢量较小时 DS 算法进行的运算要明显少于上述其他算法 我 们以 4SS 算法为例 假设当运动矢量范围为 l 时 4SS 算法需要搜索 17 各位置 而 DS 算法 最少需要搜索 13 个位置 最多只需要搜索 1

14、6 个位置 矢量范围加大时 DS 算法需要进行 搜索的位置数明显要少于 4SS 算法 实验的结果表明 DS 算法在性能相当情况下比 4SS 算法 的速度快 31 5 基于块的梯度下降搜索算法 基于块的梯度下降搜索法 BBGDS 是 1996 年由 Lurng Kuo Li 和 Ephraim Feig 提出的 该 算法采用了一个非常偏向于中心位置的搜索模式 步长为 1 的 9 点搜索 如图 2 7 所示 它不限制搜索的步数 当某一步的最小 BDM 点位于中心位置或该步已到达搜索窗口的边缘 时 则停止搜索 与 FSS 的某些搜索步骤一样 BBGDS 的每个后续搜索步骤都是增加 3 个 或 5 个

15、搜索点 这个算法非常适合于小运 动量的场合 在每一步搜索过程中 BBGDS 算法使 用了中心匹配块而不是匹配块 降低了陷 入局部最优的可能性 利用梯度下降的方 向来指导搜索方向 对该方向进行重点搜 索 从而减少和避免了不必要的搜索 大 大降低了算法的复杂度 基于块的梯度下降搜索算法 四 实验步骤 具体实验步骤如下 读入视频两帧图像 分别采用上述各种运动估计方法计算运动矢量补偿出预测图像 分 析比较各种算法性能 五 实验结果分析 我们取视频的第 1 和第 3 帧进行各种运动补偿 实验参数如下 块大小 16x16 搜索范围 dmax 7 搜索精度 1 像素 视频大小 720 400 一 全搜索运动

16、估计 运动估计结果 参考帧 当前帧 预测图像 补偿误差 Matlab 运行时间是 3 963858 重构图像 PSNR 值 38 0220 二 三步法运动估计 运动估计结果 预测图像 补偿误差 Matlab 运行时间是 0 909280 重构图像 PSNR 值 35 4990 三 新三步法运动估计 运动估计结果 预测图像 补偿误差 Matlab 运行时间是 0 900035 重构图像 PSNR 值 37 2834 四 四步法运动估计 运动估计结果 预测图像 补偿误差 Matlab 运行时间是 0 948070 重构图像 PSNR 值 37 4156 五 菱形法运动估计 运动估计结果 预测图像 补偿误差 Matlab 运行时间是 1 178112 重构图像 PSNR 值 37 7799 六 基于块的梯度下降搜索算法 运动估计结果 预测图像 补偿误差 Matlab 运行时间是 0 853036 重构图像 PSNR 值 37 6766 结果分析 通过实验我们得到各种各种匹配算法的 Matlab 执行时间 重构图像和重构图像的 PSNR 值 Matlab 执行时间反映了算法的执行效率 图像重构