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

57

2.4.3.2. Вероятностный алгоритм

В то время как детерминистический алгоритм является прямым применением теоремы о сжимающих отображениях, позволяющим легко наблюдать, как он действует, на практике этот алгоритм оказывается слишком медленным и обычно не используется для получения изображений-аттракторов IFS. Более предпочтительным является использование вероятностного алгоритма, основывающегося на «Игре хаоса» ([30], глава 5, где описывается, как играть в «Игру хаоса»).

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

58_Фракталы и вейвлеты для сжатия изображений в Аейстйц

ния, которой управляет это преобразование. Именно это дел. программа, представленная в листинге 2.4.2.

Напомним, что площадь части изображения, управляе\,0ц аффинным преобразованием, пропорциональна определи^ лю матрицы преобразования. Программа, представленная листинге 2.4.2, вычисляет определитель для каждого преобразования. Определители суммируются, и каждое зНа чение делится на сумму, чтобы получить истинное значен^ вероятности от 0 до 1 для каждого преобразования. Это так же гарантирует, что вероятности в сумме равны 1. Вы можете модифицировать программу, чтобы поэкспериментировать с неравномерными распределениями для различных частей изображения-аттрактора.

Так как вероятности /?/ уже сопоставлены преобразованиям п>,ч I = 1,то первый шаг вероятностного алгоритма - выбор случайных точек х0 = (хо,уо) 6 К2- Затем алгоритм вычисляет х\, выбирая случайное целое число /(0) из множества с вероятностью р,(0), и применяет