Modified Three-Step Search Block Matching Motion Estimation and Weighted Finite Automata based Fractal Video Compression
DOI:
https://doi.org/10.9781/ijimai.2017.444Keywords:
Fractal Theory, Motion Estimation, Compression, Three Step Search, EncodingAbstract
The major challenge with fractal image/video coding technique is that, it requires more encoding time. Therefore, how to reduce the encoding time is the research component remains in the fractal coding. Block matching motion estimation algorithms are used, to reduce the computations performed in the process of encoding. The objective of the proposed work is to develop an approach for video coding using modified three step search (MTSS) block matching algorithm and weighted finite automata (WFA) coding with a specific focus on reducing the encoding time. The MTSS block matching algorithm are used for computing motion vectors between the two frames i.e. displacement of pixels and WFA is used for the coding as it behaves like the Fractal Coding (FC). WFA represents an image (frame or motion compensated prediction error) based on the idea of fractal that the image has self-similarity in itself. The self-similarity is sought from the symmetry of an image, so the encoding algorithm divides an image into multi-levels of quad-tree segmentations and creates an automaton from the sub-images. The proposed MTSS block matching algorithm is based on the combination of rectangular and hexagonal search pattern and compared with the existing New Three-Step Search (NTSS), Three-Step Search (TSS), and Efficient Three-Step Search (ETSS) block matching estimation algorithm. The performance of the proposed MTSS block matching algorithm is evaluated on the basis of performance evaluation parameters i.e. mean absolute difference (MAD) and average search points required per frame. Mean of absolute difference (MAD) distortion function is used as the block distortion measure (BDM). Finally, developed approaches namely, MTSS and WFA, MTSS and FC, and Plane FC (applied on every frame) are compared with each other. The experimentations are carried out on the standard uncompressed video databases, namely, akiyo, bus, mobile, suzie, traffic, football, soccer, ice etc. Developed approaches are compared on the basis of performance evaluation parameters, namely, encoding time, decoding time, compression ratio and Peak Signal to Noise Ratio (PSNR). The video compression using MTSS and WFA coding performs better than MTSS and fractal coding, and frame by frame fractal coding in terms of achieving reduced encoding time and better quality of video.Downloads
References
Gonzalez, R. C., Woods, R. E. (2005) ‘Digital Image Processing’, Second Edition, Pearson Education Asia.
Acharjee, S., Dey, N., Biswas, D., Das, P., & Chaudhuri, S. S. (2012), “A novel Block Matching Algorithmic Approach with smaller block size for motion vector estimation in video compression”, 12th IEEE International Conference on Intelligent Systems Design and Applications (ISDA), 2012, pp. 668-672.
Acharjee, S., Biswas, D., Dey, N., Maji, P., & Chaudhuri, S. S. (2013), “An efficient motion estimation algorithm using division mechanism of low and high motion zone”, IEEE International Multi-Conference on Automation, Computing, Communication, Control and Compressed Sensing (iMac4s), 2013, pp. 169-172.
Acharjee, S., Pal, G., Redha, T., Chakraborty, S., Chaudhuri, S. S., & Dey, N. (2014), “Motion vector estimation using parallel processing”, IEEE International Conference on Circuits, Communication, Control and Computing (I4C), 2014, pp. 231-236.
Zhu, S., Tian, J., Shen, X. and Belloulata, K. (2009) ‘A new cross-diamond search algorithm for fast block motion estimation’, In the IEEE Int. Conf. Image Processing, ICIP’09, Cairo, Egypt, Vol. I, pp. 1581-1584.
Zhu, S., Tian, J., Shen, X. and Belloulata, K. (2009) ‘A Novel CrossHexagon Search Algorithm Based on Motion Vector Field Prediction’, In the IEEE Int. Symposium on Industrial Electronics, ISIE’09, Seoul, Korea, pp. 1870-1874.
Zhu, S., Hou, Y., Wang, Z. and Belloulata, K. (2010) ‘A novel fractal video coding algorithm using fast block matching motion estimation technology’, In the International Conference on Computer Application and System Modeling, ICCASM’10,Taiyuan, China, Vol. 8, pp.360-364.
Koga, T., Iinuma, K., Hirano, A., Iijima, Y. and Ishiguro, T. (1981) ‘Motion compensated interframe coding for video conferencing’, In Proc. National Telecommunications Conf., New Orleans, LA, pp. G5.3.1 –G5.3.5.
Jain, J. R. and Jain, A. K. (1981) ‘Displacement measurement and its application in interframe image coding’, IEEE Transactions on Communications, vol. 29, pp. 1799-1808.
Puri, A., Hang, H. M. and Schilling, D. L. (1987) ‘An efficient block matching algorithm for motion compensated coding’, Proc. IEEE Int. Conf. Acoust., Speech, and Signal Proc., pp. 1063-1066.
Ghanbar, M. (1990) ‘The cross search algorithm for motion estimation’, IEEE Trans. Commun., Vol. COM-38, pp. 950-953.
Urabe, T., Afzal, H., Ho, G., Pancha, P. and Zarki, M. E. (1994) ‘MPEG Tool- an X window-based MPEG encoder and statistical tool’, Multimedia a syst. 1(5). pp. 220-229.
R. Li, Zeng, B. and Liou, M. L. (1994) ‘A new three-step search algorithm for block motion estimation’, IEEE Transactions on Circuits and Systems for Video Technology, vol. 4, no.4, pp. 438-443.
Po, L. -M. 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, vol. 6, no. 3, pp. 313–317.
Liu, L. K. and Feig, E. (1996) ‘A block based gradient descent search algorithm for block motion estimation in video coding’, IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, no. 4 , pp. 419-422.
Zhu, S. and Ma, K.K.(2000) ‘A new diamond search algorithm for fast block-matching motion estimation’, IEEE Transactions on Image Processing, vol. 9, no. 2, pp. 287-290.
Cheung, C. H. and Po, L. M. (2002) ‘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.
Jing, X. and Lap-Pui, C.(2004) ‘An efficient three-step search algorithm for block motion estimation’, IEEE transactions on multimedia, Vol. 6, No.3, pp. 435-438.
Tham, J.Y., Ranganath, S., Ranganath, M. and Kassim, A. A.(1998) ‘A novel unrestricted center-biased diamond search algorithm for block motion estimation’, IEEE Transactions on Circuits and Systems for Video Technology, vol. 8, no. 4, pp. 369-377.
Chen, H. M., Chen, P. H., Yeh, K. L., Fang, W. H., Shie, M. C. and Lai, F.(2007) ‘Center of Mass-Based Adaptive Fast Block Motion Estimation’, EURASIP Journal on Image and Video Processing, vol. Article ID 65242, 11 pages.
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, vol. 12, pp. 349-355.
Cheung, C. H. and Po, L. M. (2000) ‘Normalized partial distortion search algorithm for block motion estimation’, IEEE Transactions on Circuits and Systems for Video Technology, vol. 10, pp. 417-422.
Li H., Liu M. (2009) ‘Cross-Hexagon-based motion estimation algorithm using motion vector adaptive search technique’, International Conference on Wireless Communications & Signal Processing, Nanjing, 2009, pp. 1-4.
Belloulata, K., Zhu, S., and Wang, Z. (2011) ‘A Fast Fractal Video Coding Algorithm Using Cross-Hexagon Search for Block Motion Estimation’, International Scholarly Research Network Signal Processing, volume 2011, Article ID 386128.
Acharjee, S., Ray, R., Chakraborty, S., Nath, S., & Dey, N. (2014), “Watermarking in motion vector for security enhancement of medical videos”, IEEE International Conference on Control, Instrumentation, Communication and Computational Technologies (ICCICCT), 2014, pp. 532-537.
Ikeda, N., Araki, T., Dey, N., Bose, S., Shafique, S., El-Baz, A., ... & Suri, J. S. (2014), “Automated and accurate carotid bulb detection, its verification and validation in low quality frozen frames and motion video”, International angiology: a journal of the International Union of Angiology, 33(6), 573-589.
Dey, N., Ashour, A., & Acharjee, S. (2017), “Applied Video Processing in Surveillance and Monitoring Systems”, pp. 1-321, Hershey, PA: IGI Global. doi:10.4018/978-1-5225-1022-2.
Kamble, S. D., Thakur, N.V., Malik, L. G. and Bajaj, P. R. (2014) ‘Fractal Video Coding Using Modified Three-step Search Algorithm for Blockmatching Motion Estimation’, Computational Vision and Robotics, Proceedings of International Conference on Computer Vision and Robotics, ICCVR’14, Advances in Intelligent Systems and Computing, Vol. 332, pp 151-162 Springer-India.
Culik, K. and Kari, J. (1995) ‘Inference algorithms for WFA and image compression’, In Y. Fisher, editor, Fractal Image Compression, chapter 13, pages 243-258. Springer-Verlag.
Kari, J. and Franti, P. (1994) ‘Arithmetic coding of weighted finite automata’, Theoretical Informatics and Applications, 28(3-4):343-360.
Hafner, U.(1996) ‘Refining Image Compression with Weighted Finite Automata’, IEEE Data compression Conference, pp. 359-368.
Katritzke, F. (2001) ‘Refinements of Data Compression Using Weighted Finite Automata’, Ph.D. dissertation.
Katritzke, F., Merzenich, W., and Thomas, M. (2003) ‘Enhancements of partitioning techniques for image compression using weighted finite automata’, Elsevier, 2003.
Kamble, S. D., Thakur, N.V., Malik, L. G. and Bajaj, P. R. (2015) ‘Color video compression based on fractal coding using quad-tree weighted finite automata’, Information system design and intelligent application, Proceedings of Second International Conference INDIA 2015, vol.2, Advances in Intelligent System and Computing, Springer India, vol. 340, pp-649-65
Downloads
Published
-
Abstract43
-
PDF21
Submit Article
Information
