Пояснительная записка (Декодирование скрытой информации с использованием алгоритма JPEG), страница 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 – Фиксированная таблица кода Хаффмана

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

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

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