doi: 10.17586/2226-1494-2016-16-3-474-481


HIERARCHICAL ADAPTIVE ROOD PATTERN SEARCH FOR MOTION ESTIMATION AT VIDEO SEQUENCE ANALYSIS

Nguyen Van Truong, A. A. Tropchenko


Read the full article  ';
Article in Russian

For citation: Nguyen Van Truong, Tropchenko A.A. Hierarchical adaptive rood pattern search for motion estimation at video sequence analysis. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2016, vol. 16, no. 3, pp. 474–481. doi: 10.17586/2226-1494-2016-16-3-474-481

Abstract

Subject of Research.The paper deals with the motion estimation algorithms for the analysis of video sequences in compression standards MPEG-4 Visual and H.264. Anew algorithm has been offered based on the analysis of the advantages and disadvantages of existing algorithms. Method. Thealgorithm is called hierarchical adaptive rood pattern search (Hierarchical ARPS, HARPS). This new algorithm includes the classic adaptive rood pattern search ARPS and hierarchical search MP (Hierarchical search or Mean pyramid). All motion estimation algorithms have been implemented using MATLAB package and tested with several video sequences. Main Results. The criteria for evaluating the algorithms were: speed, peak signal to noise ratio, mean square error and mean absolute deviation. The proposed method showed a much better performance at a comparable error and deviation. The peak signal to noise ratio in different video sequences shows better and worse results than characteristics of known algorithms so it requires further investigation. Practical Relevance. Application of this algorithm in MPEG-4 and H.264 codecs instead of the standard can significantly reduce compression time. This feature enables to recommend it in telecommunication systems for multimedia data storing, transmission and processing.


Keywords: motion compensation, block matching algorithms, hierarchical adaptive rood pattern search, block matching, similarity evaluation

References

1. Turaga D., Alkanhal M. Search Algorithms for Block Matching Estimation. Mid-term Project, 1998.
2. Toivonen T., Heikkilä J., Silvén O. A new algorithm for fast full search block motion estimation based on number theoretic transforms. Proc. 9th International Workshop on Systems: Signals and Image Processing. Manchester, UK, 2002, pp. 90–94.
3. Chen M.-J., Chiueh T.-D. One-dimensional full search motion estimation algorithm for video coding. IEEE Transactions on Circuits and Systems for Video Technology, 1994, vol. 4, no. 5, pp. 504–509. doi: 10.1109/76.322998
4. Li R., Zheng B., Liou M.L. A new three-step search algorithm for block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 1994, vol. 4, no. 4, pp. 438–442. doi: 10.1109/76.313138
5. Chau L.-P., Jing X. Efficient three-step search algorithm for block motion estimation in video coding. Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP. Hong Kong, 2003, vol. 3, pp. 421–424.
6. Po L.-M., Ma W.-C. A novel four-step search algorithm for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 1996, vol. 6, no. 3, pp. 313–317. doi: 10.1109/76.499840
7. Zhu S., Ma K.-K. A new diamond search algorithm for fast block-matching motion estimation. IEEE Transactions on Image Processing, 2000, vol. 9, no. 2, pp. 287–290. doi: 10.1109/83.821744
8. Cheung C.-H., Po. L.-M. A novel cross-diamond search algorithm for fast block motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 2002, vol. 12, no. 12, pp. 1168–1177. doi: 10.1109/TCSVT.2002.806815
9. Nie Y., Ma K.-K. Adaptive rood pattern search for fast block-matching motion estimation. IEEE Transactions on Image Processing, 2002, vol. 11, no. 12, pp. 1442–1449. doi: 10.1109/TIP.2002.806251
10. Nan K.M., Kin J.S., Pari R.H., Shin Y.S. A fast hierarchical motion vector estimation algorithm using mean pyramid. IEEE Transactions on Circuits and Systems for Video Technology, 1995, vol. 5, no. 4, pp. 344–351. doi: 10.1109/76.465087
11. Moschetti F., Kunt M., Debes E. A statistical adaptive block-matching motion estimation. IEEE Transactions on Circuits and Systems for Video Technology, 2003, vol. 13, no. 4, pp. 417–431. doi: 10.1109/TCSVT.2003.811363
12. Babu D.V., Subramanian P., Karthikeyan C. Performance analysis of block matching algorithms for highly scalable video compression. Proc. Int. Symposium on Ad Hoc and Ubiquitous Computing. Surathkal, India, 2006, pp. 179–182. doi: 10.1109/ISAHUC.2006.4290669
13. Barjatya A. Block Matching Algorithms For Motion Estimation. DIP 6620 Final Project Paper in Digital Image Processing. Utah State University, pp. 1–6.
14. Cuevas E., Zaldivar D., Pérez-Cisneros M., Olive D. Block-matching algorithm based on differential evolution for motion estimation. Engineering Applications of Artificial Intelligence, 2013, vol. 26, no. 1, pp. 488–498. doi: 10.1016/j.engappai.2012.08.003
15. Nguen V.T., Tropchenko A.A. Methods and algorithms for reducing temporal redundancy of video data. Proc. II Int. Conf. on Actual Problems of Science in XXI Century. Moscow, 2015, part 2, pp. 36–41.
 



Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2022 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.

Яндекс.Метрика