Проблемы алгоритмов архивации с потерями.

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

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

 

Стандарт MPEG

История создания стандарта MPEG начинается с 1988 года, когда Совместным Техническим Комитетом по Информационной технологии (JTSI) была организована специальная группа MPEG (Motion Pictгme Experls Group - экспертная группа по движущимся изображениям). Перед MPEG была поставлена задача разработки методов сжатия и восстановления цифрового видеосигнала в рамках стандарта, объединяющего потоки видео-, аудио- и иной цифровой информации. Результатом работы MPEG явилось создание международных стандартов для сжатия телевизионного сигнала: MPEG-1, MPEG-2, MPEG-3, MPEG-4. Использование стандартов MPEG позволяет движущиеся изображения обрабатывать и хранить как компьютерные данные, передавать по существующим сетям и каналам связи.

Стандарт MPEG-1 (1992 г.) предназначен для записи видеоданных на компакт-диски и передачи изображения ТВ по сравнительно низкоскоростным (1...3 Мбит/с) каналам связи. В нем используется стандарт развертки с четкостью значительно меньшей, чем в вещательном ТВ: 288 активных строк в кадре с 352 отсчетами а активной строке.

Стандарт MPEG-2 (1994 г.) является основным стандартом и обеспечивает высокую четкость вещательного ТВ: 576 активных строк в кадре и 720 отсчетов в строке. При скоростях передачи 3...10 Мбит/с MPEG-2 обеспечивает качество обычного телевизионного стандарта, а на скоростях 15...30 Мбит/с - качество ТВЧ.

Стандарт MPEG-3 рассматривался как промежуточный вариант и практического применения не получил.

Стандарт MPEG-4 предназначен для передачи видеоданных в низкоскоростных системах мультимедиа и видеоконференций по цифровым телефонным каналам. По своим характеристикам MPEG-4 уступает возможностям MPEG-1, обеспечивая еще меньшую четкость: 144 активных строки в кадре при 176 отсчетах в строке. Это позволяет снизить скорость цифрового потока до 64 кбит/с.

MPEG-2.

Алгоритм, положенный в основу MPEG-2, включает определенный базовый набор последовательных процедур обработки: дискретизацию аналоговогo видеосигнала, предварительную обработку, дискретное косинусное преобразование (ДКП), квантование, кодирование.

В качестве исходного видеосигнала для сжатия выступает компонентный ТВ сигнал RGB, который затем преобразуется в сигнал яркости Y и два цветоразностных сигнала U, V (А-Y, В-Y). Именно эти сигналы (Y, U, V) затем подвергаются дискретизации в формате 4:2:0 или 4:2:2.

После дискретизации осуществляется предварительная обработка, которая имеет целью подготовку массива отсчетов (Y, U, V) для реализации следующих операций. На этом этапе массив отсчетов изображения разбивается на последовательность фрагментов размером (16×16) элементов (пикселов). Каждый фрагмент состоит из блоков яркости (Y) и блоков цвета (U, V) (рис. 7.6). Общее количество блоков, имеющих размер (8×8) и образующих фрагмент изображения, в зависимости от формата дискретизации будет 8 или 6. Из них четыре блока - 4 (8×8) образуют макроблок (16×16) и несут информацию яркости (Y). Каждому сигналу цвета (U, V) в формате 4:2:2 соответствует по два блока (8×8), а в формате 4:2:0 - по одному блоку (8×8).

Рис. 7.6. Разбивка изображения на блоки в MPEG-2 155

 

Основная компрессия достигается благодаря устранению избыточности ТВ сигнала. Статистическая избыточность предполагает межэлементную корреляцию как внутри кадра, так и между кадрами. В свою очередь, это обеспечивает возможность внутрикадрового и межкадрового предсказания. Для того чтобы реализовать процедуру предсказания, последовательность кадров видеосигнала подразделяется на три типа: опорные, Р-, В-кадры.

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

Р-кадры (Predicted Frames) используют межкадровое предсказание «вперед» по предшествующим I- и Р-кадрам. Степень сжатия в них в три раза больше, чем в I-кадрам. Кадры I вида служат опорными для последующих Р-, В-кадров.

В-кадры (Bidirectionally Predicted Frames) применяют для двунаправленного предсказания, т. е. относительно как предыдущих, так и последующих кадров. В-кадры имеют наибольшее сжатие.

Кадры объединяются в группы последовательных кадров. Каждая группа начинается с I-кадра и имеет в своем составе переменное число Р- и В-кадров. I-кадры кодируются (сжимаются) и соответственно декодируются без обращения к другим кадрам. Сжатие Р-, В-кадров предполагает выявление различии (разностей) между кадрами. Техника вычисления разностей, реализованная в стандарте, имеет смысл «предсказания движения» (motion prediction). Суть ее состоит в том, что изменения в изображении интерпретируются как смещение малых областей изображения. Разбив изображение на фрагменты (16×16) элементов и определив их расположение в кадре, можно для каждого фрагмента найти набор параметров, предсказывающий направление и значение смещения. Этот набор данных называют вектором движения, а всю операцию - предсказанием с компенсацией достижения, которая, кроме вектора движения, еще вырабатывает значения ошибок, характеризующих разницу между предсказанными и истинными величинами.

На следующем этапе обработки разностные ошибки предсказания блока (8×8) или сам блок подвергаются двумерному дискретному косинусному преобразованию (DCT-discrete cosine traпsform). ДКП представляет собой разновидность преобразования Фурье и так же, как оно, имеет обратное преобразование (ОДКП), что позволяет переходить от пространственного представления блока к спектральному представлению и обратно. В результате применения ДКП блок (8×8) (рис. 7.7, а) трансформируется в блок (8×8) частотных коэффициентов (см. рис. 7.7, б). Каждый коэффициент характеризует амплитуду определенной частотной составляющей. Причем низкочастотные составляющие расположены ближе к левому верхнему углу блока, а высокочастотные - справа внизу.

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

ь~и%1~%~~~~.~ iвJr~iJF'L:вJ R1 JГд1Р1 JFJ'F~I и~гиаггЕг~ rr~rrrmrл иггг~гг~ ~~с~с~~~

Рис. 7.7. Процесс ДКП, квантования и Z-упорядочивания

 

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

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

Формирование последовательности квантованных коэффициентов для подачи на кодер осуществляется с помощью Z-упорядочивания (см. рис. 7.7, в), которое выстраивает коэффициенты в порядке возрастания частоты. Одновременно в последовательности коэффициентов образуются блоки, состоящие из одних нулей. Вид последовательности представлен на рис. 7.7. Здесь же изображен сжатый вид записи этой последовательности в форме повторяющихся одинаковых коэффициентов (RLE).

Тип кодирования в стандарте не определен, что допускает применение различных видов кодов. Это может быть код Хаффмена, арифметический код. Дополнительная компрессия достигается отдельным кодированием больших блоков нулей. Кодер МРЕG-2 должен иметь многокадровый буфер (память), в котором происходит накопление данных до их использования. Поскольку канал связи функционирует с постоянной скоростью, то буфер позволяет устранить флюктуации скорости источника.

Звуковая часть стандарта MPEG-2 регламентирует кодирование многоканального звука. Стандарт поддерживает до 5 полных широкополосных каналов плюс дополнительный низкочастотный канал и (или) до семи многоязычных комментаторских каналов. Общепринятым эталоном высшего качества звука считается качество звука, воспроизводимого с компакт-дисков. Это качество принято и для стандарта MPEG-2, и достигается оно с помощью системы компрессии цифрового сигнала звука MUSICAM. Для двухканального стереофонического сопровождения скорость цифрового потока составляет 256 кбит/с (по 128 кбит/с на моноканал).

Перед подачей в канал связи сигнал транспортного потока подвергается дополнительному помехоустойчивому кодированию и модуляции. Эти операции не входят в стандарт МРЕG. В частности, в стандарте DVB применяется каскадное помехоустойчивое кодирование: внешний код - код Рида - Соломона (204, 188), внутренний код - сверточный с относительной скоростью 1/2, 2/3, 3/4, 5/б, 7/8. Модуляция осуществляется по методу ФМ-4.

 

Алгоритм JPEG

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

Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG - Joint Photographic Expert Group - подразделение в рамках ISO - Международной организации по стандартизации. В целом алгоритм основан на дискретном косинусоидальном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов.

Метод позволяет сжимать некоторые изображения в 10-15 раз без серьезных потерь.