Методы многокритериальной оптимизации фрактального сжатия изображений

• Автор: Окунев, Вадим Вячеславович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Санкт-Петербург
• Количество страниц: 127 с.

Оглавление
Введение

Глава 1. Обзор методов сжатия цифровых изображений

1.1. Введение

1.2. Обзор современных форматов цифровых изображений

1.2.1. Компрессия без потерь

1.2.1.1. Формат GIF

1.2.1.2. Формат PNG

1.2.2. Компрессия с потерями

1.2.2.1. Формат JPEG

1.2.2.2. Метод фрактального сжатия

1.3. Классический алгоритм фрактального сжатия изображений
1.3.1. Описание классического алгоритма
1.3.2. Модификации алгоритма для разных типов графической информации
1.4. Анализ подходов к оптимизации алгоритмов фрактального сжатия
1.4.1. Выделение основных подходов
1.4.2. Оптимизация на основе параллельных вычислений
1.4.3. Оптимизация с помощью генетических алгоритмов
1.4.4. Оптимизация с помощью предметно-зависимых эвристик
1.5. Использование особенностей изображений при оптимизации алгоритмов фрактального сжатия
1.5.1. Оптимизация разбиения изображения на ранговые блоки
1.5.2. Оптимизация поиска соответствия ранговых и доменных блоков
Выводы по первой главе
Глава 2. Многокритериальный анализ эффективности методов оптимизации фрактального сжатия
2.1. Введение
2.2. Оптимизация числа операций в алгоритмах фрактального сжатия
2.2.1. Оценка числа операций в классическом фрактальном алгоритме
2.2.2. Оптимизация процедуры сравнения блоков
2.2.3. Оптимизация процедуры поиска соответствий блоков
2.2.4. Оценка допустимого числа вариантов разбиения изображения на ранговые блоки
2.3. Оценка объёма сжатого изображения
2.4. Оценка качества восстановленного изображения
2.4.1. Классические критерии качества
2.4.2. Принцип минимальной длины описания в оценке качества сжатия изображений
2.5. Выбор оптимального разбиения на ранговые блоки
2.5.1. Выбор размера рангового блока
2.5.2. Оптимизация разбиения «жадным» алгоритмом
Выводы по второй главе
Глава 3. Разработка субоптимальных методов фрактального сжатия с ограниченной ресурсоёмкостыо
3.1. Введение
3.2. Построение и описание доменных и ранговых блоков
3.2.1. Разбиение изображения на ранговые блоки
3.2.2. Покрытие изображения доменными блоками
3.2.3. Преимущества выбранных способов
3.2.4. Расширенное множество доменов
3.2.5. Индексация блоков
3.2.5.1. Основы ДКП-подхода
3.2.5.2. Алгоритм вычисления индекса блока
3.2.5.3. Упрощённое вычисление индексов «дополнительных» доменов
3.2.5.3. Общая концепция использования индексов
3.2.6. Применение дескрипторов для описания блоков
3.3. Поиск оптимальных доменных блоков
3.3.1. Иерархический поиск по индексам
3.3.2. Поиск оптимальных доменов
3.3.3. Оценка МДО сжатого изображения
3.3.4. Оценка нижней границы допустимого размера рангового блока
3.4. Выбор оптимального разбиения на ранговые блоки
3.4.1. Выбор оптимального размера ранговых блоков
3.4.2. Реализация метода квадродерева
3.5. Формат сжатого файла
3.5.1. Общая структура сжатого файла
3.5.2. Заголовок сжатого файла
3.5.3. Поле данных сжатого файла
Выводы по третьей главе
Глава 4. Экспериментальная проверка разработанных методов оптимизации фрактального сжатия
4.1. Введение
4.2. Эмпирические характеристики классического алгоритма
4.3. Тестирование метода оптимизированного поиска доменных блоков..
4.4. Связь среднего пространственного периода изображения
с параметрами фрактального сжатия
4.5. Повышение качества сжатия при оптимизации разбиения
с помощью квадродерева
4.6. Методика сравнения алгоритмов сжатия с потерями
Выводы по четвёртой главе
Заключение
Литература

зависимости от средних значений четырёх подблоков равных размеров, каждая из высокочастотных — к одному из 12 классов в зависимости от степеней определённых членов их вейвлет-разложения. Таким образом, всё множество блоков может быть разбито на 3x12x12 = 432 класса.
В статьях [77, 78] предложена классификация блоков с использованием статистических моментов — среднего значения и дисперсии. В частности, авторы работы [77] предлагают разделять блоки на классы в соответствии с их средним значением. Помимо этого, классификация каждого рангового блока производится по разности его дисперсии и дисперсии соответствующих доменов. Количество необходимых преобразований симметрии доменного блока вычисляется исходя из принадлежности к классам, которые определяются с помощью средних значений четырёх подблоков равных размеров.
В статье [79] предлагается оптимизировать поиск доменных блоков на основе гистограмм. Размер доменного блока принят в 2 раза больше размера рангового блока. Исходя из этого, для поиска доменов рассматривается исходное изображение, уменьшенное в 2 раза. Уменьшенное изображение делится на подблоки методом квадродерева, и для каждого подблока вычисляется гистограмма. Если гистограмма какого-либо рангового блока содержится в гистограмме рассматриваемого подблока, то данный подблок содержит домен, наилучшим образом соответствующий данному ранговому блоку. Затем осуществляется дальнейшее разбиение по квадродереву, пока алгоритм не придёт к подблоку, соответствующему по размеру ранговому блоку — это и будет искомый домен. Доменные блоки в данном случае являются неперекрывающимися, однако, авторы заявляют о необязательности этого условия.
В работе [80] сделано предположение о том, что коэффициент контрастности, используемый для приведения блоков к максимальному соответствию, может выходить за пределы промежутка [0; 1), при этом сохранится сходимость алгоритма, а также может быть достигнуто лучшее