В лесах фрактальной графики. Часть 4
Андрей Лёушкин
фрилансер, г.Кокшетау (Казахстан)
После открытия Бенуа Мандельбротом теории фракталов стало понятно, что данная теория способна удивительно точно описывать многие объекты и явления окружающего нас мира. Неудивительно, что теория фракталов и фрактальные алгоритмы, в частности, нашли практическое применение в очень многих областях науки и техники. Собственно о практическом применении фрактальных алгоритмов и пойдет речь в данной статье. Фрактал-арт мы затрагивать не будем, о нем достаточно подробно написано в предыдущей статье.
Фрактальное сжатие изображений
Первым и очевидным применением фрактальных алгоритмов стало так называемое фрактальное сжатие изображений. Фрактальное сжатие изображений — это алгоритм сжатия изображений с потерями, основанный на применении систем итерируемых функций к изображениям. Системы итерируемых функций (СИФ) представляют собой системы функций из некоторого фиксированного класса функций, отображающих одно многомерное множество на другое. Данный алгоритм известен тем, что в некоторых случаях позволяет получать очень высокие коэффициенты сжатия. Лучшие примеры — до 1000 раз (при приемлемом визуальном качестве) — для реальных фотографий природных объектов, что недоступно для других алгоритмов сжатия изображений в принципе.1
Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций к проблеме сжатия изображения была исследована Майклом Барнсли (Michael Barnsley) и Аланом Слоуном (Alan Sloan). Они запатентовали свою идею в 1990 и 1991 годах.
Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Наиболее наглядно этот процесс представил сам Барнсли в своей книге «Фрактальное сжатие изображения». В ней введено понятие фотокопировальной машины. Такая машина состоит из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы налагается требование: они должны уменьшать в размерах проецируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей.
Один шаг машины состоит в построении — с помощью проецирования по исходному — нового изображения. Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой или аттрактором данной СИФ. Теорема Collage Theorem гарантирует наличие ровно одной неподвижной точки для каждой СИФ. Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении.
Наиболее известны два изображения, полученных с помощью СИФ: треугольник Серпинского и папоротник Барнсли (рис. 1). Первое задается тремя, а второе — пятью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считаными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт.
Рис. 1. Треугольник Серпинского и папоротник Барнсли
Становится понятно, как работает архиватор и почему ему требуется так много времени. Фактически, фрактальная компрессия — это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований.
В худшем случае, если не будет применяться оптимизирующий алгоритм, потребуется перебор и сравнение всех возможных фрагментов изображения разного размера. Даже для небольших изображений при учете дискретности мы получим астрономическое число перебираемых вариантов. Даже резкое сужение классов преобразований, например за счет масштабирования только в определенное число раз, не позволит добиться приемлемого времени. Кроме того, при этом теряется качество изображения. Подавляющее большинство исследований в области фрактальной компрессии сейчас направлено на уменьшение времени архивации, необходимого для получения качественного изображения.
Фракталы как элементы визуализации и спецэффектов
Фракталы притягивают и завораживают своей красотой и бесконечностью. Именно поэтому (и не только) фракталы очень часто используют для создания различного рода визуализаций, видеоинсталляций, создания спецэффектов в компьютерной графике и т.д.
Начнем, пожалуй, с игр. Сегодня в очень многих играх (самый яркий пример — Minecraft, рис. 2), где присутствуют красивые природные ландшафты, так или иначе используются фрактальные алгоритмы. Этот способ зарекомендовал себя довольно эффективно. Дело в том, что настоящие природные объекты имеют в своей основе фрактальную структуру. Взяв это на вооружение, программисты предприняли попытку создать компьютерные ландшафты на базе фрактальных алгоритмов. Наблюдая сегодняшнее многообразие игр с красивыми природными ландшафтами, можно сказать — им это удалось. Более того, создано большое количество программ для генерации ландшафтов и пейзажей, основанных на фрактальных алгоритмах.
Рис. 2. Рельефы игр
Не обошлось без фракталов и в кино, где для создания различных фантастических пейзажей (как и в играх) используется тот же принцип. Действительно, зачем каждый раз создавать новое дерево или гору, тратя кучу времени, когда всё это можно во много раз быстрее сделать с помощью компьютерных программ, работающих на фрактальных алгоритмах. Интересный факт: в известном космическом хорроре «Чужой» Ридли Скотта, в эпизоде, когда команда спускается на поверхность планеты, монитор в корабле передает изображение поверхности планеты в виде сетки. Именно это изображение было создано при помощи фрактальной геометрии. Фрактальная геометрия позволяет художникам по спецэффектам без труда создавать такие объекты, как облака, дым, пламя, звездное небо и т.д.
Теперь немного затронем тему фрактальной анимации. Фрактальные изображения, созданные в различных генераторах, необычайно красивы. Что уж тогда говорить о фрактальной анимации?! Это действительно потрясающее зрелище. В первую очередь здесь стоит упомянуть о ресурсе Electric sheep, использующем распределенные вычисления для создания фрактальной анимации, основанной на алгоритме fractal flame (разработан Скоттом Дрейвсом — Scott Draves). Проще говоря, на компьютер устанавливается программное обеспечение, которое использует машину для вычисления и рендера фрактальной анимации. Одновременно с этим ПО загружает и демонстрирует уже готовую фрактальную анимацию в виде так называемых живых обоев, которые сохраняются в определенной папке. В дальнейшем их можно использовать в своих целях, например в видеомонтаже (правда, длина роликов коротковата — 5 секунд). Однако, имея в своем распоряжении программу «Апофизис» и скрипт к ней Apophymator, можно без особого труда создавать свою сколь угодно длинную анимацию (уроков по этой теме в Сети множество), главное, чтобы машина была достаточно мощной (рис. 3).
Рис. 3. Примеры фрактальных анимаций
Рис. 4. Анимированное множество Жюлиа плагина milkdrop
Зрелищность фрактальной анимации с успехом применяют и виджеи в своих видеосетах. Особенно часто такие видеоинсталляции используются на концертах электронной музыки. Для этого применяются так называемые программы виджеинга (например, Resolume). Фрактальную анимацию в качестве визуализации используют разработчики программ, напрямую не относящихся к фракталогенераторам. К примеру, хорошо известный проигрыватель Winamp имеет в своем наборе большое количество визуализаций (плагин milkdrop), в которых явно прослеживаются элементы фракталов, например анимированное множество Жюлиа (рис. 4).
Применение фракталов в телекоммуникациях
В телекоммуникациях фракталы применяются для создания фрактальных антенн (рис. 5) — относительно нового класса электрически малых антенн, принципиально отличающихся своей геометрией от известных решений. Традиционная эволюция антенн базировалась на евклидовой геометрии, оперирующей объектами целочисленной размерности (линия, круг, эллипс, параболоид и т.п.). Фрактальные антенны с удивительно компактным дизайном обеспечивают превосходную широкополосную производительность в маленьком формфакторе. Достаточно компактные для установки или встраивания в различных местах фрактальные антенны используются в морских, воздушных транспортных средствах или в персональных устройствах.
Рис. 5. Антенна в виде ковра Серпинского
В сфере сетевых технологий было также проведено множество исследований, показывающих самоподобие трафика, передаваемого по разного рода сетям. Особенно это касается речевых, аудио и видеосервисов. В связи с этим сейчас проводится изучение возможности фрактального сжатия трафика, передаваемого по сетям, для более эффективной передачи информации.
Применение фракталов в медицине
В настоящее время фракталы уже находят и, вероятно, будут и в дальнейшем находить применение в медицине. Человеческий организм состоит из множества фракталоподобных структур: кровеносная система, мышцы, бронхи и т.д., поэтому ученые задумались о возможности применения фрактальных алгоритмов для диагностики и лечения какихлибо заболеваний. Оказалось, что такая возможность существует. Теория фракталов, например, может применяться для анализа электрокардиограмм. В последние годы в развитых странах, несмотря на очевидные успехи в разработке новых лабораторных и инструментальных методов диагностики и лечения сердечнососудистых заболеваний, рост последних неуклонно продолжается. Периоды биоритмов, в частности сердечного ритма, длительностью порядка часа, суток и более можно изучать традиционными методами гистограммного или спектрального анализа. Однако оценка хроноструктуры величины и ритмов фрактальной размерности, индексов Херста позволяет на более ранней стадии и с большей точностью и информативностью судить о нарушениях гомеостазиса и о развитии конкретных заболеваний.
Фракталы могут использоваться также (пока на стадии экспериментов) в обработке медицинских рентгеновских изображений. Рентгеновские снимки, обработанные с помощью фрактальных алгоритмов, дают более качественную картинку, а следовательно — и более качественную диагностику!
Еще одна область медицины, где активно могут применяться фракталы — это гастроэнтерология. Для диагностики заболеваний желудочнокишечного тракта (ЖКТ) по сей день используются зондовые методы, которые связаны с необходимостью введения различной толщины зондов. Такая процедура неприятна как для больного, так и для медперсонала и невозможна при исследовании соматически тяжелых больных, больных в раннем послеоперационном периоде и пр. Именно этой причиной объясняется непрекращающийся интерес физиологов и клиницистов к изучению и разработке новых методов, позволяющих не только качественно, но и количественно адекватно оценивать интенсивность и характер моторной активности различных отделов ЖКТ. В качестве дополнительных методов исследования моторноэвакуатурной функции применяются методы, основанные на измерении электрической активности органов. Исследования биоэлектрической активности органов ЖКТ положили начало созданию нового метода исследования в медицине, получившего название электрогастроэнтерография. Электрогастроэнтерография — это метод исследования, позволяющий оценить биоэлектрическую активность желудка, двенадцатиперстной кишки и других отделов ЖКТ, который осуществляется посредством электрогастроэнтерограмм. Применение фрактального анализа к получаемым биоэлектрическим сигналам от органов позволяет эффективно судить об их моторной функции и успешно диагностировать различные заболевания.
Необходимо упомянуть и о недавнем открытии американских ученых в области раковых заболеваний. Они показали, что если составить карты адгезии (от лат. adhaesio — прилипание, в физике — сцепление поверхностей разнородных твердых и/или жидких тел) поверхностей нормальных и раковых клеток, то окажется, что эти карты имеют разную фрактальную размерность (рис. 6). Возможно, это открытие в будущем поможет разработать новые эффективные методы диагностики и лечения онкологических заболеваний.
Рис. 6. Карты адгезии нормальных и раковых клеток
Применение фракталов в естественных науках
Применение фракталов в естественнонаучных дисциплинах чрезвычайно важно. Не хватит и целой книги, если попытаться описать всё, поэтому остановимся на некоторых самых интересных аспектах.
Очень часто фракталы применяются в геологии и геофизике. Не секрет, что побережья островов и континентов имеют некоторую фрактальную размерность, зная которую можно очень точно вычислить их длину. Фрактальный анализ также помогает в поиске и разработке месторождений полезных ископаемых, распределение которых очень часто происходит по фрактальному механизму. Исследование разломной тектоники и сейсмичности порой тоже осуществляется с помощью фрактальных алгоритмов.
Геофизика использует фракталы и фрактальный анализ для исследования аномалий магнитного поля, для изучения распространения волн и колебаний в упругих средах, для исследования климата и многих других природных явлений.
В физике фракталы применяются еще шире. Например, в физике твердых тел фрактальные алгоритмы позволяют точно описывать и предсказывать свойства твердых, пористых, губчатых тел, различных аэрогелей. Это помогает в создании новых материалов с необычными и полезными свойствами.
Рис. 7. Турбулентность и кристаллы
Изучение турбулентности в потоках очень хорошо подстраивается под фракталы. Турбулентные потоки хаотичны, поэтому их сложно точно смоделировать. И здесь помогает переход к фрактальному представлению, что сильно облегчает работу инженерам и физикам, позволяет им лучше понять динамику сложных систем (рис. 7). При помощи фракталов также можно смоделировать языки пламени. Пористые материалы хорошо представляются во фрактальной форме в связи с тем, что они имеют очень сложную геометрию. Это используется в науке о нефти.
Итак, проведя сей небольшой обзор, можно с уверенностью сказать об огромном практическом применении фракталов и фрактальных алгоритмов. Список областей, где применяются фракталы, очень широк, и в ближайшем будущем он будет только пополняться!