7.2.5. Aлгоритм сжатия LZW для GIF

Название алгоритм получил по первым буквам фамилий его разработчиков — Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется за счет одинаковых цепочек байт. LZW реализован в форматах GIF и TIFF. Является однопроходным, то есть при кодировании и декодировании изображения не требуется предварительного анализа информации.

Для осуществления процесса сжатия необходимо преобразовать исходный поток данных в поток кодов посредством таблицы строк, которая сама создаётся (иногда по нескольку раз для одного изображения) в процессе кодирования или декодирования. В случае, когда сжимаются байтовые данные, начальное состояние таблицы – 258 строк, содержащих последовательно возрастающие коды от 0 до 255, а также специальные 9-битовые коды 256 (код инициализации таблицы, или код очистки) и 257 (код конца информации). В процессе кодирования или декодирования создаются новые строки таблицы, содержащие цепочки кодируемых байтов или ссылки для организации таких цепочек. Максимальная длина таблицы – 4096 строк, т.е. максимальное число бит для записи кода –

12.

Алгоритм (псевдокод) для LZW-сжатия записан ниже. В нём S – строка (последовательность) кодируемых байтов, С – текущий кодируемый байт, N(S)

– номер строки таблицы, содержащей значение строки кодов S: S = первый символ из входного потока;

WHILE (входной поток не пуст)

{

C = очередной символ из входного потока IF (S+C есть в таблице строк) { S = S + C;} ELSE {

выходной поток = N ( S ); добавить в таблицу строк S+C; S = C;

}

}

выходной поток = S

На рисунке 82 приведен результат работы данного алгоритма на последовательности из 12 символов ABCABCABCABC:

150

Рисунок 77 – Результат работы алгоритма LZW-сжатия Особенность алгоритма сжатия такова, что во вновь появляющихся в таб-

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

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

Ниже представлен алгоритм дляLZW-декодирования24. Здесь OldCode, NewCode – коды, R(n) – значение (строка кодов) в строке таблицы с номером n, S – строка декодируемых байтов, С – байт.

OldCode = первый символ из входного потока;

24

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

151

WHILE (входной поток не пуст)

{

NewCode = очередной символ из входного потока; S = R(NewCode);

выходной поток = S;

C = первый символ S;

добавить в таблицу R(OldCode) + C; OldCode = NewCode;

}

На рисунке 78 показан результат алгоритма декодирования закодированного ранее потока данных.

выходной поток = OldCode;

Рисунок 78 – Результат алгоритма декодирования

7.2.6. Формат JPEG и алгоритм сжатия с потерями

Алгоритм JPEG разработан группой экспертов в области фотографии

(Joint Photographic Expert Group)25 специально для сжатия 24-битных изображе-

ний. Алгоритм основан на дискретном косинусоидальном преобразовании

25

Название алгоритма читается ['jei'peg].

152

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

Пусть сжимается 24-битное изображение (8 бит на одну цветовую компоненту). Последовательность действий может выглядеть следующим образом:

1.Изображение переводится из цветового пространстваRGB в цветовое пространство YCrCb.

В нем Y — яркостная составляющая, а Cr, Cb — компоненты, отвечающие за цвет(хроматический красный и хроматический синий). За счет того, что человеческий глаз менее чувствителен к переходам цвета, чем к переходам яркости, появляется возможность соответствующим образом уменьшать -ин формационную плотность отдельно для матриц Y, Cr и Cb.

2.Исходное изображение разбивается на фрагменты 8х8 (или 16х16) пикселей. Формируются из каждого фрагмента три рабочие матрицы соответственно для Y, Cb26 и Cr компонент. На этом этапе матрицы16х16 преобразуются в матрицы 8х8 с усреднением и прореживанием(interleaving), в результате которого уже на данном этапе можно провести сокращение выходного потока более чем в 2 раза.

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

	M k*,l = 1 ååC(i, k) ×C( j,l) × M i, j ,									где
				7		7
		4	i =0 j =0
						æ		(2i +1) ×p × k ö
	С(i, k) =			A(k) × cosç					÷,	(68)
								16
						è			ø
	ì			1			, для k	= 0
	ï
	A(k) = í			2
	ï			1,			для k ¹ 0
	î

k = 0...7, l = 0...7 .

26

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

153

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

4. Квантование – деление рабочей матрицы на матрицу квантованияQ с округлением элементов до ближайшего целого.

	æ		*	ö
M **	= Roundç	M k ,l		÷	(69)
k ,l	ç	Q	k ,l	÷
	è			ø

Для каждой компоненты (Y, Cb и Cr), в общем случае, задается своя матрица квантования Q. Способ задания матрицы Q стандартом лишь рекомендуется; например, он может быть таким:

Qi, j =1 + (1 + i + j) × q, i = 0...7, j = 0...7,

(70)

где q – коэффициент качества, от которого зависит потеря качества изображения (например, q = 2).

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

Рисунок 79 – Сканирование матрицы M **

154

5. Полученная матрица M ** переводится в 64-элементный вектор при помощи “зигзаг”-сканирования, как показано на рисунке 79. Таким образом, в начале вектора идут коэффициенты матрицы, соответствующие низким частотам, а в конце – высоким. На этом этапе возможна замена коэффициентов матрицы на относительные (как разница с элементами предыдущего блока), так как соседние блоки изображения в большинстве случаев похожи друг на друга.

6.К полученному вектору применяется RLE-сжатие в формате пары чисел: [счётчик нулей, ненулевое значение]. Так, вектор 42 3 0 0 0 -2 0 0 0 0 1 ...

будет свернут в пары (0,42) (0,3) (3,-2) (4,1) ... .

7.Получившиеся пары чисел сжимаются кодированием по Хаффману с фиксированной таблицей.

Процесс восстановления изображения в этом алгоритме полностью симметричен. Метод позволяет сжимать некоторые изображения 10в -15 раз без серьезных потерь.

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

Коэффициенты компрессии: 2–200 (Задается пользователем).

Класс изображений: Полноцветные 24 битные изображения или изображения в градациях серого без резких переходов цветов (фотографии).

Симметричность: =1.

Характерные особенности: В некоторых случаях, алгоритм создает “ореол” вокруг резких горизонтальных и вертикальных границ в изображении(эффект Гиббса). Кроме того, при высокой степени сжатия изображение распадается на блоки 8×8 пикселов. При повышении степени сжатия изображение распадается на отдельные квадраты (8×8). Это связано с тем, что происходят большие потери в низких частотах при квантовании, и восстановить исходные данные становится невозможно. Для деловой графики и полиграфии данный алгоритм не рекомендуется использовать, так как тонкие горизонтальные и вертикальные линии могут исчезнуть или исказиться. Вообще алгоритмы архивации с потерями не рекомендуется использовать при сжатии изображений, которые в дальнейшем собираются либо печатать с высоким качеством, либо обрабатывать программами распознавания образов.

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

155