A NOVEL UNRESTRICTED CENTER-BIASED DIAMOND SEARCH ALGORITHM FOR BLOCKMOTION ESTIMATION

The widespread use of block-based interframe motion estimation for vid eo sequence compression in both MPEG and H.263 standards is due to its effectiveness and simplicity of implementation. Nevertheless, the hig h computational complexity of the full-search algorithm has motivated a host of suboptimal but faster search strategies. A popular example i s the three-step search (TSS) algorithm. However, its uniformly spaced search pattern is not well matched to most real-world video sequences in which the motion vector distribution is nonuniformly biased toward the zero vector. Such an observation inspired the new three-step sear ch (NTSS) which has a center-biased search pattern and supports a half way-stop technique. It is faster on the average, and gives better moti on estimation as compared to the well-known TSS, Later, the four-step search (4SS) algorithm was introduced to reduce the average case from 21 to 19 search points, while maintaining a performance similar to NTS S in terms of motion compensation errors, In this paper, we propose a novel unrestricted center-biased diamond search (UCBDS) algorithm whic h is more efficient, effective, and robust than the previous technique s, It has a best case scenario of only 13 search points and an average of 15.5 block matches. This makes UCBDS consistently faster than the other suboptimal block-matching techniques. This paper also compares t he above methods in which both the processing speed and the accuracy o f motion compensation are tested over a wide range of test video seque nces.