3.1. Введение

Современные компьютеры весьма интенсивно применяют графику. Операционные системы с интерфейсом оконного типа используют картинки, например, для отображения директорий или папок. Некоторые совершаемые системой действия, например загрузку и пересылку файлов, также отображаются графически. Многие программы и приложения предлагают пользователю графический интерфейс (GUI), который значительно упрощает работу пользователя и позволяет легко интерпретировать полученные результаты. Компьютерная графика используется во многих областях повседневной деятельности при переводе сложных массивов данных в графическое представление. Итак, графические изображения крайне важны, но они требуют так много места! Поскольку современные дисплеи передают множество цветов, каждый пиксел принято интерпретировать в виде 24-битового числа, в котором компоненты красного, зеленого и голубого цветов занимают по 8 бит каждый. Такой 24-битовый пиксел может отображать  миллионов цветов. Тогда изображение с разрешением 512х512 пикселов будет занимать 786432 байта. А изображению размером 1024х1024 пиксела потребуется 3145728 байт для его хранения. Мультфильмы и анимация, которые также весьма популярны в компьютерных приложениях, потребуют еще большего объема. Все это объясняет важность сжатия изображений. К счастью, изображения допускают частичную потерю информации при сжатии. В конце концов, изображения призваны для того, чтобы люди на них смотрели, поэтому та часть изображения, которая не воспринимается глазом, может быть опущена. Эта основная идея вот уже три десятилетия движет разработчиками методов сжатия, допускающих некоторую потерю данных.

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

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

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

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

Приведем простой тест на качественное определение потери информации при сжатии изображения. Пусть данный образ A (1) сжат в В, (2) разжат в С, и (3) их разница обозначена D=С-А. Если А был сжат без потери информации и разжат подобающим образом, то С должен быть идентичен А, и образ D должен быть равномерно белым. Чем больше информации потеряно, тем дальше будет D от равномерно белого образа.

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

1. Текст одномерен, а изображение имеет размерность 2. Весь текст можно рассматривать как одну длинную строку символов. Каждая буква текста имеет двух соседей, слева и справа. Все соседи весьма слабо коррелированы между собой. Например, в этом абзаце букве «и» предшествуют буквы «н», «р», «л», «с», «п», а за ней следуют буквы «е», «в», «н», «м», «р». В других абзацах та же буква «и» может иметь других соседей. В изображении пиксел имеет четырех непосредственных соседей и восемь ближайших (за исключением пикселов, лежащих на границе, см. рис. 3.1, где восемь ближайших соседей пиксела «*» показаны черным цветом), и между ними существует сильная корреляция.

Рис. 3.1. Четыре ближайших и восемь соседних пикселов.

2. Текст состоит из относительно небольшого числа символов алфавита. Обычно, это 128 кодов ASCII или 256 байтов длины по 8 бит каждый. Наоборот, каждый пиксел изображения представим 24 битами, поэтому может быть до  миллионов различных пикселов. Значит, число элементарных «символов» в изображении может быть огромным.

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

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

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

Итак, сжатие изображений основывается на сильной корреляции соседних пикселов. Эта корреляция также называется пространственной избыточностью.

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

12, 17, 14, 19, 21, 26, 23, 29, 41, 38, 31, 44, 46, 57, 53, 50, 60, 58, 55, 54, 52, 51, 56, 60.

Здесь только два пиксела совпадают. Их среднее значение равно 40.3. Вычитание каждого предыдущего символа даст последовательность

12, 5, -3, 5, 2, 5, -3, 6, 12, -3, -7, 13, 2, 11, -4, -3, 10, -2, -3, -1, -2, -1, 5, 4.

Эти последовательности пикселов проиллюстрированы графически на рис. 3.2, который показывает потенциал сжатия: (1) разность пикселов существенно меньше их абсолютных величин. Их среднее равно 2.58. (2) Они повторяются. Имеется только 15 различных значений. В принципе, каждый из них можно закодировать 4 битами. Они декоррелированы, то есть, разности соседних значений, в среднем, не уменьшаются. Это видно из последовательности вторых разностей:

12, -7, -8, 8, -3, 3, -8, 9, 6, -15, -4, 20, -11, 9, -15, -1, 13, -12, -1, 2, -1, -1, 6, 1.

Эти разности уже больше исходных величин.

Рис. 3.2. Величины и разности 24 соседних пикселов.

Рис. 3.3 предлагает другую иллюстрацию «коррелированных величин». Матрица А размером 32x32 заполнена случайными числами, и ее значения на рисунке (а) изображены квадратиками различных серых оттенков. Случайная природа этих элементов очевидна. Затем эту матрицу обратили и результат - матрицу В - изобразили на рисунке (b). На этот раз этот массив квадратиков 32х32 выглядит на глаз более структурированным. Прямое вычисление корреляции с помощью коэффициента Пирсона по формуле (3.1) показывает, что перекрестная корреляция верхних двух строк матрицы А является относительно малым числом 0.0412, в то время, как соответствующая величины, вычисленная для верхних строк матрицы В равна относительно большому числу -0.9831. Дело в том, что каждый элемент матрицы В зависит от всех элементов матрицы А

.                  (3.1)

Рис. 3.3. Случайная матрица (а) и ее обратная матрица (b).

n=32; a=rand(n); imagesc(a); colormap(gray)

b=inv(a); imagesc(b)

Программа на Matlab для рис. 3.3.

Пример: Воспользуемся специальной программой для иллюстрации ковариационной матрицы для (1) матрицы с коррелированными элементами и (2) матрицы с декоррелированными элементами. На рис. 3.4 показаны две 32х32 матрицы. Первая из них а является случайной (то есть, декоррелированной), а вторая матрица b является обратной для матрицы а (значит, она коррелирована). Их ковариационные матрицы также показаны. Очевидно, что матрица cov(a) близка к диагональной (недиагональные элементы равны нулю или близки к нулю), а матрица cov(b) далека от диагональной. Далее приведена программа для системы Matlab, которая рисует эти картинки.

Рис. 3.4. Ковариация коррелированной и декоррелированной матриц.

Если понятие коррелированных величин стало более ясным, то можно легко ответить на вопрос: «Как проверить стали ли пикселы изображения после некоторого преобразования декоррелированными или нет?» Ответ будет таким: «Если матрица содержит декоррелированные значения, то ковариация любой ее строки с любым столбцом равна нулю». В результате ковариационная матрица М будет диагональной. Статистическое понятия дисперсии, ковариации и корреляции обсуждаются в любом учебнике по статистике.

Принцип сжатия изображений имеет и другую сторону. Нам хорошо известно но опыту, что яркость близких пикселов тоже коррелирована. Два смежных пиксела могут иметь разные цвета. Один может быть близок к красному, а второй к зеленому, однако, если первый был ярким, то его сосед, обычно, тоже будет ярким. Это свойство можно использовать для перевода представления пикселов RGB (red, green, blue) в виде трех других компонентов: яркости и двух хроматических компонентов, определяющих цвет. Одним таким форматом (или пространством цветов) служит YCbCr, где Y (компонента «светимости») отвечает за яркость пиксела, а Сb и Сr определяют его цвет. Этот формат будет обсуждаться в § 3.7.1, но его преимущество уже легко понять. Наш глаз чувствителен к маленьким изменениям яркости, но не цвета. Поэтому потеря информации в компонентах Сb и Сr сжимает образ, внося искажения, которые глаз не замечает. А искажение информации о компоненте Y, наоборот, является более приметной.

a=rand(32); b=inv(a);

figure(l); imagesc(a); colormap(gray); axis square

figure(2); imagesc(b); colormap(gray); axis square

figure(3); imagesc(cov(a)); colormap(gray); axis square

figure(4); imagesc(cov(b)); colormap(gray); axis square

Программа на Matlab для рис. 3.4.