Алгоритм проиллюстрирован на рис. 7.20. Шаг 1 — подготовка блоков. Чтобы добавить конкретики, предположим, что на входе алгоритма JPEG — это изображение RGB с размерами 640 х 480, 24 бита на пиксель, как показано на рис. 7.21, а. RGB — это не лучшая модель цвета для сжатия. Глаз гораздо более чувствителен к яркости (luminance), а не к хроматическим данным (chrominance), то есть к цвету видеосигнала. Таким образом, мы сначала вычисляем яркость, Y, и две хроматические характеристики, Cb и Cr, компонентов R, G и B. Следующие формулы используются для 8-битных значений (от 0 до 255):

Рис. 7.20. Шаги последовательного кодирования JPEG с потерями

Для Y, Cb и Cr конструируются отдельные матрицы. Затем в матрицах Cb и Cr квадратные блоки по 4 пикселя усредняются и сводятся в один, и изображение сокращается до размеров 320 х 240. Сжатие идет с потерями, но глаз это едва ли заметит, так как главное для него — яркость. Тем не менее общий объем данных сокращается в 2 раза. Теперь из каждого элемента всех трех матриц вычитается 128, чтобы поместить ноль в центр диапазона. Наконец, каждая матрица разделяется на блоки 8 х 8. В матрице Y — 4800 блоков, в оставшихся двух — по 1200, как показано на рис. 7.21, б.

Рис. 7.21. Входные данные RGB (а). После подготовки блоков (б)

Второй шаг кодирования JPEG — применение ДКП (DCT, Discrete Cosine Transformation — дискретное косинусное преобразование) отдельно к каждому из 7200 блоков. Выход каждого ДКП — это матрица ДКП-коэффициентов 8 х 8. Элемент ДКП (0,0) — это среднее значение блока. Остальные элементы указывают на то, какая спектральная мощность у каждой пространственной частоты. Обычно эти элементы быстро уменьшаются до нуля при отдалении от начала координат (0,0), как показано на рис. 7.22.

Рис 7.22. Один блок матрицы Y (а). Коэффициенты ДКП (б)

Как только ДКП завершено, кодирование JPEG переходит к шагу 3, который называется квантованием (quantization). На этом этапе стираются наименее важные коэффициенты ДКП. Эта трансформация с потерями проводится при помощи деления каждого из коэффициентов в матрице ДКП 8 х 8 на вес, взятый из таблицы. Если все веса равны 1, при трансформации ничего не происходит. Однако если веса резко возрастают, высокая разрешающая способность падает.

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

Рис 7.23. Вычисление квантованных коэффициентов ДКП

На четвертом шаге уменьшается значение (0,0) каждого блока (в левом верхнем углу), которое заменяется на величину разности с соответствующим элементом в предыдущем блоке. Так как эти элементы являются средними значениями соответствующих блоков, они должны меняться медленно, так что при переходе к разностным значениям идет уменьшение их значений. Для остальных значений разности не вычисляются.

На пятом шаге 64 элемента линеаризуются и ко всему массиву применяется групповое кодирование. Сканирование блока слева направо, а затем сверху вниз не соберет вместе все нули, так что используется зигзагообразная модель сканирования, как показано на рис. 7.24. В этом примере она выдает 38 последовательных нулей в конце матрицы. Эта строка может быть сокращена до одного указателя, говорящего, что этих нулей 38. Данная техника называется групповым кодированием или кодированием длины серий (run-length encoding).

Теперь у нас есть список чисел, который представляет собой картинку (в трансформированном виде). На шестом шаге числа для хранения или передачи кодируются по методу Хаффмана, отдавая часто встречающимся числам более короткие коды.

Рис. 7.24. Порядок, в котором передаются квантованные значения.

JPEG может казаться сложным, но именно таким он и является на самом деле. Тем не менее возможность сжатия вплоть до двадцатикратного стоит того. Декодирование изображения JPEG требует запуска алгоритма в обратном порядке. JPEG практически симметричен: на декодирование и на кодирование уходит одинаковое время. Но не все алгоритмы сжатия симметричны, как мы сейчас увидим.

Стандарт MPEG

Наконец, мы подошли к самой сути: стандартам MPEG (Motion Picture Experts Group — экспертная группа по вопросам движущегося изображения). Хотя существует множество частных алгоритмов сжатия видео, эти стандарты определяют основные алгоритмы, используемые для сжатия видео. Они стали международными стандартами с 1993 года. Так как фильмы содержат и изображения и звук, MPEG может сжимать и аудио, и видео. Мы уже говорили о сжатии аудио и изображений, так что давайте теперь перейдем к сжатию видео.

Стандарт MPEG-1 (включающий MP3-аудио) был впервые опубликован в 1993 году, и он до сих пор широко используется. Его целью было производство выходной видеоинформации в таком же качестве, как у видеомагнитофона со сжатием в 40 раз, которая сможет передаваться со скоростью 1 Мбит/с. Такое видео подходит для широкого использования в Интернете на веб-сайтах. Не беспокойтесь, если вы не помните, что такое видеомагнитофон — MPEG-1 также использовался для хранения видео на CD. Если вы не застали и существования CD, нам придется перейти к MPEG-2. Этот стандарт был выпущен в 1996 году. Его разработали для сжатия видео в качестве телетрансляции. Сейчас этот стандарт очень распространен, так как является базовым для кодирования видео на DVD (а такое видео почти всегда попадает в Интернет) и для цифрового телевещания (DVB). Обычно видео в качестве DVD кодируется исходя из скорости передачи 4-8 Мбит/с.

В стандарте MPEG-4 есть два видеоформата. Первый из их, выпущенный в 1999 году, кодирует видео при помощи объектно-ориентированного представления. Это позволяет накладывать съемку на искусственно сконструированное изображение, например, ведущего, рассказывающего о погоде, на карту. Такая структура позволяет программам легко взаимодействовать с видеоданными. Второй формат, выпущенный в 2003 году, называется H.264 или AVC (Advanced Video Coding — продвинутое кодирование видео). Его целью является кодирование видео с в 2 раза меньшей требуемой пропускной способностью, чем предыдущие кодировщики, сохраняя то же качество, чтобы передавать в сети видео в лучшем качестве. Этот кодировщик используется для видео в высоком качестве.

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

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

Сжатие MPEG-видео использует два вида избыточности, присутствующие в фильмах: пространственную и временную. Пространственная избыточность может быть устранена при помощи кодирования каждого кадра отдельно с помощью JPEG. Этот подход используется не очень часто, как правило, когда нужен случайный доступ к каждому кадру (например, при редактировании видео). При этом варианте достигаются уровни сжатия JPEG.