Вопросы по информации, представленной на сайте, а также по фрактальному сжатию можно задать, обратившись по адресу fic [at] bos.ru с пометкой "Фрактальное сжатие" (он-лайн форма).

Список программных проектов

Информация по размещению баннера данного ресурса доступна здесь.

Закажите книгу
"Фрактальное сжатие изображений. Реализация и исследование алгоритмов"

Заказать (ljubljuknigi)
Заказать на Setbook

Подписаться на рассылку
"Фрактальное сжатие изображений"
 

Тенденции развития алгоритмов сжатия статических растровых изображений

Автор: Д.С.Ватолин "Тенденции развития алгоритмов архивации графики"
Источник: Журнал Открытые системы. Номер 4. Зима 1995
Ссылка: http://www-lat.compression.graphicon.ru/arctest/descript/rastr-comp.htm
Добавлено: 12 Октября 2010

Введение

В последнее время изображения и иллюстрации стали использоваться повсеместно. Проблема, связанная с их большим размером, появилась при работе и на рабочих станциях, и на персональных компьютерах. Так, одно полноэкранное (640х480) полноцветное TrueColor - 24 бита на точку) изображение занимает почти мегабайт. Учитывая то, что обычно используется несколько иллюстраций, и то, что они часто бывают гораздо большего размера (например при цветной печати), держать их в неупакованном виде становится накладно. В последние годы решению этой проблемы уделяется достаточно серьезное внимание. Разработано большое количество различных алгоритмов архивации графики: использовались как видоизмененные универсальные, так и абсолютно новые алгоритмы, ориентированные только на изображения. Более того, были разработаны алгоритмы, ориентированные только на конкретный класс изображений. В этой статье сделана попытка выделить основные тенденции развития алгоритмов архивации статической графики.

Основные понятия

Для того, чтобы вести речь об изображениях, необходимо определить, что под ними понимается. В статье будут рассмотрены статические растровые изображения, представляющие собой двумерный массив чисел - пикселов. Все изображения можно подразделить на две группы: с палитрой и без нее. У изображений с палитрой в пикселе хранится число - индекс в некотором одномерном векторе цветов, называемом палитрой. Чаще всего встречаются палитры из 16 и 256 цветов.
Изображения без палитры бывают в какой-либо системе цветопредставления и в градациях серого. Для последних значение каждого пиксела интерпретируется как яркость соответствующей точки. Встречаются изображения с 2, 16 и 256 уровнями серого. Одна из простых, но интересных задач заключается в приведении цветного или черно-белого изображения к двум градациям яркости, например, для печати на лазерном принтере. При использовании некой системы цветопредставления каждый пиксел представляет собой запись (структуру), полями которой являются компоненты цвета. Самой распространенной является система RGB, в которой цвет представлен значениями интенсивности красного (В), зеленого (G) и синего (В) компонента. Существуют и другие системы цветопредставления, такие, как CMYK, CIE XYZccir60-1 и т.п.

Классы изображений

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

Рассмотрим следующие примеры неформального определения классов изображений:
- изображения с небольшим количеством цветов (4-16) и большими областями, заполненными одним цветом (примеры: деловая графика - гистограммы, диаграммы, графики и т.п.);
- изображения, с использованием плавных переходов, построенные на компьютере (примеры: графика презентаций, эскизные модели в САПР, изображения построенные по методу закраски Гуро);
- фотореалистичные изображения (пример: отсканированные фотографии);
- фотореалистичные изображения с наложением деловой графики.

В качестве отдельных классов могут быть предложены некачественно отсканированные в 256 градаций серого цвета страницы журналов или растровые изображения топографических карт. Формально являясь 8 или 24-битными, они несут даже не растровую, а векторную информацию. Отдельные классы могут образовывать и совсем специфичные изображения: рентгеновские снимки или фотографии в профиль и фас из электронного досье.
Достаточно сложной и интересной задачей является поиск наилучшего алгоритма для конкретного класса изображений.

Критерии оценки алгоритмов

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

  1. Худший, средний и лучший коэффициенты сжатия. То есть доля, на которую возрастет размер изображения, если исходные данные будут наихудшими; некий среднестатистический коэффициент для того класса изображений, на который ориентирован алгоритм; и, наконец, лучший коэффициент. Последний необходим лишь теоретически, поскольку показывает степень сжатия наилучшего (как правило, абсолютно черного) изображения, не редко - фиксированного размера.
  2. Класс изображений, на который ориентирован алгоритм. Иногда указано также, почему на других классах изображений получаются худшие результаты.
  3. Симметричность. Характеризует ресурсоемкость процессов кодирования и декодирования. Для нас наиболее важными являются два коэффициента: отношение времени кодирования ко времени декодирования и требования на память.
  4. Есть ли потери качества? И если есть, то за счет чего изменяется коэффициент архивации? Дело в том, что у большинства алгоритмов сжатия с потерей информации существует возможность изменения коэффициента сжатия.
  5. Характерные особенности алгоритма и изображений, к которым его применяют.

Приложения, использующие статическую графику

Проанализируем, какими бывают приложения, использующие статическую графику, и какие требования к алгоритмам они выдвигают.
- Большое распространение сейчас получили издательские системы. Программы верстки типа PageMaker, QuarkXPress, MS WinWord есть на очень многих персональных компьютерах. В подобных системах приходится иметь дело с полноцветными изображениями самого разного размера (от 640х480 до 3000x2000) и с большими двуцветными изображениями. Поскольку иллюстрации занимают львиную долю от общего объема материала в документе, проблема хранения стоит очень остро. Изображение, соответствующее рекламной странице журнала, занимает до 20 Мб. А в номере их, естественно, несколько. Кроме того, немало могут занимать и иллюстрации к самим статьям. В результате средний журнал в 100 страниц может занимать больше 500 Мб. То же самое относится и к хорошо изданным книгам, буклетам, брошюрам...
Проблемы также создает большая разнородность иллюстраций. Единственное, что можно сказать заранее, это то, что будут преобладать фотореалистичные изображения и деловая графика.
- Другим примером являются справочники и энциклопедии на CD-ROM. С появлением большого количества компьютеров, оснащенных этим приводом (В США - у 50% машин) достаточно быстро сформировался рынок программ, выпускаемых на лазерных дисках. Несмотря на то, что емкость одного диска довольно велика (примерно 650 Мб), ее, как правило, не хватает. При создании энциклопедий и игр большую часть диска занимают статические изображения и видео. Таким образом, для этого класса приложений актуальность приобретают существенно асимметричные алгоритмы.
- Похожие требования к алгоритмам архивации выдвигает и быстро развивающаяся система "Всемирная информационная паутина" - World Wide Wed (WWW). В этой гипертекстовой системе достаточно активно используются иллюстрации. При оформлении информационных или рекламных страниц хочется сделать их более яркими и красочными. Больше всего при этом страдают пользователи, подключенные к сети с помощью медленных каналов связи. Если страница WWW перенасыщена графикой, то ожидание ее полного появления на экране может затянуться. Поскольку при этом нагрузка на процессор мала, то здесь могут найти применение эффективно сжимающие сложные алгоритмы со сравнительно большим временем разархивации.
- Свое применение машинная графика находит и в различных информационных системах. Например, уже становится привычным исследовать ультразвуковые и рентгеновские снимки не на бумаге, а на экране монитора. Постепенно в электронный вид переводят и истории болезней. Понятно, что хранить эти материалы логичнее в единой картотеке. При этом без использования специальных алгоритмов большую часть архивов займут фотографии. Поэтому при создании эффективных алгоритмов решения этой задачи нужно учесть специфику рентгеновских снимков - преобладание размытых участков.
- В геоинформационных системах - при хранении аэрофотоснимков местности - специфическими проблемами являются большой размер изображения и необходимость выборки лишь части изображения по требованию. Кроме того, может потребоваться масштабирование. Это неизбежно накладывает свои ограничения на алгоритм компрессии.
- В электронных картотеках и досье различных служб для изображений характерно подобие между фотографиями в профиль, и подобие между фотографиями в фас, которое также необходимо учитывать при создании алгоритма архивации. Подобие между фотографиями наблюдается и в любых других специализированных справочниках. В качестве примера можно привести энциклопедии птиц или цветов. Однако там различие между рисунками значительно больше и использовать подобие сложнее.

Особенности алгоритмов

Первыми для архивации изображений стали применяться привычные алгоритмы. Те, что использовались и используются в системах резервного копирования, при создании дистрибутивов и т.п. Однако время не стоит на месте, и основной тенденцией сегодня стало использование новых классов изображений. Старые алгоритмы перестали удовлетворять требованиям, предъявляемым к архивации. Многие изображения практически не сжимались, хотя "на взгляд" обладали явной избыточностью. Это привело к созданию нового типа алгоритмов - сжимающих с потерей информации. Как правило, в них можно задавать коэффициент архивации и, следовательно, степень потерь качества. При этом достигается компромисс между размером и качеством изображений.
Одна из серьезных проблем машинной графики заключается в том, что до сих пор не найден адекватный критерий оценки потерь качества изображения. А теряется оно постоянно - при оцифровке, при переводе в ограниченную палитру цветов, при переводе в другую систему цветопредставления для печати, и, что для нас особенно важно, при архивации с потерями. Можно привести пример простого критерия: среднеквадратичное отклонение значений пикселов согласно которому изображение будет сильно испорчено при понижении яркости всего на 5% (глаз этого не заметит - у разных мониторов настройка яркости варьируется гораздо сильнее). В то же время изображения со "снегом" - резким изменением цвета отдельных точек, слабыми полосами или "муаром" будут признаны "почти не изменившимися". Свои неприятные стороны есть и у других критериев. Таким образом, необходим критерий, учитывающий всевозможные пространственные регулярные эффекты, который, оказывается, не так просто построить.
Лучше всего потери качества изображений оценивают наши глаза. Отличной считается архивация, при которой невозможно на глаз различить первоначальное и раскодированное изображения. Хорошей - когда сказать, какое из изображений подвергалось архивации, можно только сравнивая две находящихся рядом картинки.
При дальнейшем увеличении степени сжатия, как правило, становятся заметны побочные эффекты, характерные для данного алгоритма. На практике, даже при отличном сохранении качества, в изображение могут быть внесены специфические регулярные изменения. Поэтому алгоритмы архивации с потерями не рекомендуется использовать при сжатии изображений, которые в дальнейшем собираются либо печатать с высоким качеством, либо обрабатывать программами распознавания образов.

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

Алгоритмы сжатия без потерь

Групповое кодирование

Групповое кодирование - Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных далее) вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары "счетчик, значение" уменьшает избыточность данных. Лучший, средний и худший коэффициенты сжатия - 1/32, 1/2, 2/1. Ситуация, когда файл увеличивается в два раза, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям.
К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при работе, и быстро выполняется. Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

LZW

Название алгоритм получил по первым буквам фамилий его разработчиков - Lempel, Ziv и Welch. Сжатие в нем, в отличие от РСХ, осуществляется уже за счет одинаковых цепочек байт. Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек. Коэффициенты сжатия: 1/1000, 1/4, 7/5. Коэффициент 1/1000 достигается только на одноцветных изображениях размером больше 4 Мб. Ориентирован LZW на 8-битные изображения, построенные на компьютере. Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко. LZW универсален - именно его варианты используются в обычных архиваторах. Он реализован в форматах GIF, TIFF и TGA.

Алгоритм Хаффмана

Один из классических алгоритмов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И напротив - встречающимся редко - цепочку большей длины. Для сбора статистики требует двух проходов по изображению. Коэффициенты сжатия: 1/8, 2/3, 1. Требует записи в файл таблицы соответствия кодируемых символов и кодирующих цепочек. На практике используются его разновидности. Так, в некоторых случаях резонно либо использовать постоянную таблицу, либо строить ее "адаптивно", т.е. в процессе архивации/разархивации. Эти приемы избавляют от двух проходов по изображению и необходимости хранения таблицы вместе с файлом. Кодирование с фиксированной таблицей применяется в качестве последнего этапа архивации в JPEG.
Близкая модификация алгоритма используется при сжатии черно-белых изображений. Последовательности подряд идущих черных и белых точек заменяются числом, равным их количеству с признаком цвета. А этот ряд уже, в свою очередь, сжимается по Хаффману с фиксированной таблицей. Алгоритм реализован в формате TIFF.

JBIG

Алгоритм разработан группой экспертов ISO (Joint Bi-level Experts Group) специально для сжатия однобитных черно-белых изображений. Например, факсов или отсканированных документов. В принципе может применяться и к 2-х, и к 4-х битовым картинкам. При этом алгоритм разбивает их на отдельные битовые плоскости. JBIG позволяет управлять такими параметрами, как порядок разбиения изображения на битовые плоскости, ширина полос в изображении, уровни масштабирования. Последняя возможность позволяет легко ориентироваться в базе больших по размерам изображений, просматривая сначала их уменьшенные копии. Настраивая эти параметры, можно использовать интересный эффект при получении изображения по сети или по любому другому каналу, пропускная способность которого мала по сравнению с возможностями процессора. Распаковываться изображение на экране будет постепенно, как бы медленно "проявляясь". При этом человек начинает анализировать картинку задолго до конца процесса разархивации.
Алгоритм построен на базе Q-кодировщика, патентом на который владеет IBM. Q-кодер также, как и алгоритм Хаффмана, использует для чаще появляющихся символов короткие цепочки, а для реже появляющихся длинные. Однако, в отличие от него, в алгоритме используются и последовательности символов. Характерной особенностью JBIG является резкое снижение степени сжатия при повышении уровня шумов входной картинки.

Lossless JPEG

Этот алгоритм, разработан группой экспертов в области фотографии (Joint Photographic Expert Group). В отличие от JBIG, Lossless JPEG ориентирован на полноцветные 24-битные безпалитровые изображения. Он представляет собой специальную реализацию JPEG без потерь. (JPEG см. "Открытые системы сегодня" # 8(29) за 1995 год). Коэффициенты сжатия: 1/20, 1/2, 1. Lossless JPEG рекомендуется применять в тех приложениях, где необходимо побитовое соответствие исходного и разархивируемого изображений.
Попробуем на этом этапе сделать некоторые обобщения. С одной стороны, приведенные алгоритмы достаточно универсальны и покрывают все типы изображений, с другой - у них, по сегодняшним меркам, слишком маленький коэффициент архивации. Используя один из алгоритмов сжатия без потерь, можно обеспечить коэффициент архивации изображения примерно в два раза. В то же время алгоритмы сжатия с потерями оперируют с коэффициентами 10-200 раз. Помимо возможности модификации изображения, одна из основных причин подобной разницы заключается в том, что традиционные алгоритмы ориентированы на работу с цепочкой. Они не учитывают так называемую "когерентность областей" в изображениях. Идея когерентности областей заключается в малом изменении цвета и структуры изображения на небольшом участке. Все алгоритмы, о которых речь пойдет ниже, были созданы позднее специально для сжатия графики и используют эту идею.
Справедливости ради следует отметить, что и в классических алгоритмах можно использовать идею когерентности. Существуют алгоритмы обхода изображения по "фрактальной" кривой, при работе которых оно также вытягивается в цепочку; но за счет того, что кривая обегает области изображения по сложной траектории, участки близких цветов в получающейся цепочке удлиняются.

Алгоритмы сжатия с потерями

Рекурсивное сжатие

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

Алгоритм

Цепочки, за счет которых происходит сжатие

Групповое кодирование

2 2 2 2 2 2 2 15 15 15 - Подряд идущие цвета

LZW

2 3 15 40 2 3 15 40 - Одинаковые подцепочки

Хаффмана

2 2 3 2 2 4 3 2 2 2 4 - Разная частота появления цвета

Рекурсивный

Плавные переходы цветов и отсутствие резких границ

JPEG

Отсутствие резких границ

Фрактальный

Подобие между элементами изображения

JPEG

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

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

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

Широкое применение JPEG сдерживается, пожалуй, лишь тем, что он оперирует 24-битными изображениями. Поэтому для того, чтобы с приемлемым качеством посмотреть картинку на обычном мониторе в 256-цветной палитре, требуется применение соответствующих алгоритмов и, следовательно, определенное время. В приложениях, ориентированных на придирчивого пользователя, таких, например, как игры, подобные задержки неприемлемы. Кроме того, если имеющиеся у вас изображения, допустим, в 8-битном формате GIF перевести в 24-битный JPEG, а потом обратно в GIF для просмотра, то потеря качества произойдет дважды при обоих преобразованиях. Тем не менее выигрыш в размерах архивов зачастую настолько велик (в 3-20 раз!), а потери качества настолько малы, что хранение изображений в JPEG оказывается очень эффективным. JPEG реализован в форматах JPG и TIFF.

Несколько слов необходимо сказать о модификациях этого алгоритма. Хотя JPEG и является стандартом ISO, формат его файлов не был зафиксирован. Пользуясь этим, производители используют свои, несовместимые между собой форматы, и, следовательно, могут изменить алгоритм. Так, внутренние таблицы алгоритма, рекомендованные ISO, заменяются ими на свои собственные. Кроме того, легкая неразбериха присутствует при задании степени потерь. Например, при тестировании выясняется, что "отличное" качество, "100%" и "0 баллов" дают существенно различающиеся картинки. При этом, кстати, "100%" качества не означает сжатия без потерь. Встречаются также варианты JPEG для специфических приложений.

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

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

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

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

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

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

Резюме


Алгоритм

Коэфф-ты сжатия

Симметричность по времени

На что ориентирован

Потери

Размерность

Групповое кодирование

1/32 1/2 2/1

1

3,4 битные

Нет

1D

LZW

1/100 1/4 7/5

1.2-3

1-8 битные

Нет

1D

Хаффмана

1/8 2/3 1/1

1-1.5

1-битные

Нет

1D

JBIG

1.5 раза

~1

1-битные

Нет

2D

Lossless JPEG

2 раза

~1

24-битн. сер.

Нет

2D

Рекурс. сжатие

2-20 раз

1.5

серые

Да

2D

JPEG

2-200 раз

~1

24-битн. сер.

Да

2D

Фрактальный

2-2000 раз

1000-10000

24-битн. сер.

Да

2D

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

Заключение

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

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

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

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

Библиографический список

  1. G.K.Wallace. "The JPEG still picture compression standard". Communication of АСМ, Volume 34, Number 4, April 1991.
  2. B.Smith, L.Rowe. "Algorithm for manipulating compressed images", Computer Graphics and applications, September 1993.
  3. R.W.McColl, G.R.Martin. "Compression of color image data usinf histogram analysis and clustering techniques". Electronics & communication engineering journal, March / April 1989.
  4. А. Jacquin, "Fractal image coding based on а theory of iterated contractive image transformations", Visual Comm. and Image Processing, v. SPIE-1360, 1990.
  5. Y. Fisher, "Fractal image compression", Siggraph'92.
  6. "Progressive Bi-level Image Compression, Revision 4.1", ISO/IEC JTC1/SC2/WG9, CD 11544, September 16, 1991.
  7. W.B. Pennebaker, J.L. Mitchell, G.G. Langdon, R.B. Arps, "An overview of the basic principles of the Q-coder adaptive binary arithmetic coder", IBM Journal of research and development, Vol.32, No.6, November 1988, рр. 771-726.
  8. D.A. Huffman, "А method for the construction of minimum redundancy codes." In processing. IRE vol.40, 1962, рр. 1098-1101.
  9. Standartization of Group 3 Facsimile apparatus for document transmission, CCITT Recomendations, Fascicle VlI.2, Т.4. 1980.
  10. Д. Ватолин, MPEG - стандарт ISO на видео в системах мультимедиа, "Открытые системы", #3, 1995.
Website templates by JustDreamweaver.com