BC/NW 2009; №1 (14):10.2
ИССЛЕДОВАНИЕ СПОСОБОВ УСКОРЕНИЯ
МЕТОДА ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ
Калязин
Н.А., Гольцов А.Г.
(Москва,
Московский Энергетический Институт (ТУ), Россия)
Метод фрактального сжатия изображения – метод сжатия с
потерями, основанный на устранении избыточности, возникающей в изображениях
вследствие их самоподобия. Проще говоря, изображение содержит информацию о себе
самом.
Сжатие состоит в нахождении коэффициентов так
называемой системы итерируемых функций (IFS, Iterated Function System)
[1]. IFS — это система трехмерных аффинных преобразований, переводящих
одно изображение в другое. Преобразованию подвергаются точки в трехмерном
пространстве (координаты x и y и яркость). Аффинное преобразование обязательно
должно быть сжимающим (приводит к уменьшению участка изображения), а также
может отражать, поворачивать и перемещать участки изображения.
В процессе сжатия исходное изображение разбивается на
так называемые ранговые блоки, которые не могут пересекаться, а также на большие по размеру доменные блоки,
которые могут пересекаться. Для каждого из ранговых блоков находится наиболее
подобный ему доменный блок, вычисляются параметры аффинного преобразования и
записываются в выходной файл.
При распаковке происходит многократное применение найденных
аффинных преобразований к любому изображению. В итоге получается
изображение настолько близкое к исходному, насколько
точно были найдены коэффициенты IFS.
Метод ярко выражено асимметричный. Это означает, что
время сжатия много больше времени распаковки, так как для нахождения
коэффициентов IFS в простейшем случае для каждого рангового блока
требуется полный перебор всех доменных блоков.
Существует несколько направлений ускорения метода
фрактального сжатия. Приведем здесь основные:
- выделение особенностей доменных блоков,
- классификация доменов,
- распареллеливание вычислений [2].
На настоящий момент реализован классический алгоритм
фрактального сжатия на языке Си, распараллелен с помощью библиотеки MPI (Message Passing Interface) и
запущен на кластере МЭИ. Эксперимент показал, что коэффициент ускорения
численно очень близок к числу параллельных процессов. Этот факт говорит о том,
что фрактальный метод сжатия крайне удобен для распараллеливания.
Дальнейшие исследования будут направлены на разработку
параллельного алгоритма сжатия с использованием анализа доменных блоков с целью
сокращения числа операций попиксельного сравнения участков изображения.
Литература
1.
Barnsley, Michael F. Fractals Everywhere, second edition, Academic Press,
2. Уэльстид С. Фракталы и вейвлеты
для сжатия изображений в действии: Учебное пособие. – М.: Издательство Триумф,
2003, - 320 с.