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

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

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

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

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

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

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

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

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

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

В разделе не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (14 августа 2019)

Основная сложность фрактального сжатия изображений заключается в необходимости поиска подходящих доменных блоков, что традиционно требует полного перебора. Этот процесс предполагает многократное сравнение каждого рангового блока с набором доменных блоков, что делает операцию вычислительно затратной. Преобразование сравнения блоков в вычисление скалярного произведения позволяет несколько упростить процесс, однако само вычисление скалярного произведения остается ресурсоемким, особенно для изображений высокого разрешения. Современные исследования показывают, что вычислительная сложность классического фрактального алгоритма может достигать O(N^4), где N — линейный размер изображения, при использовании полного перебора для сопоставления ранговых и доменных блоков^[2].

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

Для сокращения вычислительной сложности предложены различные методы оптимизации. В период активных исследований (1992–1996 годы) публиковалось до 300 статей в год, посвященных этой проблеме. Наиболее эффективными направлениями оптимизации являются:

• Метод выделения особенностей (feature extraction): Этот подход основан на извлечении ключевых характеристик блоков изображения, таких как текстурные или градиентные особенности, что позволяет сократить количество сравнений. Например, использование локальной фрактальной размерности для фильтрации контуров объектов значительно ускоряет процесс, особенно при обработке изображений с сильными помехами, таких как фотографии в условиях пыли или дыма.
• Метод классификации доменов (classification of domains): Этот метод предполагает предварительную группировку доменных блоков по определенным признакам, например, по интенсивности пикселей или геометрическим характеристикам. Одним из современных подходов является кольцевая классификация сегментов, где домены и ранговые области классифицируются на основе «колец» с расчетом математического ожидания интенсивностей пикселей. Это позволяет сократить время соотнесения блоков и ускорить сжатие в среднем на 10–15% при сохранении качества изображения.^[3]

С 2020 года исследования фрактального сжатия продолжают развиваться, хотя и с меньшей интенсивностью. Среди актуальных подходов выделяются:

• Иерархический поиск соответствий: Алгоритмы, использующие иерархический поиск, снижают вычислительную сложность до O(N^2) при ухудшении качества изображения не более чем на 5% по сравнению с полным перебором^[4].
• Пространственно-чувствительные хэш-функции: Применение хэш-функций, адаптированных к особенностям задачи, позволяет эффективно находить ближайшие соседние элементы, сокращая время поиска.^[5]
• Квадродеревья для разбиения изображения: Модификация разбиения изображения на ранговые блоки с использованием квадродеревьев и критерия минимальной длины описания улучшает коэффициент сжатия на 10% при сохранении качества^[4].

Несмотря на прогресс, высокая вычислительная сложность фрактального сжатия остается основным препятствием для его широкого распространения. Современные алгоритмы, такие как JPEG-2000, часто предпочтительнее в приложениях реального времени из-за более низких вычислительных затрат, хотя фрактальное сжатие сохраняет преимущество в сжатии текстур и природных объектов с высоким коэффициентом (до 1000:1 в отдельных случаях). Исследования после 2020 года также указывают на потенциал интеграции фрактальных методов с нейронными сетями и эвристиками, такими как генетические алгоритмы, для дальнейшего сокращения времени обработки.

Информация в этой статье или некоторых её разделах устарела. Вы можете помочь проекту, обновив её и убрав после этого данный шаблон. (11 июня 2016)

Майклом Барнсли и другими было получено несколько патентов на фрактальное сжатие в США и других странах.

Например, 4,941,193(выдан в 1990 году): Описывает методы и аппаратуру для сжатия изображений с использованием IFS US4941193A., 5,065,447 (выдан в 1991 году): Охватывает дополнительные аспекты фрактального сжатия US5065447A, 5,384,867(выдан в 1995 году): Фокусируется на улучшенных методах кодирования US5384867A, 5,416,856 (выдан в 1995 году): Описывает оптимизации для фрактального сжатия US5416856A, 5,430,812(выдан в 1995 году): Рассматривает автоматизированные процессы сжатия US5430812A. Единственный патент, близкий по тематике, за последние года — это US6775415 (выдан в 2004 году), который описывает фрактальное сжатие с использованием обучения с подкреплением. Эти патенты покрывают широкий спектр возможных изменений фрактального сжатия и серьёзно сдерживают его развитие.Эти патенты выданы до 2004 года. Поскольку они имели срок действия 17 лет с момента выдачи – то считаются уже истекшими. Таким образом, методы, описанные в этих патентах, теперь находятся в общественном достоянии и могут использоваться без ограничений. Новых патентов, связанных с фрактальным сжатием изображений, на данный момент нет (информация актуальна на июнь 2025 года).

Фрактальное сжатие изображений остается нишевой областью с ограниченной патентной активностью после 2004 года. Истекшие патенты Барнсли и отсутствие новых патентов открывают возможности для свободного использования и разработки новых алгоритмов без юридических ограничений.

• Фрактал
• JPEG 2000
• Список фракталов по размерности Хаусдорфа^[англ.]
• Сжатие изображений на базе дифференциального анализа

• Resources on fractal compression
• Коллекция статей по фрактальному сжатию: Fractal Papers Leipzig Collection
• Fractal Image Compression for Spaceborne Transputers  (недоступная ссылка с 18-05-2013 [4445 дней] — история)
• Pulcini and Verrando’s Compressor
• Сообщество фрактального сжатия изображений

Стиль этой статьи неэнциклопедичен или нарушает нормы литературного русского языка. Статью следует исправить согласно стилистическим правилам Википедии. (13 апреля 2010)