Автореферат ^*

выпускной работы магистра на тему

"Алгоритмы фрактального сжатия изображений: сравнительный анализ, модификация"

Автор: студент гр. КЭМ-07М Бубличенко Александр Владимирович

Научный руководитель: к.т.н., доцент кафедры КСМ Беловодский Валерий Николаевич

---

Содержание

• Введение
• Актуальность
• Степень научной разработанности и нерешенные проблемы
• Цели и задачи
• Предполагаемая научная новизна
• Описание результатов работы
• Описание исследований
• Описание разработанного ПО
• Эксперименты, результаты и выводы
• Заключение
• Литература

---

Введение

Актуальность работы

Задача эффективного сжатия данных всегда была одной из самых актуальных в информатике, а с развитием компьютерной, цифровой техники и Интернет она приобрела еще большее значение. Так, с начала 1980-х гг. было разработано множество алгоритмов, направленных на эффективное сжатие цифровых изображений для их передачи и хранения [1]. Развитие теории фракталов и соответствующего математического аппарата в конце XX в. повлекло разработку принципиально нового алгоритма сжатия изображений — фрактального. Идея фрактального метода сжатия изображений была сформулирована Майклом Барнсли в 1990 году [11] и концептуально заключается в следующем. Для заданного изображения по специальным правилам строится система сжимающих отображений, для которых оно является аттрактором. Тогда, в силу теоремы о неподвижной точке [10], итерационный процесс, сформированный на базе этих отображений, сходится к своему аттрактору при любом выборе начального изображения. Эффект сжатия достигается за счет того, что вместо исходного изображения для его восстановления необходимо хранить лишь коэффициенты преобразования.

К числу отличительных можно отнести ряд особенностей, обуславливающих интерес к данному методу сжатия на протяжении более двух десятилетий, а именно:

• высокий коэффициент сжатия (т.е. отношение объема исходной информации к объему кода). Так, для изображений, обладающих самоподобием, он достигает 2000;
• независимость качества декодированного изображения от масштаба его просмотра;
• существенная асимметричность, т.е. время кодирования заметно больше времени декодирования.

Основным недостатком данного метода остается сравнительно большое время кодирования, обусловленное значительным числом перебираемых вариантов. Поэтому разработка модификаций этого алгоритма, направленных на уменьшение времени кодирования, является актуальной.

Степень научной разработанности и нерешенные проблемы

Привлекательность самой идеи фрактального метода сжатия и его достоинства притягивает исследователей к развитию и совершенствованию алгоритмов его реализующих. Предлагаемые модификации касаются практически всех его сторон. В большинстве опубликованных работ по данной теме предлагаются различные методы, направленные на снижение объема перебора доменных блоков и, как следствие, — сокращение времени кодирования. Так, в работе [3] затрагивается способ разбиения доменов и предлагается ограничиться теми, которые окаймляют ранги. В работе [4] используется дискретное косинусоидальное преобразование для классификации всех доменных блоков на некоторое количество классов, в работе [5] для этого применяются R-деревья, а в работе [6] — самоорганизующаяся нейронная сеть. В работах [7] и [8] авторы используют генетический алгоритм для поиска оптимальных доменов. В работе [9] поиск ограничивается посредством меры информационной энтропии доменов. Другой, менее разработанной областью исследований, является применение нелинейных сжимающих отображений (способов аппроксимации ранговых блоков доменными блоками) [3].

Однако, возможно в силу коммерческой составляющей работ данного направления и, как следствие, отсутствия удовлетворительных описаний рассматриваемых алгоритмов, предлагаемые модификации воспринимаются, скорее, как результат интуитивных и спонтанных импровизаций, нежели обоснованный итог некоторой серии вычислительных экспериментов. Вместе с тем, каждый исследователь, начинающий путь в этой области, нуждается в наличии тщательного сопоставительного анализа основных алгоритмов.

Цели и задачи

Цель работы состоит в проведении сравнительного анализа базовых алгоритмов, установлении особенностей отбора доменных блоков, апробации методов их аппроксимации для повышения эффективности сжатия. Данная цель достигается за счет изменений в методах отбора доменных блоков и способах аппроксимации.

Идея работы — разработка новых модификаций методов отбора доменных блоков и способов их аппроксимации в ранговые блоки для повышения эффективности кодирования.

Для достижения указанной цели в магистерской работе поставлены и решены следующие задачи:

1. Изучение литературных источников и проведение теоретического анализа алгоритмов сжатия изображений с потерями.
2. Установление особенностей функционирования алгоритмов фрактального сжатия изображений, разработка реализующего их программного обеспечения.
3. Формирование набора изображений, проведение вычислительных экспериментов по установлению особенностей отбора доменных блоков и их аппроксимации, сравнительный анализ результатов, формулирование выводов.
4. Модификация отдельных этапов алгоритма, формирование его новой версии.
5. Разработка соответствующих программных компонент, проведение экспериментов, сравнительные результаты работы.

Предмет исследования — алгоритмы сжатия изображений с потерями.

Объект исследования — фрактальные алгоритмы сжатия изображений.

Методы исследования включают проведение вычислительных экспериментов, сравнительный анализ результатов, численные методы, математические методы аппроксимации, объектно-ориентированное программирование.

Предполагаемая научная новизна

Научная новизна уже проведенных и планируемых в работе исследований предполагается в следующем:

1. Разработано программное обеспечение, реализующее базовые алгоритмы фрактального сжатия и позволяющее проводить сопоставительный анализ.
2. Проведены вычислительные эксперименты, сделан сравнительный анализ и выявлены особенности отбора доменных блоков в базовых алгоритмах.
3. Анализ применимости нелинейных моделей отображений блоков изображений.
4. Предложены новые модификации алгоритма, направленные на повышение эффективности сжатия.

Описание результатов работы

Описание исследований

На текущем этапе проведены исследования двух алгоритмов фрактального сажатия изображений — базового и FE-алгоритма, которые хорошо описаны в литературе [2]. Их можно отнести к числу основных.

Базовый алгоритм условно включает следующие этапы.

Шаг 1. В изображении f выделяют множество доменных блоков. Они могут перекрываться, а величина перекрытия определяется специально предусмотренным параметром.

Шаг 2. Изображение разбивают на не перекрывающиеся ранговые блоки {R_k}. Они могут не быть одинакового размера, т.к. используется адап¬тивное разбиение методом квадро-дерева с переменным размером блоков. Это позволяет плотно заполнить ранговыми блоками маленького размера части изображения, содержащие мелкие детали.

Шаг 3. Для каждого рангового блока перебирают доменные блоки. При этом предусматривают изменение ориентации доменов (3 варианта вращения, 2 ва¬рианта вращения с отражением, 2 варианта отражения и 8-ой вариант — исходная ориентация без изменений). При каждом из вариантов ориентации домен сжимают до размеров рангового блока и вычисляют оптимальные значения коэффициентов a_ij и b_ij преобразования

методом наименьших квадратов и по формуле

вычисляют нормированное значение параметра L(R_k , D'_ij), который характеризует соответствие преобразованного сжатого i-го доменного блока w_ij(D'_ij) в его j-ой ориентации ранговому блоку R_k. Здесь r_xy ∈ R_k, d_xy ∈ D'_ij, D'_ij — i-ый доменный блок в j-ой ориентации, сжатый до размеров рангового блока, N_Rk — количество пикселей в ранговом блоке. На этом шаге алгоритм работает в одном из двух режимах, выбираемом пользователем, — с поиском и без поиска наилучшего домена. В режиме поиска наилучшего домена для каждого ранга перебираются все домены, и выбирается тот i-ый домен и его j-ая ориентация, значение L_kij которого является минимальным среди всех остальных. В режиме без поиска наилучшего домена полный перебор доменов останавливают, как только обнаруживается такой i-ый домен и его j-ая ориентация, что его значение L_kij не превышает заданной допустимой погрешности (например, L_kij ≤ 0.05). В обоих режимах, если после перебора всех доменных блоков не нашлось таких, значения L_kij которых не превышают значение заданной допустимой погрешности, то делается проверка — находится ли рассматриваемый ранговый блок на максимально допустимом уровне разбиения рангов. Если нет, то этот ранговый блок разбивают на меньшие блоки и проводят данный шаг алгоритма для них. Если да, то из всех доменов выбирают тот домен и его вариант ориентации D_ij, для которого значение L_kij является минимальным среди всех остальных, и считают рассматриваемый ранговый блок покрытым этим доменом.

Шаг 3 требует наибольших вычислений, т.к. для каждого рангового блока R_k алгоритм перебирает все (или многие, в зависимости от режима работы) доменные блоки и их варианты ориентации, проводя над каждым занимающие много машинного времени попиксельные операции изменения ориентации и нахождения коэффициентов преобразования. Хорошее сжатие зависит от возможности найти хорошее соответствие между доменными и ранговыми блоками без необходимости глубокого разбиения ранговых блоков. Чрезмерно глубокое разбиение рангов приводит к слишком большому их количеству, что ухудшает коэффициент сжатия, а недостаточно глубокое — к плохому качеству закодированного изображения.

FE-алгоритм. Сравнение рангов с доменами в базовом алгоритме требует значительных вычислительных ресурсов. С целью их снижения в FE-алгоритме (от англ. Feature Extraction — выделение особенностей) выделяется пять характеристик, описывающих доменные и ранговые блоки. И первоначально, проводится именно их сравнение, что значительно сокращает объем вычислений. Эти характеристики следующие:

• стандартное отклонение;
• асимметрия;
• межпиксельная контрастность;
• коэффициент бета, характеризующий отличие значений пикселей от значения центрального пикселя;
• максимальный градиент — максимум из горизонтального и вертикального градиентов.

Сам алгоритм включает следую¬щие этапы.

Шаг 1. Аналогично шагу 1 базового алгоритма.

Шаг 2. Дополняя шаг 2 базового алгоритма, производится вычисление и хранение значений вектора характеристик для каждого доменного блока.

Шаг 3. При обработке рангового блока сначала вычисляют его вектор характеристик, затем вычисляют расстояния между вектором характеристик данного ранга и вектором характеристик каждого домена по формуле

где f_j^R и f_j^D — это j-ые характеристики рангового и доменного блоков соответственно. Для последующего полного сравнения отбирается только заданный q процент доменов (напри¬мер, q = 2%) с минимальными значениями расстояний между векторами характеристик. Последующие действия аналогичны тем, которые выполняются в шаге 3 базового алгоритма, но с той разницей, что при переборе доменов рассматриваются только выбранные q % и наилучший выбирается из них.

Отметим, что такая процедура отбора доменов является своеобразным фильтром, который существенно ограничивает их перебираемое количество.

Описание разработанного ПО

Для проведения исследований было разработано специальное программное обеспечение на языке C# с использованием технологии Microsoft .NET Framework 2.0 и инструментальной оболочки Visual Studio 2005/2008. Оно позволяет кодировать растровые изображения в фрактальные и декодировать их рассмотренными выше алгоритмами. Пользователь может задавать настройки кодирования, регулирующие качество кодируемых изображений. Кроме того, программное обеспечение включает следующие средства анализа:

• отображение структуры доменов и рангов, как в виде таблицы со значениями их свойств, так и визуально на изображении;
• вычисление средней пиксельной ошибки между исходным и закодированным изображением;
• подсчет количества обработанных и использованных при кодировании рангов и доменов;
• определение времени кодирования и декодирования;
• отображение на закодированном изображении сетки ранговых блоков;
• автоматизированный анализ результатов кодирования изображений разными алгоритмами фрактального сжатия.

UML-диаграмма разработанного программного обеспечения представлена ниже (рисунок 1):

Рисунок 1 — UML-диаграмма разработанного программного обеспечения

 

Рисунок 2 — Экранные формы разработанного программного обеспечения

Эксперименты, результаты и выводы

С использованием разработанного программного обеспечения была проведена серия экспериментов, в которых использовалось произвольно выбранное изображение размером 256×256 пикселей, представленное на рисунке 3. Исходные данные, параметры настроек и результаты экспериментов приведены в таблице 1. На рисунке 4 представлено декодированное изображение, предварительно закодированное рассматриваемыми алгоритмами.

Рисунок 3 — Исходное изображение

В экспериментах время кодирования в обоих алгоритмах не ограничивалось. Каждый последующий эксперимент отличается от предыдущего более высокими значениями параметров, задающими качество кодируемого изображения. Опишем некоторые эти параметры, предназначение которых не было раскрыто подробно в описании алгоритмов. Начальный, максимальный уровни разбиения доменов, а также коэффициент скольжения доменов регулируют их количество, размеры и расположение. Коэффициент скольжения определяет, насколько плотно соседние домены перекрываются (так, при минимальном значении 0 — они не перекрываются вообще, а при максимальном значении 1 — перекрываются так, что остается не перекрытой область шириной ровно в один пиксель). Количество доменов зависит исключительно от этих параметров. Начальный уровень разбиения рангов задает начальное минимальное их количество и максимально возможный их размер, а максимальный уровень разбиения — их максимально допустимое количество и минимально возможный размер. Эти уровни, по сути, являются уровнями разбиения рангов методом квадро-дерева. Количество рангов по окончании кодирования зависит не только от этих параметров, но и от допустимой погрешности (см. описание алгоритмов). Средняя пиксельная ошибка показывает, насколько декодированное изображение отличается от исходного, и определяется по формуле

где p_x,y , p'_x,y — значение пикселя в точке (x, y) исходного и декодированного изображений соответственно, I_W, I_H — соответственно ширина и высота (в пикселях) изображения, N_I — количество пикселей в изображении.

Отметим, что параметры, определяющие количество доменов, непосредственно влияют на время кодирования и качество декодированного изображения, и не отражаются на коэффициенте сжатия. Параметры же, регулирующие количество и размер рангов, влияют как на время кодирования и декодирования, так и на качество декодированного изображения. А число рангов однозначно определяет коэффициент сжатия.

Таблица 1 — Результаты экспериментов

Полученные результаты позволяют сделать следующие выводы:

1. FE-алгоритм, по сравнению с базовым, позволяет сжимать изображения в десятки раз меньшее время при одинаковых параметрах настроек алгоритмов.
2. Различаются средние пиксельные ошибки алгоритмов. В зависимости от настроек, различие находится в пределах 5-16%.
3. В результате кодирования базовым алгоритмом во всех случаях достигается в среднем на 30-40% более высокий коэффициент сжатия.
4. Визуальное качество декодированного изображения заметно лучше при использовании FE-алгоритма.
5. Время декодирования закодированного изображения при различных настройках кодирования меньше при использовании базового алгоритма во всех экспериментах.

Некоторые из них вполне очевидны. Действительно, в FE-алгоритме, вместо сравнения блоков изображения происходит сравнение их векторов характеристик, что естественно отражается на быстродействии. Различие пиксельных ошибок и коэффициентов сжатия скорее всего объясняется тем, что при использовании FE-алгоритма в результате кодирования получается бoльшее количество рангов малого размера, что к тому же обеспечивает более высокую детализацию изображения, то есть — лучшее визуальное качество. Эти заключения подтверждает и рисунок 6, на котором представлено закодированное обоими алгоритмами изображение с сеткой рангов. Следует обратить внимание на то, что хотя при базовом алгоритме и получается на 5-16% худшее качество изображения, но при этом, достигается на 30-40% более высокий коэффициент сжатия.

Можно предположить, что причина выявленных различий заключается в том, что в FE-алгоритме при переборе доменов, отобранных по значениям их характеристик, не находится такой, который обеспечивал бы принятую допустимую погрешность соответствия ранговому блоку, в результате чего ранговый блок разбивается на более малые по размеру блоки. В то же время при кодировании базовым алгоритмом для тех же рангов, вполне возможно, такие домены находятся.

Для проверки этой гипотезы был разработан дополнительный программный модуль, позволяющий подсчитывать число совпадений в обоих алгоритмах при выборе домена, т.е. когда для одного ранга в обоих алгоритмах выбирается тот же домен. Изображение оставалось тем же. Настройки кодирования соответствуют тем, которые использовались в четвертом эксперименте таблицы 1, с той лишь разницей, что базовый алгоритм работает в режиме поиска наилучшего домена. Это означает, что при обработке каждого рангового блока осуществляется перебор всех доменных блоков, без остановки при достижении допустимой погрешности, и выбирается действительно наилучший. Это, на наш взгляд, позволяет проводить корректное сравнение.

В результате проведения экспериментов было установлено, что для 99.73 % ранговых блоков FE-алгоритм выбрал другие домены, т.е. — не наилучшие. Таким образом, по крайней мере, для данного изображения можно утверждать, что процедура отбора доменов, принятая в FE-алгоритме, не вполне отражает близость сравниваемых блоков.

Заключение

В результате проведенных исследований и экспериментов вытекают следующие соображения.

1. Представляется обоснованным, что эффективность сжатия в немалой степени зависит от начального разбиения исходного изображения. Действительно, невключение удачного домена или его ошибочное отбрасывание сказывается как на степени сжатия, так и на качестве декодирования. Априори представляется правдоподобным, что различие соседних близких пикселей, в целом, менее разительно, чем в областях, выбираемых случайным образом. По этой причине, включение окаймляющих доменов в первоначально формируемое их множество представляется перспективным.

2. Идея введения упрощенного набора критериев с целью существенного снижения объема вычислений является привлекательной, но в большинстве случаев сравнения доменов с рангами этот набор не позволяет выявить оптимальный домен. То есть данный набор является не вполне адекватным основному критерию. Поэтому представляется целесообразным вместо этого набора использовать основной критерий, но применять его к уменьшенным копиям рассматриваемых пар домен-ранг.

3. Напрашивается также соображение, непосредственно вытекающее из теоретических основ фрактальных методов сжатия. Так, из теоремы коллажа [10] следует, что степень отличия аттрактора системы сжимающих отображений от исходного изображения не в последнюю очередь определяется качественными характеристиками формируемых отображений. Их повышения естественно ожидать при переходе от простейших, грубых, линейных моделей, используемых в базовых алгоритмах, к более сложным — нелинейным. В этой связи попытка использования таких моделей представляется актуальным.

Практическое значение работы и личный вклад автора заключаются в разработанном программном обеспечении, реализующего два базовых алгоритма и позволяющего проводить автоматизированный сопоставительный анализ работы реализованных алгоритмов на любых изображениях. На стадии разработки находится программная реализация новых модификаций алгоритма на основе полученных выводов и выдвинутых предложений.

Основные положения отдельных этапов работы были доложены на III-й международной научно-технической конференции молодых учёных и студентов «Информатика и компьютерные технологии» (Донецк, ДонНТУ, 2007), IV-й международной научной конференции студентов, аспирантов и молодых ученых «Компьютерный мониторинг и информационные технологии» (Донецк, ДонНТУ, 2008).

По теме магистерской диссертации опубликованы три работы в сборниках тезисов докладов научных конференций.

Литература

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов. Сжатие изображений и видео. — М.: ДИАЛОГ-МИФИ, 2003
2. С. Уэлстид. Фракталы и вейвлеты для сжатия изображений в действии. Учеб¬ное пособ. — М.: Издательство «Триумф», 2003, с. 77-119
3. А.Н. Авлеева. Фрактальное сжатие изображений. Решение задач сжатия изображений с использованием систем итерированных функций. Магистерская диссертация, ДонНТУ, 2006
4. Д.С. Ватолин. Использование ДКП для ускорения фрактального сжатия изображений. Журнал «Программирование» №3 1999, с. 51-57
5. John Kominek. Algorithm for Fast Fractal Image Compression. Department of Computer Science, University of Waterloo, Canada, 1995
6. Stephen Welstead. Self-Organizing Neural Network Domain Classification for Fractal Image Coding. Proc. of the IASTED International Conference “Artificial Intelligence and Soft Computing”. Banff, Canada, 1997, pp. 248-251
7. Lucia Vences, Isaac Rudomin. Genetic Algorithms for Fractal Image and Image Sequence Compression. Manuscript. Institute of Technology, University of Monterrey, 1997
8. Lifeng Xi,Liangbin Zhang. A Study of Fractal Image Compression Based on an Improved Genetic Algorithm. International Journal of Nonlinear Science. Vol.3, No. 2, 2007, pp. 116-124
9. M. Hassaballah, M.M. Makky, Youssef B. Mahdy. A Fast Fractal Image Compression Method Based Entropy. Electronic Letters on Computer Vision and Image Analysis 5(1), 2005, pp. 30-40
10. P. M. Кроновер. Фракталы и хаос в динамических системах. Основы теории. — М.: Постмаркет, 2000
11. Barnsley, Michael F., Sloan, Alan D., Iterated Systems, Inc. Methods and apparatus for image compression by iterated function system. United States Patent 4941193, July 10, 1990

---

* — При написании данного автореферата магистерская диссертация еще не завершена. Окончательное ее завершение состоится 1 декабря 2008 г. Текст и материалы диссертации могут быть получены у автора или его руководителя после этой даты.