Сжатие изображений с помощью фракталов и всплесков

• Автор: Малыгин, Ярослав Владимирович
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Екатеринбург
• Количество страниц: 73 с. : ил.

1 Введение
2 Фракталы
2.1 Основные понятия и определения
2.2 Аппроксимация множеств
2.3 Фрактальное представление монохромных изображений
2.4 Численный алгоритм фрактального сжатия монохромного изображения
3 Методы повышения быстродействия
фрактального сжатия
3.1 Предварительная классификация фрагментов изображения
3.2 Использование преобразования Мерсенна
3.3 Использование многопроцессорной
вычислительной техники
4 Применение всплесков в задаче
фрактального сжатия
4.1 Кратномасштабный анализ
4.2 Всплеск-фрактальное преобразование
4.3 Модифицированный метод всплескфрактального сжатия
5 Поиск параметров IFS для бинарных изображений
6 Заключение
Список литературы

1 Введение
Актуальность темы
Современные информационные технологии предполагают передачу и хранение больших объемов данных. Значительную часть передаваемых данных составляют графические изображения и видеоинформация. В связи с этим важную роль играют методы сжатия (т.е. компактного описания) графических изображений. Под монохромным графическим изображением будем понимать матрицу целых чисел X = {яу}"7=от_1» хп ~ 0, 2Ь — 1. Каждый элемент матрицы X определяет интенсивность свечения графического элемента (пиксела). Нулевое значение элемента соответствует чёрному цвету, а значение (2& — 1) — белому. Параметр 6 называется глубиной цвета и определяет количество информации, необходимое для хранения значения одного элемента. Таким образом, для хранения всего изображения X необходимо т-тг-Ь бит памяти.
Если 6 = 1, такое изображение называется бинарным, т.е. в нём могут быть графические элементы только чёрного и белого цвета. Бинарное изображение также можно представить как характеристическую функцию компактного множества из Е2.
В цветном (многоканальном) изображении каждый графический элемент представляется в виде трех- или четырехмерного вектора. В этом случае каждая цветовая составляющая эквивалентна отдельному монохромному изображению и обрабатывается независимо.
Коэффициентом сжатия называется отношение количества информации, необходимой для хранения исходного (несжатого) изображения к количеству информации, требуемого для представления того же изображения в компактной форме. Различают два вида сжатия: сжатие без потерь и сжатие с потерями.
Сжатие без потерь также называется архивированием или упаковкой и используется не только при хранении изображений (форматы СШ, РСХ), но и вообще произвольных данных (например текста или программных кодов). Восстановленная информация абсолютно идентична сжимаемой. Коэффициент такого сжатия обычно не превышает 2.5 - 3.
Как видно из названия, сжатие с потерями предполагает потерю части информации при сжатии и последующем восстановлении. Использование методов сжатия с потерями ограничивается объекта/-
ми, где такие потери допустимы (обработка графической, звуковой информации и т.д.). Для оценки качества восстановления используют величину PSNR (peak signal-to-noise ratio, предельное отношение сигнал-шум), измеряемую в дБ:
п—1,ш
ё (хч ~ Vij)2 KPSNR{X,Y) = [дБ], (1.1)
где X и Y - соответственно исходное и восстановленное изображения. Качество восстановления, как правило, находится в обратной зависимости от коэффициента сжатия. Т.е. коэффициент сжатия ограничен требуемым качеством восстановления, и его значение может достигать сотни и более. В данной работе рассматриваются лишь методы сжатия с потерями.
В настоящее время для сжатия численной информации используют методы аппроксимации функций полиномами [37], рациональными дробями [5], экспонентами [32], сплайнами [26], всплесками. Одним из самых распространенных алгоритмов сжатия с потерями фотогорафических изображений является JPEG (Joint Photographie Expert Group - объединенная группа экспертов по фотографии). Этот алгоритм [31] основан на разбиении исходного изображения на фрагменты размером 8x8 пикселов. Для каждого фрагмента выполняется двумерное дискретное косинус-преобразование (ДКП) [1]. Далее происходит квантование по уровню спектра ДКП, что и определяет потери при сжатии. Коэффициенты квантования определяют, какое количество данных теряется и, следовательно, коэффициент сжатия и качество восстановленного изображения. Для получения окончательного результата выходные данные квантования без потерь упаковываются с использованием какого-либо статистического метода кодирования. Таким методом может быть арифметическое кодирования, либо кодирования по методу Хаффмана [8], [20].
Фрактальные методы сжатия изображений позволяют не только компактно хранить данные, но и воспроизводить данное изображение практически при любом увеличении. Возможность фрактального увеличения обеспечивается тем, что в таких алгоритмах запоминаются не отдельные элементы изображения, а соотношения между различными фрагментами.
Рис. 3.5. "Развертывание" графа с рис. 3.4 в дерево
о результате поиска дальше по дереву.
Например, узел номер 2 будет передавать данные узлам 4 и 8. Информация о результате поиска включает в себя номер текущего наилучшего домена I*, соответствующие коэффициенты яркости и контрастности вр и о;*, а также величину ошибки еы-•
Таким образом, информация о наилучшем по всей ветке домене накапливается в каждом из оконечных узлов ("листьях"). Эту информацию оконечные узлы передают ведущему, который и осуществляет окончательный выбор наилучшего домена для данного региона. Передача этой (и только этой) информации будет происходить неоптимальным образом (т.е. между узлами, не являющимися непосредственными соседями).
Как только узел заканчивает процедуру поиска для одного региона, он обращается к вышестоящему узлу за новой порцией данных (по следующему региону). Таким образом, основной поток данных последовательно распространяется от ведущего узла к оконечным, и в обмене информацией при этом участвуют лишь непосредственные соседи.
Теперь рассмотрим задачу разбиения прямоугольника размером 5а х 5ь на N равновеликих прямоугольных фрагментов, размерами о; х Ь;,г = О, Л'" — 1. Так как 5а,5'е,,.ЛГ, {а»}^1»^*}^1 на'