Алгоритм

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

Алгоритм Хаффмена изящно реализует общую идею статистического кодирования с использованием префиксных множеств и работает следующим образом:

Вопросы для самоконтроля

1. Какие параметры надо определить, прежде чем сравнивать два алгорит­ма сжатия видео?

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

3. Какими свойствами видеопотока мы можем пользоваться, создавая алго­ритм сжатия? Приведите примеры.

4. Что такое аудиовизуальная синхронизация? Почему выполнение ее тре­бований значительно снижает степень сжатия?

5. Назовите основные требования к алгоритмам сжатия видео.

6. Что такое I-кадры, ...

Кодирование: слой III

Слой III использует гораздо более сложный алгоритм, чем первые два слоя. Это отражается в более высокой степени сжатия оцифрованного звука. Разница между этими слоями заметна уже на первом шаге алгоритма, который осуществляет фильтрование. Применяется один и тот же банк фильтров, но после него совершается модифицированное дискретное косинус-преобразование (MDCT). Это преобразование исправляет некоторые ошибки, внесенные многофазными фильтрами, а также подразделяет подполосы, чтобы сделать их более близкими к критическим полосам. Декодер слоя III должен применить обратное MDCT, поэтому ...

MPEG-1

Алгоритм MPEG-1 в целом соответствует описанной выше общей схеме построения алгоритмов сжатия.

Характеристики MPEG-1:

Поток, разрешение: 1.5 Мбит/с, 352x240x30,352x288x25.

Плюсы: сравнительно прост в аппаратной реализации, содержит пре-[ образования, поддерживаемые на аппаратном уровне большим количест-\ вом видеокарт.

Минусы: невысокая степень сжатия. Малая гибкость формата.

Психоакустические модели

Психоакустические модели дают возможность кодеру определить порог допустимого шума квантования на каждой подполосе. Эта информация будет использоваться алгоритмом назначения битов, что в сочетании с количеством имеющихся битов задаст число уровней квантования для каждой подполосы. Стандарт MPEG устанавливает две психоакустические модели. Обе модели могут использоваться любым слоем, но только модель II выдает особую информацию для слоя III. На практике модель I используется только слоями I и П. Слой III может работать с любой моделью, но лучшие результаты получаются с моделью П. ...

Другие пути повышения степени сжатия

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

Если, с одной стороны, повышается степень сжатия, то, с другой сторо­ны, ...

Возможности по распараллеливанию

Даже беглый взгляд на этот обобщенный алгоритм позволяет заметить, что он сравнительно легко распараллеливается. Изображение 320x288 со­держит 330 макроблоков, которые можно кодировать и декодировать неза­висимо. Каждый макроблок, в свою очередь, содержит 6 блоков данных для ДКП. Распараллелить ДКП очень важно, так как, не считая поиска векторов смещения, это самая медленная операция. Заметим также, что остальные преобразования легко конвейеризуются. В результате мы получаем парал­лельно-конвейерную схему обработки потока видеоданных.

Достаточно заманчиво выглядит возможность ...

Использование векторов смещений блоков

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

Общая схема алгоритма

В целом весь конвейер преобразований можно представить так:

1. Подготовка макроблоков. Для каждого макроблока определяется, каким образом он будет сжат. В I-кадрах все макроблоки сжимаются независи­мо. В Р-кадрах блок либо сжимается независимо, либо представляет со­бой разность с одном из макроблоков в предыдущем опорном кадре, на который ссылается Р-кадр.

2. Перевод макроблока в цветовое пространство YUV. Получение нужного количества матриц 8x8.

3. Для Р- и В-блоков производится вычисление разности с соответствую­щим макроблоком в опорном кадре.

4. ...

Описание алгоритма компрессии

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

Для того чтобы удовлетворить противоречивым требованиям и увели­чить гибкость алгоритма, рассматривается 4 типа кадров:

■ 1-кадры - кадры, сжатые независимо от других кадров (I-Intra pictures);

■ Р-кадры- сжатые с использованием ссылки на одно изображение (Р-Predicted);

■ В-кадры- сжатые с использованием ссылки на два ...