Сжатие по способу RLE

В стандартах PCX и BMP предусмотрены простые алгоритмы упаковки и распаковки данных, которые называются Run Length Encoding или RLE. Реализация способа RLE в этих стандартах различается в деталях, но суть остается неизменной. Она заключается в том, что группа повторяющихся кодов заменяется двумя

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

Способ RLE основан на анализе содержимого соседних байтов. У рисунков, подготовленных с применением палитры, в них находятся коды смежных точек. А у полноцветных рисунков в каждой тройке подряд расположенных байтов хранятся базовые цвета точек, и проверять их совпадение не имеет смысла. Коды базовых цветов совпадают только у точек, окрашенных в оттенки серого цвета. Из 16М возможных комбинаций на оттенки серого цвета приходится всего 256!

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

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

Таблица 7.5. Результат сжатия трех полноцветных рисунков

Содержание рисунка	Размер рисунка	Количество цветов	Размер файла в байтах
BMP	PCX	JPEG
Значок	99x40	251	12054	12656	1565
Фотография	184x246	22 158	135846	90302	7460
Ландшафт	736x497	41 682	1 097 430	1 079 973	138964

Табл. 7.5 иллюстрирует недостатки способа сжатия RLE и очевидное преимущество стандарта JPEG. Приведенные в ней данные получены в результате преобразования файлов из формата JPG в форматы BMP (не упакованный файл) и PCX (упаковка по способу RLE).

Из табл. 7.5 видно, что только в одном случае файл формата PCX оказался короче файла формата BMP примерно на 35%. Это произошло потому, что на фотографии женское лицо окружает довольно большое пространство одноцветного фона. В двух остальных случаях сжатие по способу RLE не дает ощутимых результатов. Причина кроется не только в недостатках способа сжатия, но и в самих рисунках.

Применение палитры ограничивало разнообразие кодов точек до 256, поэтому в рисунках неизбежно повторялись одноцветные точки и их комбинации. В этих условиях алгоритм LZW, реализованный в стандарте GIF (см. раздел), обеспечивал вполне удовлетворительные результаты.

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

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

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

Цветовое пространство YUV

Трехмерное пространство света, у которого яркость и цвет являются независимыми компонентами, обычно обозначается YUV или УСЬСГ, в англоязычной технической литературе его называют "luminance/chrominance color space". Точная расшифровка аббревиатуры YUV автору неизвестна. Входящие в нее буквы обозначают следующие величины: Y — светимость (luminance), и — синий цвет, v — красный цвет. Во втором варианте записи сь является сокращением слов chrominance-blue, а сr — chrominance-red. Обратите внимание, в данном случае при описании компонент английские слова "яркость" и "цвет" не употребляются, поскольку мы имеем дело с некими абстрактными или обобщенными величинами.

Уравнения, связывающие пространство RGB с пространством YUV, приведены в табл. 7.6. Значения коэффициентов уравнений определяются на основании анализа кривой спектральной чувствительности приемника света, которым в данном случае является человеческий глаз.

Таблица 7.6. Уравнения для преобразования пространства цветов

RGB->YUV	YUV->RGB
Y = 0.299R + 0,5870 + 0,114В	R = Y+ 1,134V
U = 0,434В - 0.146R - 0,2880	G = Y- 0,578V -0,396U
V = 0.617R - 0,5170 - 0,100В	В = Y + 2.045U

Простой визуальный анализ показывает, что наибольший вклад в значение компоненты Y вносит зеленый цвет, к которому наиболее чувствителен глаз человека. В значение компоненты и основной вклад вносит синий цвет, а компоненты v — красный. Точкам серого цвета, у которых R=G=B=k соответствуют Y=k,U=V=0. Таким образом, компонента Y соответствует яркости точек серого цвета.

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

Замечание
В группу прерывания int lOh входит функция, имеющая код lOlBh. Она преобразует цвета R,G,B в оттенки серого по формуле Y = 0,299R + 0,587G + 0,114В.

В описании стандарта VESA перечислено 8 кодов моделей видеопамяти. Как уже говорилось в главе 1 (см. раздел ), на практике используются только 4 из них. К числу названных, но не используемых относится и модель YUV. Причем отсутствуют даже намеки на ее возможные характеристики. Это объясняется тем, что в простых видеокартах она не применяется. Зато современные акселераторы, как правило, выполняют преобразования, описанные в табл. 7.6. Они применяются, например, в тех случаях, когда при построении трехмерных графических объектов светимость точек зависит от расстояния до источника света, а цвет при этом не изменяется.

При использовании способа JPEG преобразование RGB -> YUV предшествует сжатию графического изображения, а обратное преобразование выполняется после его распаковки. Покажем, что это дает на двух примерах.

Предположим, что рисунок содержит N точек и занимает в памяти зы байтов. Если в нем использованы только различные оттенки серого цвета, в пространстве YUV останется только одна компонента Y, а и и v будут содержать нули. То есть еще до сжатия занимаемое изображением пространство сокращается в три раза.

Другой пример, можно усреднить цвета четырех смежных точек, расположенных в квадрате размером 2x2 точки, оставив без изменения их светимость. При этом размеры компонент и и v сократятся в 4 раза, а пространство, занимаемое всем рисунком, сократится в 2 раза. В зависимости от степени различия усредняемых цветов, воспроизведенный рисунок будет несколько отличаться от оригинала. Если оригинал не содержал контрастных точек, то это различие окажется незаметным для человеческого глаза.

Таким образом, пространство цвета YUV позволяет решать те задачи, решение которых при работе с пространством RGB было невозможно.

Общая характеристика способа JPEG

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

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

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

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

Таблица 7.7. Качество рисунка и размер файла

Величина потерь качества изображения	Размер файла в байтах
Исходный рисунок	2476101
Минимальные потери	244 998
Малые потери	73654
Средние потери	56196
Большие потери	43506

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

Способы сжатия в JPEG

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

Дополнительный способ заключается в простом усреднении значений компонент и и У. которое было описано выше. При этом можно выбрать усреднение цвета одной, 2- или 4-х смежных точек, значения компоненты v остаются без изменений. Выбор одной точки означает отказ от усреднения.

Для основного способа можно выбирать только степень потерь, о чем говорилось выше. Он заключается в том, что последовательно выбираются области рисунка размером 8x8 точек. Для каждой группы из 64 точек выполняется преобразование Фурье. Его назначение в том, чтобы отфильтровать (исключить) высокочастотную компоненту из исходных данных. Результаты преобразования квантуются и преобразуются в целые числа, которые кодируются по таблицам Хуффмана (D. A. Huffman) и записываются в выходной массив. После обработки всего изображения выходной массив упаковывается в файл одним из стандартных способов.

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

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

Файлы формата JPG

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

Среди пользователей более популярен стандарт JFIF, разработанный фирмой C-Cubc Microsystems. Это один из основных стандартов для передачи графических данных в сети Internet. Файлы, соответствующие этому стандарту, имеют тип (расширение) JPG.
JFIF расшифровывается как JPEG File Interchange Format (формат для обмена файлами JPEG). В настоящее время наибольшее распространение получила версия JFIF 1.2, опубликованная в сентябре 1992 года. К сожалению, автору не известен перевод описания стандарта на русский язык. В случае необходимости вам придется использовать описание на английском языке, которое можно легко найти в сети Internet.

Содержание раздела