Двоичное кодирование видеоинформации

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

Изображение в видео состоит из отдельных кадров, которые меняются с определенной частотой. Кадр кодируется как обычное растровое изображение, то есть разбивается на множество пикселей. Закодировав отдельные кадры и собрав их вместе, мы сможем описать все видео.

Отметим то, что видеоданные характеризуются частотой кадров и экранным разрешением. Скорость воспроизведения видеосигнала составляет 30 или 25 кадров в секунду, в зависимости от телевизионного стандарта. Наиболее известными из таких стандартов являются: SECAM, принятый в России и Франции, PAL, используемый в Европе, и NTSC, распространенный в Северной Америке и Японии.

Разрешение для стандарта NTSC составляет 768 на 484 точек, а для PAL и SECAM – 768 на 576 точек. Но не все пиксели используются для хранения видеоинформации. Так, при стандартном разрешении 768 на 576 пикселей, на экране телевизора отображается всего 704 на 540 пикселей. Поэтому для хранения видеоинформации в компьютере или цифровой видеокамере, размер кадра может отличаться от телевизионного. Например, в формате Digital Video или, как его еще называют DV, размер кадра составляет 720 на 576 пикселей. Такое же разрешение имеет кадр стандарта DVD Video. Размер кадра формата Video-CD составляет 352 на 288 пикселей.

Если представить каждый кадр изображения как отдельный рисунок, то видеоизображение будет занимать очень большой объем, например, одна секунда записи в системе PAL будет занимать 25 Мбайт, а одна минута – уже 1,5 Гбайт. Поэтому на практике используются различные алгоритмы сжатия для уменьшения скорости и объема потока видеоинформации.

Кодирование видеоинформации еще более сложная проблема, чем кодирование звуковой информации, так как нужно позаботиться не только о дискретизации непрерывных движений, но и о синхронизации изображения со звуковым сопровождением. В настоящее время для этого используется формат, которой называется AVI (Audio-Video Interleaved — чередующееся аудио и видео).

Основные мультимедийные форматы AVI и WAV очень требовательны к памяти. Поэтому на практике применяются различные способы компрессии, то есть сжатия звуковых и видеокодов. В настоящее время стандартными стали способы сжатия, предложенные MPEG (Moving Pictures Experts Group — группа экспертов по движущимся изображениям). В частности, стандарт MPEG-1 описывает несколько популярных в настоящее время форматов записи звука. Так, например, при записи в формате МР-3 при практически том же качестве звука требуется в десять раз меньше памяти, чем при использовании формата WAV. Существуют специальные программы, которые преобразуют записи звука из формата WAV в формат МР-3. Стандарт MPEG-2 описывает методы сжатия видеозаписей, которые обеспечивают телевизионное качество изображения и стереозвуковое сопровождение и имеют приемлемые требования к памяти. Совсем недавно был разработан стандарт MPEG-4, применение которого позволяет записать полнометражный цветной фильм со звуковым сопровождением на компакт-диск обычных размеров и качества.

Сжатие информации

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

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

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

Универсальные методы сжатия

Существует достаточно много универсальных (обратимых) методов сжатия, однако в их основе лежит сравнительно небольшое количество теоретических алгоритмов, которые мы рассмотрим на примерах.

Определение:метод сжатия называется обратимым, если из данных, полученных при сжатии, можно точно восстановить исходный массив данных.

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

Графическая информация – gif, tiff, png;

Видеоинформация – avi;

Для любых типов данных - zip, rar, arj,lzh, cab.

Метод упаковки

Напомним, что при кодировании информации каждому объекту (символ, пикселю, измерению звука) ставиться в соответствие двоичный код фиксированной длины i. Тогда объем всей цифровой информации можно определить по формуле V=i⋅k, где k – это количество объектов (символов, пикселей и т.д) в потоке информации.

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

Пример 1. Представлен текст в кодировки ASCII, который содержит не все 256 символов, а только 12: цифры от «0» до «9», знак (минус) и пробел. Использование ASCII кодировки будет ставить в соответствие каждому символу код объемом 8 бит. Тогда текст «280 -1296 48 40 365 -159 13 777» в памяти компьютера займет 30сим • 8бит= 240 бит= 30 байт.

Однако для кодирования такого количества символов достаточно всего 4-х бит. Если упаковать коды данных символов в 4 бита (например, так: «0» - 0000, «1» - 0001, ... «9» - 1001, минус - 1110, пробел - 1111), то получим двукратное сжатие данных (15 байт).

Формат записи чисел, при котором число записывается в десятичной системе, а цифры числа кодируются 4-битовыми кодами, называется BCD-форматом (Binary Code Decimal, или двоично-десятичная запись). BCD-формат нередко используется в программировании для хранения целых чисел, например в базах данных.

Пример 2. Сообщение «КОЛ ОКОЛО КОЛОКОЛА» записанное в кодировке ASCII будет весить

Vascii=8бит • 18 символов = 144 бита, а кодировке Unicode соответственно Vunicode = 16 бит • 18 символов = 288 бит.

Однако данное сообщение содержит всего 5 различных символов, следовательно, каждый символ может быть закодирован тремя битами, например, так: «А» - 000, «К» - 001, «Л» - 010, «О» - 011 и пробел - 111. Тогда объем сообщения будет равен V=18 символов • 3 бит = 54 бита.

В результате мы получаем коэффициент сжатия равный 144/54 = 2,(6) для кодировки ASCII и 288/54=5,(3) для кодировки Unicode.

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

Метод Хаффмана

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

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

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

Выделяют побуквенное кодирование и блочное кодирование.

Сжатие методом Хаффмана выполняется за два прохода. На первом проходе читаются все входные данные и подсчитываются частоты встречаемости всех символов. Затем по этим данным строится дерево Хаффмана, по которому вычисляются коды символов. На втором проходе, входные данные читаются еще раз и перекодируются на основе новой кодовой таблицы.

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

1) Подсчитать частоты встречаемости всех символов;

2) Построить дерево кодирования (алгоритм построения дерева);

Построить коды символов (левая ветка- 0, правая ветка -1)