Фрактальные структуры

Существует простая игра, которая требует немного терпения, но позволяет получить удивительные результаты. Вам понадобится лист бумаги в клетку, карандаш и монета. На листе нужно обозначить начальную точку, например центральную клетку. Правила игры таковы: нужно бросить монету. Если выпадет решка, то нужно отсчитать две клетки влево и закрасить следующую. Если же выпадет орел, то нужно перейти на одну клетку ниже и закрасить ее. Правила можно изменять по вашему усмотрению: например, если выпадает решка, то нужно отсчитать две клетки вверхФрактальные структуры и три вправо. После нескольких ходов на бумаге начнет появляться рисунок. Это может быть, например, дерево или цветок. Рисунок будет полностью случайным: мы установили лишь минимум правил, подобно тому как природа устанавливает свои законы. Можно написать простую компьютерную программу, чтобы мгновенно смоделировать тысячу или две тысячи ходов. Нечто подобное проделал исследователь компании 1ВМ Майкл Барнсли, и в результате получился удивительно красивый лист папоротника.

Фрактальная природа

В природе существует множество фрактальных структур. Особенно много фракталов можно увидеть, если понаблюдать за формой деревьев или растений. Если мы внимательно посмотрим на лист папоротника, то увидим, что каждая веточка в точности повторяет все растение. Строго говоря, фрактал — это фигура, которая состоит из нескольких частей, каждая из которых подобна всей фигуре. Фрактал может формироваться по очень простым правилам. Например, к полученному на каждом этапе изображению может каждый раз применяться одно и то же преобразование. Результатом каждого преобразования будет несколько уменьшенных копий оригинала. Так, у дерева образуется множество веток, каждая из которых подобна дереву в миниатюре. Именно это свойство самоподобия и является основным свойством фракталов.

Упорядоченная случайность

Рассмотрим подробнее фрактальную структуру листа папоротника. Мы можем применить к листу различные геометрические преобразования, например сжатие, вращение и перенос. Сочетая эти преобразования и выбирая определенные значения параметров, мы получим различные части листа папоротника, которые будут выглядеть как измененные копии целого листа. Из этих частей можно будет составить лист папоротника целиком. Нам потребуется всего четыре геометрических преобразования. Обозначим их А, В, С и D. Именно здесь удивительным образом вмешивается случайность. Возьмем мешок, в котором лежат четыре одинаковых шара, на каждом из которых написана одна из букв: А, В, С или D. Обозначим на плоскости точку, вытащим шар из мешка и применим к точке соответствующее преобразование. Нанесем на плоскость полученную точку, затем вытащим из мешка новый шар, применим к этой точке новое преобразование и так далее. На бумаге начнет появляться «хаотичное» множество точек, из которых постепенно начнет вырисовываться лист папоротника Этот удивительный результат, полученный Барнсли, натолкнул его на мысль, что подобный алгоритм можно использовать при сжатии изображений.

Фрактальное сжатие

Изображения на экране компьютера состоят из маленьких цветных точек (в действительности — крохотных квадратов), которые называются пикселями. Фотография среднего разрешения, отображаемая на весь экран, может содержать порядка миллиона пикселей. Чтобы передать эту информацию с помощью электрического сигнала по телефонной линии (с помощью модема), необходимо использовать один из алгоритмов сжатия изображения. Барнсли заметил, что на любом изображении всегда есть области, более или менее похожие друг на друга в зависимости от выбранного масштаба. Следовательно, в каждой паре похожих областей одну из них можно получить из другой с помощью более или менее простых преобразований. Мы уже увидели, как можно нарисовать лист папоротника, используя всего одну точку и четыре преобразования. Объем этой информации существенно меньше, чем совокупность информации обо всех точках, которые образуют лист папоротника. Аналогичные действия можно выполнить для любого изображения, в котором существует достаточно много похожих областей. Барнсли создал алгоритм сжатия, который мог соперничать с лучшими алгоритмами на рынке, и запатентовал свое изобретение. Алгоритм получил название «фрактальное сжатие».

Поделиться в соц. сетях

Опубликовать в Facebook

Оцените материал:

1 Star2 Stars3 Stars4 Stars5 Stars (Проголосуйте первым!)
Loading...Loading...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>