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

45

2.3.2. Теорема коллажа

Теорема о сжимающих отображениях (ТСО) может быть применена к отображениям на пространстве (Я(Х), /г) и, в частности, к системам итерируемых функций. Изображение, которое является единственной неподвижной точкой IFS (что гарантируется ТСО) в Я(Х), называется аттрактором EFS. Барнсли [3] сформулировал ТСО для систем итерируемых функций на (Я(Х), h) и назвал ее теоремой коллажа. Следует помнить, что «точка» в Н(Х) - это компактное множество точек в R2, представляющее двоичное изображение.

Теорема коллажа: Пусть L - точка пространства Я(Х). Задано некоторое е>0> Выберем IFS {X, wn: п = 1, 2, N) с коэффициентом сжатия s, О < s < 1, так чтобы

( n \

где А - аттрактор IFS.

Чтобы убедиться в том, что этот результат следует из ТСО, рассмотрим сжимающее отображение / на полном метрическом пространстве (ХД). Пусть X/ - неподвижная точка /. Предположим, что хе X такова, что d(x,f(x)) < s для некоторого 8 > 0. Тогда

h L,LK(L) <е,

тогда

h(L,A)<(l-s)~l h L,

V

d{x,xf)=d{xj(x^<d{xj{x))+d(f{x\f{xf))< <d(x,f(x))+sd(x,xf)

Следовательно

Отсюда следует утверждение теоремы коллажа.

46_Фракталы и вейвлеты для сжатия изображений в Дейст^

2.3.3. О чем говорит теорема коллажа

Предположим, что мы имеем двоичное изображение lq^ и можем задать сжимающие отображения такие, что

/1=1

покрывают L почти точно и не слишком перекрывают его Мы можем считать каждое wn{L) уменьшенной копией I Теорема коллажа утверждает, что тогда аттрактор А системы итерируемых функций {wn} близок к L в метрике Хаусдорфа h. «Коллажом» является набор областей wn(L).

Так как аттрактор А - это результат бесконечного числа итераций IFS, то он, по сути, является фракталом. Теорема коллажа дает алгоритм представления изображений как фракталов. На Рис. 2.3.1 приводится пример этого. На Рис. 2.3.1 (а) вы видите изображение листа (это контур настоящего кленового листа). Как показано на рисунке, изображения листа можно покрыть четырьмя его фрагментами. Это приводит к IFS с четырьмя преобразованиями и>ь и>2, и>з, W4. На Рис. 2.3.1 (Ь) показан аттрактор этой IFS. Обратите внимание на фрактальную основу этого аттрактора. В следующих разделах мы узнаем, как задать преобразования wn и как сгенерировать аттрактор.