Алгоритм сжатия изображения JPEG

Алгоритм JPEG разработан специально для сжатия изображений группой экспертов в области фотографии JPEG (Joint Photographic Expert Group) и разработан на основе ДКП.

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

Обычно внешне матрица имеет хорошо заметную особенность. Численные значения элементов матрицы быстро уменьшаются от левого верхнего угла к правому нижнему углу. Таким образом, в левом верхнем углу размещаются самые важные данные, а в правом нижнем – наименее важные. Используя это факт можно устранить наименее значимые данные. Для этого следует провести квантование преобразованных данных.

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

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

Q(i,j) = 1 + ((1 + i + j) q);

Где Q(i,j) – матрица делителей,

q - параметр качества.

Путем выбора параметра q можно управлять величинами делителей и регулировать степень сжатия. Например, при q = 2 получится матрица следующего вида (Рис.3.6):

Риунок 3.6. Пример матрицы квантования.

После деления 64 элементов матрицы на элементы матрицы Q(i,j) в качестве результата матрицу, у которой:

- Появится большое количество дополнительных нулевых значений,

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

Для экономичной записи требуется изменить порядок обхода полученных значений таким образом, чтобы последовательности нулевых элементов были бы как можно длиннее. Одним из возможных способов изменения порядка обхода является способ зиг-заг (рис3.7).

Рисунок 3.7. Преобразования двумерной матрицы в одномерную последовательность по способу «зигзаг».

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

Реализация алгоритма включает в себя рад последовательных действий, который иллюстрируется на рис. 3.8 .

Рисунок 3.8. Последовательность операций при реализации алгоритма JPEG.

1. Изображение при необходимости переводится в формат YUV.

2. Производится дискретизация цветоразностных U и V сигналов в соответствии с форматом 4:2:0. Разбиение изображения на фрагменты размером 8 х 8 элементов. Далее обработка сигналов яркости и цветности может производиться независимо и параллельно.

3. Дискретное косинусное преобразование выполняется применительно ко всем блокам размером 8 х 8 элементов.

4. Квантование в соответствии с выбранным параметром качества.

5. Сканирование «зигзаг» для получения одномерной последовательности из 64 элементов.

6. Алгоритм RLE применяется к одномерной последовательности.

7. Алгоритм Хаффмана применяется к уже сжатой с помощью RLE последовательности.

8. П.п. 3 – 7 выполняются для всех блоков форматом 8 х 8 элементов и для всех цветовых плоскостей.

Основные особенности метода JPEG состоят в следующем:

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

2. Большое число параметров, позволяющих искушенному пользователю экспериментировать с настройками метода и добиваться необходимого баланса сжатие/качество.

3. Хорошие результаты для любых типов непрерывно-тоновых изображений независимо от их разрешения, пространства цветов, размера пикселов или других свойств.

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

5. Возможность использования сжатия без потерь информации при не очень высоком коэффициенте сжатия.