2.1.2 Компактные множества и пространство Хаусдорфа.

Множество C в метрическом пространстве (X, d) называется компактным, если каждая бесконечная последовательность из C имеет сходящуюся в С подпоследовательность.

Определим пространство Хаусдорфа.

Пусть (Х, d) – полное метрическое пространство. Определим H(X) как пространство, состоящее из компактных подмножеств множества Х. Т.е., каждая точка в H(X) – это компактное подмножество из Х.

Рассмотрим произвольную точку xХ и произвольное BH(X).

Положим по определению d(x, B) = min{d(x, y):y}.

В силу компактности множества B минимум существует и ограничен.

Рассмотрим теперь произвольные A,BH(X) и определим расстояние между ними как

d(A, B) = max{d(x, B): xA}

Компактность А обеспечивает существование и конечность максимума, но d(A, B) не задает метрику, т.к., в общем случае d(A, B) d(B,A).

Определим новую меру расстояния h(A, B):

h(A, B) = max{d(A, B), d(B, A)}.

Теперь мы получили метрику в пространстве H(X).

Метрика h называется метрикой Хаусдорфа, а метрическое пространство (H(X), h) –

метрическим пространством Хаусдорфа.

2.1.3 Сжимающие отображения

Преобразование f : XX в метрическом пространстве (X, d) называется сжимающим

отображением, если существует константа s, 0 s < 1 такая, что

d(f(x₁), f(x₂)) s d(x₁, x₂) для всех x₁, x₂ X.

Константа s называется коэффициентом сжатия отображения f.

Точка х₀ называется неподвижной точкой (аттрактором) сжимающего отображения f, если

f(x₀) = x₀.

Теорема о сжимающих отображениях.

Пусть f : XX сжимающее отображение на полном метрическом пространстве (X, d).

Тогда f имеет одну и только одну неподвижную точку х₀ Х , и для любого хХ

f ⁿ(x) x₀ .

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

Пусть {w₁, w₂, … , w_N} – конечный набор сжимающих отображений в (X, d) с коэффициентами сжатия s₁, s₂, …, s_N . Определим отображение W, на компактные множества точек из Х следующим образом :

W(B) = w₁(B) w₂(B) … w_N(B) для каждого B из Н(Х).

Таким образом получили сжимающее отображение W : H(X) H(X) с коэффициентом сжатия s = max{s₁, s₂, …, s_N}

Система итерируемых функций (IFS) состоит из полного метрического пространства

(Х, d) и конечного множества сжимающих отображений w_n :X X с коэффициентами сжатия s_n. Коэффициент сжатия IFS определяется как s = max{s₁, s₂, …, s_N}.

IFS будем обозначать как {X, w_n: n = 1,2,…, N}.

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

Пусть L – точка пространства Н(Х). Задано некоторое > 0. Выберем IFS {X, w_n: n = 1,2,…,N}

с коэффициентом сжатия s, 0 < s < 1, так чтобы h(L, W(L)) ,

Тогда h(L,A) -s)^-1 h(L, W(L)) -s) ,

Где A – аттрактор данной IFS.

2.1.5 Аффинные преобразования.

Аффинные преобразования – преобразования вида

Аффинные преобразования осуществляют сжатие/растяжение, перенос и поворот объекта.

2.1.6 Кодирование изображений.

Для получения коэффициентов нужного аффинного преобразования (в простейших случаях) достаточно решить 2 системы их 3-х уравнений с 3-мя неизвестными.

В качестве примера рассмотрим построение Треугольника Серпинского. Это изображение описывается 3-мя преобразованиями :

1-е переводит точки {1,2,3} в точки {1,4,6};

2-e : {1,2,3} – в {4,2,5};

3-e : {1,2,3} – в {6,5,3},

( см. рисунок слева внизу).

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