A Block Matching Algorithm for Motion Estimation Based on Non-Backtracking Searching Method
Chen Shu · Journal of Hunan University · 2008
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.