Ростелеком ТВ 

Алгоритмы архивации с потерями. Сжатие изображений: JPEG и JPEG2000

«Реализация алгоритмов

JPEG и JPEG2000»

Выполнил:

студент группы 819

Угаров Дмитрий

Принципы работы алгоритмов JPEG и JPEG2000

1. Алгоритм JPEG

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

Алгоритм JPEG является алгоритмом сжатия с потерей качества .

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

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

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

Этапы кодирования

Процесс сжатия по схеме JPEG включает ряд этапов:

1. Преобразование изображения в оптимальное цветовое пространство;

В случае применения цветового пространства яркость/цветность (YCbCr) достигается лучшая степень сжатия. На данном этапе кодирования с помощью соответствующих соотношений цветовая модель RGB преобразуется в YCbCr:

Y = 0.299*R + 0.587*G + 0.114*B

Cb = - 0.1687*R – 0.3313*G + 0.5*B

Cr = 0.5*R – 0.4187*G – 0.0813*B.
Во время декодирования можно использовать соответствующее обратное преобразование:
R = Y + 1.402*Cr

G = Y – 0.34414*Cb – 0.71414*Cr

B = Y + 1.772*Cb.
Примечание, связывающее Y,Cb,Cr в человеческой визуальной системе:

Глаз, особенно сетчатка, имеет как визуальные анализаторы два типа ячеек: ячейки для ночного видения, воспринимающие только оттенки серого (от ярко-белого до темно-черного) и ячейки дневного видения, которые воспринимают цветовой оттенок. Первые ячейки , дающие цвет RGB, обнаруживают уровень яркости, подобный величине Y. Другие ячейки, ответственные за восприятие цветового оттенка, - определяют величину, связанную с цветоразностью.


2. Субдискретизация компонентов цветности усреднением групп пикселей;

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

1)тип 4:2:0 (когда изображение разбивается на квадраты 2х2 пикселей и в каждом из них все пиксели получают одинаковые значения каналов Cb и Cr, а яркость Y у остается у каждого своя)

2) тип 4:2:2 (объединение по компонентам цветности происходит только по горизонтали в группах по два пикселя).

3)тип 4: 4: 4 подразумевает, что каждому пикселю в каждой строке соответствует собственное уникальное значение компонентов Y, Cb и Cr. (рис.1 а)

4) тип 4:2:2. Выполнив субдискретизацию сигнала цветности с коэффициентом 2 по горизонтали, мы получим из потока 4: 4: 4 YCbCr поток 4: 2: 2 YCbCr. Запись «4: 2: 2» означает , что в отдельно взятой строке на 2 значения цветности приходятся 4 значения яркости (см. рис.1 б). Сигнал 4: 2: 2 YCbCr очень немного проигрывает по качеству изображения сигналу 4: 4: 4 YCbCr, зато требуемая ширина полосы сокращается на 33% от исходной.

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

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

DCT непосредственно применяемый к блоку (в нашем случае 8х8 пикселей) изображения будет выглядеть так:

где х, y - пространственные координаты пикселя (0..7) ,

f(x,y) - значения пикселей исходного макроблока (допустим, яркость)

u,v - координаты пикселя в частотном представлении (0..7)

w(u) =1/SQRT(2) при u=0, в остальных случаях w(u)=1 (SQRT - квадратный корень)

w(v) =1/SQRT(2) при v=0, в остальных случаях w(v)=1

Или в матричной форме:

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

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


5. Этап Вторичного Сжатия

Заключительной стадией работы кодера JPEG является кодирование полученной матрицы.

5.1 Зигзагообразная перестановка 64 DCT коэффициентов

Так, после того, как мы выполнили DCT-преобразование над блоком величин 8x8, у нас есть новый блок 8x8. Затем, этот блок 8x8 просматривается по зигзагу подобно этому:

(Числа в блоке 8x8 указывают порядок , в котором мы просматриваем 2-мерную матрицу 8x8)

0, 1, 5, 6,14,15,27,28,

2, 4, 7,13,16,26,29,42,

3, 8,12,17,25,30,41,43,

9,11,18,24,31,40,44,53,

10,19,23,32,39,45,52,54,

20,22,33,38,46,51,55,60,

21,34,37,47,50,56,59,61,

35,36,48,49,57,58,62,63

Как Вы видите, сначала - верхний левый угол (0,0), затем величина в (0,1), затем (1,0), затем (2,0), (1,1), (0,2), (0,3), (1,2), (2,1), (3,0) и т.п.

После того, как мы прошли по зигзагу матрицу 8x8, мы имеем теперь вектор с 64 коэффициентами (0..63) Смысл этого зигзагообразного вектора – в том, что мы просматриваем коэффициенты 8x8 DCT в порядке повышения пространственных частот. Так, мы получаем вектор отсортированный критериями пространственной частоты: первая величина на векторе (индекс 0) соответствует самой низкой частоте в изображении – она обозначается термином DC. С увеличением индекса на векторе, мы получаем величины соответствующие высшим частотам (величина с индексом 63 соответствует амплитуде самой высокой частоте в блоке 8x8). Остальная часть коэффициентов DCT обозначается AC.

5.2 RunLength кодирование нулей (RLE)

Теперь у нас есть вектор с длинной последовательностью нулей. Мы можем использовать это, кодируя последовательные нули. ВАЖНО: Вы увидите позже почему, но здесь мы пропускаем кодировку первого коэффициента вектора (коэффициент DC), который закодирован по-другому. Рассмотрим исходный 64 вектор как 63 вектор (это - 64 вектор без первого коэффициента)

Допустим, мы имеем 57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0,0,0,0, только 0,...,0

Здесь - как RLC JPEG сжатие сделано для этого примера:

(0,57); (0,45); (4,23); (1,-30); (0,-16); (2,1); EOB

Как Вы видите, мы кодируем для каждой величины, отличающейся от 0 количество последовательных ПРЕДШЕСТВУЮЩИХ нулей перед величиной, затем мы добавляем величину. Другое примечание: EOB - короткая форма для Конца Блока , это - специальная кодированная величина (маркер). Если мы достигли в позиции на векторе, от которого мы имеем до конца только нули вектора, мы выделим эту позицию с EOB и завершим сжатие RLC квантованного вектора.

[Заметьте, что если квантованный вектор не оканчивается нулями (имеет последний элемент не 0), мы не будем иметь маркер EOB.]

(0,57); (0,45); (4,23); (1,-30); (0,-16); (2,1); (0,0)

Другая ОСНОВНАЯ вещь: Допустим, где-нибудь на квантованном векторе мы имеем:

57, восемнадцать нулей, 3, 0,0 ,0,0 2, тридцать-три нуля, 895, EOB

Кодирование Хаффмана JPG делает ограничение, по которому число предшествующих нулей должно кодироваться как 4-битовая величина - не может превысить 15.

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

(0,57); (15,0) (2,3); (4,2); (15,0) (15,0) (1,895), (0,0)

(15,0) - специальная кодированная величина, которая указывает , что там следует за 16 последовательными нулями.

5.3 Конечный шаг - кодирование Хаффмана

Сначала ВАЖНОЕ примечание: Вместо хранения фактической величины, JPEG стандарт определяет, что мы храним минимальный размер в битах, в котором мы можем держать эту величину (это названо категория этой величины) и затем битно кодированное представление этой величины подобно этому:

7,..,-4,4,..,7 3 000,001,010,011,100,101,110,111

15,..,-8,8,..,15 4 0000,..,0111,1000,..,1111

31,..,-16,16,..,31 5 00000,..,01111,10000,..,11111

63,..,-32,32,..,63 6 .

127,..,-64,64,..,127 7 .

255,..,-128,128,..,255 8 .

511,..,-256,256,..,511 9 .

1023,..,-512,512,..,1023 10 .

2047,..,-1024,1024,..,2047 11 .

4095,..,-2048,2048,..,4095 12 .

8191,..,-4096,4096,..,8191 13 .

16383,..,-8192,8192,..,16383 14 .

32767,..,-16384,16384,..,32767 15 .

Впоследствии для предшествующего примера:

(0,57); (0,45); (4,23); (1,-30); (0,-8); (2,1); (0,0)

давайте закодируем только правую величину этих пар, кроме пар, которые являются специальными маркерами подобно (0,0) или (если мы должны иметь) (15,0)

45, аналогично , будет закодирован как (6,101101)

30 -> (5,00001)

И теперь, мы напишем снова строку пар:

(0,6), 111001; (0,6), 101101; (4,5), 10111; (1,5), 00001; (0,4), 0111; (2,1), 1; (0,0)

Пары 2 величин, заключенные в скобки, могут быть представлены в байте, так как фактически каждая из 2 величин может быть представлена в 4-битном кусочке (счетчик предшествующих нулей - всегда меньше, чем 15 и также как и категория [числа закодированные в файле JPG - в области -32767..32767]). В этом байте, старший кусочек представляет число предшествующих нулей, а младший кусочек - категорию новой величины, отличной от 0.

Конечный шаг кодировки состоит в кодировании Хаффмана этого байта, и затем записи в файле JPG , как поток из битов, кода Хаффмана этого байта, сопровождающийся битовым представлением этого числа.

Например, для байта 6 (эквивалент (0,6)) у нас есть код Хаффмана = 111000;

21 = (1,5) - 11111110110

4 = (0,4) - 1011

33 = (2,1) - 11011

0 = EOB= (0,0) - 1010

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

111000 111001 111000 101101 1111111110011001 10111 11111110110 00001

1011 0111 11011 1 1010
Достоинства и недостатки

К недостаткам формата следует отнести то, что при сильных степенях сжатия дает знать о себе блочная структура данных, изображение «дробится на квадратики» (каждый размером 8x8 пикселей). Этот эффект особенно заметен на областях с низкой пространственной частотой (плавные переходы изображения, например, чистое небо). В областях с высокой пространственной частотой (например, контрастные границы изображения), возникают характерные «артефакты» - иррегулярная структура пикселей искаженного цвета и/или яркости. Кроме того, из изображения пропадают мелкие цветные детали. Не стоит также забывать и о том, что данный формат не поддерживает прозрачность.

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

2. Алгоритм JPEG2000

Алгоритм JPEG-2000 разработан той же группой экспертов в области фотографии, что и JPEG. Формирование JPEG как международного стандарта было закончено в 1992 году. В 1997 стало ясно, что необходим новый, более гибкий и мощный стандарт, который и был доработан к зиме 2000 года.

Основные отличия алгоритма в JPEG 2000 от алгоритма в JPEG заключаются в следующем:

1)Лучшее качество изображения при сильной степени сжатия. Или, что то же самое , большая степень сжатия при том же качестве для высоких степеней сжатия. Фактически это означает заметное уменьшение размеров графики "Web-качества", используемой большинством сайтов.

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

3)Основной алгоритм сжатия заменен на wavelet. Помимо указанного повышения степени сжатия это позволило избавиться от 8-пиксельной блочности, возникающей при повышении степени сжатия. Кроме того, плавное проявление изображения теперь изначально заложено в стандарт (Progressive JPEG, активно применяемый в Интернет, появился много позднее JPEG).

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

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

6)Поддержка сжатия однобитных (2-цветных) изображений. Для сохранения однобитных изображений (рисунки тушью, отсканированный текст и т.п.) ранее повсеместно рекомендовался формат GIF, поскольку сжатие с использованием ДКП весьма неэффективно к изображениям с резкими переходами цветов. В JPEG при сжатии 1-битная картинка приводилась к 8-битной, т.е. увеличивалась в 8 раз, после чего делалась попытка сжимать, нередко менее чем в 8 раз. Сейчас можно рекомендовать JPEG 2000 как универсальный алгоритм.

7)На уровне формата поддерживается прозрачность. Плавно накладывать фон при создании WWW страниц теперь можно будет не только в GIF, но и в JPEG 2000. Кроме того, поддерживается не только 1 бит прозрачности (пиксель прозрачен/непрозрачен), а отдельный канал , что позволит задавать плавный переход от непрозрачного изображения к прозрачному фону.

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

Этапы кодирования

Процесс сжатия по схеме JPEG2000 включает ряд этапов:

1. Преобразование изображения в оптимальное цветовое пространство.
На данном этапе кодирования с помощью соответствующих соотношений цветовая модель RGB преобразуется в YUV:

При декомпрессии применяется соответствующее обратное преобразование:

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

Дискретное wavelet преобразование (DWT) также может быть двух видов - для случая сжатия с потерями и для сжатия без потерь.

Это преобразование в одномерном случае представляет собой скалярное произведение соответствующих коэффициентов на строку значений. Но т.к. многие коэффициенты нулевые, то прямое и обратное вейвлет преобразование можно записать следующими формулами (для преобразования крайних элементов строки используется ее расширение на 2 пикселя в каждую сторону, значения которых симметричны с значениями элементов строки относительно ее крайних пикселей):
y(2*n + 1) = x(2*n + 1) - (int)(x(2*n) + x(2*n + 2)) / 2

y(2*n) = x(2*n) + (int)(y(2*n - 1) + y(2*n + 1) + 2) / 4

и обратное

x(2*n) = y(2*n) - (int)(y(2*n - 1) + y(2*n + 1) + 2) / 4

x(2*n + 1) = y(2*n + 1) + (int)(x(2*n) + x(2*n + 2)) / 2.

3. Квантование коэффициентов.

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


4. Этап Вторичного Сжатия

. Как и в JPEG, в новом формате последним этапом алгоритма сжатия является кодирование без потерь. Но, в отличие от предыдущего формата, в JPEG2000 используется алгоритм арифметического сжатия.

Программная реализация

В данной работе реализованы алгоритмы JPEG и JPEG2000. В обоих алгоритмах реализовано прямое и обратное кодирование (отсутствует последний этап вторичного сжатия). Расчет JPEG происходит довольно долго (порядка 30 секунд) в связи «прямым» высчитыванием DCT. Если потребуется увеличить скорость работы , следует изначально вычислить матрицу DCT(изменения производить в классе DCT).

Перейдем к рассмотрению программы:


  1. После запуска выводится окно, где

и сможете его сохранить , нажав кнопку (2) и введя желаемое название в диалоговом окне.

  • При достаточно большом Quality Factor изображение сильно измениться. Если это JPEG алгоритм то будут ярко выражены блоки размера 8x8.(в случае алгоритма JPEG2000, блочного деления не будет)
    • До:

    После:



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

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

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

    Светимость

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

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

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

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

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

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

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

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

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

    Форматы - Подробно о декодере jpeg.

    Всем привет! Помните меня? :) Поскольку тема данной статьи интересует многих, я, не долго думая, решил нацарапать статейку. Несмотря на всю кажущуюся сложность, постараюсь изложить всё в простой, понятной форме. Хочу сразу предупредить: всё, о чем я буду писать, есть результат моих собственных экспериментов, а посему не является истиной в последней инстанции. Это всего лишь мои мысли. Таким образом, если что не так, я не виноват:). В статье буду использовать фрагменты из документации по жпегу by Ceryx, а также оптимизированные и страшно изуродованные:)) куски кода из пасовского исходника жпег декодера by Алексей Абрамов. Там, правда, мало что от него осталось, но в любом случае его я использовал в качестве базы. Данный материал не рассчитан на но─ вичков - как минимум, требуются знания языка Паскаль. Вступление сказано, теперь переходим непосредственно к делу. Декодирование жпега можно разделить на две стадии. настройка декодера на соответствующий жпег, всё это я опишу в первую очередь. 2-я - Непосредственно сам процесс декодирования, это найдёте дальше по тексту. Для лучшего понимания алгоритмов, кое-где буду приводить куски пасовского исходника. Немного теории. JPEG представляет собой упакованный кадр фотореалистичного изображения, то есть расчитан он в основном на сжатие цветных фотографий с глубиной цвета 24 бита (до цветовых преобразований подразумевается по 8 бит на каждую цветовую ком─ поненту RGB). Чтобы было понятно, как декодировать жпег, вкратце опишу процесс сжатия кадра. Кадр разбивается на блоки 8x8. Над каждым блоком производится ДКП (Дискретное Косинусное Преобразование), тем самым происходит трансформация яркостных данных из временной области в частотную. Затем полученная частотная матрица квантизируется, при этом про─ исходит оптимизация частот. Собственно, на данном этапе и проис─ ходит сжатие, за счёт отбрасывания излишней высокочастотной информации. Далее все члены матрицы вытягиваются в одну цепочку зигзагом и кодируются по RLC (Zero Run Length Coding). Финальный этап - кодирование по Хаффману, в результате которого из полного блока 8x8 остаётся лишь упакованная горстка битов. Процесс деко─ дирования выполняется в обратном кодированию порядке. Конечно, я описал лишь общую схему процесса сжатия, но думаю, пока этого вполне достаточно. Нам понадобится ещё несколько понятий. Цвета в жпеге хранятся не как RGB, а в формате YCbCr: Y - компонента яркости; Сb/Cr - цветоразностные компоненты, приблизительно показывают, сколько голубой и красной составляющей в цвете. Таким образом, если нас не интересуют цвета, можно извлечь только Y компоненту. Также по тексту будут фигурировать обозначения DC/AC. В полученном нами векторе из 64 элементов, необходимых для последующего преобразо─ вания по ДКП, первый элемент со смещением 0 называется DC - это, так сказать, нулевая частота,то есть фоновая яркость; все после─ дующие 63 элемента - AC. Это необходимо потому, что разные коэф─ фициенты кодируются по разному. 0-я частота, как правило, меняе─ тся слабо, поэтому кодируется не сам коэффициент, а разность ме─ жду этим и предыдущим DC коэффициентом. AC приходится кодировать как есть, там уже частоты меняются существенно, на протяжении всего кадра. Жпег представляет собой файл, поделенный на части - сегменты. Вот что из себя представляет сегмент: - заголовок (4 байта): $ff идентификатор сегмента n тип сегмента (1 байт) sh, sl размер сегмента, включая эти 2 байта, но не включая $FF и тип сегмента. Не в Intel"овском, а в Motorol"овском порядке: старший байт первый, младший последний! - содержимое сегмента, макс. 65533 байта. В начале сегмента стоит маркер - определённая метка: первый байт всегда FF, следующий - тип сегмента. Формат JPEG использует мотороловской формат для слов, то есть старший байт слова идёт первым, младший вторым. Приведу основные маркеры, которые нам понадобятся: D8 - SOI Start Of Image C0 - SOF0 Start Of frame (baseline) C2 - SOF2 Start Of frame (progressive) C4 - DHT Define Huffman table DB - DQT Define Quantization table DD - DRI Define Restart Interval DA - SOS Start Of Scan D9 - EOI End Of Image Немного подробнее опишу маркеры: D8,D9 = начало, конец файла; C0,C2 = определить основные параметры кадра (разрешение, цве─ тность, таблицы); C4 = таблицы Хаффмана (необходимы для декодирования битового потока); DB = таблицы квантизации (нужны для процесса деквантизации); DD = определить интервал перезапуска (редко используется в декодере); DA = начало сканирования (с этого маркера начинаются непосре─ дственно упакованные данные самого жпега). Дабы не захламлять ваши головы, уважаемые читатели, не буду сейчас углубляться в алгоритмы паковки жпега, сделаю это позже. Скажу лишь, что всё, что нам необходимо вначале сделать, - это просканировать файл от начала, от маркера SOI до маркера SOS, попутно инициализируя соответствующие переменные и таблицы. Мар─ кер SOS определяет начало пакованных данных жпега, а всё, что идёт после него, относится уже к процессу декодирования, это рассмотрим дальше. Процесс сканирования жпега начинается с чтения маркера SOI. Если в начале файла его нет, то это не жпег и можно смело пре─ кращать чтение.Сразу за маркером следуют 2 байта длины сегмента, исключение составляют SOI и EOI, у них сегмент отсутствует. Вот как выглядит основной цикл сканирования: ... Repeat BlockRead(PictureFile,v,2); if Lo(v)$FF then begin WriteLn("Invalid file format"); Close(PictureFile); Halt end; b:=Hi(v); Marker[b]:=True; if (b$D8) and (b$D9) then begin BlockRead(PictureFile,v,2); FilePtr:=Swap(v)-2; Case b of $C0,$C2: ... { Main Image Parameters } $C4: ... $DA: ... { Start Of Scan } $DB: ... $DD: ... { Define Restart Interval } End; while FilePtr0 do begin BlockRead(PictureFile,v,1); dec(FilePtr) end; if IOResult0 then begin WriteLn("I/O error !"); Close(PictureFile); Halt end end Until (b=$D9) or (b=$DA); ... BlockRead - читает из файла заданное количество байт Lo/Hi - выделяет младший/старший байт Swap - меняет старший и младший байт местами Все остальные маркеры и их сегменты, соответственно, пропус─ каются. Сканирование маркеров выполняется до тех пор, пока не встретится SOS. Это говорит о том, что все подготовительные опе─ рации выполнены и далее следует битовый поток данных самого жпега. Теперь рассмотрим подробнее обработку самих маркеров. Из─ лагать буду в такой последовательности: вначале полный формат соответствующего сегмента,далее фрагмент кода,затем комментарий. Пока описание буду давать краткое, более детально всё рассмотрим далее. Поэтому, если вдруг вам что-то будет неясно, советую пока пропустить это место и читать дальше. SOF0,SOF2: Начало кадра: ~~~~~~~~~~~~~~~~~~~~~~~~ - $ff, $c0 (SOF0) - длина (старший, младший байт), 8+кол.компонент*3 - точность данных (1 байт) в формате бит/элемент, обычно 8 - высота жпега (2 байта, Ст-Мл) - ширина жпега (2 байта, Ст-Мл) - кол.компонент (1 байт): обычно 1=чёрно-белое;3=цветное YCbCr - для каждого компонента: 3 байта - идентификатор компонента (1=Y, 2=Cb, 3=Cr) - сэмплинг фактор (бит 0-3 верт., 4-7 гор.) - номер таблицы квантизации ... $C0,$C2: begin vv:=ReadByte; { Main Image Parameters } Height:=ReadWord; Width:=ReadWord; planes:=ReadByte; if (vv8) or ((planes1) and (planes3)) then begin WriteLn("Only 8-bit Grayscale/RGB images supported"); Close(PictureFile); Halt end; For hh:=0 to planes-1 do begin CmpID.C:=ReadByte; vv:=ReadByte; CmpID.H:=Hi4(vv); CmpID.V:=Lo4(vv); CmpID.T:=ReadByte end; method:=b end; ... ReadByte/ReadWord - чтение байта/слова из файла Lo4/Hi4 - выделяет младшую/старшую часть байта Вначале следуют: разрядность данных (обычно 8 бит, остальные значения можно не обрабатывать); высота, ширина картинки в пик─ селах; количество компонент (определяет тип изображения: 1=чёр─ но-белое, 3=цветное). Далее для каждой компоненты следуют 3 бай─ та: тип компоненты (1=Y,2=Cb,3=Cr); сэмплинг фактор; номер таб─ лицы квантизации. Все эти параметры необходимо сохранить в соот─ ветствующих переменных и массивах, они нам понадобятся позже. DHT: Определить таблицу Хаффмана (ТХ): ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - $ff, $c4 (DHT) - информационный байт ТХ: бит 0..3: номер ТХ (0..3, иначе ошибка) бит 4: тип ТХ, 0=DC таблица, 1=AC таблица бит 5..7: не используется=0 - 16 байтов: количество символов с кодами длиной 1..16, сумма этих байтов есть общее количество кодов, должно быть - n байтов: таблица, содержащая символы в порядке увеличения длины кода (n = общее число кодов) Комментарий: - один DHT сегмент может содержать несколько таблиц, ... $C4:begin Repeat { Read & compile Huffman Tables } hh:=ReadByte; For vv:=0 to 15 do HT.L:=ReadByte; aa:=0; For vv:=0 to 15 do HT.V:=ReadByte;inc(aa); end; c:=0;aa:=0; For vv:=0 to 15 do begin if HT.L>0 then begin HT.H2.SV:=aa-c; HT.H2.EV:=aa+HT.L; end; For m:=1 to HT.L do begin HT.H1.V:=HT.V; if vv HT.H1.L:=vv+1; HT.H1.LV:=HT.V; end; inc(aa);inc(c) end; c:=c shl 1; end; Until FilePtr=0; end; ... Здесь несколько сложнее. Дело в том,что мало просто загрузить эти таблицы. Необходимо также преобразовать их в удобный для ра─ боты декодера формат. Поэтому остановимся на этом поподробней. Для начала немного теории. Хаффман относится к статистическому кодированию, то есть символам с большим числом вхождений в файл присваивается код с меньшей разрядностью, с меньшим числом - бо─ льшая разрядность. Таким образом образуется символьный алфавит с непропорциональными длинами присвоенных ему кодов. За счет этого достигается сжатие групп символов. В результате чего образуется выходной битовый поток данных. Для успешного декодирования бито─ вого потока необходимо иметь таблицы соответствия символов и их кодов соответствующей длины. Нас будут интересовать коды длин от 0 до 15, то есть 16 бит максимум. Вернёмся к нашему фрагменту кода. В начале стоит информацион─ ный байт, в нём: биты 0..3 - номер таблицы Хаффмана; бит 4 - тип таблицы 0=DC/1=AC. За ним следует 16 байт, которые описывают количество символов с длиной кодов от 1 до 16, сумма этих байтов есть общее количество кодов и не должна превышать 256. Потом идут символы в порядке увеличения длин кодов. Внимание!!! Идут символы, но не их коды. То есть коды нам ещё придётся им присво─ ить. Один DHT сегмент может иметь в себе несколько таблиц,каждую со своим информационным байтом. Всего таких таблиц может быть 8: 4 для DC и 4 для AC. Мы имеем таблицу символов и их длин. Теперь нам необходимо определить коды Хаффмана для каждого символа. Делается это по следующему алгоритму: вначале стартовый код c = 0; по порядку проходим все символы нашей таблицы от длины 1 до 16; на каждой итерации увеличиваем значение кода на единицу; при изменении длины кода умножаем код на 2, что равносильно сдвигу кода на один разряд влево. В результате имеем полную таб─ лицу всех символов и соответствующих им кодов Хаффмана. Что с ней делать дальше, станет понятно позже. Пока нам необходимо просто сохранить все эти данные. DQT: Определить таблицу квантизации (ТК): ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - $ff, $db (DQT) - длина (старший, младший байт) - информационный байт ТК: бит 0..3: номер ТК (0..3, иначе ошибка) бит 4..7: точность ТК, 0 = 8 бит, иначе 16 бит - n байт ТК, n = 64*(точность+1) Комментарий: - один DQT сегмент может содержать несколько таблиц, каждая со своим информационным байтом. - для точности 1 (16 бит) порядок следования - старший, потом младший (для каждого из 64 слов). ... $DB: begin Repeat { Define Quantization Tables } hh:=ReadByte; For vv:=0 to $3F do if Hi4(hh)=0 then qtmp:=ReadByte; for m:=0 to 63 do Quant:=qtmp]; for v:=0 to 7 do for w:=0 to 7 do begin if w=0 then cw:=frac else cw:=round(frac*cos((w*PI)/16)*sqrt(2)); if v=0 then cv:=frac else cv:=round(frac*cos((v*PI)/16)*sqrt(2)); cw:=(cw*cv) shr prec; Quant:=mul1(Quant,cw); end; Until FilePtr=0; end; ... Таблицы квантизации необходимы для восстановления частотной матрицы и имеют размерность 8x8, то есть всего таких коэффициен─ тов в одной матрице будет 64. На листинге: вначале считывается информационный байт, в нём биты 0..3 - номер таблицы квантизации от 0 до 3; биты 4..7 - разрядность элементов матрицы (0=8 бит, иначе 16 бит). Далее выполняется чтение и масштабирование элеме─ нтов. Один DQT сегмент может содержать несколько таблиц кванти─ зации, каждую со своим информационным байтом. Большинство жпегов рассчитаны на 8-битные таблицы. DRI: Определить интервал перезапуска: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - $ff, $dd (DRI) - длина (старший, младший байт) = 4 - рестарт интервал (старший, младший байт) в единицах MCU блоков - это значит, что через каждые n MCU блоков может быть найден маркер RSTn. Первый маркер должет быть RST0, затем RST1, и так далее, до RST7, затем снова RST0. ... $DD: begin RestartInterval:=ReadWord end ... Всё, что необходимо сделать,- это сохранить его в переменной. Отмечу, что встречаются они крайне редко. SOS: Начало сканирования: ~~~~~~~~~~~~~~~~~~~~~~~~~ - $ff, $da (SOS) - длина (старший, младший байт), 6+2*(кол.компонент сканирования) - количество компонент сканирования (1 байт), должно быть >= 1 и - для каждого компонента: 2 байта - идентификатор компонента (1=Y, 2=Cb, 3=Cr), смотреть SOF0 - используемая таблица Хаффмана: - бит 0..3: AC таблица (0..3) - бит 4..7: DC таблица (0..3) - 3 байта, должны быть пропущены (???) Комментарий: - Данные жпега следуют сразу за SOS сегментом. $DA: begin m:=ReadByte; { Start Of Scan } For hh:=0 to m-1 do begin Scan.Cmp:=ReadByte; vv:=ReadByte; Scan.TD:=Hi4(vv); Scan.TA:=Lo4(vv) end; Scan.Ss:=ReadByte; Scan.Se:=ReadByte; vv:=ReadByte; Scan.Ah:=Hi4(vv); Scan.Al:=Lo4(vv) end; За ним следует количество сканируемых компонент - обычно 1 либо 3. Далее для каждой компоненты следуют 2 байта: 1-й - иден─ тификатор компоненты (1=Y, 2=Cb, 3=Cr), 2-й - Номер используемой таблицы Хаффмана, здесь биты 0..3 = AC таблица (0..3), 4..7 = DC таблица (0..3). Затем идут 3 байта которые необходимо пропус─ тить. Как было уже сказано раньше, этот маркер является послед─ ним, за ним непосредственно следуют сжатые данные жпега. Итак, все приготовления сделаны, теперь необходимо переходить непосредственно к самому процессу декодирования жпега.Для начала объясню, как расположены сжатые данные. Информация в жпеге хра─ нится блоками 8x8, то есть по 64 байта на каждую из компонент Y/Cb/Cr. Хотя это частный случай,когда сэмплинг фактор 1:1:1, но об этом позже. Сразу за Y компонентой следуют Cb и Cr, таким об─ разом, мы имеем всего 3*64 байта на блок 8x8 изображения. Блоки начинаются с левого верхнего угла изображения и идут слева направо и сверху вниз. То есть мы постепенно спускаемся вниз. В конце этого битстрима стоит маркер конца жпега EOI, который нам не обязательно отслеживать, ведь мы и так уже знаем сколько пик─ селей, а соответственно, и блоков в нашем жпеге. Все байтовые выравнивания маркеров осуществляются заполнением оставшихся би─ тов единицами, поэтому, если в потоке встречается байт FF, его необходимо пропускать. Общий список стадий декодирования выглядит следующим образом: 1) Хаффман декодер (декодирование DC/AC коэффициентов) 2) Деквантизация вектора из 64 элементов 3) Зиг-Заг сортировка и восстановление блока 8x8 4) Применение к блоку ОДКП Повторить первые 4 стадии для каждого блока 8x8, каждого ком─ понента изображения Y/Cb/Cr. 5) Масштабирование Cb/Cr 6) Преобразование уровня 7) Преобразование YCbCr->RGB Все эти стадии описывают лишь декодирование одного блока пик─ селей MCU. Для остальных необходимо повторить эти стадии,попутно считывая данные из файла и копируя их в соответствующее место на экране или в буфере. Рассмотрим подробно каждую стадию. 1. Хаффман декодер Все данные закодированы Хаффманом, этим достигается конечное сжатие жпега. Что представляет собой этот вид кодирования? Как я уже писал, каждому кодируемому символу сопоставляется код Хаффмана в зависимости от частоты появления символа в потоке. Чем меньше вероятность появления символа, тем большей длины код ему назначается, и наоборот. Тем самым происходит так называемое непропорциональное кодирование. За счёт этого производится опти─ мизация избыточности. В результате мы имеем битовый поток (бит─ стрим). Так как данные имеют битовую структуру, а текущий код имеет неизвестно какую длину, наш дисковый драйвер должен уметь читать данные последовательно бит за битом. Далее на каждой ите─ рации необходимо добавлять бит к уже имеющимся и проверять соот─ ветствие по таблицам Хаффмана.Если код найден,то раскодированное значение сохраняется, иначе продолжается декодирование. Встаёт вопрос, как можно быстро найти текущий код в таблице? Вначале приведу процедуру чтения битового потока: procedure NextBit(var V:byte); begin V:=(V shl 1)+Read1bit end; function Read1bit:byte; { Take one bit from Current Byte } begin if Current_bit=0 then begin ReadByte; if Current_byte=$FF then begin Repeat ReadByte Until Current_byte if (Current_byte>=$D0) and (Current_byte FillChar(DC,SizeOf(DC),0);ReadByte; end; if Current_byte=0 then Current_byte:=$FF; end end; Read1bit:=(Current_byte shr 7) and 1; Current_byte:=Current_byte shl 1; inc(Current_bit); if Current_bit=8 then Current_bit:=0 end; Как видно, процедура NextBit просто добавляет следующий бит к переменной V. Функция Read1bit возвращает следующий считаный бит из потока. Она также пропускает байт FF и инициализирует все DC коэффициенты, в случае, если встречается маркер RST0-RST7 (D0-D7). Теперь перейдем к сути, декодеру: function hd(T,C:byte):byte; { Decoding Huffman Code from bitstream } var v,code:byte; begin v:=0; { L - HuffCode len; L=0 - no code; L=len+1 (1..8) lookup } NextBit(v); if HT.H1.L=1 then begin hd:=HT.H1.LV;exit end; NextBit(v); if HT.H1.L=2 then begin hd:=HT.H1.LV;exit end; NextBit(v); if HT.H1.L=3 then begin hd:=HT.H1.LV;exit end; NextBit(v); if HT.H1.L=4 then begin hd:=HT.H1.LV;exit end; NextBit(v); if HT.H1.L=5 then begin hd:=HT.H1.LV;exit end; NextBit(v); if HT.H1.L=6 then begin hd:=HT.H1.LV;exit end; NextBit(v); if HT.H1.L=7 then begin hd:=HT.H1.LV;exit end; NextBit(v); if HT.H1.L=8 then begin hd:=HT.H1.LV;exit end; { SV - Start Value (aa-w); EV - Next Code Len Value } NextBit(v);code:=v+HT.H2.SV; if code NextBit(v);code:=v+HT.H2.SV; if code then begin hd:=HT.H1.V;exit end; NextBit(v);code:=v+HT.H2.SV; if code then begin hd:=HT.H1.V;exit end; NextBit(v);code:=v+HT.H2.SV; if code then begin hd:=HT.H1.V;exit end; NextBit(v);code:=v+HT.H2.SV; if code then begin hd:=HT.H1.V;exit end; NextBit(v);code:=v+HT.H2.SV; if code then begin hd:=HT.H1.V;exit end; NextBit(v);code:=v+HT.H2.SV; if code then begin hd:=HT.H1.V;exit end; NextBit(v);code:=v+HT.H2.SV; if code then begin hd:=HT.H1.V;exit end; hd:=$ff; end; Хочу привести вам результаты своих экспериментов в данной области. Еще раз предупреждаю, что практически всё, о чем я буду говорить и говорил раньше, есть результат моих собственных домы─ слов, поэтому может отличаться от общепринятых методов и форму─ лировок. Как выяснилось, большая часть кодов не превышает 8 бит, таким образом, можно создать 256-байтную таблицу перекодировки. В этом случае декодирование происходит экстремально быстро: всё, что нам нужно - просто взять из таблицы уже готовое значение. В случае, если код >8 бит, тут немного сложнее. Нам нужно знать все начальные позиции SV и конечные позиции EV для длин кодов 8..16. То есть надо создать табличку значений, а вернее, три таблички. Первая будет содержать последовательно все наши закодирован─ ные символы, назовём её таблицей V. Расскажу, как сформировать две другие. Для каждой длины кода от 8..16 нужно задать началь─ ную позицию SV = смещению первого кода в таблице V минус сам первый код. Например, у нас есть код %110 = 6, идёт он под номе─ ром 5 в таблице, тогда SV = 5 - 6 = -1. Третья таблица должна содержать конечную позицию EV для текущей длины кода. Как и в предыдущем случае, для всех длин кодов от 8..16 нужно задать EV = смещению первого кода в таблице V плюс количество кодов этой длины. По предыдущему примеру, если количество кодов теку─ щей длины L = 4, то EV = 5 + 4 = 9. Всё это было приведено рань─ ше в куске кода обработки маркера DHT. Теперь объясню,для чего это всё нужно.В соответствии с нашими таблицами,как показано во фрагменте кода выше,поиск значения ко─ да выполняется следующим образом.Для соответствующей длины кода: складываем текущий код и SV, code = v + SV; если code Ред.: Поскольку биты из потока приходится читать в любом ме─ тоде декодирования Хаффмана, то проще (и,как ни странно,быстрее, если вести разговор о процессоре Z80) декодировать коды непосре─ дственно по дереву, бит за битом, не используя дополнительных таблиц. Соответствующие процедуры вы можете позаимствовать из распаковщика smallunr.H (см.в приложении). В ZXUnRar декодирова─ ние тоже идёт побитно, но для этого предварительно генерируется процедура разбора кодов Хаффмана на основе текущего дерева, поэ─ тому получается ещё более высокая скорость декодирования. Если вы думаете, что процесс декодирования коэффициентов на этом заканчивается, то вы ошибаетесь - он только начинается:). Пока мы имеем только раскодированные байты,из которых необходимо получить коэффициенты DC/AC. Плюс ко всему для увеличения эффек─ тивности сжатия было добавлено RLC сжатие последовательности нулей. Посмотрим, как раскодировать эти коэффициенты. Декодирование DC коэффициента производится по следующему ал─ горитму: В начале DC = 0 а) извлечение соответствующего кода Хаффмана (проверяем в таблице Хаффмана для DC) б) смотрим, к какой категории этот код принадлежит в) читаем N = биты категории, и определяем значение Diff = = (категория, N битов) г) DC = DC + Diff д) пишем DC в 64-элементный вектор: vector = DC Декодирование AC коэффициентов производится по следующему алгоритму: Для каждого AC коэффициента, пока не встретился EOB и AC_counter а) извлечение соответствующего кода Хаффмана (проверяем в таблице Хаффмана для AC) б) декодируем код Хаффмана в соответствии с (кол_пред_0, категория) в) читаем N=биты категории, и определяем значение AC = = (категория, N битов) г) пишем в 64х элементный вектор последовательность нулей = = кол_пред_0 д) увеличиваем AC_counter на кол_пред_0 е) пишем AC в 64-элементный вектор: vector = AC Фрагмент кода для чтения коэффициентов DC/AC выглядит следую─ щим образом: hb:=HD(0,Scan.TD[b]); vec:=DC[b]+Bits2Integer(Lo4(hb),ReadBits(Lo4(hb))); DC[b]:=vec;xx:=1; if method$C2 then Repeat hb:=HD(1,Scan.TA[b]); if hb=0 then Repeat vec:=0; inc(xx) Until xx>=64 else begin yy:=Hi4(hb); for m:=1 to yy do begin vec:=0; inc(xx) end; vec:=Bits2Integer(Lo4(hb),ReadBits(Lo4(hb))); inc(xx) end Until xx>=64; Объясню подробнее. Сначала определяем DC. Для этого нужно декодировать Diff. Кодируется он двумя элементами (кат, Nбит). В начале идут 4 бита (тетрада) категории, представляющие собой длину считываемого кода, которая и кодируется Хаффманом. То есть сначала декодируем её, а затем, уже зная длину кода Diff, читаем N бит. Далее идёт преобразование N битов в знаковое слово по следующим правилам: Значение Категория Биты 0 0 - -1,1 1 0,1 -3,-2,2,3 2 00,01,10,11 -7,-6,-5,-4,4,5,6,7 3 000,001,010,011,100,101,110,111 -15..-8,8..15 4 0000..0111,1000..1111 -31..-16,16..31 5 00000..01111,10000..11111 -63..-32,32..63 6 . -127..-64,64..127 7 . -255..-128,128..255 8 . -511..-256,256..511 9 . -1023..-512,512..1023 10 . -2047..-1024,1024..2047 11 . -4095..-2048,2048..4095 12 . -8191..-4096,4096..8191 13 . -16383..-8192,8192..16383 14 . -32767..-16384,16384..32767 15 . Преобразованием занимается следующий код: function Bits2Integer(bits:byte; value:word):integer; begin if (value and (1 shl (bits-1))>0) then Bits2Integer:=value else Bits2Integer:=-(value xor (1 shl bits-1)); end; В конце определяем значение DC как сумму предыдущего DC и найденного Diff. Итоговое значение сохраняется в векторе по ну─ левому смещению. Теперь о том, как определить коэффициенты AC. Здесь сложнее - их может быть несколько. Кроме того, дополнительно используется кодирование последовательности нулей (RLC). Для каждого элемента от 2 до 64 необходимо декодировать байт, содержащий в тетрадах данные (кол_пред_0, категория), где кол_пред_0 = количество предшествующих нулей. Далее от текущей позиции необходимо запол─ нить вектор нулями в количестве кол_пред_0. При этом, если байт равен (0,0), то это признак конца блока EOB, в этом случае оставшиеся элементы вектора заполняются нулями, и на этом запол─ нение вектора заканчивается. Если этого не произошло,выполняется чтение группы из Nбит бит и преобразование значения AC коэффици─ ента, как и в предыдущем случае. Декодирование DC/AC коэффициентов необходимо выполнять по со─ ответствующим таблицам Хаффмана. Ещё один момент. Существует два формата следования данных в жпеге. Первый называется baseline (маркер С0), о нём я и писал, в нём все 64 коэффициента вектора идут подряд. Жпеги этого типа открываются за один проход сверху вниз. Существует ещё один формат - progressive (маркер C2). В нём за один кадр считывается только один коэффициент, сначала DC, далее последовательно все AC. Таким образом один общий скан разбивается на несколько последовательно идущих сканов. Количес─ тво коэффициентов зависит от качества сжатия жпега. Для открытия жпега этого типа необходим кадровый буфер для хранения коэффици─ ентов DC/AC. Преимуществом данного типа является возможность увидеть кадр изображения, не дожидаясь конца файла. Чтение сле─ дующей порции коэффициентов будет лишь улучшать качество картин─ ки, кадр будет как бы фокусироваться. Ввиду сложности реализации прогрессивной развертки, я не стал поддерживать её полностью, сделав лишь чтение первого скана, содержащего DC коэффициенты. 2. Деквантизация вектора из 64х элементов На этой стадии выполняется восстановление оптимизированных коэффициентов вектора. Выполняется это следующим образом. На этапе подготовки было выполнено чтение всех необходимых нам таб─ лиц квантизации. Всё, что нам теперь нужно,- просто умножить все элементы нашего вектора на соответствующие элементы таблицы ква─ нтизации. Можно объединить эту стадию со стадией ОДКП (обратное ДКП), как поступил я сам. 3. Зиг-Заг сортировка и восстановление блока 8x8 На этапе сжатия, при переводе блока 8x8 в вектор,коэффициенты обходились зигзагом. Это было необходимо для лучшей группировки последовательности нулей. Теперь нам необходимо сделать обратную операцию - восстановить блок 8x8 из вектора. Приведу порядок следования коэффициентов в матрице: 0 1 5 6 14 15 27 28 2 4 7 13 16 26 29 42 3 8 12 17 25 30 41 43 9 11 18 24 31 40 44 53 10 19 23 32 39 45 52 54 20 22 33 38 46 51 55 60 21 34 37 47 50 56 59 61 35 36 48 49 57 58 62 63 То есть элементы вектора необходимо записывать в ячейки мат─ рицы, в соответствии с их порядковыми номерами. В результате мы имеем полностью восстановленную матрицу для последующей,пожалуй, самой важной из всех, стадии. 4. Применение к блоку ОДКП Это самая интересная часть декодирования. ОДКП (Обратное Дис─ кретное Косинусное Преобразование) относится к семейству преоб─ разований Фурье и выполняет преобразование данных из частотной области во временную. То есть на входе мы имеем матрицу частот, после применения ОДКП будет матрица дискретных значений, или яркости, пикселей. Главная трудность этой стадии состоит в том, что на самом деле преобразования Фурье выполняются слишком мед─ ленно. Не стану здесь расписывать всякие классические математи─ ческие формулы и выкладки, на эту тему можно написать целую книгу, приведу лишь самое, на мой взгляд, оптимальное решение. Существует семейство быстрых алгоритмов преобразования Фурье - ОБПФ (Обратное Быстрое Преобразование Фурье). Из множества дан─ ных методов я выбрал схему AA&N, как самую быструю. Единственный минус данного метода - небольшая потеря точности, хотя на глаз я её не заметил. Приведу фрагмент кода, считающий матрицу 1x8: ... { Even part } t0:=tout;t1:=tout; t2:=tout;t3:=tout; t10:=t0+t2;t11:=t0-t2;t13:=t1+t3; t12:=(t1-t3)*(2*c4)-t13; t0:=t10+t13;t3:=t10-t13; t1:=t11+t12;t2:=t11-t12; { Odd part } t4:=tout;t5:=tout; t6:=tout;t7:=tout; z13:=t6+t5;z10:=t6-t5; z11:=t4+t7;z12:=t4-t7; t7:=z11+z13; t11:=(z11-z13)*(2*c4); z5:=(z10+z12)*(2*c2); t10:=(2*(c2-c6))*z12-z5; t12:=(-2*(c2+c6))*z10+z5; t6:=t12-t7;t5:=t11-t6;t4:=t10+t5; tout:=t0+t7;tout:=t0-t7; tout:=t1+t6;tout:=t1-t6; tout:=t2+t5;tout:=t2-t5; tout:=t3+t4;tout:=t3-t4; ... Здесь: tout - рабочая матрица 1x8 i - номер текущей строки матрицы Константы: c2 = cos(2*PI/16); c4 = cos(4*PI/16); c6 = cos(6*PI/16); Данным кодом необходимо пройтись вначале по всем строкам на─ шей 8x8 матрицы, а затем по всем столбцам. Получается 16 итера─ ций: 8 на строки + 8 на столбцы. При обработке столбцов перед финальной записью результата следует разделить его на 8, этого требует специфика метода. Есть ещё одна тонкость, без которой алгоритм не будет работать. Перед обработкой начальную матрицу необходимо умножить на константу. Вот как это будет выглядеть: ... for j:=0 to 7 do for i:=0 to 7 do begin if i=0 then ci:=1 else ci:=cos((i*PI)/16)*sqrt(2); if j=0 then cj:=1 else cj:=cos((j*PI)/16)*sqrt(2); tout:=tin*ci*cj; end; ... Как видно, если номер элемента не нулевой,нужно умножить этот элемент на cos((i*PI)/16)*sqrt(2), иначе на единицу, то же самое и по j. Эти ухищрения делаются для уменьшения количества умноже─ ний в цикле обработки. Если предварительно перемножить данные константы с таблицами квантизации и объединить стадии 2 и 4, то есть включить в ОБПФ деквантизацию,можно выиграть немного скоро─ сти. Это и было проделано раньше при обработке маркера DQT, смо─ треть фрагмент кода. Все описанные выше этапы позволяют получить коэффициенты то─ лько одной компоненты (Y/Cb/Cr). Поэтому четыре первые стадии необходимо повторить для каждой компоненты, если, конечно, жпег полноцветный. Далее следует описание стадий уже после декодиро─ вания всех 3 компонент. ──────────────────────────────────────────────────────────────── 5. Масштабирование Cb/Cr В результате предыдущих стадий была получена информация о 3 компонентах Y/Cb/Cr. То есть 3 блока 8x8, описывающие пиксели изображения. На самом деле это является частным случаем, когда масштаб (сэмплинг фактор) компонент Y/Cb/Cr=1:1:1, но так бывает не всегда. Часто масштаб компонент принимается 2:1:1, что озна─ чает, что на 2 элемента яркости Y приходится по 1 элементу цвет─ ности Cb/Cr. Тоже самое происходит и по другой координате, то есть и по X, и по Y. Эти данные загружались раньше,при обработке маркера SOS. Существует понятие минимального кодированного блока - MCU (Minimum Coded Unit), которое описывает блок изображения. При сэмплинг факторе 1:1:1 MCU равен 8x8. При 2:1:1 MCU равен 16x16. Во втором случае получается, что данных Y компоненты в 4 раза больше, чем для Cb/Cr. Если представить блок 8x8 как DU (DataUnit), то последний случай запишется в виде: YDU, YDU, YDU, YDU, CbDU, CrDU. На 4 блока данных для яркости Y приходится по одному блоку цветности Cb/Cr. Такое допущение позволяет получить ещё большее сжатие при практически незаметном ухудшении качества картинки. С учётом сказанного для каждой компоненты необходимо также учитывать масштаб и выполнять полностью загрузку MCU. Блоки данных из 64 элементов распологаются в MCU слева направо, сверху вниз. После того, как будет загружена полностью информа─ ция о всех компонентах, необходимо выполнить ресэмплинг, то есть отмасштабировать,если необходимо, компоненты Cb/Cr. При сэмплинг факторе 2:1:1 в результате получим 3 матрицы элементов 16x16. В случае 1:1:1 все компоненты идут один к одному,и масштабирование выполнять не нужно, MCU будет равен 8x8. В принципе, бывают и другие вариации, например, Cb/Cr по X может быть на 2 юнита (1:1:1), а по Y на 1 (2:1:1). Но такие случаи бывают крайне редко, я не стал морочить ими голову и поддержал только два пер─ вых. 6. Преобразование уровня Необходимо преобразовать значения наших компонент из знаковой в беззнаковую форму. Сделать это очень просто - всё, что нужно,- это прибавить 128 ко всем 8-битным знаковым значениям наших ком─ понент. На данном этапе также выполняются регулировки яркостного и цветового баланса. Если в таблицах яркости и цветности учесть сразу и значение уровня, то данное преобразование будет выполня─ ться автоматически. 7. Преобразование YCbCr->RGB Это преобразование является заключительным этапом декодирова─ ния и осуществляет преобразование из цветового пространства YCbCr в формат экранных пикселей RGB. Делается это по стандарт─ ным формулам: R = Y + 1.402 *(Cr-128) G = Y - 0.34414*(Cb-128) - 0.71414*(Cr-128) B = Y + 1.772 *(Cb-128) Все значения YCbCr - 8 битные беззнаковые. В результате имеем декодированные пиксели изображения в формате true color (по 8 бит на компоненту). ──────────────────────────────────────────────────────────────── Вот,собственно,и всё,о чём я хотел вам рассказать.Изначально, правда, задумывалось написать статью в формате спековского асма, но, учитывая неподъёмность исходников, пришлось отказаться от этой затеи и расписать на примере пасовских фрагментов. Можно было бы ещё написать про масштабирование полученного изображе─ ния, про его обработку выходными фильтрами, но это тема отдель─ ной статьи. Да и без этого, думаю, информации для размышления подкинул достаточно. Так что, господа кодеры, изучайте, думайте и пишите качественные декодеры жпега для нашего любимого спекки. Ред.: В приложении лежит просмотрщик xjpeg by scor^3umf и исходники этого просмотрщика (публикация исходников не означает, что автор забросил этот проект - перед внесением каких-либо изменений свяжитесь с автором по адресу [email protected] ).

    Алгоритм разработан группой экспертов в области фотографии (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х8, на которых яркость и цвет меняются сравнительно плавно. Вследствие этого, при разложении матрицы такой области в двойной ряд по косинусам (формулы ниже) значимыми оказываются только первые коэффициенты. Таким образом, сжатие в JPFG осуществляется за счет плавности изменения цветов в изображении.

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

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

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

    Работа алгоритма.

    Пусть сжимается 24-битное изображение.

    Шаг I.

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

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

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

    Обратное преобразование осуществляется умножением вектора YUV на обратную матрицу:

    Шаг 2.

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

    Шаг 3.

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

    В упрощенном виде то преобразование можно представить так:

    Шаг 4.

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

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

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

    Шаг 5.

    Переводим матрицу 8x8 в 64-элементный вектор при помощи зигзагообразного сканирования, т.е. выбираем элементы с индексами (0.0). (0.1). (1.0). (2.0)...

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

    Шаг 6.

    Свертываем вектор с помощью алгоритма группового кодирования. При этом получаем пары типа (пропустить, число), где “пропустить” - счетчик пропускаемых нулей, а "число" - значение, которое необходимо поставить в следующую ячейку.

    Так, вектор будет свернут в пары (0, 42) (0, 3) (3, -2) (4, 1)

    Шаг 7.

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

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


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

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

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

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

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

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

    Последнее требование сделало возможным появление цифровых фотоаппаратов - устройства, размером с небольшую видеокамеру, снимающие 24-битовые фотографии на 10-20 Мб флэш-карту с интерфейсом PCMCIA. Потом на карта вставляется в разъем на ноутбуке и соответствующая программа позволяет считать изображения. Если бы алгоритм был несимметричен, было бы неприятно долго ждать, пока аппарат "перезарядится" - сожмет изображение.

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

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

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

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

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

    Коэффициенты компрессии: 2-200 (Задаётся пользователем).

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

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

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