HIGH PERFORMANCE BLOCK MATCHING ALGORITHM FOR HIGH BIT-RATE REAL-TIME VIDEO COMMUNICATION

(Received: 2017-11-22, Revised: 04-Jan.-2018 and 27-Jan.-2018 , Accepted: 2018-02-15)

Authors Nijad Al-Najdawi,

Keywords #Video Communication #Video Coding #Video Conferencing #Motion Estimation #Block Matching.

Abstract Although the advancements in hardware solutions are growing exponentially along with the communication channels capacity, high quality video encoders for real-time applications are still considered an open area of research. The majority of researchers interested in video encoders target their investigations towards motion estimation and block matching algorithms. Many algorithms that aim to reduce the total number of required mathematical operations when compared to Full Search have been proposed. However, the results often converge to local minima and a significant amount of computations is still required. Therefore, in this research, a hierarchy-based block matching method that facilitates the transmission of high bit-rate videos over standard communication methods is proposed. The proposed algorithm is based on the frequency domain, where the algorithm examines the similarities between a chosen frequency subset, which significantly reduces the total number of comparisons and the total mathematical computations required per block.

References

[1] V. Argyriou and T. Vlachos, "Quad-Tree Motion Estimation in the Frequency Domain Using Gradient Correlation," IEEE Transactions on Multimedia, vol. 9, no. 6, pp. 1147-1154, 2007.

[2] J. Cai and W. Pan, "On Fast and Accurate Block-based Motion Estimation Algorithms Using Particle Swarm Optimization," Elsevier Information Sciences, vol. 197, pp. 53-64, 2012.

[3] E. Cuevasa, D. Zaldívara, M. Pérez-Cisneros and D. Oliva, "Block-matching Algorithm Based on Differential Evolution for Motion Estimation," Elsevier Engineering Applications of Artificial Intelligence, vol. 26, no. 1, pp. 488-498, 2013.

[4] E. Cuevasa, D. Zaldívara, M. Pérez-Cisneros, H. Sossa and V. Osuna, "Block matching algorithm for motion estimation based on Artificial Bee Colony (ABC)," Elsevier Applied Soft Computing, vol. 3, no. 6, pp.3047-3059, 2013.

[5] Z. Cui, G. Jiang, S. Yang and C. Wu, "A New Fast Motion Estimation Algorithm Based on the Loop– epipolar Constraint for Multi-View Video Coding," Elsevier Signal Processing: Image Communication, vol. 27, no. 2, pp. 172–179, 2012.

[6] C. Erdem, G. Karabulut, E. Yanmaz and E. Anarim, "Motion Estimation in the Frequency Domain Using Fuzzy c-planes Clustering," IEEE Transactions on Image Processing, vol. 10, no. 2, pp. 1873- 1879, 2001.

[7] J. Fabrizio, S. Dubuisson and D. Béréziat, "Motion Compensation Based on Tangent Distance Prediction for Video Compression," Elsevier Signal Processing: Image Communication, vol. 27. no. 2, pp. 153–171, 2012.

[8] M. Ghanbari, "Video Coding: An Introduction to Standard Codecs," Institution of Electrical Engineers, 1999.

[9] R. Gonzales and R. Woods, Digital Image Processing, 3rd Edition, Prentice Hall, 2008.

[10] J. R. Jain and A. K. Jain, "Displacement Measurement and Its Application in Interframe Image Coding," IEEE Transactions on Communincations, vol. 29, no. 12, pp. 1799-1808, 1981.

[11] C. Je and H-M. Park, "Optimized Hierarchical Block Matching for Fast and Accurate Image Registration," Elsevier Signal Processing: Image Communication, vol. 28, no. 7, pp. 779-791, 2013.

[12] X. Jing and L. P. Chau, "An Efficient Three-step Search Algorithm for Block Motion Estimation," IEEE Transactions on Multimedia, vol. 6, no. 3, pp. 435-438, 2004.

[13] T. Koga, K. Iinuma, A. Hirano, Y. Iijima and T. Ishiguro, "Motion Compensated Interframe Coding for Video Conferencing," in: Proc. Nat. Telecommunications Conference, pp. G5.3.1-5.3.5, 1981.

[14] N. Al-Najdawi, M. N. Al-Najdawi and S. Tedmori, "Employing a Novel Cross-diamond Search in a Modified Hierarchical Search Motion Estimation Algorithm for Video Compression," Elsevier Information Sciences, vol. 268, pp. 425-435, 2014.

[15] K. Lai, Y. Chan, C. Fu and W. Siu, "Hybrid Motion Estimation Scheme for Secondary SP-frame Coding Using Inter-Frame Correlation and FMO," Elsevier Signal Processing: Image Communications, vol. 27, no. 1, pp. 1-15, 2012.

[16] F. Di Martino, V. Loia and S. Sessa, "Fuzzy Transforms for Compression and Decompression of Color Videos," Elsevier Information Sciences, vol. 180, no. 20, pp. 3914-3931, 2010.

[17] M. Pingault and D. Pellerin, "Motion Estimation of Transparent Objects in the Frequency Domain," Journal of Signal Processing, vol. 4, no. 8, 2004.

[18] I. Richardson, H.264 and MPEG-4 Video Compression: Video Coding for Next-Generation Multimedia, John Wiley & Sons, 2003.

[19] I. Richardson, Video Codec Design, John Wiley & Sons, 2002.

[20] S. Tedmori and N. Al-Najdawi, "Hierarchical Stochastic Fast Search Motion Estimation Algorithm," IET Computer Vision, vol. 6, no. 1, pp. 21-28, 2012.

[21] G. Tzimiropoulos, V. Argyriou and T. Stathaki, "Symmetry Detection Using Frequency Domain Motion Estimation Techniques," Proc. IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 861-864, 2008.

[22] R. Young and N. Kingsbury, "Frequency-domain Motion Estimation Using a Complex Lapped Transform," IEEE Transactions on Image Processing, vol. 2, no. 1, pp. 2-17, 1993.

[23] 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.

[24] H. Alzoubi and W. Pan, "Fast and Accurate Global Motion Estimation Algorithm Using Pixel Subsampling," Elsevier Information Sciences, vol. 178, no. 17, pp. 3415-3425, 2008.

[25] K. M. Nam, J. S. Kim, R. H. Park and Y. S. Shim, "A Fast Hierarchical Motion Vector Estimation Algorithm Using Mean Pyramid," IEEE Transactions on Circuits and Systems for Video Technology, vol. 5, no. 4, pp. 344–351, 1995.

[26] C. Kuo, C. Hsieh and C. Chao, "Multiresolution Video Coding Based on Kalman Filtering Motion Estimation," Elsevier Journal of Visual Communication and Image Representation, vol. 13, no. 1, pp. 348–362, 2002.

[27] B. C. Song and J. B. Ra, "A Hierarchical Block Matching Algorithm Using Partial Distortion Criterion," in: Proc. SPIE 3309, Visual Communications and Image Processing, pp. 88-95, 1998.

[28] C. K. Cheung and L. M. Po, "A Hierarchical Block Motion Estimation Algorithm Using Partial Distortion Measure," in: Proc. International Conference on Image Processing, pp. 606-609, 1997.

[29] S. Basah, A. Bab-Hadiashar and R. Hoseinnezhad, "Conditions for Motion-background Segmentation Using Fundamental Matrix," IET Computer Vision, vol. 3, no. 4, pp. 189-200, 2009.

[30] N. Al-Najdawi, S. Tedmori, O. Alzubi, O. Dorgham and J. Alzubi, "A Frequency-Based Hierarchical Fast Search Block Matching Algorithm for Fast Video Communication," International Journal of Advanced Computer Science and Applications, vol. 7, no. 4, pp. 447-455, 2016.

[31] Z. Weng, G. Chen, L. Shieh and J. Larsson, "Evolutionary Programming Kalman Filter," Elsevier Information Sciences, vol. 129, no 1-4, pp. 197-210, 2000.

[32] R. Tolimieri, M. An and C. Lu, "Algorithms for Discrete Fourier Transform and Convolution," Springer Science and Business Media, New York, pp. 55-70, 1997.

[33] MA. Diaz-Cortes, E. Cuevas and R. Rojas, "Motion Estimation Algorithm Using Block-Matching and Harmony Search Optimization," Engineering Applications of Soft Computing, Intelligent Systems Reference Library, vol. 129, 2017.

[34] S. Yu and J. Jeong, "Multidirectional Motion Estimation Algorithm for Frame Rate Up-conversion," Proc. of the 21st International Conference on Circuits, Systems, Communications and Computers, 2017.

[35] A. Abdelazim, A. Hamza and D. Ait-Boudaoud, "Cross Search Frequency Domain Motion Estimation Algorithm for the High Efficiency Video Coding Standard," 9th IEEE-GCC Conference and Exhibition, 2017.

[36] S. Jia and W. Ding, "A Fast Sub-Pixel Motion Estimation Algorithm for HEVC," IEEE International Symposium on Circuits and Systems, 2016.

[37] P. Muralidhar and C. Rao, "High Performance Architecture of Motion Estimation Algorithm for Video Compression," Journal of Circuits, Systems and Computers, vol. 25, no. 8, 2016.

[38] S. Chang and R. Wang, "Novel Motion Estimation Algorithm for Image Stabilizer," Engineering Computations, vol. 34, no. 1, pp. 77-89, 2017.

[39] S. Arora, N. Rajpal and R. Purwar, "A New Fast Motion Estimation Algorithm Using Adaptive Size Diamond Pattern Search with Early Search Termination," International Journal of Computational Vision and Robotics, vol. 7, no. 6, pp. 623-643, 2017.

[40] V. Kovacevic, Z. Pantic, A. Beric and R. Jakovljevic, "Block-Matching Correlation Motion Estimation for Frame-Rate Up-Conversion," Journal of Signal Processing Systems, vol. 84, no. 2, pp. 283-292, 2016.

[41] S. Kamble, N. Thakur and P. Bajaj, "Modified Three-Step Search Block Matching Motion Estimation and Weighted Finite Automata-based Fractal Video Compression," International Journal of Interactive Multimedia and Artificial Intelligence, vol. 4, no. 4, pp. 27-39, 2017.

[42] X. Cheng, Q. Hao and M. Xie, "A Comprehensive Motion Estimation Technique for the Improvement of EIS Methods Based on the SURF Algorithm and Kalman Filter," Sensors Journal, vol. 16, no. 4, pp. 1-15, 2016.

[43] R. Purwar, "Enhanced Dynamic Pattern Search Algorithm with Weighted Search Points for Fast Motion Estimation," Signal, Image and Video Processing, vol. 11, no. 6, pp. 1001-1007, 2017.

[44] S. Arora, N. Rajpal, K. Khanna and R. Purwar, "Improved Accuracy in Initial Search Center Prediction to Fasten Motion Estimation in H.264/AVC," IETE Journal of Research, vol. 62, no. 6, pp. 842-851, 2016.

[45] S. Arora, K. Khanna and N. Rajpal, "A Novel Hybrid Approach for Fast Block-based Motion Estimation," International Journal of Interactive Multimedia and Artificial Intelligence, vol. 4, no. 6, pp. 24-30, 2017.

[46] P. Nalluri, L. Alves and A. Navarro, "Complexity Reduction Methods for Fast Motion Estimation in HEVC," Image Communication Journal, vol. 39, pp. 280-292, 2015.

[47] S. Kamble, N. Thakur and P. Bajaj,"Fractal Coding Based Video Compression Using Weighted Finite Automata," International Journal of Ambient Computing and Intelligence, vol. 9, no. 1, 2018.