Введение

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

Определение

Формально, итерированная система функций — это конечное множество контрактивных отображений на полном метрическом пространстве. Символически, множество {wi} является итерированной системой функций, если каждое wi является сокращением на полном метрическом пространстве X.

Строительство

Иногда требуется, чтобы каждая функция была линейным или, в более общем случае, аффинным преобразованием и, следовательно, представлялась матрицей. Однако IFS могут также строиться из нелинейных функций, включая проективные и преобразования Мёбиуса. Фрактальное пламя — пример IFS с нелинейными функциями. Наиболее распространенный алгоритм для вычисления IFS-фракталов называется «игра хаоса». Он заключается в выборе случайной точки на плоскости, а затем в итеративном применении одной из функций, случайно выбранной из системы функций, для преобразования точки и получения следующей точки. Альтернативный алгоритм состоит в генерации каждой возможной последовательности функций до заданной максимальной длины, а затем в построении графиков результатов применения каждой из этих последовательностей функций к начальной точке или фигуре. Каждый из этих алгоритмов обеспечивает глобальное построение, генерирующее точки, распределенные по всему фракталу. Если отрисовывается небольшая область фрактала, многие из этих точек окажутся за пределами границ экрана. Это делает масштабирование IFS-конструкции, нарисованной таким образом, непрактичным. Хотя теория IFS требует, чтобы каждая функция была сжимающей, на практике программное обеспечение, реализующее IFS, требует лишь того, чтобы вся система была сжимающей в среднем.

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

Существуют очень быстрые алгоритмы для генерации изображения из набора параметров IFS или PIFS. Гораздо быстрее и требует значительно меньше места для хранения описания процесса создания изображения, передачи этого описания на целевое устройство и повторной генерации изображения на этом устройстве, чем хранить и передавать цвет каждого пикселя изображения. Обратная задача более сложна: имея исходное произвольное цифровое изображение, например, цифровую фотографию, необходимо найти набор параметров IFS, который при итерационном вычислении создаст изображение, визуально похожее на исходное. В 1989 году Арно Жаккин предложил решение для частного случая обратной задачи, используя только PIFS; общая постановка обратной задачи остаётся нерешённой.