Comparative Study of Three Step Search and Diamond Search Algorithm for Motion Estimation
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%.
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.