gototop
Среда, 27 Март 2013 07:30

Практическое применение фрактальных алгоритмов

Автор  androceus
Оцените материал
(4 голосов)

 После открытия Бенуа Мандельбротом теории фракталов стало понятно, что данная теория способна удивительно точно описывать многие объекты и явления окружающего нас мира. Не удивительно, что теория фракталов и фрактальные алгоритмы в частности, нашли практическое применение в очень многих областях науки и технике.

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

 Фрактальное сжатие изображений.

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

Основа метода фрактального кодирования — это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций к проблеме сжатия изображения была исследована Майклом Барнсли (англ. Michael Barnsley и Аланом Слоуном (англ. Alan Sloan).

Майкл Барнсли.

Они запатентовали свою идею в 1990 и 1991 годах. Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Наиболее наглядно этот процесс продемонстрировал сам Барнсли в своей книге "Фрактальное сжатие изображения". В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накладывается требование: они должны уменьшать в размерах проектируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей.

Один шаг Машины состоит в построении с помощью проецирования по исходному изображению нового. Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой или аттрактором данной СИФ. Collage Theorem (один из принципов фрактального сжатия) гарантирует наличие ровно одной неподвижной точки для каждой СИФ. Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении.

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

Папоротник Барнсли (слева) и треугольник Серпинского (справа).

   

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

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

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

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

Примеры фракталоподобных структур в организме человека: бронхи, сосуды, мышцы.

  

Поэтому учёные задумались можно ли применять фрактальные алгоритмы для диагностики или лечения каких-либо заболеваний? Оказывается возможно. Например теория фракталов может применятся для анализа электрокардиограмм. В последние годы в развитых странах, несмотря на очевидные успехи в разработке новых лабораторных и инструментальных методов диагностики и лечения сердечно-сосудистых заболеваний, продолжается их рост. Периоды биоритмов , и, в частности, сердечного ритма, длительностью порядка часа, суток и более, можно изучать традиционными методами гистограммного или спектрального анализа. Однако оценка хроноструктуры величины и ритмов фрактальной размерности, индексов Херста позволяют на более ранней стадии и с большей точностью и информативностью судить о нарушениях гомеостазиса и развитии конкретных заболеваний.

 Пример кардиограммы. 

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

 Пример рентгеновского снимка.

Рентгеновские снимки обработанные с помощью фрактальных алгоритмов дают более качественную картинку а соответственно и более качественную диагностику!!

 

 

 

 

 

 

Еще одна область в медицине где активно могут применятся фракталы - это гастроэнтерология.  До настоящего времени и зачастую по сей день для диагностики заболеваний ЖКТ используются зондовые методы, которые связаны с необходимостью введения различной толщины зондов, что неприятно как для больного, так и для медперсонала. Кроме того, подобная техника проведения исследований значительно сужает объем их применения ввиду невозможности использования у соматически тяжелых больных, у больных в раннем послеоперационном периоде и т.п. Именно этой причиной объясняется не прекращающийся интерес физиологов и клиницистов к изучению моторно-эвакуаторной деятельности желудка и кишечника, а также к разработке новых методов, позволяющих адекватно, не только качественно, но и количественно оценивать интенсивность и характер моторной активности различных отделов ЖКТ. В качестве дополнительных методов исследования МЭФ применяются методы, основанные на измерении электрической активности органов. Исследования биоэлектрической активности органов ЖКТ положили начало созданию нового метода исследования в медицине, получившего название электрогастроэнтерография.  Электрогастроэнтерография — метод исследования, позволяющий оценить биоэлектрическую активность желудка, двенадцатиперстной кишки и других отделов ЖКТ.

Пример электрогастроэнтерограммы.

Он основан на регистрации изменений электрического потенциала от органов ЖКТ, то есть снятие электрогастроэнтерограмм (ЭГЭГ). Применение фрактального анализа к получаемым биоэлектрическим сигналам от органов, позволяет эффективно судить о моторной функции органов и ЖКТ и успешно диагностировать различные заболевания.

 

           

 

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

Карты адгезии поверхностей раковых и нормальных клеток

 

 

 

 

 

 

 

Применение фракталов в естественных науках.

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

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

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

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

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

Пример твёрдого тела - кристаллы.

 

 

 

 

 

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

Турбулентность.

 

 Применение фракталов в телекоммуникациях.

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

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

 Фракталы как элементы визуализации и спецэффектов.

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

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

Моделирование ландшафта на основе фрактальных алгоритмов с помощью программы Fractal Landscapes.

 

 

 

 

 

 

 

 

 

Скриншот игры Minecraft.

Не обходится без фракталов и в кино. По сути в кино для создания различных фантастических пейзажей, как и в играх используются тот же принцип. Действительно, зачем каждый раз создавать новое дерево или гору, тратя на это кучу времени, когда всё это можно во много раз быстрее сделать с помощью компьютерных программ работающих на фрактальных алгоритмах. Интересный факт: в известном космическом хорроре Ридли Скотта "Чужой" в эпизоде когда команда спускается на поверхность планеты, монитор в корабле передаёт изображение поверхности планеты в виде сетки. Как раз таки это изображение и было создано при помощи фрактальной геометрии. Фрактальная геометрия позволяет художникам по спецэфффектам без труда создавать такие объекты как облака, дым, пламя, звёздное небо и т.д.

Теперь немного затронем тему фрактальной анимации. Фрактальные изображения, созданные в различных генераторах необычайно красивы. Что уж тогда говорить о фрактальной анимации, это действительное потрясающее зрелище. В первую очередь здесь стоит упомянуть о ресурсе Electric sheep.  Electric sheep - ресурс использующий распределённые вычисления для создания фрактальной анимации основанной на алгоритме fractal flame (разработан Скотом Дрейвсом). Проще говоря на ваш компьютер устанавливается программное обеспечение, которое использует вашу машину для вычисления и рендера фрактальной анимации, одновременно с этим загружая и демонстрируя вам уже готовую фрактальную анимацию в виде так называемых "живых" обоев. При этом эти самые обои сохраняются на компьютере в определённой папке и их можно оттуда вытащить, чтобы затем использовать для своих целей, например в видеомонтаже (правда длина роликов коротковата - 5 секунд). Но имея в своём распоряжении программу Апофизис и скрипт к ней  Apophymator, вы сможете без особого труда создавать свою анимацию (благо уроков по этой теме в сети множество) сколь угодно длинную, главное чтобы ваша машина была достаточно мощной.

Скриншоты анимации Electric sheep:

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

Фрактальную анимацию в качестве визуализации используют разработчики программ напрямую не относящиеся к фракталогенераторам. К примеру хорошо известный проигрыватель Winamp имеет в своём наборе большое количество визуализаций (плагин milkdrop) в которых явно прослеживаются элементы фракталов (например анимированное множество Жюлиа). Скриншоты визуализаций в плагине milkdrop для проигрывателя Winamp:

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

Оригинал статьи можно прочесть в мартовском номере журнала Компьюарт.

http://www.compuart.ru/

Прочитано 22177 раз Последнее изменение Вторник, 14 Июнь 2016 01:01

Оставить комментарий

Убедитесь, что вы вводите (*) необходимую информацию, где нужно
HTML-коды запрещены