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

Подождите немного. Документ загружается.

МУЛЬТИМЕДИАТЕХНОЛОГИИ

В ИНФОРМАЦИОННЫХ СИСТЕМАХ

МЕТОДЫ СЖАТИЯ И ФОРМАТЫ

ЗАПИСИ ГРАФИЧЕСКОЙ

ИНФОРМАЦИИ

Учебное пособие

Санкт-Петербург

2004

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

Н. Н. Красильников, О. И. Красильникова

Рекомендовано УМО по университетскому политехническому образованию

в качестве учебного пособия при подготовке инженеров по специальности

071900 "Информационные системы и технологии" направления подготовки

дипломированных специалистов 654700 "Информационные системы"

УДК 537.8

ББК 22.33

К45

Красильников Н. Н., Красильникова О. И.

К45 Мультимедиатехнологии в информационных системах. Методы

сжатия и форматы записи графической информации: Учеб. пособие/

СПбГУАП. СПб., 2004. 68 с.: ил. ISBN 5-8088-0104-4

В учебном пособии изложены вопросы, связанные с теоретическими

предпосылками сжатия графической информации; описаны наиболее рас-

пространенные и перспективные методы сжатия изображений, а также

проблема накопления ошибок, возникающая при многократной переза-

писи изображения с применением методов сжатия с потерями; приведе-

ны сведения о ряде форматов, предназначенных для графической записи

и видеоинформации.

Учебное пособие предназначено для студентов старших курсов, изу-

чающих мультимедиатехнологии в рамках технических специальностей.

Рецензенты:

кафедра видеотехники Санкт-Петербургского университета кино и телевидения;

доктор технических наук профессор В. И. Белицкий

Утверждено редакционно-издательским советом университета

в качестве учебного пособия

О. И. Красильникова, 2004

ISBN 5-8088-0104-4

1. ТЕОРЕТИЧЕСКИЕ ПРЕДПОСЫЛКИ СЖАТИЯ

ИЗОБРАЖЕНИЙ

1.1. Проблема сжатия изображений

Известно, что для записи изображений требуются достаточно боль-

шие объемы памяти, часто в единицы и даже десятки Мегабайт.

Так, например, отсканированное фотографическое цветное изобра-

жение размером 1732×1165 пикселов при 24 битах на пиксел (режим

True Color) требует 5,8 Мбайт. Такие ресурсы оказываются недостижи-

мыми, если изображение необходимо записать на дискету или передать

по Интернету. Однако наличие специально разработанных форматов

записи графических файлов, практически каждый из которых базиру-

ется на том или ином, а иногда и на нескольких алгоритмах сжатия

изображений, снимает остроту проблемы. Посредством сжатия (комп-

рессии) изображений удается в несколько раз и даже в ряде случаев в

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

Для вышеупомянутого изображения при записи его в формате TIFF тре-

буется приблизительно 4,9 Мбайт, а если использовать формат JPEG,

то можно получить разные степени сжатия в зависимости от жесткости

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

максимально высокого качества изображение будет занимать 2,4 Мбайт,

среднего (вполне приемлемого для большинства задач) качества –

0,2 Мбайт, а применение максимального сжатия позволит довести эту

цифру до 0,07 Мбайт.

Подчеркнем, что при записи изображений всегда остается важным

вопрос – сохранение качества. Как правило, проблема эффективного

сжатия изображений решается либо без потери качества, либо с мини-

мальными потерями, практически незаметными для зрителя. Это оказа-

лось возможным благодаря свойственным изображениям статистичес-

кой и психофизической избыточности, что позволяет произвести такое

кодирование изображения, при котором для его записи потребуется су-

щественно меньше двоичных единиц кода. Методы сжатия изображе-

ний, основанные на устранении избыточности обоих типов, будут рас-

смотрены в последующих подразделах.

Остановимся кратко на понятии «качество изображения», которое

можно рассматривать как меру подобия сформированного изображения

его входному оптическому. До настоящего времени не удалось сформу-

лировать полный критерий качества. Наиболее широко на практике

пользуются методом экспертных оценок, а также рядом измеряемых па-

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

тем различного назначения. Наиболее часто оцениваемыми являются

следующие параметры:

• четкость, определяемая числом элементов разложения изображения

по горизонтали и вертикали;

• воспроизведение градаций яркости внутри яркостного динамическо-

го диапазона;

• контраст, под которым понимают отношение максимальной яркости

изображения к минимальной;

• отношение сигнала к шуму, определяемое как отношение размаха

сигнала от черного до белого к эффективному значению шума;

• геометрические искажения, характеризующие точность воспроизве-

дения координат отдельных элементов исходного изображения;

• цветовоспроизведение, характеризующее степень отличия цветов в

полученном изображении от цветов в исходном изображении, а также

ряд других параметров.

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

нительных факторов. Например, если производится оценивание отно-

шения сигнала к шуму для системы, конечным звеном которой является

человек, то следует обращать внимание на степень видности помехи

для зрителя, которая зависит от ее спектрального состава. В этом слу-

чае делают оценку не отношения сигнала к шуму, а отношения сигнала

к взвешенному шуму. При этом под взвешенным шумом понимается

среднеквадратичное значение шума, предварительно пропущенного че-

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

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

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

имеются в виду шум пространственной дискретизации и шум кванто-

вания, параметры дискретизации (частоту взятия отсчетов и количе-

ство уровней квантования) следует выбирать, принимая во внимание

ряд важных факторов. Так, для предотвращения возникновения шума

пространственной дискретизации ее частота, то есть плотность отсче-

тов на изображении, в соответствии с теоремой Котельникова, должна,

по крайней мере, вдвое превышать верхнюю частоту пространственно-

го спектра дискретизируемого изображения, а во избежание появления

ложных контуров на изображении число уровней квантования должно

быть выбрано достаточно большим (стандартным требованием являет-

ся 256 уровней квантования), что потребует достаточно большого чис-

ла бит на каждый пиксел изображения. Этим как раз и обусловливается

то большое количество двоичных единиц, которым описывается изоб-

ражение, а следовательно, и необходимость его сжатия [1, 2].

1.2. Статистическая избыточность изображений

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

обусловлена наличием сильных статистических связей между его смеж-

ными пикселами, а также тем, что разные уровни их яркости имеют

неодинаковую вероятность. Применительно к последовательности кад-

ров, в случае видео, имеется дополнительный источник статистичес-

кой избыточности, который обусловлен наличием сильных статисти-

ческих связей между значениями яркости соответствующих пикселов в

смежных кадрах. На изображении это проявляется в том, что соседние

растровые элементы имеют одинаковые или близкие яркость и цвето-

вой тон. Резкие скачки этих параметров наблюдаются только при нали-

чии контуров в случае статических изображений или перемещающихся

объектов в последовательности кадров. Статистическая избыточность

сигнала, которым представлено изображение как неподвижное, так и

движущееся, может быть устранена или сильно уменьшена, а следова-

тельно, уменьшен цифровой поток путем его соответствующей переко-

дировки (сжатия). Эта перекодировка включает в себя два этапа: внача-

ле декорреляцию сигнала, а затем представление ч а с т о встречающихся

значений сигнала более короткими кодовыми комбинациями, а р е д к о

встречающихся значений – более длинными кодовыми комбинациями.

При этом не происходит потери информации, поскольку исходное изоб-

ражение может быть точно восстановлено. Вследствие этого методы, реа-

лизующие этот принцип сжатия изображений, называются методами

сжатия без потери информации, или энтропийными методами (от сло-

ва «энтропия» – одного из основных понятий теории информации).

Согласно Шеннону, энтропия является мерой, устанавливающей сред-

нее количество информации на символ сообщения (в данном случае на

растровый элемент изображения). Для последовательности из m стати-

стически независимых символов, появляющихся с вероятностями p

энтропия выражается в следующем виде:

log

Hpp

=−

∑

(1.1)

где

log

– двоичный логарифм; i – номер символа.

Если вероятность появления некоторого символа сообщения равна

единице, а остальных – нулю, то есть неопределенность появления дан-

ного символа отсутствует, энтропия будет равна нулю. Когда вероятно-

сти появления всех символов одинаковы

энтропия достигает своего максимального значения, равного

max

log

=−

∑

Сопоставляя найденное значение энтропии с ее максимальным зна-

чением, определяют величину избыточности сигнала следующим обра-

зом:

max

=−

(1.2)

В том случае, когда вероятности появления всех символов одинаковы

избыточность, как это ясно из изложенного, отсутствует.

Коэффициент, показывающий, во сколько раз можно уменьшить чис-

ло двоичных единиц кода, требующихся для представления сообщений

источника с энтропией H (в рассматриваемом случае изображения), по

сравнению со случаем, когда при том же наборе символов все символы

источника сообщения кодируются словами одинаковой длины, называ-

ется коэффициентом сжатия

max

сж

(1.3)

До сих пор мы рассматривали случай, когда смежные растровые эле-

менты изображения были статистически независимы, то есть в каче-

стве изображения был выбран белый шум. Однако в реальных изобра-

жениях значения яркостей смежных пикселов взаимно коррелированы.

В этом случае, располагая значением сигнала, представляющего яркость

пиксела, можно с некоротой вероятностью предсказать значения сигна-

лов от соседних пикселов. Следовательно, информация, привносимая

последующим пикселом в случае знания предшествующего, будет мень-

ше, чем в случае, когда сигналы, представляющие значения яркости пик-

селов, были бы статистически независимы. Тогда величина энтропии

H должна рассчитываться по другой формуле:

() () ()

log ,

Hpipjpj

=−

∑∑

(1.4)

где p

(j) – условная вероятность появления j-го символа, если предыду-

щим был i-й символ. Формула (1.4) является более общей, и в частном

случае, когда статистическая связь между пикселами отсутствует, она

переходит в формулу (1.1). Действительно, если p

(j) от i не зависит, то

можно его заменить на p(j) и записать:

() () ()

log ,

Hpipjpj

=−

∑∑

а так как внутренняя сумма не зависит от i, то суммы можно поменять

местами:

() () ()

log .

Hpjpjpi

=−

∑∑

(5)

Поскольку

()

pi=

∑

так как суммируются все вероятности p(i),

формула (1.4) переходит в формулу (1.1), что и требовалось показать.

В рассматриваемом примере, когда элементы изображения взаимно

коррелированы, энтропия H будет меньше, чем в случае, если бы значе-

ния сигнала были бы статистически независимы. Вследствие этого дос-

тижимый коэффициент сжатия возрастает. Поэтому первым шагом при

сжатии данных обычно является декорреляция кодируемой последова-

тельности, при которой устраняются статистические связи между коди-

руемыми отсчетами, и уже затем производится энтропийное кодирова-

ние статистически независимых отсчетов.

1.3. Психофизическая избыточность изображений

Психофизическая избыточность изображений обусловлена особен-

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

зволяет реализовать сжатие данных при передаче или записи изобра-

жений. Дело в том, что не все детали изображения одинаково

воспринимаются зрителем. Например, детали, имеющие одновременно

и малые размеры, и малый контраст, вследствие ограничений со сто-

роны контрастной чувствительности зрения не видны зрителю на

изображении, а поэтому без всякого ущерба для качества его воспро-

изведения могут не передаваться. Благодаря этому цифровой поток,

которым передается изображение, может быть сокращен. Этот вид

избыточности называется психофизической избыточностью изобра-

жений.

Проиллюстрируем сказанное на примере кодирования изображения

звездного неба. Известно, что пороговый контраст зрения в сильной

степени зависит от угловых размеров наблюдаемых объектов. Так, на-

пример, если при наблюдении объектов, имеющих большой угловой

размер, пороговый контраст составляет около 0,02, то при наблюдении

точечных объектов, в нашем примере звезд, он составляет не более 0,1.

Поэтому, передавая изображение пиксел за пикселом, как обычно, мож-

но квантовать яркость звезд всего на 16 уровней, расходуя на представ-

ление яркости каждой из них по четыре двоичных единицы, а не по

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

кода на представление яркости звезд, имеет место сокращение кодовой

последовательности и, следовательно, сжатие данных (изображения),

которое в данном случае составляет два раза.

Описанный метод кодирования относится к группе методов сжатия

данных с потерями информации. Смысл этого термина заключается в

том, что после декодирования распределение яркости в восстановлен-

ном изображении отличается от того, которое было до его кодирования,

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

информации. Следует иметь в виду, что речь здесь идет о потере ин-

формации, которой зрительная система не в состоянии воспользовать-

ся в силу присущих ей ограничений.

На практике при сжатии изображений применяются как методы сжатия

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

щении не только психофизической избыточности, но и статистичес-

кой), так и методы сжатия данных без потерь информации.

W(L)

2. СЖАТИЕ ИЗОБРАЖЕНИЙ БЕЗ ПОТЕРИ ИНФОРМАЦИИ

2.1. Декорреляция сигнала изображения

Выше было отмечено, что избыточность изображения обусловлена

наличием сильных корреляционных связей между значениями яркости

смежных пикселов. Кроме того, избыточность обусловлена также тем,

что неравномерность распределения плотности вероятности их значе-

ний мала. Другими словами, различие в вероятности появления тех или

иных уровней яркости невелико. На рис. 1 приведена плотность вероят-

ности значений яркости в исходном изображении W(L).

Рис. 1

В связи с этим первым шагом при сжатии изображений с использо-

ванием энтропийного кодирования является декорреляция кодируемой

последовательности, при которой устраняются статистические связи

между кодируемыми отсчетами, а затем производится кодирование ста-

тистически независимых отсчетов. Простейшим, но не оптимальным

способом декорреляции является преобразование последовательности

отсчетов кодируемого сигнала, представляющего яркость пикселов изоб-

ражения L(n) в последовательность отсчетов приращений этой яркости

()

∆

при переходе с одного пиксела на другой, то есть

() ( ) ()

Ln Ln Ln

∆=+−

где n – номер отсчета. В результате такого преобразования статистичес-

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