Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Computational complexity of fractal image compression algorithm

© The Institution of Engineering and Technology
Received 10/06/2019, Accepted 16/12/2020, Revised 03/12/2020, Published 18/01/2021

This study presents insights into the computational complexity of fractal image compression (FIC) algorithms. Unlike JPEG, a fractal encoder necessitates more CPU time in contrast to the decoder. The study examines various factors that impact the encoder and its computational cost. Many researchers have dedicated themselves to the field of fractal encoding to overcome the computational cost of the FIC algorithm. Here, this study offers a look over the approaches in the aspect of time complexity. The automated baseline fractal compression algorithm is studied to demonstrate the understanding of delay in the encoder. The study establishes how various approaches trade-off between the quality of decoder, compression ratio, and CPU time. The experiment section shows the bargain between fidelity criteria of the baseline algorithm.

Inspec keywords: image coding; computational complexity; fractals; data compression

Other keywords: automated baseline fractal compression algorithm; fractal encoder; CPU time; FIC algorithm; time complexity; compression ratio; fractal image compression algorithm; computational cost; baseline algorithm; fractal encoding; computational complexity; decoder

Subjects: Computer vision and image processing techniques; Image and video coding

References

    1. 1)
      • 14. Saad, A.M., Abdullah, M.Z., Alduais, N.A., et al: ‘Impact of spatial dynamic search with matching threshold strategy on fractal image compression algorithm performance: study’, IEEE Access., 2020, 8, pp. 52687–52699.
    2. 2)
      • 17. Hamzaoui, R.: ‘Codebook clustering by self-organizing maps for fractal image compression’, Fractals, 1997, 5, (supp01), pp. 27–38.
    3. 3)
      • 60. Wang, Z., Bovik, A.C., Sheikh, H.R., et al: ‘Image quality assessment: from error visibility to structural similarity’, IEEE Trans. Image Process., 2004, 13, (4), pp. 600–612.
    4. 4)
      • 21. He, C., Yang, S.X., Huang, X.: ‘Variance-based accelerating scheme for fractal image encoding’, Electron. Lett., 2004, 40, (2), pp. 115–116.
    5. 5)
      • 32. Wang, X.Y., Wang, S.G.: ‘An improved no-search fractal image coding method based on a modified gray-level transform’, Comput. Graph., 2008, 32, (4), pp. 445–450.
    6. 6)
      • 26. Lepsoy, S., Oien, G.E., Ramstad, T.A.: ‘Attractor image compression with a fast non-iterative decoding algorithm’. 1993 IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, Minneapolis, MN, USA, 27th April 1993, Vol. 5, pp. 337–340.
    7. 7)
      • 15. Wang, L., Liu, Z.: ‘Parent block classification of fractal image coding algorithm based on ‘Shizi'Feature’. Advances in 3D Image and Graphics Representation, Analysis, Computing and Information Technology, Singapore, 2020, pp. 333–340.
    8. 8)
      • 59. Wang, Q., Bi, S.: ‘Prediction of the PSNR quality of decoded images in fractal image coding’, Math. Probl. Eng., 2016, 2016, pp. 1–13.
    9. 9)
      • 51. Tseng, C.C., Hsieh, J.G., Jeng, J.H.: ‘Fractal image compression using visual-based particle swarm optimization’, Image Vis. Comput., 2008, 26, (8), pp. 1154–1162.
    10. 10)
      • 58. Jaferzadeh, K., Kiani, K., Mozaffari, S.: ‘Acceleration of fractal image compression using fuzzy clustering and discrete-cosine-transform-based metric’, IET Image Process., 2012, 6, (7), pp. 1024–1030.
    11. 11)
      • 12. Jaferzadeh, K., Moon, I., Gholami, S.: ‘Enhancing fractal image compression speed using local features for reducing search space’, Pattern Anal. Appl., 2017, 20, (4), pp. 1119–1128.
    12. 12)
      • 10. Ilango, S.S., Seenivasagam, V., Madhumitha, R.: ‘Hybrid two-dimensional dual tree—biorthogonal wavelet transform and discrete wavelet transform with fuzzy inference filter for robust remote sensing image compression’, Cluster Comput., 2019, 22, (6), pp. 13473–13486.
    13. 13)
      • 18. Hamzaoui, R., Saupe, D.: ‘Combining fractal image compression and vector quantization’, IEEE Trans. Image Process.., 2000, 9, (2), pp. 197–208.
    14. 14)
      • 20. Raj, Y.A., Alli, P.: ‘Turtle edge encoding and flood fill based image compression scheme’, Cluster Comput., 2019, 22, (1), pp. 361–377.
    15. 15)
      • 49. Wang, J., Chen, P., Xi, B., et al: ‘Fast sparse fractal image compression’, PloS one, 2017, 12, (9), p. e0184408.
    16. 16)
      • 5. Du, S., Yan, Y., Ma, Y.: ‘Quantum-accelerated fractal image compression: an interdisciplinary approach’, IEEE Signal Process. Lett., 2014, 22, (4), pp. 499–503.
    17. 17)
      • 22. Lian, S., Chen, X., Ye, D.: ‘Secure fractal image coding based on fractal parameter encryption’, Fractals, 2009, 17, (2), pp. 149–160.
    18. 18)
      • 3. Fisher, Y.: ‘Fractal Encoding—Theory and Applications to Digital Images’.
    19. 19)
      • 43. Li, W., Pan, Q., Liang, S., et al: ‘Research on fractal image compression hybrid algorithm based on convolutional neural network and gene expression programming’, J. Algorithm. Comput. Technol., 2019, 13, p. 1748302619874196.
    20. 20)
      • 11. Duh, D.J., Jeng, J.H., Chen, S.Y.: ‘DCT based simple classification scheme for fractal image compression’, Image Vis. Comput., 2005, 23, (13), pp. 1115–1121.
    21. 21)
      • 23. Wan, C.C., Hsieh, C.H.: ‘An efficient fractal image-coding method using interblock correlation search’, IEEE Trans. Circuits Syst. Video Technol., 2001, 11, (2), pp. 257–261.
    22. 22)
      • 34. Stapleton, W.A., Mahmoud, W., Jackson, D.J.: ‘A parallel implementation of a fractal image compression algorithm’. Proc. of 28th Southeastern Symp. on System Theory, Baton Rouge, LA, USA, 31st March 1996, pp. 332–336.
    23. 23)
      • 41. Ammah, P.N., Owusu, E.: ‘Robust medical image compression based on wavelet transform and vector quantization’, Inform. Med. Unlocked, 2019, 15, p. 100183.
    24. 24)
      • 54. Wang, J., Zheng, N.: ‘A novel fractal image compression scheme with block classification and sorting based on Pearson's correlation coefficient’, IEEE Trans. Image Process., 2013, 22, (9), pp. 3690–3702.
    25. 25)
      • 38. Iano, Y., da Silva, F.S., Cruz, A.M.: ‘A fast and efficient hybrid fractal-wavelet image coder’, IEEE Trans. Image Process., 2005, 15, (1), pp. 98–105.
    26. 26)
      • 16. Saupe, D.: ‘Accelerating fractal image compression by multi-dimensional nearest neighbor search’. Proc. DCC'95 Data Compression Conf., Snowbird, UT, USA, 28th March 1995, pp. 222–231.
    27. 27)
      • 4. Sun, Y., Xu, R., Chen, L., et al: ‘Image compression and encryption scheme using fractal dictionary and Julia set’, IET Image Process., 2015, 9, (3), pp. 173–183.
    28. 28)
      • 29. Distasi, R., Nappi, M., Riccio, D.: ‘A range/domain approximation error-based approach for fractal image compression’, IEEE Trans. Image Process., 2005, 15, (1), pp. 89–97.
    29. 29)
      • 6. Lou, L., Li, Y.: ‘Research of neighborhood searching fractal image coding algorithm based on ant colony optimization’. 2015 SAI Intelligent Systems Conf. (IntelliSys), London, UK, 10th November 2015, pp. 761–764.
    30. 30)
      • 46. Schwartz, W.R., Pedrini, H.: ‘Improved fractal image compression based on robust feature descriptors’, Int. J. Image Graphics, 2011, 11, (4), pp. 571–587.
    31. 31)
      • 42. Wu, M.S.: ‘Genetic algorithm based on discrete wavelet transformation for fractal image compression’, J. Vis. Commun. Image Represent., 2014, 25, (8), pp. 1835–1841.
    32. 32)
      • 7. Zhao, D., Zhu, S., Wang, F.: ‘Lossy hyperspectral image compression based on intra-band prediction and inter-band fractal encoding’, Comput. Electr. Eng., 2016, 54, pp. 494–505.
    33. 33)
      • 8. Saad, A.H., Abdullah, M.Z.: ‘High-speed implementation of fractal image compression in low cost FPGA’, Microprocess. Microsyst., 2016, 47, pp. 429–440.
    34. 34)
      • 44. Zhang, C., Zhou, Y., Zhang, Z.: ‘Fast fractal image encoding based on special image features’, Tsinghua Sci. Technol., 2007, 12, (1), pp. 58–62.
    35. 35)
      • 24. Xing-Yuan, W., Fan-Ping, L., Shu-Guo, W.: ‘Fractal image compression based on spatial correlation and hybrid genetic algorithm’, J. Vis. Commun. Image Represent., 2009, 20, (8), pp. 505–510.
    36. 36)
      • 40. Sheeba, K., Rahiman, M.A.: ‘Gradient based fractal image compression using Cayley table’, Measurement, 2019, 140, pp. 126–132.
    37. 37)
      • 30. Monro, D.M., Woolley, S.J.: ‘Fractal image compression without searching. InProceedings of ICASSP'94’. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, Adelaide, SA, Australia, 19th April 1994, pp. V–557.
    38. 38)
      • 31. Furao, S., Hasegawa, O.: ‘A fast no search fractal image coding method’, Signal Process., Image Commun., 2004, 19, (5), pp. 393–404.
    39. 39)
      • 27. Chang, H.T., Kuo, C.J.: ‘Iteration-free fractal image coding based on efficient domain pool design’, IEEE Trans. Image Process., 2000, 9, (3), pp. 329–339.
    40. 40)
      • 63. Menassel, R., Gaba, I., Titi, K.: ‘Introducing BAT inspired algorithm to improve fractal image compression’, Int. J. Comput. Appl., 2020, 42, (7), pp. 697–704.
    41. 41)
      • 56. Qureshi, K., Hussain, S.S.: ‘A comparative study of parallelization strategies for fractal image compression on a cluster of workstations’, Int. J. Comput. Methods, 2008, 5, (3), pp. 463–482.
    42. 42)
      • 50. Ching-Hung, Y., Kwok-Wo, W.: ‘Chaos-based encryption for fractal image coding’, Chin. Phys. B., 2012, 21, (1), p. 010502.
    43. 43)
      • 57. Panigrahy, M., Chakrabarti, I., Dhar, A.S.: ‘Low-delay parallel architecture for fractal image compression’, Circuits Syst. Signal Process., 2016, 35, (3), pp. 897–917.
    44. 44)
      • 28. Kamal, A.N.: ‘Iteration free fractal image compression for color images using vector quantization, genetic algorithm and simulated annealing’, Turkish Online J. Sci. Technol., 2015, 5, (1), pp. 39–48.
    45. 45)
      • 19. Barthel, K.U., Voyé, T.: ‘Adaptive fractal image coding in the frequency domain’. Proc. of the Int. Workshop on Image Processing, Budapest, Hungary, June 1994, Vol. 45, pp. 33–38.
    46. 46)
      • 37. Davis, G.M.: ‘A wavelet-based analysis of fractal image compression’, IEEE Trans. Image Process., 1998, 7, (2), pp. 141–154.
    47. 47)
      • 39. Yang, J.: ‘Multiple description wavelet-based image coding using iterated function system’, Math. Probl. Eng., 2013, 2013, pp. 1–12.
    48. 48)
      • 48. Cao, J., Zhang, A., Shi, L.: ‘Orthogonal sparse fractal coding algorithm based on image texture feature’, IET Image Process., 2019, 13, (11), pp. 1872–1879.
    49. 49)
      • 45. Zhou, Y.M., Zhang, C., Zhang, Z.K.: ‘Fast hybrid fractal image compression using an image feature and neural network’, Chaos, Solitons Fractals, 2008, 37, (2), pp. 623–631.
    50. 50)
      • 1. Barnsley, M.F.: ‘Fractal image compression’, Notices of the AMS, 1996, 43, (6), pp. 657–662.
    51. 51)
      • 52. Wu, H.S., Zhang, F.M.: ‘Wolf pack algorithm for unconstrained global optimization’, Math. Probl. Eng., 2014, 2014, pp. 1–17.
    52. 52)
      • 47. Chaurasia, V., Chaurasia, V.: ‘Statistical feature extraction based technique for fast fractal image compression’, J. Vis. Commun. Image Represent., 2016, 41, pp. 87–95.
    53. 53)
      • 61. Belloulata, K.: ‘Fast fractal coding of subbands using a non-iterative block clustering’, J. Vis. Commun. Image Represent., 2005, 16, (1), pp. 55–67.
    54. 54)
      • 2. Jacquin, A.E.: ‘Image coding based on a fractal theory of iterated contractive image transformations’, IEEE Trans. Image Process., 1992, 1, (1), pp. 18–30.
    55. 55)
      • 55. Cardinal, J.: ‘Fast fractal compression of greyscale images’, IEEE Trans. Image Process., 2001, 10, (1), pp. 159–164.
    56. 56)
      • 36. Kumar, R.S., Manimegalai, P.: ‘Near lossless image compression using parallel fractal texture identification’, Biomed. Signal Proc. Control, 2020, 58, p. 101862.
    57. 57)
      • 35. Jackson, D.J., Ren, H., Wu, X., et al: ‘A hardware architecture for real-time image compression using a searchless fractal image coding method’, J. Real-Time Image Process., 2007, 1, (3), pp. 225–237.
    58. 58)
      • 25. Wang, Q., Liang, D., Bi, S.: ‘Fast fractal image encoding based on correlation information feature’. 2010 3rd Int. Congress on Image and Signal Processing, Yantai, People's Republic of China, 16th October 2010, Vol. 2, pp. 540–543.
    59. 59)
      • 64. Abedellatif, H., El-Shanawany, R., Zahran, O.F., et al: ‘Comparative study of wavelet transform based fractal image compression’, Menoufia J. Electron. Eng. Res., 2019, 28, (ICEEM2019-Special Issue), pp. 24–28.
    60. 60)
      • 13. Xing-Yuan, W., Dou-Dou, Z., Na, W.: ‘Fractal image coding algorithm using particle swarm optimisation and hybrid quadtree partition scheme’, IET Image Process., 2014, 9, (2), pp. 153–161.
    61. 61)
      • 33. Wang, X.Y., Wang, Y.X., Yun, J.J.: ‘An improved no-search fractal image coding method based on a fitting plane’, Image Vis. Comput., 2010, 28, (8), pp. 1303–1308.
    62. 62)
      • 53. Lee, C.K., Lee, W.K.: ‘Fast fractal image block coding based on local variances’, IEEE Trans. Image Process., 1998, 7, (6), pp. 888–891.
    63. 63)
      • 62. Tong, C.S., Pi, M.: ‘Fast fractal image encoding based on adaptive search’, IEEE Trans. Image Process., 2001, 10, (9), pp. 1269–1277.
    64. 64)
      • 9. Roy, S.K., Kumar, S., Chanda, B., et al: ‘Fractal image compression using upper bound on scaling parameter’, Chaos, Solitons Fractals, 2018, 106, pp. 16–22.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ipr.2019.0489
Loading

Related content

content/journals/10.1049/iet-ipr.2019.0489
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address