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

  • Ria Department of Electronics and Communication Engineering, Graphic Era University, Dehradun, India
  • Subhash Chandra Yadav 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.

Author Biographies

Ria, Department of Electronics and Communication Engineering, Graphic Era University, Dehradun, India

Ria received her B.Tech. degree in Electronics & Instrumentation Engineering from Uttar Pradesh Technical University, Lucknow in 2014. She is currently working to get the M.Tech. degree in VLSI Design & System at Graphic Era University, Dehradun, India. Her research interests mainly include signal processing, multimedia processing and reconfigurable computing.

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

Mr. Subhash Chandra Yadav is an Assistant Professor at the Graphic Era University, Dehradun, India. He completed his M.Tech. Degree from Kurukshetra University, Kurukshetra, India. His area of interest includes VLSI Design, Logic Design and Signal Processing.

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. InAcoustics, 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.

Published
2016-09-22
Section
Articles