New Fast Block Matching Algorithm Using New Hybrid Search Pattern And Strategy To Improve Motion Estimation Process In Video Coding Technique

Up until today, video compression algorithm has been applied in various video applications ranging from video conferencing to video telephony. Motion Estimation or ME is deemed as one of the effective and popular techniques in video compression. As one of its techniques, the Block Matching Algorithm...

Full description

Saved in:

Bibliographic Details
Main Author:	Hamid, Nurul 'Atiqah
Format:	Thesis
Language:	English English
Published:	2016
Subjects:	T Technology (General)
Online Access:	http://eprints.utem.edu.my/id/eprint/20604/1/New%20Fast%20Block%20Matching%20Algorithm%20Using%20New%20Hybrid%20Search%20Pattern%20And%20Strategy%20To%20Improve%20Motion%20Estimation%20Process%20In%20Video%20Coding%20Technique.pdf http://eprints.utem.edu.my/id/eprint/20604/2/New%20Fast%20Block%20Matching%20Algorithm%20Using%20New%20Hybrid%20Search%20Pattern%20And%20Strategy%20To%20Improve%20Motion%20Estimation%20Process%20In%20Video%20Coding%20Technique.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utem-ep.20604
record_format	uketd_dc
institution	Universiti Teknikal Malaysia Melaka
collection	UTeM Repository
language	English English
advisor	Darsono, Abd Majid
topic	T Technology (General) T Technology (General)
spellingShingle	T Technology (General) T Technology (General) Hamid, Nurul 'Atiqah New Fast Block Matching Algorithm Using New Hybrid Search Pattern And Strategy To Improve Motion Estimation Process In Video Coding Technique
description	Up until today, video compression algorithm has been applied in various video applications ranging from video conferencing to video telephony. Motion Estimation or ME is deemed as one of the effective and popular techniques in video compression. As one of its techniques, the Block Matching Algorithm or BMA is widely employed in majority of well-known video codes due to its simplicity and high compression efficiency. As such, it is crucial to find different approaches of fast BMAs as the simplest and straightforward BMA is not a good fit for implementation of real-time video coding because of its high computational complexity. The aims for this study is to develop and design a new hybrid search pattern and strategy for new fast BMAs that can further improve the ME process in terms of estimation accuracy and video image quality, searching speed and computational complexity. There are 6 main designs that the algorithms proposed namely the Orthogonal-Diamond Search Algorithm with Small Diamond Search Pattern (ODS-SDSP), the Orthogonal-Diamond Search Algorithm with Large Diamond Search Pattern (ODS-LDSP), the Diamond-Orthogonal Search Algorithm with Small Diamond Pattern (DOS-SDSP), the Diamond-Orthogonal Search Algorithm with Large Diamond Pattern (DOS-LDSP), the Modified Diamond-Orthogonal Search Algorithm with Small Diamond Pattern (MDOS-SDSP), and the Modified Diamond-Orthogonal Search Algorithm with Large Diamond Pattern (MDOS-LDSP). These 6 algorithms are divided into 3 main methods namely Method A, Method B, and Method C depending on their search patterns and strategies. The first method involves the manipulation of the diamond pattern in the process, the second method includes the manipulation of the orthogonal steps, and lastly, the third method is the modified version of the second method to improve the performances of the algorithms. Evaluation is based on the algorithm performances in terms of the search points needed to find the final motion vector, the Peak-Signal to Noise Ratio (PSNR) of the algorithms, and the runtime performance of algorithm simulations. The result shows that the DOS-SDSP algorithm has the lowest search points with only 1.7341, 4.9059 and 4.0230 for each motion’s content respectively; meanwhile all the algorithms acquired similar and close PSNR values for all types of motion contents. As for simulation runtime, the results show that Method B has the least simulation runtime and Method C has the highest simulation runtime compared to others for all video sequences. The finding suggests that an early termination technique should be implemented at the early stage of the process, and mixing the selection of the mode is able to improve the algorithm performances. Therefore, it can be concluded that Method B gives the best performance in terms of search points reduction and simulation runtime while Method C yields the best for PSNR values for all types of motion contents.
format	Thesis
qualification_name	Master of Philosophy (M.Phil.)
qualification_level	Master's degree
author	Hamid, Nurul 'Atiqah
author_facet	Hamid, Nurul 'Atiqah
author_sort	Hamid, Nurul 'Atiqah
title	New Fast Block Matching Algorithm Using New Hybrid Search Pattern And Strategy To Improve Motion Estimation Process In Video Coding Technique
title_short	New Fast Block Matching Algorithm Using New Hybrid Search Pattern And Strategy To Improve Motion Estimation Process In Video Coding Technique
title_full	New Fast Block Matching Algorithm Using New Hybrid Search Pattern And Strategy To Improve Motion Estimation Process In Video Coding Technique
title_fullStr	New Fast Block Matching Algorithm Using New Hybrid Search Pattern And Strategy To Improve Motion Estimation Process In Video Coding Technique
title_full_unstemmed	New Fast Block Matching Algorithm Using New Hybrid Search Pattern And Strategy To Improve Motion Estimation Process In Video Coding Technique
title_sort	new fast block matching algorithm using new hybrid search pattern and strategy to improve motion estimation process in video coding technique
granting_institution	Universiti Teknikal Malaysia Melaka
granting_department	Faculty Of Electronic And Computer Engineering
publishDate	2016
url	http://eprints.utem.edu.my/id/eprint/20604/1/New%20Fast%20Block%20Matching%20Algorithm%20Using%20New%20Hybrid%20Search%20Pattern%20And%20Strategy%20To%20Improve%20Motion%20Estimation%20Process%20In%20Video%20Coding%20Technique.pdf http://eprints.utem.edu.my/id/eprint/20604/2/New%20Fast%20Block%20Matching%20Algorithm%20Using%20New%20Hybrid%20Search%20Pattern%20And%20Strategy%20To%20Improve%20Motion%20Estimation%20Process%20In%20Video%20Coding%20Technique.pdf
_version_	1747833984390266880
spelling	my-utem-ep.206042021-10-10T22:49:25Z New Fast Block Matching Algorithm Using New Hybrid Search Pattern And Strategy To Improve Motion Estimation Process In Video Coding Technique 2016 Hamid, Nurul 'Atiqah T Technology (General) TK Electrical engineering. Electronics Nuclear engineering Up until today, video compression algorithm has been applied in various video applications ranging from video conferencing to video telephony. Motion Estimation or ME is deemed as one of the effective and popular techniques in video compression. As one of its techniques, the Block Matching Algorithm or BMA is widely employed in majority of well-known video codes due to its simplicity and high compression efficiency. As such, it is crucial to find different approaches of fast BMAs as the simplest and straightforward BMA is not a good fit for implementation of real-time video coding because of its high computational complexity. The aims for this study is to develop and design a new hybrid search pattern and strategy for new fast BMAs that can further improve the ME process in terms of estimation accuracy and video image quality, searching speed and computational complexity. There are 6 main designs that the algorithms proposed namely the Orthogonal-Diamond Search Algorithm with Small Diamond Search Pattern (ODS-SDSP), the Orthogonal-Diamond Search Algorithm with Large Diamond Search Pattern (ODS-LDSP), the Diamond-Orthogonal Search Algorithm with Small Diamond Pattern (DOS-SDSP), the Diamond-Orthogonal Search Algorithm with Large Diamond Pattern (DOS-LDSP), the Modified Diamond-Orthogonal Search Algorithm with Small Diamond Pattern (MDOS-SDSP), and the Modified Diamond-Orthogonal Search Algorithm with Large Diamond Pattern (MDOS-LDSP). These 6 algorithms are divided into 3 main methods namely Method A, Method B, and Method C depending on their search patterns and strategies. The first method involves the manipulation of the diamond pattern in the process, the second method includes the manipulation of the orthogonal steps, and lastly, the third method is the modified version of the second method to improve the performances of the algorithms. Evaluation is based on the algorithm performances in terms of the search points needed to find the final motion vector, the Peak-Signal to Noise Ratio (PSNR) of the algorithms, and the runtime performance of algorithm simulations. The result shows that the DOS-SDSP algorithm has the lowest search points with only 1.7341, 4.9059 and 4.0230 for each motion’s content respectively; meanwhile all the algorithms acquired similar and close PSNR values for all types of motion contents. As for simulation runtime, the results show that Method B has the least simulation runtime and Method C has the highest simulation runtime compared to others for all video sequences. The finding suggests that an early termination technique should be implemented at the early stage of the process, and mixing the selection of the mode is able to improve the algorithm performances. Therefore, it can be concluded that Method B gives the best performance in terms of search points reduction and simulation runtime while Method C yields the best for PSNR values for all types of motion contents. 2016 Thesis http://eprints.utem.edu.my/id/eprint/20604/ http://eprints.utem.edu.my/id/eprint/20604/1/New%20Fast%20Block%20Matching%20Algorithm%20Using%20New%20Hybrid%20Search%20Pattern%20And%20Strategy%20To%20Improve%20Motion%20Estimation%20Process%20In%20Video%20Coding%20Technique.pdf text en public http://eprints.utem.edu.my/id/eprint/20604/2/New%20Fast%20Block%20Matching%20Algorithm%20Using%20New%20Hybrid%20Search%20Pattern%20And%20Strategy%20To%20Improve%20Motion%20Estimation%20Process%20In%20Video%20Coding%20Technique.pdf text en validuser https://plh.utem.edu.my/cgi-bin/koha/opac-detail.pl?biblionumber=106022 mphil masters Universiti Teknikal Malaysia Melaka Faculty Of Electronic And Computer Engineering Darsono, Abd Majid 1. Ahmed, Z., Hussain, A.J., and Al-Jumeily, D., 2011. Mean Predictive Block Matching for Fast Block Matching Motion Estimation. 3rd European Workshop on Visual Information Processing, EUVIP 2011 - Final Program, pp.67–72. 2. Basari, R.A.M.M.E.A.A. and Ahmad, B.H., 2010. Performance Analysis of Block Matching Algorithms in Motion Estimation, pp.11–13. 3. Burg, J., 2008. The Science of Digital Media. 1st ed. Prentice Hall. 4. Chalidabhongse, J., Kuo, C.J., and Member, S., 1997. Multiresolution-Spatio-Temporal Correlations, 7(3), pp.477–488. 5. Chung, K.L. and Chang, L.C., 2003. A New Predictive Search Area Approach for Fast Block Motion Estimation. IEEE Transactions on Image Processing, 12(6), pp.648–652. 6. Duanmu , C. J., 2006. Fast Scheme for the Four-Step Search Algorithm in Video Coding. 2006 IEEE International Conference on Systems, Man, and Cybernetics, pp. 3181-3185. 7. Gharavi, H. and Mills, M., 1990. Blockmatching Motion Estimation Algorithms - New Results. IEEE Transactions on Circuits and Systems for Video Technology, 37(5), pp.649–651. 8. Ghanbari, M., 1999. Video Coding : An Introduction to Standard Codecs. Institution of Electrical Engineers Stevenage, UK. 9. Ghanbari, M., 2011. Standard Codecs: Image Compression to Advanced Video Coding 3rd Edition. IET. 10. Hamid, N.A., Darsono, A.M., Manap, N.A., Manap, R.A., and Sulaiman, H.A., 2014. A New Orthogonal – Diamond Search Algorithm for Motion Estimation. International Conference on Computer, Communications, and Control Technology (I4CT) 2014. pp.467–471. 11. Haskell, B.G. and Puri, A., 2012. Chapter 2 MPEG Video Compression Basics. The MPEG Representation of Digital Media. Springer. 12. Immanuel Alex Pandian, S., Josemin Bala, G., and Anitha, J., 2011. Enhanced modified Orthogonal Search For Motion Estimation. 2011 IEEE Recent Advances in Intelligent Computational Systems, pp.907–910. 13. Jia, H. and Li, Z., 2004. A New Cross Diamond Search Algorithm For Block Motion Estimation. IEEE International Conference on Acoustics Speech and Signal Processing, pp.iii – 357–60. 14. Juan, L., Bin, F., and Wen-yu, L., 2006. Adaptive Motion Vector Prediction Based on Spatiotemporal Correlation . 15. Khan, N. A., Masud, S., and Ahmad, A., 2006. A Variable Block Size Motion Estimation Algorithm for Real-Time H.264 Video Encoding. Signal Processing: Image Communication, 21(4), pp.306–315. 16. Kim, D. W., Choi, J. S., and Kim, J. T., 1998. Adaptive Motion Estimation Based on Spatio-Temporal Correlation. Signal Processing: Image Communication, 13(2), pp.161–170. 17. Lam, C. W., Po, L. M., and Cheung, C.H., 2004. A Novel Kite-Cross-Diamond Search Algorithm for Fast Block Matching Motion Estimation. 2004 IEEE International Symposium on Circuits and Systems, 3, pp.2–5. 18. Luo, L., Zou, C., Gao, X., and He, Z., 1997. A New Prediction Search Algorithm for Block Motion Estimation in Video Coding. IEEE Transactions on Consumer Electronics, 43(1), pp.56–61. 19. Manap, R.A., Ranjit, S.S.S., Basari, A.A., and Ahmad, B.H., 2010. Performance Analysis of Hexagon-Diamond Search Algorithm for Motion Estimation. 2010 2nd International Conference on Computer Engineering and Technology, pp.V3–155–V3–159. 20. Marques, O., 2011. Practical Image and Video Processing Using MATLAB. Wiley. 21. Metkar, S. and Talbar, S., 2013. Motion Estimation Techniques for Digital Video Coding. Springer India. 22. Mistry, K., 2008. Spring 2008 Comparative study of Motion Estimation (ME) Algorithms. 23. Nayak, S., 2008. Module 7 Video Coding and Motion Estimation. 24. Nie, Y. and Ma, K.-K., 2002. Adaptive Rood Pattern Search For Fast Block-Matching Motion Estimation. IEEE Transactions on Image Processing : A Publication of The IEEE Signal Processing Society, 11(12), pp.1442–9. 25. Olivares, J., Hormigo, J., Villalba, J., Benavides, I., and Zapata, E.L., 2006. SAD Computation Based on Online Arithmetic for Motion Estimation. Microprocessors and Microsystems, 30(5), pp.250–258. 26. Oliveira, J.C. De, 1997. A Java H.263 Decoder Implementation. University of Ottawa. 27. Pandian, S.I.A., George, B.A., and Josemin Bala, G., 2011. A Study on Block Matching Algorithms for Motion Estimation. International Journal on Computer Science & Engineering, 3(1), pp.34–44. 28. Patwary, A.K., 2011. Fast Adaptive Motion Estimation for H.264, pp.6330–6333. 29. Patwary, M.A.K. and Othman, M., 2010. Motion Estimation and H.264 / AVC : A Review. Journal of Telecommunications, 6(1), pp.51–60. 30. Pesquet-Popescu, B., Cagnazzo, M. and Dufaux, F., 2013. Motion Estimation Techniques. TELECOM ParisTech, pp.33-34. 31. Po, L. and Ma, W.-C., 1996. A Novel Four-Step Search Algorithm for Fast Block Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology, 6(3), pp.313–317. 32. Po, L.-M. and Cheung, C.H., 2002. A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology, 12(12), pp.1168–117. 33. Rao, R. and Srinivasan, R., 1985. Predictive Coding Based on Efficient Motion Estimation. IEEE Transaction on Communications, 33(8), pp.888–896. 34. Rath G. B., and Makur, A., 2003. Subblock Matching-Based Conditional Motion Estimation With Automatic Threshold Selection for Video Compression. IEEE Transactions on Circuits and Systems for Video Technology, 13( 9), pp. 914–924. 35. Richardson, I.E.G., 2003. H.264 and MPEG-4 Video Compression, USA: Wiley. 36. Rijkse, K., 1996. H.263:Video Coding for Low-Bit-Rate Communication. IEEE Communications Magazine, 34(12), pp.42 – 45. 37. Sarwer, M.G. and Wu, Q.M.J., 2009. Adaptive Variable Block-Size Early Motion Estimation Termination Algorithm for H.264/AVC Video Coding Standard. IEEE Transactions on Circuits and Systems for Video Technology, 19(8), pp.1196–1201. 38. Santamarfa, M., and Trujillo, M., 2012. A Comparison of Block-Matching Motion Estimation Algorithms. 39. Sengupta, S., 2009. Module:7 Video Coding And Motion Estimation; Lesson 20 Basic Building Blocks & Temporal Redundancy. [on-line] 40. Available at: http://www.nptel.ac.in/courses/117105083/20 [Accessed on 2 July 2015] 41. Soongsathitanon, S., Woo, W.L., and Dlay, S.S., 2005. Fast Search Algorithms for Video Coding Using Orthogonal Logarithmic Search Algorithm. IEEE Transactions on Consumer Electronics, 51(2), pp.552–559. 42. Song, T.S.T., Ogata, K., Saito, K., and Shimamoto, T., 2007. Adaptive Search Range Motion Estimation Algorithm for H.264/AVC. 2007 IEEE International Symposium on Circuits and Systems, pp.3956–3959. 43. Sullivan, G.J. and Wiegand, T., 1998. Rate Distortion Optimization for Video Compression. 44. Sun, N., Fan, C. and Xia, X., 2009. An Effective Three-Step Search Algorithm for Motion Estimation. 2009 IEEE International Symposium on IT in Medicine and Education, pp.400–403. 45. Takaya, K., 2006. Detection of Moving Objects in Video Scene - MPEG like Motion Vector vs. Optical Flow. The First International Workshop on Video Processing for Security. Quebec City. 46. Vetrivel, S., Suba, K., and Athisha, G., 2010. An Overview of H.26x Series and its Applications. International Journal of Engineering Science and Technology, 2(9), pp.4622–4631. 47. Wang, Y., Ostermann, J. and Zhang, Y.Q., 2002. Video Processing and Communications (Vol. 5). Upper Saddle River: Prentice Hall. 48. Wang, Y., 2005. EE4414: Motion Estimation Basics. [on-line] Available at: http http://eeweb.poly.edu/~yao/EE4414/video_coding.pdf [Accessed on 6 June 2015] 49. Wang, X., Wan, W., and Ma, Y., 2010. A Novel Hexagon Diamond Search Algorithm for Motion Estimation. 2010 International Conference on Audio, Language and Image Processing, pp.1489–1493. 50. Watkinson, J., 2001. The MPEG Handbook : MPEG-1, MPEG-2, MPEG-4. Focal Press. 51. Whitaker, J. C., Benson, B., 2003. The Principles of Video Compression. Standard Handbook of Video and Television Engineering. 4th, Access Engineering. 52. Wong, S., Vassiliadis, S., and Cotofana, S., 2002. A Sum of Absolute Differences Implementation in FPGA Hardware. 2002 Proceedings of Euromicro Conference, 28th, pp. 183-188. 53. Xu, J., Po, L., and Cheung, C., 1999. Adaptive Motion Tracking Block Matching Algorithms for Video Coding. IEEE Transactions on Circuits and Systems for Video Technology, 9(7), pp.1025–1029. 54. Zhao, H., Yu, X.B., Sun, J.H., Sun, C., and Cong, H.Z., 2008. An Enhanced Adaptive Rood Pattern Search Algorithm for Fast Block-Matching Motion Estimation. 1st International Congress on Image and Signal Processing, CISP 2008. pp.416–420. 55. Zhu, C., Lin, X., and Chau, L.P., 2002. Hexagon-Based Search Pattern for Fast Block Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology, 12(5), pp.349–355. 56. Zhu, S. and Ma, K.K., 2000. Correction to ‘a new diamond search algorithm for fast block-matching motion estimation’. IEEE transactions on image processing : a publication of the IEEE Signal Processing Society, 9(3), pp.525

New Fast Block Matching Algorithm Using New Hybrid Search Pattern And Strategy To Improve Motion Estimation Process In Video Coding Technique

Similar Items