ICTACT Journal on Image and Video Processing

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Performance-Based Study on Diamond Search and its Variations for Efficient Motion Estimation in Video


Affiliations
1 Department of Computer Science and Engineering, Jain University, India
2 Department of Electrical Engineering, National Institute of Technology, Silchar, India
     

   Subscribe/Renew Journal


The motion estimation is a crucial process of video encoding process which needs to be dealt with high importance. There has been a lot of research works on the topic and various block-based motion estimation techniques were designed and implemented for the same. Out of the existing developed techniques, Diamond Search (DS) is one of the efficient motion estimation technique and most no. of new algorithms are designed based on this DS only. In this paper, we will be critically reviewing the Diamond Search (DS) and few existing variations of block matching algorithms based on DS which varies according to search criteria, search pattern, size of the search window, macro block size and PSNR values. The algorithms are being applied to different video sequences to do a comparative study among them and check out which variation of DS is efficient for which video sequences.

Keywords

Block Matching, DS, MDSS, Motion Estimation, MV.
Subscription Login to verify subscription
User
Notifications
Font Size

  • S. Zhu and K.K. Ma, “A New Diamond Search Algorithm for Fast Block-Matching Motion Estimation”, IEEE Transactions on Image Processing, Vol. 9, No. 2, pp. 287-290, 2000.

  • C.H. Cheung and L.M. Po, “A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimation”, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 12, No. 12, pp. 1168-1177, 2002.

  • C.H. Cheung and L.M. Po, “A Novel Small-Cross-Diamond Search Algorithm for Fast Video Coding and Video Conferencing Applications”, Proceedings of International Conference on Image Processing, pp. 1-5, 2002.

  • H. Jia and L. Zhang, “A New Cross Diamond Search Algorithm for Block Motion Estimation”, Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing, pp. 231-237, 2004.

  • C.W. Lam, L.M. Po and C.H. Cheung, “A New CrossDiamond Search Algorithm for Fast Block Matching Motion Estimation”, Proceedings of International Conference on Neural Networks and Signal Processing, pp. 1262-1265, 2003.

  • W.I. Choi, B. Jeon and J. Jeong, “Fast Motion Estimation with the Modified Diamond Search for Variable Motion Block Sizes”, Proceedings of International Conference on Image Processing, pp. 364-371, 2003.

  • H. Jia and L. Zhang, “Directional Diamond Search Pattern for Fast Block Motion Estimation”, Electronics Letters, Vol. 39, No. 22, pp. 1581-1583, 2003.

  • C.W. Lam, L.M. Po and C.H. Cheung, “A Novel Kite-Cross-Diamond Search Algorithm for Fast Block Matching Motion Estimation”, Proceedings of International Conference on Circuits and Systems, pp. 723-729, 2004.

  • A. Barjatya, “Block Matching Algorithms for Motion Estimation”, IEEE Transactions Evolution Computation, Vol. 8, No. 3, pp. 225-239, 2004.

  • G. Ding and Q. Dai, “A Line-Diamond Parallel Search Algorithm for Block Motion Estimation. In Image and Graphics”, Proceedings of 3rd International Conference on Image and Graphics, pp. 320-323, 2004.

  • L.M. Po and C.H. Cheung, “Novel Cross-Diamond-Hexagonal Search Algorithms for Fast Block Motion Estimation”, IEEE Transactions on Multimedia, Vol. 7, No. 1, pp. 16-22, 2005.

  • H.S. Yoon, G.S. Lee, S.H Kim and J.Y. Chang, “Motion Estimation based on Temporal Correlations”, Proceedings of IEEE International Conference on Information and Communication Technology, pp. 75-83, 2002.

  • X. Yi and N. Ling, “Rapid Block-Matching Motion Estimation using Modified Diamond Search Algorithm”, Proceedings of IEEE International Conference on Circuits and Systems, pp. 5489-5492, 2005.

  • H. So, J. Kim, W.K. Cho and Y.S. Kim, “Fast Motion Estimation using Modified Diamond Search Patterns”, Electronics Letters, Vol. 41, No. 2, pp. 62-63, 2005.

  • G. Ding, Q. Dai and W. Xu, “Fast Motion Estimation Algorithm based on Predictive Line Diamond Search Technology”, Proceedings of IEEE International Conference on Circuits and Systems, pp. 523-527, 2005.

  • H. Liu, Y. Lie and C. Xie, “Fast Block-Matching Motion Estimation based on an Improved Cross-Diamond Search Algorithm”, Proceedings of IEEE International Conference on Circuits and Systems, pp. 1-4, 2005.

  • A. Moradi, R. Dianat, S. Kasaei and M.T.M. Shalmani, “Enhanced Cross-Diamond-Hexagonal Search Algorithms for fast Block Motion Estimation”, Proceedings of IEEE International Conference on Advanced Video and Signal Based Surveillance, pp. 558-563, 2005.

  • A. Samet, N. Souissi, W. Zouch, M.A. Ben Ayed and N. Masmoudi, “New Horizontal Diamond Search Motion Estimation Algorithm for H. 264/AVC”, Proceedings of IEEE International Conference on Communication, Control and Signal Processing, pp. 13-15, 2006.

  • H.T. Lin and J.S. Chiang, “A New Diamond-Arc-Hexagon Search Algorithm for Fast Block Motion Estimation”, Proceedings of IEEE International Conference on Communication, Control and Signal Processing, pp. 811-816, 2006.

  • H.S. Lee, J.H. Jung and D.J. Park, “An Efficient Diamond Search with Large Kite Search Patterns for Fast Block Motion Estimation”, Proceedings of IEEE International Conference on International Conference on Applied Science and Engineering, pp. 3137-3141, 2006.

  • Y.W. Huang, C.Y. Chen, C.H. Tsai, C.F. Shen and L.G. Chen, “Survey on Block Matching Motion Estimation Algorithms and Architectures with New Results”, Journal of VLSI Signal Processing Systems for Signal, Image and Video Technology, Vol. 42, No. 3, pp. 297-320, 2006.

  • G. Jeon, J. Kim and J. Jeong, “Enhanced Cross-Diamond Search Algorithm for Fast Block Motion Estimation”, Proceedings of IEEE International Conference on Image Analysis and Recognition, pp. 481-490, 2007.

  • C.J. Duanmu, X. Chen, Y. Zhang and S. Zhou, “Mixed Diamond, Hexagon, and Cross Search Fast Motion Estimation Algorithm for H. 264”, Proceedings of IEEE International Conference on Multimedia and Expo, pp. 761-764, 2008.

  • J.S. Chiang, H.T. Lin and C.H. Hsia, “Novel Fast Block Motion Estimation using Diamond-Arc-Hexagon Search Patterns”, Journal of the Chinese Institute of Engineers, Vol. 31, No. 6, pp. 955-966, 2008.

  • Y. Ismail, J. McNeelly, M. Shaaban and M.A. Bayoumi, “Enhanced Efficient Diamond Search Algorithm for Fast Block Motion Estimation”, Proceedings of IEEE International Conference on Circuits and Systems, pp. 3198-3201, 2009.

  • X. Wang, W. Wan, J. Zhang and Y. Ma, “Research on the Motion Estimation with a Novel Octagon Cross Diamond Search Algorithm”, Proceedings of IEEE International Conference on Microelectronics and Electronics, pp. 89-92, 2010.

  • I.A. Hashad, A.R. Sadek and S.K. Mandour, “A Novel Reduced Diamond Search (RDS) Algorithm with Early Termination for Fast Motion Estimation”, International Journal of Video and Image Processing and Network Security, Vol. 10, No. 4, pp. 32-39, 2010.

  • R.A. Manap, S.S.S. Ranjit, A.A. Basari and B.H. Ahmad, “Performance Analysis of Hexagon-Diamond Search Algorithm for Motion Estimation”, Proceedings of IEEE International Conference on Computer Engineering and Technology, pp. 152-155, 2010.

  • T. Swati and M.V.R. Vittal, “Estimation of Motion Vector Parameters using Modified Diamond Search”, International Journal of Computer Applications, Vol. 15, No. 8, pp. 38-41, 2011.

  • A.A. Devi, M.R. Sumalatha, N.M. Priya, B. Sukruthi and M. Minisha, “Modified Diamond-Square Search Technique for Efficient Motion Estimation”, Proceedings of IEEE International Conference on Recent Trends in Information Technology, pp. 1149-1153, 2011.

  • S. Gupta and S.M. Arora, “Motion Estimation Method between Diamond Search and Three Step Search”, Proceedings of National Conference on Web and Knowledge-Based Systems on Emerging Trends and Perspectives, pp. 23-33, 2011.

  • K. Singh and S.R. Ahamed, “Modified Small-Cross Diamond Search Motion Estimation Algorithm for H. 264/AVC”, Proceedings of IEEE International Conference on Recent Trends in Information Technology, pp. 1-5, 2013.

  • J. Luo and J. Peng,“An Unsymmetrical Diamond Search Algorithm for H. 264/AVC Motion Estimation”, Proceedings of IEEE International Conference on Chinese Conference on Image and Graphics Technologies, pp. 54-65, 2013.

  • S. Banchhor and D. Shukla, “An Improved Diamond Search Pattern for Motion Estimation”, i-manager’s Journal on Pattern Recognition, Vol. 3, No. 3, pp. 1-19, 2016.

  • N.A. Hamid, A.M. Darsono, N.A. Manap, R.A. Manap and H.A. Sulaiman, “A New Orthogonal-Diamond Search Algorithm for Motion Estimation”, Proceedings of IEEE International Conference on Computer, Communications, and Control Technology, pp. 1-6, 2014.

  • N.A. Hamid, A.M. Darsono, N.A. Manap, R.A. Manap and H.A. Sulaiman, “Performance Evaluation of Orthogonal-Diamond Search of Block Matching Algorithm for Video Coding”, Jurnal Teknologi, Vol. 76, No. 1, pp. 61-66, 2015.

  • S.K. Sahu and D. Shukla, “A New Approach of Block Matching Motion Estimation Algorithm for H. 264/AVC Video Codec”, i-manager’s Journal on Pattern Recognition, Vol. 4, No. 2, pp. 1-10, 2017.


Abstract Views: 205

PDF Views: 0




  • Performance-Based Study on Diamond Search and its Variations for Efficient Motion Estimation in Video

Abstract Views: 205  |  PDF Views: 0

Authors

Hussain Ahmed Choudhury
Department of Computer Science and Engineering, Jain University, India
Nidul Sinha
Department of Electrical Engineering, National Institute of Technology, Silchar, India
Tanvir H. Sardar
Department of Computer Science and Engineering, Jain University, India
Archana Wagh-Mare
Department of Computer Science and Engineering, Jain University, India

Abstract


The motion estimation is a crucial process of video encoding process which needs to be dealt with high importance. There has been a lot of research works on the topic and various block-based motion estimation techniques were designed and implemented for the same. Out of the existing developed techniques, Diamond Search (DS) is one of the efficient motion estimation technique and most no. of new algorithms are designed based on this DS only. In this paper, we will be critically reviewing the Diamond Search (DS) and few existing variations of block matching algorithms based on DS which varies according to search criteria, search pattern, size of the search window, macro block size and PSNR values. The algorithms are being applied to different video sequences to do a comparative study among them and check out which variation of DS is efficient for which video sequences.

Keywords


Block Matching, DS, MDSS, Motion Estimation, MV.

References