3. Особенности сжатия с потерей информации

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

Самая большая работа по кодированию ведется над изображениями, скажем, при передаче факсов. Если бы образ стандартного машинописного листа формата А4 не был бы сжат, то его передача даже при низком разрешении заняла около часа. В самых распространенных факсах, принадлежащих группе III по классификации Международного консультативного комитета по телеграфии и телефонии, использованы фиксированные таблицы кодировки. Похожую схему кодирования дает хорошо известный формат представления графических файлов PCX. В нем очередной байт кода может означать либо счетчик повторений, если он начинается битами 11, либо байтом точек исходного изображения. Число повторений задается младшими 6 битами байта повторения, т.е. имеет значение до 63. Изображение чистого листа бумаги при этом будет сжато больше чем в 30 раз.

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

Рассмотрим сущность основных алгоритмов сжатия с потерей информации.

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

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

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

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

Алгоритмы MPEG. Стандарт сжатия звуковых и видео файлов MPEG разработан Экспертной группой кинематографии (Moving Picture Experts Group) с целью ускорения загрузки загрузки таких файлов или пересылки по компьютерным сетям.

Существуют разные стандарты MPEG: MPEG-1, MPEG-2, MPEG-3, MPEG-4, MPEG-7.

Стандарт MPEG состоит из трех частей: Audio, Video, System (объединение и синхронизация двух первых).

По стандарту MPEG-1 потоки видео и звуковых данных передаются со скоростью 150 Кбайт/с - с такой же скоростью, как и односкоростной CD-ROM-проигрыватель - и управляются путем выборки ключевых видео кадров и заполнением только областей, изменяющихся между кадрами. MPEG-1 обеспечивает качество видеоизображения более низкое, чем видео, передаваемое по телевизионному стандарту.

MPEG-1 был разработан и оптимизирован для работы с разрешением 352 ppl (point per line - точек на линии)240 lpf (line per frame - линий в кадре)30 fps (frame per second - кадров в секунду), что соответствует скорости передачи CD-звука высокого качества. Используется цветовая схема YCbCr (где Y - яркостная плоскость, Cb и Cr - цветовые плоскости).

Принципы кодирования звука основаны на том факте, что человеческое ухо не совершенно и на самом деле в несжатом звуке (CD-audio) передается много избыточной информации. Принцип сжатия работает на эффектах маскировки некоторых звуков для человека (например, если идет сильный звук на частоте 1000 Гц, то более слабый звук на частоте 1100 Гц уже не будет слышен человеку, также будет ослаблена чувствительность человеческого уха на период в 100 мс после и 5 мс до возникновения сильного звука). Психоакустическая модель, используемая в MPEG, разбивает весь частотный спектр на части, в которых уровень звука считается одинаковым, а затем удаляет звуки не воспринимаемые человеком, благодаря указанным выше эффектам.

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

MPEG-4 представляет собой стандарт для низкоскоростной передачи (64 Кбит/с). Его идея состоит в том, что он разделяет исходный видеокадр на различные элементы, называемые медиа объектами, описывает структуру этих объектов и их взаимосвязи, чтобы затем собрать их в видеозвуковую сцену.

Видеозвуковая сцена состоит из медиа объектов, объединенных в иеархическую структуру:

• неподвижные картинки (например, фон);

• видео объекты (например,говорящий человек);

• аудио объекты (например, голос связанный с этим человеком);

• текст, связанный с данной сценой;

• синтетические объекты – объекты, которых не было изначально в записываемой сцене, но которые туда добавляются при демонстрации пользователю.

• Текст, связанный с головой из которого в конце синтезируется голос. 

Такой способ представления данных позволяет: 

• перемещать и помещать медиа объекты в любое место сцены;

• трансформировать объекты, изменять геометрические размеры;

• собирать из отдельных объектов составной объект и проводить над ним какие-либо операции;

• изменять текстуру объекта (например, цвет), манипулировать объектом (например, заставить ящик передвигаться по сцене);

• изменять точку наблюдения за сценой и т.п.

Стандарт для описания различных типов мультимедийной информации (а не для ее кодирования) MPEG-7 стал разрабатываться сравнительно недавно с целью обеспечения эффективного и быстрого поиска. MPEG-7 официально называют Multimedia Content Description Interface (Интерфейс описания мультимедиа данных). Он определяет стандартный набор свойств для различных типов мультимедиа информации, а так же стандартизует способ определения новых свойств и их взаимосвязей. Для этой цели MPEG-7 вводит DDL (Description Definition Language - язык описания определений). Основная цель применения MPEG-7 - это поиск мультимедиа информации (так же, как сейчас можно найти текст по какому-нибудь предложению).

1Алгоритм Лемпеля — Зива — Велча(Lempel-Ziv-Welch,LZW) — это универсальный алгоритм сжатия данных без потерь. Алгоритм разработан так, чтобы его можно быстро реализовать, но он не обязательно оптимален, поскольку он не проводит никакого анализа входных данных.

2Основанный на частной собственности и на идее коммерческого использования авторских и иных прав.

3симметричный алгоритм блочного шифрования (размер блока 128 бит, ключ 128/192/256 бит), принятый в качестве стандарта шифрования правительством США. Этот алгоритм хорошо проанализирован и сейчас широко используется.

4Алгоритм основан на схеме сжатия данных по словарю и обеспечивает высокий коэффициент сжатия, а также позволяет использовать словари различного размера (до 4 Гб)

5Шеннон К.Работы по теории информации и кибернетике. М.: ИЛ, 1963.