РЕАЛИЗАЦИЯ ФРАКТАЛЬНОГО СЖАТИЯ И ДЕКОМПРЕССИИ ИЗОБРАЖЕНИЙ ПАРАЛЛЕЛЬНО-КОВЕЙЕРНЫМ СПОСОБОМ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

  • М.Д. Чекина
Ключевые слова: Фракталы, фрактальное сжатие изображений, ПЛИС, реконфигурируемые вычислительные системы

Аннотация

Фрактальные алгоритмы находят все большее количество областей применения –
от компьютерной графики до моделирования сложных физических процессов, но для их
программной реализации требуются значительные вычислительные мощности. Фрак-
тальное сжатие изображений отличается высокой степенью компрессии данных при хо-
рошем качестве восстановленного изображения. Целью данной работы является повыше-
ние производительности реконфигурируемых вычислительных систем (РВС) при реализа-
ции фрактального сжатия и декомпрессии изображений. В работе описаны разработан-
ные методы фрактального сжатия и последующей декомпрессии изображений, реализо-
ванные параллельно-конвейерным способом для РВС. Основная идея параллельной реализа-
ции фрактального сжатия изображений сводится к параллельному выполнению попарного
сравнения доменных и ранговых блоков. Для достижения наилучшей производительности
необходимо одновременно сравнивать максимальное количество пар. При практической
реализации фрактального сжатия изображений на РВС учитываются такие критические
ресурсы, как количество входных каналов и количество логических ячеек ПЛИС. Для задачи
фрактального сжатия изображения критическим ресурсом являются каналы данных, по-
этому параллельная организация вычислений заменяется параллельно-конвейерной после
выполнения редукцию производительности параллельной вычислительной структуры. По-
дача каждого операнда в вычислительную структуру осуществляется последовательно
(побитово), что экономит вычислительный ресурс и уменьшает простой оборудования.
Для хранения коэффициентов системы итерируемых функций, кодирующих изображение,
введена структура данных, задающая отношения между номерами ранговых и доменных
блоков и соответствующими параметрами. Для удобства последующей декомпрессии
элементы массива, кодирующего сжатое изображение, упорядочены по номерам ранговых
блоков, что позволяет избежать двойной косвенной адресации в вычислительной структу-
ре. Представленный подход позволяет масштабировать параллельно-конвейерную про-
грамму на любое количество программируемых логических интегральных схем (ПЛИС).
Практическая реализация фрактального сжатия изображений, выполненная на реконфи-
гурируемом компьютере Терциус-2, содержащем восемь ПЛИС, обеспечивает ускорение в
15000 раз по сравнению с универсальным многоядерным процессором и в 18–25 раз по срав-
нению с существующими решениями для ПЛИС. Реализация декомпрессии изображения на
реконфигурируемом компьютере показывает ускорение в 380 раз по сравнению с аналогич-
ной реализацией для многоядерного универсального процессора.

Литература

1. Doris Chen. Deshanand Singh Fractal Video Compression in OpenCL: An Evaluation of
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.
Опубликован
2021-02-25
Выпуск
Раздел
РАЗДЕЛ III. РЕКОНФИГУРИРУЕМЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ