Фрактальное сжатие.

Введение Изображения и иллюстрации используются повсеместно. Проблема, связанная с большим объемом для их обработки и хранения, появилась при работе и на рабочих станциях, и на персональных компьютерах. Разработано большое количество различных алгоритмов архивации графики.

История создания Выход книги Мандельброта «фрактальная геометрия природы» 1977 г. Джон Хатчинсон опубликовал статью «Фракталы и самоподобие» IFS (Iterated Function System( система итерируемых функций)) 1981 г. Майкл Брасли «Фракталы повсюду» Collage Theorem ( основа математического обоснования идеи фрактальной компрессии) 1988 г. Арнауд Джеквин опубликовал практический алгоритм 1992 г.

Идея Фрактальная архивация основана на: 1. Представление в более компактной форме коэффициентов системы итерируемых функций изображения. IFS - это набор трехмерных аффинных преобразований, переводящих одно изображение в другое.

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

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

Оценка потерь и способы их регулирования Механизмы: Фиксированная величина степени сжатия приводит к ограничению количества преобразований. Дробление фрагмента при достижение порогового значения между исходным изображением и его лучшим приближением. Установка минимального размера, дробления фрагмента.

Возможности масштабирования Масштабирование - уникальная особенность, присущая фрактальной компрессии. Восстанавливаемое изображение может иметь любое разрешение. Распознавание изображения.

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

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

Кодирование цветных изображений. HSB (тон, насыщенность, яркость). YUV (Y - компонента яркости; U и V хранят характеристики цвета). YUV 411.

JPEG Краткий обзор. Преобразование цветов RGB в цвета YUV – подвыборка. Метод сжатия JPEG: Изменение частоты. Усреднение. Сжатие методом Хаффмана.

Сравнение с JPEG Сходства: Оба алгоритма оперируют 8-битными (в градациях серого) и 24-битными полноцветными изображениями. Оба являются алгоритмами сжатия с потерями и обеспечивают близкие коэффициенты архивации. У фрактального алгоритма, и у JPEG существует возможность увеличить степень сжатия за счет увеличения потерь. Кроме того, оба алгоритма очень хорошо распараллеливаются.

Сравнение с JPEG Различия Время сжатия у фрактального в сотни раз дольше, зато декомпрессия происходит в 5-10 раз быстрее. JPEG использует разложение изображения по косинусоидальным функциям.

Итерация восстановления изображения Итерация - от латинского iteratio – повторение. Вычисление по одной формуле, когда полученного значения на предыдущем шаге применяется в последующем шаге.

Сжатие цветных изображений. Сжатие 6.5:1 Сжатие 3:1. оригинал

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