THE PARALLEL-PIPELINED IMPLEMENTATION OF THE FRACTAL IMAGE COMPRESSION AND DECOMPRESSION FOR RECONFIGURABLE COMPUTING SYSTEMS
Abstract
Fractal algorithms find an increasing number of areas of application - from computer
graphics to modeling complex physical processes, but their software implementation requires
significant computing power. Fractal image compression is characterized by a high degree of data
compression with good quality of the reconstructed image. The aim of this work is to improve the
performance of reconfigurable computing systems (RCS) when implementing fractal compression
and decompression of images. The paper describes the developed methods of fractal compression
and subsequent decompression of images, implemented in a parallel-pipeline method for RCS. Themain idea of parallel implementation of fractal image compression is reduced to parallel execution
of pairwise comparison of domain and rank blocks. For best performance, the maximum
number of pairs must be compared simultaneously. In the practical implementation of fractal image
compression on the DCS, such critical resources as the number of input channels and the
number of FPGA logical cells are taken into account. For the problem of fractal image compression,
data channels are a critical resource; therefore, the parallel organization of computations is
replaced by parallel-pipeline, after the performance reduction of the parallel computational structure
is performed. Each operand goes into the computational structure sequentially (bit by bit) to
save computational resources and reduce equipment downtime. To store the coefficients of the
iterated functions system encoding the image, a data structure has been introduced that specifies
the relation between the numbers of rank and domain blocks and the corresponding parameters.
For the convenience of subsequent decompression, the elements of the array encoding the compressed
image are ordered by the numbers of the rank blocks, which avoids double indirect addressing
in the computational structure. Applying this approach for parallel-pipeline programs
allows scaling computing structure to plurality programmable logic arrays (FPGAs). A practical
implementation performed on a reconfigurable computer Tertius-2 containing eight FPGAs provides
an acceleration of 15000 times compared to a universal multi-core processor and 18–25
times compared to existing solutions for FPGAs. The implementation of image decompression on a
reconfigurable computer shows an acceleration of 380 times in comparison with the similar implementation
for a multi-core general-purpose processor.
References
CPUs, GPUs, and FPGAs as Acceleration Platforms, 2013 18th Asia and South Pacific Design
Automation Conference, pp. 297-304.
2. Barnsley M., Hurd L.P. Fractal Image Compression. Wellsley Massachusetts: A.K. Peters Ltd,
1993, 224 p.
3. Fisher Y. Fractal Image Compression: Theory and Application. Springer-Verlag, New York,
1995.
4. Boychenko I.V., Kulbaev S.S., Nemerov A.A., Golenkov V.V. Eksperiment po fraktal'nomu
szhatiyu rgb izobrazheniy na vychislitel'nom klastere [Experiment on fractal compression of
rgb images on a computing cluster], Izvestiya Tomskogo politekhni-eskogo universiteta [Bulletin
of the Tomsk Polytechnic University], 2012, Vol. 321, No. 5, pp. 87-92.
5. Munesh Singh Chauhan, Ashish Negi, Prashant Singh Rana. Fractal Image Compression using
Dynamically Pipelined GPU Clusters, Proceedings of the Second International Conference
on Soft Computing for Problem Solving (SocProS, 2012), December 28-30, 2012.
6. Mohammed Ismail B., Eswara Reddy B., Bhaskara Reddy T. Cuckoo inspired fast search algorithm
for fractal image encoding, Journal of King Saud University – Computer and Information
Sciences, 2016.
7. Md. Enamul Haque, Abdullah Al Kaisan, Mahmudur R Saniat, and Aminur Rahman. GPU
Accelerated Fractal Image Compression for Medical Imaging in Parallel Computing Platform,
arXiv:1404.0774v1 [cs.DC] 3 Apr 2014.
8. Munesh Singh Chauhan, Ashish Negi. Fractals Image Rendering and Compression using GPUs,
International Journal of Digital Information and Wireless Communications (IJDIWC) 2(1): 1-6
The Society of Digital Information and Wireless Communications, 2012. ISSN 2225-658X.
9. A-M.H.Y. Saad, M.Z. Abdullah High-speed implementation of fractal image compression in
low cost FPGA, Microprocessors and Microsystems 47. August 2016. Doi:
10.1016/j.micpro.2016.08.004.
10. A-M.H.Y. Saad, M.Z. Abdullah High-Speed Fractal Image Compression Featuring Deep Data Pipelining
Strategy, IEEE Access PP(99):1-1 · November 2018. Doi: 10.1109/ACCESS.2018.2880480.
11. Son T.N., Hung O.M., Xuan D.T., Tran V.L., Dzung N.T., Hoang T.M. Implementation of Fractal
image compression on FPGA, 4th International Conference on Communications and Electronics
ICCE 2012, online IEEExplorer, Hue City, Vietnam. 1-3 Aug. 2012, pp. 339-344.
12. Padmavati S. Vaibhav Meshram FPGA Implementation for Fractal Quadtree Image Compression,
International Journal of Computer Sciences and Engineering, Oct. 2018, Vol. 6, Issue-10.
13. Thai Nam Son Tran V Long, Hoang Manh Thang, Nguyen Tien Dzung. Efficient implementation
of a fractal color image compression on FPGA, 2013 International Conference of Soft
Computing and Pattern Recognition (SoCPaR), 2013. Doi: 10.1109/SOCPAR.2013.7054124.
14. Thai Nam Son Thang Manh Hoang, Nguyen Tien Dzung Nguyen Hoang Giang Fast FPGA Implementation
of YUV-based Fractal Image Compression, 2014 IEEE Fifth International Conference
on Communications and Electronics (ICCE), 2014. Doi: 10.1109/CCE.2014.6916745.
15. Guzik V.F., Kalyaev I.A., Levin I.I. Rekonfiguriruemye vychislitel'nye sistemy [Reconfigurable
computing systems], ed. by I.A. Kalyaeva. Rostov-on-Don: Izd-vo YUFU, 2016, 472 p.
16. Beklemishev D.V. Kurs analiticheskoy geometrii i lineynoy algebry [A course in analytic geometry
and linear algebra]. Moscow: Vyssh. shk., 1998, 320 p.
17. Levin I.I., Dordopulo A.I., Sorokin D.A., Kalyaev Z.V., Doronchenko Yu.I. Rekonfiguriruemye
komp'yutery na osnove plis Xilinx Virtex Ultrascale [Xilinx Virtex Ultrascale PLD-based reconfigurable
computers], V sb.: Parallel'nye vy-chislitel'nye tekhnologii (PaVT'2019).
Korotkie stat'i i opisaniya plakatov XIII Mezh-dunarodnoy nauchnoy konferentsii [Parallel
computational technologies (PCT 2019)], 2019, pp. 288-298.
18. Dordopulo A.I., Levin I.I. Metody reduktsii vychisleniy dlya programmirovaniya gibridnykh
rekonfiguriruemykh vychislitel'nykh sistem [Computation reduction methods for programming
hybrid reconfigurable computing systems], XII mul'tikonferentsiya po problemam upravleniya
(MKPU-2019): Mater. konferentsii [Materials of the XII multiconference on management
problems 2019]: in 4 vol., 2019, pp. 78-82.
19. Kolmogorov A.N., Fomin S.V. Elementy teorii funktsiy i funktsional'nogo analiza [Elements
of the theory of functions and functional analysis]. 4th ed. Moscow: Nauka, 1976, 544 p.
20. Levin I.I., Pelipets A.V. Effektivnaya realizatsiya rasparallelivaniya na rekonfiguriruemykh
sistemakh [Efficient Parallel Execution on Reconfigurable Systems], Vestnik komp'yuternykh i
informatsionnykh tekhnologiy [Herald of computer and information technologies], 2018, No. 8,
pp. 11-16.
