Сжатие графических файлов

 

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

 

.

 

Возьмем матрицу преобразования:

 

.

(1.26)

 

Сначала найдем по правилам матричной алгебры произведение

 

,

 

Затем

 

.

(1.27)

 

Получим

 

.

 

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

 

.

 

Именно эта операция (квантования) и приводит к потере данных, хотя эта потеря мало отражается на исходных данных. В самом деле, легко восстановить из (3.27) матрицу С:

 

.

(1.28)

 

и, аналогично,

 

.

(1.29)

 

С помощью (3.28), (3.29) получим восстановленную приближенную матрицу исходных данных:

 

.

 

После квантования получим

 

.

 

Эта последняя матрица очень близка к исходной матрице D (!).

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

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

 

.

(1.30)

 

В (3.30)  – значение пикселя в строке x и столбце y квадратной матрицы пикселей размеров ;

 

 

Матрица одномерного DCT-преобразования использует расчетную формулу

 

.

(1.31)

 

Заметим, что величины

 

 

изменяются для  и  так что в результате из них можно построить следующую матрицу преобразования (для )

 

	1	1	1	1	1	1	1	1
	0,981	0,831	0,556	0,195	-0,195	-0,556	-0,831	-0,981
	0,924	0,383	-0,383	-0,924	-0,924	-0,383	0,383	0,924
	0,831	-0,195	-0,981	-0,556	0,556	0,981	0,195	-0,831
	0,707	-0,707	-0,707	0,707	0,707	-0,707	-0,707	0,707
	0,556	-0,981	0,195	0,831	-0,831	-0,195	0,981	-0,556
	0,383	-0,924	0,924	-0,383	-0,383	0,924	-0,924	0,383
	0,195	-0,556	0,831	-0,981	0,981	-0,831	0,556	-0,195

 

Эта матрица является ортогональной и построена по тем же принципам, что и матрица W, которую мы рассмотрели выше. Нам остается коротко охарактеризовать алгоритм сжатия JPEG, основу которого составляет DCT-преобразование.

В JPEG используется цветовая модель YCrCb, где Y передает светимость пикселя. Преобразование DCT выполняется отдельно к светимости Y, и отдельно к матрице, кодирующей хроматические числа Cr и Cb. К светимости Y применяется одномерное DCT преобразование. Для компоненты <Cr, Cb> выполняется разбиение изображения на матрицы пикселей . К каждой из таких матриц применяется двумерное DCT-преобразование. Таким образом, выполняется сжатие с потерей информации.

Сокращение JPEG происходит от слов Joint Photographic Expert Group – совместная группа по фотографии. Проект JPEG стал стандартом в 1991г. – принят международной организацией стандартов ISO.