A Review on Block Matching Motion Estimation and Automata Theory based Approaches for Fractal Coding

Authors

  • Shailesh D. Kamble Yashwantrao Chavan Maharashtra Open University image/svg+xml
  • Nileshsingh Thakur Prof Ram Meghe College of Engineering & Management, India.
  • Preeti Bajaj G. H. Raisoni College of Engineering, India.

DOI:

https://doi.org/10.9781/ijimai.2016.4214

Keywords:

Fractal Theory, Motion Estimation, Compression, Decoding Time

Abstract

Fractal compression is the lossy compression technique in the field of gray/color image and video compression. It gives high compression ratio, better image quality with fast decoding time but improvement in encoding time is a challenge. This review paper/article presents the analysis of most significant existing approaches in the field of fractal based gray/color images and video compression, different block matching motion estimation approaches for finding out the motion vectors in a frame based on inter-frame coding and intra-frame coding i.e. individual frame coding and automata theory based coding approaches to represent an image/sequence of images. Though different review papers exist related to fractal coding, this paper is different in many sense. One can develop the new shape pattern for motion estimation and modify the existing block matching motion estimation with automata coding to explore the fractal compression technique with specific focus on reducing the encoding time and achieving better image/video reconstruction quality. This paper is useful for the beginners in the domain of video compression.

Downloads

Download data is not yet available.

References

[1] M. F. Barnsley, Fractals Everywhere, Academic Press, 1988.

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

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

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

[5] M. F. Barnsley and A. D. Sloan, “A better way to compress images”, Byte, pp. 215-223, January 1988.

[6] Y Fisher, “Fractal Image Compression”, SIGGRAPH-1992 Course Notes.

[7] R. C. Gonzalez, R. E. Woods, “Digital Image Processing”, Second Edition, Pearson Education Asia, 2005.

[8] L. P. Hurd, M. A. Gustavas, M. F. Barnsley. “Fractal Video Compression”, AK Peters Ltd., 1993.

[9] Thakur Nileshsingh V, Dr. O. G. Kakde, “Color Image Compression on Spiral Architecture using Optimized Domain Blocks in Fractal Coding”, IEEE 4th International Conference on Information Technology, pp. 234-242, 2007.

[10] C. S. Tong, and M. Wong, “Adaptive Approximate Nearest Neighbor Search for Fractal Image Compression”, IEEE Transactions on Image Processing, vol. 11, no. 6, pp. 605-615, June 2000.

[11] S. K. Ghosh, J. Mukherjee, and P. P. Das, “Fractal Image Compression: A Randomized Approach”, Pattern Recognition Letters, vol. 25, no. 9, pp. 1013-1024, July 2004.

[12] T. K. Truong, C. M. Kung, J. H. Jeng, and M. L. Hsieh, “Fast Fractal Image Compression using Spatial Correlation”, Chaos, Solitons & Fractals, vol. 22, no. 5, pp. 1071-1076, Dec. 2004.

[13] C. Wang, and J. Kao, “A Fast Encoding Algorithm for Fractal Image Compression”, IEICE Electronics Express, vol. 1, no.12, pp. 352-357, 2004.

[14] C. Fan, and P. Liu, “A Fast Matching Algorithm Based on Adaptive Classification Scheme”, 5th IEEE International Conference on Cognitive informatics, ICCI 2006, vol. 1, pp. 541-546, 17-19 July 2006.

[15] Q. Wang, D. Liang, Sheng Bi, “Fast Fractal Image Encoding Based on Correlation Information Feature”, 3rd International Congress on Image and Signal Processing, vol. 2, pp. 540-543, 2010.

[16] S. K. Ghosh, J. Mukhopadhyay, V. M. Chowdary, and A. Jeyaram, “Relative Fractal Coding and Its Application in Satellite Image Compression”, Proceedings of ICVGIP, Ahmadabad, india, pp. 469-474, Dec. 2002.

[17] A. Conci, and F. R. Aquino, “Fractal Coding Based on Image Local Fractal Dimension”, Computational and Applied Mathematics, vol. 24, no. 1, pp. 83-98, 2005.

[18] J. Li, D. Yuan, Q. Xie, and C. Zhang, “Fractal Image Compression by Ant Colony Algorithm”, the 9th International Conference for Young Computer Scientists, ICYCS 2008, pp. 1890-1894, 18-21 Nov. 2008.

[19] H. Hartenstein, M. Ruhl, and D. Saupe, “Region-Based Fractal Image Compression”, IEEE Transactions on Image Processing, vol. 9, no. 7, pp. 1171-1184, July 2000.

[20] K. Belloulata, and J. Konrad, “Fractal Image Compression with Region Based Functionality”, IEEE Transactions on Image Processing, vol. 11, no. 4, pp. 351-362, April 2002.

[21] H. Harenstein, and D. Saupe, “Lossless Acceleration of Fractal ImageEncoding Via the Fast Fourier Transform”, Signal Processing: Image Communication, vol. 16, no. 4, pp. 383-394, Nov. 2000.

[22] R. Franco, and D. Mala, “Adaptive Image Partitioning for Fractal Coding Achieving Designated Rates Under A Complexity Constraint”, Proceedings of International Conference on Image Processing, vol. 2, pp. 435-438, Oct. 2001.

[23] Hai Wang, “Fast Image Fractal Compression with Graph-Based Image Segmentation Algorithm”, International Journal of Graphics, vol. 1, no. 1, November-2010.

[24] M. Hassaballah, M. M. Makky, and Y. B. Mahdy, “A Fast Fractal Image Compression Method Based Entropy”, Electronic Letters on Computer Vision and Image Analysis, vol. 5, no. 1, pp. 30-40, 2005.

[25] C. He, X. Xu, and J. Yang, “Fast Fractal Image Encoding using one-norm of normalized Block”, Chaos, Solitons & Fractals, vol. 27, no. 5, pp. 1178- 1186, March 2006.

[26] N. Rowshanbin, S. Samavi, and S. Shirani, “Acceleration of Fractal Image Compression using Characteristic Vector Classification”, Canadian Conference on Electrical and Computer Engineering, CCECE 06, pp. 2057-2060, May 2006.

[27] F. Ce, “Fast Encoding Algorithm Based on Different Contrast Scales”, International Symposium on Microwave, Antenna, Propagation and EMC Technologies for Wireless Communications, pp. 1105-1108, 16-17 Aug. 2007.

[28] J. Han, “Speeding Up Fractal Image Compression Based on Local Extreme Points”, Eighth ACIS International Conference on Software Engineering, Artificial intelligence, Networking, and Parallel/Distributed Computing, SNPD 2007, vol. 3, pp. 732-737, 30 July-1 Aug. 2007.

[29] C. Xing, Y. Ren, and X. Li, “A Hierarchical Classification Matching Scheme for Fractal Image Compression”, Congress on Image and Signal Processing, CISP’08, pp. 283-286, 27-30 May 2008.

[30] J. Han, “Fast Fractal Image Compression using Fuzzy Classification”, Fifth International Conference on Fuzzy Systems and Knowledge Discovery, FSKD’08, vol. 3, pp. 272-276, 18-20 Oct. 2008.

[31] Z. Qin, H. Yu, and J. Ju, “Fractal Image Compression Based on Numbers of Hopping and Variance of Continuing Positive and Negative Pixels”, the 9th International Conference for Young Computer Scientists, ICYCS 2008, pp. 2954-2958, 18-21 Nov. 2008.

[32] R. Hashemian, and S. Marivada, “Improved Image Compression using Fractal Block Coding”, Proceedings of IEEE International Symposium on Micro-Nanomechatronics and Human Science, vol. 2, pp. 544-547, Dec. 2003.

[33] A. Kapoor, K. Arora, A. Jain, and G. P. Kapoor, “Stochastic Image Compression using Fractals”, Proceedings of the International Conference on Information Technology: Coding and Computing (Computers and Communications) (ITCC), pp. 574-579, April 2003.

[34] S. K. Mitra, C. A. Murthy, M. K. Kundu, B. B. Bhattacharya, and T. Acharya, “Fractal Image Compression using Iterated Function System with Probabilities”, Proceedings of International Conference on Information Technology: Coding and Computing, pp. 191-195, April 2001.

[35] C. Gungor, and A. Ozturk, “A Hash Based Image Classification Technic and Application on Fractal Image Compression”, IEEE 15th Signal Processing and Communications Applications, SIU 2007, pp. 1-4, 11-13 June 2007.

[36] M. Salarian, and H. Hassanpour, “A New Fast no Search Fractal Image Compression in DCT Domain”, International Conference on Machine Vision, ICMV 2007, pp. 62-66, 28-29 Dec. 2007.

[37] K-W C. Eugene, and G-H Ong, “A Two-Pass Improved Encoding Scheme for Fractal Image Compression”, International Conference on Computer Graphics, Imaging and Visualization, pp. 214-219, 26-28 July 2006.

[38] V. R. Prasad, Vaddella, R. Babu, and Inampudi, “Adaptive Gray Level Difference To Speed Up Fractal Image Compression”, International Conference on Signal Processing, Communications and Networking, ICSCN ‘07, pp. 253-258, 22-24 Feb. 2007.

[39] Z. Peng, T. C. S. Tian, H. Zhao, and F. Meng, “Fractal Image Coding Based on High Order Spectrum using nonparametric Estimation”, International Conference on Communications, Circuits and Systems, ICCCAS 2007, pp. 812-815, 11-13 July 2007.

[40] D. J. Duh, J. H. Jeng, and S. Y. Chen, “Fractal Image Compression with Predicted Dihedral Transformation”, 12th IEEE Symposium on Computers and Communications, ISCC 2007, pp. 661-666, 1-4 July 2007.

[41] X. Liu, Y. Zhang, and D. Li, “Implementation of A Quick Fractal Image Compression Algorithm and Its Application in Digital Certificate Solution Scheme”, IEEE International Conference on Automation and Logistics, pp. 441-445, 18-21 Aug. 2007.

[42] G. N. Melnikov, “the Fractal Method of the Image Coding”, Siberian Conference on Control and Communications, SIBCON 07, pp.153-157, 20-21 April 2007.

[43] Riccardo Distasi, Michele Nappi, and Daniel Riccio, “A Range/Domain Approximation Error-Based Approach for Fractal Image Compression”, IEEE Transactions on image processing, VOL. 15, NO. 1, January 2006.

[44] E. W. Jacobs, Y. Fisher, and R. D. Boss, “Image Compression: A Study of Iterated Transform Method”, Signal Processing, vol. 29, no. 3, pp. 251-263, Dec. 1992.

[45] L. Moltredo, M. Nappi, D. Vitulano, and S. Vitulano, “Color Image Coding Combining Linear Prediction and Iterated Function Systems”, Signal Processing, vol. 63, no. 2, pp. 157-162, Dec. 1997.

[46] B. Hurtgen, P. Mols, and S. F. Simon, “Fractal Transformation Coding of Color Images”, Visual Communication and Image Processing, SPIE Proceedings, pp. 1683-1691, 1994.

[47] Y. Zhang and L. M. Po, “Fractal Color Image Compression using Vector Distortion Measure”, Proceedings of IEEE International Conference on Image Processing, vol. 3, pp. 276-279, 23-26 October 1995.

[48] I. M. Danciu, and J. C. Hart, “Fractal Color Compression in the L*a*b* Uniform Color Space”, Data Compression Conference, pp. 540, March 1998.

[49] Z. Li, L. Zhao, and N. Y. Soma, “Fractal Color Image Compression”, Proceedings of the 13th Brazilian Symposium on Computer Graphics and Image Processing, pp. 185-192, 2000.

[50] D. D. Giusto, M. Murroni, and G. Soro, “Fractal Coding of Color Images using Earth Mover’s Distance”, Proceedings of the 2nd International conference on Mobile Multimedia Communications, Mobimedia’06, ACM, vol. 324, pp. 1-5, 18-20 Sept. 2006.

[51] Thakur N. V. and Kakde O. G. (2007b) „Color image compression with modified fractal coding on spiral architecture‟, Journal of multimedia, vol. 2(4), p.p.55-66.

[52] K. Culik and J. Kari, “Inference algorithms for WFA and image compression”. In Y. Fisher, editor, Fractal Image Compression, chapter 13, pages 243-258. Springer-Verlag, 1995.

[53] J. Kari and P. Franti, “Arithmetic coding of weighted finite automata. Theoretical Informatics and Applications”, 28(3-4):343-360, 1994.

[54] U. Hafner, Lehrstuhl fur Inf., Wurzburg Univ., Germany “Refining Image Compression with Weighted Finite Automata”, presented at the IEEE Data compression Conference, March 1996 , pp. 359-368.

[55] F. Katritzke, “Refinements of Data Compression Using Weighted Finite Automata”, Ph.D. dissertation, graph. Darst.-Siegen, Univ., Diss., 2001.

[56] F. Katritzke, W. Merzenich, M. Thomas, “Enhancements of partitioning techniques for image compression using weighted finite automata”,Elsevier, 2003.

[57] Y. Fisher, T. P. Shen and D. Rogovin, “Fractal (Self-VQ) encoding of video sequences,” VCIP, vol. 2308, pp. 1359-1370, 1994.

[58] C. S. Kim, R. C. Kim and S. U. Lee, “Fractal coding of video sequence using circular prediction mapping and noncontractive interframe mapping”, IEEE Transaction on Image Processing, vol. 7, no. 4, pp. 601-605, 1998.

[59] D. T. Hoang, P.M. Long and J. S. Vitter. Explicit bit minimization for motion-compensated video coding. In J. A. Storer and M. Cohn editors, Proc. of the Data Compression Conference, Pages 175-184, 1994.

[60] Ullrich Hafner, Stefan Frank, Michael Unger, Jurgen Albert. Hybrid Weighted Finite Automata for Image and Video Compression. Report 160 (revised) March 1997.

[61] Paul Bao, Xiaohu Ma. Video Coding Based on Bitplane and GFA Modeling. 0-7803-9584-0/06, 2006 IEEE. Pp. 109-113.

[62] Paul Bao and Xiaohu Ma, School of Computer Engineering, Nanyang Technological University, Very Low Bit rate Video Compression based on GFA Modeling. 2004, IEEE, International Conference on Multimedia and Expo (ICME).

[63] Gary J. Sullivan and Thomas Wiegand, Video Compression- From Concepts to the H.264/AVC Standard. 0018-9219/$20.00 © 2005 IEEE. Proceedings of the IEEE, VOL. 93, NO. 1, JANUARY 2005.

[64] Karel Culik II, Vladimir Valenta. Finite Automata Based Compression of Bi-level and Simple Color Images. Utah: Data Compression Conference, 1996.

[65] Xiaohu Ma, Huanqin Chen. Image Compression Method Based on Generalized Finite Automata. ICALIP, IEEE, 2008, pp. 1688-1692.

[66] Kamble, S. D., Thakur, N.V., Malik, L. G. and Bajaj, P. R. (2015b) "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-658.

[67] Thakur N. V. and Kakde O. G. (2006a) „Fractal color image compression on a pseudo spiral architecture‟, IEEE International Conference on cybernetics and intelligent systems, p.p.1-6.

[68] Thakur N. V. and Kakde O. G. (2006b) "A novel compression technique for color image database‟, IEEE International Conference on advanced computing and communications, p.p. 240–243.

[69] J. Domaszewicz and V. A. Vaishampayan, “Graph-theoretical analysis of the fractal transform”, in Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, ICASSP’95, Apr. 1995, vol. IV, pp. 2559-2562.

[70] M. Wang, R. Liu, and C. H. Liu, “Adaptive partition and hybrid method in fractal video compression”, Computers & Mathematics with Applications, vol. 51, no. 11, pp.1715-1726, 2006.

[71] T. Ochotta and D. Saupe, “Edge-based partition coding for fractal image compression”, The Arabian Journal for Science and Engineering, Special Issue on Fractal and Wavelet Methods, vol. 29(2C), 2004.

[72] K. Belloulata and J. Konrad, “Fractal image compression with regionbased functionality”, IEEE Transaction on Image Processing, Vol. 11, no. 4, pp. 351-362, Apr. 2002.

[73] K. Belloulata, “Fast fractal coding of subbands using a noniterative block clustering”, Journal of Visual Communication and Image Representation, N°.16, pp. 55-67, Feb. 2005.

[74] K. Belloulata and S. Zhu, “A New Object-Based System for Fractal Video Sequences Compression”, In the Data Compression Conference, DCC’08, Utah, USA, March 2008, pp. 508 510.

[75] K. Belloulata and S. Zhu, “A New Object-Based Fractal Stereo CODEC with quadtree-based disparity or motion compensation”, in the IEEE Int. Conf. on Acoustics, Speech and Signal Processing, ICASSP’06, Toulouse, France, 14-19 may 2006, Vol. II, pp. 481-484.

[76] S. Zhu and K. Belloulata, “A novel object-based fractal stereo video codec”, in the IEEE Int. Conf. Image Processing, ICIP’05, Genova, Italy, 22-24 Sept. 2005, Vol. I, pp. 805-808.

[77] S. Zhu, J. Tian, X. Shen, K. Belloulata, “A new cross-diamond search algorithm for fast block motion estimation”, in the IEEE Int. Conf. Image Processing, ICIP’09, Cairo, Egypt, 07-11 Nov. 2009, Vol. I, pp. 1581-1584.

[78] S. Zhu, J. Tian, X. Shen, K. Belloulata, “A Novel Cross- Hexagon Search Algorithm Based on Motion Vector Field Prediction”, in the IEEE Int. Symposium on Industrial Electronics, ISIE’09, Seoul, Korea, July 2009, pp. 1870-1874.

[79] S. Zhu, Y. Hou, Z. Wang and K. Belloulata, “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, Oct. 2010,Vol. 8, pp.360-364.

[80] Information Technology-Coding of Audio Visual Objects-Part 2: Visual, ISO/IEC 14 469-2 (MPEG-4 Visual), 1999.

[81] R. Li, B. Zeng, and M. L. Liou, “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, 1994.

[82] L.-M. Po and W.-C. Ma, “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, 1996.

[83] L. K. Liu and E. Feig, “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, 1996.

[84] S. Zhu and K. K. Ma, “A new diamond search algorithm for fast blockmatching motion estimation”, IEEE Transactions on Image Processing, vol. 9, no. 2, pp. 287-290, 2000.

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

[86] J. Y. Tham, S. Ranganath, M. Ranganath, and A. A. Kassim, “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, 1998.

[87] H. M. Chen, P. H. Chen, K. L. Yeh, W. H. Fang, and M. C. Shie and F. Lai, “Center of Mass-Based Adaptive Fast Block Motion Estimation”, EURASIP Journal on Image and Video Processing, vol. 2007, Article ID 65242, 11 pages.

[88] Ce Zhu, Xiao Lin, and Lap-Pui Chau, “Hexagon-based search pattern for fast block motion estimation”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 12, pp. 349-355, May 2002.

[89] C. H. Cheung and L.M Po, “Normalized partial distortion search algorithm for block motion estimation”, IEEE Transactions on Circuits and Systems for Video Technology, vol. 10, pp. 417-422, March 2000.

[90] Li Hong-ye Liu Ming-jun “Cross-Hexagon-based motion estimation algorithm using motion vector adaptive search technique” International Conference on Wireless Communications & Signal Processing, 2009.

[91] Kamel Belloulata, Shiping Zhu, Zaikuo Wang, “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, 2011.

[92] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, “Motion compensated interframe coding for video conferencing,” in Proc. National Telecommunications Conf., New Orleans, LA, pp. G5.3.1 –G5.3.5., 1981.

[93] J. R. Jain and A. K. Jain, “Displacement measurement and its application in interframe image coding” IEEE Transactions on Communications, vol. 29, pp. 1799-1808, Dec. 1981.

[94] A. Puri, H. M. Hang and D. L. Schilling, “An efficient block matching algorithm for motion compensated coding,” Proc. IEEE Int. Conf. Acoust., Speech, and Signal Proc., pp. 1063-1066, 1987.

[95] M. Ghanbari, “The cross search algorithm for motion estimation,” IEEE Trans. Commun., Vol. COM-38, pp. 950-953, Jul. 1990.

[96] Toshiyuki Urabe, Hassan Afzal , Grace Ho, Pramod Pancha and Mogda El Zarki , “MPEG Tool Version 1.03.Readme File”, Departmenr of Electrical Engineering, Univesity of Pennsylvania, Philadelpia.

[97] Xuan Jing and Chau Lap-Pui, “An efficient three-step search algorithm for block motion estimation,” IEEE transactions on multimedia, Vol. 6, No.3, pp. 435-438, 2004.

[98] S. D. Kamble, N. V. Thakur, L.G. Malik and P. R. Bajaj, “Fractal Video Coding Using Modified Three-step Search Algorithm for Block-matching Motion Estimation”, Computational Vision and Robotics Proceedings of International Conference on Computer Vision aand Robotics, ICCVR’14, Advances in Intelligent Systems and Computing ,Vol. 332, pp 151-162 Springer-India, 2015.

[99] Y. G. Wu and G. F. Huang,”Motion vector generation for video coding by gray prediction”, IET Comput. Vis., 2011, Vol. 5, Iss. 1, pp. 14–22.

[100] Deng, J.: ‘Control problems of grey system’, Syst. Control Lett., 1982, 5, pp. 288–294.

Downloads

Published

2016-12-01
Metrics
Views/Downloads
  • Abstract
    37
  • PDF
    15

How to Cite

D. Kamble, S., Thakur, N., and Bajaj, P. (2016). A Review on Block Matching Motion Estimation and Automata Theory based Approaches for Fractal Coding. International Journal of Interactive Multimedia and Artificial Intelligence, 4(2), 91–104. https://doi.org/10.9781/ijimai.2016.4214

Issue

Vol. 4 No. 2 (2016): IJIMAI 2016 - Regular Issue.

Section

Regular Articles