Сжатие изображений: JPEG и JPEG2000. Декодирование JPEG для чайников

Алгоритм разработан группой экспертов в области фотографии (Joint Photographic Expert Group) специально для сжатия 24-битных и полутоновых изображений в 1991 году. Этот алгоритм не очень хорошо сжимает двухуровневые изображении, но он прекрасно обрабатывает изображения с непрерывными тонами, в которых близкие пикселы обычно имеют схожие цвета. Обычно глаз не в состоянии заметить какой-либо разницы при сжатии этим методом в 10 или 20 раз.

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

Рассмотрим работу алгоритма подробнее. Предположим, что сжимается полноцветное 24-битное изображение. В этом случае получаем следующие этапы работы.

Шаг 1. Переводим изображение из пространства RGB в пространство YCbCr с помощью следующего выражения:

Отметим сразу, что обратное преобразование легко получается путем умножения обратной матрицы на вектор , который по существу является пространством YUV:

.

Шаг 2. Разбиваем исходное изображение на матрицы 8х8. Формируем из каждой три рабочие матрицы ДКП – по 8 бит отдельно для каждой компоненты. При больших степенях сжатия блок 8х8 раскладывается на компоненты YCbCr в формате 4:2:0, т.е. компоненты для Cb и Cr берутся через точку по строкам и столбцам.

Шаг 3. Применение ДКП к блокам изображения 8х8 пикселей. Формально прямое ДКП для блока 8х8 можно записать в виде

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

.

Здесь является матрицей, размером 8х8 элементов, описывающая 8-ми мерное пространство, для представления столбцов блока в этом пространстве. Матрица является транспонированной матрицей и делает то же самое, но для строк блока . В результате получается разделимое преобразование, которое в матричном виде записывается как

Здесь - результат ДКП, для вычисления которого требуется операций умножения и почти столько же сложений, что существенно меньше прямых вычислений по формуле выше. Например, для преобразования изображения размером 512х512 пикселей потребуется арифметических операций. Учитывая 3 яркостных компоненты, получаем значение 12 582 912 арифметических операций. Количество умножений и сложений можно еще больше сократить, если воспользоваться алгоритмом быстрого преобразования Фурье. В результате для преобразования одного блока 8х8 нужно будет сделать 54 умножений, 468 сложений и битовых сдвигов.

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

Шаг 4. Квантование. На этом шаге происходит отбрасывание части информации. Здесь каждое число из матрицы делится на специальное число из «таблицы квантования», а результат округляется до ближайшего целого:

.

Причем для каждой матрицы Y, Cb и Cr можно задавать свои таблицы квантования. Стандарт JPEG даже допускает использование собственных таблиц квантования, которые, однако, необходимо будет передавать декодеру вместе со сжатыми данными, что увеличит общий размер файла. Понятно, что пользователю сложно самостоятельно подобрать 64 коэффициента, поэтому стандарт JPEG использует два подхода для матриц квантования. Первый заключается в том, что в стандарт JPEG включены две рекомендуемые таблицы квантования: одна для яркости, вторая для цветности. Эти таблицы представлены ниже. Второй подход заключается в синтезе (вычислении на лету) таблицы квантовании, зависящей от одного параметра , который задается пользователем. Сама таблица строится по формуле

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

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

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

Рис. 2. «Зигзаг»-сканирование

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

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

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

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

Рис. 3. Схема упорядочения DC коэффициентов

Рис. 4. Структурная схема алгоритма JPEG

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

При разработке данного стандарта руководствовались тем, что данный алгоритм должен был сжимать изображения довольно быстро – не более минуты на среднем изображении. Это в 1991 году! А его аппаратная реализация должна быть относительно простой и дешевой. При этом алгоритм должен был быть симметричным по времени работы. Выполнение последнего требования сделало возможным появление цифровых фотоаппаратов, снимающие 24 битные изображения. Если бы алгоритм был несимметричен, было бы неприятно долго ждать, пока аппарат «перезарядится» - сожмет изображение.

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

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

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

При сохранении JPEG-файла можно указать степень качества, а значит и степень сжатия, которую обычно задают в некоторых условных единицах, например, от 1 до 100 или от 1 до 10. Большее число соответствует лучшему качеству, но при этом увеличивается размер файла. Обыкновенно, разница в качестве между 90 и 100 на глаз уже практически не воспринимается. Следует помнить, что восстановленное из формата JPEG изображение не является точной копией оригинала. Распространённым заблуждением является мнение о том, что качество JPEG тождественно доле сохраняемой информации.

Широкая поддержка формата JPEG разнообразным ПО нередко приводит к кодированию в JPEG изображений, для того не предназначенных - безо всякого выигрыша по степени сжатия в сравнении с правильно сделанными PNG или GIF, но с прискорбными последствиями для качества. Например, попытка записать в JPEG изображение, содержащее мелкие контрастные детали (особенно, цветные) приведёт к появлению характерных хорошо заметных артефактов даже при высокой «степени качества».

Сжатие

При сжатии изображение преобразуется из цветового пространства 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"). Допускается также использование различных типов прореживания для Cb и Cr, но на практике такие схемы встречаются исключительно редко.

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

Матрицы, используемые для квантования коэффициентов ДКП, хранятся в заголовочной части 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 содержит последовательность маркеров, каждый из которых начинается с байта 0xFF, свидетельствующего о начале маркера, и байта — идентификатора. Некоторые маркеры состоят только из этой пары байтов, другие же содержат дополнительный данные, состоящие из двухбайтового поля с длиной информационной части маркера (включая длину этого поля, но за вычетом двух байтов начала маркера т.е. 0xFF и идентификатора) и собственно данных.

Основные маркеры JPEG

Маркер	Байты	Длина	Назначение

• Tutorial

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

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

Если есть желание, то предлагаю пройти те же этапы самостоятельно параллельно со статьей. Проверить, насколько приведенные рассуждения подходят для разных изображений, попытаться внести свои модификации в алгоритм. Это очень интересно. В качестве инструмента могу порекомендовать замечательную связку Python + NumPy + Matplotlib + PIL(Pillow). Почти вся моя работа (в т. ч. графики и анимация), была произведена с помощью них.

Внимание, трафик! Много иллюстраций, графиков и анимаций (~ 10Мб). По иронии судьбы, в статье про JPEG всего 2 изображения с этим форматом из полусотни.

Каков бы ни был алгоритм сжатия информации, его принцип всегда будет один - нахождение и описание закономерностей. Чем больше закономерностей, тем больше избыточности, тем меньше информации. Архиваторы и кодеры обычно «заточены» под конкретный тип информации, и знают где можно их найти. В некоторых случаях закономерность видна сразу, например картина голубого неба. Каждый ряд его цифрового представления можно довольно точно описать прямой.

Будем тренироваться на кошках енотах. В качестве примера взято серое изображение, приведенное выше. Оно хорошо совмещает как однородные области, так и контрастные. А если мы научимся сжимать серое, то и с цветным не будет проблем.

Векторное представление

Для начала проверим насколько зависимы два соседних пикселя. Логично предположить, что скорее всего, они будут очень похожи. Проверим это для всех пар изображения. Отметим их на координатной плоскости точками так, что значение точки по оси X - значение первого пикселя, по оси Y - второго. Для нашего изображения размером 256 на 256 получим 256*256/2 точек:

Предсказуемо, что большинство точек находится на или рядом с прямой y=x (а их там еще больше, чем видно на рисунке, так как они многократно накладываются друг на друга, и, к тому же, они полупрозрачные). А раз так, то было бы проще работать, повернув их на 45°. Для этого нужно выразить их в другой системе координат.

Базисные вектора новой системы, очевидно, такие: . Вынуждены делить на корень из двойки, чтобы получить ортонормированную систему (длины базисных векторов равны единичке). Здесь показано, что некоторая точка p = (x, y) в новой системе будет представлена как точка (a 0 , a 1). Зная новые коэффициенты, мы легко можем получить старые обратным поворотом. Очевидно, первая (новая) координата является средним, а вторая - разностью x и y (но деленные на корень из 2). Представьте, что вам предложено оставить только одно из значений: либо a 0 , либо a 1 (то есть другое приравнять нулю). Лучше выбрать a 0 , так как значение a 1 и так, скорее всего, будет около нуля. Вот, что получится, если мы восстановим изображение только по a 0:

Увеличение в 4 раза:

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

Это один и тот же график, но с разных точек зрения. Красные линии - оси, которые напрашивались сами собой. Им соответствуют вектора: . Напоминаю, что приходится делить на некоторые константы, чтобы длины векторов стали равны единице. Таким образом, разложив по такому базису, мы получим 3 значения a 0 , a 1 , a 2 , причем a 0 важнее a 1 , а a 1 важнее a 2 . Если мы выбросим a 2 , то график «сплющится» в направлении вектора e 2 . Этот и так довольно не толстый трехмерный лист станет плоским. Он потеряет не так много, зато мы избавимся от трети значений. Сравним изображения, восстановленные по тройкам: (a 0 , 0, 0), (a 1 , a 2 , 0) и (a 0 , a 1 , a 2). В последнем варианте мы ничего не выбросили, поэтому получим оригинал.

Увеличение в 4 раза:

Второй рисунок уже хорош. Резкие участки немного сгладились, но в целом картинка сохранилась очень неплохо. А теперь, точно так же поделим на четверки и визуально определим базис в четырехмерном пространстве… А, ну да. Но можно догадаться, каким будет один из векторов базиса, это: (1,1,1,1)/2. Поэтому можно посмотреть проекцию четырехмерного пространства на пространство, перпендикулярное вектору (1,1,1,1), чтобы выявить другие. Но это не лучший путь.
Наша цель - научиться преобразовывать (x 0 , x 1 , ..., x n-1) к (a 0 , a 1 , ..., a n-1) так, что каждое значение a i все менее важно, чем предыдущие. Если мы сможем так делать, то, возможно, последние значения последовательности вообще можно будет выбросить. Вышеприведенные опыты намекают, что можно. Но без математического аппарата не обойтись.
Итак, нужно преобразовать точки к новому базису. Но сначала необходимо найти подходящий базис. Вернемся к первому эксперименту разбиения на пары. Будем считать обобщенно. Мы определили базисные векторы:

Выразили через них вектор p :

или в координатах:

Чтобы найти a 0 и a 1 нужно спроецировать p на e 0 и e 1 соответственно. А для этого нужно найти скалярное произведение

аналогично:

В координатах:

Часто бывает удобнее проводить преобразование в матричной форме.

Тогда A = EX и X = E T A. Это красивая и удобная форма. Матрица E называется матрицей преобразования и является ортогональной, с ней мы еще встретимся.

Переход от векторов к функциям.

С векторами малых размерностей работать удобно. Однако мы хотим находить закономерности в бОльших блоках, поэтому вместо N-мерных векторов удобнее оперировать последовательностями, которыми представлено изображение. Такие последовательности я буду называть дискретными функциями, так как следующие рассуждения применимы и к непрерывным функциям.
Возвращаясь к нашему примеру, представим такую функцию f(i), которая определена всего в двух точках: f(0)=x и f(1)=y. Аналогично зададим базисные функции e 0 (i) и e 1 (i) на основе базисов e 0 и e 1 . Получим:

Это очень важный вывод. Теперь во фразе «разложение вектора по ортонормированным векторам» мы можем заменить слово «вектор» на «функция» и получить вполне корректное выражение «разложение функции по ортонормированным функциям». Не беда, что мы получили такую куцую функцию, так как такие же рассуждения работают и для N-мерного вектора, который можно представить как дискретную функцию с N значениями. А работа с функциями нагляднее, чем с N-мерными векторами. Можно и наоборот, представить такую функцию как вектор. Более того, обычную непрерывную функцию можно представить бесконечномерным вектором, правда уже не в евклидовом, а гильбертовом пространстве. Но мы туда не пойдем, нас будут интересовать только дискретные функции.
А наша задача нахождения базиса превращается в задачу нахождения подходящей системы ортонормированных функций. В следующих рассуждениях предполагается, что мы уже как-то определили набор базисных функций, по которым и будем раскладывать.
Допустим, у нас есть некоторая функция (представленная, например, значениями), которую мы хотим представить в виде суммы других. Можно представлять этот процесс в векторном виде. Для разложения функции нужно «спроецировать» ее на базисные функции по очереди. В векторном смысле вычисление проекции дает минимальное сближение исходного вектора к другому по расстоянию. Помня о том, что расстояние вычисляется с помощью теоремы Пифагора, то аналогичное представление в виде функций дает наилучшее среднеквадратичное приближение функции к другой. Таким образом, каждый коэффициент (k) определяет «близость» функции. Более формально, k*e(x) - лучшее среднеквадратичное приближение к f(x) среди l*e(x).
В следующем примере показан процесс приближения функции только по двум точкам. Справа - векторное представление.

Применительно к нашему эксперименту разбивания на пары, можно сказать, что эти две точки (0 и 1 по абсцисс) - пара соседних пикселей (x, y).
То же самое, но с анимацией:

Если мы возьмем 3 точки, то нужно рассматривать трехмерные вектора, однако приближение будет точнее. А для дискретной функции с N значениями нужно рассматривать N-мерные вектора.
Имея набор полученных коэффициентов, можно легко получить исходную функцию, просуммировав базисные функции, взятые с соответствующими коэффициентами. Анализ этих коэффициентов может дать много полезной информации (в зависимости от базиса). Частным случаем этих соображений является принцип разложения в ряд Фурье. Ведь наши рассуждения применимы к любому базису, а при разложении в ряд Фурье берется вполне конкретный.

Дискретные преобразования Фурье (ДПФ)

В предыдущей части мы пришли к выводу, что неплохо было бы разлагать функцию на составные. В начале 19 века Фурье тоже задумался над этим. Правда картинки с енотом у него не было, поэтому ему пришлось исследовать распределение тепла по металлическому кольцу. Тогда он выяснил, что очень удобно выражать температуру (и ее изменение) в каждой точке кольца как сумму синусоид с разными периодами. «Фурье установил (рекомендую к прочтению , интересно), что вторая гармоника затухает в 4 раза быстрее, чем первая, а гармоники более высоких порядков затухают с ещё большей скоростью».
В общем, вскоре оказалось, что периодичные функции замечательно раскладываются на сумму синусоид. А так как в природе существует много объектов и процессов, описывающимися периодичными функциями, то появился мощный инструмент их анализа.
Пожалуй, один из самых наглядных периодических процессов - это звук.

• 1-й график - чистый тон частотой 2500 герц.
• 2-й - белый шум. Т. е. шум c равномерно распределенными частотами по всему диапазону.
• 3-й - сумма первых двух.

Если бы мне дали значения последней функции на тот момент, когда я не знал про ряды Фурье, и попросили проанализировать их, то я бы точно растерялся и не смог бы сказать ничего путного. Ну, да, какая-то функция, но как понять, что там есть что-то упорядоченное? Но если бы я догадался прослушать последнюю функцию, то ухо уловило бы чистый тон среди шума. Хотя и не очень хорошо, так как я специально при генерации подобрал такие параметры, чтобы на суммарном графике сигнал визуально растворился в шуме. Как я понял, до сих пор точно не уставлено, как слуховой аппарат делает это. Однако, недавно стало ясно, что он не раскладывает звук на синусоиды. Возможно, когда-нибудь мы поймем как это происходит, и появятся более совершенные алгоритмы. Ну, а мы пока по старинке.
Почему бы не попробовать взять синусоиды в качестве базиса? На самом деле мы фактически уже сделали это. Вспомним наше разложение на 3 базисных вектора и представим их на графике:

Да-да, знаю, это выглядит как подгонка, но с тремя векторами трудно ожидать большего. Зато теперь понятно, как получить, например, 8 базисных векторов:


Не очень сложная проверка показывает, что эти вектора попарно перпендикулярны, т. е. ортогональны. Это значит, их можно использовать как базис. Преобразование по такому базису широко известно, и называется дискретным косинусным преобразованием (DCT). Думаю, из приведенных графиков понятно как получается формула DCT-преобразования:

Это все та же формула: A = EX с подставленным базисом. Базисные вектора указанного DCT (они же векторы-строки матрицы E) ортогональны, но не ортонормированы. Это следует помнить при обратном преобразовании (не буду останавливаться на этом, но, кому интересно - у inverse DCT появляется слагаемое 0.5*a 0 , так как нулевой вектор базиса больше остальных).
На следующем примере показан процесс приближения промежуточных сумм к исходным значениям. На каждой итерации очередной базис умножается на очередной коэффициент и прибавляется к промежуточной сумме (то есть так же, как и в ранних опытах над енотом - треть значений, две трети).

Но, все-таки, несмотря на некоторые доводы о целесообразности выбора такого базиса, реальных аргументов пока нет. Действительно, в отличие от звука, целесообразность разложения изображения на периодические функции гораздо менее очевидна. Впрочем, изображение действительно может быть слишком непредсказуемым даже на небольшом участке. Поэтому, картинку делят на достаточно маленькие кусочки, но не совсем крохотные, чтобы разложение имело смысл. В JPEG изображение «нарезается» на квадраты 8x8. В пределах такого кусочка фотографии обычно очень однородны: фон плюс небольшие колебания. Такие области шикарно приближаются синусоидами.
Ну, допустим, этот факт более или менее понятен интуитивно. Но появляется нехорошее предчувствие насчет резких цветовых переходов, ведь медленно изменяющиеся функции нас не спасут. Приходится добавлять разные высокочастотные функции, которые справляются со своей работой, но побочно проявляются на однородном фоне. Возьмем изображение 256x256 с двумя контрастными областями:

Разложим каждую строку с помощью DCT, получив, таким образом, по 256 коэффициентов на строку.
Затем оставим только первые n коэффициентов, а остальные приравняем нулю, и, поэтому, изображение будет представлено в виде суммы только первых гармоник:

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

И вообще, если вдали от границы мы видим первоначальный равномерный фон, то при приближении к ней, амплитуда начинает расти, наконец достигает минимального значения, а затем резко становится максимальным. Это явление известно как эффект Гиббса.

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


При изучении DCT может сложиться ложное впечатление, что всегда вполне достаточно всего нескольких первых (низкочастотных) коэффициентов. Это верно для многих кусочков фотографий, тех, чьи значения не меняются резко. Однако, на границе контрастных участков значения будут резво «скакать» и даже последние коэффициенты будут велики. Поэтому, когда слышите о свойстве сохранения энергии DCT, делайте поправку на то, что оно относится ко многим видам встречаемых сигналов, но не ко всем. Для примера подумайте, как будет выглядеть дискретная функция, коэффициенты разложения которой равны нулю, кроме последнего. Подсказка: представьте разложение в векторном виде.
Несмотря на недостатки, выбранный базис является одним из лучших на реальных фотографиях. Чуть позже мы увидим небольшое сравнение с другими.

DCT vs все остальное

Когда я изучал вопрос ортогональных преобразований, то, честно говоря, меня не очень убеждали доводы о том, что все вокруг - это сумма гармонических колебаний, поэтому нужно и картинки раскладывать на синусоиды. А может быть лучше подойдут какие-нибудь ступенчатые функции? Поэтому искал результаты исследований об оптимальности DCT на реальных изображениях. То, что «Именно DCT чаще всего встречается в практических приложениях благодаря свойству «уплотнения энергии»» написано везде. Это свойство означает, что максимальное количество информации заключено в первых коэффициентах. А почему? Нетрудно провести исследование: вооружаемся кучей разных картинок, различными известными базисами и начинаем считать среднеквадратичное отклонение от реального изображения для разного количества коэффициентов. Нашел небольшое исследование в статье (использованные изображения ) по этой методике. В ней приведены графики зависимости сохраненной энергии от количества первых коэффициентов разложений по разным базисам. Если вы просмотрели графики, то убедились, что DCT стабильно занимает почетное… эмм… 3-место. Как же так? Что еще за KLT преобразование? Я восхвалял DCT, а тут…

KLT

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

DFT

DFT (Discrete Fourier Transform) - дискретное преобразование Фурье. Под этим названием иногда упоминается не только конкретная трансформация, но и весь класс дискретных трансформаций (DCT, DST...). Посмотрим на формулу DFT:

Как вы догадываетесь, это ортогональное преобразование с каким-то комплексным базисом. Так как подобная комплексная форма встречается чуть чаще, чем всегда, то имеет смысл изучить ее вывод.
Может сложится впечатление, что любой чистый гармонический сигнал (с целой частотой) при DCT разложении будет давать только один ненулевой коэффициент, соответствующий этой гармонике. Это не так, поскольку помимо частоты, важна и фаза этого сигнала. Например, разложение синуса по косинусам (подобным образом и в дискретном разложении) будет таким:

Вот вам и чистая гармоника. Она наплодила кучу других. На анимации показаны коэффициенты DCT синусоиды в разных фазах.


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

Простое тригонометрическое тождество дает важный результат: сдвиг по фазе заменяется суммой синуса и косинуса, взятых с коэффициентами cos(b) и sin(b). Значит, можно раскладывать функции на сумму синусов и косинусов (без всяких фаз). Это распространенная тригонометрическая форма. Однако, гораздо чаще используется комплексная. Для ее получения нужно воспользоваться формулой Эйлера . Просто подставим производные формулы для синуса и косинуса, получим:


Теперь небольшая замена. Верхнее подчеркивание - сопряженное число.

Получим итоговое равенство:

c - комплексный коэффициент, действительная часть которого равна косинусному коэффициенту, а мнимая - синусному. А множество точек (cos(b), sin(b)) является окружностью. В такой записи каждая гармоника входит в разложение и с положительной и с отрицательной частотой. Поэтому в различных формулах Фурье-анализа обычно происходит суммирование или интегрирование от минус до плюс бесконечности. Производить вычисления часто бывает удобнее именно в такой комплексной форме.
Преобразование раскладывает сигнал на гармоники с частотами от одного до N колебаний на области сигнала. Но частота дискретизации составляет N на области сигнала. А по теореме Котельникова (aka теорема Найквиста - Шеннона) частота дискретизации должна по крайней мере в два раза превышать частоту сигнала. Если это не так, то получается эффект появления сигнала с ложной частотой:

Пунктирной линий показан неверно восстановленный сигнал. С таким явлением вы часто сталкивались в жизни. Например, забавное движение колес автомобиля на видео, или муаровый эффект.
Это приводит к тому, что вторая половина из N комплексных амплитуд как будто состоит из других частот. Эти ложные гармоники второй половины являются зеркальным отображением первой и не несут дополнительной информации. Таким образом, у нас остается N/2 косинусов и N/2 синусов (образующих ортогональный базис).
Ладно, базис есть. Его составляющие - гармоники с целым числом колебаний на области сигнала, а значит, крайние значения гармоник равны. Точнее почти равны, так как последнее значение берется не совсем с края. Более того - каждая гармоника почти зеркально симметрична относительно своего центра. Все эти явления особенно сильны на низких частотах, которые нам и важны при кодировании. Это плохо еще и тем, что на сжатом изображении будут заметны границы блоков. Проиллюстрирую DFT-базис с N=8. Первые 2 ряда - косинусные составляющие, последние - синусные:

Обратите внимание на появление дублей составляющих при повышении частоты.

Можете мысленно подумать, как мог бы быть разложен сигнал, значения которого плавно уменьшаются с максимального значения в начале до минимального в конце. Более-менее адекватное приближение смогли бы сделать лишь гармоники ближе к концу, что для нас не очень здорово. На рисунке слева приближение несимметричного сигнала. Справа - симметричного:


С первым дела крайне плохи.
Так может быть сделать как в DCT - уменьшить частоты в 2 или другое количество раз, чтобы количество некоторых колебаний было дробным и границы находились в разных фазах? Тогда составляющие будут неортогональны. И ничего тут не поделать.

DST

Что если вместо косинусов в DCT использовать синусы? Мы получим Discrete Sine Transform (DST). Но для нашей задачи все они неинтересны, так как и целые и половинки периодов синусов близки к нулю на границах. То есть мы получим примерно такое же неподходящее разложение, как и у DFT.

Возвращаясь к DCT

Как у него дела на границах? Хорошо. Есть противофазы и нет нулей.

Все остальное

Не-Фурье преобразования. Не буду описывать.
WHT - матрица состоит только из ступенчатых составляющих со значениями -1 и 1.
Haar - по совместительству ортогональное вейвлет-преобразование.
Они уступают DCT, но легче для вычислений.

Итак, вас посетила мысль придумать свое преобразование. Помните вот что:

1. Базис должен быть ортогонален.
2. С фиксированным базисом вы не сможете превзойти KLT по качеству сжатия. Между тем, на реальных фотографиях DCT почти не уступает.
3. На примере DFT и DST нужно помнить про границы.
4. И помнить, что у DCT есть еще хорошее преимущество - вблизи границ составляющих их производные равны нулю, а значит, переход между соседними блоками будет довольно плавным.
5. У преобразований Фурье существуют быстрые алгоритмы со сложностью O(N*logN), в отличие от вычисления в лоб: O(N 2).

Будет непросто, правда? Впрочем, для некоторых типов изображений можно подобрать лучший базис, чем у DCT.

Двумерные преобразования

Сейчас попробуем провести такой эксперимент. Возьмем, для примера, кусочек изображения.

Его 3D график:

Пройдемся DCT(N=32) по каждой строке:

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

Коэффициент (0,0) получился слишком большим, поэтому на графике он уменьшен в 4 раза.
Итак, что получилось?
Левый верхний угол - самые значащие коэффициенты разложения самых значащих коэффициентов.
Левый нижний угол - самые незначащие коэффициенты разложения самых значащих коэффициентов.
Правый верхний угол - самые значащие коэффициенты разложения самых незначащих коэффициентов.
Правый нижний угол - самые незначащие коэффициенты разложения самых незначащих коэффициентов.
Понятно, что значимость коэффициентов уменьшается, если двигаться по диагонали из левого верхнего угла в правый нижний. А какой важнее: (0, 7) или (7, 0)? Что они вообще означают?
Сначала по строкам: A 0 = (EX T) T = XE T (транспонировали, так как формула A=EX для столбцов), затем по столбцам: A=EA 0 = EXE T . Если аккуратно посчитать, то получится формула:

Таким образом, если вектор раскладывается на синусоиды, то матрица на функции вида cos(ax)*cos(by). Каждый блок 8x8 в JPEG представляется в виде суммы 64-х функций вида:


В Википедии и других источниках такие функции представлены в более удобной форме:

Поэтому коэффициенты (0, 7) или (7, 0) одинаково полезны.
Впрочем, фактически это обычное одномерное разложение на 64 64-мерных базиса. Все вышесказанное применимо не только к DCT, но и к любому ортогональному разложению. Действуя по аналогии, в общем случае получаем N-мерное ортогональное преобразование.
А вот уже 2-мерное преобразование енота (DCT 256x256). Опять же с обнуленными значениями. Числа - количество необнуленных коэффициентов из всех (оставлялись самые значимые значения, находящиеся в треугольной области в левом верхнем углу).

Запомните, что коэффициент (0, 0) называется DC, остальные 63 - AC.

Выбор размера блока

Товарищ спрашивает : почему в JPEG используется разбиение именно 8x8. Из заплюсованного ответа:

The DCT treats the block as if it were periodic and has to reconstruct the resulting jump at the boundaries. If you take 64x64 blocks, you"ll most likely have a huge jump at the boundaries, and you"ll need lots of high-frequency components to reconstruct that to a satisfactory precision

Мол, DCT работает хорошо только на периодических функциях, и если вы возьмете большой размер, то, скорее всего, получите гигантский скачок на границах блока и понадобится много высокочастотных компонентов для его покрытия. Это неверно! Такое объяснение очень похоже на DFT, но не на DCT, так как оно отлично покрывает такие скачки уже первыми составляющими.
На той же странице приводится ответ из MPEG FAQ, с основными аргументами против больших блоков:

• Мало прибыли при разбиении на большие блоки.
• Увеличение вычислительной сложности.
• Высокая вероятность большого количества резких границ в одном блоке, что вызовет эффект Гиббса.

Предлагаю самостоятельно исследовать это. Начнем с первого .


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

Большие блоки не показаны, так как визуально почти неотличимы от 32x32. Теперь посмотрим на абсолютную разность с исходным изображением (усиленную в 2 раза, иначе ничего толком не видно):

8x8 дает лучший результат, чем 4x4. Дальнейшее увеличение размера уже не дает хорошо заметного преимущества. Хотя я всерьез бы задумался над 16x16, вместо 8x8: увеличение сложности на 33% (о сложности в следующем абзаце), дает небольшое, но все-таки видимое улучшение при одинаковом количестве коэффициентов. Однако, выбор 8x8 выглядит достаточно обоснованным и, возможно, является золотой серединой. JPEG был опубликован в 1991. Думаю, что такое сжатие являлось очень сложным для процессоров того времени.

Второй аргумент. Нужно помнить, что при увеличении размера блока потребуется больше вычислений. Давайте оценим насколько. Сложность преобразования в лоб, как мы уже вполне умеем: O(N 2), так как каждый коэффициент состоит из N слагаемых. Но на практике используется эффективный алгоритм быстрого преобразования Фурье (БПФ, Fast Fourier Transform, FFT). Его описание выходит за рамки статьи. Его сложность: O(N*logN). Для двумерного разложения нужно воспользоваться им дважды по N раз. Таким образом, сложность 2D DCT - O(N 2 logN). Теперь сравним сложности вычисления изображения одним блоком и несколькими маленькими:

• Одним блоком (kN)x(kN): O((kN) 2 log(kN)) = O(k 2 N 2 log(kN))
• k*k блоками N*N: O(k 2 N 2 logN)

Это значит, что, например, вычисление при разбиении на 64x64 в два раза сложнее, чем на 8x8.

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


Хотя искажения блоков 16x16 простираются дальше, чем у 8x8, но надпись более плавная. Поэтому меня убедили только первые два аргумента. Но мне что-то больше нравится разделение на 16x16.

Квантование

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


Стандартная матрица соответствует 50% качеству в FastStone и IrfanView. Такая таблица была выбрана с точки зрения баланса качества и степени сжатия. Думаю, что значение для DC-коэффициента больше соседних из-за того, что DCT ненормализовано и первое значение получается больше, чем следовало бы. Высокочастотные коэффициенты огрубляются сильнее из-за их меньшей важности. Думаю, сейчас такие матрицы используются редко, так как ухудшение качества хорошо заметно. Никто не запрещает использовать свою таблицу (со значениями от 1 до 255)
При декодировании происходит обратный процесс - квантованные коэффициенты почленно умножаются на значения матрицы квантования. Но так как мы округляли значения, то не сможем точно восстановить исходные коэффициенты Фурье. Чем больше число квантования, тем больше погрешность. Таким образом, восстановленный коэффициент является лишь ближайшим кратным.
Еще пример:

И на десерт, рассмотрим качество 5% (при кодировании в Fast Stone).


При восстановлении этого блока мы получим только усредненное значение плюс вертикальный градиент (из-за сохранившегося значения -1). Зато для него хранится всего два значения: 7 и -1. C другими блоками ситуация не лучше, вот восстановленная картинка:

Кстати, насчет 100% качества. Как вы догадываетесь, в этом случае матрица квантования состоит полностью из единиц, то есть квантования не происходит. Однако, из-за округления коэффициентов до целого, мы не можем в точности восстановить исходную картинку. Например, енот сохранил 96% пикселей точно, а 4% отличались на 1/256. Разумеется, такие «искажения» невозможно заметить визуально.
А можете посмотреть матрицы квантования различных фотоаппаратов.

Кодирование

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

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

• d9rg3
• wfr43gt
• wfr43gt
• d9rg3
• d9rg3
• d9rg3
• wfr43gt
• d9rg3

Как бы вы облегчили свою задачу? Особого желания мучительно диктовать все эти слова у вас нет. Но их всего два и они повторяются. Поэтому вы просто как-нибудь диктуете первые два слова и договариваетесь, что далее «d9rg3» будете называть первым словом, а «wfr43gt» - вторым. Тогда достаточно будет продиктовать: 1, 2, 2, 1, 1, 1, 2, 1.

Подобные слова мы будем обозначать как A, B, C..., и называть их символами. Причем под символом может скрываться что угодно: буква алфавита, слово или бегемот в зоопарке. Главное, что одинаковым символам соответствуют одинаковые понятия, а разным - разные. Так как наша задача - эффективное кодирование (сжатие), то будем работать с битами, так как это наименьшие единицы представления информации. Поэтому, запишем список как ABBAAABA. Вместо «первое слово» и «второе слово» можно использовать биты 0 и 1. Тогда ABBAAABA закодируется как 01100010 (8 бит = 1 байт).

Пример 1
Закодировать ABC.
3-м разным символам (A, B, C) никак нельзя сопоставить 2 возможных значений бита (0 и 1). А раз так, то можно использовать по 2 бита на символ. Например:

• A: 00
• B: 01
• C: 10

Последовательность битов, сопоставленная символу, будем называть кодом. ABC будет кодироваться так: 000110.

Пример 2
Закодировать AAAAAABC.
Использовать по 2 бита на символ A кажется немного расточительным. Что, если попробовать так:

• C: 00

Закодированная последовательность: 000000100.
Очевидно, этот вариант не подходит, так как непонятно, как декодировать первые два бита этой последовательности: как AA или как C? Использовать какой-нибудь разделитель между кодами очень расточительно, будем думать как по-другому обойти это препятствие. Итак, неудача произошла из-за того, что код C начинается с кода A. Но мы полны решимости кодировать A одним битом, пусть даже B и С будут по два. Исходя из такого пожелания, A дадим код 0. Тогда коды B и C не могут начинаться на 0. Но могут на 1:

• B: 10
• C: 11

Последовательность закодируется так: 0000001011. Попробуйте мысленно декодировать ее. Вы сможете сделать это только одним способом.
Мы выработали два требования к кодированию:

1. Чем больше вес символа, тем короче должен быть его код. И наоборот.
2. Для однозначного декодирования код символа не может начинаться с кода любого другого символа.

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

Пример 3
Рассмотрим общий случай для 4-х символов с любыми весами.

• A: pa
• B: pb
• C: pc
• D: pd

Без потери общности, положим pa ≥ pb ≥ pc ≥ pd. Существуют всего два принципиально разных по длинам кодов варианта:


Какое из них предпочтительнее? Для этого нужно вычислить получаемые длины закодированных сообщений:
W1 = 2*pa + 2*pb + 2*pc + 2*pd
W2 = pa + 2*pb + 3*pc + 3*pd
Если W1 меньше W2 (W1-W2<0), то лучше использовать первый вариант:
W1-W2 = pa - (pc+pd) < 0 => pa < pc+pd.
Если C и D вместе встречаются чаще других, то их общая вершина получает самый короткий код из одного бита. В противном случае, один бит достается символу A. Значит, объединение символов ведет себя как самостоятельный символ и имеет вес равный сумме входящих символов.
Вообще, если p - вес символа представленный долей его вхождения (от 0 до 1), то лучшая длина кода s=-log 2 p.
Рассмотрим это на простом случае (его легко представить в виде дерева). Итак, нужно закодировать 2 s символов с равными весами (1/2 s). Из-за равенства весов длины кодов будут одинаковыми. Каждому символу потребуется s бит. Значит, если вес символа 1/2 s , то его длина s. Если вес заменить заменить на p, то получим длину кода s=-log 2 p . Значит, если один символ встречается в два раза реже другого, то длина его кода будет на бит длиннее. Впрочем такой вывод легко сделать, если вспомнить, что добавление одного бита позволяет в два раза увеличить количество возможных вариантов.
И еще одно наблюдение - два символа с наименьшими весами всегда имеют наибольшие, но равные длины кодов. Более того, их биты, кроме последнего, совпадают. Если бы это было неверно, то, по крайней мере, один код можно было бы укоротить на 1 бит, не нарушая префиксности. Значит, два символа с наименьшими весами в кодовом дереве имеют общего родителя уровнем выше. Вы можете видеть это на примере С и D выше.

Пример 4
Попробуем решить следующий пример, по выводам, полученным в предыдущем примере.

1. Все символы сортируются в порядке убывания весов.
2. Два последних символа объединяются в группу. Этой группе присваивается вес, равный сумме весов этих элементов. Эта группа участвует в алгоритме наравне с символами и другими группами.

Шаги повторяются, пока не останется только одна группа. В каждой группе одному символу (или подгруппе) присваивается бит 0, а другому бит 1.
Этот алгоритм называется кодированием Хаффмана.
На иллюстрации приведен пример с 5-ю символами (A: 8, B: 6, C: 5, D: 4, E: 3). Справа указан вес символа (или группы).

Кодируем коэффициенты

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

Обратите внимание - шкала логарифмическая! Сможете объяснить причину появления скопления значений превышающих 200? Это DC-коэффициенты. Так как они сильно отличаются от остальных, то неудивительно, что их кодируют отдельно. Вот только DC:

Обратите внимание, что форма графика напоминает форму графиков из самих ранних экспериментов деления на пары и тройки пикселей
Вообще, значения DC-коэффициентов могут меняться от 0 до 2047 (точнее от -1024 до 1023, так как в JPEG производится вычитание 128 из всех исходных значений, что соответствует вычитанию 1024 из DC) и распределяться довольно равномерно с небольшими пиками. Поэтому кодирование Хаффмана здесь не очень-то поможет. А еще представьте, каким большим будет дерево кодирования! И во время декодирования придется искать в нем значения. Это очень затратно. Думаем дальше.
DC-коэффициент - усредненное значение блока 8x8. Представим градиентный переход (пусть не идеальный), который часто встречается в фотографиях. Сами DC значения будут разными, но они будут представлять арифметическую прогрессию. Значит, их разность будет более-менее постоянна. Построим гистограмму разностей:

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

То есть положительные значения прямо кодируются их двоичным представлением, а отрицательные - так же, но с заменой ведущей 1 на 0. Осталось решить, как кодировать длины. Так как их 12 возможных значений, то можно использовать 4 бита для хранения длины. Но вот тут-то как раз лучше использовать кодирование Хаффмана.

Значений с длинами 4 и 6 больше всего, поэтому им достались самые короткие коды (00 и 01).

Может возникнуть вопрос: почему на примере у значения 9 код 1111110, а не 1111111? Ведь можно смело поднять «9» на уровень выше, рядом с «0»? Дело в том, что в JPEG нельзя использовать код, состоящий только из единиц - такой код зарезервирован.
Есть еще одна особенность. Коды, полученные описанным алгоритмом Хаффмана могут не совпасть по битам с кодами в JPEG, хотя их длины будут одинаковыми. Используя алгоритм Хаффмана, получают длины кодов, а сами коды генерируются (алгоритм прост - начинают с коротких кодов и добавляют их по очереди в дерево как можно левее, сохраняя свойство префиксности). Например, для дерева выше хранится список: 0,2,3,1,1,1,1,1. И, разумеется, хранится список значений: 4,6,3,5,7,2,8,1,0,9. При декодировании коды генерируются таким же способом.

Теперь порядок. Мы разобрались как хранятся DC:
[код Хаффмана для длины DC diff (в битах)]
где DC diff = DC текущее - DC предыдущее

Смотрим AC:

Так как график очень похож на график для разностей DC, то принцип тот же: [код Хаффмана для длины AC (в битах)]. Но не совсем! Так как на графике шкала логарифмическая, то не сразу заметно, что нулевых значений примерно в 10 раз больше, чем значения 2 - следующего по частоте. Это понятно - не все пережили квантование. Вернемся к матрице значений, полученной на этапе квантования (используя матрицу квантования FastStone, 90%).

Так как встречается много групп подряд идущих нулей, то появляется идея - записывать только количество нулей в группе. Такой алгоритм сжатия называется RLE (Run-length encoding, кодирование повторами). Осталось выяснить направление обхода «подряд идущих» - кто за кем? Выписать слева направо и сверху вниз - не очень эффективно, так как ненулевые коэффициенты концентрируются около левого верхнего угла, а чем ближе к правому нижнему - тем больше нулей.

Поэтому, в JPEG используется порядок, называемый «Zig-zag», он показан на левом рисунке. Такой способ хорошо выделяет группы нулей. На правом рисунке - альтернативный способ обхода, не относящийся к JPEG, зато с любопытным названием (пруф). Он может использоваться в MPEG при сжатии видео с чересстрочной разверткой. Выбор алгоритма обхода не влияет на качество изображения, но может увеличить количество кодируемых групп нулей, что в итоге может отразиться на размере файла.
Модифицируем нашу запись. Для каждого ненулевого AC - коэффициента:
[Количество нулей перед AC][код Хаффмана для длины AC (в битах)]
Думаю, что вы сразу скажете - количество нулей тоже отлично закодируется Хаффманом! Это очень близкий и неплохой ответ. Но можно немного оптимизировать. Представьте, что имеем некоторый коэффициент AC, перед которым было 7 нулей (разумеется, если выписывать в зигзагообразном порядке). Эти нули - дух значений, которые не выдержали квантования. Скорее всего, наш коэффициент тоже сильно потрепало и он стал маленьким, а, значит, его длина - короткой. Значит, количество нулей перед AC и длина AC - зависимые величины. Поэтому записывают так:
[код Хаффмана для (Количество нулей перед AC, длина AC (в битах)]
Алгоритм кодирования остается тем же: те пары (количество нулей перед AC, длина AC), которые встречаются часто, получат короткие коды и наоборот.

Строим гистограмму зависимости количества по этим парам и дерево Хаффмана.


Длинный «горный хребет» подтверждает наше предположение.

Особенности реализации в JPEG:
Такая пара занимает 1 байт: 4 бита на количество нулей и 4 бита на длину AC. 4 бита - это значения от 0 до 15. Для длины AC хватит с избытком, но ведь нулей может быть больше 15? Тогда используется больше пар. Например, для 20 нулей: (15, 0)(5, AC). То есть, 16-й ноль кодируется как ненулевой коэффициент. Так как ближе к концу блока всегда полно нулей, то после последнего ненулевого коэффициента используется пара (0,0). Если она встретится при декодировании, значит оставшиеся значения равны 0.

Выяснили, что каждый блок закодирован хранится в файле так:
[код Хаффмана для длины DC diff ]
[код Хаффмана для (количество нулей перед AC 1 , длина AC 1 ]
…
[код Хаффмана для (количество нулей перед AC n , длина AC n ]
Где AC i - ненулевые AC коэффициенты.

Цветное изображение

Способ представления цветного изображения зависит от выбранной цветовой модели. Простое решение - использовать RGB и кодировать каждый цветовой канал изображения по отдельности. Тогда кодирование не будет отличаться от кодирования серого изображения, только работы в 3 раза больше. Но сжатие изображения можно увеличить, если вспомнить, что глаз более чувствительнее к изменению яркости, чем цвета. Это значит, что цвет можно хранить с бОльшими потерями, чем яркость. У RGB нет отдельного канала яркости. Она зависит от суммы значений каждого канала. Поэтому, RGB-куб (это представление всех возможных значений) просто «ставят» на диагональ - чем выше, тем ярче. Но на этом не ограничиваются - куб немного поджимают с боков, и получается скорее параллелепипед, но это лишь для учета особенностей глаза. Например, он более восприимчив к зеленому, чем синему. Так появилась модель YCbCr.

(Изображение с Intel.com)
Y - компонента яркости, Cb и Cr являются синей и красной цветоразностными компонентами. Поэтому, если хотят сильнее сжать изображение, то RGB переводят в YCbCr, и каналы Cb и Cr прореживают. То есть разбивают на небольшие блоки, например 2x2, 4x2, 1x2, и усредняют все значения одного блока. Или, другими словами, уменьшают размер изображения для этого канала в 2 или 4 раза по вертикали и/или горизонтали.

Каждый блок 8x8 кодируется (DCT + Хаффман), и закодированные последовательности записываются в таком порядке:

Любопытно, что спецификация JPEG не ограничивает в выборе модели, то есть реализация кодировщика может как угодно разделить изображение по цветовым компонентам (каналам) и каждый будет сохранен по отдельности. Мне известно об использовании Grayscale (1 канал), YCbCr (3), RGB (3), YCbCrK (4), CMYK (4). Первые три поддерживаются почти всеми, а вот с последними 4-канальными бывают проблемы. FastStone, GIMP поддерживают их корректно, а штатные программы Windows, paint.net корректно извлекают всю информацию, но потом выбрасывают 4 черный канал, поэтому (Antelle сказал, что не выбрасывают, читайте его комментарии) показывают более светлое изображение. Слева - классический YCbCr JPEG, справа CMYK JPEG:



Если они различаются по цветам, или видна только одна картинка, то, скорее всего, у вас IE (любой версии) (UPD. в комментариях говорят «или Safari»). Можете попробовать открыть статью в разных браузерах.

И еще кое-что

В двух словах о дополнительных возможностях.

Progressive mode

Разложим полученные таблицы коэффициентов DCT на сумму таблиц (примерно так (DC, -19, -22, 2, 1) = (DC, 0, 0, 0, 0) + (0, -20, -20, 0, 0) + (0, 1, -2, 2, 1)). Сначала закодируем все первые слагаемые (как мы уже научились: Хаффман и обход зигзагом), затем вторые и т. д. Такой трюк полезен при медленном интернете, так как сперва загружаются только DC коэффициенты, по которым строится грубая картинка c «пикселями» 8x8. Затем округленные AC коэффициенты, позволяющие уточнить рисунок. Затем грубые поправки к ним, затем более точные. Ну и так далее. Коэффициенты округляются, так как на ранних этапах загрузки точность не столь важна, зато округление положительно сказывается на длине кодов, так как для каждого этапа используется своя таблица Хаффмана.

Lossless mode

Сжатие без потерь. DCT нет. Используется предсказание 4-й точки по трем соседним. Ошибки предсказания кодируются Хаффманом. По-моему, используется чуть чаще, чем никогда.

Hierarhical mode

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

Арифметическое кодирование

Алгоритм Хаффмана создает оптимальные коды по весу символов, но это верно только для фиксированного соответствия символов с кодами. Арифметическое не имеет такой жесткой привязки, что позволяет использовать коды как бы с дробным числом бит. Утверждается, что оно уменьшает размер файла в среднем на 10% по сравнению с Хаффманом. Не распространено из-за проблем с патентом, поддерживается не всеми.

Я надеюсь, что теперь вам понятен алгоритм JPEG интуитивно. Спасибо за прочтение!

UPD
vanwin предложил указать использованное ПО. С удовольствием сообщаю, что все доступны и бесплатны:

• Python + NumPy + Matplotlib + PIL(Pillow) . Основной инструмент. Нашелся по выдаче «Matlab free alternative». Рекомендую! Даже если вам не знаком Python, то уже через пару часов научитесь производить расчеты и строить красивые графики.
• JpegSnoop . Показывает подробную информацию о jpeg-файле.
• yEd . Редактор графов.
• Inkscape . Делал в нем иллюстрации, такие как пример алгоритма Хаффмана. Прочитал несколько уроков, оказалось очень здорово.
• Daum Equation Editor . Искал визуальный редактор формул, так как с Latex-ом не очень дружу. Daum Equation - плагин к Хрому, мне показался очень удобен. Помимо мышкотыкания, можно редактировать Latex.
• FastStone . Думаю, его представлять не надо.
• PicPick . Бесплатная альтернатива SnagIt. Сидит в трее, скриншотит что скажут куда скажут. Плюс всякие плюшки, типа линейки, пипетки, угломера и пр.

Теги: Добавить метки

Голосование: 22, 4

Введение

На сегодняшний день качественная, высокопроизводительная компьютерная графика является одной из важнейших задач разработчиков программного обеспечения. Огромные средства вкладываются в разработку эффективного оборудования для различных графических и мультимедийных систем. В последние годы появились компьютеры способные в реальном времени воспроизводить сложнейшие визуальные образы, давно превзошедшие по качеству телевизионные или полиграфические. Это способствовало появлению огромного количества программ, использующих эти возможности: компьютерные игры, видео-приложения, 3d-анимация и т.д. Но у всех этих программ есть одна отличительная особенность: графические данные, с которыми они работают, занимают очень много места.

В то время уже были достаточно распространены среди пользователей персональных компьютеров такие графические форматы, как BMP, PCX, GIF. Но даже уменьшение объема графической информации в два раза оказалось недостаточным для современных графических систем. В связи с этим с конца 80х годов две крупнейшие в мире организации стандартов CCITT и ISO объединили свои усилия для выработки единого стандарта формата графического файла, сжатого с потерями. Новый стандарт получил свое название JPEG по имени группы разработчиков Joint Photographic Experts Group.

Сделаем небольшое замечание: JPEG прежде всего является методом сжатия. Его нельзя рассматривать в качестве полноценного стандарта представления изображений. Поэтому в нем не задаются такие специфические параметры изображения, как геометрический размер пикселя, пространство цветов или чередование битовых строк. То же можно сказать и о JPEG2000, и о JPEG-LS — это методы сжатия, а не полноценные стандарты.

1. JPEG

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

Рис. 1.

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

Если изображение содержит более одной компоненты, то они кодируются по отдельности. В связи с этим, на данном этапе выполняется перевод графического изображения из его компонентного представления в цветоразностное, яркостное представление (ICT — Irreversible Color Transform). В связи с тем, что человеческий глаз более восприимчив к яркостному сигналу, чем к цветовому, это преобразование позволит добиться больших результатов сжатия при меньших визуальных потерях. Далее будет рассматриваться кодирование одной отдельной компоненты.

Рис. 2.

Рис. 3.

Помимо ICT преобразования, на данном этапе исходное изображение разбивается на малые квадратные блоки и выполняется сдвиг основания значений цвета относительно нуля для корректного пространственного представления изображения: -> [-2 p-1 , 2 p-1 - 1] . Эти шаги важны для эффективной работы кодера на следующем этапе.

1.2. ДКП

Являясь ключевым шагом алгоритма сжатия, дискретное косинусное преобразование (далее ДКП) представляет собой разновидность преобразования Фурье и, также как и последнее, имеет обратное преобразование (ОДКП). Если рассматривать изображение как совокупность пространственных волн, где оси X и Y соответствуют ширине и высоте картинки, а по оси Z откладываются значения цвета соответствующих пикселей, то можно перейти от пространственного представления картинки к ее спектральному представлению и обратно. ДКП преобразует матрицу пикселей размера N x N в матрицу частотных коэффициентов соответствующего размера.

Рис. 4.

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

Из формул (рис. 4) видно, что вычисление одного элемента результирующей матрицы требует O(N 2) времени, поэтому почти невозможно выполнить преобразование всей матрицы целиком. Группа разработчиков JPEG предложила оптимальный вариант решения этой проблемы: разбивать исходную матрицу на квадраты стандартного размера 8x8 и выполнять преобразование каждого из них. Использование блоков большего размера позволит улучшить качество сжатия, но не до бесконечности, так как слишком мала вероятность того, что сильно отдаленные точки похожи друг на друга.

Стоит отметить, что в ходе вычислений используется только 32 заранее вычисленных значения косинусов, что позволяет заметно увеличить скорость работы преобразования. Это уже, несомненно, приводит к частичной потери информации, но ее объемы относительно несущественны.

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

1.3. Округление

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

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

3	5	7	9	11	13	15	17
5	7	9	11	13	15	17	19
7	9	11	13	15	17	19	21
9	11	13	15	17	19	21	23
11	13	15	17	19	21	23	25
13	15	17	19	21	23	25	27
15	17	19	21	23	25	27	29
17	19	21	23	25	27	29	31

Пример матрицы округления с фактором качества равным 2.

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

1.4. Сжатие

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

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

Рис. 5.

Наконец, на третьем и заключительном шаге полученный результат сжимается, как обычные данные с помощью алгоритма Хаффмана или арифметического кодирования в зависимости от реализации. Этот этап носит название «кодирование энтропии» (в терминологии JPEG).

1.5. Декодирование

Так как ДКП является преобразованием Фурье, к нему существует обратное дискретное косинусное преобразование (ОДКП). Алгоритм декодирования повторяет алгоритм кодирования в обратном порядке.

2. JPEG2000

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

• Устранение неэффективного сжатия в области низких частот . Существующие алгоритмы неплохо справлялись со сжатием среднечастотных и высокочастотных областей, но в области низких частот они показывали плохие результаты.
• Сжатие с потерями и без потерь . На момент разработки не существовало стандарта, позволяющего сжимать с потерями и без потерь в едином сжимающем потоке.
• Обработка больших изображений . Существующие алгоритмы не позволяли эффективно сжимать изображения размером более 64Kx64K без разбиения на тайлы.
• Единая структура алгоритма сжатия . Текущая реализация JPEG поддерживала 44 модификации, большая часть которых была специфичной для некоторых приложений и не поддерживалась большей частью декодеров.
• Помехоустойчивость . Во время разработки JPEG сетевые технологии не были еще достаточно развиты, и проектировщики JPEG не задумывались над помехоустойчивостью при передаче изображений по небезопасным каналам и возможностью восстановления изображения в случае его повреждения в результате передачи.
• Компьютерно-сгенерированные изображения . Исходные алгоритмы неплохо работали на цифровых фотографиях и изображениях, полученных с помощью цифровой фотокамеры или сканера, но неэффективно обрабатывали изображения, созданные на компьютере, например, с помощью графических редакторов.
• Сложные документы . JPEG показывал очень плохие результаты при обработке сложных двумерных изображений (в частности изображений текста).

На следующей диаграмме представлены основные шаги работы кодера JPEG2000.

Рис. 6.

Рис. 7.

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

Рис. 8.

2.2. ДВП

JPEG2000 использует дискретное вейвлетное преобразование (Discrete Wavelet Transformation), для разбиения изображения на высокочастотные и низкочастотные области. ДВП обрабатывает каждую строку и столбец исходного изображения с помощью частотного фильтра.

Рис. 9.

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

• LL – низкие частоты по строкам и столбцам
• HL – высокие частоты по строкам и низкие по столбцам
• LH – низкие частоты по строкам и высокие по столбцам
• HH – высокие частоты по строкам и столбцам

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

Рис. 10.

Рис. 11.

2.3. Округление

Для округления коэффициентов ДВП используется постоянный квантователь с мертвой зоной. (рис. 14) Для каждого фрагмента используется постоянное значение шага округления для всех коэффициентов этого фрагмента. Формула вычисления округленных значений представлена на рисунке 12. Здесь y - исходное значение коэффициента, sign(y) определяет знак коэффициента, а Δb - значение шага округления. Мертвая зона квантователя - это интервал диапазоном 2Δb около нуля, она дает большее количество нулей на выходе.

2.4. Кодирование

Кодирование полученных округленных коэффициентов выполняется поблочно. По стандарту JPEG2000 непосредственно перед кодированием фрагменты разбиваются на достаточно малые блоки (например, размером 32x32 или 64x64) так, чтобы все блоки одного фрагмента были одинакового размера. Разбиение на блоки выполняется для того, чтобы осуществить более гибкую организацию сжатой информации для повышения помехоустойчивости и так далее.

Рис. 16.

В JPEG2000 каждый блок кодируется по отдельности. Алгоритм кодирования обходит матрицу коэффициентов округления каждого блока полосами, как показано на рисунке 17. Блоки разбиваются на блоки с номинальной высотой 4. Далее полосы сканируются сверху вниз, а колонки в каждой полосе обходятся слева направо.

Рис. 17.

В процессе кодирования коэффициенты в блоке виртуально представляются в виде битовых плоскостей. Одну из таких плоскостей составляют знаки коэффициентов; остальные плоскости соответствуют различным разрядам величин коэффициентов (положение бита в плоскости соответствует положению коэффициента в блоке). Кодирование осуществляется по плоскостям: сначала кодируется плоскость, соответствующая старшему разряду коэффициентов, затем следующая по убыванию, и т.д. Может случиться так, что N наиболее приоритетных битовых плоскостей (НПБ-плоскостей), не будут содержать единиц. В этом случае НПБ-плоскостью становится первая по порядку плоскость, содержащая хотя бы одну единицу. Предшествующие ей пустые плоскости опускаются при кодировании, а информация о их количестве заносится в заголовок блока.

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

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

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

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

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

2.5. Организация данных

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

Рис. 20.

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

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

Достижение высокого качества сжатия, безусловно, было одной из главных задач при создании стандарта, и здесь разработчики добились явного прогресса. Стандарт JPEG2000 превосходит по эффективности стандарт JPEG примерно в 2 раза при сжатии с потерями и на 5-20% при сжатии без потерь. Конечно, эффективность при сжатии без потерь в данном случае оказывается не такой высокой, как, скажем, у стандарта JPEG-LS, однако она вполне приемлема. Что же касается эффективности сжатия с потерями, здесь стандарт позволяет получать результаты, близкие к наилучшим на сегодняшний день результатам для подобного рода методов.

3. JPEG-LS

Формат JPEG-LS был основан на формате LOCO-I (Low Complexity Lossless Compression for Images). Алгоритм сжатия без потерь LOCO-I, принятый за основу при разработке стандарта JPEG-LS, впервые предусматривал не только lossless, но и near lossless режим (сжатие с ограниченными, задаваемыми пользователем потерями). В отличие от JPEG2000 lossless mode, JPEG-LS получился по-настоящему удачным: при большей эффективности сжатия новый стандарт обеспечивает высокую скорость компрессии/декомпрессии и не слишком требователен к ресурсам компьютера.

Важно понимать, что формат JPEG-LS:

• не является расширением или модификацией метода JPEG;
• не использует ни DCT (ДКП), ни арифметическое кодирование;
• использует слабое квантование только в моде «почти без потерь»

3.1. Введение основных понятий и принципов работы

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

Кодер (Encoder) «отвечает» за процесс кодирования, а именно: получает на вход исходное изображение в цифровом формате и все необходимые параметры, определенные стандартом, и с помощью специального набора процедур создает набор данных, содержащих сжатое изображение Декодер (Decoder) «отвечает» за процесс декодирования и преобразование фрагментов, а именно: получая на вход данные со сжатым изображением и все необходимые параметры, выводит реконструированное изображение

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

Рис. 21.

Немного информации об исходном изображении : как ниже показано на схеме (рис. 22), исходное изображение может состоять из Nf компонент. Каждая компонента Ci содержит двумерный массив пикселей (samples) из x i столбцов и y i строк. Размеры компонент зависят от двух параметров: X и Y, где X - максимум среди x i значений, а Y - максимум среди y i значений всех компонент. (В стандарте JPEG-LS целая глава посвящена отличиям в работе с мультикомпонентными изображениями по сравнению с однокомпонентными, однако в этой статье мы остановимся лишь на работе однокомпонентными изображениями).

Рис. 22.

На рисунке отмечена ориентация каждой компоненты: top (верх), bottom (низ), left (лево), и right (право). Порядок, в котором пиксели подаются на обработку процедурам кодирования, определен так: left-to-right (слева направо) и top-to-bottom (сверху вниз) по компоненте.

Для прогнозирования текущего пикселя x используются пиксели контекста a, b, c, d. В зависимости от контекста кодер выбирает моду: серийную (run mode) или регулярную (regular mode) . Серийная мода выбирается, если y и z скорее всего будут совпадать, регулярная – в противном случае. Сделаем тут замечание, связанное с наличием опции «почти без потерь» : при включении этой опции серийная мода будет выбрана, если y и z будут почти совпадать в соответствии с параметром допустимого отклонения NEAR.

В случае использования серийной моды мы начинаем просмотр текущей строки с пикселя x и находим наибольшую длину серии пикселей, совпадающих с контекстным пикселем a. Таким образом, в пределах текущей строки мы получаем серию одинаковых пикселей, совпадающих по значению с известным нам пикселем a. Осталось только закодировать длину серии. (Это делается с помощью массива J из 32 элементов). Вы уже могли догадаться, что при включенной опции «почти без потерь» выбирается серия пикселей, близких к a с помощью параметра NEAR.

Теперь рассмотрим наши действия в случае использования регулярной моды. Для вычисления прогноза пикселя x (Px) используются величины пикселей a, b и c. Затем вычисляется так называемая ошибка прогноза (Errval). Ее значение равно разности значения x и Px. Errval корректируется некоторым членом, зависящим от контекста, а затем кодируется с помощью кодов Голомба. Код Голомба зависит от a, b, c, d и Errval этих же пикселей, которые хранятся в специальных массивах A и N. При включении опции «почти без потерь» перед кодированием ошибка прогноза ещё дополнительно квантуется.

Рис. 23.

3.2. Кодер

В основном JPEG-LS используется как метод сжатия информации без потерь, следовательно, восстановленный файл изображения обычно идентичен исходному файлу. В моде почти без потерь исходный и реконструированный образ могут отличаться. Будем обозначать реконструированный пиксель Rp, а исходный пиксель - p.

На стадии инициализации кодер выполняет следующие операции:

• Вычисляются параметры RANGE = floor((MAXVAL + 2 * NEAR) / (2 * NEAR + 1)) + 1, qbpp = ceil(log RANGE), bpp = max(2, ceil(log(MAXVAL + 1))), LIMIT = 2 * (bpp + max(8, bpp)) . (В случае кодирования без потерь NEAR = 0, RANGE = MAXVAL + 1 . Если включена мода «почти без потерь», NEAR > 0). MAXVAL и NEAR - параметры, задаваемые приложением, реализующим алгоритм.
• Инициализируются индексные массивы N , A , B и C . Поясним их предназначение: N используется для хранения частоты вхождения каждого контекста, A — для накопления величины ошибки предсказания, B — для вычисления систематического отклонения, C — для хранения величин корректирования ошибки прогноза.
• Инициализируются переменные для серийной моды (run mode) RUNindex=0 и J = {0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 9,10,11,12,13,14,15} .
• Инициализируются две вспомогательные переменные Nn , Nn=0 для кодирования пикселя прерывания серии.

Введем некоторые функции и переменные, которые будут использоваться в дальнейшем:

GetNextSample() Функция: получает информацию о следующем пикселе исходного изображения и устанавливает соответствующие значения переменных x, a, b, c, d, Ix, Ra, Rb, Rc, Rd . Если считанный пиксель лежит в конце строки, то GetNextSample() устанавливает EOLine = 1 . Во всех остальных случаях EOLine = 0 . Значения Ra, Rb, Rc, Rd наследуют свои значения от вычисленного прежде значения Rx . EOLine Глобальная переменная: устанавливается функцией GetNextSample(): равна 1, если текущий пиксель - последний в строке, равна 0 - в противном случае. AppendToBitStream(a,b) Функция: добавляет неотрицательное число в двоичной форме в поток из закодированных битов, используя b бит. Наиболее значимые биты добавляются первыми. Quantize(a) Функция: используется для квантования ошибки предсказания в режиме «почти без потерь». ComputeRx() Функция: возвращает реконструированное значение Rx для текущего пикселя (использует квантованную «ошибку предсказания»).

Из приведенного изображения (рис. 23) ясно, что немалую роль в кодировании пикселя x играют пиксели a, b, c и d. Попробуем разобраться, что происходит, когда эти пиксели отсутствуют. Так при кодировании верхней строки контекстные пиксели с, b и d отсутствуют, поэтому их значения считаются нулевыми. Если текущий пиксель находится в начале или конце строки, то пиксели a, с или d не определены. В этом случае для a и d используется реконструированное значение Rb пикселя b (или нуль для верхней строки), а для c используется реконструированное значение a при кодировании первого символа предыдущей строки. Таким образом, кодер должен выполнить часть работы декодера, реконструируя некоторые пиксели.

Кодер начинает работу со следующих трех шагов:

После установления контекста Q, кодер прогнозирует пиксель х. Сначала производится вычисление прогноза Рх с помощью так называемого «правила края» (edge-detecting predictor):

if (Rc > = max(Ra, Rb)) Px = min(Ra, Rb);
else {
if (Rc <= min(Ra, Rb))
Px= max(Ra, Rb);
else
Px = Ra + Rb - Rc;
}

Поясним суть «правила края». Для этого рассмотрим случай b < а. При этом условии «правило края» выбирает b в качестве прогноза х во многих случаях, когда вертикальный край изображения находится непосредственно слева от х. Аналогично, пиксель а выбирается в качестве прогноза х во многих случаях, когда горизонтальный край находится непосредственно над х. Если край не обнаруживается, то «правило края» вычисляет прогноз в виде а + b - с, что имеет простую геометрическую интерпретацию. Если каждый пиксель является точкой трехмерного пространства, то прогноз а + b - с помещает Рх на ту же плоскость, что и точки а, b и с.

Следующий шаг — корректировка прогноза (prediction correction from the bias) с помощью числа SIGN (зависящего от трех зонных чисел Qi), корректирующих величин C(Q) (выводимых из систематических смещений, и здесь не обсуждаемых) и параметра MAXVAL.

if (SIGN == +1)
Px = Px + C(Q);
else
Px = Px - C(Q);

If (Px > MAXVAL)
Px = MAXVAL;
else if (Px < 0)
Px = 0;

После того, как прогноз Рх найден, кодер вычисляет ошибку прогноза Errval в виде разности х - Рх, но меняет знак, если величина SIGN отрицательная.

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

if (Errval > 0)
Errval = (Errval + NEAR) / (2 * NEAR + 1);
else
Errval = - (Errval - NEAR) / (2 * NEAR + 1);

При этом используется параметр NEAR, однако имеются некоторые детали, которые здесь не приводятся. Основной шаг реконструкции состоит в нахождении Rx = Px + SIGN * Errval * (2 * NEAR + 1) .

Ошибка прогноза (после возможного квантования) претерпевает сокращение области (modulo reduction). (После этого она готова для главного этапа кодирования).

if (Errval < 0)
Errval = Errval + RANGE;
if (Errval >= ((RANGE + 1) / 2))
Errval = Errval - RANGE;

Коды Голомба (основной параметр был обозначен через b). В JPEG-LS этот параметр обозначается m. Если число m уже выбрано, то код Голомба неотрицательного целого числа n состоит из двух частей: унарного кода целой части числа n/m и двоичного представления n mod m . Этот код является идеальным для целых чисел, имеющих геометрическое распределение (то есть, когда вероятность числа n равна (1 - r) * r n , 0 < r < 1) . Для каждого геометрического распределения найдется такое число m, что код Голомба, построенный по m, имеет наименьшую возможную среднюю длину. Простейший случай, когда m равно степени 2 (m = 2 k), приводит к простым операциям кодирования/декодирования. Код числа n состоит в этом случае из k младших разрядов числа n, перед которыми стоит унарный код числа, составленного из остальных старших разрядов числа n. Этот специальный код Голомба обозначается через G(k) .

Для примера вычислим код G(2) числа n = 19 = 10011 2 . Поскольку k = 2, то m = 4. Начнем с двух младших разрядов, 11 2 , числа n. Они равны 3, что то же самое, что n mod m (3 = 19 mod 4) . Оставшиеся старшие разряды, 100 2 дадут число 4, которое равно целой части n/m (19/4 = 4.75). Унарный код 4 равен 00001, значит код G(2) числа n = 19 равен 00001|11.

На практике всегда имеется конечное число неотрицательных целых чисел. Обозначим наибольшее число через I. Наибольшая длина G(0) равна I + 1, а поскольку I может быть велико, желательно лимитировать размер кода Голомба. Это делается с помощью специального кода Голомба LG(k, glimit) , который зависит от двух параметров k и glimit. Сначала следует сформировать число q из самых старших разрядов числа n. Если q < glimit- - 1 , то код LG(k, glimit) совпадает с кодом LG(k]. В противном случае, приготавливается унарный код числа glimit - ceil(log I) - 1 (то есть, glimit - ceil(log I) - 1 нулей, за которыми стоит единственная 1). Это действует как код esc, после которого стоит двоичный код n - 1 из ceil(log I) бит.

Ошибки прогнозов не обязательно являются положительными числами. Они равны некоторым разностям, которые могут быть нулевыми или отрицательными. Однако коды Голомба были построены для положительных чисел. Поэтому перед кодированием отрицательные значения ошибок следует отразить на множество неотрицательных чисел. Для этого используется отображение:
MErrval =
2 * Errval если Errval >= 0,
2 * |Errval| если Errval < 0.

Это отображение перемежает отрицательные и положительные величины в виде последовательности 0, -1, +1, -2, +2, -3,... .

В нижеприведенной таблице перечислены некоторые ошибки прогноза, отображенные значения и их коды LG(2, 32) при условии, что алфавит имеет размер 256 (то есть, I = 255 и ceil(log I) = 8).

Таблица: ошибки прогнозов, отображения и коды LG(2, 32)

Ошибка прогноза	Отображенное значение	Код
0	0	1 00
-1	1	1 01
1	2	1 10
-2	3	1 11
2	4	01 00
-3	5	01 01
3	6	01 10
-4	7	01 11
4	8	001 00
-5	9	001 01
5	10	001 10
-6	11	001 11
6	12	0001 00
...
50	100	000000000000 000000000001 01100011

Теперь необходимо обсудить выбор параметра k для кодов Голомба. Это делается адаптивно. Параметр k зависит от контекста, и его значение обновляется каждый раз, когда обнаруживается пиксель с этим контекстом. Вычисление k можно выразить простой строкой:
for (k=0; (N[Q]< где А и N - массивы индексов от 0 до 364. В этой формуле используется контекст Q в качестве индекса двух массивов. В начале k инициализируется нулем, а затем совершается цикл. На каждой итерации цикла элемент массива N[Q] сдвигается влево на k разрядов и сравнивается с A[Q]. Если сдвинутое значение N[Q] больше или равно A[Q], то выбирается текущее значение k. В противном случае, k увеличивается на 1, и тест повторяется.

После нахождения числа k, ошибка прогноза Errval преобразуется с помощью в число MErrval, которое кодируется с помощью кода LG(k, LIMIT). Число LIMIT является параметром. Обновление массивов А и N (вместе со вспомогательным массивом B) иллюстрирует следующий фрагмент кода (параметр RESET устанавливается приложением):

B[Q] = B[Q] + Errval * (2 * NEAR + 1);
A[Q] = A[Q] + abs(Errval);
if (N[Q] == RESET) {
A[Q] = A[Q]>>1;
B[Q] = B[Q]>>1;
N[Q] = N[Q]>>1;
}
N[Q] = N[Q] + 1;

Теперь поговорим о просчитывании систематического отклонения прогноза. Значение C[Q], корректирующее прогноз, должно быть обновлено в конце кодирования пикселя x. Для этого необходимы две переменные — B[Q] и N[Q]. N[Q] — это количество вхождений контекста Q с момента инициализации. B[Q] — систематическое отклонение, позволяющее обновлять значение C[Q] как максимум один раз за итерацию. Итак, прогнозирующее значение C[Q] вычисляется в соответствии со следующим кодом:

if (B[Q] <= -N[Q]) {
B[Q] = B[Q] + N[Q];
if (C[Q] > MIN_C)
C[Q] = C[Q] - 1;
if (B[Q] <= -N[Q])
B[Q] = -N[Q] + 1;
}
else if (B[Q] > 0) {
B[Q] = B[Q] - N[Q];
if (C[Q] < MAX_C)
C[Q] = C[Q] + 1;
if (B[Q] > 0)
B[Q] = 0;
}

Константы MIN_C и MAX_C — это минимальное и максимальное возможное значение индексного массива C, равные соответственно -128 и 127.

Кодирование в серийной моде делается иначе. Напомним, что кодер выбирает эту моду, когда обнаруживает последовательные пиксели x, чьи значения Ix совпадают и равны восстановленной величине Ra контекстного пикселя a. Для опции «почти без потерь» пиксели в серии должны иметь значения Ix, которые удовлетворяют неравенству |Ix - Ra| <= NEAR . Серия не должна выходить за пределы текущей строки. Длина серии кодируется (сам пиксель кодировать не нужно, поскольку он равен Ra), и если конец серии находится раньше конца строки, то после ее закодированной длины будет сразу записан код следующего пикселя (который прерывает серию). Две основные задачи кодера в этой моде состоят

1. в отслеживании серии и кодировании ее длины;
2. в кодировании пикселя, прервавшего серию.

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

RUNval = Ra;
RUNcnt = 0;
while (abs(Ix - RUNval) <= NEAR) {
RUNcnt = RUNcnt + 1;
Rx = RUNval;
if (EOLine == 1)
break;
else
GetNextSample();
}

Поясним некоторые введенные величины: RUNcnt — это счетчик повторяющихся пикселей (для серийной моды), а RUNval - текущее значение реконструированного повторяющегося пикселя.

Опишем процесс кодирования серий. Первый фрагмент кода описывает кодирование для сегментов серий длины rm:

while (RUNcnt >= (1< AppendToBitStream(1, 1);
RUNcnt = RUNcnt - (1< if (RUNindex < 31))
RUNindex = RUNindex + 1;
}

Следующий же код иллюстрирует кодирование для сегментов серий длины меньше, чем rm:

if (EOLine == 0) {
AppendToBitStream(0, 1);
AppendToBitStream(RUNcnt, J);
if (RUNindex > 0)) {
RUNindex = RUNindex - 1;
}
else if (RUNcnt > 0)
AppendToBitStream(1, 1);

Здесь кодер использует таблицу J, состоящую из 32 записей, обозначаемых rk. J инициализируется величинами
0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14, 15 .

Для каждого значения rk обозначим rm = 2 rk . Числа rm (их всего 32) называются порядком кода. Первые 4 величины rk имеют rm = 2 0 = 1. Для второй четверки rm = 2 1 = 2, а для следующей четверки rm = 2 2 = 4. Для последнего числа rm = 2 15 = 32768. Кодер выполняет процедуру, описанную , для нахождения длины серии, которая сохраняется в переменной RUNlen . Затем эта переменная кодируется разбиением на слагаемые, величины которых равны последовательным числам rm. Например, если RUNlen=6 , то его представляют в виде 6 = 1 + 1 + 1 + 1 + 2 с помощью первых пяти чисел rm. Оно кодируется с помощью 5 бит. Запись производится инструкцией AppendToBitStream(l,l) . Каждый раз, когда пишется 1, соответствующая величина rm вычитается из RUNlen . Если RUNlen было равно в начале 6, то она последовательно уменьшается до 5, 4, 3, 2 и 0.

Может случиться, что длина RUNlen серии не равна целой сумме чисел rm. Например, RUNlen = 7 . В этом случае в качестве кода записывается пять битов 1, за которыми следует префиксный бит и остаток от RUNlen (в нашем примере это 1), который запишется в файл в виде числа из rk бит (текущее значение rk из нашего примера равно 2). Эта последняя операция выполняется вызовом процедуры AppendToBitStream (RUNcnt, J) . Префиксным битом служит 0, если серия прерывается в строке другим пикселем. Если же серия идет до конца строки, то префиксный бит равен 1.

Вторая основная задача кодера, состоящая в кодировании пикселя прерывания серии, делается аналогично кодированию текущего пикселя. Обсудим детали её реализации.

Рассмотрим ситуацию, когда ход кодирования прерван концом строки пикселей: как будет кодироваться новый пиксель, вызывающий прерывание? Этот вопрос решается кодированием разницы между значением Ix в текущей позиции x и реконструированным значением пикселей a или b (напомним, что это соседние пиксели по отношению к x - см. рис. 23). В этом случае рассматриваются две различные ситуации: первая, когда abs(Ra - Rb) <= NEAR , вторая - в противном случае. По сути кодирование пикселя прерывания серии происходит теми же методами, что и кодирование нового пикселя в регулярной моде с тем лишь дополнением, что Ix должно отличаться от Ra на величину большую NEAR, иначе ход кодирования будет продолжен. Опишем операции, которые должны быть выполнены:

if (abs(Ra - Rb) <= NEAR)
RItype = 1;
else
RItype = 0;
if (RItype == 1)
Px = Ra;
else
Px = Rb;
Errval = Ix - Rb;

Фрагмент кода выше определяет индекс RItype и ошибку предсказания для пикселя x. Затем следует в случае необходимости изменить знак Errval, а для опции «почти без потерь» также провести квантование ошибки предсказания:

if ((RItype == 0) && (Ra > Rb)) {
Errval = -Errval;
SIGN = -1;
else
SIGN = 1;
if (NEAR > 0) {
Errval = Quantize(Errval);
Rx = ComputeRx();
}
else
Rx = Ix;
Errval = ModRange(Errval, RANGE);

Теперь вычислим вспомогательную переменную TEMP, которая будет использоваться для вычисления параметра k в кодах Голомба.

if (RItype == 0)
TEMP = A;
else
TEMP = A + (N>>1);

Установим Q = RItype + 365 . Параметр k для кодов Голомба будем вычислять следующим образом: for (k=0; (N[Q]<

if (Errval < 0) {
Nn[Q] = Nn[Q] + 1;
A[Q] = A[Q] + ((EMErrval + 1 -RItype)>>1);
if (N[Q] == RESET) {
A[Q] = A[Q]>>1;
N[Q] = N[Q]>>1;
Nn[Q] = Nn[Q]>>1;
}
N[Q] = N[Q] + 1;

На этом и завершим описание кодера JPEG-LS. Отметим, что оно, безусловно, неполное, но мы и не ставили перед собой цели — скопировать стандарт этого метода. Все опущенные детали вы сможете найти в стандарте. Сейчас же перейдем к краткому описанию принципов работы декодера.

3.3. Декодер

Как упоминалось ранее, метод JPEG-LS почти симметричный, поэтому копировать с небольшими изменениями описание кодера мы не будем — эту информацию можно прочитать и в стандарте. Остановимся лишь на том, как происходит декодирование в серийной моде. После того, как вычислены все величины для текущего пикселя, считывается новый бит R из потока битов. Если он равен 1, то:

1. Изображение дополняется 2 J|RUNindex| пикселями со значением Ra.
2. Если на предыдущем шаге изображение уже было дополнено 2 J|RUNindex| пикселями и RUNindex < 31, то RUNindex увеличивается на 1. Если последний пиксель в строке ещё не декодирован, то мы снова считываем биты, в противном случае переходим к вычислению всех требуемых величин.

Если же бит равен 0, то:

1. Считывается J|RUNindex| бит из битового потока и преобразовывается в число, а изображение дополняется пикселями со значениями Ra в количестве, соответствующем вычисленному числу.
2. Если RUNindex > 0, то RUNindex уменьшается на 1.
3. Декодируется пиксель прерывания серии и снова начинается вычисление всех необходимых величин.

3.4. Формат файла

Сжатый файл состоит:

• из сегментов данных, содержащих коды Голомба и длины серий;
• из сегментов маркеров (информация необходимая декодеру);
• из сегмента «остальных» маркеров (некоторые зарезервированные маркеры JPEG).

Маркером здесь мы называем байт из единиц, за которым следует специальный код, сигнализирующий о начале нового сегмента. Если за маркером следует байт, у которого старший бит равен 1, то этот байт является началом сегмента маркеров. В противном случае, начинается сегмент данных.

3.5. Коды Голомба

Мы уже не раз упоминали коды Голомба. Что же это такое? Код Голомба неотрицательного целого числа «может быть эффективным кодом Хаффмана». Он зависит от выбора некоторого параметра b. Принцип кодирования таков:

• вычисляются две величины
  q = floor((n - 1) / b) и
  r = n - qb - 1 ;
• происходит построение кода из двух частей: первая часть — q в унарном коде, вторая часть — двоичное выражение для r , состоящее из floor(log 2 b) бит для малых остатков и из ceil(log 2 b) бит для больших.

Мы не приводим математическое обоснование использования кодов Голомба в JPEG-LS, отметим лишь, что, если входной поток данных состоит из целых чисел, причем вероятность числа n равна P(n) = (1 - p) n - 1 p (0 <= p <= 1) , то коды Голомба будут оптимальными кодами для этого потока данных, если выбрать параметр b следующим образом:
(1 - p) b + (1 - p) b + 1 <= 1 <= (1 - p) b - 1 + (1 - p) b .

3.6. Заключение

Формат JPEG-LS разрабатывался, прежде всего, для хранения изображений в медицинских целях, то есть для тех случаев, когда важно иметь большое изображение без малейших потерь качества. Как уже говорилось, за основу был взят формат LOCO-I, разработанный в стенах «HP Labs». Затем он был доработан совместными усилиями «HP» и «Mitsubishi». Обе компании разрешили использовать их патенты на этот формат без оплаты лицензии, поэтому JPEG-LS можно встретить и в обычных программах для PC.

Поясню на собственном примере. Может быть и поможете мне в понимании некоторых вещей. Задача поставленная передо мной самим собой следующая. Передать кадр (по команде) из WEB камеры в память сотового телефона с последующей передачей на другой сотовый. Из Вашей статьи не понятно, на какой формат следует забазироваться, доступность алгоритма. Далее - сосинусное преобразование - только поверхностное толкование, а где посмотреть детальный алгоритм с конкретным примером (скажете учи мат. анализ, но и там почти нет конкретных примеров, а если есть, то пропущены целые куски расчетов. Может есть конкретная методичка, так сошлитесь. Структуру организации файла вообще выкинули и даже ссылок не указали. "В получаемой матрице низкочастотные компоненты расположены ближе к левому верхнему углу, а более высокочастотные смещаются вправо вниз", мне кажется, что она так делается, а не получается (может ошибаюсь!).

Вопрос: как из JPG кадра отловить например только нужную информацию для дальнейшего декодирования в разрешении экрана телефона, не применяя PC, используя МК. Достаточно черно-белого варианта кадра. На какие FFxx надо обратить внимание и записать только ту информацию. Где взять структуру кадра WEB камеры. Я понимаю, что вопрос сложен, многопланов. Что например на МК не сделать расшифровку кадра и сжать затем с нужным разрешением, но вот вырезать хотя-бы верхний угол с нужным форматом это наверное можно.

Буду благодарен за информацию.

Что умею = программировать на VB, МК. Самостоятельная действующая интерактивная разработка управлением по сот.телефону несколькими реле, аудиоконтроль с использованием сотового телефона.

>> Вторым шагом является непосредственно применение >>алгоритма кодирования повторов (LZW)

может, RLE?

Разумеется, на этом шаге JPEG (см. контект), — RLE. Спасибо за обнаружение погрешности.

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

Наверняка многих работающих с графикой на компьютере интересует вопрос: а как удается изображение, занимающее весьма впечатляющий объем в памяти ПК, втиснуть в гораздо меньший размер на диске? Помнится, на заре своей издательской деятельности слово «компрессия» для меня было таким загадочным и удивительным… В самом деле, каким образом происходит сжатие изображений — ведь без него сейчас немыслимо представить ни Сеть, ни цифровую фотографию, ни цветную полиграфию?

Итак, сжатие. Оно может как приводить к потере качества, так и не приводить. Последний случай — это такие методы, как RLE (Run Length Encoding, кодирование длин серий, в результате которого образуются пары типа (skip , value , где skip — это число подряд идущих нулей, а value — следующее за ними значение) и LZW (компрессия методом Lempel-Ziff-Welch), реализованные в форматах PSD, GIF и TIFF. Широко используются они и архиваторами типа RAR и ZIP. Средняя степень компрессии сжатия без потерь — 2-3 раза.

Если нужно сжать изображение сильнее, без потери качества не обойтись. Каковы принципы? Во-первых, любое изображение содержит определенную избыточность, удаление которой не приведет к заметному изменению качества картинки. Во-вторых, человеческий глаз более восприимчив к изменениям яркости, нежели цвета. Поэтому для разных каналов изображения применяются различные степени сжатия — информация теряется, но визуально это не заметно. Кроме того, чувствительность глаза к мелким элементам изображения невелика, что позволяет без ущерба для качества их удалить. Так можно сжимать изображение (даже если ухудшение качества становится уже заметным) вплоть до приемлемого порога. Степень деградации качества определяется для каждого конкретного случая. Для полиграфии допустимы лишь минимальные искажения, а для размещения в Интернете (в зависимости от предназначения) — гораздо большие.

Наибольшую популярность среди методов компрессии с потерями получил JPEG, который даже при тридцатикратном сжатии сохраняет достаточное качество картинки. Кстати, в большинстве современных методов сжатия данных (например, Layer-4, известный как mp3, а также MPEG) реализованы механизмы, аналогичные JPEG. Давайте познакомимся поближе с этим форматом, тем более что не так давно была окончательно утверждена его новейшая реализация JPEG2000, в которую вошли все дополнения, внесенные в JPEG/MPEG за десять лет его развития.

JPEG

Название алгоритма компрессии — аббревиатура от Joint Photographic Expert Group, инициативной группы, образованной из экспертов ITU (International Telecommunication Union) и ISO (International Organization for Standartization). Именно поэтому в ее названии присутствует приставка Joint. В 1992 г. JPEG был объявлен международным стандартом в области графических изображений.

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

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

JPEG лучше всего компрессирует полноцветные и монохромные изображения фотографического качества. Если же требуется сохранить картинку с индексной палитрой, то сначала она конвертируется в полноцветную. При компрессии методом JPEG нужно иметь в виду, что все зависит от характера изображений: гораздо меньший объем будут занимать те, где изменения цвета незначительны и нет резких цветовых переходов. JPEG применяется всюду, где нужно хранить фотоизображения: в цифровых фотоаппаратах, полиграфии (EPS DCS 2.0), немыслим без него и Интернет.

Существует несколько разновидностей JPEG-компрессии, мы же рассмотрим только две из них, использующиеся в стандартном пакете для работы с растровыми изображениями Adobe Photoshop, — baseline и progressive . Два других способа — ariphmetic и loseless — экзотика, в силу ряда причин не получившая широкого распространения.

Как происходит сжатие

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

Y = 0,299xR+0,587*G+0,114xB Cb = (B-Y)/0,866/2+128 Cr = (R-Y)/0,701/2+128

2. На следующем этапе происходит т. н. префильтрация , при которой соседние пиксели отдельно в каждом из каналов Cb и Cr группируются попарно в горизонтальном и вертикальном направлениях, а яркостный канал Y оставляется без изменений. После этого вся группа из четырех пикселов получает усредненное значение соответствующих компонент Cb и Cr. Для краткости такую схему можно обозначить как 4:1:1 (такая же форма представления принята в DRAW — окно экспорта в jpeg). С учетом того, что каждый пиксел кодируется 3 байтами (по 256 уровней для каждого из трех каналов), в результате объем данных автоматически сокращается в 2 раза (вместо 12 байт для передачи 4 пикселов достаточно передать всего 4+1+1 = 6 байт). С точки зрения математики такое преобразование приводит к существенной потере информации, но человеческий глаз потери не воспринимает, поскольку в обычных фотографических изображениях присутствует существенная избыточность.

3. Полученная информация, прошедшая стадию первичной «очистки», отдельно в каждом канале снова группируется в блоки, но уже размером 8x8, после чего для них применяется основное сжатие — т. н. дискретное косинусное преобразование , для краткости — DCT (discrete cosine transform). В результате информация о распределении яркости пикселов преобразуется в другой вид, где она описывается распределением, основанном на частоте появления той или иной яркости пикселов. DCT имеет ряд преимуществ перед другими преобразованиями (например, перед преобразованием Фурье), обеспечивая лучшее восстановление информации.

Вместо массива из 64 значений (8x8 пикселов) для каждого блока, из которых состоит изображение, мы получаем массив из 64 частот. Рассмотрим работу DCT на примере. Допустим, яркость пикселов в одном блоке нашего изображения имеет вид, представленный на рис. 1 слева, тогда результат преобразования будет таким, как показано справа.

1

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

4. Следующий этап — удаление малозаметной глазу информации из блока, или квантование (quantization). Все составляющие делятся на различные коэффициенты, определяющие значимость каждой из них для качественного восстановления исходного изображения, и результат округляется до целого значения. Именно эта процедура вносит наибольшие потери качества, снижая конечный объем изображения. Высокочастотные составляющие квантуются грубо, а низкочастотные — точнее, поскольку наиболее заметны. Дабы несколько сгладить понижение качества, в канале яркости используются меньшие коэффициенты деления, чем в каналах цветности. Но чаще (это делается для ускорения расчетов) вместо специально подобранных значений берется всего одно — то, которое вводит пользователь при выборе степени компрессии.

Вот, например, как выглядит окно Photoshop при сохранении изображения c помощью операции Save for web, где параметр Quality (вернее, производная от него) — тот самый коэффициент округления (рис. 2).

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

4

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

5. После выполнения основной работы по сжатию изображения дальнейшие преобразования сводятся к второстепенным задачам: оставшиеся составляющие собираются в последовательность таким образом, чтобы сначала располагались отвечающие за крупные детали, а потом — за все более мелкие. Если посмотреть на рисунок, то движение кодировщика похоже на зигзагообразную линию. Этап так и называется — ZigZag (рис. 5).

5

Затем получившаяся последовательность сжимается: сначала обычным RLE, затем методом Хаффмана.

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

Вот, в общем, и все преобразования. А теперь давайте подсчитаем, какая компрессия была достигнута в нашем примере. Мы получили 7 значений, по которым восстановится первоначальное изображение размером 8x8. Итак, компрессия от применения DCT-преобразования в обоих каналах цветности составила 8x8/7 ≈ 9 раз. Отведем на канал яркости не семь, а 11 коэффициентов, что даст 8x8/11 ≈ 6. Для всех трех каналов получится (9+9+6)/3=8 раз. Снижение качества при «прореживании» изображения, произошедшего на второй стадии, дает дополнительно двойной прирост (схема 4-1-1, учитывающая особенности кодирования яркостной составляющей), что даст итоговый результат — 16 раз. Это грубый подсчет, не учитывающий некоторых аспектов, но отражающий реальную картину. Чтобы получить тридцатикратное сокращение размера файла, нужно оставить всего 3-4 составляющие.

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

Недостатки JPEG

1. Невозможность достичь высоких степеней сжатия за счет ограничения на размер блока (только 8x8).
2. Блочность структуры на высоких степенях компрессии.
3. Закругление острых углов и размывание тонких элементов в изображении.
4. Поддерживаются только RGB-изображения (использовать JPEG для CMYK-изображений можно только в формате EPS через DCS).
5. Изображение нельзя отобразить до тех пор, пока оно не загрузится полностью.

С тех пор, как JPEG был утвержден в качестве стандарта, прошло уже десять лет. За это время группы исследователей предложили ряд существенных дополнений в первоначальный вариант, которые вылились в конце прошлого года в появление нового стандарта.

JPEG2000

С 1997 г. были начаты работы, направленные на создание универсальной системы кодирования, которая снимала бы все ограничения, накладываемые JPEG, и могла эффективно работать со всеми типами изображений: черно-белыми, в градациях серого, полноцветными и многокомпонентными, причем независимо от содержания (будут ли это фотографии, достаточно мелкий текст или даже чертежи). В его разработке принимали участие наряду с международными стандартизирующими организациями такие гранды промышленности, как Agfa, Canon, Fujifilm, Hewlett-Packard, Kodak, LuraTech, Motorola, Ricoh, Sony и др.

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

Основные требования, предъявляемые к формату JPEG2000:

1. Достижение повышенной по сравнению с JPEG степени компрессии.
2. Поддержка монохромных изображений, что позволит применять его для компрессии изображений с текстом.
3. Возможность сжатия вообще без потерь.
4. Вывод изображений с постепенным улучшением детализации (как в progressive GIF).
5. Использование в изображении приоритетных областей, для которых качество может устанавливаться выше, чем в остальной части изображения.
6. Декодирование в реальном режиме времени (без задержек).

Принцип сжатия

В качестве основного механизма компрессии в JPEG2000, в отличие от JPEG, используется волновое (wavelet) преобразование — система фильтров, применяемых ко всему изображению. Не вдаваясь в детали компрессии, отметим лишь основные моменты.

6

Сначала точно так же, как и для JPEG, происходит конвертирование изображения в систему YCrCb, после чего — первичное удаление избыточной информации (путем уже известного объединения соседних пикселей в блоки 2x2). Затем все изображение делится на части одинакового размера (tile), над каждой из которых независимо от других и будут происходить дальнейшие преобразования (это снижает требования к объему памяти и вычислительным ресурсам). Далее каждый канал проходит фильтрацию низкочастотным и высокочастотным фильтрами отдельно по строкам и по рядам, в результате чего после первого прохода в каждой части формируются четыре более мелких изображения (subband). Все они несут информацию об исходном изображении, но их информативность сильно отличается (рис. 6).

Например, изображение, полученное после низкочастотной фильтрации по строкам и рядам (вверху слева), несет наибольшее количество информации, а полученное после высокочастотной — минимальное. Информативность у изображений, полученных после НЧ-фильтрации строк и ВЧ для столбцов (и наоборот), средняя. Наиболее информативное изображение опять подвергается фильтрации, а полученные составляющие, как и при jpeg-компрессии, квантуются. Так происходит несколько раз: для сжатия без потерь цикл обычно повторяется 3 раза, с потерями — разумным компромиссом между размером, качеством и скоростью декомпрессии считается 10 итераций. В результате получается одно маленькое изображение и набор картинок с мелкими деталями, последовательно и с определенной точностью восстанавливающих его до нормального размера. Очевидно, что наибольшая степень компрессии получается на крупных изображениях, поскольку можно установить большее количество циклов.

Практическая реализация

С тех пор, как были заложены основы компрессии методом JPEG2000, ряд компаний разработал достаточно эффективные алгоритмы ее реализации.

Среди крупных разработчиков ПО можно отметить Corel (кстати, она одна из первых внедрила в свои пакеты поддержку формата wi, основанного на волновых преобразованиях, за что ей честь и хвала) — все изображения, поставляемые на компакт-дисках с пакетом CorelDRAW вплоть до девятой версии, сжимались именно таким способом.

Позже к ней подтянулась и Adobe. Часть идей, заложенных в JPEG2000, была применена разработчиками Photoshop 6 в виде продвинутых опций при сохранении изображения в формате JPEG (обычном, основанном на косинусном преобразовании). Среди них — прогрессивный JPEG (параметр Progressive в окне Save for Web). Этот алгоритм предназначен, главным образом, для систем реального времени и работает точно так же, как и прогрессивный GIF. Сначала появляется грубая копия изображения, состоящая всего из нескольких блоков большого размера, а со временем, когда подгружаются остальные данные, структура начинает просматриваться все четче, пока, наконец, конечное изображение не восстановится полностью. В отличие от GIF, такой алгоритм создает большую нагрузку на просмотрщик, поскольку ему придется полностью выполнять весь цикл преобразований для каждой передаваемой версии.

Из других дополнений отметим включение в файл нескольких JPEG-сжатых изображений с разной степенью компрессии, разрешением и даже цветовыми моделями. Соответственно, в Photoshop 6 появилась возможность выделять в изображении отдельные области и применять для них другие установки компрессии (Region-Of-Interest , впервые такой механизм был предложен еще в 1995 г.), используя более низкие значения в таблице квантования. Для этого задается требуемая область (например, в виде нового канала в изображении) и нажимается пиктограмма маски возле пункта Quality (Качество). В появившемся окне можно экспериментировать с изображением, передвигая ползунки, — готовый результат отображается на экране, позволяя быстро находить необходимый компромисс между качеством и размером.

Специализированные конверторы и просмотрщики

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

Специализированные решения от других компаний доступны в виде коммерческих разработок. Одни реализованы в виде отдельных программ (JPEG 2000 разработки Aware), другие — в виде дополнительных модулей для наиболее распространенных растровых редакторов (ImagePress JPEG2000 разработки Pegasus Imaging и модуль LEAD JPEG2000 от LEAD Technologies). На их фоне выделяется компания LuraTech, давно занимающаяся этим вопросом. Она продвигает свою технологию LuraWave в самодостаточном продукте LuraWave SmartCompress (доступна уже третья версия) и предлагает модули для Photoshop, Paintshop, Photopaint. Отличительная особенность — более высокая скорость работы (практически мгновенное преобразование) даже с картинками размером в несколько мегабайт. Соответственно и цена этого модуля самая высокая — 79 долл.

Чтобы просматривать JPEG2000-изображения браузерами, необходимо установить специальный модуль-просмотрщик (все разработчики предлагают его бесплатно). Вставка изображения в html-документ, как и любого plug-in, сводится к использованию конструкции EMBED (с дополнительными параметрами). Например, означает, что будет использоваться прогрессивный метод переда- чи изображения. То есть в нашем примере (файл размером 139 Кбайт) сначала передаются только 250 байт, на основании которых будет построено грубое изображение, затем, после дозагрузки 500 байт, изображение обновляется (так продолжается до достижения значения LIMIT).

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

9

Выводы

Итак, JPEG2000 объективно показывает лучшие результаты, чем JPEG только на высоких степенях сжатия. При компрессии в 10-20 раз особой разницы не заметно. Сможет ли он вытеснить или просто составить конкуренцию широко распространенному формату? В ближайшее время — вряд ли, в большинстве случаев соотношение качество/размер, обеспечиваемое JPEG, вполне приемлемо. А те 10-20% дополнительной компрессии, которые дает JPEG2000 при визуально одинаковом качестве, вряд ли приведут к росту его популярности.

Зато к новому формату проявляют пристальный интерес компании-производители цифро- вых камер, поскольку размеры светочувствительных матриц с каждым годом неуклонно увеличиваются, и помещать изображения в память становится все труднее. И вот тогда новый формат получит большее распространение, и кто знает, возможно, через какое-то время JPEG2000 сравняется с JPEG. Во всяком случае, Analog Micro Devices недавно выпустила специализированный чип, в котором компрессия/декомпрессия по новой технологии реализованы на аппаратном уровне, а министерство обороны США уже сейчас активно использует новый формат для записи фотоснимков, полученных со спутников-шпионов.

Факты и домыслы

1. JPEG теряет качество при открытии и повторном сохранении файла.

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

2. JPEG теряет качество при редактировании файла.

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

3. Результат компрессии с одинаковыми параметрами в разных программах будет одинаков.

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

4. При установке максимального качества изображение сохраняется без каких-либо потерь качества.

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

5. Любой файл JPEG можно открыть в любом редакторе, понимающем формат JPEG.

Неправда. Такую разновидность JPEG, как прогрессивный (progressive JPEG), некоторые редакторы не понимают.

6. JPEG не поддерживает прозрачность.

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

7. JPEG сжимает лучше, чем GIF.

Неправда. У них разная область применения. В общем случае, типичная «гифовская» картинка после конвертирования в JPEG будет иметь больший объем.

JPEG2000 против JPEG

7

1. При двадцати-тридцатикратном сжатии JPEG2000 и JPEG дают приблизительно одинаковое качество (кстати говоря, Photoshop не может сжать обычную фотографию больше этого предела).

2. При большем сжатии качество JPEG2000 существенно выше, чем у JPEG, что позволяет без особых потерь сжимать до 50 раз, а с некоторыми потерями (речь идет об изображениях для Интернет) — до 100 и даже до 200.

3. При больших степенях компрессии в тех областях, где происходит плавное изменение цвета, изображение не приобретает характерную для простого JPEG блочную структуру. JPEG2000 также несколько размазывает и закругляет острые контуры — см. фотографии (рис. 7 и 8).

На нем представлены результаты компрессии тестового файла с разными степенями компрессии (слева — сохраненные в Photoshop в формате JPG, справа — в формате JPEG2000). Для изображения на рис. 7 были выбраны степени компрессии 20, 40, 70 и 145 (их можно явно указывать при сохранении в JPEG2000), степень сжатия JPG выбиралась из того расчета, чтобы размер файла был таким же, как после сжатия по JPEG2000. Как говорится, результаты налицо. Для чистоты был проведен второй эксперимент на изображении с более четкими деталями (со степенями компрессии 10, 20, 40 и 80). Преимущество опять же на стороне JPEG2000 (рис. 8).

8

4. Поскольку, по сути, в одном JPEG2000-файле хранятся копии с разным разрешени

ем, для тех, кто делает галереи изображений в Интернете, отпадает необходимость создавать для них thumbnails.

5. Особый интерес представляет компрессия без искажений (режим loseless). Так, тестовый файл при LZW-сжатии из Photoshop занял 827 Кбайт, а сжатый JPEG2000 — 473 Кбайт.

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

7. Отсутствие поддержки JPEG2000 в браузерах. Чтобы просматривать такие изображения, нужно скачать довольно большой дополнительный модуль (1,2 Мбайта).

8. Отсутствие бесплатного ПО для сохранения изображений в новом формате.

Журналов в свободном доступе.

На ту же тему: