Кодирование данных

Уровни

Уровень	Разрешение	Битовая скорость
Low	352*240*30	4 Mbps
Main	720*480*30	15 Mbps
High 1440	1440*1152*30	60 Mbps
High	1920*1080*30	80 Mbps

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

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

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

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

г) текст, связанный с этой сценой;

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

е) текст (например, связанный с головой), из которого в конце синтезируется голос.

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

Алгоритм компрессии видео работает по той же схеме, что и в предыдущих стандартах, но есть несколько радикальных нововведений. В отличие от прежних стандартов, которые делили кадр на квадратные блоки вне зависимости от содержимого, новый кодер оперирует целыми объектами произвольной формы. К примеру, человек, двигающийся по комнате, будет восприниматься как отдельный объект, перемещающийся относительно другого неподвижного объекта - заднего плана. Также применен "интеллектуальный" способ расстановки ключевых кадров. Ключевые кадры не расставляются с заданной регулярностью, а выделяются кодером только в те моменты, в которые происходит смена сюжета. Естественно, алгоритмы поиска и обработки объектов сложной формы, углубленного анализа последовательностей кадров требуют существенно больших вычислительных ресурсов для качественного восстановления (декомпрессии) изображения этого формата, нежели в случае MPEG1 и -2. В результате усовершенствования эффективность компрессии видео в MPEG4 возросла настолько, что позволяет размещать полнометражный фильм длительностью полтора-два часа с весьма приличным качеством всего на одном стандартом компакт-диске (650 Мб).

Кодирование звука и музыки в стандартах MPEG осуществляется отдельным аудиокодером. По мере развития стандарта MPEG звуковые кодеры также совершенствовались, становясь все эффективнее. В основе повышения эффективности - та же идея: сократить объем "второстепенной" для слушателя аудиоинформации. В результате в составе стандарта MPEG1 было создано семейство из трех звуковых кодеров, названных "слоями": Layer I, Layer II, Layer III. Все они, подобно видеокодерам, построены на несовершенстве "человеческого фактора": психоакустическая модель использует несовершенства слухового аппарата человека. В несжатом звуке передается много избыточной информации, которую человеческое ухо не воспринимает. Большой эффект для сжатия дает, например, явление маскирования некоторых звуков. В частности, если сначала подать громкий звук на частоте 1000 Гц, то более тихий звук на частоте 1100 Гц уже не будет фиксироваться слухом. В модели используется и явление ослабления чувствительности человеческого уха на период в 5 мс - до и 100 мс - после возникновения сильного звука. Психоакустическая модель разбивает весь спектр на блоки, в которых уровень звука считается близким. Затем удаляет звуки, формально не воспринимаемые человеком. Потом следует процедура сжатия, и, наконец, формируется цифровой информационный поток.

Первый "слой" (Layer I) был рассчитан на поток скоростью 192 кбит/с на канал.

Разновидность Layer II, предназначенная для потоков до 128 кбит/с на канал, была разработана как компромисс между качеством звука, величиной потока и сложностью кодера.

Layer III исходно был рассчитан на низкоскоростные сети с потоком до 64 кбит/с на канал. Однако введенные усовершенствования позволили сохранить "CD-качество" звука при низкой скорости потока. Это требует больших вычислительных ресурсов, но производительность современных компьютеров достаточна. В результате появился формат сжатия аудиоинформации МР3 (полное его название - MPEG Audio Layer III), который начал вполне самостоятельную жизнь. Тот же институт Фраунгофера выпустил первый аппаратный кодер, работающий в реальном времени. За этим шагом последовали другие (МР3-Pro). Сегодня миниатюрные МР3-плейеры и диктофоны с флэш-картами разных мастей знакомы многим. Любой пользователь Интернета знает о распространении сжатого звука через сеть, знает о серверах, "набитых" музыкой в формате МР3.

Алгоритм RLE (Run-length encoding, Кодирование длин серий, или Кодирование повторов) — один из самых простых и старых алгоритмов сжатия данных, который оперирует сериями данных, то есть последовательностями, в которых один и тот же символ встречается несколько раз подряд. При кодировании серия одинаковых символов заменяется последовательностью, которая содержит сам повторяющийся символ и количество его повторов (пара «счетчик – значение»). Признаком счетчика служат две единицы в старших битах. Поскольку на счетчик отведено 6 бит, длина закодированной цепочки не может превышать 64 символа. Строку из 64 одинаковых байт алгоритм кодирует с помощью 2 байт, т.е. максимальный коэффициент сжатия равен 32. Такой алгоритм используется в формате PCX.

Рассмотренный алгоритм эффективен при кодировке текста, двоичных файлов, черно-белых изображений с большой площадью фона и т.п. Не требует дополнительной памяти в процессе работы. Однако если строка содержит большое количество неповторяющихся символов, ее объем в результате кодирования может возрасти. Поэтому часто используется другой вариант алгоритма RLE. При этом признаком повтора является единица в старшем разряде, признаком отсутствия – ноль. Под счетчик отводится 7 бит, поэтомy максимальный коэффициент сжатия равен 64, увеличение объема данных не превышает 1/128. Такая схема используется в одном из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.

Коэффициенты компрессии: Первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, 128/129. (Лучший, средний, худший коэффициенты).

Алгоритм LZ (Лемпела-Зива). Обнародован в 1978 году. Сущность состоит в том, что фразы (цепочки байт) заменяются указателем на то место, где они в тексте уже ранее появлялись. Данный метод быстро приспосабливается к структуре текста и может кодировать короткие функциональные слова, т.к. они очень часто в нем появляются. Новые слова и фразы могут также формироваться из частей ранее встреченных слов.

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

Существует довольно большое семейство LZ-подобных алгоритмов, различающихся, например, методом поиска повторяющихся цепочек. Один из достаточно простых вариантов этого алгоритма предполагает, что во входном потоке идет либо пара <счетчик, смещение относительно текущей позиции>, либо просто <счетчик> “пропускаемых” байт и сами значения байтов (как во втором варианте алгоритма RLE). При разархивации для пары <счетчик, смещение> копируются <счетчик> байт из выходного массива, полученного в результате разархивации, на <смещение> байт раньше, а <счетчик> (т.е. число равное счетчику) значений “пропускаемых” байт просто копируются в выходной массив из входного потока. Данный алгоритм требует полного перебора буфера при поиске одинаковых подстрок. В результате сложно задать большой буфер из-за резкого возрастания времени компрессии. Однако потенциально построение алгоритма, в котором на <счетчик> и на <смещение> будет выделено по 2 байта (старший бит старшего байта счетчика — признак повтора строки / копирования потока), даст возможность сжимать все повторяющиеся подстроки размером до 32Кб в буфере размером 64Кб. При этом в худшем случае произойдет увеличение размера файла на 32770/32768 (в двух байтах записано, что нужно переписать в выходной поток следующие 2¹⁵ байт). Максимальный коэффициент сжатия составит в пределе 8192 раза. В пределе, поскольку максимальное сжатие мы получаем, превращая 32Кб буфера в 4 байта, а буфер такого размера мы накопим не сразу. Однако, минимальная подстрока, для которой нам выгодно проводить сжатие, должна состоять в общем случае минимум из 5 байт, что является недостатком данного алгоритма.

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

Алгоритм LZW (Лемпела-Зива-Велча). Обнародован в 1984 году. В данном алгоритме выгодно сжимать даже цепочки, состоящие из 2 байт.

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

Рассмотрим пример.

Сначала производится инициализация таблицы строк так, чтобы она содержала все возможные строки, состоящие из одного символа. Например, если производится сжатие байтовых данных, то таких строк в таблице будет 256 («0», «1»,..., «255»). Для кода очистки и кода конца информации зарезервированы значения «256» и «257». В рассматриваемом варианте алгоритма используется 12‑битный код, и, соответственно, под коды для строк остаются значения от 258 до 4095. Добавляемые строки записываются в таблицу последовательно, при этом индекс строки в таблице становится ее кодом.

Пусть кодированию подвергается последовательность «45, 55, 55, 151, 55, 55, 55». Тогда, согласно изложенному выше алгоритму, в выходной поток сначала помещается код очистки «256», потом к изначально пустой строке добавляется «45» и проверяется, есть ли строка «45» в таблице. Поскольку при инициализации в таблицу были занесены все строки из одного символа, то строка «45» есть в таблице. Далее считаем следующий символ «55» из входного потока и проверяется, есть ли строка «45, 55» в таблице. Такой строки в таблице пока нет, поэтому в таблицу заносится строка «45, 55» (с первым свободным кодом 258), а в выходной поток записывается код «45».

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

Как видно, записываемые в поток коды постепенно возрастают. До тех пор, пока в таблице не появится, например, в первый раз код 512, все коды будут меньше 512. Кроме того, при компрессии и при декомпрессии коды в таблице добавляются при обработке одного и того же символа, т.е. это происходит “синхронно”. Можно воспользоваться этим свойством алгоритма для того, чтобы повысить степень компрессии. Пока в таблицу не добавлен 512 символ, в выходной битовый поток будут записываться коды из 9 бит, а сразу при добавлении 512 — коды из 10 бит. Соответственно декомпрессор также должен будет воспринимать все коды входного потока 9-битными до момента добавления в таблицу кода 512, после чего будет воспринимать все входные коды как 10-битные. Аналогично поступают при добавлении в таблицу кодов 1024 и 2048. Данный прием позволяет примерно на 15% поднять степень сжатия.

Коэффициенты компрессии: Примерно 1000, 4, 5/7 (Лучший, средний, худший коэффициенты).

Алгоритм Хаффмана. Алгоритм основан на том факте, что некоторые символы из стандартного 256-символьного набора (ASCII) в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, – реже. Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 8, а для записи редких символов – длинные, то суммарный объем файла уменьшится.

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

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

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

Рассмотренная процедура продолжается до тех пор, пока все дерево не сформировано, т.е. пока все не сведется к одному узлу.

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

Каждый символ изначально представлялся 8-ю битами (одним байтом). После применения алгоритма Хаффмана каждый символ кодируется меньшим количеством бит.

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

В теории кодирования информации показывается, что код Хаффмана является префиксным, то есть код никакого символа не является началом кода какого-либо другого символа.

Коэффициенты сжатия изображений: 8, 1.5, 1 (Лучший, средний, худший коэффициенты).

Дата добавления: 2014-01-04