| К следующей главе | К оглавлению | К предыдущей главе |
Алгоритм компрессии JPEG был разработан группой экспертов в области фотографии специально для сжатия 24-битных изображений. JPEG — Joint Photographic Expert Group — подразделение в рамках ISO — международной организации по стандартизации. В целом алгоритм основан на дискретном косинусном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.
Для этого используется квантование коэффициентов. При этом преобразовании теряется часть информации, но могут достигаться большие коэффициенты сжатия.
Рассмотрим работу алгоритм подробнее. Предположим для примера, что мы сжимаем 24-битное изображение. Тогда весь алгоритм представляет собой несколько последовательных шагов:
Шаг 1. Преобразование цветового пространства [RGB] в [YcbCr].
Шаг 2. Разбиение изображения на блоки размером 8*8 пикселей.
Шаг 3. Дискретное косинусное преобразование
Шаг 4. Квантование
Шаг 5. Зигзаг-сканирование
Шаг 6. Групповое кодирование (RLE)
Шаг 7. Кодирование по Хаффману
Вся дальнейшая работа производится именно с этим цветовым пространством. В нем Y— яркостная составляющая, а Cr, Cb— компоненты, отвечающие за цвет (хроматический красный и хроматический синий).
Преимущством представления цвета через YCrCb, по сравнению с RGB, является то, что оно наиболее близко к "естественному", тому, которое неосознанно выполняет человек. Y-компонента, или яркость, тесно связана с качеством картинки.
Человеческий глаз устроен таким образом, что наиболее чувствителен именно к яркостной составляющей изображения (Y-компонента) и наименее к цветовым. Причина этого лежит в физиологии. Глаз, имеет два типа визуальных анализаторов: палочки и колбочки. Палочковый аппарат обладает большей чувствительностью, чем колбочковый. Палочковый аппарат начинает реагировать на яркости порядка 10-4…10-5 кд/м2, колбочковый на яркости порядка единиц кандел на квадратный метр. Таким образом, световой динамический диапазон глаза составляет около 109. Еще одно свойство нашего зрительного анализатора заключается в том, что палочковый аппарат абсолютно не чувствителен к цвету. Вечером, когда количества падающего на зрачок света не хватает для того, чтобы вызвать реакцию колбочки, все в какой-то мере теряет цвет.
Причем чувствительность человеческого глаза к разным цветам тоже величина не постоянная. Кривая, определяющая чувствительность глаза к различным длинам волн, называется кривой относительной видности. Следует заметить, что при существенном уменьшении яркости кривая относительной видности изменяется. (рис.2, кривая 2) При нормальных яркостях зрачок оказывается более чувствителен к нижней части цветового спектра, нежели к верхней. Формат JPG как раз и учитывает эти особенности.Именно за счет того, что человеческий глаз менее чувствителен к цвету, чем к яркости, появляется возможность архивировать массивы для Cr и Cb компонент с большими потерями и, соответственно, большими коэффициентами сжатия. Подобное преобразование уже давно используется в телевидении. На сигналы, отвечающие за цвет, там выделяется более узкая полоса частот.
Упрощенно перевод из цветового пространства RGB в цветовое пространство YCrCb можно представить так:
Обратное преобразование осуществляется умножением вектора YUV на обратную матрицу:
Шаг 2. Разбиение изображения на блоки размером 8*8 пикселей.
Разбиваем исходное изображение на матрицы 8х8. Если горизонтальный размер (Х) исходного изображения не делится на 8, то кодер должен сделать его делимым, дополняя остальные правые столбцы (пока Х не станет кратным 8). Аналогично, если размер Y не делится на 8, кодер должен дополнить строки. Поскольку каждый пиксел в блоке 8*8 имеет три компонента (Y, Cr, Cb), ДКП применяется отдельно к каждому блоку. Таким образом, из каждой матрицы изображения, размером 8*8 пикселей формируются три рабочие матрицы— по 8*8 бит отдельно для каждой компоненты. Изображение делится по компоненте Y— как и в первом случае, а для компонент Cr и Cb матрицы набираются через строчку и через столбец. Т.е. из исходной матрицы размером 16x16 получается только одна рабочая матрица ДКП. При этом, как нетрудно заметить, теряется 3/4 полезной информации о цветовых составляющих изображения и получается сразу сжатие в два раза. Так можно поступать благодаря работе в пространстве YCrCb. На результирующем RGB изображении, как показала практика, это сказывается не сильно.
Блоки 8*8 обрабатываются слева направо и сверху вниз. Применяем ДКП к каждой рабочей матрице.
ДКП – разновидность гармонического (спектрального) анализа. Все преобразования, которые обычно проделываются над сигналами при их цифровой обработке, так или иначе сводятся к разложению функций в другие, так называемые базисные функции. В результате ДКП блока 8*8 образуется блок из 64 коэффициентов (амплитуды базисных функций). Коэффициент – это число, выражающее степень присутствия конкретной пространственной частоты, имеющейся в изображении. Такое двумерное представление дает заметить интересные особенности – видно, что горизонтальная координата положения базисной функции характеризует горизонтальную составляющую изменений изображения в исходном квадрате, вертикальная координата - вертикальную составляющую. Чем больше, к примеру, коэффициент перед базисной функцией, расположенной более справа, тем больше резких переходов изображения в горизонтальной плоскости мы имеем.
Например, если коэффициент перед 8-й базисной функцией (координаты [8,1]) максимален - мы имеем на изображении вертикальную сетку с шириной линий и промежутков в 1 пиксель (пиксели в горизонтальной плоскости чередуются с максимальной частотой), тогда как максимальный коэффициент 57-й базисной функции (координаты [1,8]) означал бы горизонтальную сетку изображения. Важно, что функции, характеризующие оба направления колебаний сразу, представляет собой не простое сочетание горизонтальных и вертикальных составляющих колебаний - это умножение 'горизонтальных' и 'вертикальных' косинусов. К примеру, 64-я базисная функция (координаты [8,8]) представляет собой максимальные колебания максимальной частоты в центре квадрата, затухающие до нуля к краям
Т.о. после ДКП получается матрица, в которой коэффициенты в левом верхнем углу соответствуют низкочастотной составляющей изображения, а в правом нижнем - высокочастотной.
В упрощенном виде это преобразование можно представить так:
,где
В стандарт JPEG включены рекомендованные МК, построенные опытным путем. В качестве примера приведем следующие матрицы квантования:
Матрица квантования яркостной компоненты Y q(u, v):
| 16 | 11 | 10 | 16 | 24 | 40 | 51 | 61 |
| 12 | 12 | 14 | 19 | 26 | 58 | 60 | 55 |
| 14 | 13 | 16 | 24 | 40 | 57 | 69 | 56 |
| 14 | 17 | 22 | 29 | 51 | 87 | 80 | 62 |
| 18 | 22 | 37 | 56 | 68 | 109 | 103 | 77 |
| 24 | 35 | 55 | 64 | 81 | 104 | 113 | 92 |
| 49 | 64 | 78 | 87 | 103 | 121 | 120 | 101 |
| 72 | 92 | 95 | 98 | 112 | 100 | 103 | 99 |
Матрица квантования цветоразностных компонент Y q(u,v):
| 17 | 18 | 24 | 47 | 99 | 99 | 99 | 99 |
| 18 | 21 | 26 | 66 | 99 | 99 | 99 | 99 |
| 24 | 26 | 56 | 99 | 99 | 99 | 99 | 99 |
| 47 | 66 | 99 | 99 | 99 | 99 | 99 | 99 |
| 99 | 99 | 99 | 99 | 99 | 99 | 99 | 99 |
| 99 | 99 | 99 | 99 | 99 | 99 | 99 | 99 |
| 99 | 99 | 99 | 99 | 99 | 99 | 99 | 99 |
| 99 | 99 | 99 | 99 | 99 | 99 | 99 | 99 |
На этом шаге осуществляется управление степенью сжатия, и происходят самые большие потери. Понятно, что, задавая МК с большими коэффициентами, мы получим больше нулей и, следовательно, большую степень сжатия, но потери будут больше, то есть ухудшится визуальное качество.
Матрицы для большего или меньшего коэффициентов сжатия получают путем умножения исходной матрицы на некоторое число Q-factor.
При декодировании на приемной стороне коэффициенты матрицы ДКП умножаются на элементы матрицы квантования, что восстанавливает верные значения коэффициентов, но с ошибкой округления.
С квантованием связаны и специфические эффекты алгоритма. При больших значениях коэффициента Q-factor потери в высоких и низких частотах в результате приводят к различного рода искажениям, классификация которых будет приведеня ниже.
Массив коэффициентов, извлекаемых из матрицы ДКП, содержит некоторое количество нулевых значений. Для того, чтобы способствовать объединению нулевых элементов в группы, используется зигзагообразное сканирование матрицы, начиная с левого верхнего угла, т.е. берем элементы с индексами (0,0), (0,1), (1,0), (2,0)...
Таким образом, в начале вектора мы получаем коэффициенты матрицы, соответствующие низким частотам, а в конце— высоким, большая часть которых имеет нулевое значение.
Свертываем вектор с помощью алгоритма группового кодирования (RLE - Run Length Encoding). При этом получаем пары типа (пропустить, число), где “пропустить” является счетчиком пропускаемых нулей, а “число”— значение, которое необходимо поставить в следующую ячейку. Так, вектор 42 3 0 0 0 -2 0 0 0 0 1 0 0 0 0 0 . будет свернут в пары (0,42) (0,3) (3,-2) (4,1) (ЕОВ).
(ЕОВ) –символ "конец блока"
Зигзаг-сканирование позволяет сгруппировать самый большой массив нулевых коэффициентов, обычно располагающийся в правой нижней части блока матрицы коэффициентов. Символ ЕОВ (конец блока) заменяет этот массив нулей.
Свертываем получившиеся пары кодированием по Хаффману с фиксированной таблицей. Малые серии нулей и малые величины ненулевых коэффициентов более вероятны. поэтому им ставятся в соответствие короткие кодовые слова. Символ ЕОВ кодируется самой короткой кодовой комбинацией.
Шестой и седьмой шаги представляют собой энтропийное кодирование. Процесс восстановления изображения в алгоритме JPEG полностью симметричен. Метод позволяет сжимать некоторые изображения в 10-15 раз без серьезных потерь.
Вверх На главную| К следующей главе | К оглавлению | К предыдущей главе |
