Источник: «Информационные управляющие системы и компьютерный мониторинг» — 2010 / Сборник материалов I Всеукраинской научно-технической конференции студентов, аспирантов и молодых ученых «Информационные управляющие системы и компьютерный мониторинг» (ИУС и КМ - 2010). — Донецк, ДонНТУ — 2010, Том II, с. 8.
УДК 519.8:004.02
Анализ
модификаций алгоритмов фрактального сжатия изображений
Анастасова
Е.А., Беловодский В.Н.
Донецкий национальный технический университет
Компьютерных наук и технологий
E-mail: anastasovakaterina@rambler.ru
В данной статье предлагается краткая
сравнительная характеристика существующих методов модификации базового
фрактального алгоритма сжатия изображения.
Введение
Изображения широко используются в различных сферах, как повседневной жизни человека, так и в конкретных областях науки. Очевидно, что качество изображений анализируемых пользователем играет не последнюю роль. Для хранения изображений с высоким качеством требуются большие объемы памяти, что может создавать неприемлемые ситуации при работе с изображениями. В зависимости от требований, выдвигаемых к изображению, существует возможность, варьируя методы сжатия, получать приемлемые характеристики изображения. Каждый из алгоритмов и их модернизации имеет ряд характеристик, анализируя которые можно варьировать их применение в зависимости от поставленной задачи.
Постановка задачи
В настоящее время существует достаточное количество направлений улучшения алгоритмов сжатия изображений. В результате выполнения работы ставится задачей получить сравнительный анализ существующих методов модификации фрактальных алгоритмов сжатия. В качестве критерия для сравнения предлагается анализировать основные характеристики результата работы методов и их этапы работы.
Решение проблемы
В первую
очередь укажем основные позиции для базового фрактального алгоритма. Базовый
алгоритм предполагает разбиение исходного изображения на доменные и ранговые
блоки. После чего для каждого ранга перебирают доменные блоки (для каждого
варианта ориентации домен сжимают до размеров рангового блока и определяют
оптимальные значения коэффициентов преобразования методом наименьших
квадратов). Затем вычисляют нормированное значение параметра L, который
характеризует соответствие полученного сжатого доменного блока в его ориентации
ранговому блоку. Возможно два режима работы алгоритма (с поиском и без поиска
лучшего домена). В режиме с поиском лучшего домена для каждого ранга
перебираются все домены, и выбирается с минимальным L. В режиме без поиска
наилучшего домена полный перебор доменов останавливают, как только определяется
такой i-й домен и его j-я ориентация, что значение его параметра L не превышает заданной
допустимой ошибки. Теперь поэтапно рассмотрим существующие методы для
модификации базового алгоритма. Наиболее распространенной модификацией базового
алгоритма является FE-алгоритм. С целью снижения
вычислительных затрат в FE-алгоритме
выделяют пять характеристик, которые описывают доменные и ранговые блоки. И сначала,
проводится именно их сравнение. Это значительно сокращает объем вычислений. Эти
характеристики: стандартное отклонение, асимметрия, межпиксельная контрастность,
коэффициент 
, которые характеризует отличия значений пикселов от значения
центрального пикселя, максимальный градиент – максимум среди горизонтального и
вертикального градиентов. При обработке рангового блока вычисляют его вектор
характеристик, потом вычисляют расстояния между вектором характеристик данного
ранга и вектором характеристик каждого домена. Процедура отбора доменов
является своеобразным фильтром, который значительно ограничивает количество
доменов, которые перебираются [1]. Для ускорения
процесса также является возможным в качестве критерия оптимальности использовать
коэффициент корреляции Пирсона:
r’=
(R,D)
Чем лучше реальная зависимость R от D аппроксимируется линейной, тем ближе по модулю к 1 будет их коэффициент корреляции. Использование этого коэффициента позволяет сразу оценить оптимальность текущего домена для данного ранга, без расчета коэффициента преобразования контраста и яркости. Таким образом, эти коэффициенты рассчитываются один раз для каждого ранга. Выполняется преобразование формул, описывающих соотношения для определения коэффициентов яркости и контраста, через коэффициент корреляции. Кроме того, заранее вычисляется среднеквадратичное отклонение яркостей пикселей рангов и доменов. После этого становится возможным рассматривать только те домены, которые удовлетворяют неравенству:
,
т.е. контрастность домена должна быть выше контрастности ранга (предлагается подсчитывать среднее значение яркости пикселей для каждого ранга, а не коэффициент яркости для каждого домена, что значительно ускоряет процесс сжатия в среднем в 9,35 раза) [2]. Также существует возможность варьировать и другие характеристики: результат спектрального анализа Фурье, вейвлет анализа, характеристики оттенка или текстуры изображения. Кроме того, алгоритм такого рода эффективно реализован с использованием самообучающихся карт Кохонена [3].
Важным направлением в ускорении алгоритмов сжатия является алгоритмы с учетом частот использования доменов. Общая схема способа: каждому домену присваивается величина N, которая означает количество рангов, для которых он был принят, при обработке каждого ранга домены будут просматриваться в порядке уменьшения этой величины, при очередном выборе домена эта величина будет обновляться.
При анализе литературы по данной тематике было отмечено, что большой интерес для исследователей разных стран составляют алгоритмы с использованием обрамляющих доменов. Перед началом обработки очередного ранга формируются домены, которые обрамляют его. Каждый i-й обрамляющий домен имеет единый геометрический центр со своим рангом и превышает его на величину 2i, где i = 1,2,3,…и т.д. Формирование этих доменов останавливается, как только будет сформирован такой, размер которого в два раза превышает размер ранга. Обрамляющие домены включаются к начальносформированному множеству доменов. При их переборе рассматриваются вначале обрамляющие домены, а потом – другие. Наиболее интересно – высокий процент рангов, для которых выбраны обрамляющие домены, на фоне ухудшения средней пиксельной ошибки.
Широко применяется использование пирамидального метода сравнения. Суть алгоритма следующая. Вместо набора используется непосредственно основной критерий, но применяется он к уменьшенным копиям сравниваемых пар домен-ранг.
При применении нелинейного отображения следует отметить что значение влияния отличается в зависимости от алгоритма. В базовом алгоритме наблюдаются значительные расхождения, а в FE-алгоритме они в большинстве случаев не так значительны [1].
Еще
одним методом повышения эффективности является
алгоритмы, в своей основе имеющие нетривиальные схемы разбиения изображения на
блоки. Наиболее популярным является алгоритм квадро-дерева. Он позволяет
представить всю схему разбиения в виде древовидной структуры, в которой каждый
узел, если он не является последним в ветви, может иметь четыре потомка (рис.
а) ).
а) б)
Достоинствами метода является простота реализации и
удобство кодирования древовидной структуры, но он считается достаточно жестким
и с точки зрения степени сжатия выгодно минимизировать количество блоков в
схеме разбиения. Для повышения гибкости предлагается использовать
перекрывающиеся ранговые блоки (рис. б) ). Это обеспечивает более рациональное
перекрытие изображения блоками по сравнению с алгоритмом квадро-дерева. В
результате общее количество блоков уменьшается за счет увеличения количества
блоков большего размера. Критерием для выбора размера служит дисперсия яркости
пикселей. Такой подход требует больше вычислений, но уменьшение числа рангов
позволяет повысить коэффициент сжатия [2]. Относительно новым
направлением в модернизации фрактальных методов являются алгоритмы, основанные на минимизации
RD-функции Лагранжа. В качестве начальных данных берется некоторый входной набор данных,
которому в результате выполнения процедуры сжатия-восстановления ставится в
соответствие выходной набор данных той же природы, Y=F(X,u), где u - набор управляющих параметров
алгоритма сжатия F.
Можно настраивать
алгоритм кодирования F
на необходимые
характеристики [4]. Заслуживающими внимания являются работы описывающие методы
анализа эффективности ортогональных преобразований, предназначенных для сжатия
коррелированных данных; для сжатия данных описывается дискретное псевдокосинусное преобразование
(ДПКП), новые быстрые алгоритмы вычисления ДПКЛ, на базе которых возможно получать
схему компрессиистатических изображений (аналогична методу JPEG характеристики).
Для обработки неподвижных и динамических изображений предлагаются формализующие
процедуры анализа и синтеза схем компрессии цифровых изображений на основе
дискретных ортогональных преобразований. Оценки вычислительных затрат
показывают, что алгоритм на основе ДПКЛ не уступает JPEG в том числе в части,
касающейся вычислительной сложности реализации [4]. В работах иностранных
авторов часто упоминается метод для уменьшения времени кодирования за счет
сокращения размера бассейна доменов на основе стоимости энтропии каждого
доменного блока. Экспериментальные результаты на стандартных изображениях показывают,
что предложенный метод дает превосходную производительность по сравнению с
обычными алгоритмами фрактального кодирования. Этот метод основан на удалении
доменного блока с высокой энтропией, применим в ситуациях, когда
требуется очень малое время кодировки и допускается ухудшение качества и
является весьма сопоставимым с другими методами ускорения. Таким образом, все бесполезные домены будут удалены из пула, обеспечивая более
продуктивный доменный бассейн. Предлагаемый метод, как представляется [5].
Выводы
Краткие
замечания и выводы по проведенному анализу приведены в сравнительной таблице 1.
Таблица
1
|
Модификация |
Вид изображения |
Время кодирования |
Средняя пиксельная ошибка |
Коэффициент сжатия |
|
Учет частоты использования доменов |
фотореалистичные |
Уменьшение на 7-12% |
Снижение на 4 % |
Практически не изменился |
|
с резкими переходами |
Уменьшение на 33-42% |
На 14% |
-//- |
|
|
Обрамляющие домены |
фотореалистичные |
Уменьшение на 20-40% |
Ухудшение на 28-35% |
Увеличивается на 10-28% (наиболее высокий показатель) |
|
с резкими переходами |
Уменьшение на 9-15% |
Ухудшение на 30-43% |
- |
|
|
Пирамидальный метод сравнения |
фотореалистичные |
Повышение в 3-3,5 раз |
Улучшение на 43% |
Уменьшение на 40-53% |
|
с резкими переходами |
-//- |
-//- |
-//- |
|
|
Нелинейное отображение |
фотореалистичные |
Уменьшение на 13-39% |
Ухудшение <=10% |
Уменьшается на 4-16% |
|
с резкими переходами |
Уменьшение до 58% |
малы |
Может увеличиваться не больше чем на 11% |
|
|
Использование квадро-дерева |
требует
больше вычислений, но уменьшение числа рангов позволяет повысить коэффициент
сжатия. |
|||
|
Применение ДПКЛ |
по всем ключевым характеристикам не уступает JPEG |
|||
|
Основанные на показателях энтропии |
дает превосходную производительность по сравнению с обычными алгоритмами фрактального кодирования |
|||
Список источников:
1. Бубличенко, А.В. Алгоритмы сжатия изображений: сравнительный анализ и модификации / А.В. Бубличенко, В.Н. Беловодский / Квалификационная работа магистра. – 2008.
2. Илюшин С.В. Фрактальное сжатие телемедицинских изображений / С.В. Илюшин, С.Д. Свет / «Электросвязь», №4 – 2009.
3.
Прохоров, В.Г.
Использование карт Кохонена для ускорения фрактального сжатия изображений / В.Г
Прохоров / Прикладне програмне забезпечення,
№2. - 2009. – С. 7.
4. Умняшкин, С.В. Математические методы и алгоритмы цифровой компрессии изображений с использованием ортогональных преобразований / С.В. Умняшкин / Автореферат диссертации. – 2001.
5.
Hassaballah, M. A fast fractal image compression
method based / M. Hassaballah, M.M. Makky and Youssef B. Mahdy / Electronic Letters on Computer Vision and Image
Analysis 5(1). –