Принципи фрактального кодування зображень

КИЇВ – 2012

 

Міністерство  освіти, науки, молоді та спорту України

Національний технічний університет  України

“Київський політехнічний  інститут”

Факультет електроніки

Кафедра акустики та акустоелектроніки

 

 

 

 

 

Реферат

на тему «Принципи фрактального кодування зображень»

з дисципліни:     Методи реєстрації і обробки інформації

 

 

 

 

 

Виконала        

студентка 5 курсу

групи ДГм81

Михеєва А.М.

 

 

 

СОДЕРЖАНИЕ

 

Введение: что  такое фрактал и его история 3

 

1. Идея и задача фрактального сжатия изображения 4

2. Алгоритм сжатия и восстановления изображения 4

3. Сравнение эффективности сжатия с другими методами 7

4. Сложности и методы их устранения 9

 

Список используемой литературы 10

 

 

Введение: что такое фрактал и его история

Строгое определение фракталов, или самоподобных множеств, было дано Дж. Хатчинсоном в 1981 году. Он назвал множество самоподобным, если оно состоит из нескольких компонент, подобных всему этому множеству, т.е. компонент получаемых афинными преобразованиями – поворотом, сжатием и отражением исходного множества.  [3]

Классическим примером фрактала является лист папоротника – так называемый “папоротник Барнсли” :

 

Рисунок 1 – “Папоротник Барнсли”

 

Широкое применение фрактального описания физических явлений началось с работ Бенуа Мандельброта, в частности, наиболее известной его работы, “Фрактальная геометрия природы” [1].

Мандельброт придумал термин "фрактал" как производную от латинского слова «fractus», что означает «ломанный, фрагментарный, нерегулярный», и был первым, кто показал, что многие математические модели, ранее считавшиеся актуальными только для чистой математики, могут быть с успехом быть применены для описания явлений природы и социальной сферы.

Вопросом фрактального сжатия начали заниматься в 1987 году профессора университета штата Джорджия Майкл Барнсли и Алан Слоун.  В 1988 году Барнсли выпустил книгу “Фракталы повсюду” [5], а свою идею фрактального сжатия Барнсли и Слоун запатентовали в 1990 и 1991 годах.

 

1. Идея и задача фрактального сжатия изображения

Фрактальное сжатие изображений  – алгоритм сжатия изображений c потерями, основанный на применении систем итерируемых  функций (как правило, являющимися аффинными преобразованиями) к изображениям. Данный алгоритм известен тем, что в некоторых случаях позволяет получить очень высокие коэффициенты сжатия при приемлемом визуальном качестве для реальных фотографий природных объектов, что недоступно для других алгоритмов сжатия изображений в принципе. Коэффициент сжатия у фрактальных алгоритмов варьируется в пределах 2-2000. Особенностью метода является потребность в колоссальных вычислительных мощностях при архивации. Из-за сложной ситуации с патентованием широкого распространения алгоритм не получил. [2, 4]

Фрактальная компрессия стала  практически реализуемой после  введения Арно Жаквином понятия итерируемых кусочно-определённых функций, в которых, каждое из набора отображений покрывает изображение частично, а не целиком.

Идея метода фрактального сжатия заключается в следующем: предположим, что исходное изображение является неподвижной точкой некоего сжимающего отображения. Тогда можно вместо самого изображения запомнить каким-либо образом это отображение, а для восстановления достаточно многократно применить это отображение к любому стартовому изображению. По теореме Банаха, такие итерации всегда приводят к неподвижной точке, то есть к исходному изображению.

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

Приведем алгоритм фрактального сжатия изображений на основе терминологии и обозначений работы [7].

2. Алгоритм сжатия и восстановления изображения

Метрика — функция, заданная на пространстве, возвращающая расстояние между двумя точками этого пространства.

Сжимающее отображение (преобразование) — функция на метрическом пространстве, равномерно уменьшающая расстояние между двумя точками пространства. Например, y=0.5x.

Аффинные преобразования  — это правила, в соответствии с которым каждому элементу множества ставится в соответствие элемент этого же множества. [2]

Математический язык. Есть отображение , где – множество всех возможных изображений. является объединением отображений :

где – изображение, а   – какие-то (возможно, перекрывающиеся) области изображения . Каждое преобразование переводит в . Таким образом,

Представим изображение в виде функции двух переменных На множестве всех таких функций введём метрику (расстояние между изображениями), например, таким образом:

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

Такие отображения называются сжимающими, и для них справедливо  следующее утверждение: если к какому-то изображению мы начнём многократно применять отображение таким образом, что

то в пределе, при , стремящемся к бесконечности, мы получим одно и то же изображение вне зависимости от того, какое изображение мы взяли в качестве F0:

 

 

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

1. по размерам больше ;
2. имеет ту же форму, размеры и положение, что и ;
3. Коэффициент u преобразования должен быть меньше единицы;
4. Значение должно быть как можно меньше.

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

Таким образом, для компрессии изображения W нужно:

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

  

а)

б)

 

Рисунок 2 – Разбиение изображения

 

Соответственно, для декомпрессии изображения нужно будет:

1. Создать какое-то (любое) начальное изображение ;
2. Многократно применить к нему отображение (объединение );
3. Так как отображение сжимающее, то в результате, после достаточного количества итераций, изображение придёт к аттрактору, конечному состоянию, и перестанет меняться. Аттрактор и является исходным изображением. Декомпрессия завершена.
3. Сравнение эффективности сжатия с другими методами

 

В нижеприведенной таблице приведена  сравнительная характеристика методов  сжатия изображения [4]:

Алгоритм	Коэфф-ты сжатия	Симметричность по времени (ресурсоемкость)	На какие изображения ориентирован	Потери	Размерность
Групповое кодирование	1/32 1/2 2/1	1	3,4 битные	Нет	1D
LZW	1/100 1/4 7/5	1.2-3	1-8 битные	Нет	1D
Хаффмана	1/8 2/3 1/1	1-1.5	1-битные	Нет	1D
JBIG	1.5 раза	~1	1-битные	Нет	2D
Lossless JPEG	2 раза	~1	24-битн. сер.	Нет	2D
Рекурс. сжатие	2-20 раз	1.5	серые	Да	2D
JPEG	2-200 раз	~1	24-битн. сер.	Да	2D
Фрактальный	2-2000 раз	1000-10000	24-битн. сер.	Да	2D

В приведенной таблице видны  тенденции развития алгоритмов за последние годы:

 

1. ориентация на фотореалистичные изображения с 16 миллионами цветов (24 бита);
2. использование сжатия с потерями, возможность за счет потерь регулировать качество изображений;
3. использование избыточности изображений в двух измерениях;
4. появление существенно несимметричных алгоритмов;
5. увеличивающаяся степень сжатия изображений.

 

4. Сложности и методы их устранения

Ничто не гарантирует наличие свойства самоподобия у произвольного изображения, а даже если объект и является фрактальным, то надо узнать, каким образом выделить ту область (или области), на основе которых строится изображение. Несмотря на то, что группой Барнсли было создано программное обеспечение, реализующее эти алгоритмы (например, библиотеки фрактального сжатия используются в Microsoft Encarta), осталась проблема скорости сжатия. Достаточно эффективное решение не найдено до сих пор, а сам Майкл Барнсли продолжает упорно работать в выбранном направлении [2, 6]. 

Для нахождения соответствующих доменных блоков требуется полный перебор. Поскольку при этом переборе каждый раз должны сравниваться два массива, данная операция получается достаточно длительной. Сравнительно простым преобразованием её можно свести к операции скалярного произведения двух массивов, однако даже скалярное произведение считает сравнительно длительное время. [8]

Наиболее эффективными оказались  два направления исследований: метод  выделения особенностей и метод  классификации доменов. Первый из них, метод выделения особенностей, сокращает количество вычислений, необходимых для доменно-рангового сопоставления. Второй, классификация доменов, сокращает время поиска приемлемого доменно-рангового соответствия. Примеры показывают, что использование этих методов сокращает время кодирования от часов до секунд и, таким образом, делает возможным практическое применение фрактального кодирования. [9]

Как показал поиск литературы для написания реферата, сейчас этим вопросом активно не занимаются. На данный момент известно достаточно большое количество алгоритмов оптимизации перебора, возникающего при фрактальном сжатии, поскольку большинство статей, исследовавших алгоритм были посвящены этой проблеме, и во время активных исследований (1992-1996 года) выходило до 300 статей в год. [2]