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

Фрактальное сжатие
Треугольник Серпинского — изображение, задаваемое тремя аффинными преобразованиями

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

Содержание

Суть фрактального сжатия

Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций (IFS) к проблеме сжатия изображения была исследована Майклом Барнсли (Michael Barnsley[1]) и Аланом Слоуном (Alan Sloan). Они запатентовали свою идею в 1990 и 1991 гг (U.S. Patent 5,065,447 (англ.)). Джеквин (Jacquin) представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков изображения (domain and range subimage blocks), блоков квадратной формы, покрывающих все изображение. Этот подход стал основой для большинства методов фрактального кодирования, применяемых сегодня. Он был усовершенствован Ювалом Фишером (Yuval Fisher) и рядом других исследователей.

В соответствии с данным методом изображение разбивается на множество неперекрывающихся ранговых подизображений (range subimages) и определяется множество перекрывающихся доменных подизображений (domain subimages). Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований.

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

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

Вкратце метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), то есть определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).

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

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

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

Основная сложность метода

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

На данный момент известно достаточно большое количество алгоритмов оптимизации перебора, возникающего при фрактальном сжатии, поскольку большинство статей, исследовавших алгоритм были посвящены этой проблеме, и во время активных исследований (1992—1996 года) выходило до 300 статей в год. Наиболее эффективными оказались два направления исследований: метод выделения особенностей (feature extraction) и метод классификации доменов (classification of domains).

Патенты

Майклом Барнсли и другими было получено несколько патентов на фрактальное сжатие в США и других. Например, U.S. Patent 4,941,193 (англ.), 5,065,447 (англ.), 5,384,867 (англ.), 5,416,856 (англ.) и 5,430,812 (англ.). Эти патенты покрывают широкий спектр возможных изменений фрактального сжатия и серьёзно сдерживают его развитие.

Данные патенты не ограничивают исследований в этой области, то есть можно придумывать свои алгоритмы на основе запатентованных и публиковать их. Также можно продавать алгоритмы в страны, на которые не распространяются полученные патенты. Кроме того срок действия большинства патентов — 17 лет с момента принятия и он истекает для большинства патентов в ближайшее время, соотвественно использование методов, покрывавшихся этими патентами станет гарантированно свободным.

Примечания

См. также

  • Фрактал — базовое исходное понятие
  • Кривая Коха — пример кривой, задаваемой IFS. Для изображений аналогичное пребразование происходит в двумерном пространстве.
  • Треугольник Серпинского — простой пример изображения, которое легко задать IFS
  • JPEG 2000 — основной «конкурент» фрактального сжатия по степени сжатия
  • en:List of fractals by Hausdorff dimension

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "Фрактальное сжатие" в других словарях:

  • фрактальное сжатие — Технология, применяемая для сжатия изображений. Использует сложный алгоритм для хранения изображений в виде фракталов. Позволяет достигать высокой степени сжатия до 200:1 с применением фрактальных алгоритмов для представления изображения.… …   Справочник технического переводчика

  • Сжатие видео — (англ. Video compression)  уменьшение количества данных, используемых для представления видеопотока. Сжатие видео позволяет эффективно уменьшать поток, необходимый для передачи видео по каналам радиовещания, уменьшать пространство,… …   Википедия

  • Сжатие данных с потерями — У этого термина существуют и другие значения, см. Сжатие. Сжатие данных с потерями  метод сжатия (компрессии) данных, при использовании которого распакованные данные отличаются от исходных, но степень отличия не является существенной с точки …   Википедия

  • Алгоритм фрактального сжатия — Треугольник Серпинского  изображение, задаваемое тремя аффинными преобразованиями Фрактальное сжатие изображений  алгоритм сжатия изображений c …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • фрактал — В прошлом математики концентрировали внимание на множествах и функциях, для которых могут быть применены методы классических вычислений. Функции, которые не являются достаточно гладкими или регулярными, часто игнорировались как… …   Справочник технического переводчика

  • Фрактал — Множество Мандельброта  классический образец фрактала …   Википедия

  • Фрактальная графика — Множество Мандельброта классический образец фрактала Фрактал (лат. fractus дробленый) термин, означающий геометрическую фигуру, обладающую свойством самоподобия, то есть составленную из нескольких частей, каждая из которых подобна всей фигуре… …   Википедия

  • Фракталы — Множество Мандельброта классический образец фрактала Фрактал (лат. fractus дробленый) термин, означающий геометрическую фигуру, обладающую свойством самоподобия, то есть составленную из нескольких частей, каждая из которых подобна всей фигуре… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»