Comparative Study of Three Step Search and Diamond Search Algorithm for Motion Estimation

Authors

  • Subhash Chandra Yadav Department of Electronics and Communication Engineering, Graphic Era University, Dehradun, India
  • Ria Department of Electronics and Communication Engineering, Graphic Era University, Dehradun, India

Keywords:

Motion Estimation, SAD, Diamond Search, Three Step Search, VLSI Architecture, PSNR

Abstract

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

Download data is not yet available.

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

Downloads

Published

2023-02-28

How to Cite

Yadav, S. C., & Ria. (2023). Comparative Study of Three Step Search and Diamond Search Algorithm for Motion Estimation. Journal of Graphic Era University, 4(2), 66–71. Retrieved from https://journal.riverpublishers.com/index.php/JGEU/article/view/118

Issue

Section

Articles