一种基于降采样的块匹配三步搜索改进算法

An Improved Three Step Search Algorithm Based on Down-Sampled Block Matching

在视频图像处理中,运动估计对于提高视频信号去隔行和降噪的效果具有举足轻重的作用,是整个运动补偿视频图像处理算法的关键部分.在视频处理芯片的硬件实现中,运动估计的性能和算法复杂度直接决定了芯片的速度、面积和功耗;同时,运动估计在视频图像编码中也同样决定了整个编码算法的效率.在新三步算法的基础上权衡运动估计算法的性能和运算复杂度,提出了一种块内降采样的搜索算法(down-sampled diamond NTSS,DSD-NTSS).该算法利用图像的局部相似性特征,对搜索块的内部像素采用交叉采样方式做块匹配的运算以降低算法复杂度.仿真结果表明,在保证了同等的图像处理质量的情况下,该算法与新三步法相比运算量降低了一半左右;而与全搜索、菱形搜索、三步搜索等其他快速算法相比,该算法在性能和算法复杂度上的综合表现更为优秀.

In video processing,motion estimation plays an important role in video de-interlace and de-noise,being a key part of the motion compensation algorithms.The performance and complexity of motion estimation algorithm have a direct impact on speed,area and power consumption of video processing chips.Also,motion estimation determines the efficiency of coding algorithms in video compression.This paper proposes a Down-sampled Diamond NTSS algorithm（DSD-NTSS） based on New Three Step Search（NTSS） algorithm,taking both performance and complexity of motion estimation algorithms into consideration.According to the local similarity of the image cross sampling is adopted for block matching to reduce the computation cost.Experiment results show that DSD-NTSS is a good tradeoff between performance and complexity.Compared with NTSS,the proposed DSD-NTSS reduces half the computation cost,keeping the equivalent image quality.While compared with Four Step Search（FSS）、Diamond Search（DS）、Three Step Search（TSS） and some other fast searching algorithms,the proposed DSD-NTSS is comprehensively better in performance and complexity.