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

Рассмотрим еще один способ применения системы итерируемых функций. Возьмем кость. Вместо цифр 1, 2, 3, 4, 5, 6 на шести гранях нанесем всего три буквы х, у, z. Каждая из них будет повторяться дважды. На листе бумаги нарисуем треугольник, вершины которого обозначим теми же буквами х, у, z. Перед началом игры внутри треугольника отмечают произвольную начальную точку. После первого броска расстояние от исходной точки до вершины треугольника, обозначенной буквой, выпавшей при бросании кости, делят пополам и наносят первую точку. Далее алгоритм повторяется от этой точки и т. д. Постепенно на листе бумаги появляется известный фрактал Серпинского. Разумеется, для этой игры совершенно несущественно, чтобы исходный треугольник был равносторонним. С равным успехом «играть в хаос» можно с треугольником любой формы. Дело в том, что фрактал Серпинского является аттрактором для данного алгоритма.

Изменим правила игры. Станем фиксировать точки не на середине отрезка, а на расстоянии в 1/3 от соответствующей вершины. Результат показан на рисунке. Получившееся множество точек — «пыль Серпинского» аналогично множеству «пыль Кантора». Фрактальная размерность такого множества равна единице.

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

Шестиугольник Серпинского состоит из шести одинаковых частей, каждая из которых подобна целому, но имеет размер в три раза меньше исходного. Поэтому его фрактальная размерность D = ln6/lnЗ = 1,6309... Кстати, именно в этом случае игра в хаос будет подобна настоящей игре в кости: на шести гранях игрального кубика можно поставить цифры от одного до шести, соответствующие каждой из вершин шестиугольника.

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

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

Каждая строчка этой матрицы соответствует одному аффинному преобразованию с коэффициентами а, b, с, d, e, f. В последнем столбце таблицы приведены вероятности р, в соответствии с которыми выбирается то или иное преобразование. Результат действия этой системы итерируемых функций на некоторую начальную точку для разного числа итераций показан на рисунке.

Лист папоротника. Слева направо показаны 2000, 4000, 10000, 50000 и 200000 итераций

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

Еще один пример — кленовый лист. Он может быть закодирован следующей матрицей:

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

Изображение кленового листа может быть воспроизведено с помощью относительно простой системы итерируемых функций, так как этот вид изображений обладает высокой степенью самоподобия. Это значит, что целое изображение состоит из уменьшенных копий его самого. Увеличивая такое изображение, мы будем наблюдать одну и ту же степень детализации независимо от разрешения. Реальные изображения не обладают высоким уровнем самоподобия, которое присутствует в изображениях, полученных с помощью систем итерируемых функций. Более того, реальные изображения могут быть представлены различной глубиной цвета от битовых— 1 bit/px (черный/белый) до TrueColor— 24 bit/px и более качественных. Если мы хотим представить такое изображение как результат действия системы итерируемых функций, то, очевидно, нам понадобятся разные системы итерируемых функций для разных фрагментов изображения.

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

Фрактальное кодирование

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

Выявление структуры данных — ключевой аспект эффективного представления и хранения этих данных.

Широко распространено кодирование образов JPEG. Конкуренцию алгоритму сжатия JPEG составляет фрактальное кодирование изображений. Барнсли и Слоун впервые увидели возможность применения фрактального кодирования в середине 1980-х годов. В 1987 году они основали компанию «Iterated Systems Inc.». Оборот