摘要
针对视频图像的运动估计问题,提出了一种无回溯搜索的快速块匹配算法.算法基于快速模式匹配KMP算法思想,将图像中的块匹配转化为一个一维的串模式匹配.利用子块的自匹配特性,计算子块中每一个像素的next值.当模式中第j个像素与主块中的像素"失配"时,从子块的next数组中找到第r个像素继续比较,不需要回溯到开始匹配的位置.对具有不同复杂运动的视频图像进行实验,结果表明:在搜索窗口大小为(-12,-12)×(12,12)的区域内,与六边形搜索算法相比,在运算速度相同的条件下,本算法可大幅度提高运动估计的精度.
A non-backtracking searching algorithm for block matching in video was proposed to address the problem of motion estimation. Based on the idea of the KMP algorithm of character string for fast pattern matching, our algorithm converts the block matching in the video image into the pattern matching of a character string. The next function value of each pixel in the sub-block can be easily obtained by taking advantage of the self-matching trait of the block. And the rth pixel from the next array of the block can also be found out to keep the comparing without backtracks to the start position of matching while the jth pixel matching is lost. Experimental results on videos of various motion have shown that our NBT algorithm has a great improvement in the searching precision when the searching area is restricted to （ -12, -12） × （12, 12）, as compared with the HEXBS.
出处
《湖南大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2008年第6期72-76,共5页
Journal of Hunan University:Natural Sciences
基金
国家自然科学基金资助项目(60673093)
湖南省自然科学基金资助项目(06JJ2065)
长江学者和创新团队发展计划资助项目
关键词
运动估计
无回溯
块匹配
失配
中心偏置
motion estimation
non-backtracking
block matching
mismatching
center-blased
