Компьютерная графика: Методические указания к самостоятельной работе студентов на практических занятиях по информатике, страница 5

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

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

Таблица 1

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

Цвет	Частота появления	Длина цепочки	Цепочка битов
Розовый	9631	1	0
Желтый	3286	3	100
Черный	1957	3	101
Зеленый	1785	4	1100
Красный	1470	4	1101
Синий	873	4	1110
Белый	627	5	11110
Серый	371	5	11111

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

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

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; информация о яркости хранится для каждого пикселя отдельно, а цвет – в общем для всех пикселей блоке (уже одно это позволяет уменьшить хранимый объем изображе­ния в два раза при незначительной потере качества).

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

2.4. Форматыграфическихфайлов

Для того чтобы программа могла загрузить графический файл, ей должен быть «знаком» формат этого файла, чтобы знать, что, откуда и как из него прочесть. Если программа может работать с определенным форматом, то говорят, что она поддерживает этот формат. Например, редактор Paint поддерживает форматы BMPи JPEG.

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

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

Формат PCX фирмы ZSoft – один из наиболее старых и широко поддерживаемых форматов для персонального компьютера. Благодаря простоте формата PCX начинающие программисты пользуются именно им. Многие профессиональные графические пакеты также поддерживают формат PCX. Этот формат использует самый простой вид сжатия – RLE, по этой причине он хорошо подходит для хранения рисунков и чертежей, но не годится для хранения
фотографий.