8. Сжатие изображений по блочному алгоритму jpeg.

Как известно, все множество цветовых оттенков может быть задано различными пропорциями яркости трех цветовых составляющих, - в частности, красного (Red – R), зеленого (Green – G) и голубого (Blue – B). В памяти компьютера изображение чаще всего представляется как матрица (растр) точек - пикселей.

(Наряду с таким «растровым» представлением существует и так называемое «векторное», когда элементы изображения - кривые – описываются математическими уравнениями. К «векторному» описанию изображения применимы способы сжатия данных без потерь. Здесь мы будем говорить о методах, применяемых по отношению к растровым изображениям).

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

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

Алгоритм JPEG. Включает следующие этапы:

1. Осуществляется переход от RGB - представление к так называемому кодированию YUV. Здесь Y – яркостная составляющая (Y=R+G+B), а U и V – цветовые (V=R, V=G). Оба способа взаимообратимы, но YUV–представление позволяет выделить яркостную составляющую, к которой нужно относиться более бережно, чем к цветовым

2. Выделяются блоки 8х8 пикселей. При этом каждой из составляющих YUV отвечает матрица коэффициентов Pij. (Например, в матрице U значение Pij=0 означает, что у данной точки отсутствует красная цветовая составляющая, а Pij=255 значит, что она будет максимально яркой).

3. В ыполняется так называемое «прореживание». Четверки блоков изображения 8х8 объединяются в «макроблоки» 16х16, а затем для цветовых составляющих U и V из соответствующих матриц исключаются все четные строки и столбцы. При этом матрица яркостной составляющей Y остается нетронутой (рис.8.). В итоге количество коэффициентов сокращается вдвое (вместе 4х3=12 блоков остается 6).

Рис.8 «Прореживание» в алгоритме JPEG

2. Для всех оставшихся блоков изображения выполняется так называемое дискретное косинус-преобразование (ДКП). При этом матрицы NxN (N=8) коэффициентов Р преобразуются в матрицы D в соответствии со следующей процедурой:

Смысл этого преобразования заключается в том, что коэффициенты d_ij отражают «амплитуду колебаний» яркости пикселей. Например, если все пиксели блока имеют одинаковую яркость, то максимальными будет коэффициент d₁₁ , а остальные d_ij = 0. Чем больше деталей в изображении, тем большими будут значения “удаленных” коэффициентов

Как правило, значения коэффициентов в направлении “обхода” (рис.9) быстро уменьшаются, и это дает возможность эффективно сжимать информацию, представлению в таком виде

Рис. 9 Направление обхода коэффициентов матрицы D, полученной в результате ДКП

5. Ключевой этап алгоритма – “огрубление” коэффициентов (рис.10)

Если все коэффициенты “отмасштабировать”, поделив, скажем, на 8, то длина кода для каждого из них сократится на 3 бита из 8. Но поскольку “удаленные” коэффициенты (правая нижняя часть матрицы) обычно малы, они просто обнуляются в результате масштабирования (рис.4.6). Нужно сказать, что именно на этом этапе информация о деталях изображения необратимо теряется.

Огрубление коэффициентов d_ij/8

Рис. 10 Огрубление коэффициентов матрицы D

Регулируя величину делителя, можно задавать соотношение – «степень сжатия – качество восстановленного изображения».

6. Последний этап – кодирование оставшихся коэффициентов. Он включает несколько шагов:

• коэффициенты записываются в цепочку в порядке “обхода” (в примере цепочка имеет вид 16 8 6 1 3 4 0 0 0 1… ;

• последовательности нулей в цепочке кодируются методом повторов;

• длины “нулевых” серий кодируются по Хаффману.

В результате подобного кодирования из примерно полутора тысяч бит, описывающиx блок, остается обычно несколько десятков: код изображения сжимается в десятки раз.