Тема №8. Сжатие растровых изображений

1. Компьютерная графика

Москин Николай Дмитриевич
Институт математики и информационных
технологий
Петрозаводский государственный университет

2. § 8 Сжатие растровых изображений. Алгоритм JPEG

Сжатие без потерь: в ходе
цикла сжатие/восстановление
не происходит потери
информации.
Общим свойством всех схем
сжатия является наличие
данных, для которых «сжатая»
версия будет больше
несжатой.

3. Групповое кодирование RLE

Простая техника замены
серии последовательных
пикселей одного цвета кодом
цвета и количеством
пикселей в серии называется
групповым кодированием
(Run-Length Encoding - RLE).
Его эффективность зависит
от сжимаемого изображения.

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

Данный подход называется кодированием переменной
длины (variable-length coding), первые работы появились
в конце 1940-х годов. Самым известным алгоритмом
этого класса является кодирование Хаффмана.
Данные кодируются так, чтобы для хранения наиболее
часто встречающихся значений требовалось меньше
битов. Например:
код наиболее распространенного цвета кодируется
одним битом,
следующая группа часто встречающихся цветов двумя битами и т.д.

5. Схемы сжатия со словарем

С конца 1970-х годов схемы кодирования переменной
длины в значительной мере уступили место схемам
сжатия со словарем (dictionary-based schemes).
В этих алгоритмах строится таблица, или словарь, в
которую вводятся строки байтов встречающиеся во
входных данных; затем все вхождения этих строк
заменяются указателем, обращающимся к словарю.
Здесь используются коды фиксированной длины,
которые, однако, указывают на строки переменной
длины в словаре.

6. Технологии LZ77, LZ78 и LZW

LZ77 и LZ78 (авторы Abraham Lempel и Jacob
Ziv, опубликованы в 1977 и 1978 г.). На свободно
распространяемой версии LZ77 основан метод
сжатия в PNG, как и несколько известных
универсальных программ сжатия, подобных
PKZIP.
LZW - разновидность алгоритма LZ78,
разработанная Терри Уелшем (Terry Welsh),
используется в GIF.

7. Сжатие с потерями

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

8. Сжатие JPEG

JPEG – это аббревиатура от названия организации
Joint Photographic Experts Group (Объединенная группа
экспертов в области фотографии).
Исходное изображение представляется двумерной
матрицей, элементами которой являются цвет или
яркость пикселя. Упаковка значений матрицы
выполняется за три этапа.
Дискретное косинус-преобразование
Квантование
Вторичное сжатие

9. Сочетание сигналов различной частоты

Любую периодическую волну
можно разложить на набор
правильных синусоид с разными
частотами (частота – это
количество повторений сигнала в
единицу времени).
На рисунке показано, как
сочетание синусоидальных волн с
частотами f, 3f, 5f, 7f и т.д. образует
сигнал похожий на меандр
(прямоугольное колебание).

10. Преобразование Фурье

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

11. Представление меандра в частотной области

12. Представление сигнала в частотной области

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

13. Представление изображения

Яркость изображения можно рассматривать
как сигнал, который можно разложить на
составляющие его частоты.
Каждый пиксель для своих координат x и y
дает значение z, поэтому изображение
можно рассматривать как сложный
трехмерный сигнал.

14. Трехмерное изображение ириса

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

Дискретное косинус-преобразование
(Discrete Cosine Transform - DCT) подобно
преобразованию Фурье, раскладывает
сигнал на составляющие его частоты.
На вход ДКП подается массив пикселей,
по которому вычисляется набор коэффициентов, представляющих амплитуду
частотных компонентов изображения (по
двум направлениям x и y).

16. Квантование JPEG

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

17. Квантование JPEG

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

18. Обработка коэффициентов

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

19. JPEG - восстановление

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

20. Артефакты сжатия

При низком качестве сжатия на изображении
становятся видимыми квадраты размером 8×8,
к которым применяется ДКП, и появляются
границы.
Подобные нежелательные элементы на сжатом
изображении называются артефактами
сжатия.

21. Артефакты сжатия