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

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

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

Рождение фрактальной геометрии обычно связывают с выходом в 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одержанию

Вперёд

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

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

В начале 80-х годов Майкл Барнсли выдвинул идею получения заранее заданного изображения как аттрактора хаотического процесса. Барнсли пытался ответить на вопрос: возможно ли для данного изображения построить хаотическую систему, которая будет являться для него странным аттрактором. Он использовал систему итерируемых функций (Iterated Function System - IFS).

Наиболее распространённым примером фрактального изображения, сгенерированного с помощью IFS является изображение папоротника (рис.1.10), использованное для создания данного изображения, состоит из 4-х аффинных преобразований. Каждое преобразование кодируется считанными байтами, хотя исходное изображение может быть любого размера. Таким образом, можно заключить, что фрактальная компрессия – это поиск самоподобных областей и определение для них параметров аффинных преобразований.

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

Рис. 1.10. Изображение папоротника, сгенерированного с помощью IFS

В основе фрактального сжатия лежат несколько основных определений и теорем. Рассмотрим их вкратце.

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

f: X 1  X 2 , если оно переводит пространство Х 1 в пространство Х 2 .

Преобразование f: X 1  X 2 в метрическом пространстве (X,d) называется сжимающим, если существует константа s , 0s<1 такая что:

d(f(x 1),f(x 2))  sd(x 1 ,x 2),

где d(x 1 ,x 2) – расстояние от точки х 1 до точки х 2 в пространстве X.

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

Рис. 1.11. Сжимающее отображение для точек в пространстве R 2

На рисунке 1.11 показан пример сжимающего отображения (R 2 ,d 2), примененного к множеству точек в R 2 . Здесь данное преобразование применялось более одного раза: сначала f(x) вычислялось для точки х, а затем преобразование f применялось к результату преобразования: f(f(x)). Такое последовательное, многократное применение преобразования называют итерациями и обозначают как: f on , т.е. f(f(…f(x)…)), где f применяется n раз.

Теорема о сжимающих отображениях : пусть f: X 1 X 2 сжимающее отображение на полном метрическом пространстве. Тогда f имеет всего одну и только одну неподвижную точку x f X и для любого х из Х последовательность { f on (x):n=1,2,…} сходиться к x f . Эта теорема лежит в основе всех подходов к фрактальному сжатию изображении.

Пусть {w 1 ,w 2 ,…,w n } конечный набор сжимающих отображений в пространстве (X,d) с коэффициентами сжатия s 1 ,s 2 ,…,s n , 0s<1. Определим отображение W, воздействующее на компактные множества точек B из Х:

W(B)=w 1 (B) w 2 (B)… w n (B)=U N n=1 (B) (1.21)

Таким образом, W осуществляет отображение в данном пространстве с коэффициентов сжатия s, где s=max{s 1 ,s 2 ,…,s n }.

Система итерирующих функций (IFS) состоит из полного метрического пространтсва (X,d) и конечного множества сжимающих отображений w n: XX c коэффициентами сжатия s n . Таким образом, IFS можно обозначить следующим образом: {X,w n:n=1,2,..,N}, или если рассматривать пространство точек в R 2 , то просто {w n }.

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

Пусть есть двоичное изображение LR 2 и пусть есть сжимающие отображения, такие что: U N n =1 w n (L)

Покрывают L почти точно. Можно считать такое w n (L) уменьшенной копией L. Тогда теорема коллажа утверждает, что аттрактор А (аттрактором IFS называется изображение, которое является единственной неподвижной точкой IFS) системы {w n } близок к L. «Коллажом» является набор областей wn(L).

Так как аттрактор А – это результат бесконечного числа итераций IFS, то он является по своей сути фракталом.

Рис. 1.12. Иллюстрация теоремы коллажа.

(а) исходное изображение и четыре фрагмента изображения;

(б) изображение-аттрактор

Чтобы на практике применить теорему коллажа, необходимо выбрать преобразования, которые будут являться сжимающими отображениями. Одним из таких преобразований являются аффинные преобразования: T: R 2 R 2:

(1.23)

где a, b, c, d, e, f R. Аффинные преобразования могут осуществлять поворот, перемещение и масштабирование.

На рисунке 1.13 показано действие аффинного преобразования на множество точек вR 2 .

Рис. 1.13. Воздействие аффинного преобразования на точки в пространстве R 2

Чтобы создать IFS изображение – нужно найти хотя бы некоторое приблизительное самоподобие в изображении. Затем нужно выделить точки и преобразование IFS для каждой из фигур подобия на изображении. Когда точки и преобразования для IFS определены, то вычисляются коэффициенты аффинного преобразования, используя систему уравнений, основанную на выражении1 (1.23).

Существует два алгоритма построения изображения-аттрактора с помощью IFS. Один из них это прямое применение теоремы о сжимающих отображениях, а другой – применение так называемой «игры хаоса».

Детерминированный алгоритм для построения изображения являющегося аттрактором IFS, к любому начальному изображению B применяет теорему о сжимающих отображениях. Алгоритм строит последовательность изображений A n , многократно применяя IFS отображение W={w 1 ,w 2 ,…,w n }:

A n =W on (B) (1.24)

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

Вероятностный алгоритм связывает с каждым аффинным преобразованием w i в IFS вероятность p i . Эти вероятности определяют, насколько плотно каждая часть изображения-аттрактора покрыта точками. Вероятностный алгоритм создаёт изображение - аттракторы высокого качества быстрее, чем детерминированный алгоритм. Это происходит не только из-за того, что вероятностный алгоритм на каждом шаге итерации выполняет меньшую работу, но и сама выполненная работа даёт лучший результат.

Рис. 1.14. Детерминированный алгоритм, применённый к IFS папоротника.

Вид изображения A n после: a)2-х, b)3-х, c)10-и, d)30-и итераций.

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

Рис. 1.15. Отображение доменных блоков в ранговые

при фрактальном сжатии изображения

Базовый алгоритм фрактального кодирования изображения выполняется следующим образом (Рис 1.15):

1. Изображение f разбивается на не перекрывающиеся ранговые блоки {R i }. В самом простом случае блоки могут представлять собой прямоугольники, но могут быть и другие формы.

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

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

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

Блок-схема такого алгоритма представлена на рис.1.16.

В настоящее время известны следующие разновидности такого алгоритма .

Алгоритм Фишера. Идея алгоритма заключается в том, чтобы некоторым образом классифицировать D-блоки и R-блоки, а поиск близкого D-блока производить в том же классе, к которому относится ранговая область. Делается это следующим образом .

Исходные блоки разбиваются на четыре части. Для каждой из частей подсчитывается среднее значение и дисперсияпикселей. Далее блоки классифицируются по следующему принципу. Определим три базовых типа блоков

тип 1:
,

тип 2:
,

тип 3:
.

Понятно, что любой блок при помощи соответствующего аффинного преобразования квадрата в квадрат можно привести к виду, соответствующему одному из указанных типов. После того, как мы зафиксировали три основных класса, блоки классифицируются по дисперсии. Таким образом, в каждом из трех классов появляются 24 подкласса, итого 72 класса. Поиск близкого к R-блоку D-блока производится перебором в соответствующем классе.

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

При использовании ГА для поиска оптимальных решений каждый элемент xX пространства оптимизации должен быть представлен как векторb B из N символов двоичного алфавита A = {0,1}, где B = A N . Необходимо также, чтобы пространство оптимизации X состояло из конечного числа элементов.

Популяцией П = (χ 1 , χ 2 ,…, χM) численности M считается вектор пространства B M , координаты которого называются генотипами особей данной популяции.

Шагом ГА является переход от текущего поколения к следующему, т.е. получение новой популяции
из
. В построении очередной особи новой популяции участвуют операторы кроссинговера (скрещивания), мутации и случайный оператор отбора,Select : B M
{1,…,M} действие которого состоит в выборе номера особи родителя при порождении очередного потомка.

Для определения ГА необходимо задать оператор кроссинговера Cross : BB
BB и оператор мутацииMut : B
B.

Действие кроссинговера
заключается в выборе случайным образом некоторой позицииj , равномерно распределенной от1 до N-1 , после чего результат формируется в виде

Влияние кроссинговера регулируют с помощью вероятности
срабатывания этого оператора (в противном случае все остается без изменений).

Рис. 1.16. Блок схема основных шагов фрактального кодирования изображения

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

Целевая функция исходной задачи, заменяется в ГА на неотрицательную функцию пригодности генотипа
, где
B.

Процесс работы алгоритма представляет собой последовательную смену поколений, на каждом шаге которой популяция
наполняется парами потомков от особей популяции
по формуле

где
- особи с наименьшей пригодностью популяции
. То есть индивиды извлекаются попарно из
и после кроссинговера и мутации помещаются в
. Изменение вероятностей мутации и кроссинговера позволяет регулировать работу ГА и настраивать его на конкретные задачи.

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

где в нижней части под знаком суммы – евклидово расстояние между исходным и преобразованным блоком. Данная функция удовлетворяет требования ГА (неотрицательна) и адекватна для оператора рулеточной селекции, при которой каждый индивид
популяции t оказывается родителем при формировании очередной особи
популяции  t+1 с вероятностью

.

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

Оператор мутации для данного алгоритма – стандартный, а оператор кроссинговера был модифицирован следующим образом:

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

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

Алгоритм 1.

Алгоритм 2.

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

Создается два изображения одинакового размера А и Б. Размер изображений может быть не равен размеру исходного изображения. Начальный рисунок областей А и Б не имеет значения. Это могут быть случайные данные.

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

Данные из области Б преобразуются в область А. Этот шаг идентичен предыдущему, только изображения А и Б поменялись местами, т.е. теперь область А делится на блоки и ранговые области изображения Б отображаются на эти блоки.

Процедуры 2 и 3 повторяются до тех пор, пока изображения А и Б не станут неразличимыми.

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

К достоинствам фрактального метода можно отнести:

Высокие коэффициенты сжатия.

Высокую скорость обратного преобразования.

Возможность дальнейшего структурного анализа изображения .

При этом фрактальный метод обладает следующими недостатками:

Зависимостью результатов работы метода от принципов отбора базовых элементов и доменов.

Коэффициент сжатия зависит от повторяемости базовых элементов.

Алгоритм ориентирован на полноцветные изображения и изображения в градациях серого цвета. Фрактальное сжатие реализовано в формате FIF.

В настоящее время существует достаточно много алгоритмов сжатия изображений. Основой любых методов сжатия данных является использование естественной избыточности исходной информации. Сжатие изображений осуществляется либо в пространственной либо в частотной областях изображения. Наиболее яркими примерами пространственного сжатия изображений являются алгоритмы PCX, GIF, а частотного сжатия - JPEG.

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

В подобных алгоритмах можно выделить три основных шага:

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

Выбор наиболее значимых частотных коэффициентов.

Вторичное сжатие выбранных коэффициентов, например арифметическим или статистическим алгоритмом сжатия.

BC/NW 2008, №1 (12): 4

BC/NW 2008, №2 (13): 11 .1

ИССЛЕДОВАНИЕ СПОСОБОВ УСКОРЕНИЯ МЕТОДА ФРАКТАЛЬНОГО СЖАТИЯ ИЗОБРАЖЕНИЙ

Калязин Н.А., Гольцов А.Г.

(Москва, Московский энергетический институт(технический университет), Россия)

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

Рассматриваемый метод имеет ряд преимуществ, среди которых:

- потенциально высокая степень сжатия,

- малое время распаковки,

- возможность восстанавливать лишь часть изображения,

- возможность восстанавливать изображение произвольного размера,

- широкие возможности в выборе параметров сжатия.

Метод ярко выраженно асимметричный. Это означает, что время сжатия существенно больше времени распаковки. Коэффициент симметричности метода (отношение времени сжатия ко времени распаковки) может достигать 1000-10000 . Таким образом, задача ускорения работы метода фрактального сжатия весьма актуальна.

Рассмотрим принципы, лежащие в основе метода.

Ключевым понятием метода является система итерируемых функций (IFS , Iterated Function System ), возможность применения которых к проблеме сжатия изображений впервые была исследована Майклом Барнсли .

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

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

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

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

- линза может менять яркость и уменьшать контрастность,

- линза может зеркально отражать и поворачивать свой фрагмент изображения,

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

Рис.1. Машина Барнсли

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

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

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

Рис. 2. «Треугольник Серпинского»

Рис.3. «Папоротник Барнсли»

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

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

Рис. 4. Самоподобные области в изображениях

,(1)

где a , b , c , d , e , f – действительные числа и , называется двумерным аффинным преобразованием.

Преобразование , представимое в виде

,(2)

где a , b , c , d , e , f , q , r , s , t , u – действительные числа и , называется трехмерным аффинным преобразованием.

Пусть - преобразование в пространстве X . Точка , такая что , называется неподвижной точкой (аттрактором преобразования).

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

.(3)

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

Пусть - сжимающее преобразование в полном метрическом пространстве ( X , d ). Тогда существует в точности одна неподвижная точка этого преобразования и для любой точки последовательность сходится к .

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

Пусть трехмерное аффинное преобразование записано в виде

(4)

и определено на компактном множестве декартова квадрата . Тогда оно переведет часть поверхности S в область , расположенную со сдвигом ( e , f ) и поворотом, заданным матрицей

.(5)

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

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

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

В дальнейшем области будут именоваться блоками, а области - доменными (рис. 5).

Рис. 5. Перевод доменного блока в ранговый

Проиллюстрируем итерационный процесс восстановления ранее сжатого изображения (рис. 6).

Рис. 6. Исходное изображение

На каждой итерации производится применение IFS к текущему изображению. На рис. 7. показаны изображения, соответствующие каждой из 10-ти первых итераций (включая 0-ю).

Рис. 7. Процесс восстановления изображения

Для оценки качества восстановленного изображения применяется количественная оценка искажений, называемая пиковым соотношением сигнал/шум (PSNR – peak signal - to - noise ratio ) . Она рассчитывается по следующим формулам:

(6)

(7)

где и - количества столбов и строк, M – максимальное значение яркости пикселя, - пиксельное значение исходного изображения в i -ой строке и j -м столбце, а - пиксельное значение декодированного изображения, rms – погрешность, вычисленная по методу наименьших квадратов.

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

Опишем более подробно последовательность действий, выполняемых при сжатии изображения.

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

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

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

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

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

1. Все блоки являются квадратами со сторонами, параллельными сторонам изображения. Таким образом, изображение равномерной сеткой разбивается на набор ранговых блоков (рис. 8а).

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

3. Доменные блоки берутся «через точку» и по вертикали, и по горизонтали (рис. 8б).

4. При переводе доменного блока в ранговый поворот квадрата возможен только на 0, 90, 180 и 270 градусов. Также допускается зеркальное отражение. Общее число возможных преобразований (считая пустое) – 8.

Рис. 8. Принцип разбиения изображения на ранговые (а) и доменные блоки (б)

Степень подобия рангового и доменного блоков я вычислял при помощи следующей формулы:

,(8)

где r и d – соответственно значения яркостей пикселей рангового и доменного блоков, M – математическое ожидание значений яркостей соответствующего блока.

Эта формула основана на расчете коэффициента корреляции.

При восстановлении исходного изображения была использована формула

,(9)

где r – значение блока восстанавливаемого изображения, d – значение блока преобразовываемого изображения, p – изменение контраста блока, q – сдвиг по яркости блока.

Чтобы найти коэффициент p , я использовал квадратный корень из отношения дисперсий рангового и доменного блоков:

,(10)

где D – дисперсия значений яркости пикселей соответствующего блока; для тех доменных блоков, у которых msr > 0, и формулу

(11)

для тех доменных блоков, у которых msr < 0.

Чтобы найти коэффициент q , я использовал формулу:

.(12)

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

Предположим, что n x m - размер исходного изображения в пикселях, rsz – сторона рангового блока.

Тогда количество ранговых блоков в изображении будет

,(13)

а доменных (помня, что сторона доменного блока всегда вдвое больше стороны рангового)

.(14)

Таким образом, необходимо произвести rnum x dnum поблочных сопоставлений, что уже для изображения размером 512 x 512 и стороной рангового блока 8 пикселей составляет 251 920 384. Не стоит забывать, что в рассматриваемом нами алгоритме в каждом таком сопоставлении необходимо организовать цикл по всем пикселям блока для расчета математического ожидания и дисперсии. Более того, время, затрачиваемое на сжатие изображения в градациях серого, в простейшем случае утраивается, если речь идет о цветном изображений (так как для представления информации о яркости и цвете пикселя требуется как минимум три составляющих).

Теперь очевидно, почему множество исследований направлено на ускорение метода фрактального сжатия.

Существует два основных направления таких исследований :

Сокращение числапоблочных сопоставлений,

Ускорение сопоставлений путем повышений производительности вычислений.

К первому направлению относятся методы:

Выделение особенностей доменных блоков,

Классификация доменов.

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

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

Основываясь на данной предпосылке, я попытался написать параллельную программу на языке Си с использованием библиотеки MPI (Message Passing Interface ). Для эксперимента использовался вычислительный кластер МЭИ, имеющий в своем составе 16 узлов, каждый из которых состоит из двух двухъядерных процессоров AMD Opteron x86_64 , 2.2 ГГц . Пиковая производительность кластера составляет 281.6 GFlop/s.

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

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

На рис. 9 представлены зависимости времени сжатия изображения от числа параллельных процессов (рис. 9а) и коэффициента ускорения от числа параллельных процессов (рис. 9б) для изображения с разрешением 256 x 256 пикселей. Из диаграммы на рис. 9а следует, что характер зависимости времени сжатия изображения от числа параллельных процессов не меняется при изменении значения стороны рангового блока. Из диаграммы на рис. 9б следует, коэффициент ускорения не зависит от значения стороны рангового блока и численно весьма близок числу параллельных процессов. Последнее наблюдение подтверждает тезис о том, что метод фрактального сжатия хорошо поддается распараллеливанию.

Рис. 9. Зависимости времени сжатия изображения от числа параллельных процессов (а) и коэффициента ускорения от числа параллельных процессов (б) для изображения с разрешением 256 x 256 пикселей. Линии на каждой из диаграмм соответствуют различным значениям стороны рангового блока

На рис. 10 представлены зависимости времени сжатия изображения от числа параллельных процессов (рис. 10а) и коэффициента ускорения от числа параллельных процессов (рис. 10б) при стороне рангового блока равной 4 пикселя. Из диаграммы на рис. 10а следует, что характер зависимости времени сжатия от числа процессов не меняется при изменении разрешения сжимаемого изображения. Из диаграммы на рис. 10б следует, что коэффициент ускорения не меняется и от разрешения сжимаемого изображения. Это говорит о том, что фрактальный метод сжатия одинаково хорошо распараллеливается для изображений всех размеров.

Рис. 10. Зависимости времени сжатия изображения от числа параллельных процессов (а) и коэффициента ускорения от числа параллельных процессов (б) при стороне рангового блока равной 4 пикселя. Линии на каждой из диаграмм соответствуют разрешениям исходного изображения

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

ЛИТЕРАТУРА

1. Ватолин Д. С. Тенденции развития алгоритмов сжатия статических растровых изображений // Открытые системы сегодня. - 1995. - № 8 (29). – с. 25–30.

2. Barnsley Michael F. Fractal Image Compression, AK Peters, Ltd., 1993.

3. Barnsley Michael F. Fractals Everywhere, second edition, Academic Press, San Diego , 1993.

4. Jacquin A. Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations // IEEE Transactions on Image Processing. 1992. Vol . 1, N 1. P . 18–30.

5. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. – М.: ДИАЛОГ-МИФИ, 2003. – 384 с.

6. Уэльстид С. Фракталы и вейвлеты для сжатия изображений в действии: Учебное пособие. – М.: Издательство Триумф, 2003, - 320 с.

7. Информационно-аналитический центр parallel . ru , “Кластерные установки России и СНГ”,http://parallel.ru/russia/russian_clusters.html.

При векторном квантовании одновременно кодируется группа из 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?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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