Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Глава 1. Теория сжатия информации.

Введение

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

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

Организация эффективного телевизионного и мультимедийного вещания, на данный момент является первоочередной задачей. Однако основной сложностью при работе с видео являются большие объемы дискового пространства, необходимого для хранения даже небольших фрагментов. Например, при записи на один компакт-диск "в бытовом качестве" на него можно поместить несколько тысяч фотографий, примерно 10 ч музыки и всего полчаса видео. Видео "телевизионного" формата 720x576 пикселов 25 кадров в секунду в системе RGB требует потока данных примерно в 240 Мбит/с (т. е. 1.8 Гб/мин), в час 108Гб. Для 24 часовой записи потребуется 2592 Гб (2,6 Tб).. Если, к примеру, использовать модем со скоростью передачи 56 Kб/с, то ему потребуется около 2 лет для передачи одного дня видео съемки.

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

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

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

Глава 1. Теория сжатия информации.

Основные понятия.

Сжатие видео — уменьшение количества данных, используемых для представления видеопотока. Сжатие видео позволяет эффективно уменьшать поток, необходимый для передачи видео по каналам радиовещания, уменьшать пространство, необходимое для хранения данных на CD, DVD или жёстких дисках.

Компрессия статического или видео изображения может быть осуществлено двумя основными методами – с потерей или без потери качества.

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

Сжатие с потерями качества - потери качества могут наблюдаться в случае, если в процессе сжатия информация была утеряна. Однако с точки зрения человеческого восприятия сжатием с потерями следует считать лишь то сжатие, при котором на глаз можно отличить результат сжатия от оригинала. Таким образом, несмотря на то, что два изображения – оригинал и результат сжатия с использованием того или иного компрессора — побитно могут не совпадать, разница между ними будет совсем незаметной. Основная идея – значительно увеличить коэффициент сжатия, пренебрегнув незначительными деталями, не заметными для человеческого глаза. Примерами здесь могут служить алгоритмы JPEG для сжатия статической графики и алгоритм M-JPEG для сжатия видео.

Сжатие без потерь с точки зрения восприятия

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

Базовые стратегии сжатия

Базовых стратегий сжатия три:

1. Преобразование потока ("Скользящее окно-словарь"). Описание поступающих данных через уже обработанные. Сюда входят LZ-методы для потоков "слов", т. е. когда комбинации поступающих элементов предсказуемы по уже обработанным комбинациям. Преобразование по таблице, RLE, LPC, DC, MTF, VQ, SEM, Subband Coding, Discrete Wavelet Transform - для потоков "элементов", т. е. когда не имеет смысла рассматривать комбинации длиной два и более элемента или запоминать эти комбинации, как в случае Linear Prediction Coding.

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

Статистическая стратегия.

а) Адаптивная (поточная). Вычисление вероятностей для поступающих данных на основании статистики по уже обработанным данным. Кодирование с использованием этих вычисленных вероятностей. Семейство РРМ-методов- для потоков "слов", адаптивные варианты методов

Хаффмана и Шеннона - Фано, арифметического кодирования - для потоков "элементов". В отличие от первого случая, давно собранная статистика имеет тот же вес, что и недавняя, если метод не борется с этим специально, что гораздо сложнее, чем в случае LZ. Кроме того, считаются вероятными все комбинации, даже те, которые еще не встречались в потоке и скорее всего никогда не встретятся.

б) Блочная. Отдельно кодируется и добавляется к сжатому блоку его статистика. Статические варианты методов Хаффмана, Шеннона - Фано и арифметического кодирования - для потоков "элементов". Статическое СМ - для "слов".

3. Преобразование блока. Входящие данные разбиваются на блоки, которые затем трансформируются целиком, а в случае блока однородных данных лучше брать весь блок, который требуется сжать. Это методы сортировки блоков ("BlockSorting''-методы: ST, BWT, PBS), а также Fourier Transform, Discrete Cosine Transform, фрактальные преобразования, Emimerative Coding.

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

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

■ чем больше и однороднее данные и память, тем эффективнее блочные методы;

■чем меньше и неоднороднее данные и память, тем эффективнее поточные методы;

■ чем сложнее источник, тем сильнее улучшит сжатие оптимальная преобразование;

■ чем проще источник, тем эффективнее прямолинейное статистическое решение.

Типы избыточности

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

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

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

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

Статистическая избыточность. Сигналы видеоизображения содержат много повторяющейся информации, включая регулярность сигналов синхронизации строки кадров, так что значения отсчетов сигнала в определенной степени являются предсказуемыми. Для уменьшения объема передаваемых данных может использоваться статистическая вероятность следующего отсчета данных, который по известному соотношению связан с предыдущим. Количество бит может быть также уменьшено, поскольку нет необходимости передавать информацию, которая обычно включается в темные строки и поля аналоговой видеокартинки. Все, что нужно передавать, — это коды, показывающие синхронизацию строк и кадров. Избыточная информация тоже не передается, так что скорость передачи бит, уменьшается без какого-либо ухудшения качества изображения. Это процесс без потерь. Анализ материалов некоторых программ показал, что объем избыточной информации может достигать уровня 98 %.

1.4. Преобразование цветового представления растрового изображения.

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

В связи с этим в схеме кодирования видеоданные переводятся в YUV-представление, также называемое YCrCb (Y – компонент яркости и U (или Cr) и V (или Cb) – два компонента цветности, где Cr – Chromatic red (хроматический красный), Cb – Сhromatic blue (хроматический синий)). Это необходимо потому, что при представлении изображений в RGB–виде нельзя различить яркостную и цветовую информацию.

Преобразование цветового пространства RGB в цветовое пространство YUV представляется с помощью матрицы перехода в виде

Обратное преобразование осуществляется с помощью обратной матрицы перехода в виде

Теоретически каждый элемент изображения требует 3 байта. Такое представление, когда и яркость, и компоненты цветности имеют равное число независимых значений, обычно обозначают как схема 4 : 4 : 4. Способ сжатия цветовой информации называется субдискретизацией и заключается в объединении цветовой информации для соседних элементов изображений. При использовании данного способа значения яркости Y запоминаются для каждого элемента изображения. Для значений U и V вычисляется и запоминается только среднее значение для четырех (схема субдискретизации 4 : 2 : 2), восьми (схема субдискретизации 4 : 1 : 1) и 16 элементов (схема субдискретизации 16 : 1 : 1). Требуемый объем памяти на каждый пиксел при таких способах составляет, соответственно, 12, 10 и 9 битов. Таким образом, количество данных на элемент изображения можно сократить с 24 до 12, 10 или 9 битов соответственно.

Алгоритм Хаффмана

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

Алгоритм построения схемы можно представить следующим образом:

1. Вычисляем вероятность появления каждого символа в информации

2. Каждому символу присваивается значение равное его частоте вхождения

3. Полученный список элементов (пара символ — значение) сортируется по убыванию: от часто встречаемых к менее встречаемым

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

5. Новый список сортируется по убыванию

6. Операции 4, 5 выполняются до тех пор, пока не останется один элемент

7. Выписывается последний оставшейся элемент

8. От него откладывают две ветви с элементами, которые его составляют

9. От каждого элемента, если он не является символом, откладываются такие же две ветви с входящими в него элементами

10. Процесс выполняется до тех пор, пока все элементы не будут выписаны

11. Каждому ребру назначается коды 0 и 1( )

12. Для каждого символа (не элемента) в дереве выписывается префиксный код, как последовательность кодов рёбер идущих от вершины к символу


Алгоритм Шеннона — Фано

Алгоритм Шеннона —Фано — один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано. Алгоритм использует коды переменной длины: часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся — кодом большей длины. Коды Шеннона — Фано префиксные, то есть, никакое кодовое слово не является префиксом любого другого. Это свойство позволяет однозначно декодировать любую последовательность кодовых слов.

Основные этапы:

1. Символы первичного алфавита выписывают в порядке убывания вероятностей.

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

3. В префиксном коде для первой части алфавита присваивается двоичная цифра «0», второй части — «1».

4. Полученные части рекурсивно делятся и их частям назначаются соответствующие двоичные цифры в префиксном коде.

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

Kодирование длин серий (RLE)

Данный алгоритм чрезвычайно прост в реализации. RLE (Run Length Encoding), или групповая кодировка - один из наиболее старых алгоритмов сжатия данных. Суть метода сжатия заключается в замене символов, которые повторяются, на один некоторый флаг и счетчик повторений кодируемого символа. Основная проблема заключается в том, чтобы архиватор при восстановлении сжатой последовательности смог отличить в анализируемом потоке сжатую серию от несжатых символов. Решение данной задачи достаточно очевидное - поместить во все цепочки некоторые флаги (например, использовать первый бит как признак кодировки серии). Метод достаточно эффективный для графических изображений в формате «байт на пиксел» (например, форматы РСХ и BMP используют кодировку RLE) .

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

Арифметическое кодирование.

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

Перед началом работы соответствующий тексту интервал есть [0; 1).

При обработке очередного символа его ширина сужается за счет выделения этому символу части интервала.

1.6.5. Дискретное косинусное преобразование

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

При использовании частотно-временных преобразований используется понятие периодического расширения функции, заключающееся в следующем: если преобразуется дискретный ряд отсчетов, то его спектр становится периодичным, а в случае преобразования частотного спектра периодически продолжается восстановленный дискретный ряд данных В точках нечетного периодического расширения исходного ряда вперед и назад (на стыках сегментов) имеет место разрыв амплитуд (рис.2, б). В этом случае из-за скачков амплитуды Фурье-спектр B'(p) убывает пропорционально 1/p, где р – индекс спектрального коэффициента. Четное расширение приводит к разрыву не амплитуд, а первой производной (рис.2, в), вследствие чего частотный спектр ДКП B''(p) убывает пропорционально 1/p2. Таким образом, из-за сужения спектра для восстановления сигнала с заданной точностью требуется меньшее число коэффициентов. ДКП представляет изображение в виде набора спектральных компонентов, что позволяет вести дальнейшую обработку изображения, в частности уменьшение точности представления коэффициентов с учетом особенностей визуальной системы человека. Данное преобразование выполняется поблочно.

 

 

Рис. 2. Сравнение спектральных особенностей ДКП и ДПФ: а – последовательность исходных отсчетов А(m); б – расширение последовательности для преобразования Фурье А'(m) и ее частотный спектр B(p)~1/p; в – расширение последовательности для косинусного преобразования А''(m) и ее частотный спектр B'(p) ~ 1/p2

Прямое двухмерное ДКП блока ||A||размером M x N исходного изображения определяется следующим образом:

(1)

где B[p,q] – значения спектральных коэффициентов в преобразованном блоке;

m,n – координаты пикселей в исходном блоке изображения; p,q – индексы коэффициентов в преобразованном блоке; A[m,n] – значения пикселей в исходном блоке ||A||.

В результате исходный блок точек преобразуется в матрицу частотных коэффициентов ДКП такого же размера. Наиболее важным коэффициентом является коэффициент с координатами (0,0), поскольку он представляет собой среднее значение всей матрицы и является постоянной составляющей сигнала DC (Direct Current). Все остальные коэффициенты являются переменными составляющими АС (Alternating Current).

Обратное ДКП определяется следующим выражением:

(2)

Для стандартного блока 8 x 8, M = N = 8, поэтому ДКП имеет вид

(3)

где

Матричная форма выражения (2) имеет следующий вид:

B = TMT ′, (4)

где

– значения элементов матрицы Т; M – сдвинутый блок исходного изображения; T ′ – транспонированная матрица T.

В выражении (4) матрица М получена из исходной матрицы путем вычитания 128 из каждого элемента пикселя, так как пиксельные значения черно-белого изображения изменяются от 0 до 255 (чисто черный цвет представляется 0, чисто белый цвет – 255), а ДКП работает со значениями пикселей от –128 до +127.

Восстановленный блок вычисляется по формуле A′ = round (T BT ) + 128 , где round(x) – функция округления до целого.

Матрица частотных коэффициентов ДКП не имеет прямой геометрической связи с положением пикселей видеосигнала на растре, а представляет собой форму математической записи, при которой частотные коэффициенты ДКП являются двухмерным спектром изображения по горизонтальному и вертикальному направлениях кадра. Изображение базисных функций преобразования ДКП (3) представлено на рис. 2. Графический смысл этого преобразования заключается в том, что блок изображения рассматривается как суперпозиция изображений синусоидальных колебаний разной частоты. Так, если изображение имеет постоянную яркость, то (для простоты рассматривается черно-белое изображение) его блок коэффициентов будет содержать только один коэффициент DC с координатами (0,0). Если яркость изображения меняется по косинусоиде вдоль горизонтальной оси, то его блок ДКП будет содержать два коэффициента (0,0) и (2,0). Численные значения коэффициентов соответствуют яркостям соответствующих составляющих. Более сложные изображения представляются большим количеством коэффициентов ДКП.

Спектр ДКП имеет важную особенность для компрессии видеоданных: основная энергия частотных составляющих этого спектра концентрируется в небольшой области около нулевых частот. Амплитуда высокочастотных оставляющих мала или равна нулю. (Рис. 3.)

Важной операцией является перевод матричной формы представления коэффициентов в векторную. Матрица коэффициентов просматривается в определенном порядке с целью получения длинных последовательностей нулей и формирования вектора таким образом, чтобы с увеличением порядкового номера коэффициента возрастала и соответствующая ему частота. Это необходимо для правильного квантования. Наиболее распространенный порядок просмотра матрицы – сканирование зигзагом. (Рис. 4.)

 

Рис. 3. Набор базисных функций ДКП


Рис. 4. Зигзаг сканирование

 

Большинство из существующих стандартных алгоритмов видеосжатия, например таких, как MPEG-1, MPEG-2, MPEG-4, H.261, H.263, divX, основаны на разбиении изображения на блоки (обычно размером 8 х 8 пикселей) и использовании ДКП внутри каждого блока. Подобные алгоритмы имеют следующие недостатки:

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

- при больших степенях сжатия на изображении становится видна блочная структура, этот эффект называется "блокинг-эффектом";

- энтропийное кодирование спектральных коэффициентов из различных блоков не зависит от информации в соседних блоках.

Квантование

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

Для решения этой задачи стандарт JPEG определяет простой механизм именуемый квантованием (quantization), представ­ляющим, в свою очередь, условное название (division). Чтобы выполнить квантование коэффициентов DCT, доста­точно просто разделить их на другое значение и округлить до ближайшего целого числа:

Квантованное значение = Округление (Коэффициент/ Значение кванта)

Чтобы обратить процесс, следует выполнить умножение:

Коэффициент = Квантованное значение х Значение кванта

При выборе в качестве значения кванта числа 20, более поло­вины коэффициентов на Рис. 7 было бы преобразовано в нули.


Рис. 7 Коэффициенты DCT

 

Чтобы определить значения квантов для изображения, в формате JPEG используется массив из 64 элементов, на­зываемый таблицей квантования (quantization table). Можно использовать несколько таблиц квантова­ния с тем, чтобы все компоненты, которые должны быть квантованными, не использовали одинаковые значения. Ка­ждое значение таблицы квантования используется для кван­тования соответствующего коэффициента DCT.

Стандарт JPEG не определяет значения квантования, которые должны использоваться. Это остается за конкретной про­граммой. Тем не менее, стандарт все же предоставляет в ка­честве примера пару таблиц квантования, которые, как ут­верждается в стандарте, были проверены на опыте и показали хорошие результаты. Эти таблицы показаны на Рис. 7.

На Рис. 8 показаны результаты квантования дискретных значений из Рис. 6, выполненного с помощью показанной на Рис. 7 таблицы квантования для компонента Y. После квантования только 19 из 64 коэффициентов DCT значения отличны от нуля.

Рис. 8. Примеры таблиц квантования из стандарта JPEG

 
 

 


Рис. 9. Результаты квантования дискретных значений

 

Базовый алгоритм.

Рассмотрим применение алгоритма. Алгоритм ориентирован на сжатие полноцветных (с глубиной цвета 24 бита, по 8 бит на каждую из 3-х компонент) изображений или изображений в градациях серого без резких переходов цветов. Алгоритм оперирует областями 8x8 точек, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого при применении к матрице такой области дискретного косинусного преобразования (ДКП) значимыми оказываются только первые коэффициенты. Таким образом, сжатие в JPEG осуществляется за счет плавности изменения цветов в изображении. Структурная схема алгоритма JPEG представлена на рис. 10.

 

Рис. 10. Структурная схема алгоритма JPEG.

 

На этом рисунке в блоке «RGB в YCbCr» происходит преобразование цветовых пространств. YCbCr представляет собой аппаратно-ориентированную модель, используемую в телевидении и служащую для сокращения передаваемой полосы частот за счет использования психофизиологических особенностей зрения. В этой модели Y – интенсивность цвета, а Cb и Сr – синяя и красная цветоразностные компоненты. Кодирование изображений в этой палитре существенно уменьшает количество информации, требуемой для воспроизведения изображения без существенной потери его качества.

В блоке «Дискретизация» происходит разделение исходного изображения на матрицы 8x8 точек и формирование из них рабочих матриц ДКП по 8 бит отдельно для каждой компоненты. При больших степенях сжатия этот шаг может выполняться чуть сложнее. Изображение делится по компоненте Y, как и в первом случае, а для компонент Сr и Сb матрицы набираются через строчку и через столбец. То есть из исходной матрицы размером 16x16 получается только одна рабочая матрица ДКП. При этом, как нетрудно заметить, мы теряем 3/4 полезной информации о цветовых составляющих изображения и получаем сразу сжатие в 2 раза. Мы можем поступать так благодаря работе в пространстве YCrCb. На результирующем RGB-изображении, как показала практика, это сказывается несильно.

Блок «ДКП» является ключевым компонентом работы алгоритма. ДКП позволяет переходить от пространственного представления картинки к ее спектральному представлению и обратно. Воздействуя на спектральное представление картинки, состоящее из «гармоник», то есть, отбрасывая наименее значимые из них, можно балансировать между качеством воспроизведения и степенью сжатия.

В блоке «Квантование» происходит деление рабочей матрицы на матрицу квантования поэлементно с округлением элементов до целого значения.

На этом шаге осуществляется управление степенью сжатия. Задавая матрицу квантования с большими коэффициентами, можно получить больше нулей и, следовательно, большую степень сжатия.

В блоке «Зигзаг» – сканирование» происходит перевод матрицы размером 8x8 точек в 64-элементный вектор при помощи «зигзаг»-сканирования.

В блоке «RLE» происходит операция свертывания полученного вектора с помощью алгоритма группового кодирования RLE.

В блоке «сжатие по Хаффману» происходит свертывание получившихся пар кодированием по Хаффману.

Процесс восстановления изображения в этом алгоритме полностью симметричен.

Алгоритм JPEG 2000

Алгоритм JPEG 2000 разработан той же группой экспертов в области фотографии, что и JPEG. Основные отличия алгоритма в JPEG 2000 от алгоритма в JPEG заключаются в следующем:

1. Лучшее качество изображения при сильной степени сжатия. Или, что то же самое, большая степень сжатия при том же качестве для высоких степеней сжатия. Фактически это означает заметное уменьшение размеров графики "Web-качества", используемой большинством сайтов.

2. Поддержка кодирования отдельных областей с лучшим качеством. Известно, что отдельные области изображения критичны для восприятия человеком (например, глаза на фотографии), в то время как качеством других можно пожертвовать (например, задний план). При "ручной" оптимизации увеличение степени сжатия проводится до тех пор, пока не будет потеряно качество в какой-то важной части изображения. Сейчас появляется возможность задать качество в критичных областях, сжав остальные области сильнее, т.е. мы получаем ещё большую окончательную степень сжатия при субъективно равном качестве изображения.

3. Основной алгоритм сжатия заменён на wavelet. Помимо указанного повышения степени сжатия это позволило избавиться от 8-пиксельной блочности, возникающей при повышении степени сжатия. Кроме того, плавное проявление изображения теперь изначально заложено в стандарт Progressive JPEG, активно применяемый в Интернет, появился много позднее JPEG.

4. Для повышения степени сжатия в алгоритме используется арифметическое сжатие. Изначально в стандарте JPEG также было заложено арифметическое сжатие, однако позднее оно было заменено менее эффективным сжатием по Хаффману, поскольку арифметическое сжатие было защищено патентами. Сейчас срок действия основного патента истёк, и появилась возможность улучшить алгоритм.

5. Поддержка сжатия без потерь. Помимо привычного сжатия с потерями JPEG 2000 обеспечивает и сжатие без потерь.

Таким образом, становится возможным использование JPEG для сжатия медицинских изображений, в полиграфии, при сохранении текста под распознавание OCR-системами и т.д.

6. Поддержка сжатия однобитных (2-цветных) изображений. Для сохранения однобитных изображений (рисунки тушью, отсканированный текст и т.п.) ранее повсеместно рекомендовался формат GIF, поскольку сжатие с использованием ДКП весьма неэффективно к изображениям с резкими переходами цветов. В JPEG при сжатии 1-битная картинка приводилась к 8-битной, т.е. увеличивалась в 8 раз, после чего делалась попытка сжимать, нередко менее чем в 8 раз. Сейчас можно рекомендовать JPEG 2000 как универсальный алгоритм.

7. На уровне формата поддерживается прозрачность. Плавно накладывать фон при создании WWW страниц теперь можно будет не только в GIF, но и в JPEG 2000. Кроме того, поддерживается не только 1 бит прозрачности (пиксел прозрачен/непрозрачен), а отдельный канал, что позволит задавать плавный переход от непрозрачного изображения к прозрачному фону.

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

Схема работы алгоритма JPEG 2000 представлена на рис. 11.

Рассмотрим алгоритм по шагам.

Шаг 1. В JPEG 2000 предусмотрен сдвиг яркости (DC level shift) каждой компоненты (RGB) изображения перед преобразованием в YUV. Это делается для выравнивания динамического диапазона (приближения к 0 гистограммы частот), что приводит к увеличению степени сжатия.

Шаг 2. Переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную (Red),зелёную (Green) и синюю (Blue) составляющие цвета точки, в цветовое пространство YUV. Этот шаг аналогичен JPEG, за тем исключением, что кроме преобразования с потерями предусмотрено также и преобразование без потерь.

Рис. 11. Схема работы алгоритма JPEG 2000

Шаг 3. Дискретное wavelet преобразование (DWT).

Шаг 4. Так же, как и в алгоритме JPEG, после DWT применяется квантование. Коэффициенты квадрантов делятся на заранее заданное число. При увеличении этого числа снижается динамический диапазон коэффициентов, они становятся ближе к 0, и мы получаем большую степень сжатия. Варьируя эти числа для разных уровней преобразования, для разных цветовых компонент и для разных квадрантов, мы очень гибко управляем степенью потерь в изображении. Рассчитанные в компрессоре оптимальные коэффициенты квантования передаются в декомпрессор для однозначной распаковки.

Шаг 5. Для сжатия получающихся массивов данных в JPEG 2000 используется вариант арифметического сжатия, называемый MQ-кодер.

Характеристики алгоритма JPEG 2000.

• Коэффициенты компрессии: 2…200 (задаётся пользователем), возможно сжатие без потерь.

• Класс изображений: полноцветные 24-битные изображения, изображения в градациях серого, 1-битные изображения (JPEG 2000 наиболее универсален).

• Характерные особенности: можно задавать качество участков изображений.

Motion-JPEG

Motion-JPEG (или М-JPEG) является наиболее простым алгоритмом сжатия видеоданных. В нем каждый кадр сжимается независимо алгоритмом JPEG. Этот прием дает высокую скорость доступа к произвольным кадрам как в прямом, так и в обратном порядке следования. Соответственно легко реализуются плавные "перемотки" в обоих направ

Последнее изменение этой страницы: 2016-06-09

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...