Сжатие графической информации

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

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

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

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

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

2.3.1. Сжатие без потерь

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

Алгоритм RLE (Run-Length Encoding – кодирование длины серии) часто называют алгоритмом группового сжатия, так как одинаковые данные группируются в процессе сжатия. Когда говорят об однородных объектах, то обычно их группируют, называя общее количество, вместо того, чтобы называть каждый по отдельности. Например, проще сказать: «В нашей группе учится 30 студентов», чем: «В нашей группе учится студент, студент, студент, ...». Точно такой же принцип используется в алгоритме RLE: если в изображении подряд идут несколько одинаковых пикселей, то записывается не каждый из них отдельно, а лишь их общее количество и цвет.

Рассмотрим пример. Предположим, что исходное изображение хранится в режиме 16 цветов. Числом 8 кодируется ярко-красный цвет, 14 – желтый, а числом 10 – ярко-зеленый. Исходная цепочка пикселей будет следующей: 8, 8, 8, 8, 8, 14, 14, 14, 10, 10, 10, 10, 10, 10, 14, 14, 14, а сжатая – 5, 8, 3, 14, 6, 10, 3, 14, где первая цифра означает количество пикселей, а вторая – их цвет. В результате сжатия цепочка стала короче более чем в два раза.

Алгоритм Хаффмана. При хранении изображения в обычном виде на
каждый пиксель выделено одинаковое количество битов, зависящее от используемого режима. Например, для кодирования восьми цветов достаточно трех бит. Это означает, что для хранения восьмицветного изображения размером
100 × 200 пикселей потребуется 100 × 200 × 3 = 60 000 бит = 7 500 байт.

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

Возьмем то же самое восьмицветное изображение размером 100 × 200. Пример распределения частот появления цветов на этом изобра­жении приведен в табл. 1.

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

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

Таблица 1

Сжатие графических данных по алгоритму Хаффмана

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

Итак, сжатое с помощью алгоритма Хаффмана изображение будет
занимать:

9631·1 + 3286·3 + 1957·3 + 1785·4 + 1470·4 + 873·4 +

+627·5 + 371·5 = 46 862 бит / 1024 = 5 858 байт.

Исходное изображение занимало 7 500 байт, а сжатое – 5 858 байт, т. е. примерно на 22 % меньше. Конечно, результат не очень впечатляющий, зато
в отличие от алгоритма при сжатии изображения по RLE алгоритму Хаффмана неважно, стоят ли одинаковые пиксели подряд или нет, важно лишь их общее количество на изображении. Любой дисбаланс в частоте появления цветов
позволяет сократить размер, занимаемый изображением в памяти.

Алгоритм LZW, названный по инициалам его изобретателей (Lempel, Ziv, Welch), основан на замене цепочек байтов более короткими кодами. Графи­ческие данные в режиме полутонов или индекси­рованных цветов зачастую имеют много повторяющихся цепочек. Программа, использующая алгоритм LZW, последовательно пробегает по сжимаемому файлу, и когда она обнаруживает новую цепочку, то по­мещает ее в таблицу и присваивает более короткий «кодовый номер». Если такая же цепочка встретится вновь, то вместо того чтобы цели­ком ее повторять, программа запишет в выходной файл кодовый но­мер. Чем чаще цепочка повторяется в файле, тем больший эффект от использования кодового номера.

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

Для сжатия изображений фотореалистичного качества этот алгоритм малоэффективен.

2.3.2. Сжатие с потерями

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

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

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

Наиболее популярным алгоритмом сжатия с потерями является JPEG-сжатие, разработанное объединенной группой экспертов по фотографии (Joint Photographic Experts Group).

Сжатие с потерями основано на некоторых особенностях воспри­ятия информации человеческим глазом. Во-первых, человек обращает больше внимания на крупные детали изображения. Мелкие детали, размером в один – два пикселя, воспринимаются не очень точно, если спе­циально не вглядываться. При просмотре изображения на некотором расстоянии соседние пиксели вообще сливаются друг с другом. Таким образом, небольшое искажение цвета мелких деталей вряд ли будет заметно человеку. Во-вторых, человек лучше воспринимает яркость, чем цвет. Можно добиться экономии, если отбросить часть информации о цвете, но сохранить информацию о яркости. Обычно с этой
целью пиксели группируются в блоки размером 2 × 2; информация о яркости хранится для каждого пикселя отдельно, а цвет – в общем для всех пикселей блоке (уже одно это позволяет уменьшить хранимый объем изображе­ния в два раза при незначительной потере качества).

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: