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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цели и задачи

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

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

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

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 г. Текст и материалы диссертации могут быть получены у автора или его руководителя после этой даты.

Ключевые слова: нейронные сети; сжатие изображений; машинное обучение; фракталы.

Аннотация

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

1. Введение

Фрактальное кодирование изображений представляет собой подающий надежды подход в приложениях сжатия изображений, таких как веб-сайты Интернет . Однако, потребность во времени для этапа кодирования в этом подходе было сдерживающим препятствием его принятию как практического метода. Процесс кодирования заключается в отображении доменных блоков в ранговые блоки изображения. Для каждого рангового блока алгоритм ищет такой доменный блок и соответствующее преобразование, которые обеспечат наилучшее соответствие ранговому блоку. Классификация доменных блоков может значительно ускорить выполнение кодирования, сокращая количество доменов, среди которых нужно проводить поиск . Использование самоорганизующихся нейронных сетей с целью классификации доменов уже было исследовано . Эти сети дают улучшение, по сравнению с базовыми подходами к классификации, благодаря определению топологии кластеров классов. Вклад данной работы состоит в комбинировании классификации доменов с помощью самоорганизующейся нейронной сети вместе с выделением характеристик с целью обеспечения еще более быстрого кодирования изображений. Небольшой набор характеристик изображения, измеряющих тоновые и текстурные качества, вычисляются для каждого доменного и рангового блока. Таким образом, каждый блок имеет ассоциированный с ним вектор характеристик, размер которого не зависит от размера блока. Выделение характеристик является выгодным по двум причинам. Во-первых, получаемое в результате снижение объема задачи сокращает количество вычислений, необходимых в процессе поиска доменов. Во-вторых, так как характеристики независимы от структуры конкретных доменов, то становится возможным обучать самоорганизующуюся сеть на одном изображении и применять полученную в результате сеть для классификации на других изображениях. Таким образом, время обучения сети не является частью общего времени кодирования. Измерения времени фрактального кодирования изображений обычно выражают в терминах времени выполнения на рабочей станции Sun или Silicon Graphics. Представленный здесь подход обеспечивает сопоставимые измерения при выполнении на ПК Pentium 120 MHz.

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

Фрактально кодирование изображений основано на теории систем итерируемых функций (далее сокращенно СИФ, от англ. Iterated Function System - IFS). Теория СИФ имеет в своей основе теорему о сжимающих отображениях (далее сокращенно ТОС, от англ. Contraction Mapping Theorem - CMT) из классического анализа, которая используется для построения фрактальных изображений итеративным образом. Фрактальное изображение является фиксированной точкой в пространстве изображения, что гарантируется ТОС, и это изображение называется аттрактором СИФ. Обратная задача, решаемая фрактальным кодированием изображений, начинается с рассмотрения заданного изображения и вычисления СИФ, представляющей изображение, близкое к заданному, - его аттрактор. Код фрактального изображения обычно (хотя, не всегда) требует меньшего объема для хранения, чем изображение-оригинал, что проявляет этот метод как метод сжатия. Эмпирические результаты показывают, что во многих случаях фрактальный метод настолько же хорош, как и JPEG, который считают стандартом сжатия на сегодня .

Фрактальное сжатие изображений использует специальную разновидность СИФ, называемую системой итерируемых кусочно-определенных функций (далее сокращенно СИКФ, от анг. Partitioned Iterated Function System - PIFS). СИКФ состоит из полного метрического пространства X , набора поддоменов D i ⊂ X, i = 1,...,n , и набора сжимающих преобразований w i ~ : D i → X, i = 1,...,n . Мы рассматриваем изображения в градациях серого как функции действительные значений f(x, y) , определенные на квадратной области I 2 = I×I . Пусть w i ~ (x, y) - аффинное преобразование I 2 → I 2 , такое что

при условии, что w i ~ - обратимо и (x,y) ∈ R i . Константа s i расширяет или сужает диапазон значений функции f и, коль скоро мы говорим об изображениях в градациях серого, то она управляет контрастностью. Аналогично, константа o i увеличивает или уменьшает значения градаций серого, или управляет яркостью. Преобразование w i ~ называется пространственной составляющей преобразования w i .

Базовый алгоритм выполняется следующим образом. Разбиваем изображение на не перекрывающиеся прямоугольные ранговые блоки {R i } . Блоки R i могут быть одинакового размера, но чаще используется некоторая разновидность разбиения с переменным размером блоков, что дает возможность плотно заполнять ранговыми блоками маленького размера части изображения, содержащие мелкие детали. Представленные здесь результаты, были получены с использованием схемы разбиения методом квадро-дерева (quadtree partition scheme), описанной в . Покрываем изображение последовательностью доменных блоков, возможно перекрывающихся. Домены могут быть разных размеров и обычно их количество исчисляется сотнями и тысячами. Аффинное преобразование (2.1) является пространственным сжимающим преобразованием, если |det A i |

(2.3)

была небольшой. Для оцифрованных изображений интеграл (2.3) заменяется суммированием по пикселям. Если после нахождения наилучшего w i величина (2.3) оказывается все еще больше некоторой заранее определенной погрешности, то схема разбиения методом квадро-дерева разбивает ранг на четыре более малых прямоугольника, и процесс поиска оптимального преобразования повторяется для этих меньших блоков. Этот процесс продолжается до тех пор, пока величина (2.3) не станет меньше допустимой погрешности или пока не достигается заранее определенная максимальная глубина квадро-дерева. Изображение декодируется итеративным применением преобразования W к изображению f , где

W(f)(x,y) = w i (f)(x,y) для (x,y) ∈ R i

Если преобразования {w i } были выбраны корректно, то итерирование W 0n (f) будет близко к исходному изображению при некотором достаточном значении n . Этап кодирования требует значительных вычислений из-за большого количества доменов, среди которых нужно осуществлять поиск для каждого рангового блока, а также из-за вычислений, проводимых при каждом сравнении домена с рангом. В этой работе сокращение вычислительных потребностей этапа кодирования решается в двух направлениях. Во-первых, вводится понятие характеристик изображения, определяемых для каждого доменного и рангового блока. Тогда потенциально подходящие домены могут быть выбраны на основе значений небольшого количества этих характеристик, чем значений самих пикселей. Во-вторых, предлагается организация доменных блоков в кластерную топологию посредством самоорганизующейся нейронной сети. Это еще больше сокращает время кодирования, позволяя сети быстро определять месторасположение в пространстве характеристик тех доменных блоков, которые похожи на ранговые блоки.

3. Выделение характеристик

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

Здесь используются следующие шесть характеристик: 1) стандартное отклонение (standard deviation), σ; 2) асимметрия (skewness), которая представляет собой сумму кубов разностей между значениями пикселей и средним значением блока, нормированных кубом σ; 3) межпиксельная контрастность (neighbor contrast), которая измеряет разность между значениями соседних пикселей; 4) бета (beta), которая показывает насколько сильно отличаются значения пикселей от значения в центре блока; 5) горизонтальный градиент (horizontal gradient), который характеризует изменение значений пикселей блока по горизонтали; 6) вертикальный градиент (vertical gradient), который характеризует изменение значений пикселей блока в направлении сверху вниз. Среднее пиксельное значение не используется в качестве характеристики, поскольку контрастность и яркость меняются в процессе сопоставления доменного и рангового блоков. При сравнении расстояний в пространстве характеристик, вектор характеристик нормализуют для того, чтобы набольшие значения характеристик не доминировали при сравнении.

4. Самоорганизующиеся нейронные сети

Следующее улучшение, которое может быть сделано - это классификация доменов и рангов на основе этих характеристик и сравнение рангов только с доменными похожих классов. Используемая здесь схема классификации доменов основана на самоорганизующейся нейронной сети Кохонена . Этот тип сети состоит из решетки (lattice) узловых позиций (node positions). С каждым узлом решетки связан весовой вектор, который имеет ту же размерность, что и размерность векторов характеристик. Размерность используемых здесь векторов характеристик составляет 6. А используемая здесь решетка узлов состоит из 10 строк и 10 столбцов. Каждый узел представляет класс доменных блоков изображения, поэтому общее количество узлов мы стремимся сохранить довольно малым. Можно рассматривать и другие способы организации узлов, такие как матрицы более высокой размерности.

Процесс обучения происходит независимо, без какого-либо контроля со стороны человека. Сеть весовых векторов инициализируется случайными значениями. Затем в сеть поступает входной вектор характеристик, и мы отыскиваем весовой вектор, самый близкий к входному вектору. То есть, мы находим i’j’ , такие что

||v – w i’j’ || ≤ ||v – w ij || для всех i, j

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

w ij new = w ij old + ε·exp(α·||v–w ij old || 2)·(v– w ij old)

где ij - это индексы узлов, которые находятся в окрестности узла i’j’ . Размер этой окрестности сокращается с каждой новой итерацией процесса обучения. Параметр ε - это шаг итерации, и α обратно пропорционально этому шагу. Программная реализация представленных результатов приведена в .

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

5. Результаты

В таблице 1 представлены результаты сравнения фрактального сжатия изображений с использованием трех различных методов, применительно к изображениям, показанным на рисунках 1 и 2. «Базовый» («base») метод - это стандартный метод разбиения квадро-деревом, обсуждаемый в , без классификации доменов. Величина «уровень квадро-дерева» («quadtree level») обозначает максимально допустимую глубину квадро-дерева. Здесь большое число обуславливает более малые ранговые блоки, что приводит к лучшему качеству декодируемого изображения, но при этом к худшей компрессии. «Порог ошибки» («error threshold») - это параметр, контролирующий условие разбиения ранговых блоков на более малые блоки следующего более высокого уровня квадро-дерева. Значения ошибок вычисляются путем сравнения исходного растрового изображения с изображением, декодированным с использованием 6 итераций (большее количество итераций дало бы немного меньшие ошибки). «Средняя ошибка, %» («average error») - это средняя ошибка, приходящаяся на один пиксель, в то время как «PSNR» - это пиковое отношение сигнал-шум, вычисляемое как в . Метод «FO» (features-only) на основе только характеристик сравнивает доменные и ранговые блоки по шести характеристикам, рассмотренных в разделе 3. Последний метод («SO») классифицирует домены с использованием самоорганизующейся нейронной сети с выделением характеристик, как было рассмотрено выше. В каждом случае всего было использовано 320 доменных блоков. Большее количество доменов привело бы к увеличению времени кодирования и в какой-то степени лучшим коэффициентам сжатия.

Коэффициенты сжатия оцениваются отношением в среднем 4 байт для каждого рангового блока к 66614 байтам исходного растрового изображения. SO-метод работает приблизительно в два раза быстрее FO-метода и в сто раз быстрее базового метода («время на блок» выражает меру времени выполнения, которая не зависит от конечной точности изображения; приведенные здесь значения времени соответствуют ПК Pentium 120MHz). Самоорганизующаяся сеть была обучена отдельно на изображении, отличном от представленных здесь двух изображений, поэтому время обучения не включено в общее время для этого метода. Степень сжатия и качество декодированного изображения, как при ускоренных методах, так и при базовом методе, соизмеримы.

Таблица 1 — Результаты фрактального сжатия изображений при использовании самоорганизующейся классификации доменов («SO»-метод), сравнении доменов на основе только характеристик («FO»), и базовом методе («Base»)

	Изображение	Порог ошибки	Уровень квадро-дерева	Количество блоков	Время, (с)	Время на блок, (с)	Средняя ошибка, %		Коэфф. сжатия
(а)	(б)

Рисунок 2 — (а): Исходное растровое изображение «Leaves» (256×256, 256 градаций серого); (б): Декодированное изображение (6 итераций, уровень квадро-дерева равен 7, средняя пиксельная ошибка равна 3.05%, сжатие 1.6:1). Более высокий уровень детализации в этом изображении приводит к уменьшению быстродействия

6. Выводы

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

Литература

1. E. DeJesus, “Walking, Talking Web”, Byte, January, 1997, 81-84.
2. Y. Fisher, ed., Fractal Image Compression, (New York: Springer-Verlag, 1995).
3. A. Jacquin, “Image coding based on a fractal theory of iterated contractive image transformations”, IEEE Trans. Image Proc. 1, 1992, 18-30.
4. A. Bogdan and H. Meadows, “Kohonen neural network for image coding based on iteration transformation theory”, Proc. SPIE 1766, 1992, 425-436.
5. R. Hamzaoui, “Codebook clustering by self-organizing maps for fractal image compression”, NATO ASI Conf. On Fractal Image Encoding and Analysis, July, 1995.
6. M. Barnsley, Fractals Everywhere, 2nd ed. (Boston: Academic Press, 1993).
7. T. Kohonen, Self-Organization and Associative Memory, (Springer-Verlag, 1989).
8. S. Welstead, Neural Network and Fuzzy Logic Applications in C/C++, (New York: John Wiley and Sons, 1994).