Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Одним из наиболее ярких примеров среди различных систем итерируемых функций, несомненно, является открытая М. Барнсли система из четырех сжимающих аффинных преобразований, аттрактором для которой является множество точек, поразительно напоминающее по форме изображение листа папоротника. Ее можно представить в виде следующей таблицы
|
a |
b |
c |
d |
e |
f |
p |
(1.52) |
|
0 |
0 |
0 |
0.16 |
0 |
0 |
0.01 |
|
|
0.85 |
0.04 |
-0.04 |
0.85 |
0 |
1.6 |
0.85 |
|
|
0.2 |
-0.26 |
0.23 |
0.22 |
0 |
1.6 |
0.07 |
|
|
-0.15 |
0.28 |
0.26 |
0.24 |
0 |
0.44 |
0.07 |
Каждая строчка этой таблицы соответствует одному аффинному преобразованию с коэффициентами а, b, c, d, e, f в соответствии с выражением (1.34). В последнем столбце таблицы приведены вероятности р, в соответствии с которыми в методе случайных итераций выбирается то или иное преобразование.
Результат действия этой системы функций на некоторую начальную точку для разного числа итераций приведен на рис. 1.43.
Рис. 1.43. Лист папоротника. Слева направо показано 2000, 4000, 10000, 50000 и 200000 итераций.
Видно, как с ростом числа итераций действительно возникает все более и более четкое изображение листа папоротника, удивительным образом напоминающее существующее в природе растение. Это множество точек бесконечно самоподобно, как и полагается всякому фракталу. Как следует из рис. 1.44, увеличенные малые фрагменты изображения подобны целому. Для разрешения этих фрагментов необходимо только, чтобы число итераций было достаточно велико.
Таким образом, чем больше используемое разрешение, тем больше точек требуется внести в память компьютера для того, чтобы построить соответствующее изображение. С другой стороны, запоминать координаты этих точек вовсе не требуется, так как они каждый раз могут быть заново получены с использованием системы функций, заданных таблицей (1.52).
Рис. 1.44. Увеличенный фрагмент листа папоротника.
В результате всего 28 чисел содержат всю необходимую информацию об этом нетривиальном рисунке! Возникает мысль, а нельзя ли подобным образом "кодировать" и другие изображения. Эта идея, будучи реализованной на практике, позволила бы сжимать изображения в десятки или даже в сотни раз. И действительно в 1988 г. она была успешно воплощена Барнсли и Слоаном в созданной ими совместно компании по кодированию и сжатию графической информации с помощью соответствующим образом подобранной системы функций.
Давайте разберем более подробно этот замечательный пример и дадим по возможности наглядную геометрическую интерпретацию числам, приведенным в таблице (1.52). Для этой цели на рис. (1.45) показано действие этой системы функций на квадрат АВСD (изображенный на рисунке пунктиром), повернутый на 45° так, что одна из его диагоналей совпадает с вертикальной осью у, а другая параллельна горизонтальной оси х (на рисунке, чтобы избежать громоздкости, сами оси не показаны). Начало координат при этом совпадает с точкой А.
Первое преобразование соответствует сжатию этого квадрата в вертикальный отрезок прямой, длина которого составляет 16% от диагонали квадрата. Он обозначен на рисунке цифрой 1. Как мы убедимся ниже, это будущий "стебель" всех листьев папоротника.
Рис. 1.45. Действие системы функций (1.52) на квадрат АВСD.
Второе преобразование превращает квадрат АВСD в квадрат А2В2С2D2, который имеет размер в 85% от оригинала, повернут по часовой стрелке относительно вершины А на угол в 2.7° и смещен по вертикали вверх на расстояние в 1.6 условных единиц.
Третье аффинное преобразование переводит квадрат АВСВ в параллелограмм АзВзСзDз. Для этого сторона квадрата АВ сжимается в 3.07 раза и поворачивается вокруг точки А на угол в 46.25° против часовой стрелки. Сторона же квадрата АD этим преобразованием сжимается примерно в 3.12 раза и поворачивается в том же направлении на угол в 52.6°. После чего образовавшийся (близкий к ромбу)
параллелограмм сдвигается вертикально вверх на 1.6 у.е.
Наконец, четвертое преобразование трансформирует исходный квадрат в параллелограмм А4В4С4D4 - Для этого сторона АВ сжимается в 3.29 раза и поворачивается по часовой стрелке вокруг начала координат на угол примерно в 137.7°. Сторона же АD сжимается в 2.74 раза и поворачивается на угол в 30.4°, но против часовой стрелки! Затем получившийся параллелограмм смещается на 0.44 у.е. по вертикали вверх.
Заметим, что в результате четвертого преобразования направление обхода вершин параллелограмма А4В4С4D4 меняется на противоположное по сравнению с исходным квадратом АВСD. Другими словами, четвертое преобразование содержит в себе операцию отражения (например, в вертикальной плоскости) и переводит в итоге правую систему координат в левую. Смысл этого действия для получения правильного изображения листа папоротника мы выясним несколько позже.
Давайте теперь исключим первое преобразование из нашей системы функций. В результате получим СИФ вида
|
a |
b |
c |
d |
e |
f |
Р |
(1.53) |
|
0.85 |
0.04 |
-0.04 |
0.85 |
0 |
1.6 |
0.86 |
|
|
0.2 |
-0.26 |
0.23 |
0.22 |
0 |
1.6 |
0.07 |
|
|
-0.15 |
0.28 |
0.26 |
0.24 |
0 |
0.44 |
0.07 |
всего с тремя функциями и исправленными вероятностями (которые в сумме всегда должны давать единицу). Изображение, полученное итерациями этой СИФ, показано ниже на рис. 1.46 (слева).
Рис. 1.46. Лист без стебля (слева) и стебель без листьев (справа).
|
а |
b |
c |
d |
e |
f |
p |
(1.54) |
|
0 |
0 |
0 |
0.16 |
0 |
0 |
0.05 |
|
|
0.85 |
0.04 |
-0.04 |
0.85 |
0 |
1.6 |
0.95 |
Как видно, в нем отсутствует стебель. Это и понятно. Ведь за формирование стебля как раз и ответственно первое и второе аффинные преобразования. Действительно, если мы теперь оставим только их
то получим стебель, изображенный на рис. 1.46 справа.
|
а |
b |
с |
d |
e |
f |
p |
(1.55) |
|
0 |
0 |
0 |
0.16 |
0 |
0 |
0.01 |
|
|
0.85 |
0 |
0 |
0.85 |
0 |
1.6 |
0.85 |
|
|
0.2 |
-0.26 |
0.23 |
0.22 |
0 |
1.6 |
0.07 |
|
|
-0.15 |
0.28 |
0.26 |
0.24 |
0 |
0.44 |
0.07 |
Довольно очевидно, что за слабый изгиб листа папоротника вправо ответственен поворот на угол в 2.7°, фигурирующий во втором преобразовании. Если мы теперь исключим этот поворот, то получим систему функций вида
Соответствующее этой системе изображение аттрактора приведено на рис. 1.47 слева. Как и следовало ожидать, в нем уже нет изгиба, лист папоротника получился прямой. Если теперь трансляцию в четвертом преобразовании сделать такой же, как и в третьем, т. е. использовать систему функций
Рис. 1.47. Прямой лист папоротника. Слева — (1.55), справа — (1.56).
|
а |
b |
с |
d |
е |
f |
p |
(1.56) |
|
0 |
0 |
0 |
0.16 |
0 |
0 |
0.01 |
|
|
0.85 |
0 |
0 |
0.85 |
0 |
1.6 |
0.85 |
|
|
0.2 |
-0.26 |
0.23 |
0.22 |
0 |
1.6 |
0.07 |
|
|
-0.15 |
0.28 |
0.26 |
0.24 |
0 |
1.6 |
0.07 |
то получим изображение, приведенное на рис. 1.47 справа. Таким образом, трансляция в третьем и четвертом преобразовании задает относительное положение листьев папоротника по обе стороны от стебля.
Кажется, теперь мы начинаем понимать, как работает система функций (1.52). Первые два преобразования формируют стебель, второе и третье формируют листья с одной стороны, а второе и четвертое — с другой стороны стебля (см. рис. 1.48). Относительное положение листьев определяется трансляцией.
Рис. 1.48. Аттрактор второго и третьего (слева) и второго и четвертого (справа) преобразований системы функций (1.52).
Нам осталось разобраться, зачем нужно отражение в четвертом преобразовании. Для этого воспользуемся упрощенной версией системы функций (1.52). А именно, для третьего и четвертого преобразований используем матрицы Â3 ,4 соответственно:
(1.57).
Первая из них соответствует сжатию в 3 раза по обеим осям и повороту против часовой стрелки на угол 60°. Вторая в дополнение к первой содержит еще и операцию отражения в вертикальной плоскости, т.е. замену х à - х. В итоге вместо (1.52) мы приходим к системе функций
|
а |
b |
c |
d |
e |
f |
p |
(1.58) |
|
0 |
0 |
0 |
0.16 |
0 |
0 |
0.01 |
|
|
0.85 |
0.04 |
-0.04 |
0.85 |
0 |
1.6 |
0.85 |
|
|
0.1667 |
-0.2887 |
0.2887 |
0.1667 |
0 |
1.6 |
0.07 |
|
|
-0.1667 |
0.2887 |
0.2887 |
0.1667 |
0 |
0.44 |
0.07 |
Результат действия этой системы функций показан на рис. 1.49 слева.
Если же теперь для четвертого преобразования мы вместо поворота на +60° и последующего отражения в вертикальной плоскости используем поворот на —60° (т.е. по часовой стрелке), то получим систему функций
|
а |
b |
с |
d |
e |
f |
p |
(1.59) |
|
0 |
0 |
0 |
0.16 |
0 |
0 |
0.01 |
|
|
0.85 |
0.04 |
-0.04 |
0.85 |
0 |
1.6 |
0.85 |
|
|
0.1667 |
-0.2887 |
0.2887 |
0.1667 |
0 |
1.6 |
0.07 |
|
|
0.1667 |
0.2887 |
-0.2887 |
0.1667 |
0 |
0.44 |
0.07 |
Результат ее итераций показан на рис. 1.49 справа.
Рис. 1.49. Лист папоротника с правильным изгибом (слева) и с неправильным (справа).
Сравнивая два изображения, мы понимаем, что отражение приводит к правильному изгибу тех листьев, которые расположены с правой стороны от стебля. Если бы во втором преобразовании не содержалось этого изгиба, то лист папоротника был бы прямой и результат действия обоих преобразований (1.58) и (1.59) тогда, очевидно, был бы одинаков.
Меняя параметры аффинных преобразований, входящих в систему функций (1.52), можно получить различные модификации листа папоротника (см. рис. 1.50). Часто они оказываются совсем не похожими на своего "родителя".
И в завершение приведем СИФ для растения, которое особенно популярно в канун нового года. Это, безусловно, елка, и построить ее можно по образу и подобию листа папоротника, надо только, чтобы ее ветки смотрели не вверх, как листья у папоротника, а вниз (см. рис. 1.51). Левая елка получена с помощью системы функций (1.60), где в качестве третьего и четвертого преобразований использованы соответственно повороты на +120° и —120° со сжатием в 3 раза по обоим осям где, в отличие от предыдущего случая, поворот в двух последних преобразованиях произведен на угол ±3π/4. Использованы также несколько другие значения вероятностей. Кроме того, для большей правдоподобности изображения в обоих случаях мы несколько утолщили "ствол".
Рис. 1.50. Представители "семейства папоротниковых".
Рис. 1.51. Елки.
|
а |
b |
с |
d |
е |
f |
p |
(1.60) |
|
0.1 |
0 |
0 |
0.16 |
0 |
0 |
0.01 |
|
|
0.85 |
0 |
0 |
0.85 |
0 |
1.6 |
0.85 |
|
|
-0.1667 |
-0.2887 |
0.2887 |
-0.1667 |
0 |
1.6 |
0.07 |
|
|
-0.1667 |
0.2887 |
-0.2887 |
-0.1667 |
0 |
1.6 |
0.07 |
Правая елка получена с помощью системы функций (1.61)
|
а |
b |
с |
d |
е |
f |
p |
(1.61) |
|
0.1 |
0 |
0 |
0.16 |
0 |
0 |
0.01 |
|
|
0.85 |
0 |
0 |
0.85 |
0 |
1.6 |
0.73 |
|
|
-0.2357 |
-0.2357 |
0.2357 |
-0.2357 |
0 |
1.6 |
0.13 |
|
|
-0.2357 |
0.2357 |
-0.2357 |
-0.2357 |
0 |
1.6 |
0.13 |