8. Обработка и формирование графических файлов

 8.3. Сжатие графических файлов

Растровые файлы имеют большие размеры. Если пренебречь заголовками файла и другими неграфическими данными, его размер пропорционален количеству пикселов в изображении и количеству битов, требуемых для представления каждого пиксела. Полноцветная картинка размером 1024´768 пикселов занимает более двух мегабайт памяти, а одна секунда видеофильма телевизионного качества в растровом представлении требует около тридцати мегабайт. Поэтому жесткий диск можно заполнить мгновенно. Даже компакт-диск, который вмещает около 700 мегабайт данных, не столь велик, чтобы сохранить графические файлы, если не попытаться уменьшить их объем.  

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

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

Идея метода группового кодирования (run-lenght encoding – RLE). заключается в том, что последовательность повторяющихся значений заменяется парой чисел: одно из них указывает длину группы (число повторений данного значения), а другое – собственно это значение. Это очень общий и очень простой метод без потерь. В том или ином виде он используется во многих популярных сегодня форматах графических файлов и, в частности, в PCX и BMP. В его основе лежит тот факт, что многие изображения избыточны, поскольку содержат большое количество смежных пикселов одного цвета. Посмотрим, например, как с помощью группового кодирования сжимается изображение, в котором встречается подряд 100 пикселов с нулевым значением. Эта последовательность из 100 нулей кодируется парой чисел (100,0). Следовательно такой фрагмент картинки сократится в пятьдесят раз.  

Метод JPEG получил свое название от аббревиатуры объединенной группы экспертов в области фотографии (Joint Photographic Expert Group – JPEG), которая его и разработала. JPEG широко используется при сжатии статических изображений для их хранения на компакт-дисках. Этот метод существенно более сложен, чем RLE. Основная идея метода – разделить информацию в изображении по уровню важности, и затем отбросить менее важную ее часть, уменьшая тем самым общий объем хранимых данных. Это достигается преобразованием матрицы цветовых значений в матрицу амплитуд, которые соответствуют определенным частотам разложения изображения. (Звуковые колебания, например, можно разложить математическими методами на простые синусоидальные гармоники различных амплитуд и частот, которые при сложении воспроизводят исходный сигнал). Строку или столбец пикселов изображения тоже можно представить амплитудами и частотами. Речь здесь идет не о спектральном составе света, а о форме воображаемых кривых, которые образуют графики, если значения пикселов служат ординатами. Отметим, что формула преобразования матрицы пикселов в матрицу амплитуд совсем не проста. JPEG-сжатие отбрасывает часть высокочастотных компонент изображения, оставляя компоненты с низкими частотами. Человеческий глаз менее чувствителен к высокочастотным вариациям цвета, поскольку общий вид изображения определяется низкими частотами. Значение пиксела, полученное при восстановлении изображения, несколько отличается от исходного значения, так как часть информации была потеряна, хотя обычно они очень близки.  

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

Чем ниже коэффициент качества, тем большее количество информации отбрасывается.  

Когда любой из методов (RLE или JPEG) применяется к полноцветному изображению, то красная, зеленая и синяя компоненты сжимаются независимо. Если в растровой картинке используется палитра или просто оттенки серого, то значения пикселов можно закодировать в один проход.  

Приступим к детальному рассмотрению методов RLE и JPEG.  

Алгоритм группового кодирования  

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

Чтобы идентифицировать серии неповторяющихся значений пикселов, программа также вставляет метки, указывающие количество таких значений в серии. Зарезервированный бит необходим для того, чтобы можно было отличить метку отрезка, от метки серии неповторяющихся значений. Например, в 8-ми битах можно специфицировать последовательности длиной до 127 пикселов (максимальное число, представимое 7-ю битами); восьмой бит в каждой метке может отличать отрезок от серии неповторяющихся пикселов. В нашем примере благодаря RLE-сжатию размер строки уменьшился с 32 до 19 байт, т.е. на 40 процентов. Точно так же обрабатывается каждая строка пикселов, и отрезки одинаковых значений пикселов сжимаются во всем изображении.  

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

Алгоритм JPEG  

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

К значениям пикселов применяется формула, названная дискретным косинусоидальным преобразованием (Discrete Cosine Transform – DCT). DCT переводит матрицу значений пикселов 8´8 в матрицу значений амплитуд такой же размерности, соответствующую определенным частотам синусоидальных колебаний. Левый верхний угол матрицы соответствует низким частотам, а правый нижний – высоким.  

Коэффициент качества, введенный пользователем, используется в простой формуле, которая генерирует значения элементов другой матрицы 8´8, названной матрицей квантования. Чем ниже коэффициент качества, тем большие значения будут иметь элементы матрицы.  

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

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

Декодирование JPEG-изображения начинается с шага обратного кодированию без потерь, в результате чего восстанавливается матрица квантования пикселов.  

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

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

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

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

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

JBIG  

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

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

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

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

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

Контрольные  вопросы.

1.  Для чего выполняют сжатие графических файлов?  

2.  Какие основные подходы к сжатию вам известны?  

3.  Дайте характеристику вычислительному процессу при сжатии методом JPEG.

     Содержание