Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Алгоритм JPEG

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

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

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

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

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

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


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

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

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

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

nu,v] = ^Hc(i,u)xC(j,v)y<y[iJl

4 ,=о у=о


где


C(i,u) = A(m)xcos(-—l )Xuxn \



А(и) =4=, for us*O, •Jl

1, for u*0.


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

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

rY[u,v])

Yq[u, v] = IntegerRound

q[u,v]

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

В стандарт 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 раз без серьезных потерь.

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

■ задается степень сжатия;

■ выходное цветное изображение может иметь 24 бита на точку.

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

■ При повышении степени сжатия изображение распадается на отдельные квадраты (8x8). Это связано с тем, что происходят большие потери в низких частотах при квантовании и восстановить исходные данные ста­новится невозможно.

■ Проявляется эффект Гиббса- ореолы по границам резких переходов цветов.

Как уже говорилось, стандартизован JPEG относительно недавно -в 1991 г. Но уже тогда существовали алгоритмы, сжимающие сильнее при меньших потерях качества. Дело в том, что действия разработчиков стан­дарта были ограничены мощностью существовавшей на тот момент техники. То есть даже на ПК алгоритм должен был работать меньше минуты на среднем изображении, а его аппаратная реализация должна быть относи­тельно простой и дешевой. Алгоритм должен был быть симметричным (время разархивации примерно равно времени архивации).

Выполнение последнего требования сделало возможным появление та­ких устройств, как цифровые фотоаппараты, снимающие 24-битовые фото­графии на 8-256 Мб флеш-карту." Йвтом эта карта вставляется в разъём на вашем ноутбуке и соответствующая программа позволяет считать изобра­жения. Не правда Ня, если бы алгоритм был несимметричен, было бы не­приятно долго ждать, пока аппарат "перезарядится" - сожмет изображение.

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

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

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

Как стандарт ISO JPEG начинает все шире использоваться при обмене изображениями в компьютерных сетях. Поддерживается алгоритм JPEG в форматах Quick Time, PostScript Level 2, Tiff 6.0 и на данный момент зани­мает видное место в системах мультимедиа.

Характеристики алгоритма JPEG:o !ш. ,. Степень сжатия: 2-200 (задается здльзователем). ,ц, :_,. . Класс изображений: полноцветные 2jj.битовые изображения или изо-| бражения в градациях серого без резких переходов цве^о&,(фотографии).

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

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