Адаптивная генерация матриц квантования в JPEG-подобных схемах

Лужков Юрий Валерьевич,

аспирант Санкт-Петербургского государственного университета информационных технологий, механики и оптики.

Научный руководитель – доктор технических наук, профессор

Тропченко Александр Ювенальевич .

Введение

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

Широкая распространенность формата JPEG (Joint Photographic Experts Group ) [Wallace G. K.] ставит перед исследователями следующий вопрос: возможно ли модифицировать существующую схему компрессии таким образом, чтобы увеличить качество сжатия, не меняя при этом алгоритм декомпрессии? Решение этой задачи позволит внедрять модификации в существующие компрессоры, не заботясь о наличии у пользователей специального (модифицированного) программного обеспечения для декомпрессии изображений.

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

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

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

Адаптивное квантование сигнала

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

Так, пусть дано множество интервалов и множество точек , тогда функция квантования определяется как для . В случае равномерного скалярного квантования множество интервалов можно представить в виде:

где – параметр, или шаг квантования , – базовое смещение интервалов, , – номер интервала, который и является кодируемым объектом. Тогда операция квантования может быть сведена к простому делению с округлением:

.(1)

Адаптивность в скалярном квантовании достигается за счёт индивидуального выбора шага квантования для каждого квантуемого значения.

Адаптивное скалярное квантование на основе весового критерия

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

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

Таким образом, процедура квантования выполняется с учетом некоторой статистической информации о сигнале, заданном как , собранной от M блоков и уникальной для элементов каждого индекса n . Функция квантования (1) в этом случае будет обозначаться как , а функция параметра квантования – .

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

Одним из способов вычисления базируется на средних амплитудах:

.(2)

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

.(3)

Обратимся к вопросу определения функции . Пусть её значения должны быть ограничены диапазоном . Введём линейную функцию от :

,

где и – минимальное и максимальное значение соответственно (случай рассматривается отдельно).

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

.(4)

Поскольку любой в общем случае зависит от всех элементов исходного спектрального вектора , функция E также зависит от . Фактически, это есть функция шага квантования сигнала . Введем обозначение . Тогда формула (4) окончательно принимает вид:

.(5)

Таким образом, функция шага квантования локализована в диапазоне от a 1 до a 2 .Варьируя её форму, можно в большей или меньшей степени подавлять определённые группы коэффициентов.

Применим теперь предложенный подход для адаптивной генерации матриц квантования в схеме JPEG . В (5) будем использовать линейную корректирующую функцию и критерий максимальных амплитуд (3).

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

Рис. 1. Стандартные и сгенерированные функции параметра квантования с упорядоченными

по возрастанию значениями.

График для изображения « Oldman » приведен на рис. 2, слева. Справа показаны результаты компрессии с применением матриц по умолчанию и матриц, сгенерированных в рамках эксперимента. Как видно из результатов, разница в степени сжатия составляет до 20 % в пользу адаптивного подхода при одинаковых значениях PSNR .

Рис. 2. Генерация адаптивных матриц квантования для схемы JPEG .

Заключение

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

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

Литература

1. Fung H. T., Parker K. J. Design of image-adaptive quantization tables for JPEG // Journal of Electronic Imaging. – 1996. – Vol. 4, N. 2. – P. 144 – 150.

2. Gray R.M., Neuhoff D.L. Quantization // IEEE Transactions on Information Theory. – 1998. – Vol. 44, N. 6. – P. 2325 – 2383.

3. Ratnakar V., Livny M. Extending RD -OPT with global thresholding for JPEG optimization // Data Compression Conference. – 1996.

4. Wallace G. K. The JPEG still picture compression standard // IEEE Trans. Consumer Electronics. – 1992. – Vol. 38, N. 1. – P. 18 – 34.

Алгоритм JPEG

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

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

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

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

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

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

Упрощенно перевод из цветового пространства RGB в цветовое пространство YCrCb можно представить с помощью матрицы перехода:

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

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

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

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

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

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

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

Таким образом, в начале вектора мы получаем коэффициенты матрицы, соответствующие низким частотам, а в конце - высоким.

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

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

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

Конвейер операций, используемый в алгоритме JPEG:

Существенными положительными сторонами алгоритма является то, что:

1. Задается степень сжатия.
2. Выходное цветное изображение может иметь 24 бита на точку.

Отрицательными сторонами алгоритма является то, что:

1. При повышении степени сжатия изображение распадается на отдельные квадраты (8x8). Это связано с тем, что происходят большие потери в низких частотах при квантовании, и восстановить исходные данные становится невозможно.
2. Проявляется эффект Гиббса – ореолы по границам резких переходов цветов.

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

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

Стандартизован JPEG в 1991 году. Но уже тогда существовали алгоритмы, сжимающие сильнее при меньших потерях качества. Дело в том, что действия разработчиков стандарта были ограничены мощностью существовавшей на тот момент техники.

Несколько слов необходимо сказать о модификациях этого алгоритма. Хотя JPEG и является стандартом ISO, формат его файлов не был зафиксирован. Пользуясь этим, производители создают свои, несовместимые между собой форматы, и, следовательно, могут изменить алгоритм. Так, внутренние таблицы алгоритма, рекомендованные ISO, заменяются ими на свои собственные. Кроме того, легкая неразбериха присутствует при задании степени потерь. Например, при тестировании выясняется, что "отличное" качество, “100%” и “10 баллов” дают существенно различающиеся картинки. При этом, кстати, "100%" качества не означают сжатие без потерь . Встречаются также варианты JPEG для специфических приложений.

Характеристики алгоритма JPEG:
Степень сжатия 2-200 (Задается пользователем).
Класс изображений: Полноцветные 24 битные изображения или изображения в градациях серого без резких переходов цветов (фотографии).
Симметричность: 1
Характерные особенности: В некоторых случаях, алгоритм создает "ореол" вокруг резких горизонтальных и вертикальных границ в изображении (эффект Гиббса). Кроме того, при высокой степени сжатия изображение распадается на блоки 8x8 пикcелей.

JPEG-сжатие цифрового изображения

Одним из наиболее полных и популярных стандартов сжатия изображений является стандарт JPEG.

Сам процесс сжатия состоит из трех последовательных шагов:

а) Вычисление дискретного косинусного преобразования (ДКП) для матриц 8*8-блоков, полученных после стандартного разбиения матрицы ЦИ;

б) квантование коэффициентов ДКП;

в) кодирование неравномерным кодом.

Сначала ЦИ разбивается на отдельные блоки размером 8*8 элементов, которые обрабатываются последовательно слева направо и сверху вниз. Обработка каждого блока начинается со сдвига по яркости значений всех его 64 элементов, что достигается вычитанием величины , где - максимальное число уровней яркости. Затем вычисляется двумерное ДКП элементов блока. Полученные значения коэффициентов квантуются в соответствии с формулой:

,

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

.

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

. (2.5)

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

Отквантованные значения коэффициентов переупорядочиваются зигзаг-преобразованием согласно:

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

Одномерный массив, полученный после зигзаг-преобразования, упорядочивается по возрастанию пространственной частоты, при этом, как правило, возникают длинные последовательности нулей, что эффективно используется процедурой JPEG-кодирования. Рекомендованная JPEG матрица квантования имеет следующий вид:

Пример . Последовательное кодирование и декодирование JPEG . Рассмотрим сжатие и восстановление следующего блока 8*8 элементов согласно стандарту последовательного кодирования JPEG:

Исходные пиксели могут иметь 256 или 2 8 уровней яркости, так что процесс кодирования начинается со сдвига диапазона значений – вычитания из значений пикселей величины 2 7 или 128. В результате получается массив:

который после прямого ДКП будет иметь вид:

Если для квантования полученных данных используется приведенная выше матрица квантования, то после квантования коэффициенты примут вид:

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

(-26 -31 -3 -2 -6 2 -4 1 -4 1 1 5 0 2 0 0 -1 2 0 0 0 0 0 -1 -1 КБ)

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

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

Полностью восстановленный блок получается после выполнения обратного ДКП полученного массива:

и обратного сдвига диапазона значений на +2 7 =+128. В результате получаем:

Все отличия значений элементов исходного и восстановленного блоков возникают вследствие самой природы сжатия с потерями, являющегося сутью JPEG процедур сжатия и восстановления. В данном примере ошибки восстановления находятся в диапазоне от -14 до 11 и распределены следующим образом:

Характерные особенности сингулярных чисел блоков матрицы цифрового изображения при JPEG-сжатии. Пусть исходное ЦИ в градациях серого, хранящееся в некотором формате без потерь, например, в формате TIF, матрица которого имеет размеры , разбивается стандартным образом на блоки . Если для каждого блока ЦИ определить множество всех СНЧ (сингулярный спектр), то оказывается, что в среднем лишь 2.40% от общего числа блоков (ОЧБ) имеют нулевые СНЧ.

Данный факт не случаен. Ранг любой матрицы определяется количеством ее ненулевых СНЧ, а значит наличие нулей в сингулярном спектре будет говорить о том, что число ее линейно независимых строк (столбцов) меньше размера. Однако, для произвольного реального ЦИ, даже с учетом коррелированности значений яркости пикселей, вероятность того, что строки (столбцы) очередного блока окажутся линейно зависимыми, невелика.

Квантование коэффициентов DCT, которое происходит в процессе сохранения ЦИ в формате JPEG (с потерями), является необратимой процедурой и приводит к некоторым особенностям возмущений СНЧ блоков.

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

У полученной матрицы практически все блоки содержат нулевые СНЧ, причем таких значений в блоках будет достаточно много (табл.2.1). Такая ситуация закономерна. После квантования и округления коэффициентов DCT блоков многие из них, отвечающие высоким и средним частотам, обнулятся, оставаясь нулями после ЧВ, что, учитывая соответствие между коэффициентами дискретного преобразования Фурье и сингулярными тройками матрицы изображения, где - СНЧ и отвечающие ему левый и правый СНВ соответственно, приведет к обнулению наименьших (а возможно и средних по величине) СНЧ матриц блоков.

Табл.2.1. Результаты сингулярного разложения блоков частично восстановленных изображений

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

Для наглядного представления справедливости вышесказанного рассмотрим изображение СELL.TIF (рис.2.5(а)). На рис.2.5(б) представлена матрица нулевых СНЧ блоков (МНСЧБ) размерности ЧВ-изображения, каждый элемент которой равен количеству нулевых СНЧ в соответствующем блоке. На рисунке выделены элементы, имеющие наименьшие значения, что позволяет наглядно увидеть соответствие между контурами исходного ЦИ и блоками, содержащими наименьшее количество нулевых СНЧ.

Пусть исходное изображение, подвергшееся JPEG-сжатию, восстанавливается полностью. Это означает, что после ЧВ все значения яркости пикселей округляются до целых и вводятся в диапазон . Это действие возмутит матрицу изображения, полученную после ЧВ, определенным образом изменится количество нулевых СНЧ в блоках (табл.2.2). Там, где после ЧВ не было элементов, значительно меньших 0 или больших 255, возмущение матрицы будет небольшим. В соответствии с соотношением

, (2.6)

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

Рис.2.5. Исходное изображение СELL.TIF (а); МНСЧБ после ЧВ (б); МНСЧБ после полного восстановления (в)

Наиболее заметным различие между совокупным исходным изображением и полностью восстановленным после JPEG-сжатия будет при сравнении их МНСЧБ. Типичная картина представлена на рис.2.5(в), при этом МНСЧБ для CELL.TIF имела только нулевые значения.

Таблица 2.2. Результаты сингулярного разложения блоков полностью восстановленных изображений

Вопросы

1. Что означает сжатие даннях? Что такое избыточность даннях?
2. Основные виды избыточности данных.
3. Как реализуется сжатие посредством квантования?
4. Что такое малоранговая оппроксимация изображения? Как реализуется сжатие посредством использования малоранговых аппроксимаций изображения?
5. Что такое сингулярное разложение матрицы?
6. Что такое спектральное разложение матрицы?
7. Соответствие между параметрами цифрового изображения в пространственной и частотной областях.
8. Основные шаги JPEG-сжатие цифрового изображения. Матрицы квантования.
9. Характерные особенности сингулярных чисел блоков матрицы цифрового изображения при JPEG-сжатии.
10. Частичное и полное восстановление цифрового изображения после сжатия.

Литература

1. Кобозева А.А. Анализ информационной безопасности / А.А.Кобозева, В.А.Хорошко. – К.: Изд. ГУИКТ, 2009. – 251 с.
2. Деммель Дж. Вычислительная линейная алгебра / Дж.Деммель; пер.с англ. Х.Д.Икрамова. - М.: Мир, 2001. - 430 с.
3. Бахвалов Н.С. Численные методы / Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков. - М.: БИНОМ. Лаборатория знаний, 2006. - 636 с.
4. Гонсалес Р. Цифровая обработка изображений / Р.Гонсалес, Р.Вудс; пер. с англ. под ред. П.А.Чочиа. - М.: Техносфера, 2005. - 1072 с.
5. Каханер Д. Численные методы и программное обеспечение / Д.Каханер, К.Моулер, С.Нэш; пер. с англ. Х.Д.Икрамова. - М.: Мир, 2001. - 575 с.
6. Гантмахер Ф.Р. Теория матриц / Ф.Р.Гантмахер. - М.: Наука, 1988. - 552 с.
7. Воеводин В.В. Вычислительные основы линейной алгебры / В.В.Воеводин. - М.: Наука. Гл.ред.физ.-мат.лит., 1977. - 304 с.

(произносится «джейпег» Joint Photographic Experts Group, по названию организации-разработчика) - один из популярных графических форматов, применяемый для хранения фотоизображений и подобных им изображений. Файлы, содержащие данные JPEG, обычно имеют расширения.jpeg, .jfif, .jpg, .JPG, или.JPE. Однако из них.jpg самое популярное расширение на всех платформах.

1. Объединенная группа экспертов в области фотографии;

2. Разработанный данной группой метод сжатия изображений и соответствующий графический формат, часто используемый в WWW. Характерен компактностью файлов и, соответственно, быстрой передачей, а также «потерей» качества изображения. Используется преимущественно для фотографий, поскольку для них потеря качества менее критична. Сохраняет параметры цвета в цветовой модели RGB.

JPEG (произносится «джейпег », англ. Joint Photographic Experts Group , по названию организации-разработчика) - один из популярных графических форматов, применяемый для хранения фотоизображений и подобных им изображений. Файлы, содержащие данные JPEG, обычно имеют расширения .jpeg , .jfif , .jpg , .JPG , или .JPE . Однако из них .jpg самое популярное расширение на всех платформах. MIME-типом является image/jpeg.

Алгоритм JPEG является алгоритмом сжатия данных с потерями.

Область применения

Алгоритм JPEG в наибольшей степени пригоден для сжатия фотографий и картин, содержащих реалистичные сцены с плавными переходами яркости и цвета. Наибольшее распространение JPEG получил в цифровой фотографии и для хранения и передачи изображений с использованием сети Интернет.

С другой стороны, JPEG малопригоден для сжатия чертежей, текстовой и знаковой графики, где резкий контраст между соседними пикселами приводит к появлению заметных артефактов. Такие изображения целесообразно сохранять в форматах без потерь, таких как TIFF, GIF, PNG или RAW.

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

JPEG не должен использоваться и в тех случаях, когда недопустимы даже минимальные потери, например, при сжатии астрономических или медицинских изображений. В таких случаях может быть рекомендован предусмотренный стандартом JPEG режим сжатия Lossless JPEG (который, к сожалению, не поддерживается большинством популярных кодеков) или стандарт сжатия JPEG-LS.

Сжатие

При сжатии изображение преобразуется из цветового пространства RGB в YCbCr (YUV). Следует отметить, что стандарт JPEG (ISO/IEC 10918-1) никак не регламентирует выбор именно YCbCr, допуская и другие виды преобразования (например, с числом компонентов, отличным от трёх), и сжатие без преобразования (непосредственно в RGB), однако спецификация JFIF (JPEG File Interchange Format, предложенная в 1991 году специалистами компании C-Cube Microsystems, и ставшая в настоящее время стандартом де-факто) предполагает использование преобразования RGB->YCbCr.

После преобразования RGB->YCbCr для каналов изображения Cb и Cr, отвечающих за цвет, может выполняться «прореживание» (subsampling), которое заключается в том, что каждому блоку из 4 пикселов (2х2) яркостного канала Y ставятся в соответствие усреднённые значения Cb и Cr (схема прореживания «4:2:0»). При этом для каждого блока 2х2 вместо 12 значений (4 Y, 4 Cb и 4 Cr) используется всего 6 (4 Y и по одному усреднённому Cb и Cr). Если к качеству восстановленного после сжатия изображения предъявляются повышенные требования, прореживание может выполняться лишь в каком-то одном направлении - по вертикали (схема «4:4:0») или по горизонтали («4:2:2»), или не выполняться вовсе («4:4:4»).

Стандарт допускает также прореживание с усреднением Cb и Cr не для блока 2х2, а для четырёх расположенных последовательно (по вертикали или по горизонтали) пикселов, то есть для блоков 1х4, 4х1 (схема «4:1:1»), а также 2х4 и 4х2. Допускается также использование различных типов прореживания для Cb и Cr, но на практике такие схемы применяются исключительно редко.

Далее, яркостный компонент Y и отвечающие за цвет компоненты Cb и Cr разбиваются на блоки 8х8 пикселов. Каждый такой блок подвергается дискретному косинусному преобразованию (ДКП). Полученные коэффициенты ДКП квантуются (для Y, Cb и Cr в общем случае используются разные матрицы квантования) и пакуются с использованием кодов Хаффмана. Стандарт JPEG допускает также использование значительно более эффективного арифметического кодирования, однако, из-за патентных ограничений (патент на описанный в стандарте JPEG арифметический QM-кодер принадлежит IBM) на практике оно не используется.

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

При сохранении изображения в JPEG-файле указывается параметр качества, задаваемый в некоторых условных единицах, например, от 1 до 100 или от 1 до 10. Большее число обычно соответствует лучшему качеству (и большему размеру сжатого файла). Однако, даже при использовании наивысшего качества (соответствующего матрице квантования, состоящей из одних только единиц) восстановленное изображение не будет в точности совпадать с исходным, что связано как с конечной точностью выполнения ДКП, так и с необходимостью округления значений Y, Cb, Cr и коэффициентов ДКП до ближайшего целого. Режим сжатия Lossless JPEG, не использующий ДКП, обеспечивает точное совпадение восстановленного и исходного изображений, однако, его малая эффективность (коэффициент сжатия редко превышает 2) и отсутствие поддержки со стороны разработчиков программного обеспечения не способствовали популярности Lossless JPEG.

Разновидности схем сжатия JPEG

Стандарт JPEG предусматривает два основных способа представления кодируемых данных.

Наиболее распространённым, поддерживаемым большинством доступных кодеков, является последовательное (sequential JPEG) представление данных, предполагающее последовательный обход кодируемого изображения поблочно слева направо, сверху вниз. Над каждым кодируемым блоком изображения осуществляются описанные выше операции, а результаты кодирования помещаются в выходной поток в виде единственного «скана», т.е. массива кодированных данных, соответствующего последовательно пройденному («просканированному») изображению. Основной или «базовый» (baseline) режим кодирования допускает только такое представление. Расширенный (extended) режим наряду с последовательным допускает также прогрессивное (progressive JPEG) представление данных.

В случае progressive JPEG сжатые данные записываются в выходной поток в виде набора сканов, каждый из которых описывает изображение полностью с всё большей степенью детализации. Это достигается либо путём записи в каждый скан не полного набора коэффициентов ДКП, а лишь какой-то их части: сначала - низкочастотных, в следующих сканах - высокочастотных (метод «spectral selection» т.е. спектральных выборок), либо путём последовательного, от скана к скану, уточнения коэффициентов ДКП (метод «successive approximation», т.е. последовательных приближений). Такое прогрессивное представление данных оказывается особенно полезным при передаче сжатых изображений с использованием низкоскоростных каналов связи, поскольку позволяет получить представление обо всём изображении уже после передачи незначительной части JPEG-файла.

Обе описанные схемы (и sequential, и progressive JPEG) базируются на ДКП и принципиально не позволяют получить восстановленное изображение абсолютно идентичным исходному. Однако, стандарт допускает также сжатие, не использующее ДКП, а построенное на основе линейного предсказателя (lossless, т.е. «без потерь», JPEG), гарантирующее полное, бит-в-бит, совпадение исходного и восстановленного изображений. При этом коэффициент сжатия для фотографических изображений редко достигает 2, но гарантированное отсутствие искажений в некоторых случаях оказывается востребованным. Заметно большие степени сжатия могут быть получены при использовании не имеющего, несмотря на сходство в названиях, непосредственного отношения к стандарту JPEG ISO/IEC 10918-1 (ITU T.81 Recommendation) метода сжатия JPEG-LS, описываемого стандартом ISO/IEC 14495-1 (ITU T.87 Recommendation).

Синтаксис и структура формата JPEG

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

После вычисления всех коэффициентов DCT их необходимо проквантовать. На этом шаге происходит отбрасывание части информации (небольшие потери происходят и на предыдущем шаге из-за конечной точности вычислений на компьютере). Каждое число из матриц коэффициентов DCT делится на специальное число из «таблицы квантования», а результат округляется до ближайшего целого. Как уже отмечалось, необходимо иметь три такие таблицы для каждой цветовой компоненты. Стандарт JPEG допускает использование четырех таблиц, и пользователь может выбрать любую из этих таблиц для квантования компонентов цвета. Все 64 числа из таблицы квантования являются параметрами JPEG. В принципе, пользователь может поменять любой коэффициент для достижения большей степени сжатия. На практике весьма сложно экспериментировать с таким большим числом параметров, поэтому программное обеспечение JPEG использует два подхода:

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

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

Светимость

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

3. 64 числа выстраиваются одно за другим как при сканировании зигзагом (см. рис. 3.5а). В начале стоят ненулевые числа, за которыми обычно следует длинный хвост из одних нулей. В файл выводятся только ненулевые числа (после надлежащего кодирования) за которыми следует специальный код ЕОВ (end-of-block, конец блока). Нет необходимости записывать весь хвост нулей (можно также сказать, что ЕОВ кодирует длинную серию нулей).

Пример : В табл. 3.51 приведен список гипотетических коэффициентов DCT, из которых только 4 не равны нулю. При зигзагообразном упорядочении этих чисел получается последовательность коэффициентов:

Табл. 3.51. Квантованные коэффициенты.

А как написать подпрограмму для считывания элементов матрицы по зигзагу? Простейший способ состоит в ручном прослеживании этого пути и в записи результата в массив структур zz, в котором каждая структура состоит из пары координат клеток, через которые проходит зигзагообразный путь (см. рис. 3.52).

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

4. Ненулевые коэффициенты преобразования сжимаются по методу Хаффмана (см. § 3.7.5).

5. Первое из этих чисел (коэффициент DC, см. стр. 145) обрабатывается отдельно от других чисел (коэффициентов АС).

Рис. 3.52. Координаты зигзагообразного пути.