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

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

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

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

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

Основа метода фрактального кодирования - это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций к проблеме сжатия изображения была исследована Майклом Барнсли (англ. Michael Barnsley и Аланом Слоуном (англ. Alan Sloan).

Майкл Барнсли.

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

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

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

Папоротник Барнсли (слева) и треугольник Серпинского (справа).

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

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

Применение фракталов в медицине.

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

Примеры фракталоподобных структур в организме человека: бронхи, сосуды, мышцы.

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


Пример кардиограммы.

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


Пример рентгеновского снимка.

Рентгеновские снимки обработанные с помощью фрактальных алгоритмов дают более качественную картинку а соответственно и более качественную диагностику!!

Еще одна область в медицине где активно могут применятся фракталы - это гастроэнтерология. До настоящего времени и зачастую по сей день для диагностики заболеваний ЖКТ используются зондовые методы, которые связаны с необходимостью введения различной толщины зондов, что неприятно как для больного, так и для медперсонала. Кроме того, подобная техника проведения исследований значительно сужает объем их применения ввиду невозможности использования у соматически тяжелых больных, у больных в раннем послеоперационном периоде и т.п. Именно этой причиной объясняется не прекращающийся интерес физиологов и клиницистов к изучению моторно-эвакуаторной деятельности желудка и кишечника, а также к разработке новых методов, позволяющих адекватно, не только качественно, но и количественно оценивать интенсивность и характер моторной активности различных отделов ЖКТ. В качестве дополнительных методов исследования МЭФ применяются методы, основанные на измерении электрической активности органов. Исследования биоэлектрической активности органов ЖКТ положили начало созданию нового метода исследования в медицине, получившего название электрогастроэнтерография. Электрогастроэнтерография - метод исследования, позволяющий оценить биоэлектрическую активность желудка, двенадцатиперстной кишки и других отделов ЖКТ.


Пример электрогастроэнтерограммы.

Он основан на регистрации изменений электрического потенциала от органов ЖКТ, то есть снятие электрогастроэнтерограмм (ЭГЭГ). Применение фрактального анализа к получаемым биоэлектрическим сигналам от органов, позволяет эффективно судить о моторной функции органов и ЖКТ и успешно диагностировать различные заболевания.

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

Карты адгезии поверхностей раковых и нормальных клеток

Применение фракталов в естественных науках.

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

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


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

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


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

Пример твёрдого тела - кристаллы.


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

Турбулентность.

Применение фракталов в телекоммуникациях.


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

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

Фракталы как элементы визуализации и спецэффектов.

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

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


Моделирование ландшафта на основе фрактальных алгоритмов с помощью программы Fractal Landscapes.


Скриншот игры Minecraft.

Не обходится без фракталов и в кино. По сути в кино для создания различных фантастических пейзажей, как и в играх используются тот же принцип. Действительно, зачем каждый раз создавать новое дерево или гору, тратя на это кучу времени, когда всё это можно во много раз быстрее сделать с помощью компьютерных программ работающих на фрактальных алгоритмах. Интересный факт: в известном космическом хорроре Ридли Скотта "Чужой" в эпизоде когда команда спускается на поверхность планеты, монитор в корабле передаёт изображение поверхности планеты в виде сетки. Как раз таки это изображение и было создано при помощи фрактальной геометрии. Фрактальная геометрия позволяет художникам по спецэфффектам без труда создавать такие объекты как облака, дым, пламя, звёздное небо и т.д.

Теперь немного затронем тему фрактальной анимации. Фрактальные изображения, созданные в различных генераторах необычайно красивы. Что уж тогда говорить о фрактальной анимации, это действительное потрясающее зрелище. В первую очередь здесь стоит упомянуть о ресурсе Electric sheep. Electric sheep - ресурс использующий распределённые вычисления для создания фрактальной анимации основанной на алгоритме fractal flame (разработан Скотом Дрейвсом). Проще говоря на ваш компьютер устанавливается программное обеспечение, которое использует вашу машину для вычисления и рендера фрактальной анимации, одновременно с этим загружая и демонстрируя вам уже готовую фрактальную анимацию в виде так называемых "живых" обоев. При этом эти самые обои сохраняются на компьютере в определённой папке и их можно оттуда вытащить, чтобы затем использовать для своих целей, например в видеомонтаже (правда длина роликов коротковата - 5 секунд). Но имея в своём распоряжении программу Апофизис и скрипт к ней Apophymator, вы сможете без особого труда создавать свою анимацию (благо уроков по этой теме в сети множество) сколь угодно длинную, главное чтобы ваша машина была достаточно мощной.

Скриншоты анимации Electric sheep:

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

Фрактальную анимацию в качестве визуализации используют разработчики программ напрямую не относящиеся к фракталогенераторам. К примеру хорошо известный проигрыватель Winamp имеет в своём наборе большое количество визуализаций (плагин milkdrop) в которых явно прослеживаются элементы фракталов (например анимированное множество Жюлиа). Скриншоты визуализаций в плагине milkdrop для проигрывателя Winamp:

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

Оригинал статьи можно прочесть в мартовском номере журнала Компьюарт.

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

Цели и задачи

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

Идея работы - разработка новых модификаций методов отбора доменных блоков и способов их аппроксимации в ранговые блоки для повышения эффективности кодирования.

Для достижения указанной цели в магистерской работе поставлены и решены следующие задачи:

  1. Изучение литературных источников и проведение теоретического анализа алгоритмов сжатия изображений с потерями.
  2. Установление особенностей функционирования алгоритмов фрактального сжатия изображений, разработка реализующего их программного обеспечения.
  3. Формирование набора изображений, проведение вычислительных экспериментов по установлению особенностей отбора доменных блоков и их аппроксимации, сравнительный анализ результатов, формулирование выводов.
  4. Модификация отдельных этапов алгоритма, формирование его новой версии.
  5. Разработка соответствующих программных компонент, проведение экспериментов, сравнительные результаты работы.

Предмет исследования - алгоритмы сжатия изображений с потерями.

Объект исследования - фрактальные алгоритмы сжатия изображений.

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

Предполагаемая научная новизна

Научная новизна уже проведенных и планируемых в работе исследований предполагается в следующем:

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

Описание результатов работы

Описание исследований

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

Базовый алгоритм условно включает следующие этапы.

Шаг 1. В изображении f выделяют множество доменных блоков. Они могут перекрываться, а величина перекрытия определяется специально предусмотренным параметром.

Шаг 2. Изображение разбивают на не перекрывающиеся ранговые блоки {R k } . Они могут не быть одинакового размера, т.к. используется адап¬тивное разбиение методом квадро-дерева с переменным размером блоков. Это позволяет плотно заполнить ранговыми блоками маленького размера части изображения, содержащие мелкие детали.

Шаг 3. Для каждого рангового блока перебирают доменные блоки. При этом предусматривают изменение ориентации доменов (3 варианта вращения, 2 ва¬рианта вращения с отражением, 2 варианта отражения и 8-ой вариант - исходная ориентация без изменений). При каждом из вариантов ориентации домен сжимают до размеров рангового блока и вычисляют оптимальные значения коэффициентов a ij и b ij преобразования

методом наименьших квадратов и по формуле

вычисляют нормированное значение параметра L(R k , D" ij) , который характеризует соответствие преобразованного сжатого i -го доменного блока w ij (D" ij) в его j -ой ориентации ранговому блоку R k . Здесь r xy ∈ R k , d xy ∈ D" ij , D" ij — i -ый доменный блок в j -ой ориентации, сжатый до размеров рангового блока, N R k — количество пикселей в ранговом блоке. На этом шаге алгоритм работает в одном из двух режимах, выбираемом пользователем, — с поиском и без поиска наилучшего домена. В режиме поиска наилучшего домена для каждого ранга перебираются все домены, и выбирается тот i -ый домен и его j -ая ориентация, значение L kij которого является минимальным среди всех остальных. В режиме без поиска наилучшего домена полный перебор доменов останавливают, как только обнаруживается такой i -ый домен и его j -ая ориентация, что его значение L kij не превышает заданной допустимой погрешности (например, L kij ≤ 0.05). В обоих режимах, если после перебора всех доменных блоков не нашлось таких, значения L kij которых не превышают значение заданной допустимой погрешности, то делается проверка — находится ли рассматриваемый ранговый блок на максимально допустимом уровне разбиения рангов. Если нет, то этот ранговый блок разбивают на меньшие блоки и проводят данный шаг алгоритма для них. Если да, то из всех доменов выбирают тот домен и его вариант ориентации D ij , для которого значение L kij является минимальным среди всех остальных, и считают рассматриваемый ранговый блок покрытым этим доменом.

Шаг 3 требует наибольших вычислений, т.к. для каждого рангового блока R k алгоритм перебирает все (или многие, в зависимости от режима работы) доменные блоки и их варианты ориентации, проводя над каждым занимающие много машинного времени попиксельные операции изменения ориентации и нахождения коэффициентов преобразования. Хорошее сжатие зависит от возможности найти хорошее соответствие между доменными и ранговыми блоками без необходимости глубокого разбиения ранговых блоков. Чрезмерно глубокое разбиение рангов приводит к слишком большому их количеству, что ухудшает коэффициент сжатия, а недостаточно глубокое — к плохому качеству закодированного изображения.

FE-алгоритм. Сравнение рангов с доменами в базовом алгоритме требует значительных вычислительных ресурсов. С целью их снижения в FE-алгоритме (от англ. Feature Extraction — выделение особенностей) выделяется пять характеристик, описывающих доменные и ранговые блоки. И первоначально, проводится именно их сравнение, что значительно сокращает объем вычислений. Эти характеристики следующие:

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

Сам алгоритм включает следую¬щие этапы.

Шаг 1. Аналогично шагу 1 базового алгоритма.

Шаг 2. Дополняя шаг 2 базового алгоритма, производится вычисление и хранение значений вектора характеристик для каждого доменного блока.

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

где f j R и f j D - это j -ые характеристики рангового и доменного блоков соответственно. Для последующего полного сравнения отбирается только заданный q процент доменов (напри¬мер, q = 2%) с минимальными значениями расстояний между векторами характеристик. Последующие действия аналогичны тем, которые выполняются в шаге 3 базового алгоритма, но с той разницей, что при переборе доменов рассматриваются только выбранные q % и наилучший выбирается из них.

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

Описание разработанного ПО

Для проведения исследований было разработано специальное программное обеспечение на языке C# с использованием технологии Microsoft .NET Framework 2.0 и инструментальной оболочки Visual Studio 2005/2008. Оно позволяет кодировать растровые изображения в фрактальные и декодировать их рассмотренными выше алгоритмами. Пользователь может задавать настройки кодирования, регулирующие качество кодируемых изображений. Кроме того, программное обеспечение включает следующие средства анализа:

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

UML-диаграмма разработанного программного обеспечения представлена ниже (рисунок 1):

Рисунок 1 — UML-диаграмма разработанного программного обеспечения

Рисунок 2 — Экранные формы разработанного программного обеспечения

Эксперименты, результаты и выводы

С использованием разработанного программного обеспечения была проведена серия экспериментов, в которых использовалось произвольно выбранное изображение размером 256×256 пикселей, представленное на рисунке 3. Исходные данные, параметры настроек и результаты экспериментов приведены в таблице 1. На рисунке 4 представлено декодированное изображение, предварительно закодированное рассматриваемыми алгоритмами.

Рисунок 3 — Исходное изображение

Рисунок 4 — Визуализация восьми итераций декодирования изображения, закодированного базовым (а) и FE- (б) алгоритмами фрактального сжатия изображений. Анимация состоит из 9 кадров с задержкой в 50 мс между кадрами; задержка до повторного воспроизведения составляет 400 мс; количество циклов воспроизведения ограничено 10-ю.

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

где p x,y , p" x,y — значение пикселя в точке (x, y) исходного и декодированного изображений соответственно, I W , I H — соответственно ширина и высота (в пикселях) изображения, N I - количество пикселей в изображении.

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

Таблица 1 — Результаты экспериментов

Параметры № эксперимента
FE-алгоритм

Количество доменов

нач.ур.дом.

макс.ур.дом.

Коэфф. скольжения доменов

Количество рангов

Нач. уровень разбиения рангов

Допуст.погр.

Искать наилучший домен

Ср. пикс. ошибка, %

Коэфф.сжатия

Время кодирования, (с)

Время декодирования, (с)

Базовый алгоритм

Количество доменов

нач.ур.дом.

макс.ур.дом.

коэф.скольж.дом.

Количество рангов

Нач. уровень разбиения рангов

Макс. уровень разбиения рангов

Допуст.погр.

Искать наилучший домен

Ср. пикс. ошибка, %

Коэфф.сжатия

Время кодирования, (с)

Время декодирования, (с)

Полученные результаты позволяют сделать следующие выводы:

  1. FE-алгоритм, по сравнению с базовым, позволяет сжимать изображения в десятки раз меньшее время при одинаковых параметрах настроек алгоритмов.
  2. Различаются средние пиксельные ошибки алгоритмов. В зависимости от настроек, различие находится в пределах 5-16%.
  3. В результате кодирования базовым алгоритмом во всех случаях достигается в среднем на 30-40% более высокий коэффициент сжатия.
  4. Визуальное качество декодированного изображения заметно лучше при использовании FE-алгоритма.
  5. Время декодирования закодированного изображения при различных настройках кодирования меньше при использовании базового алгоритма во всех экспериментах.

Некоторые из них вполне очевидны. Действительно, в FE-алгоритме, вместо сравнения блоков изображения происходит сравнение их векторов характеристик, что естественно отражается на быстродействии. Различие пиксельных ошибок и коэффициентов сжатия скорее всего объясняется тем, что при использовании FE-алгоритма в результате кодирования получается бoльшее количество рангов малого размера, что к тому же обеспечивает более высокую детализацию изображения, то есть - лучшее визуальное качество. Эти заключения подтверждает и рисунок 6, на котором представлено закодированное обоими алгоритмами изображение с сеткой рангов. Следует обратить внимание на то, что хотя при базовом алгоритме и получается на 5-16% худшее качество изображения, но при этом, достигается на 30-40% более высокий коэффициент сжатия.

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

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

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

Заключение

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

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

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

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

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

Основные положения отдельных этапов работы были доложены на III-й международной научно-технической конференции молодых учёных и студентов «Информатика и компьютерные технологии» (Донецк, ДонНТУ, 2007), IV-й международной научной конференции студентов, аспирантов и молодых ученых «Компьютерный мониторинг и информационные технологии» (Донецк, ДонНТУ, 2008).

  • Lifeng Xi,Liangbin Zhang. A Study of Fractal Image Compression Based on an Improved Genetic Algorithm. International Journal of Nonlinear Science. Vol.3, No. 2, 2007, pp. 116-124
  • M. Hassaballah, M.M. Makky, Youssef B. Mahdy. A Fast Fractal Image Compression Method Based Entropy. Electronic Letters on Computer Vision and Image Analysis 5(1), 2005, pp. 30-40
  • P. M. Кроновер. Фракталы и хаос в динамических системах. Основы теории. - М.: Постмаркет, 2000
  • Barnsley, Michael F., Sloan, Alan D., Iterated Systems, Inc. Methods and apparatus for image compression by iterated function system. United States Patent 4941193, July 10, 1990

    • * — При написании данного автореферата магистерская диссертация еще не завершена. Окончательное ее завершение состоится 1 декабря 2008 г. Текст и материалы диссертации могут быть получены у автора или его руководителя после этой даты.

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

    Идея метода

    Фрактальное сжатие основано на том, что мы представляем изображение в более компактной форме - с помощью коэффициентов системы итерируе­мых функций (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}