Пояснительная записка (1191409), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Алгоритм JPEG

В 1991 году группой экспертов в области фотографии (Joint Photographic Expert Group) был разработан специально для сжатия 24-битных и полутоновых изображений алгоритм JPEG.

JPEG – достаточно мощный алгоритм. Практически он является стандартом де-факто для полноцветных изображений.

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

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

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

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

Рассмотрим пошагово алгоритм JPEG [2]. Будем сжимать 24-битное изображение.

Шаг 1. Учитывая особенности восприятия информации человеческим глазом, переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную (Red), зеленую (Green) и синюю (Blue) составляющие цвета точки, в цветовое пространство YCrCb (иногда называют YUV). В нем Y – яркостная составляющая, а Cr, Cb – компоненты, отвечающие за цвет (хроматический красный и хроматический синий). За счет того, что человеческий глаз менее чувствителен к цвету, чем к яркости, появляется возможность архивировать массивы для Cr и Cb компонент с большими потерями и, соответственно, большими степенями сжатия.

Математически перевод из цветового пространства RGB в цветовое пространство YCrCb представляет собой аффинное преобразование одного пространства в другое.

Формальное описание такого перехода можно приближенно (приближение за счет точности коэффициентов матрицы) описать формулой (1.1):

(1.1)

Обратное преобразование для (1.1) существует (за счет невырожденности матрицы преобразования) и имеет представление в виде формулы (1.2):

, (1.2)

где осуществляется умножение вектора YUV на обратную матрицу преобразования.

Шаг 2. Разбиваем исходное изображение на матрицы 8x8. Формируем из каждой три рабочие матрицы ДКП – по 8 бит отдельно для каждой компоненты – имеем 24-битовый массив. При больших степенях сжатия этот шаг может выполняться чуть сложнее. Изображение делится по компоненте Y – как и в первом случае, а для компонент Cr и Cb матрицы набираются через строчку и через столбец. Т.е. из исходной матрицы размером 16x16 получается только одна рабочая матрица ДКП. При этом, как нетрудно заметить, мы теряем 3/4 полезной информации о цветовых составляющих изображения и получаем сразу сжатие в два раза. Мы можем поступать так благодаря работе в пространстве YCrCb. На результирующем RGB изображении, как показала практика, это сказывается несильно.

Шаг 3. В упрощенном виде ДКП при n=8 можно представить в виде формулы (1.3):

, (1.3)

где ,

.

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

Шаг 4. Производим квантование. В принципе, это просто деление рабочей матрицы на матрицу квантования поэлементно. Для каждой компоненты (Y, U и V), в общем случае, задается своя матрица квантования (далее МК) q[u,v]. Например, формулой (1.4) задается МК для компоненты Y:

(1.4)

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

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

Шаг 5. Переводим матрицу 8x8 в 64-элементный вектор при помощи «зигзаг-сканирования» как показано на рисунке 1.1, т.е. берем элементы с индексами (0,0), (0,1), (1,0), (2,0)...

Рисунок 1.1 – Обход матрицы методом «зигзаг»

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

Шаг 6. Производим свертывание полученного вектора с помощью алгоритма группового кодирования. При этом получаем пары типа (пропустить, число), где «пропустить» является счетчиком пропускаемых нулей, а «число» – значение, которое необходимо поставить в следующую ячейку. Так, вектор 42 3 0 0 0 -2 0 0 0 0 1... будет свернут в пары (0,42) (0,3) (3,-2) (4,1)...

Шаг 7. Свертываем получившиеся пары кодированием по Хаффману с фиксированной таблицей (таблица 1.1).

Таблица 1.1 – Фиксированная таблица кода Хаффмана

Длина серии	Код белой подстроки	Код черной подстроки
0	00110101	0000110111
1	00111	010
2	0111	11
3	1000	10
4	1011	011
5	1100	0011
6	1110	0010
7	1111	00011
8	10011	000101
9	10100	000100

Продолжение таблицы 1.1

Длина серии	Код белой подстроки	Код черной подстроки
10	00111	0000100
11	01000	0000101
12	001000	0000111
13	000011	00000100
14	110100	00000111
15	110101	000011000
16	101010	0000010111
17	101011	0000011000
18	0100111	0000001000
19	0001100	00001100111
20	0001000	00001101000
21	0010111	00001101100
22	0000011	00000110111
23	0000100	00000101000
24	0101000	00000010111
25	0101011	00000011000
26	0010011	000011001010
27	0100100	000011001011
28	0011000	000011001100
29	00000010	000011001101
30	00000011	000001101000
31	00011010	000001101001
32	00011011	000001101010
33	00010010	000001101011
34	00010011	000011010010
35	00010100	000011010011
36	00010101	000011010100
37	00010110	000011010101
38	00010111	000011010110
39	00101000	000011010111
40	00101001	000001101100
41	00101010	000001101101
42	00101011	000011011010
43	00101100	000011011011
44	00101101	000001010100
45	00000100	000001010101
46	00000101	000001010110
47	00001010	000001010111
48	00001011	000001100100
49	01010010	000001100101
50	01010011	000001010010
51	01010100	000001010011
52	01010101	000000100100
53	00100100	000000110111
54	00100101	000000111000
55	01011000	000000100111
56	01011001	000000101000

Окончание таблицы 1.1

Длина серии	Код белой подстроки	Код черной подстроки
57	01011010	000001011000
58	01011011	000001011001
59	01001010	000000101011
60	01001011	000000101100
61	00110010	000001011010
62	00110011	000001100110
63	00110100	000001100111

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

Характеристики

Список файлов ВКР