Алгоритмы сжатия изображений


Фрактальный алгоритм - часть 2


/p>

=>


В худшем случае, если не будет применяться оптимизирующий алгоритм, потребуется перебор и сравнение всех возможных фрагментов изображения разного размера. Даже для небольших изображений при учете дискретности мы получим астрономическое число перебираемых вариантов. Причем, даже резкое сужение классов преобразований, например, за счет масштабирования только в определенное количество раз, не дает заметного выигрыша во времени. Кроме того, при этом теряется качество изображения. Подавляющее большинство исследований в области фрактальной компрессии сейчас направлены на уменьшение времени архивации, необходимого для получения качественного изображения.

Далее приводятся основные определения и теоремы, на которых базируется фрактальная компрессия. Этот материал более детально и с доказательствами рассматривается в [3] и в [4].

Определение. Преобразование 

, представимое в виде

где a, b, c, d, e, f действительные числа и 

называется двумерным аффинным преобразованием.

Определение. Преобразование 

, представимое в виде

где a, b, c, d, e, f, p, q, r, s, t, u действительные числа и 

называется трехмерным аффинным преобразованием.

Определение. Пусть 

— преобразование в пространстве Х. Точка 

такая, что 

называется

неподвижной точкой (аттрактором) преобразования.

Определение. Преобразование 

в метрическом пространстве (Х, d) называется сжимающим, если существует число s: 

, такое, что

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

Теорема. (О сжимающем преобразовании)

Пусть 

в полном метрическом пространстве (Х, d). Тогда существует в точности одна неподвижная точка 

этого преобразования, и для любой точки 

последовательность 

сходится к 

.

Более общая формулировка этой теоремы гарантирует нам сходимость.




- Начало -  - Назад -  - Вперед -