10.4 Кодирование информации
При кодировании с преобразованием осуществляется линейное преобразование исходного коррелированного множества отсчетов в некоррелированное множество посредством функций Фурье, Уолша, Харра и т.д.
Рис.10.16
С точки зрения сохранения информации различают методы кодирования
без потери информации и
с потерей информации.
В первых уменьшается статистическая или информационная избыточность, а во вторых стараются потерять прежде всего только ту информацию, к которой приёмник (например, человек) не чувствителен или мало чувствителен. Кодирование с потерей информации применяется тогда, когда полное сохранение информации не даёт нужной степени компрессии.
10.4.1 Кодирование без потерь
Алгоритм Хаффмана основан на статистике повторяемости. Чаще повторяющиеся элементы (символы, пиксели) кодируются более короткими последовательностями битов. Иногда используются готовые кодовые таблицы (симметричные алгоритмы), иногда они строятся в процессе сжатия на основе статистического анализа информации (асимметричные алгоритмы).
Алгоритм Лемпеля-Зива-Уэлча (LZW) отличается от алгоритма Хаффмана кодированием не отдельных элементов, а последовательностей. Используется в архиваторах LHARC, PKZIP, ARJ и т.п. Сжатие текстов – до 50%.
RLE-алгоритм (Run Length Encoding) кодирует последовательности одинаковых элементов, указывая элемент и длину последовательности.
10.4.2 Кодирование изображений с потерями
Алгоритм JPEG (Joint Photographic Experts Group) используется для цветных неподвижных изображений. Предложен в 1990 году.
Метод WIC (Wavelet Image Compression) – аналогичен JPEG, но вместо разложения по тригонометрическим функциям используется разложение по специальным волновым функциям – вэйвлетам, что увеличивает степень сжатия.
Метод MPEG (Moving Pictures Experts Group) – основан на JPEG, предложен в 1992 г.
Фрактальное сжатие. Термин "фрактальный" ввел Б. Мандельброт. Практическое применение для сжатия изображений нашли фракталы на основе систем итеративных функций (IFS - Iterated Function System). IFS строится для каждого изображения (автоматически) с таким расчётом, чтобы при их повторяющемся выполнении изображение постепенно уточнялось. Чем больше выполняется итераций, тем лучше его качество. Коэффициент сжатия достигает 10000:1, но процесс сжатия (т.е. построение IFS) длится долго.
Существуют три главных промышленных стандарта для сжатия и кодирования изображений:
Стандарты серии Н для сжатия видеоизображений (Н.261, Н.320),
JPEG для сжатия неподвижных изображений,
MPEG для сжатия подвижных изображений.
Рекомендации серии Н являются стандартами МККТТ (Международного Консультативного Комитета по Телеграфии и Телекоммуникации), или в английской аббревиатуре CCITT (Consultative Committee for International Telegraph and Telecommunication). Начиная с конца 70-х годов, эти стандарты нашли широкое признание среди большинства европейских производителей, а позднее и среди американских и японских производителей. Общепринятые стандарты (Н.216) и более современная версия (Н.320) предназначены для передачи изображений со скоростями, кратными 64Кбит/с (р 64 Кбит/с), являющейся наименьшей скоростью, какая может быть использована в узкополосных цифровых сетях с интеграцией служб (Integrated Services Digital Network - ISDN).
По существу, стандарты серии Н используют сходство между видеокадрами. Каждый новый кадр сравнивается с предыдущим, а кодируются и передаются только разности между ними. Хотя в действительности процесс сжатия является несколько более сложным, идея работы схемы основана на сходстве между кадрами.
Позднейшая версия стандартов серии Н, Н.320, является наиболее ранним стандартом из числа широко используемых. Оба эти стандарта реализуют комбинацию из методов ДКП (дискретное косинусное преобразование) и кодирования по Хаффману.
JPEG стандарт реализует следующий алгоритм (рис.10.17).
Рис.10.17
Исходное изображение для яркостной и цветоразностных составляющих делится на пиксельные блоки размером 8 на 8. Эти блоки обрабатываются независимо. После ДКП из временного (или пространственного) представления блока формируются такие же блоки в спектральной области. Другими словами, 64 числа, соответствующие амплитудам сигналов для каждого пикселя, заменяются другими 64 числами, соответствующими амплитудам спектральных составляющих по формуле:
;
;
;
;
.
При квадратном блоке M=N=8. Аmn - амплитуда сигнала.
Формула
обратного дискретного косинусного
преобразования:
,
;
.
После преобразования низкочастотные компоненты и компонента для постоянного тока размещаются в верхнем левом углу блока, в то время как высокие частоты находятся в нижнем правом. Пример результатов ДКП для одного блока представлен в табл.10.1.
Табл.10.1. Прямое дискретное косинусное преобразование
Исходный блок |
После ДКП |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Табл.10.2. Таблицы квантизации
Низкая компрессия |
Высокая компрессия |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Второй шаг на пути сжатия состоит в отказе от передачи некоторых из 64 спектральных значений. Как видно из табл.10.1, почти весь сигнал содержится в низкочастотных компонентах. Это означает, что самые высокие компоненты частоты могут быть устранены при некоторой деградации сигнала в качестве.
Степень сжатия определяется таблицей квантизации, пример которой для высокого и низкого значений компрессии показан в табл.10.2. Каждое значение в спектре делится на соответствующее значение в таблице и результат округляется к ближайшему целому числу. Например, верхнее левое значение таблицы - единица, оставляет неизменным значение постоянной составляющей. Нижнее правое значение при низкой компрессии (16) означает, что первоначальный диапазон от -127 до 127 уменьшен до от -7 до 7. Другими словами, значение будет уменьшено с восьми бит до четырех бит. При максимальном сжатии, нижнее правое значение (256) полностью устраняет спектральное значение.
На следующем шаге кодирования измененный спектр преобразуется из массива значений в линейную последовательность с помощью так называемого метода диагонального обхода или зигзаг упорядочивания. На рис.10.18 показан путь, по которому происходит считывание значений из массива. При таком способе все высокочастотные компоненты собираются вместе в конце линейной последовательности. Это позволяет группировать нули от устраняемых компонент спектра в самом конце, после чего нулевые значения кодируются с использованием алгоритма кодирования повторов (RLE), постоянная составляющая - с помощью ДИКМ, а потом результат обрабатывается с помощью «кодирования энтропии», т. е. алгоритма Хаффмана.
Рис.10.18
С помощью JPEG можно кодировать и движущиеся изображения, если подвергать сжатию каждый кадр независимо от других.
MPEG - аббревиатура от Moving Pictures Experts Group, названия комитета по стандартизации методов цифровой компрессии потоков видеоданных международной организации ISO/IEC (International Standards Organization/International Electrotechnical Commission). Первоначально задача комитета заключалась в разработке формата хранения и проигрывания аудио/видеоданных с компакт-дисков CD-ROM. В результате был создан стандарт MPEG-1, ориентированный на низкоскоростные (около 1 Мбит/с) каналы передачи информации и ограниченный разрешением кадра 352 × 288 (для PAL-сигнала). Затем по мере расширения задач передачи видео, повышения пропускной способности каналов и роста требований к визуальному качеству получаемых изображений появились MPEG-2, MPEG-4.
Стандарт MPEG-1 ориентирован на системы записи на компакт-диски (CD ROM) и низкоскоростные каналы передачи ТВ изображений (скорости цифрового потока 1,5 Мбит/с и меньше). При этом в стандарте MPEG-1 используется стандарт развертки с четкостью в четверо меньшей, чем в вещательном телевидении: 288 активных строк и 352 отсчета в активной части ТВ строки, для чего при кодировании сигналов ТВ систем обычной четкости производится децимация (прореживание) в два раза исходных ТВ отсчетов по вертикальным и горизонтальным направлениям ТВ растра.
Стандарт MPEG-2 был специально разработан для кодирования ТВ сигналов вещательного телевидения. Он позволяет получить полную четкость декодированного ТВ изображения, соответствующую Рекомендации 601 МККР. (При скорости передачи видеоданных 9 Мбит/с качество ТВ изображения соответствует студийному).
С принятием стандарта MPEG-2 работы по компрессии видеоданных перешли в область практической реализации. На данный момент можно назвать, по крайней мере, десяток фирм, которые выпускают для продажи кодеры и декодеры по стандарту MPEG-2. Наиболее известны из них Philips, Panasonic, Page Micro Technology, CLJ Communi-cation, Wegener Communications, Scientific-Atlanta, NTL, Segem Group и др.
В октябре 1995 г. через спутник Pan Am Sat начато 20-канальное ТВ вещание по стандарту MPEG-2, осуществляемое на территории Скандинавии, Бельгии, Нидерландов, Люксембурга, Ближнего Востока и Африки. В этой сети будет использовано более миллиона декодеров MPEG-2.
На стандарт MPEG-2 ориентированы и создаваемая сейчас 100-канальная система непосредственного телевизионного вещания (НТВ) Канады, и 150-канальная система НТВ оператора спутника "Эхостар", а также 10-канальная система НТВ Австралии, как и системы НТВ других стран.
В Российской Федерации телекомпания ВГТРК ввела в эксплуатацию четырехканальную систему НТВ по стандарту MPEG-2.
Пакет стандартов MPEG предусматривает и возможность перехода к телевидению высокой четкости (ТВЧ). Первоначально алгоритмы сжатия видеоданных сигналов ТВЧ разрабатывались в виде самостоятельного стандарта MPEG-3, однако на последующих этапах стандарт MPEG-3 был объединен со стандартом MPEG-2, после чего стандарт MPEG-3, как самостоятельный, перестал использоваться.
Стандарт MPEG-4 - это организация видеоконференций при передаче видеоданных по цифровым телефонным каналам. При этом используется стандарт развертки с четкостью, в четыре раза меньшей, чем в стандарте MPEG-1. Так, кадр ТВ изображения содержит 144 активные строки и 176 отсчетов ТВ сигнала в активной части строки. Этот стандарт может также использоваться в низкоскоростных системах мультимедиа.
До сих пор речь шла только о компрессии изображений. Но полноценное видео подразумевает и звуковую составляющую. Считается, что звук CD-качества требует оцифровки с частотой 44,1 кГц при глубине 16 бит на канал, что соответствует потоку в 706 Кбит/с на канал (1,4 Мбит/с для стерео). DAT-качество сигнала определяет частоту оцифровки в 48 кГц (полоса частот 4-24 000 Гц) и увеличивает поток до 768 Кбит/с на канал. Подход к сжатию информации основан на методе MUSICAM.
MPEG-стандарт разрешает три уровня (Layer) компрессии аудио. Layer 1 использует наиболее простой алгоритм с минимальной компрессией, что предполагает 192 Кбит/с на канал. Алгоритм Layer 2 более сложный, зато и степень компрессии больше - 128 Кбит/с на канал. Мощный алгоритм сжатия цифрового звука CD-качества (в 11 раз без различаемых человеческим ухом потерь) Layer 3 обеспечивает максимально возможное качество звука при жестких ограничениях потока - не более 64 Кбит/с на канал. В основном он предназначен для Интернет. Его значение столь велико, что он получил особое сокращенное наименование MP3, что означает MPEG Layer 3.
MPEG-2 изначально был нацелен на решение задачи передачи телевизионных изображений. MPEG-2, как определено в документе ISO/IEC 13818-2, объединяет семейство взаимосогласованных и совместимых сверху вниз цифровых стандартов сжатия телевизионных сигналов. Точнее, он допускает 4 уровня (Levels) разрешения кадра и 5 базовых профилей (Profiles) кодирования сигналов яркости и цветности.
Уровни: низкий LL (Low Level) с разрешением кадра 352 х 288 (соответствует MPEG-1), основной ML (Main Level) 720 х 576, высокий HL-1440 (High Level) 1440 х 1152 и высокий HL-1920 1920 х 1152. Согласно Рекомендации ITU-R BT.601 (International Telecommunications Union - Recommendation) основной уровень определяет разрешение стандартного телевизионного кадра, а высокие уровни ориентированы на телевидение высокой четкости. Профили: простой SP (Simple Profile), основной MP (Main Profile), два масштабируемых - по отношению сигнал/шум SNR Scalable Profile и по разрешению Spatially Scalable Profile и, наконец, высокий HP (High Profile).
Поток видеоданных представляет собой иерархическую структуру, элементы которой строятся и объединяются друг с другом в соответствии с определенными синтаксическими и семантическими правилами.
Существует 6 типов элементов этой иерархической структуры:
Видеопоследовательность
Группа изображений
Изображение
Срез
Макроблок
Блок.
Видеопоследовательность – элемент потока видеоданных высшего уровня. Она представляет собой серию последовательных кадров телевизионного изображения. MPEG-2 допускает как построчные, так и чересстрочные последовательности. Чересстрочная последовательность – это серия телевизионных полей. В процессе компрессии поля могут кодироваться раздельно. Это дает изображения типа «поле». Два поля, кодируемые как телевизионный кадр, образуют изображение типа «кадр». В одной чересстрочной последовательности могут использоваться и изображения-поля, и изображения-кадры. В последовательностях с построчным разложением каждое изображение представляет собой кадр.
В соответствии с используемыми методами дифференциального кодирования различают три типа изображений: I, P и B. Изображение типа I кодируется по стандарту JPEG с использованием только той информации, которая содержится в нем самом (I - Intra-coded picture). В нем устраняется только пространственная избыточность. При кодировании P и B изображений используется межкадровое кодирование. При кодировании изображения типа P формируется разность между исходным изображением и предсказанием, полученным на основе предшествующего или последующего изображения типа I (P – Predictive-coded picture). Изображение типа B – это изображение, при кодировании которого используется предсказание, сформированное на основе предшествующего и последующего изображений типа I или P (B – Bidirectionally-predicted-coded picture). В изображениях типа P и B устраняется и пространственная, и временная избыточность.
Серия изображений, содержащих одно I-изображение, называется группой изображений. Пример видеопоследовательности с различными типами изображений показан на рис.10.19 (стрелками показаны направления предсказания в пределах одной группы изображений). Чем больше группа изображений, тем большая степень компрессии может быть достигнута.
Рис.10.19
Типичным является следующий порядок кодирования I, Р, В кадров. В кодере вырабатываются группы, состоящие из 15 чередующихся кадров: I0, B1, B2, P3, B4, B5, P6, B7, B8, P9, B10, B11, I12, B13, B14, P15 и т. д., в которых I кадры следуют с интервалом: (1/25 Гц) х 15= 0,6 с.
При передаче по каналу связи порядок следования I, Р и В кадров меняется. В декодер в начале поступают опорные I и Р кадры, без которых нельзя начать декодирование. Типичным является следующий порядок передачи I, P, B кадров: I0, P3, B1, B2, P6, B4, B5, P9, B7, B8, I12, B10, B11 - P15, B13 и т. д.