Методическое пособие Теория информации-2

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

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

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

друга цветов. Поэтому здесь особенно важно, сколько оттенков способен

различить человеческий глаз: если «цветовое разрешение» формата превышает

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

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

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

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

использует значения длиной в 1 разряд). Чтобы вычислить количество цветов,

нужно возвести число 2 в степень, показатель которой равен количеству

отведенных на каждую составляющую цвета бит. Так, если на один пиксель
отводится	от 1 до 8 бит, следовательно, можно отображать от 2 = 2 до
2; = 256	цветов. Качество, при котором невозможно отличить компьютерную

фотографию от настоящей, достигается только при не менее, чем трех байтах на пиксель, что дает 2>8, или около 16 млн цветов.

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

области, но для удобства исследований в работе все изображения определяются
в квадратных областях, т.е. ¦0; º§, а · ¦0; §, где	º	– ширина
изображения, а – высота изображения и º = .

Все изображения можно подразделить на две группы: с палитрой и без нее. У изображений с палитрой в пикселе (одном из отчетов изображения – значение функции œ , · для конкретного и · ) храниться число – индекс в некотором одномерном векторе цветов, называемом палитрой. Палитры обычно бывают 8, 16 и 256 цветов.

Изображения без палитры обычно бывают в определенной системе цветопредставления или в градациях серого. В градациях серого значения

221

каждого из пикселей определяется как яркость точки. Наиболее часто встречаются изображения с 2, 16 и 256 уровнями серого.

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

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

Наиболее распространенной системой цветопредставления, используемой в электронных и компьютерных системах, является система RGB. В этой системе цвет определяется как комбинация красного, зелёного и синего цвета. И на каждую из составляющих приходиться по одному байту. Существуют и другие системы цветопредставления, такие как CMYK, CIE, YUU и YCrCb.

В цветовой модели CMYK используется четыре цвета. Первые три названы по первой букве цвета и составляют CMY – Cyan [ голубой], Magenta [пурпурный], Yellow [желтый]. В качестве четвертого цвета используется черный [black]. Современный экран может произвести практически любой цвет.

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

выводимых на печать. Каждое из чисел CMYK представляет из себя процент

(%) краски данного цвета. Например, для получения цвета «хаки» следует смешать 30% голубой краски, 45% пурпурной краски, 80% желтой краски и 5%

черной. Это можно обозначить следующим образом: (30,45,80,5). Иногда пользуются таким обозначением: C30 M45 Y80 K5. Важно понимать, что цифровое значение не описывает реальный цвет. Оно лишь означает набор аппаратных данных, которые будут использованы для изготовления цвета. На практике все будет зависеть от характеристик и качества бумаги, состояния печатной машины, условиями просмотра отпечатка и даже влажности в помещении.

Для улучшения преобразования изображения из RGB в CMYK в 1976 г.

была принята система CIE Lab в качестве единого международного стандарта.

Из цветового пространства сканера информация трансформируется не сразу в

CMYK, а в промежуточное цветовое пространство CIE Lab, которое включает

222

все теоретически возможные оттенки. Система автоматически рассчитывает убавление цветов, противоположных добавляемым. Длина волны для каждого из основных цветов (красного, синего и зеленого) строго определена. Модель

CIE Lab содержит три основных составляющих: L* – светлоту, а* – красный и зеленый цвет, а также b* – синий и желтый цвет (красный и зеленый, синий и желтый являются противоположными, или взаимоисключающими цветами). По определению модель CIE Lab представляет все видимые человеком цвета. Она исходно разработана по принципу равномерного восприятия цвета. Это означает, что при изменении любых основных цветов на одну и ту же величину зрительное их восприятие изменяется в той же степени. На самом деле эта модель несовершенна, и все-таки она наиболее достоверна.

Условно можно выделить следующие классы изображений:

• Изображения с небольшим количеством цветов и большими областями,

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

техническая, инженерная или плакатная графика.

•Изображения с плавными переходами цветов, построенные на компьютере: графика презентаций и виртуальные модели;

•Фотореалистичные изображения, полученные после цифровой фотосъемки, сканирования, а также постобработка этих изображений.

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

7.1.2. Классификация методов сжатия цифровых изображений

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

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

223

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

таким алгоритмам относят RLE-кодирование, код Хаффмана, дельта-

кодирование, LZW. Если декодированное изображение отличается от кодированного, то подобный алгоритм называют алгоритмом сжатия с потерями. К таким алгоритмам относятся алгоритмы CS&Q, JPEG, MPEG.

Рассмотрим этапы процедуры сжатия данных в общем виде. Любой метод сжатия реализует три основных этапа:1 – кодирование или первичное сжатие; 2 – вторичное сжатие; 3 – декодирование или восстановление изображения.

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

(сжатие с распознаванием).

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

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

7.1.3. Ключевые характеристики алгоритмов сжатия цифровых

изображений

Ключевыми характеристиками являются коэффициент сжатия, оценка

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

224

Коэффициент сжатия сж определяет во сколько раз файл, хранящий
сжатое изображение » , меньше файла, хранящего исходное изображение »>.
		= »>
сж				(7.1)
Величины » и »> выражаются в байтах. сж – величина безразмерная.
Существует большое	число		показателей для оценки	качества

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

	наиболее широкое распространение –		среднеквадратичное		отклонение	и
	критерий соотношения сигнал/шум.	“ , ·			“ , ·
	Пусть есть два изображения:			- оригинал,		-
			l × T,		и ¼
	восстановленное изображение размером			тогда среднеквадратичное

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

n , · = ½	∑ ∑ÁÀ¾“ , · − “¼ , · ¿>	(7.2)
	l T

Стоит отметить, что в соответствии с данным критерием декодированное изображение будет признано «плохим» при изменении, например, его яркости всего на 5 %. А в случае появления резкого изменения отдельных точек на изображении – « битых» пикселей, такие изображения будут признаны почти не изменившимися.

Критерий соотношения сигнал/шум (PSNR, signal-to-noise ratio) можно выразить уравнением:

n , · = 10 log *	∑		∑	Á	¼	>	(7.3)
		Â		À	¾“ , · − “ , · ¿

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

Лучше всего потери в качестве оценивает человеческий глаз. Сжатие изображение можно считать отличной, если на глаз невозможно отличить

225

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

При оценке времени преобразования цифрового изображения различают две величины: время сжатия Ãсж и время восстановления Ãвос. Время сжатия в свою очередь состоит из времени, затрачиваемого на основное преобразование,

à и времени упаковки à . Время восстановления включает в себя время

оп Ã уп Ã

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

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

следующих критериев:

∙разброс коэффициентов сжатия при работе с хорошим (алгоритм подходит для обработки данного класса изображений),

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

∙отношение времени кодирования ко времени декодирования цифрового изображения данного класса;

∙потери качества.

7.1.4. Алгоритмы сжатия изображений без потерь

Кодирование серий последовательностей

Наиболее известный и простой алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding – RLE). Суть данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. На рис. 7.1а проиллюстрирован принцип этого кодирования для последовательности данных с частым повторением серии нулей. Всякий раз, когда нуль встречается во входных данных, в выходной файл записываются два значения: нуль, указывающий на начало кодирования, и

число нулей в серии. Если среднее значение длины серии больше двух,

происходит сжатие. С другой стороны, множество одиночных нулей в данных

226

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

(рис. 7.1б).
23 4 67 0 3 54 2 0 4	а5	0 1 21 45 38 …
56 1 0 1 9 23 4 0б		1 8 0 1 3 21 …

Рис. 7.1. Пример работы алгоритма RLE:

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

последовательность больше исходной

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

кодированную серию от других – некодированных последовательностей

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

Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIFF), т.к. последние содержат достаточно длинных серий повторяющихся последовательностей байтов. Лучший, средний и худший коэффициенты сжатия -1/32, 1/2, 2/1.

Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже – с

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

227

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

Сжатие изображений по методу Хафмана

Алгоритм сжатия по методу Хафмана подробно был рассмотрен в главе 6,

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

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

встречающимся редко - код большей длины (т.е. формируется префиксный код переменной длины).

Применение данного алгоритма требует два прохода по файлу – один для просмотра и сбора статистической информации, второй – для кодирования.

Коэффициенты сжатия: 1/8, 2/3, 1.

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

Основным недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к величине 2Bм, поскольку каждый символ кодируется целым числом бит. Так, при кодировании данных с двухсимвольным алфавитом сжатие всегда отсутствует, т.к. несмотря на различные вероятности появления символов во входном потоке алгоритм фактически сводит их до 1/2. Такой алгоритм реализован в формате TIFF.

Алгоритм Лемпеля-Зива (LZ-compression)

Алгоритм Лемпеля-Зива относится к словарным алгоритмам. Существует целая группа LZ-алгоритмов. Далее будет рассмотрен алгоритм LZ77. В

228

алгоритме LZ77 в качестве словаря выступают T последних обработанных символов. Каждая кодовая комбинация состоит из трех компонентов (кодовая триада). Первые два компонента указывают на строку словаря4, идентичную начальной части кодируемой символьной последовательности: один из этих компонентов является смещением строки в словаре (смещение определяется относительно текущей обрабатываемой позиции), а второй – длиной этой строки. Третий компонент представляет собой первый символ кодируемой последовательности, не принадлежащий строке, описываемой первыми двумя компонентами (символ записывается в кодовой триаде в своем исходном представлении). Длина совпадения ограничивается сверху некоторым числом l. В процессе работы алгоритма на каждом шаге в словаре осуществляется поиск строки, имеющей наибольшее совпадение с кодируемой символьной последовательностью. В случае, когда совпадение в словаре отсутствует,

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

Декодирование кода, полученного с применением алгоритма LZ77,

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

являющийся третьим компонентом кодовой триады. Благодаря простоте декодера алгоритм LZ77 и его производные обладают очень высокой скоростью декодирования. Процесс кодирования является существенно более медленным,

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

Рассматриваемый алгоритм относится к адаптивным алгоритмам. Способ кодирования того или иного сообщения (в данном случае в качестве сообщения выступает строка символов) непосредственно зависит от содержимого словаря,

которое меняется в процессе работы.

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

229

Ограничения, накладываемые на размер словаря и длину совпадения,

породили понятие скользящее окно (sliding window). Скользящее окно состоит из двух частей – задней, именуемой буфером поиска (search buffer),и передней,

называемой буфером просмотра (look-ahead buffer). Кодируемая строка всегда находится внутри буфера просмотра, а идентичная ее части строка словаря имеет свое начало в пределах буфера поиска. Буфер поиска и буфер просмотра имеют длины T и l соответственно, причем, как правило, T значительно превосходит l. В процессе работы алгоритма осуществляется последовательное перемещение (скольжение) окна по обрабатываемой информации. При этом каждая обработанная строка или символ переходят из передней части скользящего окна в его заднюю часть, а в переднюю часть добавляется очередная порция информации, равная по длине обработанному информационному блоку. В связи с ограничением, накладываемым на размер буфера поиска, при добавлении в него очередной строки из буфера, начиная с конца, удаляется строка, по длине идентичная удаленной строке.

Составляющие удаленной строки более не являются частью словаря.

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

символов: 169166168171169168175170167166165170170170170170167168171 168168170171170167168169166. Пусть ширина скользящего окна составляет 24

символов, из них 15 символов составляет буфер поиска и 9 символов – буфер просмотра. В таблице 7.1 представлен результат работы данного алгоритма, при условии уже заполненного буфера поиска (пропущен начальный этап заполнения скользящего окна).

Таким образом, часть строки, в которую вошло 64 символа по 3 бита каждый, закодируется последовательностью, из 17 × 3 = 51 символов по 3

бита каждый.

На рассмотренном выше примере видны отдельные недостатки алгоритма

LZ77. Во-первых, длина кодовой триады, кодирующей только один символ,

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

230