Фрактальное сжатие изображений. Фрактальный алгоритм Фрактальный алгоритм

При векторном квантовании одновременно кодируется группа из N отсчетов цифрового сигнала (N- мерный вектор). В случае одномерного сигнала векторами могут быть группы по N последовательных отсчетов. В случае изображения векторами могут быть блоки из нескольких смежных по горизонтали и по вертикали элементов изображения. На рис. 5.54 представлена структурная схема системы передачи информации, в котором используется векторное квантование .

Смысл векторного квантования заключается в следующем. Множество всех встречающихся в сигнале N -мерных векторов разбиваются на L подмножеств так, что входящие в каждое подмножества векторы мало отличаются друг от друга. В каждом подмножестве выбирается один эталонный вектор, представляющий все векторы этого подмножества. Все эталонные векторы записываются в кодовую книгу и каждому из них присваивается определенное кодовое слово.

Входной цифровой сигнал x(n) поступает на вход кодера. Процедура кодирования заключается в том, что для каждого N-мерного вектора в кодовой книге находится наиболее близкий к нему эталонный вектор, код которого поступает на выход кодера. Таким образом, для каждой группы из N -отсчетов входного сигнала x(n) передается одно кодовое слово u(k).


В декодере в соответствии с принятым кодовым словом u(k) (штрих показывает, что сигнал пришел канал связи) из кодовой книги считывается эталонный вектор, преобразуемый в группу из N отсчетов выходного сигнала y(n) . Кодовая книга может изменяться в зависимости от свойств кодируемого сигнала.

Векторное квантование относится к методам сжатия с потерями, и так как реальные группы из N отсчетов входного сигнала X(n) в выходном сигнале y(n) заменяются эталонными N - мерными векторами. Одним из достоинств векторного квантования является простота декодера, в котором выполняется только операция считывания эталонного вектора из кодовой книги.

В то же время поиск в кодере эталонного вектора наиболее близкого к кодируемому требует большого объема вычислений. Наиболее близкий эталонный вектор считывается из кодовой книги, когда достигается минимальное значение квадратичной ошибки квантования E :

E= S(а j -b j) 2 ,

где а j - элементы входного вектора; b j – элементы эталонного вектора.

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

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


Однако большой объем вычислений при кодировании препятствует применению этих методов в системах цифрового телевидения .

Контрольные вопросы

1. В какой последовательности кодируются по стандарту JPEG блоки цветного изображения?

2. Почему квантование коэффициентов ДКП создает менее заметные искажения, чем кантование самого изображения?

3. Каким образом в стандарте JPEG осуществляется управление степенью сжатия?

4. В чем состоит сущность кодирования с переменной длиной кодовых слов?

5. Что означает термин “гибридное кодирование” применительно к стандартам MPEG-1, MPEG-2?

6. Зачем перед кодированием по MPEG-1, MPEG-2 выполняется перестановка кадров в GOP?

7. В чем различаются кадровый и полевой режимы кодирования в MPEG-1, MPEG-2?

8. Почему для B -кадров достигается наибольшая степень сжатия?

9. Каково назначение буферного ЗУ в кодере MPEG-2?

10. Что такое масштабируемость?

11. Что такое уровни и профили MPEG-2?

12. Как выделяются данные разных ТВ-программ из транспортного потока MPEG-2?

Фрактальный алгоритм

История фрактального сжатия

Рождение фрактальной геометрии обычно связывают с выходом в 1977 году книги Б. Мандельброта "Фрактальная геометрия природы". Одна из основных идей книги заключалась в том, что средствами традиционной геометрии (то есть используя линии и поверхности), чрезвычайно сложно представить природные объекты. Фрактальная геометрия задает их очень просто.

В 1981 году Джон Хатчинсон опубликовал статью "Фракталы и самоподобие", в которой была представлена теория построения фракталов с помощью системы итерируемых функций (IFS , Iterated Function System). Четыре года спустя появилась статья Майкла Барнсли и Стефана Демко, в которой приводилась уже достаточно стройная теория IFS. В 1987 году Барнсли основал Iterated Systems, компанию, основной деятельностью которой является создание новых алгоритмов и ПО с использованием фракталов. Всего через год, в 1988 году, он выпустил фундаментальный труд "Фракталы повсюду". Помимо описания IFS, в ней был получен результат, известный сейчас как Collage Theorem, который лежит в основе математического обоснования идеи фрактальной компрессии.

Первая статья об успехах Барнсли в области компрессии появилась в журнале BYTE в январе 1988 года. В ней не описывалось решение обратной задачи, но приводилось несколько изображений, сжатых с коэффициентом 1:10000, что было совершенно ошеломительно. Но практически сразу было отмечено, что несмотря на броские названия ("Темный лес", "Побережье Монтере", "Поле подсолнухов") изображения в действительности имели искусственную природу. Это, вызвало массу скептических замечаний, подогреваемых еще и заявлением Барнсли о том, что "среднее изображение требует для сжатия порядка 100 часов работы на мощной двухпроцессорной рабочей станции, причем с участием человека".

Отношение к новому методу изменилось в 1992 году, когда Арнауд Джеквин, один из сотрудников Барнсли, при защите диссертации описал практический алгоритм и опубликовал его. Этот алгоритм был крайне медленным и не претендовал на компрессию в 10000 раз (полноцветное 24-разрядное изображение с его помощью могло быть сжато без существенных потерь с коэффициентом 1:8 - 1:50); но его несомненным достоинством было то, что вмешательство человека удалось полностью исключить. Сегодня все известные программы фрактальной компрессии базируются на алгоритме Джеквина. В 1993 году вышел первый коммерческий продукт компании Iterated Systems. Ему было посвящено достаточно много публикаций, но о коммерческом успехе речь не шла, продукт был достаточно "сырой", компания не предпринимала никаких рекламных шагов, и приобрести программу было тяжело.

В 1994 году Ювал Фишер были предоставил во всеобщее пользование исходные тексты исследовательской программы, в которой использовалось разложение изображения в квадродерево и были реализованы алгоритмы оптимизации поиска. Позднее появилось еще несколько исследовательских проектов, которые в качестве начального варианта программы использовали программу Фишера. В июле 1995 года в Тронхейме (Швеция) состоялась первая школа-конференция, посвященная фрактальной компрессии.

Идея метода

Фрактальная архивация основана на том, что мы представляем изображение в более компактной форме – с помощью коэффициентов системы итерируемых функций (Iterated Function System – далее по тексту как IFS). Строго говоря, IFS представляет собой набор трехмерных аффинных преобразований , в нашем случае переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (х_координата, у_координата, яркость).

Наиболее наглядно этот процесс продемонстрировал Барнсли в своей книге "Fractal Image Compression". Там введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран:

  • Линзы могут проецировать часть изображения произвольной формы в любое другое место нового изображения.
  • Области, в которые проецируются изображения, не пересекаются.
  • Линза может менять яркость и уменьшать контрастность.
  • Линза может зеркально отражать и поворачивать свой фрагмент изображения.
  • Линза должна масштабировать (уменьшать) свой фрагмент изображения.

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

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

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


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

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

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

Математические основы фрактального сжатия

Определение. Преобразование w:R 2 –> R 2 , представимое в виде

где a, b, c, d, e, f, p, q, r, s, t, u действительные числа и (x y z) принадлежит R 3 называется трехмерным аффинным преобразованием.

Определение. Пусть f:X –> X – преобразование в пространстве Х. Точка x f принадлежащая X такая, что f(x f)=x f называется неподвижной точкой (аттрактором) преобразования.

Определение. Пусть f:X–>X в метрическом пространстве (Х, d) называется сжимающим, если существует число s: 0 <= s < 1, такое, что d(f(x),f(y)) <= s * d(x,y) длялюбых x,y принадлежащих X.

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

Теорема (О сжимающем преобразовании). Пусть f:X –> X в полном метрическом пространстве (Х, d). Тогда существует в точности одна неподвижная точка x f принадлежащая X этого преобразования, и для любой точки x принадлежащей X последовательность {f n (x): n=0,1,2…} сходится к x f .

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

Определение. Изображением называется функция S, определенная на единичном квадрате и принимающая значения от 0 до 1 или S(x,y) принадлежит для любых x,y принадлежащих .

Пусть трехмерное аффинное преобразование w f:R 3 –> R 3 , записано в виде

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

Определение. Конечная совокупность W сжимающих трехмерных аффинных преобразований w i , определенных на областях D i , таких, что w i (D i) = R i и пересечение R i с R j является пустым множеством, называется системой итерируемых функций (IFS).

Системе итерируемых функций однозначно сопоставляется неподвижная точка – изображение. Таким образом, процесс компрессии заключается в поиске коэффициентов системы, а процесс декомпрессии – в проведении итераций системы до стабилизации полученного изображения (неподвижной точки IFS). На практике бывает достаточно 7-16 итераций. Области R i в именуются ранговыми, а области D i – доменными.

Типовая схема фрактального сжатия

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

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

Первые три условия означают, что отображение w i будет сжимающим. А в силу четвёртого условия кодируемое изображение R и его образ W(R) будут похожи друг на друга. В идеале R = W(R). А это означает, что изображение R и будет являться неподвижной точкой W. Именно здесь используется подобие различных частей изображения. Как оказалось, практически все реальные изображения содержат такие похожие друг на друга, с точностью до аффинного преобразования , части.

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

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

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

Различия начинаются, если мы рассмотрим время, необходимое алгоритмам для архивации/разархивации. Так, фрактальный алгоритм сжимает в сотни и даже в тысячи раз дольше, чем JPEG . Распаковка изображения, наоборот, произойдет в 5-10 раз быстрее. Поэтому, если изображение будет сжато только один раз, а передано по сети и распаковано множество раз, то выгодней использовать фрактальный алгоритм.

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

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

Характеристики фрактального алгоритма

Коэффициенты компрессии: 2-2000 (Задается пользователем).

Класс изображений: Полноцветные 24 битные изображения или изображения в градациях серого без резких переходов цветов (фотографии). Желательно, чтобы области большей значимости (для восприятия) были более контрастными и резкими, а области меньшей значимости - неконтрастными и размытыми.

Симметричность: 100-100000.

Характерные особенности: Может свободно масштабировать изображение при разархивации, увеличивая его в 2-4 раза без появления "лестничного эффекта". При увеличении степени компрессии появляется "блочный" эффект на границах блоков в изображении.


Назад К cодержанию Вперёд

В радиотехнике и теории связи фракталы позволили разработать высокоэффек­тивные методы сжатия информации. В 1988 г. известный американский специалист в теории динамических систем и эргодической теории Барнсли (Barnsley) предло­жил некоторые идеи для сжатия и хранения графической информации. Он назвал свой метод фрактальным сжатием информации. Происхождение названия связано с тем, что геометрические образы, возникающие в этом методе, обычно имеют фрактальную природу в смысле Мандельброта.

Фрактальное сжатие основано на том, что изображение представляется в бо­лее компактной форме с помощью коэффициентов так называемой системы итерируемых функций (Iterated Function System - IFS ). Система итерирую­щих функций - это совокупность сжимающих аффинных преобразований. Как известно, аффинные преобразования - геометрические преобразования плоскости или пространства, включающие в себя масштабирование, поворот и параллельный перенос, при котором фигуры сохраняют свои свойства. В изображениях преобразованию подвергаются точки в трехмерном пространст­ве (координата X , координата Y , яркость). По существу IFS представляет со­бой систему из некоторого фиксированного класса функций, отображающих одно многомерное множество на другое. Аффинное преобразование считается сжимающим, если коэффициент масштабирования меньше единицы.

Наиболее наглядна процесс сжатия информации Барнсли продемонстри­ровал в своей книге «Fractal Image Compression» (Фрактальное сжатие изо­бражения). Там введено понятие Фотокопировальной Машины (рис. 2.69), состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. На линзы накладывается ряд специфических требований:

    линзы могут проецировать часть изображения произвольной формы в любое другое место нового изображения;

    области, в которые проецируются изображения, не пересекаются;

    линзы могут менять яркость и уменьшать контрастность;

    линзы могут зеркально отражать и поворачивать свой фрагмент изобра­жения;

Линзы должны уменьшать (масштабировать) свой фрагмент изображения.

Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. Одна итерация работы Машины заключается в том, что по исходному изо­бражению с помощью проектирования строится новое, после чего новое бе­рется в качестве исходного. В процессе итераций получается изображение, которое перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз, и не будет зависеть от исходной картинки. Это изобра­жение является аттрактором данной IFS. Соответствующая теория гарантиру­ет наличие ровно одного аттрактора для каждой IFS.

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

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

Рассмотрим фрактальный алгоритм, который преобразует изображение не­которым заданным способом. Например, этот способ предполагает уменьше­ние линейных размеров исходного изображения (например, рисунок «улыбающееся лицо») в два раза и тройное его копирование (рис. 2.70).

Пусть имеется три разных изображения: «улыбающееся лицо», буква А и салфетка Серпинского, показанных слева на рис. 2.71. Если процесс выбран­ного способа преобразования повторять к данным изображениям итеративно несколько раз, то возникающие из различных исходных изображений рисун­ки станут похожими друг на друга.

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

    оно не зависит от начального изображения, поскольку при достаточно большом числе итераций исходное изображение уменьшится до аттрактора (точки);

    оно определяется исключительно процедурой преобразования;

    последующие преобразования преобразуют его в самое себя;

    оно может иметь сколь угодно мелкие детали.

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

На практике достаточно большое количество преобразований можно описать с помощью матричного уравнения, определяющего линейное преобразование координат x и у:

где a i , b i , c i , d i , g i , и h i - параметры аффинного преобразования.

На рис. 2.72 показаны ряд процедур преобразования и их аттракторов.

Последний случай (рис. 2.72, в - правый крайний рисунок) относится к так называемому «папоротнику Барнсли». Это внешне сложное изображение полу­чено за счет четырех аффинных преобразований, каждое из которых имеет шесть параметров (см. уравнение (2.281)). С аналитической точки зрения тот же папоротник Барнсли создается с помощью IFS четырьмя аффинными преобра­зованиями (в нашей терминологии «линзами»). Каждое преобразование кодиру­ется буквально считанными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт.

Если для штрихового изображения папоротника Барнсли перемножить число преобразований (4), число параметров (6) и число бит под хранение каждого из параметров (например 32), то получим 4 х 6 х 32 = 768 бит - столько бит необ­ходимо для хранения способа получения этого изображения. В то же время изо­бражение папоротника (1 бит/пиксел) имеет разрешение 256 х 256 пиксел. Для прямого хранения такого изображения необходимо 65536 бит, т. е. рассматри­ваемая схема позволяет «сжать» изображение примерно в 85 раз. Такое опреде­ление коэффициента сжатия в некоторой мере условно. Дело в том, что для хра­нения алгоритма преобразования требуется определенное, заранее известное, количество бит. Но этот алгоритм позволяет создать изображение любого раз­мера с достаточно мелкими деталями, для хранения которого требуется другое (возможно, большее) число друг на друга бит. Соответственно размеру изображения будет меняться и коэффициент сжатия. Возникает вопрос: можно ли для любой детали изображения подобрать деталь, которая после некоторых преобразований станет достаточно похожей на исходную?

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

где х, у - координаты пикселов.

Пусть z имеет 256 фиксированных уровней. Само аффинное преобразова­ние /-го блока полутонового изображения имеет вид:

где a i , b i , c i , d i , g i , и h i - параметры аффинного преоб­разования; s i , r i - коэффициенты преобразования контраста и яркости блока.

Теперь исходное изображение необходимо разбить на блоки (домены), для которых будут подбираться подобные блоки (ранговые области). Вычисление оп­тимальных коэффициентов преобразования контраста и яркости квадратов путем минимизации среднеквад­ратичной разности яркостей пикселов домена и кан­дидата в ранговую область может быть произведено по разным формулам, приведенным в специальной литературе.

Итак, понятие фрактала привело к развитию новойматематической модели, дающей единое описание форм, присущих многим природным явлениям. Оказывается, природа устроена так, что именно фрак­тальные модели хорошо описывают многие реальные объекты, структура кото­рых не отражается традиционными моделями. Этим объясняется современная популярность фрактального подхода к анализу различных объектов и процессов в физике, радиотехнике, системах передачи информации и др. В частности, сей­час большое внимание специалистов уделяется разработке широкополосных фрактальных антенн (рис. 2.73).

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

Фракталы — удивительные математические объекты, подкупающие своей простотой и богатыми возможностями по построению объектов сложной природы при помощи всего лишь нескольких коэффициентов и простой итеративной схемы.
Именно эти возможности и позволяют использовать их для сжатия изображений, особенно для фотографий природы и прочих сложных самоподобных изображений.
В этой статье я постараюсь коротко дать ответ на простой вопрос: «Как же это делается?».

Для начала все-таки придется немного углубиться в математику и ввести несколько определений.
Нам пригодятся следующие:

  • Метрика — функция, заданная на пространстве, возвращающая расстояние между двумя точками этого пространства. Например, привычная нам Эвклидова метрика. Если на пространстве задана метрика, оно называется метрическим. Метрика должна удовлетворять определенным условиям, но не будем углубляться.
  • Сжимающее отображение (преобразование) — функция на метрическом пространстве, равномерно уменьшающая расстояние между двумя точками пространства. Например, y=0.5x.
Сжимающие отображения обладают важным свойством. Если взять любую точку и начать итеративно применять к ней одно и то же сжимающее отображение: f(f(f...f(x))), то результатом будет всегда одна и та же точка. Чем больше раз применим, тем точнее найдем эту точку. Называется она неподвижной точкой и для каждого сжимающего отображения она существует, причем только одна.

Несколько аффинных сжимающих отображений образуют систему итерированных функций (СИФ). По сути, СИФ — это множительная машина. Она принимает исходное изображение, искажает его, перемещает, и так несколько раз.
Например, вот так при помощи СИФ из трех функций строится треугольник Серпинского:

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

Если функции, входящие в СИФ,— сжимающие, то сама СИФ тоже имеет неподвижную точку. Вот только эта «точка» будет уже не привычной нам точкой в N-мерном пространстве, а множеством таких точек, то есть изображением. Оно называется аттрактором СИФ. Для СИФ, приведенной выше, аттрактором будет треугольник Серпинского.

Тут мы переходим на следующий уровень — в пространство изображений. В этом пространстве:

  • Точка пространства — это изображение.
  • Расстояние между точками показывает, насколько похожи изображения между собой, насколько «близки» (естественно, если его задать соответствующим образом).
  • Сжимающее отображение делает два любых изображения более похожими (в смысле заданной метрики).

Имея СИФ, найти аттрактор просто. Во всяком случае, имея под рукой компьютер. Можно взять абсолютно любое начальное изображение и начать применять к нему СИФ. Пример с тем же треугольником, но уже построенным из квадрата:

Получается, что для построения довольно сложной фигуры нам потребовалось 18 коэффициентов. Выигрыш, как говорится, налицо.
Вот если бы мы умели решать обратную задачу — имея аттрактор, строить СИФ… Тогда достаточно взять аттрактор-изображение, похожее на фотографию вашей кошки и можно довольно выгодно его закодировать.

Вот здесь, собственно, начинаются проблемы. Произвольные изображения, в отличие от фракталов, не самоподобны, так что так просто эта задача не решается. Как это сделать придумал в 1992 году Арнольд Жакин, в то время — аспирант Майкла Барнсли, который считается отцом фрактального сжатия.

Самоподобие нам нужно обязательно — иначе ограниченные в своих возможностях аффинные преобразования не смогут правдоподобно приблизить изображения. А если его нет между частью и целым, то можно поискать между частью и частью. Примерно так, видимо, рассуждал и Жакин.

Упрощенная схема кодирования выглядит так:

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

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

Получение оптимального преобразования — отдельная тема, однако большого труда оно не составляет. Но другой недостаток схемы виден невооруженным глазом. Можете сами подсчитать, сколько доменных блоков размером 32×32 содержит двухмегапиксельное изображение. Полный их перебор для каждого рангового блока и есть основная проблема такого вида сжатия — кодирование занимает очень много времени. Разумеется, с этим борются при помощи различных ухищрений, вроде сужения области поиска или предварительной классификации доменных блоков. С различным ущербом для качества.

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

Пожалуй, для введения информации достаточно. Интересующиеся могут почитать соответствующие статьи в

В декабре 1992 года, перед самым Рождеством, компания Microsoft выпустила свой новый компакт-диск Microsoft Encarta. С тех пор эта мультимедиа-энциклопедия, содержащая информацию о животных, цветах, деревьях и живописных местах, не покидает списки наиболее популярных энциклопедий на компакт-дисках. В недавнем опросе Microsoft Encarta опять заняла первое место, опередив ближайшего конкурента - Комптоновскую мультимедиа-энциклопедию. Причина подобной популярности кроется в удобстве использования, высоком качестве статей и, главное, в большом количестве материалов. На диск записано 7 часов звука, 100 анимационных роликов, примерно 800 масштабируемых карт, а также 7000.качественных фотографий. И все это - на одном диске! Напомним, что обычный компакт-диск в 650 Мбайт без использования компрессии может содержать либо 56 минут качественного звука, либо 1 час видео разрешения с разрешением 320х200 в формате MPEG-1, либо 700 полноцветных изображений размером 640х480. Чтобы разместить больше информации, необходимы достаточно эффективные алгоритмы архивации. Мы не будем останавливаться на методах архивации для видео и звука, рассмотрим историю фрактального сжатия графической информации. Рождение фрактальной геометрии обычно связывают с выходом в 1977 году книги Б. Мандельброта "Фрактальная геометрия природы". Одна из основных идей книги заключалась в том, что средствами традиционной геометрии (то есть, используя линии и поверхности), чрезвычайно сложно представить природные объекты. Фрактальная геометрия задает их очень просто. В 1981 году Джон Хатчинсон опубликовал статью "Фракталы и самоподобие", в которой была представлена теория построения фракталов с помощью системы итерируемых функций (IFS, Iterated Function System). Спустя четыре года появилась статья Майкла Барнсли и Стефана Демко, в которой приводилась уже достаточно стройная теория IFS. В 1987 году Барнсли основал Iterated Systems, компанию, основной деятельностью которой является создание новых алгоритмов и ПО с использованием фракталов. Всего через год, в 1988 году, он выпустил фундаментальный труд "Фракталы повсюду". Помимо описания IFS, в ней был получен результат, известный сейчас как Collage Theorem, который лежит в основе математического обоснования идеи фрактальной компрессии. Если построение изображений с помощью фрактальной математики можно назвать прямой задачей, то построение по изображению IFS - это обратная задача. Довольно долго она считалась неразрешимой. Первая статья об успехах Барнсли в области компрессии появилась в журнале BYTE в январе 1988 года. В ней не описывалось решение обратной задачи, но приводилось несколько изображений, сжатых с коэффициентом 1:10000, что было совершенно ошеломительно. Но практически сразу было отмечено, что несмотря на броские названия ("Темный лес", "Побережье Монтере", "Поле подсолнухов") изображения в действительности имели искусственную природу. Это, вызвало массу скептических замечаний, подогреваемых еще и заявлением Барнсли о том, что "среднее изображение требует для сжатия порядка 100 часов работы на мощной двухпроцессорной рабочей станции, причем с участием человека". Когда в 1991 году впервые была опубликована информация о возможностях фрактального сжатия, она наделала много шуму. Майкл Барнсли, один из разработчиков алгоритма, утверждал, что разработан способ нахождения коэффициентов фрактала, сколь угодно близкого к исходной картинке. Фракталы, эти красивые образы динамических систем, ранее использовались в машинной графике в основном для построения изображений неба, листьев, гор, травы. Красивое и, что важнее, достоверно имитирующее природный объект изображение могло быть задано всего несколькими коэффициентами. Неудивительно, что идея использовать фракталы при сжатии возникала и раньше, но считалось практически невозможным построить соответствующий алгоритм, который подбирал бы коэффициенты за приемлемое время. Итак, в 1991 году такой алгоритм был найден. Кроме того, в дальнейших его статьях декларировался ряд уникальных возможностей новой технологии. Так, фрактальный архиватор позволяет, например, при распаковке произвольно менять разрешение (размеры) изображения без появления эффекта зернистости. Более того, он распаковывает гораздо быстрее, чем ближайший конкурент, JPEG, и не только статическую графику, но и видео. В качестве примера приводилась программа, показывающая на машине с процессором i386/33 МГц цветной видеофильм с частотой 20 кадров в секунду без всякой аппаратной поддержки. В отличие от JPEG, в алгоритм изначально заложена возможность управлять степенью потерь на участках с максимальными потерями качества. Коэффициент сжатия изображений в целом примерно как у JPEG, но на некоторых реальных картинках достигалось сжатие в 10000 (!) раз. В 1992 году Арнауд Джеквин, один из сотрудников Барнсли, при защите диссертации описал практический алгоритм и опубликовал его. Этот алгоритм был крайне медленным и не претендовал на компрессию в 10000 раз (полноцветное 24-разрядное изображение с его помощью могло быть сжато без существенных потерь с коэффициентом 1:8 - 1:50); но его несомненным достоинством было то, что вмешательство человека удалось полностью исключить. Сегодня все известные программы фрактальной компрессии базируются на алгоритме Джеквина. В 1993 году вышел первый коммерческий продукт компании Iterated Systems. Ему было посвящено достаточно много публикаций, но о коммерческом успехе речь не шла, продукт был достаточно "сырой", компания не предпринимала никаких рекламных шагов, и приобрести программу было тяжело. В 1994 году Ювал Фишер были предоставил во всеобщее пользование исходные тексты исследовательской программы, в которой использовалось разложение изображения в квадродерево и были реализованы алгоритмы оптимизации поиска. Позднее появилось еще несколько исследовательских проектов, которые в качестве начального варианта программы использовали программу Фишера. В июле 1995 года в Тронхейме (Швеция) состоялась первая школа-конференция, посвященная фрактальной компрессии. Таким образом, многие важные события в области фрактальной компрессии произошли за последние три года: алгоритм только-только начинает развиваться. Как уже отмечалось, недостатком алгоритма фрактального сжатия является большое время кодирования. Решение этой проблемы в 1999 году предложил Д.С.Ватолин в своей статье "Использование ДКП для ускорения фрактального сжатия изображения". В работе рассматривается применение дискретного косинусоидального преобразования (ДКП) для ускорения работы фрактального алгоритма сжатия изображений. ДКП используется для разбиения всего множества блоков в изображении на 256 классов, что позволяет достичь почти 100-кратного ускорения работы алгоритма при приемлемых потерях в качестве изображения. В отличие от других работ, в данной статье детально описан разработанный алгоритм и полученные результаты.

Примерка © 2024 Edu35ru - Основы работы на персональном компьютере