Суперфрактал - Сергей Леонидович Деменок Страница 34

Для продвижения бизнеса Барнсли и его коллеги провели блестящую рекламную кампанию. Они опубликовали несколько искусственно созданных картин со сжатием 10 000:1, что значительно превосходит типовой коэффициент сжатия изображений по стандарту JPEG (50:1). Более того, обратный процесс извлечения изображения из фрактального кода — один из самых простых и быстрых. Как и в случае сжатия JPEG, фрактальное сжатие не исключает потери в том смысле, что восстановленное изображение может не соответствовать исходному изображению «точка в точку».

Еще в начале 1990-х годов этот растущий бизнес был защищен патентами: U.S. Patent 5065447 (англ), U.S. Patent 4941193, 5065447, 5384867, 5416856 и 5430812. Патенты покрывают широкий спектр возможных изменений фрактального сжатия и серьезно сдерживают его развитие. Сегодня срок действия большинства патентов истек или истекает в ближайшем будущем. Это, возможно, приведет к ренессансу фрактального метода сжатия изображений.

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

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

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

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

В 1992 году Арнольд Джеквин (в то время он был аспирантом Майкла Барнсли) придумал, как это сделать. Прежде всего необходимо найти самоподобие фрагментов данного изображения. Самоподобие необходимо, иначе ограниченные в своих возможностях аффинные преобразования не смогут верно описать изображение. Если подобия не прослеживается между частью и целым, то можно поискать его между частью и частью.

Упрощенная схема кодирования выглядит так. Изображение делится на небольшие квадратные области — блоки. Параллельно покрываем изображение доменами. Каждый из доменов в четыре раза больше блока. Домены могут пересекаться, их пул покрывает все изображение.

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

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

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

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

Фрактальное кодирование и «игра хаоса» стоят в одном ряду с теорией цепей Маркова и методом Монте Карло. Цепь Маркова, говоря нестрого, есть последовательность особых случайных событий. Их особенность в том, что при фиксированном настоящем будущее независимо от прошлого. Это замечательная идея! Мы с ней живем. Будущее зависит от нашего поведения в настоящем. Наше поведение в настоящем может идти вразрез с прошлыми намерениями и линиями поведения. В каждой точке настоящего совершается разрыв с прошлым. Но и от прошлого мы не можем отказаться.

В русле этой модели американский математик польского происхождения Станислав Улам разработал метод, названный им «методом Монте Карло». Во время долгого выздоровления после болезни Улам раскладывал пасьянсы и задался вопросом, какова вероятность того, что пасьянс сложится. Вместо того чтобы использовать обычные для подобных задач соображения комбинаторики, Улам предположил, что можно просто поставить эксперимент большое число раз и, подсчитав число удачных исходов, оценить вероятность. Эти идеи легли в основу развития теории суперфракталов.

Суперфракталы

Обычные фракталы, которые мы строим по строго определенным правилам, не способны описать природное разнообразие. В книге «Суперфракталы» Майкл Барнсли пишет:

Такая модель появилась в 2002 году в процессе интенсивного сотрудничества Майкла Барнсли, Джона Хатчинсона и Оржана Стенфло в Австралийском Национальном университете (Камберра).

Традиционно математические пространства и множества содержат в себе точки. Сжимающие отображения уменьшают расстояния между точками. Если взять любую точку и начать последовательно применять к ней одно и то же сжимающее отображение ƒ(x), то результатом будет всегда одна и та же точка на множестве X — точечный аттрактор данного отображения.

Аттрактор системы итерированных функций представляет собой не точку, но фигуру, форма которой часто представляет собой фрактал — некое предельное множество точек Н (х). Если мы станем применять ту же систему итерируемых функций для точек множества Н (X), то аттрактором таких преобразований будет то