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

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

() ( ) ( )

сс

2212.

kLkLk

=−+





В этих формулах значения, заключенные в скобки, представляют со-

бой номера отсчетов. Возврат от последовательностей

()

последовательностям

()

2Lk

()

Lk+

осуществляется следующим

образом:

( ) () ()

2,Lkvkvk

( ) () ()

21 .

Lk vkvk

+= −

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

вергается строка, состоящая из восьми пикселов, яркости которых рав-

ны: (120, 111, 112, 118, 117, 114, 110, 102). Следуя приведенному выше

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

вательности отсчетов

()

равные соответственно (115, 5,

115, 115,5, 106) и (4,5, – 3, 1,5, 4). Характерной особенностью второй

группы отсчетов

()

является то, что их значения близки к нулю.

Кроме того, поскольку вторая группа отсчетов содержит информацию

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

странственных частот, в то время как спектр первой группы отсчетов –

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

те вейвлет-преобразования произошло разделение сигнала по спектру

частот. Рассмотренная операция может быть рекурсивно повторена по

отношению к

()

,vk

в результате чего исходная последовательность,

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

тельностями: (115,25, 110,75), (0,25, 4,75), (115,5, 115, 115,5, 106). Обычно

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

ных они рекурсивно повторяются несколько раз.

Аналогичным образом может быть реализован алгоритм при вейв-

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

случае изображение разбивается на группы размером 2×2 пиксела. Обо-

значая значения яркостей пикселов в группе:

()

2,2 ,Lkn

()

21,2,Lk n

()

2,2 1,

Lkn+

()

21,21,

Lk n++

где k – номер

строки; n – номер столбца, будем иметь после преобразования для каж-

дой группы по четыре компонента:

()

()( )

2,2 2 1,2

,4,

2,21 21,21

LknLk n

Lkn Lk n

+++





+++++





()

()( )

сс

2,2 2 1,2

,4,

2,2 1 2 1,2 1

LknLk n

Lkn Lk n

++−





−+−++





()

()( )

сс

2,2 2 1,2

,4,

2,2 1 2 1,2 1

LknLk n

Lkn Lk n

−++





++−++





()

()( )

сс

2,2 2 1,2

,4.

2,2 1 2 1,2 1

LknLk n

Lkn Lk n

−+−





−++++





Эти компоненты объединяются в четыре матрицы и обычно разме-

щаются рядом на одной плоскости (как это показано на рис. 12, б).

Обратим внимание на то, что суммарное количество отсчетов, которы-

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

честву отсчетов в исходном изображении, то есть размер исходного изоб-

ражения (как это видно на рис. 12, а), и суммарный размер изображений,

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

няется это тем, что при вычислении компонентов

()

vkn

()

vkn

()

,,vkn

()

,vkn

имеют место две последовательные операции: пер-

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

стотных диапазона, а вторая – в прореживании (децимации) результа-

тов расфильтровки, при котором в окончательных матрицах сохраняется

Рис. 12

а) б)

()

,vkn

()

,vkn

()

,vkn

()

,vkn

→

()

,Lkn

каждый второй отсчет по строке и каждый второй отсчет по столбцу.

На рис. 13, а приведено изображение, представленное массивом

()

,,Lkn

а на рис. 13, б – четыре изображения, соответствующие мас-

сивам

()

vkn

– верхнее левое,

()

vkn

– верхнее правое,

()

vkn

–

нижнее левое и

()

,vkn

– нижнее правое. На рис. 13 хорошо видно,

что массив

()

,vkn

представляет собой уменьшенную копию исходно-

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

шением. Эта компонента разложения носит название а ппроксима-

ц и и . Компоненты

()

vkn

()

vkn

()

vkn

содержат резкие

границы, ориентированные вертикально, горизонтально и соответствен-

но по диагонали. Добавление к аппроксимации компонентов, содержа-

щих границы, восстанавливает исходное разрешение изображения. На

рис. 12, б показана ориентация контуров, передаваемых компонентами

()

,vkn

()

,vkn

()

,vkn

Как уже было отмечено, при формировании вейвлет-компонентов

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

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

ваемых примерах расфильтровка осуществляется путем свертки исход-

ного изображения с импульсными функциями

()

в два

приема: сначала – вдоль строк, а затем – вдоль столбцов. При этом для

свертки используются известные формулы:

Рис. 13

а) б)

()

()()

1''

,,,

kn L kn h n n

−

=−

∑

()

()()

2''

,,,

kn L kn h n n

−

=−

∑

где N – протяженность импульсной функции. Восстановление исходно-

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

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

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

все компоненты суммируются.

В рассмотренных выше примерах был использован простейший слу-

чай – вейвлеты Хаара, при этом

()

11;

−=

()

01;

()

11;

()

11;

−=

()

01;

()

=−

. Однако в настоящее время в алго-

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

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

леты, в частности, в архиваторе JPEG 2000 –

()

значения

которых приведены в табл. 2.

3.6. Сжатие изображений на основе вейвлет-преобразования

Обратимся теперь к рассмотрению метода сжатия данных на основе

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

Таблица 2

k h

(k) h

(k)

0 1,115087052456994 0,6029490182363579

±1 0,5912717631142470 – 0,2668641184428723

±2 – 0,05754352622849957 – 0,07822326652898785

±3 – 0,09127176311424948 0,01686411844287495

±4 0 0,02674875741080976

±5 0 0

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

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

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

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

четыре матрицы отсчетов (коэффициентов), второй раз оно применяет-

ся к аппроксимации, то есть к матрице, представляющей размытую вер-

сию исходного изображения (аппроксимацию), и наконец, третий раз –

к полученной на втором этапе аппроксимации. Если вейвлет-преобра-

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

ществляется децимация полученной матрицы. На рис. 14, а приведен

результат трехкратного вейвлет-преобразования изображения, а на рис.

14, б – поясняющая диаграмма. Полученные компоненты квантуются

(высокочастотные – на меньшее число уровней, низкочастотные – на

большее).

Этот метод в значительной степени похож на метод сжатия данных,

используемый в JPEG, и отличается от него лишь тем, что в JPEG кван-

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

коэффициенты), полученные в результате ДКП, в то время как в рас-

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

ненты, полученные в результате вейвлет-преобразований. И в том, и в

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

ся в том, что оно мало чувствительно к шуму квантования высокочас-

Рис. 14

а) б)

()

vkn

()

vkn

()

vkn

()

vkn

→

()

vkn

()

vkn

()

vkn

()

vkn

()

vkn

()

vkn

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

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

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

нии отсутствуют такие неприятные артефакты (искажения), как замет-

ность блочной структуры. Поскольку высокочастотные компоненты

квантуются на малое число уровней, а их большинство (как это видно

на рис. 14), на их сохранение расходуется мало двоичных единиц кода,

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

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

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

уровней в них вносится шум квантования, то есть имеет место потеря

информации, но если сжатие не слишком велико, то есть число исполь-

зуемых уровней квантования не слишком занижено, то эти шумы на

восстановленном изображении будут незаметны. Квантование отсче-

тов компонентов осуществляется путем деления матрицы отсчетов на

матрицу квантования. Затем проквантованные отсчеты подвергаются

энтропийному кодированию, аналогично тому, как это делается в JPEG.

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

сжатие, которое составляет около трех раз.

Результирующее сжатие данных, которое получается при использо-

вании данного метода, достигает 30–50 раз.

В заключение отметим, что при большом сжатии данных этот метод

также приводит к появлению артефактов на восстановленных изобра-

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

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

гих методов сжатия данных.

3.7. Фрактальное кодирование

Фрактальный метод сжатия изображений относится к группе мето-

дов сжатия с потерей информации. Другими словами, в случае приме-

нения фрактального метода восстановленное (декомпрессированное)

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

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

этого метода положили исследования Майкла Барнсли, который открыл

класс теорем, позволивших эффективно сжимать изображения. При ис-

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

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

на замечательной особенности реальных изображений, заключающейся

в том, что в них с небольшими вариациями многократно повторяются

отдельные самоподобные фрагменты, например листья в кроне дерева,

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

темным и светлым (как это показано на рис. 15). Хотя эти фрагменты

различаются между собой в деталях, тем не менее в них много общего.

Не претендуя на детальность изложения, опишем алгоритм сжатия при

фрактальном сжатии изображений.

Процесс сжатия начинается с того, что берутся два идентичных эк-

земпляра кодируемого изображения А и Б. Один из них разделяется на

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

ром задается набор доменов, которые могут взаимно перекрываться (как

это показано на рис. 16). Домены должны включать в себя характерные

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

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

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

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

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

мене. Для того чтобы получить наилучшую аппроксимацию, домены

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

ходит не только их геометрическая деформация, но и изменения контра-

Рис. 15

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

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

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

делится на четыре части, и процесс повторяется. Качество требуемой

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

та ошибки аппроксимации (среднего квадрата несовпадения). Номера

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

а также коэффициенты афинного преобразования сжимаются путем эн-

тропийного кодирования и записываются в файл. Файл сжатого изобра-

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

областей и доменов, а также таблицу эффективно упакованных афин-

ных коэффициентов для каждой ранговой области.

Алгоритм декодирования изображений не столь нагляден. Он заклю-

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

А и Б, распределение яркости в которых безразлично. На них выделяют-

ся области, границы которых совпадают с границами ранговых облас-

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

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

распределения яркости в ранговых областях изображения A. После это-

го изображения А и Б меняются местами, и операция повторяется. Можно

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

Рис. 16

А Б

Домены

Ранговые области

ление яркости в изображениях А и Б будет приближаться к распределе-

нию яркости в исходном изображении.

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

метричны. Следует также отметить, что процесс сжатия требует боль-

ше времени, чем процесс декомпрессии.

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

эффициенты сжатия, составляющие от 50 до 500 раз в зависимости от

типа изображения и допустимого уровня шума преобразования. В на-

стоящее время этот метод применяется на практике, а графические фай-

лы, при создании которых он был использован, легко узнать по расши-

рению (.fif).

4. АЛГОРИТМЫ СЖАТИЯ ИЗОБРАЖЕНИЙ В ФОРМАТАХ

ЗАПИСИ НЕПОДВИЖНЫХ И ДВИЖУЩИХСЯ

ИЗОБРАЖЕНИЙ

4.1. Обзор форматов записи изображений

В настоящее время имеется большое разнообразие форматов записи

графических изображений. Одни из них предназначены для записи изоб-

ражений в растровом представлении, другие – в векторном. Растровое

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

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

чением яркости или цвета. Так как задается вся область графического

изображения, то такие изображения имеют фон. Что касается изобра-

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

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

чек и набора инструкций относительно того, например, где и какой

толщины должна быть проведена линия. Поскольку в данном пособии

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

ний, то остановимся на рассмотрении форматов записи, предназначен-

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

щихся областей использования эффективно сжатых изображений – это

крупнейшее информационное хранилище – World Wide Web, которое

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

Многочисленные используемые форматы записи растровых изобра-

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

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

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

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

в практической деятельности. К таким особенностям относятся: дос-

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

можность хранения нескольких изображений в одном файле и т. д. Само

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

графических файлов.