6. Методы сжатия сообщений с потерями
Курс “Теория информации и кодирования”

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

Подходы к сжатию с потерями информации
Реализация сжатия звука. Метод MP3
Реализация сжатия изображений. Метод JPEG
Реализация сжатия видео. Метод MPEG

6.1 Подходы к сжатию с потерями информации


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

Важные аргументы в пользу применения сжатия с потерями для изображний и звука отображены на рис. 6.1:
  • изображения и звук предъявляют высокие требования к каналам передачи (особенно, с учетом высокого траффика). Например, хранение минуты несжатого видео даже при относительно скромном разрешении 800х600 требует около 2Гбайт памяти;
  • универсальные методы сжатия, используемые, например, в архиваторах, не обеспечивают радикального уменьшения объема этих видов сообщений. Например, исходный растровый файл (формат .bmp) при архивировании уменьшается лишь в 2-4 раза;
  • в силу особенностей человеческого зрения и слуха определенные потери качества воспринимаются как приемлемые. Например, фотография, сжатая каким-либо из современных методов в 10-15 раз на глаз мало отличается от исходного варианта, а звук с битрейтом в 5-6 раз меньше исходного удовлетворяет большинство слушателей.

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

Учет особенностей слуха при сжатии звука
Эффективность сжатия звука с потерями качества основана на учете особенностей человеческого слуха (рис.6.2):
  • тихие звуки начиная с некоторого порога практически не воспринимаются на слух. Поэтому соответствующие участки звукового потока можно кодировать очень компактно - например, просто задавать длительность интервала "тишины", не передавая в этот период звуковые отсчеты;
  • громкие звуки снижают чувствительность уха слуха. Поэтому их можно кодировать "грубее", увеличивая шаг квантования и используя меньшее количество разрядов. Поскольку чувствительность восстанавливается не сразу, после громкого звука можно некоторое время сохранять режим экономичного кодирования (это называют "маскированием" звука во времени);
  • эффект маскирования проявляется также в частотной области: относительно мощные частотные составляющие маскируют восприятие своих более слабых соседей по спектру. Эти эффекты локализованы внутри конкретных частотных полос, которые названы критическими (их всего 25). Кроме того от полосы частот зависит чувствительность слуха.
    Все перечисленные эффекты глубоко исследовались и формализованы в виде так называемой психоакустической модели, которая активно используется для эффективного сжатия звука. В частности, эти подходы реализованы в рамках популярного стандарта mp3.

Учет особенностей зрения при сжатии изображений и видео
Методы сжатия с потерями качества для статических изображений и видео используют особенности человеческого зрения (рис.6.3):
  • зрение не критично к мелким деталям изображений. В связи с этим «сглаживание» мелких деталей не вызывает ощущения значительного ухудшения качества. На практике такое сглаживание выполняют либо в пределах небольших участков изображения (в результате проявляется его «мозаичность»), либо по всему изображению в целом (это проявляется как потеря его четкости). Такой подход реализован соответственно в стандартах JPEG и JPEG2000. Еще один подход — выделение похожих элементов изображения, для которых может быть построено общее математическое описание (подобно векторному представлению). Такой подход называется фрактальным;
  • зрение более критично к искажениям яркости, нежели цвета. Исходя из этого выполняют разделение цветовых и яркостной составляющей. Этот эффект применяют, в частности, в телевидении, где для передачи яркостной составляющей используют более широкую полосу частот. Стандарт сжатия JPEG предусматривает более значительное огрубление цветовых составляющих изображения по сравнению с яркостной;
  • зрение не воспринимает слишком быстрое изменение изображения. Поэтому при восприятии видеоряда можно выделять “опорные” кадры, обеспечивающие четкость картинки и «промежуточные», которые необходимы для создания эффекта непрерывности. Такой подход применяют при сжатии видео, где «опорные» кадры кодируются с достаточно высоким качеством, а промежуточные кадры сжимаются гораздо сильнее. Это предусмотрено, в частности, в стандарте MPEG.

Контрольные вопросы:
1) Что понимается под «потерей информации» при кодировании звука и изображений
2) Какие основные факторы определяют важность использования сжатия с потерями
3) Охарактеризуйте основные особенности слуха, которые учитываются при сжатии звука с потерями
4) Охарактеризуйте основные особенности зрения, которые учитываются при сжатии с потерями статических изображений и видео


6.2 Реализация сжатия звука. Метод mp3

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

В связи с тем, что психоакустическая модель опирается на учет особенностей частотных диапазонов, при сжатии звука активно используются спектральные преобразования (рис.6.4):
  • поскольку частотный состав звука меняется во времени (достаточно представить музыкальный отрывок, где солируют разные инструменты), построение спектра выполняют для коротких отрезков времени. В частности, на рисунке показан звуковой фрагмент из N=500 отсчетов амплитуды. При частоте дискретизации 44 кГц он занимает всего около сотой доли секунды;
  • для получения спектра используется широко применяемое дискретное преобразование Фурье (ДПФ). В частности, прямое ДПФ преобразует набор из N значений амплитуды звука xn в набор комплексных величин Xk, по которым опеределяются амплитуды спектральных составляющих. В дальнейшем звуковые амплитуды xn могут быть восстановлены применением обратного ДПФ. Это означает, что хранить звук можно и в спектральной форме;
  • как наглядно видно на примере, спектр звукового фрагмента может быть гораздо лучше приспособлен для сжатия: более, чем в половине всего диапазона амплитуды частотных составлящих нулевые или очень малы;
  • таким образом, спектральное преобразование позволяет создать условия для сжатия кода звука. Такое сжатие может быть особенно эффективным, если дополнительно учесть маскирующее действие соседних частот в рамках психоаккустической модели. Это активно используется, в частности, в современном стандарте сжатия звука MP3, который мы детально рассмотрим ниже.

Общая характеристика метода сжатия mp3
Метод сжатия звука MP3 является одним из наиболее популярных. Его основные особенности иллюстрирует рис.6.5.
  • принципиальные особенности метода состоят в следующем:
    - во-первых, он активно использует психоакустическую модель, удаляя из звукового поток именно ту информацию, которая не будет существенно влиять на восприятие;
    - во-вторых, обеспечивает задание соотношения степени сжатия и величины потерь непосредственно пользователем исходя из величины битрейта;
  • в MP3 использутся следующие базовые приемы сжатия:
    - звуковой поток разбивается на последовательность блоков-фреймов, для каждого из которых выполняется сжатие;
    - для фреймов выполняется спектральное преобразование. Переход к спектру позволяет в дальнейшем выделить частотные составляющие, которые слабо влияют на восприятие звука;
    - для экономичного кодирования выполняется квантование спектра с учетом заданного пользователем уровня потерь;
    - сжатие полученных данных c использованием статистических методов.
  • эффективность сжатия дополнительно повышается за счет учета сложности кодирования отдельных фреймов:
    - для более сложных фреймов может автоматически задаваться повышенный битрейт. Это так называемый режим переменного битрейта VBR;
    - объем кода, выделяемый согласно битрейту, автоматически перераспределяется между соседними фреймами — от более простых к более сложным.

Особенности реализации сжатия в MP3
Конкретные особенности сжатия в MP3 отображены на рис.6.6:
  • Этап 1. Разбиение потока на блоки для сжатия
    Поток разбивается на фреймы длиной порядка 1000 звуковых отсчетов (сэмплов). Точное количество сэмплов во фрейме 1152 (унаследовано от предшествующего стандарта). Фрейм состоит из двух «гранул» по 576 сэмплов, которые обрабатываются по-отдельности. При этом каждый фрейм включает заголовок со служебной информацией, который содержит синхровставку, частоту дискретизации, количество звуковых каналов, значение битрейта;
  • Этап 2. Предварительный анализ блока
    На шаге А блок преобразуется в спектр и в нем выделяются частотные полосы для анализа, Для гранулы из 576 сэмплов используется 32 полосы по 18 амплитуд («бинов»).
    На шаге Б выполняется анализ с использованием психоакустической модели. Оценивается возможность маскирования внутри частотных полос. Оценивается необходимость дробления гранул для коротких звуков (576=3*192). Для раздробленых фрагментов выполняется повторное преобразование и анализ;
  • Этап 3. Выполняется огрубление спектра исходя из заданного битрейта
    На шаге А выделяются частотные полосы для огрубления. При этом используются 22 полосы, для которых степень огрубления задается индивидуально.
    На шаге Б выполняется собственно огрубление. Амплитуды внутри полос масштабируются с учетом возможностей маскирования (путем умножения на коэффициент данной полосы Кi<1). Значения амплитуд делятся на значение «квантователя» X исходя из битрейта;
  • Этап 4. Статистическое сжатие
    Выполняется кодирование по Хаффмену для каждой частотной полосы огрубления. Эффект достигается, поскольку после огрубления остаются небольшие числа, среди которых много нулей (для маскируемых значений). Для разных уровней квантования может использоваться несколько кодовых таблиц.

Пример квантования спектра в МР3
Для лучшего понимания приведем числовой пример квантования спектра — рис.6.7:
  • пусть для некоторой i-й полосы спектра значения четырех соседних амплитуд Aij частотных составляющих спектра будут соответственно 8739; 1195; 384; 421 (для кодирования здесь нужно 2*4=8 байтов=64 бита). С учетом условий психоакустической модели три более слабых частотных составляющих не будут восприниматься на слух, поэтому их можно кодировать максимально экономично;
  • огрубление амлитуд выполняется по формуле Gij = int(Aij*Ki/X). Примем, что исходя из заданного битрейта, значение квантователя X=200. При коэффициенте маскирования для полосы Кi=0.2, результаты огрубления Gij получат значения 9; 1; 0; 0. При этом в результате сжатия по Хаффмену нули будут скорее всего закодированы одним битом (они встречаются очень часто), так что общая длина кода составит порядка 10 битов вместо 64-х. Значения восстановленных амплитуд Bij будут отличаться от исходных на величину погрешности квантования и составят соответственно 9000; 1000; 0;
  • кодирование можно сделать еще более компактным, если уменьшить коэффициент маскирования например до Кi=0,1 и тем самым увеличить долю нулей за счет удаления еще одной замаскированной составляющей. В этом случае мы получим последовательность Gij 4; 0; 0; 0, которая будет восстановлена до Bij 8000; 0; 0; 0. Это уже близко к сжатию примерно на порядок. Платой за улучшение сжатия будет увеличение погрешности («шума квантования») для наиболее значимой частотной составляющей: если в первом случае округление выполнялось с точностью до 1000, то во втором — до 2000.

Контрольные вопросы:
1) С какой целью при сжатии звука и изображений с потерями используют спектральные преобразования
2) Опираясь на рис.6.4, поясните использование дискретных преобразований Фурье
3) Охарактеризуйте принципиальные особенности и основные приемы сжатия для метода MP3 (используйте рис.6.6)
4) Опираясь на рис.6.6, расскажите об этапах практической реализации сжатия звука в MP3
5) На примере рис.6.7 поясните использование маскирования, квантования и статистического сжатия в MP3.


6.3 Реализация сжатия изображений. Метод JPEG

Идея метода
Стандарт сжатия изображений JPEG разрабатывался еще в 80-х годах с учетом ограничений тогдашних компьютеров, однако успешно применяется и сегодня.
Основная идея метода — разбиение изображения на небольшие блоки с последующим сжатием их кода, которое визуально отображается сглаживанием мелких деталей (рис.6.8):
  • cглаживание достигается за счет использования спектрального преобразования и подавления высокочастотных составляющих. На этом этапе возникают потери качества изображения, которые, тем не менее субъективно воспринимаются как приемлемые (пример — на рис.6.3);
  • метод JPEG сочетает применение спектрального преобразования с использованием сжатия без потерь (кодирования Хаффмена и RLE), а также инженерных решений по подготовке к сжатию (например, разделения яркостной и цветовых составляющих с дополнительным огрублением последних);
  • обычно JPEG позволяет сжимать изображения в 10-15 раз без существенной потери качества. При более сильном сжатии проявляется мозаичность изображения, а также так называемый «эффект Гибсона» - более резкое выделение границ резких цветовых переходов. Время сжатия и восстановления изображения близки между собой.

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

Предварительная обработка изображения
На этом этапе выполняются три шага преобразования растрового изображения (рис.6.9):
  • Шаг А - для разделения яркостной и цветовой составляющих выполняется переход к так называемому цветоразностному представлению (ICT — Irreversible Color Transform). Тройка параметров RGB преобразуется в тройку коэффициентов YUV (YсrCb). Здесь Y – яркостная составляющая, а U и V – цветовые (так называемые “хроматический красный” - Cr и “хроматический синий” Cb). Прямое преобразование выполняется умножением вектора RGB на матрицу коэффициентов. С помощью той же матрицы может быть выполнено и обратное преобразование;
  • Шаг Б - изображение разделяется на блоки 8х8 пикселей, внутри которых в дальнейшем выполняется сглаживания деталей (рис.6.2). Именно эти прямоугольные блоки при сильном сжатии изображения выделяются как элементы «мозаики». Каждый блок изображения представляется тремя матрицами коэффициентов Pij размером 8х8. Матрицы соответствуют составляющим YUV. (Например, в матрице U значение Pij=0 означает, что у данной точки отсутствует красная цветовая составляющая, а Pij=255 значит, что эта составляющая будет максимально яркой);
  • Шаг В - выполняется так называемое «прореживание» строк и столбцов цветовых составляющих блоков изображения. В результате их размер сокращается в четыре раза, при этом огрубление цветов незначительно сказывается на восприятии изображения. Четверки блоков изображения 8х8 объединяются в «макроблоки» 16х16, а затем для цветовых составляющих U и V из соответствующих матриц исключаются все четные строки и столбцы. При этом матрица яркостной составляющей Y остается нетронутой В итоге количество коэффициентов сокращается вдвое (12 блоков остается 6).

Спектральное преобразование данных
Для выделенных блоков изображения выполняется спектральное преобразование данных, чтобы выделить информацию именно о мелких деталях, которые затем могут быть огрублены (пример на рис.6.10):
  • математически каждый блок изображения 8х8 пикселей представляется матрицей P из 64 коэффициентов pxy. Каждый из коэффициентов pxy может иметь значение от 0 до 255, поскольку кодируется одним байтом;
  • для перехода к спектральной форме изображения используется так называемое дискретное косинус-преобразование (ДКП) в его двумерном варианте. При этом от «пространственной» матрицы P, где каждый элемент характеризует пиксель с соотвествующим расположением, мы переходим к аналогичной «спектральной» матрице D, элементы которой соответствуют частотным составляющим;
  • расчет элементов матрицы D ведется по формуле, показанной на рисунке. В итоге коэффициенты dij отражают «амплитуду колебаний» яркости пикселей для различных частот. Так, одинаковой яркости всех пикселей отвечает нулевая частота (однородный фон - колебания отсутствуют). Соответствующий элемент расположен в верхнем левом углу матрицы D и в данном случае он будет единственным ненулевым. Если внутри блока появляется градиент яркости, то ненулевыми становятся и другие коэффициенты. Самая высокая частота отвечает изменениям яркости соседних пикселей. Ей отвечает коэффициент в правом нижнем углу матрицы;
  • полученные элементы dij («двумерный спектр») можно преобразовать в удобную для обработки одномерную форму, если развернуть его в строку. Такое преобразование выполняется путем обхода матрицы D «зигзагом» от левого верхнего к нижнему правому углу матрицы (как это видно на рис.6.5). Теперь последовательность коэффициентов соответствует линейному росту частоты и похожа на привычный одномерный спектр (это отображено на рис.6.7, который мы рассмотрим в дальнейшем).
    Обратим внимание, что процедура ДКП, как и дальнейшая обработка ее результатов, выполняется независимо для каждой составляющей цветовой модели YUV.

Квантование спектра и сжатие данных
На этом этапе выделяются два шага:
- подготовка к сжатию за счет огрубления (квантования) спектров блоков. Здесь возникают потери информации о деталях изображения;
- собственно сжатие кода. Оно выполняется с использованием стандартных методов и к потерям не приводит.
Ниже мы детально рассмотрим именно первый этап, поскольку второй реализуется уже знакомыми нам методами. Процедуру квантования спектра блока иллюстрирует рис.6.11:

.
.
.
.
.
.
.
.
.
.
.


  • первоначально все коэффициенты матрицы D делятся с отбрасыванием дробной части на некоторые установленные делители. В примере такой делитель принят равным 8. В реальном алгоритме JPEG делители увеличиваются с возрастанием частот (на рисунке приведен фрагмент реальной матрицы делителей, в котором отображены первые 16 значений из 63);
  • восстановление исходного вида матрицы выполняется обратным умножением на те же коэффициенты. Однако, поскольку при делении дробные части результатов отбрасывались, происходит необратимая потеря информации;
  • в результате процедуры огрубления набор коэффициентов может содержать много нулей. Кроме того маленькие цифры встречаются чаще, а набор используемых значений многократно уменьшается. Хотя каждый коэффициент по-прежнему кодируется одним байтом (то-есть, никакого сжатия еще не произошло), значительно улучшились условия для сжатия на следующем шаге преобразования;
  • нетрудно видеть, что увеличивая значения делителей, мы дополнительно улучшим предпосылки сжатия (возрастет количество нулей и сократится объем алфавита). При этом за рост степени сжатия придется заплатить ухудшением качества изображения.

Результаты обработки блока изображения
Рассмотрим теперь более детально особенности обработки уже знакомого нам блока изображения (рис.6.8) в связи с особенностями алгоритма JPEG – рис.6.12:
  • процедура обработки блока выполняется параллельно для всех трех составляющих цветовой модели. Для наглядности на рисунке выделена наиболее важная яркостная составляющая Y;
  • значения коэффициентов исходной матрицы P, матрицы спектра D и матрицы огрубленных коэффициентов D* представлены в виде полос, которые располагаются в направлении роста частоты (порядок обхода пикселей «зигзагом» от верхнего левого к нижнему правому углу матрицы описан выше);
  • как видно, в результате ДКП амплитуды частотных составляющих в целом убывают для более высоких частот. Кроме того, при огрублении для более “удаленных” коэффициентов используются большие значения делителей (рис.6.6). В результате при огрублении из спектра «вычищаются» именно высокочастотные составляющие, которым отвечают более мелкие детали изображения. Подобные изменения происходят и для спектров двух других составляющих U и V, которые не видны на рисунке. В итоге смещается их баланс, а вместе с ним итоговые цвета пикселей;
  • визуально эти изменения выражается в “смазывании” четких цветовых различий соседних пикселей. Например, исходно черные пикслели получили “промежуточные” бардовые и коричневые цвета, а соседние с ними ярко-красные и желтые стали более темными. Кроме того, в результате усреднения цвета внутри блоков на поле изображения выделяются их границы. Это приводит к визуальному эффекту мозаичности.

В результате подобного кодирования из примерно полутора тысяч бит, описывающиx блок, остается обычно несколько десятков: код изображения сжимается в 10-15 и более раз.

Контрольные вопросы
1. Дайте краткую характеристику сжатия изображений согласно стандарту JPEG.
2. Назовите основные этапы сжатия по стандарту JPEG и охарактеризуйте их содержание.
3. Расскажите о шагах предварительной подготовки изображения к сжатию в JPEG.
4. Используя рис.6.5, расскажите о применении спектрального преобразования в JPEG.
5. Опираясь на рис.6.6, поясните процедуру огрубления спектра блока изображения в JPEG.
6. По рис.6.7 расскажите о визуальных эффектах, возникающих при сжатии блоков изображений по стандарту JPEG.


6.4 Реализация сжатия видео. Метод MPEG

Неравномерность кодирования потока в MPEG
Форматы сжатия MPEG предусматривают использование трех типов кадров (рис.6.13):
  • опорные или внутренние I-кадры (Intra frame) получаются за счет сжатия по JPEG исходных кадров видеопотока. Они следуют с невысокой частотой (типична частота 2 кадра/c);
  • прогнозные P-кадры (Predicted frame) вставляются в промежутки между I-кадрами и содержат только изменения между ними (вновь появившиеся части изображения и векторы смещения его элементов). Именно здесь реализуется сжатие за счет разностного кодирования;
  • двунаправленные B-кадры (Bidirectional frame) формируются интерполяцией по данным предшествующего и последующего I- и P- кадров. Они необходимы для плавности восприятия. Важно, что для построения B-кадров все необходимые I- и P- кадры должны быть уже получены.

Блок кадров, начиная с I и включая все зависящие от него P и B, называется GOP (Group of Pictures). Последовательно идущие GOP составляют выходной видеопоток. Типичная последовательность кадров: IBBPBBIBBPBBIBB… (рис.6.13).

Соответственно, последовательность кадров по их номерам будет обрабатываться в следующем порядке: 1423765…. При этом воспроизводится они будут в порядке нумерации, а согласование обработки и воспроизведения произойдет за счет использования задержки по времени. Очевидно, что чем меньше движения присутствует в кодируемой последовательности кадров, тем эффективнее использование P и B-кадров.

Основные разновидности MPEG имеют следующие особенности:
  • MPEG-1 и MPEG-2 используют для формирования опорных кадров алгоритм JPEG. При этом в MPEG-2 используется ряд совершенствований;
  • MPEG-4 использует технологию фрактального сжатия изображений.
    Сжатие MPEG при приемлемом уровне качества позволяет сокращать объем кода видеопотока в сотни раз.

Метод компенсации движения
Важным условием эффективности MPEG является экономичное кодирование прогнозных кадров благодаря методу «компенсации движения» (рис.6.14):
  • при кодировании прогнозного кадра относительно предшествующего опорного алгоритм выявляет три вида областей: сохранящиеся области изображения; вновь появляющиеся элементы; переносимые элементы предыдущего кадра, которые в новом кадре будут занимать другое положение;
  • для трех перечисленных видов областей применяется разное кодирование: для сохраняемых - ссылки на их описание в предыдущем кадре, для новых — JPEG-описание, а для переносимых — разностное кодирование. Разумеется, для всех областей задаются координаты их в новом кадре;
  • метод компенсации движения, применяемый в MPEG, предусматривает разностное кодирование переносимых областей изображения относительно прогноза. Такой подход позволяет дополнительно сэкономить объем кода (см. пример на рис.6.14).

Контрольные вопросы
1) За счет чего реализуется учет инерционности зрения при сжатии видеопотока
2) Перечислите основные виды кадров MPEG и кратко охарактеризуйте их особенности
3) Объясните на примере рис.6.13 согласование обработки и воспроизведения поступающих кадров видеопотока.
4) Поясните суть метода компенсации движения, используя пример на рис.6.14



О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP