Алгоритм фрактального сжатия

Материал из Википедии — свободной энциклопедии

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

Содержание 1 Суть фрактального сжатия 2 Основная сложность метода 3 Патенты 4 Цитаты 5 См. также 6 Ссылки

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

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

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

[править] Основная сложность метода

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

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

[править] Патенты

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

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

[править] Цитаты

1. ↑ Домашняя страница Майкла Барнсли

[править] См. также

• Фрактал - базовое исходное понятие
• Кривая Коха - пример кривой, задаваемой IFS. Для изображений аналогичное пребразование происходит в двумерном пространстве.
• Треугольник Серпиньского - простой пример изображения, которое легко задать IFS
• JPEG 2000 - основной "конкурент" фрактального сжатия по степени сжатия

[править] Ссылки

• Resources on fractal compression
• Коллекция статей по фрактальному сжатию: Fractal Papers Leipzig Collection
• Fractal Image Compression for Spaceborne Transputers
• Pulcini and Verrando's Compressor