ЛекцииММ2 (Курс электронных лекций), страница 6

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

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

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

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

Симметричность. Характеризует ресурсоемкость процессов кодирования и декодирования. Для нас наиболее важными являются два коэффициента: отношение времени кодирования ко времени декодирования и требования на память.

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

Характерные особенности алгоритма и изображений, к которым его применяют.

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

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

Большое распространение сейчас получили издательские системы. Программы верстки типа PageMaker, QuarkXPress, Ventura есть на очень многих персональных компьютерах. В подобных системах приходится иметь дело с полноцветными изображениями самого разного размера (от 640х480 до 3000x2000) и с большими двуцветными изображениями. Поскольку иллюстрации занимают львиную долю от общего объема материала в документе, проблема хранения стоит очень остро. Изображение, соответствующее рекламной странице журнала, занимает до 20 Мб. А в номере их, естественно, несколько. Кроме того, немало могут занимать и иллюстрации к самим статьям. В результате средний журнал в 100 страниц может занимать больше 500 Мб. То же самое относится и к хорошо изданным книгам, буклетам, брошюрам. Проблемы также создает большая разнородность иллюстраций. Единственное, что можно сказать заранее, это то, что будут преобладать фотореалистичные изображения и деловая графика.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К положительным сторонам алгоритма, пожалуй, можно отнести только то, что он не требует дополнительной памяти при работе, и быстро выполняется. Ориентирован алгоритм на изображения с небольшим количеством цветов: деловую и научную графику. Применяется в форматах РСХ, TIFF, ВМР.

LZW

Собственно исходный Lempel/Ziv подход к сжатию данных был впервые обнародован в 1977г., а усовершенствованный (Terry Welch) вариант был опубликован в 1984г. LZW - код (Lempel-Ziv & Welch) является на сегодняшний день одним из самых распространенных кодов сжатия без потерь. Именно с помощью LZW-кода осуществляется сжатие в таких графических форматах, как TIFF и GIF, с помощью модификаций LZW осуществляют свои функции очень многие универсальные архиваторы. Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек.

Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселей. Реализация алгоритма LZW жестко зафиксирована международным стандартом и Американским Национальным институтом стандартов (ANSI), однако существуют достаточно интересные его модификации, которые дают больший коэффициент сжатия некоторых специфичных типах файлов - например, на исходных текстах программ.

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

Отсутствие потерь информации при LZW-кодировании обусловило широкое распространение основанного на нем формата TIFF. Этот формат не накладывает каких-либо ограничений на размер и глубину цвета изображения и широко распространен, например, в полиграфии. Другой основанный на LZW формат - GIF - более примитивен - он позволяет хранить изображения с глубиной цвета не более 8 бит/пиксельь. В начале GIF - файла находится палитра. Это таблица, устанавливающая соответствие между индексом цвета - числом в диапазоне от 0 до 255 и истинным, 24-битным значением цвета.

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

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

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

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

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

Кодирование Хаффмана, вероятно, самый известный и классический метод сжатия данных. Простота и элегантность способа сделали его на долгое время академическим фаворитом. Но коды Хаффмана имеют и практическое применение; например, статические коды Хаффмана используются на последнем этапе сжатия JPEG. Кодирование Шеннона - Фано (Shannon - Fano), довольно близкое к кодированию Хаффмана, используется как один из этапов в мощном "imploding" - алгоритме программы PKZIP.

Кодирование Хаффмана работает на предпосылке, что некоторые символы используются в представлении данных чаще, чем другие. Наиболее общее представление - алфавит ASCII - использует 8 бит для каждого символа. В английском языке буква e явно будет чаще встречаться, чем буква q, хотя мы используем для их представления одинаковое количество бит. Если мы используем только 4 бита для e и 12 бит для q, мы могли бы выиграть несколько бит, сохраняя английский текст.