Уроки 4 - 5
Сжатие данных без потерь
(§3. Сжатие данных)

Содержание урока

Основные понятия

Алгоритм RLE

Префиксные коды

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

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

Выводы

Вопросы и задания

Задачи

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

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

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

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

Самые известные примеры сжатия с потерями — это алгоритмы JPEG (для изображений), MP3 (для упаковки звука) и все алгоритмы упаковки видеофильмов (MJPEG, MPEG4, DivX, XviD).

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

Рис. 1.5

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

Из классической RGB-модели (красный, зелёный, синий) цвет переводится в модель YCbCr, где Y — яркость, Сb — «синева», Сr — «краснота»:

Y = 0,299 • R + 0,587 • G + 0,114 • В,

Сb = 128 - 0,1687 • R - 0,3313 • G + 0,5 • В,

Сr = 128 + 0,5 • R - 0,4187 • G - 0,0813 • В.

В этих формулах R, G и В обозначают красную, зелёную и синюю составляющие цвета в RGB-модели. Чёрно-белое изображение (точнее, оттенки серого), содержит только Y-составляющую, компоненты цвета Сb и Сr равны 128 и не несут полезной информации.

Основная идея сжатия основана на том, что человеческий глаз более чувствителен к изменению яркости, т. е. составляющей Y. Поэтому на синюю и красную составляющие, Сb и Сr, приходится меньше полезной информации, и на этом можно сэкономить. Рассмотрим квадрат размером 2x2 пикселя. Можно, например, сделать так: запомнить Y-компоненту для всех пикселей изображения (4 числа) и по одной компоненте Сb и Сr на все 4 пикселя (рис. 1.6).

Рис. 1.6

Для определения сохраняемых значений СЬ и Сг можно использовать, например, усреднение — принять

Сb = (Cb₁ + Cb₂ + Cb₃ + Сb₄)/4, Сr = (Сr₁ + Сr₂ + Сr₃ + Сr₄)/4.

Таким образом, вместо 12 чисел мы должны хранить всего 6, данные сжаты в 2 раза. Однако мы не сможем восстановить обратно исходный рисунок, потому что информация и том, какие были значения Сb и Сr для каждого пикселя, безвозвратно утеряна, есть только некоторые средние значения. При выводе такого изображения на экран можно, например, считать, что все 4 пикселя имели одинаковые значения Сb и Сr. Более сложные алгоритмы используют информацию о соседних блоках, сглаживая резкие переходы при изменении этих составляющих. Поэтому при кодировании с помощью алгоритма JPEG изображение несколько размывается.

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

На рисунке 1.7 вы видите результат сжатия изображения шарика в формате JPEG с разным качеством.

Рис. 1.7

Рисунки, сохранённые с качеством 100 и 50, практически не отличаются внешне, однако второй из них занимает в 2,65 раза меньше места. При снижении качества до минимального явно заметны искажения (артефакты), вызванные потерей информации при сжатии. Кажется, что рисунок построен из квадратов размером 8x8 пикселей (в действительности именно такие квадраты использует алгоритм в качестве базовых ячеек). Кроме того, искажения особенно заметны там, где происходит резкий переход от одного цвета к другому.

Тот же самый рисунок был сохранён в формате BMP без сжатия и с RLE-сжатием, а также в форматах GIF (сжатие без потерь с помощью алгоритма LZW) и PNG (сжатие без потерь с помощью алгоритма DEFLATE). Размеры полученных файлов (в килобайтах) сравниваются на диаграмме (рис. 1.8).

Рис. 1.8

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

Теперь рассмотрим другой рисунок, в котором у объектов есть большие области одного цвета и чёткие границы у объектов. Здесь ситуация несколько меняется (рис. 1.9).

Рис. 1.9

Форматы GIF и PNG обеспечивают степень сжатия, сравнимую с алгоритмом JPEG среднего качества. Учитывая, что JPEG приводит к искажению изображения, a GIF и PNG — нет, для таких рисунков не рекомендуется использовать формат JPEG.

Другой известный пример сжатия с потерями — алгоритм MPEG-1 Layer 3, который более известен как MP3. В нём отбрасываются некоторые компоненты звука, которые практически неразличимы для большинства людей. Такой подход называется кодированием восприятия, потому что он основан на особенностях восприятия звука человеком.

Одна из главных характеристик сжатия звукового файла — битрейт (англ. bitrate — темп поступления битов). Битрейт — это число битов, используемых для кодирования 1 с звука. Формат MP3 поддерживает разные степени сжатия, с битрейтом от 8 до 320 Кбит/с.

Звук, закодированный с битрейтом 256 Кбит/с и выше, даже профессионал вряд ли отличит от звучания компакт-диска. Вспоминая материал учебника 10 класса, можно подсчитать, что 1 секунда звука занимает на компакт-диске (частота дискретизации 44 кГц, глубина кодирования 16 битов, стерео)

2 • 88 000 = 176 000 байтов = 1 408 000 битов = 1375 Кбит.

Таким образом, формат MP3 обеспечивает степень сжатия 1375/256 ≈ 5,4 при сохранении качества звучания для человека (хотя часть информации, строго говоря, теряется).

Для сжатия видео может использоваться алгоритм MJPEG (англ. Motion JPEG — JPEG в движении), когда каждый кадр сжимается по алгоритму JPEG. Кроме того, широко применяют стандарт MPEG-4, разработанный специально для сжатия цифрового звука и видео.

Программы (и устройства), которые выполняют кодирование и декодирование звука и видео, называют кодеками (англ. codec — coder/decoder — кодировщик/декодировщик). Наиболее известные аудиокодеки (программы для преобразования звука) - MP3, Ogg Vorbis (OGG) и ААС. Среди видеокодеков чаще всего используются кодеки стандарта MPEG-4 (DivX, Xvid, Н.264, QuickTime) и кодек WMV (Windows Media Video). Самые популярные свободные (англ. open source) и бесплатные (англ. freeware) кодеки собраны в пакет K-Lite Codec Pack (codecguide.com).

Следующая страница Выводы

Cкачать материалы урока