Comparative Study of Three Step Search and Diamond Search Algorithm for Motion Estimation
Keywords:
Motion Estimation, SAD, Diamond Search, Three Step Search, VLSI Architecture, PSNRAbstract
Over the last couple of decades, video processing and coding/decoding has grown exponentially. The processing
power of the computers available has grown in almost equal proportions. However, with the introduction of newer
video standards, which are further more complex, it has become imperative to work on more optimized algorithms
and implement them efficiently and judiciously. A number of parallel implementations of the algorithms have
also been introduced, including using reconfigurable systolic arrays for the same. In this paper, we compare the
two most commonly used search algorithms, Diamond Search and Three Step Search for motion estimation and
decide which one is better for a given type of video sequence. This information can help in better decision making
regarding the choice of the algorithm for a certain video sequence and save time by as much as 50%.
Downloads
References
Furht, B., Greenberg, J., & Westwater, R. (2012). Motion estimation algorithms for video compression (Vol. 379).
Springer Science & Business Media.
Hsieh, C. H., & Lin, T. P. (1992). VLSI architecture for block-matching motion estimation algorithm. IEEE
Transactions on Circuits and Systems for Video Technology, 2(2), 169-175.
Komarek, T., & Pirsch, P. (1989, May). VLSI architectures for block matching algorithms. In Acoustics, Speech,
and Signal Processing, 1989. ICASSP-89., 1989 International Conference on (pp. 2457-2460). IEEE.
Li, R., Zeng, B., & Liou, M. L. (1994). A new three-step search algorithm for block motion estimation. IEEE
transactions on circuits and systems for video technology, 4(4), 438-442.
Lin, S. S. (2004). Low-power motion estimation processors for mobile video application (Doctoral dissertation,
MS thesis, Graduate Institute of Electronic Engineering, National Taiwan University, Taipei, Taiwan).
Lin, Y. L. S., Kao, C. Y., Kuo, H. C., & Chen, J. W. (2009). VLSI Design for Video Coding: H. 264/AVC
Encoding from Standard Specification to Chip. Springer Science & Business Media.
Yang, K. M., Sun, M. T., & Wu, L. (1989). A family of VLSI designs for the motion compensation block-matching
algorithm. IEEE Transactions on Circuits and Systems, 36(10), 1317-1325
