Fast Full-Search Algorithm of Fractal Image Compression for Acceleration Image Processing
DOI:
https://doi.org/10.25271/sjuoz.2023.11.1.1122Keywords:
Image Processing, FIC, Iteration Function System (IFS), Acceleration of Image, deep data learning, Signal ProcessingAbstract
A new processing algorithm based on fractal image compression is proposed for image processing efficiency. An image will partition into non-overlapping blocks called range blocks and overlapping blocks called domain blocks, with the domain blocks generally bigger than the range blocks, to achieve a rapid encoding time. This research introduced a new fast full-search algorithm approach that starts the search for the best matching domain in the range block from the closest points in the range blocks and expands the search until an acceptable match is found or the search is completed to save even more encoding time. The proposed fast full-search approach, despite its simplicity, is more efficient than the standard search method. The search reduction, peak signal to noise ratio, compression ratio, and encoding time of the suggested approach are all examined. The proposed method can encode a 512x512 grayscale Lena image in 0.36 seconds, with a total search reduction of 87% according to experimental results.
References
Y. Fisher, Fractal Image Compression: Theory and Application. New York, NY, USA: Springer-Verlag, 1995.
M. Barnsley and L. Hurd, Fractal Image Compression. Natick, MA, USA: A K Peters, 1993.
A. E. Jacquin, ‘‘Image coding based on a fractal theory of iterated contractive image transformations,’’ IEEE Trans. Image Process., vol. 1, no. 1, pp. 18–30, Jan. 1992.
S. Mozaffari, K. Faez, and M. Ziaratban, ‘‘Character representation and recognition using quad tree-based fractal encoding scheme,’’ in Proc. 8th Int. Conf. Document Anal. Recognit. (ICDAR), Aug./Sep. 2005, pp. 819–823.
S. Kiani and M. E. Moghaddam, ‘‘A multi-purpose digital image watermarking using fractal block coding,’’ J. Syst. Softw., vol. 84, no. 9, pp. 1550–1562, 2011.
C. E. Martin and S. A. Curtis, ‘‘Fractal image compression,’’ J. Funct. Program., vol. 23, no. 6, pp. 629–657, 2013.
M. Polvere and M. Nappi, ‘‘Speed-up in fractal image coding: Comparison of methods,’’ IEEE Trans. Image Process., vol. 9, no. 6, pp. 1002–1009, Jun. 2000.
B. Wohlberg and Gerhard de Jager, ''A review of the Fractal Image Compression Literature'', IEEE Transactions on Image Processing, vol. 8, No. 12, pp. 1716-1729, Dec. 1999
R. Distasi, M. Polvere, and M.Nappi, '' Split Decision functions in Fractal image Coding'',
Electronics Letters, vol.34, No. 8, pp. 751-753, April 1998.
B. Ramanurthi and A. Gersho, ''Classified Vector Quantization of Images'', IEEE Transactions on Communication, COM-34, vol. 11, pp. 1105-1115, 1986
E.W. Jacobs, Y. Fisher, and R.D. Boss, ''Image Compression: A study of the Iterated Transform Method'', Signal Processing, vol. 29, pp. 251-263, 1992.
R. Distasi, M. Nappi, and D. Riccio, ''A Range/Domain Approximation Error-Based
Approach for Fractal Image Compression'', IEEE Transactions on Image Pocessing, vol.15, No. 1, pp. 89-97, Jan. 2006.
B. B. Eqbal, ''Enhancing the Speed of Fractal Image Compression'', Optical Engineering, vol. 34, No.6, June 1995.
T. Zumbakis, and J. Valantinas, ''A New Approach to Improving Fractal Image Compression Times'', Proceedings of fourth Intlernational Symposium on Image and Signal Processing Analysis, pp. 468- 473, ISPA 2005.
M. Panigrahy, I. Chakrabarti, and A. S. Dhar, ‘‘Low-delay parallel architecture for fractal image compression,’’ Circuits, Syst., Signal Process., vol. 35, no. 3, pp. 897–917, Mar. 2016.
T. Kovács, ‘‘A fast classification based method for fractal image encoding,’’ Image Vis. Comput., vol. 26, pp. 1129–1136, Aug. 2008.
H. Wang, ‘‘Fast image fractal compression with graph-based image segmentation algorithm,’’ Int. J. Graph., vol. 1, no. 1, pp. 19–28, 2010.
X.-Y. Wang, Y.-X. Wang, and J.-J. Yun, ‘‘An improved no-search fractal image coding method based on a fitting plane,’’ Image Vis. Comput., vol. 28, no. 8, pp. 1303–1308, 2010.
Y. Zheng, G. Liu, and X. Niu, ‘‘An improved fractal image compression approach by using iterated function system and genetic algorithm,’’ Comput. Math. Appl., vol. 51, pp. 1727–1740, Jun. 2006.
N. Rowshanbin, S. Samavi, and S. Shirani, ‘‘Acceleration of fractal image compression using characteristic vector classification,’’ in Proc. Can. Conf. Elect. Comput. Eng., May 2006, pp. 2057–2060.
Y.-G. Wu, M.-Z. Huang, and Y.-L. Wen, ‘‘Fractal image compression with variance and mean,’’ in Proc. Int. Conf. Multimedia Expo (ICME), vol. 1, Jul. 2003, pp. I-353-1–I-353-6.
S. Zhu and X. Zong, ‘‘Fractal lossy hyperspectral image coding algorithm based on prediction,’’ IEEE Access, vol. 5, pp. 21250–21257, 2017.
M.-S. Wu, J.-H. Jeng, and J.-G. Hsieh, ‘‘Schema genetic algorithm for fractal image compression,’’ Eng. Appl. Artif. Intell., vol. 20, no. 4, pp. 531–538, 2007.
X. Wang, D. Zhang, and X. Guo, ‘‘Novel hybrid fractal image encoding algorithm using standard deviation and DCT coefficients,’’ Nonlinear Dyn., vol. 73, nos. 1–2, pp. 347–355, Jul. 2013.
J. H. Jeng, T. K. Truong, and J. R. Sheu, ‘‘Fast fractal image compression using the Hadamard transform,’’ IEE Proc.-Vis., Image Signal Process., vol. 147, no. 6, pp. 571–574, Dec. 2000.
S. Zhu, S. Zhang, and C. Ran, ‘‘An improved inter-frame prediction algorithm for video coding based on fractal and H.264,’’ IEEE Access, vol. 5, pp. 18715–18724, 2017.
R. da Rosa Righi, V. F. Rodrigues, C. A. Costa, and R. Q. Gomes, ‘‘Exploiting data parallelism on multicore and SMT systems for implementing the fractal image compressing problem,’’ Comput. Inf. Sci., vol. 10, no. 1, p. 34, 2016.
X.-Y. Wang, X. Guo, and D.-D. Zhang, ‘‘An effective fractal image compression algorithm based on plane fitting,’’ Chin. Phys. B, vol. 21, no. 9, Sep. 2012, Art. no. 090507.
M. E. Haque, A. A. Kaisan, M. R. Saniat, and A. Rahman, ‘‘GPU accelerated fractal image compression for medical imaging in parallel computing platform,’’ CORR, vol. abs/1404.0774, Apr. 2014.
U. Erra, ‘‘Toward real time fractal image compression using graphics hardware,’’ in Proc. Int. Symp. Vis. Comput., 2005, pp. 723–728.
B. M. Ismail, B. E. Reddy, and T. B. Reddy, ‘‘Cuckoo inspired fast search algorithm for fractal image encoding,’’ J. King Saud Univ.-Comput. Inf. Sci., vol. 30, no. 4, pp. 462–469, 2018.
A. H. Saad and M. Abdullah, "High-speed implementation of fractal image compression in low cost FPGA," Microprocessors and Microsystems, vol. 47, pp. 429-440, 2016.
W. Xing-Yuan, L. Fan-Ping, and W. Shu-Guo, ‘‘Fractal image compression based on spatial correlation and hybrid genetic algorithm,’’J.Vis.Commun. Image Represent., vol. 20, no. 8, pp. 505–510, Nov. 2009.
D. J. Duh, J. H. Jeng, and S. Y. Chen, ‘‘DCT based simple classification scheme for fractal image compression,’’ Image Vis. Comput., vol. 23, no. 13, pp. 1115–1121, Nov. 2005.
X. Wu, D. J. Jackson, and H.-C. Chen, ‘‘A fast fractal image encoding method based on intelligent search of standard deviation,’’ Comput. Electr. Eng., vol. 31, no. 6, pp. 402–421, Sep. 2005.
X.-Y. Wang, Y.-X. Wang, and J.-J. Yun, ‘‘An improved fast fractal image compression using spatial texture correlation,’’ Chin. Phys. B, vol. 20, no. 10, Oct. 2011, Art. no. 104202.
K. Jaferzadeh, K. Kiani, and S. Mozaffari, ‘‘Acceleration of fractal image compression using fuzzy clustering and discrete-cosine-transform-based metric,’’ IET Image Process., vol. 6, no. 7, pp. 1024–1030, Oct. 2012.
C. S. Tong and M. Pi, ‘‘Fast fractal image encoding based on adaptive search,’’ IEEE Trans. Image Process., vol. 10, no. 9, pp. 1269–1277, Sep. 2001.
L. E. George and A. M. Kadim, “Color image compression using fast VQ with DCT based block indexing method,” in Springer, 6754, 2011, pp. 253–263.
S. Zhu, Y. Hou, Z. Wang, and K. Belloulata, “Fractal video sequences coding with region-based functionality,” Elsevier Inc., vol. 36, no. 11, pp. 5633–5641, 2012, doi: 10.1016/j.apm.2012.01.025.
A. G. Baviskar and S. S. Pawale, “Efficient Domain Search for Fractal Image Compression Using Feature Extraction Technique,” Springer, 2012, pp. 353–365.
S. V Veenadevi and A. G. Ananth, “Fractal image compression using quadtree decomposition and huffman coding,” Signal Image Process., vol. 3, no. 2, p. 207, 2012.
R. E. Chaudhari and S. B. Dhok, “Acceleration of fractal video compression using FFT,” IEEE, pp. 1–4, 2013, doi: 10.1109/ICACT.2013.6710524.
C. Rawat and S. Meher, “A Hybrid Image Compression Scheme Using DCT and Fractal Image Compression.,” Int. Arab J. ,Information Technoly,Zarqa Univ., vol. 10, no. 6, pp. 553–562, 2013.
U. Nandi, S. Santra, J. K. Mandal, and S. Nandi, “Fractal image compression with quadtree partitioning and a new fast classification strategy,” in Proceedings of the 2015 Third International Conference on Computer, Communication, Control and Information Technology (C3IT), IEEE., 2015, pp. 1–4.
R. E. Chaudhari and S. B. Dhok, “Fast quadtree based normalized cross correlation method for fractal video compression using FFT,” J. Electr. Eng. Technol. Korean Inst. Electr. Eng., vol. 11, no. 2, pp. 519–528, 2016, doi: 10.5370/JEET.2016.11.2.519.
V. Chaurasia, R. K. Gumasta, and Y. Kurmi, “Fractal image compression with optimized domain pool size,” in 2017 International Conference on Innovations in Electronics, Signal Processing and Communication (IESC),IEEE, 2017, pp. 209–212.
K. Jaferzadeh, I. Moon, and S. Gholami, “Enhancing fractal image compression speed using local features for reducing search space,” Springer-Verlag London 2016, vol. 20, no. 4, pp. 1119–1128.
A.-M. H. Y. Saad and M. Z. Abdullah, “High-Speed Fractal Image Compression Featuring Deep Data Pipelining Strategy,” IEEE Access, vol. 6, pp. 71389–71403, 2018.
A. Banerjee, U. Biswas, and M. K. Naskar, “Fractal image compression of an atomic image using quadtree decomposition,” in 2019 Devices for Integrated Circuit (DevIC), IEEE., 2019, pp. 501–504.
A.-M. H. Y. Saad, M. Z. Abdullah, A. M. A. Nayef, and A. S. H. Abdul-Qawy, “An Improved Full-search Fractal Image Compression Method with Dynamic Search Approach,” in 2020 IEEE, pp. 15–18.
A.-M. H. Y. Saad, M. Z. Abdullah, N. A. M. Alduais, and H. H. Y. Sa’ad, “Impact of spatial dynamic search with matching threshold strategy on fractal image compression algorithm performance: study,” IEEE Access, vol. 8, pp. 52687–52699, 2020.
X.-Y. Wang and D.-D. Zhang, ‘‘Discrete wavelet transform-based simple range classification strategies for fractal image coding,’’ Nonlinear Dyn., vol. 75, no. 3, pp. 439–448, Feb. 2014
X.-Y. Wang, F.-P. Li, and Z.-F. Chen, ‘‘An improved fractal image coding method,’’ Fractals, vol. 17, no. 4, pp. 451–457, Dec. 2009.
W. Xing-Yuan, W. Na, and Z. Dou-Dou, ‘‘Fractal image coding algorithm using particle swarm optimisation and hybrid quadtree partition scheme,’’ IET Image Process., vol. 9, no. 2, pp. 153–161, Feb. 2015.
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Baydaa Sh. Z. Abood , Hanan A. R. Akkar, Amean Sh. Al-Safi
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License [CC BY-NC-SA 4.0] that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work, with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online.
