A Fast Motion Estimation Algorithm Based on Diamond and Octagon Search Patterns

摘要

Based on the directional characteristic of SAD(Sum of Absolute Difference) distribution and the centerbiased characteristic of motion vectors, a fast blockmatching motion estimation algorithm, DOS(Diamond and Octagon Search), is proposed in this paper. Firstly, DOS employs Diamond Search Pattern(DP) to judge if the MBD(Minimum Block Distortion) point is near the initial search center by one pixel, if the MBD point is not within the circular area with a radius of one pixcl, Octagon Pattern(OP) may be used to locate the best matching block with large motion vector, and diamond search pattern(DP) to refine the motion vector. Experimental results show that the proposed DOS algorithm can reduce the computational complexity of the block-matching motion estimation remarkably while incurring little, if any, loss in quality.