Алгоритм JPEG

Алгоритм JPEG

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

Алгоритм разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG - Joint Photographic Expert Group - подразделение в рамках ISO - Международной организации по стандартизации. Название алгоритма читается ['jei'peg]. В целом алгоритм основан на дискретном косинусоидальном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.

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

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

Как работает алгоритм

Итак, рассмотрим алгоритм подробнее. Пусть мы сжимаем 24-битное изображение.

Шаг 1.

Перевод в цветовое пространство YCbCr. Переводим изображение из цветового пространства RGB, с компонентами, отвечающими за красную (Red), зеленую (Green) и синюю (Blue) составляющие цвета точки, в цветовое пространство YCrCb (иногда называют YUV).

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

Перевод осуществляется по следующей формуле:

обратный перевод:

Шаг 2.

Субдискретизация  компонент цветности. Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП - по 8 бит отдельно для каждой компоненты. При больших степенях сжатия этот шаг может выполняться чуть сложнее. Изображение делится по компоненте Y - как и в первом случае, а для компонент Cr и Cb матрицы набираются через строчку и через столбец.

После перевода в цветовое пространство YCbCr осуществляется субдискретизация по следующим соотношениям: 4:4:4 (отсутствие передискретизации), 4:2:2 (компоненты цветности меняются через одну по горизонтали), 4:2:0 (компоненты цветности меняются через одну по горизонтали; при этом по вертикали они меняются через строку). Проиллюстрируем подробнее данные соотношения на примерах. Будем преобразовывать блок 4 × 4 пикселя изображения:

 

1. Y₀₀Cb₀₀Cr₀₀ Y₀₁Cb₀₁Cr₀₁ Y₀₂Cb₀₂Cr₀₂ Y₀₃Cb₀₃Cr₀₃
2. Y₁₀Cb₁₀Cr₁₀ Y₁₁Cb₁₁Cr₁₁ Y₁₂Cb₁₂Cr₁₂ Y₁₃Cb₁₃Cr₁₃
3. Y₂₀Cb₂₀Cr₂₀ Y₂₁Cb₂₁Cr₂₁ Y₂₂Cb₂₂Cr₂₂ Y₂₃Cb₂₃Cr₂₃
4. Y₃₀Cb₃₀Cr₃₀ Y₃₁Cb₃₁Cr₃₁ Y₃₂Cb₃₂Cr₃₂ Y₃₃Cb₃₃Cr₃₃

тогда:

• 4:4:4. Cубдискретизированный блок будет таким же.
• 4:2:2. Cубдискретизированный блок будет таким:
• Y₀₀Cb₀₀Cr₀₀ Y₀₁Cb₀₀Cr₀₀ Y₀₂Cb₀₂Cr₀₂ Y₀₃Cb₀₂Cr₀₂
• Y₁₀Cb₁₀Cr₁₀ Y₁₁Cb₁₀Cr₁₀ Y₁₂Cb₁₂Cr₁₂ Y₁₃Cb₁₂Cr₁₂
• Y₂₀Cb₂₀Cr₂₀ Y₂₁Cb₂₀Cr₂₀ Y₂₂Cb₂₂Cr₂₂ Y₂₃Cb₂₂Cr₂₂
• Y₃₀Cb₃₀Cr₃₀ Y₃₁Cb₃₀Cr₃₀ Y₃₂Cb₃₂Cr₃₂ Y₃₃Cb₃₂Cr₃₂
• 4:2:0. Cубдискретизированный блок будет таким:
• Y₀₀Cb₀₀Cr₀₀ Y₀₁Cb₀₀Cr₀₀ Y₀₂Cb₀₂Cr₀₂ Y₀₃Cb₀₂Cr₀₂
• Y₁₀Cb₀₀Cr₀₀ Y₁₁Cb₀₀Cr₀₀ Y₁₂Cb₀₂Cr₀₂ Y₁₃Cb₀₂Cr₀₂
• Y₂₀Cb₂₀Cr₂₀ Y₂₁Cb₂₀Cr₂₀ Y₂₂Cb₂₂Cr₂₂ Y₂₃Cb₂₂Cr₂₂
• Y₃₀Cb₂₀Cr₂₀ Y₃₁Cb₂₀Cr₂₀ Y₃₂Cb₂₂Cr₂₂ Y₃₃Cb₂₂Cr₂₂

В дальнейшем компоненты обрабатываются и хранятся отдельно друг от друга. Таким образом, в последних  двух случаях мы сразу убрали и информации соответственно. Выбор того или иного способа передискретизации влияет на изменение степени сжатия. Очевидно, что при отсутствии передискретизации степень сжатия ухудшится, а при схеме 4:2:0 будет наибольшей. Если изображение не делится нацело на блоки 4 × 4, то оно дополняется по непрерывности, т.е. в случае, если размер по вертикали не делится на 4, то добавляется еще от одной до трех строк, совпадающих с последней снизу. Аналогично делается, если размер по горизонтали не делится на 4 - добавляются столбцы, совпадающие с самым правым.

Мы можем поступать так благодаря работе в пространстве YCrCb. На результирующем RGB изображении, как показала практика, это сказывается несильно.

Шаг 3.

Применение  дискретного косинус-преобразования. Пусть изображение имеет размеры N × N. Прямое преобразование записывается так:

Обратное преобразование имеет следующий вид:

Дискретное преобразование обладает свойствами.

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

Коэффициенты t(u, v) - это амплитуды пространственных частот изображения. В случае изображений с плавными переходами большая часть информации содержится в низкочастотном спектре.

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

Шаг 4.

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

где означает покомпонентное умножение и взятие целой части, т.е. T_ij = [t_ijq_ij ], где t_ij - исходные коэффициенты ДКП, q_ij - компоненты матрицы квантования, [] - операция взятия целой части. Таким образом, происходит квантование области определения коэффициентов исходной матрицы. Матрицы квантования разные для компонент цветности и яркости.

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

Матрицы квантования оговорены  в стандарте, а для изменения  степени сжатия их умножают на определенный коэффициент. Очевидно, что потери на этой стадии самые большие; если убрать слишком много информации из низкочастотных компонент (т.е. слишком сильно огрубить компоненты), то появятся артефакты: распадение на квадраты 8 × 8, эффект Гиббса (возникновение ореола рядом с местами резких цветовых переходов)

Шаг 5.

Зигзаг-упорядочивание. К каждой квантованной матрице применяется так называемое зигзаг-упорядочивание. Это особый проход матрицы для получения последовательности Сначала идет элемент T₀₀, затем T₀₁, T₁₀, T₁₁ . . . Причем для типичных фотореалистических изображений сначала будут идти ненулевые коэффициенты, соответствующие низкочастотным компонентам, а затем - множество нулей.

Шаг 6.

Сжатие методом RLE Полученная последовательность кодируется с помощью модифицированного алгоритма группового кодирования. Выводятся пары чисел: первое - число нулей, второе - значение после подпоследовательности нулей. Например, закодируем такую последовательность:

122 0 125 0 0 44 0 0 0 0 -1.

Получим: (0, 122) (1, 125) (2, 44) (4, -1). Также существует специальный код для обозначения того факта, что оставшиеся значения в последовательности суть нули.

Шаг 7.

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

Алгоритм восстановления изображения суть инверсия вышеприведенных действий. Степень сжатия от 5 до 100 и более раз (варьируется с помощью матриц квантования и задания метода субдискретизации). При этом визуальное качество для большинства фотореалистичных изображений остается на хорошем уровне при сжатии до 15 раз.

Данный алгоритм и формат являются самыми распространенными для передачи и хранения полноцветных изображений. Столь широкое распространение  объясняется несколькими причинами: относительно невысокой вычислительной сложностью (что было очень актуально до 1996 года), достаточной степенью стандартизованности формата и алгоритма, а также отсутствием необходимости платить какие-либо лицензионные отчисления (т.к. отсутствуют патентованные алгоритмы). К недостаткам алгоритма относят возникновение упоминавшихся выше артефактов, которые слишком заметны для человеческого глаза.

Описанная выше схема сжатия является типичной для алгоритмов сжатия изображений  с потерями (за исключением фрактального). Отличие в основном состоит в типе преобразования на шаге 3. Далее мы рассмотрим другой вид преобразования.

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

Степень сжатия: 2-200 (Задается пользователем).

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

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

Характерные особенности: В некоторых случаях, алгоритм создает "ореол" вокруг резких горизонтальных и вертикальных границ в изображении (эффект Гиббса). Кроме того, при высокой степени сжатия изображение распадается на блоки 8х8 пикселов.