Name
Title | ||
|---|---|---|
A novel unrestricted center-biased diamond search algorithm for block motion estimation |
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 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. 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 |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1109/76.709403 | IEEE Trans. Circuits Syst. Video Techn. |
Keywords | Field | DocType |
faster search strategy,new three-step search,novel unrestricted center-biased diamond,four-step search,search algorithm,search point,better motion estimation,motion compensation,center-biased search pattern,three-step search,block-based interframe motion estimation,block motion estimation,spaced search pattern,testing,pattern matching,computational complexity,motion estimation,transform coding,indexing terms,data compression,video compression,robustness,zero vector | Computer vision,Incremental heuristic search,Block-matching algorithm,Quarter-pixel motion,Pattern recognition,Computer science,Motion compensation,Beam search,Artificial intelligence,Motion estimation,Binary search algorithm,Motion vector | Journal |
Volume | Issue | ISSN |
8 | 4 | 1051-8215 |
Citations | PageRank | References |
291 | 24.53 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jo Yew Tham | 1 | 442 | 47.35 |
| Surendra Ranganath | 2 | 1211 | 102.74 |
| M. Ranganath | 3 | 291 | 24.53 |
| Ashraf A. Kassim | 4 | 1164 | 97.26 |