2.2 Изображения в градациях серого.

2.2.1 Метрическое пространство.

Изображения в градациях серого можно рассматривать как вещественные функции f(x,y),

определенные на единичном квадрате I²=I x I.

На этих функциях можно ввести метрику следующим образом:

Пусть F – пространство вещественных функции, интегрируемых с квадратом на I² с введенной метрикой. Тогда (F,d) – полное метрическое пространство и в нем выполняется теорема о сжимающих отображениях.

Поскольку работать мы будем с цифровыми изображениями, которые по сути являются матрицами фиксированных значений функции f(x,y), взятых в фиксированных точках (x_i, y_j), в этом случае можно пользоваться среднеквадратичной метрикой (rms):

2.2.2 Pifs и аффинные преобразования изображений в градациях серого.

В этом разделе используются IFS специального вида – системы итерируемых кусочно-определенных функций (PIFS). PIFS состоит из полного метрического пространства X, набора подобластей D_i из Х и набора сжимающих отображений

w_i : D_i X, i=1, 2, … , n.

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

Пусть w_{0 i} – аффинное преобразование, переводящее в себя единичный квадрат I².

W_{0 I} (x,y) = A_i(x,y)^T +b_i , где А_i – некоторая матрица размера 2х2, b_i – вектор размера 2х1.

Пусть D_i – некоторая подобласть I², и пусть R_i – область значений преобразования

w_{0 i}:

w_{0 i} (D_i) = R_i.

Определим отображение w_i:F F, действующее на изображение f(x,y):

( если w_0i - обратимо и (х,у) из R_i).

Константа s_i управляет контрастностью, o_i управляет яркостью.

w_i – это базовое аффинное преобразование изображений в градациях серого.

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

Для того, чтобы отображение w_i было сжимающим потребуем выполнение условия

d₂(w_i(f), w_i(g))  sd₂(f, g).

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

Пусть {R_i} образуют покрытие множества I², и при этом попарно не пересекаются.

Пусть v_i – PIFS вида v_i : D_i  R_i для некоторого множества доменных областей D_i.

Для каждого v_i определим соответствующее сжатие w_i на пространстве изображений F указанным выше способом.

Пусть W(f(x,y)) = w_i(f(x,y)) для (x ,y) из R_i .

Тогда W является сжатием на F, имеет единственную неподвижную точку f_W и

W_n(f) f_W

при n  для любых изображений f.

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

Пусть задано изображение в градациях серого f . Пусть W – сжимающее отображение такое, что d₂(f,W(f))  .

Тогда d₂(f, f_W) -s), где s - коэффициент сжатия отображения W.

2.2.3 Фрактальное кодирование.

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

Базовый алгоритм кодирования выглядит следующим образом:

1)Разбиваем исходное изображение на непересекающиеся ранговые блоки.

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

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

4)Если достаточно точного соответствия не получаем, то разбиваем ранговые блоки на меньшие. Продолжаем этот процесс до тех пор, пока не добьемся приемлемого соответствия, или размер ранговых блоков не достигнет некоторого заранее определенного предела.