Система итерированных функций

Метод построения фракталов

Треугольник Серпинского, созданный с помощью IFS (раскрашен для иллюстрации самоподобной структуры)

Цветная IFS, разработанная с использованием программного обеспечения Apophysis и визуализированная Electric Sheep .

В математике системы итерированных функций ( IFS ) представляют собой метод построения фракталов ; полученные фракталы часто являются самоподобными . Фракталы IFS больше связаны с теорией множеств, чем с фрактальной геометрией. ^[1] Они были введены в 1981 году.

Фракталы IFS , как их обычно называют, могут иметь любое количество измерений, но обычно вычисляются и рисуются в 2D. Фрактал состоит из объединения нескольких копий самого себя, каждая копия преобразуется функцией (отсюда «функциональная система»). Каноническим примером является треугольник Серпинского . Функции обычно являются сжимающими , что означает, что они сближают точки и уменьшают формы. Следовательно, форма фрактала IFS состоит из нескольких возможно перекрывающихся меньших копий самого себя, каждая из которых также состоит из копий самого себя, и так до бесконечности . Это источник его самоподобной фрактальной природы.

Определение

Формально, система итерированных функций представляет собой конечный набор отображений сжатия на полном метрическом пространстве . ^[2] Символически,

${\displaystyle \{f_{i}:X\to X\mid i=1,2,\dots ,N\},\ N\in \mathbb {N} }$

является итеративной системой функций, если каждая из них является сжатием на полном метрическом пространстве . ${\displaystyle f_{i}}$ ${\displaystyle X}$

Характеристики

Построение IFS с помощью игры хаос (анимированное)

IFS создается с двумя функциями.

Хатчинсон показал, что для метрического пространства или, в более общем смысле, для полного метрического пространства такая система функций имеет единственное непустое компактное (замкнутое и ограниченное) фиксированное множество S . ^[3] Один из способов построения фиксированного множества — начать с начального непустого замкнутого и ограниченного множества S ₀ и повторить действия f _i , принимая S _{n +1} за объединение образов S _n при f _i ; затем принимая S за замыкание предела . Символически единственное фиксированное (непустое компактное) множество обладает свойством ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle X}$ ${\displaystyle \lim _{n\rightarrow \infty }S_{n}}$ ${\displaystyle S\subseteq X}$

${\displaystyle S={\overline {\bigcup _{i=1}^{N}f_{i}(S)}}.}$

Таким образом, множество S является фиксированным множеством оператора Хатчинсона, определенного для посредством ${\displaystyle F:2^{X}\to 2^{X}}$ ${\displaystyle A\subseteq X}$

${\displaystyle F(A)={\overline {\bigcup _{i=1}^{N}f_{i}(A)}}.}$

Существование и единственность S является следствием принципа отображения сжатия , как и тот факт, что

${\displaystyle \lim _{n\to \infty }F^{n}(A)=S}$

для любого непустого компактного множества в . (Для сжимающего IFS эта сходимость имеет место даже для любого непустого замкнутого ограниченного множества ). Случайные элементы, сколь угодно близкие к S, могут быть получены с помощью «игры в хаос», описанной ниже. ${\displaystyle A}$ ${\displaystyle X}$ ${\displaystyle A}$

Недавно было показано, что IFS неконтрактивного типа (т.е. составленные из отображений, которые не являются контракциями относительно любой топологически эквивалентной метрики в X ) могут давать аттракторы. Они естественным образом возникают в проективных пространствах, хотя классическое иррациональное вращение на окружности также может быть адаптировано. ^[4]

Коллекция функций генерирует моноид при композиции . Если таких функций всего две, моноид можно визуализировать как бинарное дерево , где в каждом узле дерева можно выполнить композицию с одной или другой функцией ( т.е. взять левую или правую ветвь). В общем случае, если есть k функций , то можно визуализировать моноид как полное k -арное дерево , также известное как дерево Кэли . ${\displaystyle f_{i}}$

Конструкции

Папоротник Барнсли , ранний IFS

Губка Менгера , трехмерная IFS.

IFS "дерево" построено с нелинейной функцией Julia

Иногда требуется, чтобы каждая функция была линейным , или, в более общем смысле, аффинным , преобразованием, и, следовательно, представлена ​​матрицей . Однако IFS также могут быть построены из нелинейных функций, включая проективные преобразования и преобразования Мёбиуса . Фрактальное пламя является примером IFS с нелинейными функциями. ${\displaystyle f_{i}}$

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

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

Хотя теория IFS требует, чтобы каждая функция была сжимающей, на практике программное обеспечение, реализующее IFS, требует, чтобы вся система была сжимающей только в среднем. ^[5]

Системы секционированных итерационных функций

PIFS (системы секционированных итерированных функций), также называемые локальными системами итерированных функций, ^[6] обеспечивают удивительно хорошее сжатие изображений, даже для фотографий, которые, по-видимому, не имеют самоподобной структуры, демонстрируемой простыми фракталами IFS. ^[7]

Обратная задача

Существуют очень быстрые алгоритмы для генерации изображения из набора параметров IFS или PIFS. Это быстрее и требует гораздо меньше места для хранения описания того, как оно было создано, передачи этого описания на целевое устройство и повторной генерации этого изображения на целевом устройстве, чем сохранение и передача цвета каждого пикселя в изображении. ^[6]

Обратная задача сложнее: имея некоторое исходное произвольное цифровое изображение, например цифровую фотографию, попытайтесь найти набор параметров IFS, который при оценке итерацией даст другое изображение, визуально похожее на оригинал. В 1989 году Арно Жакен представил решение ограниченной формы обратной задачи, используя только PIFS; общая форма обратной задачи остается нерешенной. ^{[8] [9] [6]}

Начиная с 1995 года все программное обеспечение для фрактального сжатия основано на подходе Жакена. ^[9]

Примеры

На схеме показано построение IFS из двух аффинных функций. Функции представлены их воздействием на двуединичный квадрат (функция преобразует выделенный квадрат в заштрихованный квадрат). Комбинация двух функций образует оператор Хатчинсона . Показаны три итерации оператора, а затем окончательное изображение — неподвижная точка, окончательный фрактал.

Ранние примеры фракталов, которые могут быть получены с помощью IFS, включают множество Кантора , впервые описанное в 1884 году, и кривые де Рама , тип самоподобной кривой, описанный Жоржем де Рамом в 1957 году.

История

В своем нынешнем виде IFS были задуманы Джоном Э. Хатчинсоном в 1981 году ^[3] и популяризированы книгой Майкла Барнсли «Фракталы повсюду ».

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

—  Майкл Барнсли и др. ^[10]

Смотрите также

• Математический портал

• Комплексно-базовая система
• Теорема коллажа
• Бесконечные композиции аналитических функций
• L-система
• Фрактальное сжатие

Примечания

1. Зобрист, Джордж Уинстон; Чаман Сабхарвал (1992). Прогресс в компьютерной графике: Том 1. Intellect Books. стр. 135. ISBN 9780893916510. Получено 7 мая 2017 г.
2. Майкл Барнсли (1988). Фракталы повсюду , стр. 82. Academic Press, Inc. ISBN 9780120790623 . 
3. Хатчинсон, Джон Э. (1981). «Фракталы и самоподобие» (PDF) . Indiana Univ. Math. J. 30 ( 5): 713–747. doi : 10.1512/iumj.1981.30.30055 .
4. М. Барнсли, А. Винс, Игра хаоса в общей системе итерированных функций
5. Draves, Scott ; Erik Reckase (июль 2007 г.). "Алгоритм фрактального пламени" (PDF) . Архивировано из оригинала (PDF) 2008-05-09 . Получено 2008-07-17 .
6. Бруно Лакруа. «Фрактальное сжатие изображений». 1998.
7. Фишер, Ювал (1992-08-12). Пшемыслав Прусинкевич (ред.). Заметки к курсу SIGGRAPH'92 - Фрактальное сжатие изображений (PDF) . SIGGRAPH. Том. Фракталы - от народного искусства к гиперреальности. ACM SIGGRAPH . Архивировано из оригинала (PDF) 2017-09-12 . Получено 2017-06-30 .
8. Дитмар Саупе, Рауф Хамзауи. «Обзор литературы по фрактальному сжатию изображений».
9. Джон Коминек. "Алгоритм быстрого фрактального сжатия изображений". doi :10.1117/12.206368.
10. Майкл Барнсли и др. , «Фракталы и суперфракталы V-переменной» (PDF) . (2,22 МБ)

Ссылки

• Draves, Scott ; Erik Reckase (июль 2007 г.). "Алгоритм фрактального пламени" (PDF) . Архивировано из оригинала (PDF) 2008-05-09 . Получено 2008-07-17 .
• Фальконер, Кеннет (1990). Фрактальная геометрия: Математические основы и приложения . John Wiley and Sons. стр. 113–117, 136. ISBN 0-471-92287-0.
• Barnsley, Michael ; Andrew Vince (2011). «The Chaos Game on a General Iterated Function System». Эргодическая теория динам. систем . 31 (4): 1073–1079. arXiv : 1005.0322 . Bibcode :2010arXiv1005.0322B. doi :10.1017/S0143385710000428. S2CID  122674315.
• Для исторического обзора и обобщения: Дэвид, Клэр (2019). «фрактальные свойства функций типа Вейерштрасса». Труды Международного геометрического центра . 12 (2): 43–61. doi : 10.15673/tmgc.v12i2.1485 . S2CID  209964068.

Внешние ссылки

• Учебник по элементарной теории бесконечных композиций комплексных функций