03_imcompr (Лекции)

Глава 12

Сжатие изображений

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

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

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

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

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

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

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

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

Как работает алгоритм группового кодирования

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

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

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

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

Как работает алгоритм JPEG

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

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

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

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

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

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

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

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