4.4. Коллажи

Рассмотрим задачу, обратную к нахождению аттрактора СИФ. Пусть в нашем распоряжении имеется некоторое изображение или его часть, например листка, дерева и т. п. Необходимо найти совокупность сжимающих аффинных отображений, для которых данное множество является аттрактором. Решение обратной задачи имеет большое значение для такой области прикладных исследований, как сжатие изображений, широко использующееся при передаче изображений в реальном времени. Проиллюстрируем сказанное на примере передачи телевизионного сигнала высокой четкости (HDTV). Из-за того что стандартные кабели, подводящие сигнал к пользовательским телеприемникам, не могут передавать данные достаточно быстро, частота обновления экрана не удовлетворяет стандарту HDTV — она ниже требуемой. По некоторым оценкам, для достижения приемлемой частоты регенерации требуется сжатие данных порядка 1000:1. Было опробовано множество алгоритмов, некоторые из которых претендуют на успешное решение проблемы.

Один привлекательный способ сжатия изображения заключается в том, чтобы разбить исходное изображение на компоненты и считать их аттракторами некоторых СИФ. Так как каждое аффинное преобразование определяется всего лишь шестью коэффициентами, то полное изображение, в принципе, может быть закодировано достаточно малым числом аффинных коэффициентов. Тогда по кабелю можно передавать коэффициенты, а изображение (совокупность аттракторов) восстанавливать по ним, выполняя алгоритм СИФ.

Рассмотрим гипотетический пример. Пусть нам требуется передать изображение ковра Серпинского размером 512 х 512. Не применяя сжатия, придется послать 262144 бит информации, нуль или единицу для каждого пиксела. С другой стороны, если бы мы передали всего лишь 18 аффинных коэффициентов трех аффинных преобразований, связанных с ковром Серпинского, мы смогли бы полностью восстановить оригинал в приемной части. Можно сказать, что в этом случае мы достигли бы сжатия 262144 : 18 = 14563 : 1.

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

Рис. 4.17. Коллаж из фигуры «лист»

Метод который мы рассмотрим ниже, метод коллажа, основан на элементарных свойствах фрактальных изображений.

Предположим, что некоторая конфигурация X представляет собой объединение (коллаж) N непересекающихся множеств, связанных с X преобразованиями подобия с коэффициентами подобия соответственно. В отличие от п. 2.1, коэффициенты подобия могут быть не равны друг другу. Единственное условие: . Тогда X — аттрактор СИФ, заданной преобразованиями .

Например, ковер Серпинского (рис. 2.4) есть коллаж из трех копий самого себя, уменьшенных в два раза.

Вообще говоря, мы можем использовать не только преобразования подобия, но и другие. Это обстоятельство становится важным, если нам, к примеру, требуется эффект удлинения в некотором направлении, как на рис. 4.17. Безусловно, отыскание аффинных отображений для произвольного аттрактора может оказаться очень сложным делом.

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

Теорема 4.4.4. Пусть I — непустое компактное множество (исходное изображение), — сжимающие отображения с коэффициентами сжатия соответственно, Е — аттрактор СИФ или ССИФ, связанной с этими отображениями, и Тогда, если для некоторого выполняется неравенство:

то

Доказательство. Сначала вспомним некоторые свойства сжимающего отображения Т с коэффициентом сжатия s, определенного на метрическом пространстве (X, d). Выберем произвольный элемент . Пусть причем — неподвижная точка. Тогда

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

то есть теорема доказана.

Рис. 4.18. Коллаж из фигуры «дерево»

Рис. 4.17, 4.18, 4.19 и 4.20 иллюстрируют, как используя метод коллажа можно получать некоторые из фракталов, с которыми мы уже знакомы. На этих рисунках конфигурации, обведенные штриховой линией, можно рассматривать в качестве приближения к аттрактору. Элементы коллажа обведены сплошной линией и представляют собой результат применения одного из аффинных преобразований к штрихованной фигуре. Таким образом, мы можем считать, что аттрактор составлен (приблизительно) из элементов коллажа. Очевидно, результат будет тем лучше, чем лучше мы выберем начальное приближение, как указывает теорема 4.4.4.