4.2. Реализация СИФ

Как было отмечено в п. 4.1, имеется два подхода к реализации СИФ: детерминированный и рандомизированный. Детерминированный алгоритм позволяет получать привлекательные изображения, но требует обработки больших массивов нулей и единиц. Единица означает, что соответствующий пиксел принадлежит изображению, а нуль означает, что соответствующий пиксел не принадлежит изображению.

Рис. 4.3. Модифицированный ковер Серпинского

Для компьютерной программы детерминированного СИФ алгоритма лучше всего подходят такие языки программирования, как Си, Паскаль, Фортран или другие, допускающие компиляцию. Компилированная версия программы (в машинном коде) всегда работает намного быстрее версии с встроенным интерпретатором.

В рандомизированном алгоритме нет необходимости хранить большие массивы данных в памяти. Поэтому им удобно пользоваться на компьютерах с ограниченными ресурсами, вычисляя одну точку на каждом шаге и сразу же отображая ее на экране. С другой стороны, для того чтобы получить изображение приемлемого качества, требуются тысячи точек, поэтому данный подход нельзя назвать экономным.

Детерминированный алгоритм.

Сначала выберем размеры окна х для графического вывода. Размеры меньше 200 х 200 используются обычно для прикидки, чтобы посмотреть, как примерно будет выглядеть конечное изображение. Начиная где-то с 256 х 256, качество изображений становится удовлетворительным.

Однако если вы хотите получить превосходный результат, размеры окна должны составлять 400 х 400 или более. При этом не стоит забывать, что вычисления производятся для точек на каждой итерации, и, следовательно, с ростом объем вычислений может превысить разумные пределы.

Далее, когда размер окна зафиксирован, имеет смысл использовать преобразование мировых координат в экранные, описанное в п. 3.4, и найти эквиваленты аффинных отображений для окна . Тогда все вычисления можно будет производить в экранных координатах. Далее мы предполагаем, что все отображения заданы в экранных координатах.

Программная реализация детерминированного алгоритма не лишена подводных камней. Если какая-нибудь точка выйдет за пределы окна , это приведет к аварийному останову программы с сообщением об ошибке типа «индекс вышел за пределы». Такое может случиться, даже если визуально аттрактор целиком содержится внутри выбранного окна. Обычно подобная проблема возникает на одной из первых итераций. Практическое решение состоит в том, чтобы проверять новые точки сразу же после их нахождения и прекращать вычисления для точек, вышедших за границы окна. Это не должно привести к существенной потере информации в конечном изображении, так как большинство точек в конечном изображении являются результатом итерирования многих различных начальных точек.

Пусть СИФ задана аффинными преобразованиями:

Будем хранить все коэффициенты в одной матрице С размера :

Далее следует детерминированный алгоритм СИФ (ДСИФ).

Алгоритм 4.2.1. (ДСИФ)

Назначение: детерминированная система итерированных функций. Вход:

Выход:

Т (бинарная матрица аттрактора размера )

Инициализация:

Шаги:

Рандомизированный алгоритм.

Укажем два главных отличия рандомизированного алгоритма от детерминированного. Во-первых, начальное множество содержит всего одну точку. Во-вторых, на каждом шаге используется только одно аффинное преобразование из всей совокупности преобразований, задающих СИФ.

Это преобразование выбирается случайным образом. Полученное множество также содержит ровно одну точку, которая сразу же выводится на экран и используется для вычисления следующей итерации. Следовательно, отпадает необходимость хранить все точки, кроме текущей.

Аффинное преобразование уменьшает (или увеличивает) площади в раз (см. упр. 1 в конце этого параграфа). Для того чтобы в процессе случайного выбора преобразования с малым детерминантом не появлялись слишком часто, имеет смысл производить выбор с вероятностями, пропорциональными детерминантам. Для этого определим веса

где — матрица аффинного преобразования Очевидно, то есть определенные нами веса суть вероятности. В рандомизированном алгоритме преобразование выбирается с вероятностью Для этого используется внешняя подпрограмма . Она принимает вектор в качестве входного параметра и возвращает одно из чисел , причем число j появляется с вероятностью

Ниже приводится рандомизированный алгоритм (РСИФ), в котором все вычисления и вывод на экран производятся в мировых координатах.

Алгоритм 4.2.2. (РСИФ)

Назначение: рандомизированная система итерированных функций.

Вход:

Выход:

изображение аттрактора.

Инициализация:

графическое окно вывода

Шаги:

Замечание: команда означает, что целое число к выбирается случайным образом с вероятностью

Интересные примеры аттракторов, построенных при помощи СИФ, изображены на рис. 4.4, 4.5, 4.6, 4.7, 4.8 и 4.9. Соответствующие аффинные коэффициенты приведены в табл. 4.1.