Методы сжатия с регулируемой потерей информации.

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

Например, было установлено, что глаз человека наиболее чувствителен к зеленому цвету, чувствительность к красному ниже примерно в 4 раза, а к синему — почти в 10 раз! А это означает, что на хранение информации о красной и синей составляющих цвета можно было бы отводить меньше бит. Но в большинстве форматов графических файлов это не так — цветовые компоненты кодируются одинаковым количеством бит. Этот пример показывает, что традиционные способы представления видеоинформации обладают очень большой степенью избыточности, при условии, что речь идет о воспроизведе­нии видеоинформации для человека.

Для разработки и стандартизации эффективных методов сжатия аудио- и видеоинформации на рубеже 1980-1990-х годов были созданы Группа экспертов по фотографическим изображениям (Joint Photographic Experts Group, сокр. JPEG) и Группа экспертов по видеоизображениям (Motion Picture Experts Group, сокр. MPEG).

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

Наиболее известными методами сжатия с регулируемой потерей информации являются:

• JPEG — метод сжатия графических данных;

• MPEG — группа методов сжатия видеоданных;

• МРЗ — метод сжатия звуковых данных.

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

Алгоритм JPEG

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

Собственно сжатие JPEG осуществляется в несколько этапов: сперва цвета пикселей переводятся из RGB -представления в YUV -представление (в соответствующей ему цветовой модели YCbCr цвет представляется компонентами «яркость» Y, «цветоразность зеленый-красный» Сr и «цветоразность зеленый-синий» Сb). Затем в каждой второй строке и каждом втором столбце матрицы пикселей информация о цветовых компонентах Сb и Сr просто удаляется (!), что мгновенно уменьшает объем данных вдвое. Оставшиеся данные подвергаются специальной процедуре «сглаживания», при которой объем данных не изменяется, но потенциальная степень их сжимаемости резко увеличивается. На этом этапе учитывается желаемый коэффициент сжатия. Затем данные сжимаются алгоритмом Хаффмана.

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

Алгоритм МРЗ

Алгоритм МРЗ (точное название MPEG-1 Layer 3) является частью стандарта MPEG и описывает сжатие аудиоинформации. Помимо сжимаемого звукового фрагмента алгоритму передается также желаемый битрейт (англ. bitrate) — количество бит, используемых для кодирова­ния одной секунды звука. Этот параметр регулирует долю информации, которая будет удалена при сжатии.

Сжатие МРЗ также осуществляется в несколько этапов: звуковой фрагмент разбивается на небольшие участки — фреймы (англ. frames), а в каждом фрейме звук разлагается на составляющие звуковые колебания, которые в физике называют гармониками. С точки зрения математики, звук разлагается на группу синусоидальных колебаний с разными частотами и амплитудами. Затем начинается психоакустическая обработка - удаление маловажной для человеческого восприятия звуковой информации, при этом учитываются различные особенности слуха. Желаемый битрейт определяет, какие эффекты будут учитываться при сжатии, а также количество удаляемой информации. На последнем этапе оставшиеся данные сжимаются алгоритмом Хаффмана.

Алгоритм МРЗ позволяет сжимать звуковые файлы в несколько раз. При этом даже самый большой битрейт 320 Кбит/с стандарта МРЗ обеспечивает четырехкратное сжатие аудиоинформации по сравнению с форматом Audio CD, при таком же субъективном качестве звука. Формат МРЗ стал стандартом де-факто для распространения музыкальных файлов через Интернет.

Алгоритмы MPEG

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

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

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

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

Разновидности формата MPEG отличаются друг от друга по возможностям, качеству воспроизводимого изображения и максимальной степени сжатия:

• MPEG-1 — использовался в первых Video CD (VCD-I);

• MPEG-2 — используется в DVD и Super Video CD (SVCD, VCD-II);

• MJPEG — формат сжатия видео, в котором каждый кадр сжимается по методу JPEG;

• MPEG-4 — популярный эффективный формат сжатия видео;

• DivX, XviD — улучшенные модификации формата MPEG-4.

Вопросы и задания.

1. Для метода упаковки подсчитайте коэффициент сжатия текста, содержащего только прописные английские бук­вы, пробелы и знаки препинания (точка, запятая, дефис).

2. Для метода упаковки подсчитайте коэффициент сжатия текста, содержащего прописные и строчные русские бук­вы, пробелы, цифры и знаки препинания (точка, запя­тая, дефис).

3. Приведите примеры алгоритмов сжатия с потерей и без потери информации.

4. Что произойдет, если в упакованном методом RLE сооб­щении пропустить один байт?

5. Какова длина последовательности, после кодирования которой методом RLE получилось следующее: 11111111 11111111 11000000 00000001 00000010 11111111 00000000?

6. Как надо поступить при RLE-кодировании, если количе­ство идущих подряд одинаковых байтов больше 127 и не помещается в 7 разрядов?

7. Постройте дерево Хаффмана и выпишите коды символов для сообщения

AHFBHCEHEHCEAHDCEEHHHCHHHDEGHGGEHCHH.

Выводы.

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

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

Увидели насколько информатика связана с другими науками: физикой, биологией, колориметрией и, конечно, математикой.

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

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: