«Фрактальное сжатие» - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Фрактальное сжатие 1 8.47kb.
Практикум n 9 Архивирование и сжатие в оc unix по курсу «Операционные... 1 66.02kb.
8 пьезоэлектрики 1 26.35kb.
Кодирование звука 1 11.33kb.
Растяжение и сжатие 1 25.48kb.
Online-сжатие трафика 1 67.42kb.
Домашнее задание по теме: «Кодирование звука. Решение заданий А8» 1 9.61kb.
«Дуэль брызгалок» /4469 1 12.07kb.
Цк-135/8 Назначение и область применения 1 29.21kb.
1. Управление обсерваторией и система астрономического анализа. 1 144.65kb.
Создание и использование сжатых и шифрованных файлов и папок ntfs 1 30.25kb.
Фрактальное сжатие 1 8.47kb.
Направления изучения представлений о справедливости 1 202.17kb.

«Фрактальное сжатие» - страница №1/1



Московский государственный институт электроники и математики

Кафедра электронно-вычислительной аппаратуры


РАБОТА НА ТЕМУ

«Фрактальное сжатие»

( по дисциплине “Компьютерная Графика”)

Выполнил: студент группы № С-54

Сарумов К.М.

Проверил: преподаватель

Королев Д.А.


Москва 2007


Содержание





Содержание 3

Введение 4

Статистическая и визуальная избыточность изображений 6

Статистическая избыточность изображений 6

Визуальная избыточность изображений 7

О кодировании цветных изображений 7

Обзор алгоритмов сжатия с потерями 8

Метод усеченного блочного кодирования (УБК) 8

JPEG 8

Краткий обзор 8



Преобразование цветов RGB в цвета YUV 8

Метод сжатия JPEG 9

Изменение частоты 9

Усреднение 9

Сжатие методом Хаффмана 9

Фрактальное сжатие 10

Обзор 10

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

Идея метода 11

Сравнение с JPEG 14

Увеличение быстродействия метода. Оценка потерь 15

Возможности видеокомпрессии 16

Заключение 17

Источники 19

Приложение 1. Берегись патентов! 20

Приложение 2. 21


Введение


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

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

Речь пойдет о новом перспективном алгоритме - фрактальном сжатии графической информации.

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

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

Статистическая и визуальная избыточность изображений


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

Существует два типа избыточности:



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

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

Статистическая избыточность изображений


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

Если предположить, что квантованные значения яркости не равновероятны, то уменьшение информации возможно путем изменения количества бит информации для кодирования пикселей: более вероятные кодируются словами с меньшим количеством бит, менее вероятные - с большим. Этот метод называется кодированием словами переменной длины или энтропийным кодированием.

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


  • различные коды могут иметь различное количество бит

  • коды символов с большей частотой встречаемости, имеют больше бит, чем коды символов с меньшей частотой

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

Этими свойствами обладает известный алгоритм Хаффмана.

Визуальная избыточность изображений


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

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


О кодировании цветных изображений


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

Так как глаз человека более чувствителен к изменению яркости, чем к изменению цвета, часто возникает желание преобразовать систему цветов RGB в такую систему, где информация о яркости пикселях запоминалась бы отдельно от информации о цвете. Общеупотребительной системой цветов, которая хранит яркость пикселя в виде отдельной компоненты данных о его цвете, является система HSB (тон, насыщенность, яркость) и YUV (Y - компонента яркости; U и V хранят характеристики цвета).


Обзор алгоритмов сжатия с потерями

Метод усеченного блочного кодирования (УБК)


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

JPEG

Краткий обзор


JPEG - один из самых распространенных и достаточно мощных алгоритмов, представляет собой метод сжатия изображений, реализуемый различными способами. Работает он как на черно-белых, так и на полноцветных изображениях.

Коэффициент архивации в JPEG может изменяться в пределах от 2 до 200 раз. Как и у любого другого алгоритма сжатия с потерями, у JPEG свои особенности. Наиболее известны ‘эффект Гиббса’ и дробление изображения на квадраты. Первый проявляется около резких границ предмета, образуя вокруг своеобразный ‘ореол’. Разбиение на квадраты происходит, когда задается слишком большой коэффициент сжатия для данной картинки. Тем не менее, не смотря на эти недостатки, для архивации изображений, предназначенных для просмотра человеком, он на данный момент является лучшим.


Преобразование цветов RGB в цвета YUV


В сжатии JPEG применяется система цветов YUV. Разделение данных RGB на данные YUV позволяет программе сжатия уделять больше внимание данным о яркости (Y), чем данным о цвете (UV). Этот процесс называется подвыборкой, так как три компоненты выбираются с различной частотой. Так метод подвыборки, который называется YUV411, на каждую выборку цвета делает четыре выборки данных о яркости. Например, если рисунок не подвергался подвыборке, то величины YUV встречаются в нем с одинаковой частотой. При использовании подвыборки YUV411 на шесть значений выборки обработанного файла приходится двенадцать значений выборки исходного файла. Таким образом, подвыборка данных сразу уменьшает размер файла изображения.

Метод сжатия JPEG


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

Изменение частоты


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

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



Усреднение


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

Сжатие методом Хаффмана


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

Фрактальное сжатие

Обзор

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


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

В 1981 году Джон Хатчинсон опубликовал статью "Фракталы и самоподобие", в которой была представлена теория построения фракталов с помощью системы итерируемых функций (IFS, Iterated Function System). Четыре года спустя появилась статья Майкла Барнсли и Стефана Демко, в которой приводилась уже достаточно стройная теория 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); но его несомненным достоинством было то, что вмешательство человека удалось полностью исключить. Сегодня все известные программы фрактальной компрессии базируются на алгоритме Джеквина.

Первые практические результаты были получены Jacquin в 1992 году. Алгоритм основывается на идее подобия между элементами изображения. Коэффициенты сжатия у фрактальных алгоритмов варьируются в пределах 2-2000 раз. Причем большие коэффициенты достигаются на реальных изображениях, что нетипично для предшествующих алгоритмов. Кроме того, при разархивации изображение можно масштабировать. Уникальная особенность этого алгоритма заключается в том, что увеличенное изображение не дробится на квадраты.

В 1993 году вышел первый коммерческий продукт компании Iterated Systems. Ему было посвящено достаточно много публикаций, но о коммерческом успехе речь не шла, продукт был достаточно "сырой", компания не предпринимала никаких рекламных шагов, и приобрести программу было тяжело. В 1994 году Ювал Фишер были предоставил во всеобщее пользование исходные тексты исследовательской программы, в которой использовалось разложение изображения в квадродерево и были реализованы алгоритмы оптимизации поиска. Позднее появилось еще несколько исследовательских проектов, которые в качестве начального варианта программы использовали программу Фишера. В июле 1995 года в Тронхейме (Швеция) состоялась первая школа-конференция, посвященная фрактальной компрессии.


Идея метода


Фрактальная архивация основана на том, что мы представляем изображение в более компактной форме - с помощью коэффициентов системы итерируемых функций (Iterated Function System - далее по тексту как IFS). Прежде, чем рассматривать сам процесс архивации, разберем, как IFS строит изображение, т.е. процесс декомпрессии.
Строго говоря, IFS представляет собой набор трехмерных аффинных преобразований, в нашем случае переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (х_координата, у_координата, яркость).
Наиболее наглядно этот процесс продемонстрировал Барнсли в своей книге «Fractal Image Compression». Там введено понятие Фотокопировальной Машины, состоящей из экрана, на котором изображена исходная картинка, и системы линз, проецирующих изображение на другой экран:

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

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

  • Линза может менять яркость и уменьшать контрастность.

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

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

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


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


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

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





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

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

Сравнение с JPEG


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

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

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

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

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

Увеличение быстродействия метода. Оценка потерь


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

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



Возможности видеокомпрессии


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

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

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

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



Заключение


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

Но, все же, есть один существенный недостаток, который полностью перекрывает все достоинства фрактального сжатия. Это - высокая ресурсоемкость, а вследствие этого - большое время сжатия. Можно оценить трудоемкость алгоритма. При сжатии без дроблений блоков она пропорциональна произведению мощности множества доменов на мощность множества блоков. При сжатии с дроблением каждого блока трудоемкость возрастает приблизительно в 16 раз. Более того, так как мощности множеств доменов и блоков квадратично зависят от линейных размеров изображения, то трудоемкость алгоритма будет пропорциональна R^4, где R - это размер изображения. То есть время сжатия растет настолько быстро с увеличением размеров изображения, что о сжатии изображений размером более 1024x1024 пикселей даже на самом быстром имеющимся на сегодняшний день персональном компьютере не может быть и речи!

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

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

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


Источники





  1. http://iitam.omsk.net.ru/~eremeev/fract_r.htm

  2. http://www.bsu.ru/library/berson/fragsjatie.html

  3. http://compression.graphicon.ru/book/part2/part2__3.htm#_Toc448152512

  4. http://shaos.ru/fractals/paper3/

  5. http://www.osp.ru/cw/1996/06/30_print.htm

  6. http://www.armosystems.ru/system/compression_mpeg.ahtm

  7. http://public.tsu.ru/~shab/progs/fc200.zip (программа для фрактального сжатия изображений (исходники))

  8. http://mylib.by.ru/fraktal/frakt.htm

Приложение 1. Берегись патентов!


Специфическая проблема, с которой приходится сталкиваться при реализации алгоритма фрактальной компрессии, - проблема лицензирования. На алгоритм в 1990 году Майкл Барнсли и Алан Слоан получили патент № 4.941.193, а в !991 году Барнсли получил второй патент N 5.065447 В них рассматривается модифицированная схема представления изображения, названная Разделенная Система Итерируемых Функций (Partitioned IFS), и алгоритм автоматически переводит изображение в PIFS.

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

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

Известный судебный процесс по поводу MS DOS 6.0 был спровоцирован незаконным использованием корпорацией Microsoft алгоритма LZRW1, правами на который обладает компания Stac. Интересно, что правами на такой же алгоритм обладает и фирма Gibson&Graybill, поскольку патентное бюро США не смогло в свое время установить, что выдает патент на очень похожий алгоритм. Отметим также, что Рос Вильямс, именем которого назван алгоритм, не имеет к этим двум патентам никакого отношения...

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

Приложение 2.




Рисунок 1. «Lena.bmp» - оригинал

Алгоритм с фиксированным размером блоков



«Lena.fif» – закодированное.

Размер областей пикселей.

Сжатие 4:1. PSNR = 31.4dB.

Время 773 сек.



«Lena.fif» – закодированное.

Размер областей пикселей.

Сжатие 16:1. PSNR = 27.18dB.

Время 1011 сек.

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



«Lena.fif» – закодированное.

Начальный размер областей пикселей.

Сжатие 7.2:1. PSNR = 29.4dB.

Время 1938 сек.



«Lena.fif» – закодированное.

Начальный размер областей пикселей.

Сжатие 7.2:1. PSNR = 29.4dB.

Время 3650 сек.

Процесс восстановления. 1,2,3,4,5,15 – итерации





Сжатие цветных изображений



Рисунок 2. «Heron.bmp» - оригинал



«Heron.fif» - закодированное.

Сжатие 3:1.



«Heron.fif» - закодированное.

Сжатие 6.5:1.






Нельзя стать хорошим солдатом без некоторой доли глупости. Флоренс Найтингейл
ещё >>