一种基于遗传搜索和模板匹配的运动估计方法

摘要

本发明公开了一种基于遗传搜索和模板匹配的运动估计方法，属于视频压缩编码技术领域。该方法包括如下步骤：采用多种方法对待编码帧中的待编码块进行预测，得到多个预测运动矢量；分别对搜索窗中各预测运动矢量指向的点进行搜索，并采用三种终止策略进行判断，满足则结束搜索；利用初始模板进行种群初始化，对种群循环进行复制、交叉、选择操作，直至满足遗传终止条件，在此基础上对相邻点进行搜索，以搜索得到的匹配块对待编码块进行编码；遍历整帧图像，完成整帧图像的编码。本发明结合运动矢量的统计特性设置了三种终止策略，并且混合使用模板匹配和遗传搜索算法，在保证编码质量的同时大幅减少了运动估计的时间。

主权项

1.一种基于遗传搜索和模板匹配的运动估计方法，其特征在于包括以下步骤：（1）以待编码帧的前一个已编码帧为当前参考帧；对待编码帧的其中一个待编码块分别采用中值滤波、上层块预测、相邻帧预测的方法进行预测，相应得到该待编码块的中值预测运动矢量、上层块预测运动矢量和相邻帧预测运动矢量；同时采用中值滤波的方法预测该待编码块的SAD值；（2）由所述待编码块的坐标加上所述中值预测运动矢量，得到当前参考帧的搜索中心点；计算得到以所述搜索中心点为起始点的块的SAD值；判断是否满足第一终止策略的条件：若满足，则以所述搜索中心点为最优点，并执行步骤（10）；若不满足，则执行步骤（3）；所述第一终止策略如式（1）所示，若y₁=1，则表示满足第一终止策略的条件；否则表示不满足第一终止策略的条件；y₁=[(SAD-Pred_SAD)<TH1]&&(Pred_mv==0)              (1)式（1）中，SAD表示以所述搜索中心点为起始点的块的SAD值；Pred_SAD表示所述预测的待编码块的SAD值；Pred_mv表示所述中值预测运动矢量；TH1表示第一阈值，所述第一阈值由式（2）计算得到；TH1=TH_static/TH_factor                           (2)式（2）中，TH_static表示预设的参数；TH_factor表示阈值因子，所述阈值因子由式（3）计算得到；式（3）中，blocktype表示所述待编码块的类型，1表示16x16类型块，2表示16x8类型块，3表示8x16类型块，4表示8x8类型块，5表示8x4类型块，6表示4x8类型块，7表示4x4类型块；（3）由所述待编码块的坐标分别加上所述上层块预测运动矢量和相邻帧预 测运动矢量，相应得到上层块预测搜索点和相邻帧预测搜索点；分别以所述待编码块的起始点、搜索中心点、上层块预测搜索点和相邻帧预测搜索点为中心点，得到各所述中心点的水平和垂直方向的相邻点；计算每个以所述中心点为起始点的块和每个以所述相邻点为起始点的块的SAD值，从中得到当前最小SAD值；（4）判断是否满足第二终止策略的条件：若满足，则以所述当前最小SAD值所对应的块的起始点作为最优点，并执行步骤（10）；若不满足，则判断是否满足第三终止策略的条件：若满足，则执行步骤（9）；若不满足，则执行步骤（5）；所述第二终止策略如式（4）所示，若y₂=1，则表示满足第二终止策略的条件；否则表示不满足第二终止策略的条件；y₂=(min_SAD-Pred_SAD<TH1)                (4)式（4）中，min_SAD表示步骤（3）所述的当前最小SAD值；Pred_SAD表示所述预测的待编码块的SAD值；TH1表示所述第一阈值；所述第三终止策略如式（5）所示，若y₃=1，则表示满足第三终止策略的条件；否则表示不满足第三终止策略的条件；y_3＝[abs(MV_x-Pred_MV_x)<=2]&&[abs(MV_y-Pred_MV_y)<=2]&&[(min_SAD-Pred_SAD)<TH2]  (5)式（5）中，abs()表示取绝对值函数；MV_x、MV_y分别表示步骤（3）所述当前最小SAD值对应块的运动矢量的x、y分量；Pred_MV_x、Pred_MV_y分别表示步骤（2）所述中值预测运动矢量的x、y分量；min_SAD表示步骤（3）所述当前最小SAD值；Pred_SAD表示所述预测的待编码块的SAD值；TH2表示第二阈值，所述第二阈值由式（6）计算得到；TH2=TH_DS/TH_factor                               (6)式（6）中，TH_DS为预设的参数；TH_factor表示所述阈值因子；（5）以步骤（2）所述搜索中心点为中心设计初始模板，计算初始遗传种群中的每个个体的SAD值，所述初始遗传种群的每个个体分别对应为以所述初始模板所覆盖的各个点为起始点的块；（6）判断是否满足遗传终止策略：若满足，则执行步骤（9）；若不满足，则对当代遗传种群中与最小SAD值对应的个体进行三次复制、对与第二小SAD 值对应的个体进行两次复制、并舍弃与最大的三个SAD值对应的三个个体，再对其余每个个体复制一次；（7）对步骤（6）复制得到的每个复制个体进行一次变异操作得到对应的变异个体，并计算每个所述变异个体的SAD值；从所述复制个体和与其对应的变异个体中选择其SAD值较小者进入下一代遗传种群；（8）判断所述当代遗传种群是否达到预设的种群迭代阈值：若已达到，则执行步骤（9）；否则，执行步骤（6）；（9）以所述当代遗传种群中与最小SAD值对应的块的起始点作为中心点，在该中心点的水平和垂直方向得到四个相邻点，分别计算以该四个相邻点为起始点的各个块的SAD值，从中选取与最小SAD值对应的块的起始点为最优点；（10）对以所述最优点为起始点的匹配块进行编码；判断当前参考帧与所述待编码帧之间的已编码帧的帧数是否小于预设的最大参考帧数：若小于，以该当前参考帧的前一个已编码帧作为当前参考帧并返回执行步骤（2）；否则完成所述待编码块的编码，并执行步骤（11）；（11）遍历所述待编码帧，判断是否还存在待编码块；若存在，则返回步骤（1）对下一个待编码块进行编码；若不存在，则结束。