Please use this identifier to cite or link to this item:
Title: A novel unrestricted center-biased diamond search algorithm for block motion estimation
Authors: Tham, J.Y. 
Ranganath, S. 
Ranganath, M.
Kassim, A.A. 
Keywords: Block matching
Center-biased search strategy
Diamond search pattern
Fast motion compensation
Video compression
Issue Date: 1998
Citation: Tham, J.Y.,Ranganath, S.,Ranganath, M.,Kassim, A.A. (1998). A novel unrestricted center-biased diamond search algorithm for block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology 8 (4) : 369-377. ScholarBank@NUS Repository.
Abstract: The widespread use of block-based interframe motion estimation for video sequence compression in both MPEG and H.263 standards is due to its effectiveness and simplicity of implementation. Nevertheless, the high computational complexity of the full-search algorithm has motivated a host of suboptimal but faster search strategies. A popular example is 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 search (NTSS) which has a center-biased search pattern and supports a halfway-stop technique. It is faster on the average, and gives better motion 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 NTSS in terms of motion compensation errors. In this paper, we propose a novel unrestricted center-biased diamond search (UCBDS) algorithm which is more efficient, effective, and robust than the previous techniques. 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 the above methods in which both the processing speed and the accuracy of motion compensation are tested over a wide range of test video sequences. © 1998 IEEE.
Source Title: IEEE Transactions on Circuits and Systems for Video Technology
ISSN: 10518215
DOI: 10.1109/76.709403
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jan 29, 2023

Page view(s)

checked on Feb 2, 2023

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.