Перевод в цветовое пространство YCbCr

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

Выбор Kr и Kb зависит от оборудования. Обычно берётся Kb=0.114;Kr=0.299. В последнее время также используется Kb=0.0722;Kr=0.2126, что лучше отражает характеристики современных устройств отображения.

 

Субдискретизация компонент цветности

После перевода в цветовое пространство YCbCr выполняется дискретизация. Возможен один из трёх способов дискретизации:
4

·:4:4 – отсутствует субдискретизация;

· 4:2:2 – компоненты цветности меняются через одну по горизонтали;

· 4:2:0 – компоненты цветности меняются через одну строку по горизонтали, при этом по вертикали они меняются через строку.

При использовании второго или третьего способа мы избавляется от 1/3 или 1/2 информации соответственно. Очевидно, что чем больше информации мы теряем, тем сильнее будут искажения в итоговом изображении.

 

Дискретное косинусное преобразование

Изображение разбивается на компоненты 8*8 пикселов, к каждой компоненте применятся ДКП. Это приводит к уплотнению энергии в коде. Преобразования применяются к компонентам независимо.

 

Квантование

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

 

Зигзаг-обход матриц

Зигзаг-обход матрицы – это специальное направление обхода, представленное на рисунке:

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

 

RLE- кодировние

Используется особый вид RLE-кодирования: выводятся пары чисел, причём первое число в паре кодирует количество нулей, а второе – значение после последовательности нулей. Т.е. код для последовательности 0 0 15 42 0 0 0 44 будет следующим (2;15)(0;42)(3;44).

 

Кодирование методом Хаффмана

Используется описанный выше алгоритм Хаффмана. При кодировании используется заранее определённая таблица.
Алгоритм декодирования заключается в обращении выполненных преобразований.
К достоинствам алгоритма можно отнести высокую степень сжатие (5 и более раз), относительно невысокая сложность (с учётом специальных процессорных инструкций), патентная чистота. Недостаток – артефакты, заметные для человеческого глаза.

 

Фрактальное сжатие

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

 

1.Разделение изображения на неперекрывающиеся области (домены). Набор доменов должен покрывать всё изображение полностью.

2.Выбор ранговых областей. Ранговые области могут перекрываться и не покрывать целиком всё изображение.

3.Фрактальное преобразование: для каждого домена подбирается такая ранговая область, которая после аффинного преобразования наиболее точно аппроксимирует домен.

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

Этапы восстановления изображения:

 

1.Создание двух изображений одинакового размера A и B. Размер и содержание областей не имеют значения.

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

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

4.Шаги 3 и 4 повторяются до тех пор, пока изображения A и B не станут неразличимыми.

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