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

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

     Слово фрактал введено в 1975 году Бенуа Мандельбротом. Оно произведено от латинского fractus, от которого происходят английские термины fraction, fractional - дробь, дробный. С математической точки зрения фрактал - это, прежде всего множество с дробной размерностью.
     Мы хорошо представляем себе, что точка имеет размерность 0, отрезок и окружность - размерность 1, круг и сфера - размерность 2. С одномерными объектами мы связываем понятие длины, с двумерными - площади и так далее. Но как можно представить себе множество с размерностью 3/2? По-видимому, для этого требуется нечто промежуточное между длиной и площадью, и если длину условно назвать 1-мерой, а площадь - 2-мерой, то требуется (3/2)-мера.[7]
     В 1919 году Ф. Хаусдорф действительно определил такую a-меру и на этой основе каждому множеству в евклидовом пространстве сопоставил число, названное им метрической размерностью. Он же привел первые примеры множеств с дробной размерностью. Оказалось, что дробную размерность имеют канторово множество, кривая Кох и другие экзотические объекты, до недавнего времени малоизвестные за пределами математики.[7]
     Бенуа Мандельброт в своих книгах привел яркие примеры применения фракталов к объяснению некоторых природных явлений. Мандельброт уделил большое внимание интересному свойству, которым обладают многие фракталы. Дело в том, что часто фрактал можно разбить на сколь угодно малые части так, что каждая часть окажется просто уменьшенной копией целого. Иначе говоря, если мы будем смотреть на фрактал в микроскоп, то с удивлением увидим ту же самую картину, что и без микроскопа. Это свойство самоподобия резко отличает фракталы от объектов классической геометрии.
     Необходимо отметить, что свойство самоподобия характерно только для регулярных фракталов.Многие регулярные фракталы строятся путем бесконечного повторения нескольких простых операций - заменой одного элемента некоторой комбинацией других, ему подобных. Затем эта же операция повторяется с каждым из этих элементов, и так далее до бесконечности. На методе простой замены основан первый алгоритм построения фракталов.
     Возникает вопрос, нельзя ли эту "процедуру замены" перевести на язык математических формул. Таким образом, в середине 80-х годов появился метод Систем Итерируемых Функций - СИФ (Iterated Function System - IFS) как простое средство получения фрактальных структур. Таким образом, некоторые из вышеперечисленных фракталов можно получить с помощью метода СИФ. Метод Систем Итерируемых функций является основой для второго алгоритма построения фрактальных структур. Вместо детерминированного способа построения регулярных фракталов в алгоритм создания фрактальных структур был включен некоторый элемент случайности, что приводит к построению случайных фракталов. Многие фракталы могут быть получены с помощью этих двух алгоритмов. Тогда в первом случае они построены как регулярные фракталы, а во втором как случайные.
     Одним из наиболее ярких примеров среди различных систем итерируемых функций является открытая М. Брансли система из четырех сжимающих аффинных преобразований, аттрактором для которой является множество точек, поразительно напоминающее по форме изображение листа папоротника.
     Третьим алгоритмом создания фрактальных объектов на плоскости является использование комплексных отображений, сопоставляющих одному комплексному числу другое комплексное число по некоторому итерационному правилу. Примером фрактала полученного с помощью комплексных отображений является множество Жюлиа.

     Пусть d - обычная Евклидова размерность пространства, в котором находится фрактальный объект (d = 1 - линия, d = 2 - плоскость, d = 3 - обычное трехмерное пространство). Покроем теперь этот объект целиком d-мерными "шарами" (куб, квадрат или просто отрезок прямой) радиуса l. Предположим, что нам потребовалось для этого не менее чем N(l) шаров. Тогда, если при достаточно малых l величина N(l) меняется с l по степенному закону N(l)~1/l^D, то D - называется хаусдорфовой или фрактальной размерностью этого объекта. Эту формулу можно переписать в виде

Это и служит общим определением фрактальной размерности D. В соответствии с ним D является локальной характеристикой данного объекта.[2,стр.15]

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

Рисунок 3.1 - Салфетка Серпинского
Фрактальная размерность салфетки Серпинского подсчитывается по формуле
D=ln3/ln2=1,5849
Салфетка имеет нулевую площадь, так как нетрудно проверить, что в процессе ее построения была исключена площадь, в точности равная площади исходного треугольника. Об этом же свидетельствует и значение фрактальной размерности D<2, которая меньше размерности плоскости на которой находится этот объект. [2, стр.20]

     Для большинства регулярных фракталов фрактальная размерность D меньше, чем размерность d того пространства, в котором находится данный фрактальный объект. Неравенство D < d отражает факт некомпактности фрактала, причем чем больше различаются величины D и d, тем более рыхлым является фрактал.
     Существуют фракталы, которые плотно заполняют пространство, в котором они находятся, так что их фрактальная размерность D = d. Одним из примеров такого рода являются кривые Пеано (Peano curves). Дракон Хартера-Хейтуэя является примером кривой Пеано, для которой область, которую она заполняет на плоскости, имеет причудливую форму. Первые четыре шага его построения представлены на рис.3.2.

Рисунок 3.2 - Первые четыре шага построения дракона Хартера-Хейтуэя
Как следует из рис.3.2 каждый из отрезков прямой на следующем шаге заменяется на два отрезка, образующих боковые стороны равнобедренного прямоугольного треугольника, для которого исходный отрезок являлся бы гипотенузой. В результате отрезок как бы прогибается под прямым углом. Направление прогиба чередуется. Первый отрезок прогибается вправо (по ходу движения слева направо), второй - влево, третий - опять вправо и т.д. На рис.3.2 пунктиром показана конфигурация предыдущего шага. Таким образом, после каждого шага число имеющихся отрезков удваивается, а длина каждого соответственно уменьшается в раз. Поэтому фрактальная размерность образующейся в результате (после бесконечного числа шагов) кривой равна 2. [2, стр.28-29]
     Для реализации указанного выше алгоритма построения необходимо перейти к комплексным числам Z_A, Z_B и Z_C (рис.3.3).

Рисунок 3.3 - Представление в комплексных числах
Для нахождения координат точки C представим комплексные числа в тригонометрической форме. Нахождение координат точки C представлено формулами (3.1) - (3.8).
                                                              (3.1)
                                                                                                        (3.2)
                                                                   (3.3)
                               (3.4)
                                      (3.5)
      (3.6)
                                                                     (3.7)
                                                                     (3.8)
Результатом реализации приведенного выше алгоритма является программа, разработанная в среде Visual C++6.0. На рис.3.4 представлено 16-е поколение дракона Хартера-Хейтуэя.

Рисунок 3.4 - Изображение 16-го поколения дракона Хартера-Хейтуэя
Программа позволяет задавать координаты начального отрезка построения, а также номер поколения дракона.

     Рассмотрим алгоритм построения, основанный на методе IFS на примере упомянутой выше салфетки Серпинского.
Поместим исходный равносторонний треугольник с длинной стороны, для определенности равной единице, на комплексную плоскость Z так, как показано на рис. 3.5 слева.

Рисунок 3.5 - Преобразование t₁. В скобках даны декартовы координаты вершин
Зададим линейное преобразование t₁, которое переводит на комплексной плоскости в равносторонний треугольник в два раза меньшего размера, представленный на рис.3.5 справа t₁: f₁(z)=1/2*z
Если теперь сместить этот маленький треугольник по горизонтали вправо на величину, равную 1/2, то получим преобразование t₂, переводящее исходный треугольник в треугольник представленный на рис.3.6 справа.

Рисунок 3.6 - Преобразование t₂
Соответствующая этому преобразованию функция равна
t₂: f₂(z)=1/2*z+1/2
Последний, третий маленький треугольник получается с помощью преобразования t₃, представленного на рис. 3.7.

Рисунок 3.7 - Преобразование t₃
Соответствующая ему функция f₃(z) получается из f₁(z) трансляцией на комплексный вектор

     В результате три представленные линейные функции осуществляют искомое преобразование исходного треугольника в три треугольника в два раза меньшего размера. Если теперь каждый из этих трех маленьких треугольников подвергнуть этим трем преобразованиям, то тогда возникнет уже 9 треугольников в 4 раза меньше исходного. Таким образом, выполняя эту процедуру определенное число раз, мы получим салфетку Серпинского. Причина этого заключается в том, что салфетка является своеобразным аттрактором для этой системы из трех линейных преобразований.
     Для реализации построения салфетки Серпинского на компьютере можно применить так называемый метод случайных итераций (игра в хаос), который связан с системой итерируемых функций.
     Возьмем, например, начальную точку z₀ в центре исходного треугольника. Далее каждому из четырех преобразований сопоставим одинаковую вероятность p_i=1/3. После чего, выбирая случайным образом последовательность преобразований будем получать все новые и новые точки - z₁=f_i(z₀), z₂=f_j(z₁), z₃=f_k(z₂). В итоге после большого числа итераций получим ярко выраженную фрактальную структуру салфетки Серпинского. [2, стр.32-35]
     Результатом реализации приведенного выше алгоритма является программа, разработанная в среде VisualC++ 6.0. Результат работы программы представлен на рис.3.8.

Рисунок 3.8 - Результат построения после 50000 итераций

     Еще одним алгоритмом создания фрактальных объектов на плоскости является использование комплексных отображений, сопоставляющих одному комплексному числу z_n=x_n+i*y_n другое комплексное число z_n+1=x_n+1+i*y_n+1 по итерационному правилу, которое представлено формулой z_n+1=f(z_n), где f(z) - некоторая нелинейная функция z, n - номер итерации.
     Множество Жюлиа наряду с множеством Мандельброта занимает центральное место в теории фракталов. Множество Жюлиа представляет собой границу области притяжения неподвижных точек комплексных отображений. Наиболее изученным из них является отображение, представленное формулой f(z)=z²+c, где c=c₁+i*c₂ - const; ;c - множество всех комплексных чисел.
     Существуют два алгоритма его построения. Первый из них основан на использовании исходного отображения, второй - обратного.
     Справедлива следующая теорема. Предположим, что |c|<2. Пусть и пусть z_n=f_c⁽ⁿ⁾(z) для n = 1,2,3,… Если существует такое n, что |z_n|=>2, то имеет место , т.е. орбита стремится к бесконечности и z не принадлежит множеству Жюлиа. На этой теореме основан первый алгоритм - построение на основе исходного отображения.      Второй алгоритм построения, основанный на обратном отображении, опирается на свойство множество Жюлиа, состоящее в том, что для обратного отображения, т.е.

множество Жюлиа - аттрактор. [6, стр.219]
     В ходе выполнения работы была написана программа в среде Visual_C++6.0, реализующая построение множества Жюлиа по описанным выше алгоритмам.
     На рис.3.9 представлено множество Жюлиа для различных значений параметра c. Программа позволяет менять параметры построения.

Рисунок 3.9 - Множество Жюлиа для c=0.11+i*0.66

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

     Основным недостатком фрактального алгоритма является то, что требуются значительные вычислительные ресурсы при осуществлении сжатия изображений, в то время как разархивация происходит очень быстро. Значительные ресурсы требуются на подгонку домена под ранговый блок. Первые реализации фрактальных методов кодирования были очень медленными. Известно, что в случаях, когда число доменов превышает 100000, процесс кодирования занимает более двух дней! Это препятствовало использованию фрактальных методов сжатия на практике. Для сокращения и ускорения полного перебора всех участков изображения разработано много методов: основанные на аппаратном распараллеливании и ускорении вычислений, основанные на уменьшении количества сравнений одного блока с другими, основанные на изменении алгоритма. [8] Целью данной работы является разработка алгоритма сокращения количества вычислений при сжатии изображений. Практическая ценность заключается в предполагаемом уменьшении временных затрат и вычислительных мощностей при фрактальном сжатии изображений.
     При написании данного автореферата магистерская работа еще не завершена. Окончательное завершение – январь 2007 года. Полный текст работы и все материалы по теме могут быть получены у автора или его руководителя после указанной даты.