≡× МЕНЮ

• Проблемы 
• Сетевое 
• Обзоры
• Интернет
• Windows 7

Оценка сжатия изображения фрактальным методом. Фрактальный алгоритм. Черно – белые изображения

В радиотехнике и теории связи фракталы позволили разработать высокоэффек­тивные методы сжатия информации. В 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).

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

В декабре 1992 года, перед самым Рождеством, компания Microsoft выпустила свой новый компакт-диск Microsoft Encarta. С тех пор эта мультимедиа-энциклопедия, содержащая информацию о животных, цветах, деревьях и живописных местах, не покидает списки наиболее популярных энциклопедий на компакт-дисках. В недавнем опросе Microsoft Encarta опять заняла первое место, опередив ближайшего конкурента - Комптоновскую мультимедиа-энциклопедию. Причина подобной популярности кроется в удобстве использования, высоком качестве статей и, главное, в большом количестве материалов. На диск записано 7 часов звука, 100 анимационных роликов, примерно 800 масштабируемых карт, а также 7000 качественных фотографий. И все это - на одном диске! Напомним, что обычный компакт-диск в 650 Мбайт без использования компрессии может содержать либо 56 минут качественного звука, либо 1 час видео разрешения с разрешением 320х200 в формате MPEG-1, либо 700 полноцветных изображений размером 640х480.

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

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

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

Итак, в 1991 году такой алгоритм был найден. Кроме того, в дальнейших его статьях декларировался ряд уникальных возможностей новой технологии. Так, фрактальный архиватор позволяет, например, при распаковке произвольно менять разрешение (размеры) изображения без появления эффекта зернистости. Более того, он распаковывает гораздо быстрее, чем ближайший конкурент JPEG , и не только статическую графику, но и видео. В качестве примера приводилась программа, показывающая на машине с процессором i386/33 МГц цветной видеофильм с частотой 20 кадров в секунду без всякой аппаратной поддержки. В отличие от JPEG, в алгоритм изначально заложена возможность управлять степенью потерь на участках с максимальными потерями качества. Коэффициент сжатия изображений в целом примерно как у JPEG, но на некоторых реальных картинках достигалось сжатие в 10000 (!) раз.

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

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

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

Четыре года спустя появилась статья Майкла Барнсли и Стефана Демко, в которой приводилась уже достаточно стройная теория IFS. В 1987 году Барнсли основал Iterated Systems, компанию, основной деятельностью которой является создание новых алгоритмов и ПО с использованием фракталов.

Всего через год, в 1988 году, он выпустил фундаментальный труд "Фракталы повсюду". Помимо описания IFS, в ней был получен результат, известный сейчас как Collage Theorem, который лежит в основе математического обоснования идеи фрактальной компрессии.

Если построение изображений с помощью фрактальной математики можно назвать прямой задачей, то построение по изображению IFS - это обратная задача. Довольно долго она считалась неразрешимой, однако Барнсли, используя Collage Theorem, построил соответствующий алгоритм. (В 1990 и 1991 годах эта идея была защищена патентами.) Если коэффициенты занимают меньше места, чем исходное изображение, то алгоритм является алгоритмом архивации.

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

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

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

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

Идея

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

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

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

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

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

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

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

Оценка потерь и способы их регулирования

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

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

Возможности масштабирования

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

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

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

Масштабирование - уникальная особенность, присущая фрактальной компрессии. Со временем ее, видимо, будут активно использовать как в специальных алгоритмах масштабирования, так и во многих приложениях. Действительно, этого требует концепция "приложение в окне". Было бы неплохо, если бы изображение, показываемое в окне 100х100, хорошо смотрелось при увеличении на полный экран - 1024х768.

Сравнение с JPEG

Сегодня наиболее распространенным алгоритмом архивации графики является JPEG . Сравним его с фрактальной компрессией.

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

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

1. Фракталы и история возникновения метода фрактального сжатия

В декабре 1992 года, перед самым Рождеством, компания Microsoft выпустила свой новый компакт-диск Microsoft Encarta. С тех пор эта мультимедиа-энциклопедия, содержащая информацию о животных, цветах, деревьях и живописных местах, не покидает списки наиболее популярных энциклопедий на компакт-дисках. В недавнем опросе Microsoft Encarta опять заняла первое место, опередив ближайшего конкурента - Комптоновскую мультимедиа-энциклопедию. Причина подобной популярности кроется в удобстве использования, высоком качестве статей и, главное, в большом количестве материалов. На диск записано 7 часов звука, 100 анимационных роликов, примерно 800 масштабируемых карт, а также 7000.качественных фотографий. И все это - на одном диске! Напомним, что обычный компакт-диск в 650 Мбайт без использования компрессии может содержать либо 56 минут качественного звука, либо 1 час видео разрешения с разрешением 320х200 в формате MPEG-1, либо 700 полноцветных изображений размером 640х480. Чтобы разместить больше информации, необходимы достаточно эффективные алгоритмы архивации. Мы не будем останавливаться на методах архивации для видео и звука. Речь пойдет о новом перспективном алгоритме - фрактальном сжатии графической информации.

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

Определение фрактала, данное Мандельбротом, звучит так: "Фракталом называется структура, состоящая из частей, которые в каком-то смысле подобны целому"

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

Существует большое разнообразие фракталов. Потенциально наиболее полезным видом фракталов являются фракталы на основе системы итеративных функций (Iterated Function System - IFS) . Метод IFS применительно к построению фрактальных изображений, изобретённый большим их знатоком Майклом Барнсли (Michael Barnsley) и его коллегами из Технологического института шт. Джорджия (Georgia Institute of Technology) , базируется на самоподобии элементов изображения и заключается в моделировании рисунка несколькими меньшими фрагментами его самого. Специальные уравнения позволяют переносить, поворачивать и изменять масштаб участков изображения; таким образом, эти участки служат компоновочными блоками остальной части картины.

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

IFS -фракталы имеют одно вполне реальное и полезное применение: с их помощью можно сжимать большие растровые изображения до долей их нормальных размеров. Этот утверждение следует из теоремы Банаха о сжимающих преобразованиях (также известной как Collage Theorem ) и является результатом работы исследователя Технологического института шт. Джорджия Майкла Барнсли в области IFS . Вооружившись этим выводом, он ушёл из института, запатентовал свое открытие и основал компанию Iterated Systems Incorporated . О своём достижении он рассказал миру в журнале Byte за январь 1988 г. Однако там отсутствовали какие-либо сведения о решении обратной задачи: как по заданному изображению найти аффинные преобразования. К тому моменту у этой задачи не было даже намёка на решение. В статье Барнсли было показано несколько реалистичных фрактальных изображений, но все они были созданы вручную.

В идеале хотелось бы уметь находить для любого изображения систему аффинных преобразований (IFSM) , воспроизводящую изображение с заданной точностью. Однако решение находилось немного в стороне. Первым нашёл его именно студент Барнсли, Арно Жакан (Arnaud Jacquin) . Предложенный метод получил название «Система итерируемых кусочно-определённых функций» (Partitioned Iterated Function System - PIFS) . Согласно этой схеме, отдельные части изображения подобны не всему изображению, а только его частям.

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

Фрактальные методы сжатия позволяют сжать информацию в 10 000 раз. Все известные программы фрактальной компрессии базируются на алгоритме Джеквина - сотрудника Барнсли, который в 1992 году при защите диссертации описал практический алгоритм фрактального сжатия. Несомненным достоинством работы было то, что вмешательство человека в процесс сжатия удалось полностью исключить.

Рассмотрим механизм фрактального сжатия данных. Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Прежде чем рассматривать процесс архивации, разберем, как IFS строит изображение. Строго говоря, IFS - это набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, у координата, яркость). Наиболее наглядно этот процесс продемонстрировал сам Барнсли в своей книге "Фрактальное сжатие изображения". В ней введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран. Каждая линза проецирует часть исходного изображения. Расставляя линзы и меняя их характеристики, можно управлять получаемым изображением. На линзы накладывается требование они должны уменьшать в размерах проектируемую часть изображения. Кроме того, они могут менять яркость фрагмента и проецируют не круги, а области с произвольной границей. Одна шаг Машины состоит в построении с помощью проецирования по исходному изображению нового. Утверждается, что на некотором шаге изображение перестанет изменяться. Оно будет зависеть только от расположения и характеристик линз и не будет зависеть от исходной картинки. Это изображение называется неподвижной точкой или аттрактором данной IFS. Collage Theorem гарантирует наличие ровно одной неподвижной точки для каждой IFS. Поскольку отображение линз является сжимающим, каждая линза в явном виде задает самоподобные области в нашем изображении. Благодаря самоподобию мы получаем сложную структуру изображения при любом увеличении. Наиболее известны два изображения, полученных с помощью IFS треугольник Серпинского и папоротник Барнсли Первое задается тремя, а второе - питью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время, как изображение, построенное с их помощью, может занимать и несколько мегабайт. Становится понятно, как работает архиватор, и почему ему требуется так много времени. Фактически, фрактальная компрессия - это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований. В худшем случае, если не будет применяться оптимизирующий алгоритм, потребуется перебор и сравнение всех возможных фрагментов изображения разного размера. Даже для небольших изображений при учете дискретности мы получим астрономическое число перебираемых вариантов. Даже резкое сужение классов преобразований, например, за счет масштабирования только в определенное число раз, не позволит добиться приемлемого времени. Кроме того, при этом теряется качество изображения. Подавляющее большинство исследований в области фрактальной компрессии сейчас направлены на уменьшение времени архивации, необходимого для получения качественного изображения.

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

Есть отображение, где - множество всех возможных изображений. W является объединением отображений w i :

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

Если к какому-то изображению F 0 мы начнём многократно применять отображение W таким образом, что

Это конечное изображение F называют аттрактором , или неподвижной точкой отображения W . Также известно, что если преобразования w i являются сжимающими, то их объединение W тоже является сжимающим.

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

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

1. d i по размерам больше r i .

2. w i (r i ) имеет ту же форму, размеры и положение, что и r i .

3. Коэффициент u преобразования w i должен быть меньше единицы.

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 , а также разбиение изображения на домены.

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

1. Создать какое-то (любое) начальное изображение R 0 .

2. Многократно применить к нему отображение W (объединение w i ).

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

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

4. Оценка коэффициента сжатия и вычислительных затрат

Размер данных для полного определения ранговой области рассчитывается по формуле:

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

где V и H - вертикальный и горизонтальный размеры изображения, Size - размер доменного блока, Step - шаг поиска доменной области.

Для хранения преобразования T необходимо 3 бита.

Для хранения U и V необходимо 9 и 7 бит соответственно.

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

Nd = Md = (256 - 8 + 1) / 4 = 62

Nb = Mb = CEIL (log 2 62) = 6

Z = 12 + 3 + 6 + 6 = 27

Коэффициент сжатия S составляет

S = (8 * 8 * 8) / 27 = 19

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

А теперь оценим вычислительную сложность данного алгоритма. На этапе компрессии мы должны перебрать все доменные области - 1"024 штуки, для каждой - все ранговые - 58"081 штука (при шаге 1), а для каждой из них, в свою очередь, - все 8 преобразований. Итого получается 1"024 х 58"081 х 8 = 475"799"552 действия. При этом эти действия не тривиальны и включают несколько матричных операций, которые, в свою очередь, включают операции умножения и деления чисел с плавающей точкой.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Идея метода

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

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

Наиболее наглядно этот процесс продемонстрировал М. F. Barnsley в книге . Там введено понятие "фотокопировальной машины", состоящей из экрана, на котором изображена исходная картинка, и системы линз, про­ецирующих изображение на другой экран (рис. 2.2):

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

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

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

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

Исходное

/ изображение

Получаемое изображение

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

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

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

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

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

Рис. 2.3. Треугольник Серпинского Рис 2.4. Папоротник Барнсли

Упражнение. Укажите в изображении 4 области, объединение которых покры­вало бы все изображение и каждая из которых была бы подобна всему изо­бражению (не забывайте о стебле папоротника).

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

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

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

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

Определение. Преобразование w: R 1 -> Л 2 , представимое в виде где а, Ъ, с, d, e,f- действительные числа и (х у)еЯ г - называется двумер­ным аффинным преобразованием.

Определение. Преобразование w : Л 3 -» Д 3 , представимое в виде

w(x) = w

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

Определение. Пусть /:Х->Х - преобразование в пространстве X.

Точка x f eX, такая, что f(x f) = x f , называется неподвижной точкой (аттрактором) преобразования.

Определение. Преобразование /:Х->Х в метрическом пространстве

(X, d) называется сжимающим, если существует число S: 0 £ s < 1, такое, что

d(f(x),f(y))V*,yeX.

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

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

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

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

Пусть трехмерное аффинное преобразование w,: R 3 -> R 3 , записано в виде Y и определено на компактном подмножестве £>. декартова квадрата

х (мы пользуемся особым видом матрицы преобразования, чтобы уменьшить размерность области определения с R 3 до R 2). Тогда оно переве­дет часть поверхности S в область Л, расположенную со сдвигом (ej) и по­воротом, заданным матрицей r. При этом, если интерпретировать значения функции 5(л:,^)е как

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

Определение. Конечная совокупность W сжимающих трехмерных аффин­ных преобразований W t , определенных на областях D t , таких, что w,(Ј>,) = R, и J?,. r\Rj=

V/ * j , называется системой итерируемых функций (IFS).

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

Построение алгоритма

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

В учебном варианте алгоритма, изложенном далее, сделаны следую­щие ограничения на области:

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

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

3. Все доменные блоки- квадраты и имеют фиксированный размер. Изо­бражение равномерной сеткой разбивается на набор доменных блоков.

4. Доменные области берутся "через точку" и по I и по У, что сразу уменьшает перебор в 4 раза.

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

6. Масштабирование (сжатие) по вертикали (яркости) осуществляется в фиксированное число раз - 0.75.

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

7. Очень компактно представить данные для записи в файл. Нам требуется на каждое аффинное преобразование в IFS:

♦ Два числа для того, чтобы задать смещение доменного блока. Если мы ограничим входные изображения размером 512x512, то достаточ­но будет по 8 бит на каждое число.

♦ Три бита для того, чтобы задать преобразование симметрии при пе­реводе доменного блока в ранговый.

♦ 7-9 бит для того, чтобы задать сдвиг по яркости при переводе.

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

Например, для файла в градациях серого 256 цветов 512x512 пикселов при размере блока 8 пикселов аффинных преобразований будет 4096 (512/8-512/8). На каждое потребуется 3.5 байта. Следовательно, если исход­ный файл занимал 262144 (512-512) байт (без учета заголовка), то файл с ко­эффициентами будет занимать 14336 байт. Степень сжатия- 18 раз. При этом мы не учитываем, что файл с коэффициентами тоже может обладать избыточностью и сжиматься без потерь с помощью, например, LZW.

Отрицательные стороны предложенных ограничений:

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

2. Аналогично мы не сможем воспользоваться подобием объектов в изобра­жении, коэффициент подобия между которыми сильно отличается от двух.

3. Алгоритм не сможет воспользоваться подобием объектов в изображе­нии, угол между которыми не кратен 90°.

Такова плата за скорость компрессии и за простоту упаковки коэффи­циентов в файл.

Сам алгоритм упаковки сводится к перебору всех доменных блоков и подбору для каждого соответствующего ему рангового блока. Ниже приво­дится схема этого алгоритма.

for (all range blocks) {

min_distance = MaximumDistance;

R^j = image->CopyBlock(i, j) ;

for (all domain blocks) { // С поворотами и отр.

current=KoopflMHaTH тек. преобразования;

D=image->CopyBlock(current);

current_distance = R_jj.L2distance(D) ; if(current_distance < min_distance) {

// Если коэффициенты best хуже: min_distance = current_distance; best = current; } }

// Next domain block Save_Coefficients_to_file(best);

// Next range block

Как видно из приведенного алгоритма, для каждого рангового блока де­лаем его проверку со всеми возможными доменными блоками (в том числе с прошедшими преобразование симметрии), находим вариант с наименьшей мерой L 2 (наименьшим среднеквадратичным отклонением) и сохраняем ко­эффициенты этого преобразования в файл. Коэффициенты - это (1) коорди­наты найденного блока, (2) число от 0 до 7, характеризующее преобразова­ние симметрии (поворот, отражение блока), и (3) сдвиг по яркости для этой пары блоков. Сдвиг по яркости вычисляется как b для r-,j - значения пикселов рангового блока (К), a dy - значения пикселов доменного блока (D). При этом мера считается как

rf(tf,D) = ££(,;,+S-0.754,) 2 .

Мы не вычисляем квадратного корня из L 2 меры и не делим ее на л, по­скольку данные преобразования монотонны и не помешают нам найти экс­тремум, однако мы сможем выполнять на две операции меньше для каждого блока.

Посчитаем количество операций, необходимых нам для сжатия изобра­жения в градациях серого 256 цветов 512x512 пикселов при размере блока 8 пикселов:

Число операций

4096 (=512/8-512/8)

492032 (=(512/2-8)* (512/2-8)*8)

> 3*64 операций"+"

> 2*64 операций " "

> 3* 128.983.236.608 операций "+"

> 2* 128.983.236.608 операций " "

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

Схема алгоритма декомпрессии изображений

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

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

Прочитаем из файла коэффициенты всех блоков; Создадим черное изображение нужного размера; Until(изображение не станет неподвижным){

For(every range (R)){

D=image->CopyBlock(D_coord_for_R); For(every pixel}