Применение фракталов

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

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

Подробнее о фрактальной графике в разделе "Генерация".

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

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

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

Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций (IFS) к проблеме сжатия изображения была исследована Майклом Барнсли (Michael Barnsley) и Аланом Слоуном (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 лет с момента принятия и он истекает для большинства патентов в ближайшее время, соответственно использование методов, покрывавшихся этими патентами станет гарантированно свободным.

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

Теория фракталов на рынке в свое время вызвала бурные споры, прежде всего, потому что автор, как считают многие, вставил в свою теорию много научной терминологии (фрактал, аттрактор и т.д.), и сделал это не совсем корректно. Поскольку фракталы Вилямса появляются на рынке достаточно часто и практически на всех временных таймфреймах и являются, по сути, простыми локальными экстремумами на отрезке из 5 баров и практически не соответствуют математической теории фракталов. Точно таким же образованием на графике являются и ТД-точки второго порядка Томаса Демарка. Однако, несмотря все эти совпадения это теория весьма популярна и до сих пор.

Совсем не обязательно чтобы баров было пять (5 – минимальное количество баров для формирования фрактала на рынке) и чтобы, например, для фрактала вверх максимумы, начиная от центрального (самого высшего) бара последовательно снижались. Так же необязательным условием является то, что у центрального бара фрактала «вверх» минимум, как и максимум, был выше остальных.

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

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

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

• неразветвляющееся бесконечное дерево, тождественное само себе с любой итерации («У попа была собака…», «Притча о философе, которому снится, что он бабочка, которой снится, что она философ, которому снится…», «Ложно утверждение, что истинно утверждение, что ложно утверждение…»)
• неразветвляющиеся бесконечные тексты с вариациями («У Пегги был весёлый гусь…») и тексты с наращениями («Дом, который построил Джек»).

• венок сонетов (15 стихотворений), венок венков сонетов (211 стихотворений), венок венков венков сонетов (2455 стихотворений)
• «рассказы в рассказе» («Книга тысячи и одной ночи», Я. Потоцкий «Рукопись, найденная в Сарагосе»)
• предисловия, скрывающие авторство (У. Эко «Имя розы»)
• Т. Стоппард «Розенкранц и Гильденстерн мертвы» (сцена с представлением перед королём).

• Х. Л. Борхес «В кругу развалин»
• Х. Кортасар «Жёлтый цветок»
• Ж. Перек «Кунсткамера»