Идея фрактального метода сжатия изображений была сформулирована в начале 1980-х годов [1] и концептуально заключается в следующем. Для заданного изображения по специальным правилам строится система сжимающих отображений, для которых оно является аттрактором. Тогда, в силу теоремы о неподвижной точке, итерационный процесс, сформированный на базе этих отображений, сходится к своему аттрактору при любом выборе начального изображения. Эффект сжатия достигается за счет того, что вместо исходного изображения для его восстановления необходимо хранить лишь коэффициенты преобразования.
К числу отличительных можно отнести ряд особенностей, обуславливающих интерес исследователей к данному методу сжатия на протяжении более двух десятилетий. Это: а) высокий коэффициент сжатия (т.е. отношение объема исходной информации к объему кода). Так, для изображений, обладающих самоподобием, он достигает 2000; б) независимость качества декодированного изображения от масштаба его просмотра; в) существенная асимметричность, т.е. время кодирования заметно больше времени декодирования.
Одной из главных проблем фрактального метода сжатия изображений, по сравнению с другими, остается высокое время кодирования. Привлекательность самой идеи фрактального метода сжатия и его достоинства притягивает исследователей к развитию и совершенствованию алгоритмов его реализующих. Предлагаемые модификации касаются практически всех его сторон. В большинстве опубликованных работ по данной теме предлагаются различные методы, направленные на снижение объема перебора доменных блоков и, как следствие, — сокращение времени кодирования. Это: модификации способа разбиения доменов, классификация доменов с помощью дискретного косинусоидального и вейвлет-преобразования, R-деревьев, самоорганизующихся нейронных сетей, использование генетических алгоритмов, меры информационной энтропии для поиска оптимальных доменов и др. Менее разработанной областью исследований данной темы, является применение нелинейных сжимающих отображений.
Однако, возможно в силу коммерческой составляющей работ данного направления и, как следствие отсутствие удовлетворительных описаний рассматриваемых алгоритмов, предлагаемые модификации воспринимаются, скорее, как результат интуитивных и спонтанных импровизаций, нежели обоснованный итог некоторой серии вычислительных экспериментов. Вместе с тем, каждый исследователь, начинающий путь в этой области, нуждается в наличии тщательного сопоставительного анализа основных алгоритмов. Проведение и последующее изложение такого анализа и является основной целью данной работы.
Автором была проведена серия экспериментов по сравнительному анализу базовых алгоритмов, подробно описанных в литературе [1]. Результаты экспериментов и гипотезы выявленных недостатков были изложены в [2]. Напомним, было выражено предположение, что в FE-алгоритме не всегда выбираются оптимальные домены с использованием упрощенного набора характеристик. С целью проверки этой гипотезы и вскрытия выявленных различий был разработан дополнительный программный модуль, позволяющий подсчитывать число совпадений в обоих алгоритмах при выборе домена. Совпадение здесь понимается так: для одного ранга в обоих алгоритмах выбирается тот же домен. Изображение оставалось тем же. Настройки кодирования соответствуют тем, которые использовались в [2], но с той разницей, что базовый алгоритм работает в режиме поиска наилучшего домена. Это означает, что при обработке каждого рангового блока осуществляется перебор всех доменных блоков, без остановки по достижении допустимой погрешности, и выбирается наилучший. Это позволяет проводить корректное сравнение.
В результате проведения вычислительных экспериментов было установлено, что для 99.73 % ранговых блоков FE-алгоритм выбрал не те же домены, которые были выбраны в базовом алгоритме, т.е. — не наилучшие. Таким образом, напрашивается вывод, что процедура отбора по значениям характеристик в FE-алгоритме неадекватно выявляет близость соответствия между доменными и ранговыми блоками.
Идея введения упрощенного набора критериев с целью существенного снижения объема вычислений является привлекательной, но в большинстве случаев сравнения доменов с рангами этот набор не позволяет выявить оптимальный домен. То есть данный набор является не вполне адекватным основному критерию. Поэтому представляется целесообразным вместо этого набора использовать основной критерий, но применять его к уменьшенным копиям рассматриваемых пар домен-ранг. Это можно реализовать алгоритмом, который аналогичен базовому [2], за исключением 2-го и 3-го шагов. На шаге 2 при генерации доменных блоков для каждого из них строятся его уменьшенные копии. Первая копия имеет размер 2x2 пикселей, вторая — 4x4 пикселей и т.д. до исходного размера домена. На шаге 3 перед началом обработки очередного рангового блока сначала строятся его уменьшенные копии аналогичным образом. Затем проводится многоуровневый отбор наилучшего доменного блока для данного ранга. На 0-м уровне сравниваются уменьшенные копии размером 2x2 пикселей данного ранга и домена. При сравнении запоминаются величина Lkij (средняя пиксельная ошибка) и наилучшая ориентация для каждого доменного блока. Для последующего сравнения отбираются только m (например, m=20) доменных блоков с наименьшим значением величины Lkij. На всех последующих уровнях сравниваются уменьшенные копии соответствующего размера рангового и доменных блоков, но уже только в сохраненной на первом уровне наилучшей ориентации каждого отдельного домена. Этот процесс продолжается до последнего уровня уменьшенных копий рангового блока. На последнем уровне сравнения отбирается только один доменный блок с наименьшей величиной Lkij. Преимущество такой модификации алгоритма заключается в сохранении основного критерия сравнения и его применении последовательно к уменьшенным копиям пар ранг-домен, что позволит на первых же уровнях сравнения отбрасывать неоптимальные домены и оставлять только перспективные.
Литература
- Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. Учебное пособие. — М.: Издательство «Триумф», 2003
- Бубличенко А.В. Сравнительный анализ базового и FE-алгоритмов фрактального сжатия изображений. Материалы III международной научно-технической конференция молодых учёных и студентов «Информатика и компьютерные технологии 2007» — Донецк. ДонНТУ, 2007