Быстродействующий алгоритм фрактального сжатия изображений Текст научной статьи по специальности «Компьютерные и информационные науки»
Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Шарабайко Максим Павлович, Осокин Александр Николаевич
Исследованы наиболее эффективные с точки зрения уменьшения времени сжатия модификации алгоритма фрактального сжатия изображений . На основе исследования программных реализаций синтезирован быстродействующий алгоритм фрактального сжатия, использующий классификацию блоков , распараллеливание процесса сжатия, переупорядочивание пикселей блоков в памяти. Данные модификации существенно ускоряют процесс сжатия (до 1000 раз по сравнению с базовым) при сохранении размера сжатого файла и несущественных потерях в качестве. Модификация разбиения методом квадродерева упрощает процесс разбиения и работу с изображениями неквадратных размеров.
Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Шарабайко Максим Павлович, Осокин Александр Николаевич
The most efficient modifications of fractal image compression algorithm from the point of view of compression time decrease have been studied. The fast fractal compression algorithm using block classification , compression process parallelism, reodering block pixels in memory was synthesized on the basis of software implementation investigation. These modifications accelerate considerably the compression process (up to 1000 times in comparison with the basic one) preserving the size of a compressed file and having insignificant quality losses. The quadtree partitioning modification simplifies partitioning and work with nonsquare size images.
Текст научной работы на тему «Быстродействующий алгоритм фрактального сжатия изображений»
БЫСТРОДЕЙСТВУЮЩИЙ АЛГОРИТМ ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ
М.П. Шарабайко, А.Н. Осокин
Томский политехнический университет E-mail: sme_box@tpu.ru
Исследованы наиболее эффективные с точки зрения уменьшения времени сжатия модификации алгоритма фрактального сжатия изображений. На основе исследования программных реализаций синтезирован быстродействующий алгоритм фрактального сжатия, использующий классификацию блоков, распараллеливание процесса сжатия, переупорядочивание пикселей блоков в памяти. Данные модификации существенно ускоряют процесс сжатия (до 1000 раз по сравнению с базовым) при сохранении размера сжатого файла и несущественных потерях в качестве. Модификация разбиения методом квадродерева упрощает процесс разбиения и работу с изображениями неквадратных размеров.
Фрактальное сжатие изображений, классификация блоков, классификация Фишера, классификация на основе центра масс, классификация Саупе, классификация Саупе
Фишера, разбиение квадродеревом.
Fractal image compression, block classification, Fisher classification, Saupe classification, mass-center classification, quadtree partitioning.
Фрактальное сжатие изображений - алгоритм сжатия с потерями, основанный на представлении изображения в более компактной форме с помощью коэффициентов систем итерируемых кусочно-определённых функций (PIFS - Partitioned Iterated Function Systems), как правило, являющихся аффинными преобразованиями частей изображения [1]. Степень сжатия изображений может достигать 100:1 [2].
Фрактальная компрессия стала практически реализуемой после введения Арно Жаквином (Arnaud Jacquin) [3] понятия итерируемых кусочно-определённых функций, в которых, каждое из набора отображений покрывает изображение частично, а не целиком.
На текущий момент основными недостатками алгоритма являются большие временные затраты сжатия и невозможность гарантировать ту или иную степень потерь (качество декодированного изображения зависит от самоподобия сжимаемого). Достоинства включают степень сжатия на уровне JPEG при сравнительно одинаковом качестве, быстрый процесс декодирования, независимость восстанавливаемого изображения отраз-решения (хранится структура изображения, а не данные о пикселях), потери проявляются в виде размытия изображения, а не в виде высокочастотных шумов в области контрастных переходов, свойственный алгоритму JPEG.
Характеристики современных ЭВМ позволяют преодолеть проблему скорости сжатия, сохраняя перечисленные достоинства. Последние могут найти широкое применение в области сжатия видеоинформации, например, в технологии Intel Wireless Display [4].
Целью работы является исследование имеющихся модификаций алгоритма и их объединение для увеличения быстродействия базового.
В общих чертах, фрактальное сжатие можно разделить на два этапа:
1) разбиение изображения на множество ранговых блоков и на множество доменных блоков (которые могут перекрывать друг друга);
2) применение преобразований для каждой пары доменный-ранговый блок: геометрическое, отображающее доменный блок в ранговый, и аффинное, изменяющее значения яркости доменного блока до максимального соответствия значениям яркости рангового блока.
От схемы разбиения, используемой на первом этапе, зависит качество сжатия. Чем больше доменных блоков, тем больше шанс найти наиболее подобный ранговому блок.
На втором этапе необходимо так преобразовать доменный блок, чтобы он был максимально подобен ранговому. Общая формула преобразования значений пикселей доменного блока выглядит следующим образом:
где D* и Д - преобразованный и исходный г-й доменный блок соответственно; s - коэффициент изменения контраста; о - коэффициент сдвига по яркости.
Помимо непосредственного преобразования значений пикселей по формуле (1), доменный блок также может быть подвергнут общему масштабированию (уменьшение размеров до размеров рангового блока, например, интерполяцией или простым прореживанием), повороту и другим аффинным преобразованиям.
Преобразованный доменный блок должен соответствовать ранговому блоку как можно сильнее, поскольку именно так ранговый блок будет восстановлен при декодировании. Для оценивания расхождения (расстояния) между преобразованным доменным и данным ранговым блоками, необходимо ввести соответствующую метрику. Обычно используется функция среднеквадратического отклонения (СКО) [1, 2, 5]:
Q = £ (D* - R)2 =£ ((sDt + о)- R )2, (2)
где Rt - г-й ранговый блок, D,‘ и Д - преобразованный и исходный г-й доменный блок соответственно, N - количество пикселей в ранговом блоке.
Очевидно, чем меньше расстояние (2) между блоками, тем больше они подобны.
Коэффициенты 5 и о можно найти из формулы (2), взяв частные производные по этим переменным.