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

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

Для файлов графических изображений разработано множество схем и алгоритмов сжатия, основными из которых являются:

· Групповое сжатие;

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

· Сжатие по схеме LZW;

· Арифметическое сжатие;

· Сжатие с потерями;

· Преобразование цветов RGB цвета палитр и др.

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

Алгоритмы сжатия с потерями основаны на избыточности данных.

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

Рассмотрим подробнее первые два алгоритма сжатия.

Групповое сжатие представляет собой одну из самых простых схем.

Её смысл заключается в том, что серия повторяющихся величин заменяется единственным знаком этой величины с указанием их количества. На следующем примере можно легко заметить сокращение длины записи:

а а ббббббб с ддд ееее ааа – 2а 7б 1с 3д 4е 3а.

Данный алгоритм прост в реализации и хорошо сжимает файлы с большими однотонными областями. Используется во многих форматах растровых файлов.

Кодирование методом Хаффмана заключается в замене данных более эффективными кодами. Более короткие коды используются для замены более часто появляющихся величин. Например в выражении «абббсссддеееееееееф» есть шесть уникальных величин с частотами появления: а-1; б-3; с-3; д-2; е-9; ф-1. Для образования минимального кода используется двоичное дерево. Такой алгоритм объединяет в пары элементы, появляющиеся наименее часто, затем пара объединяется в один элемент с объединённой частотой. Это действие повторяется до тех пор пока все элементы не объединяться в пары.

Принцип кодирования в зависимости от частоты появления с помощью двоичного дерева формирования (выращивания) двоичных кодов подробно показан на рис. 9.6. Таким образом, кодирование выполняется в два этапа: создание статистической модели и собственно кодирование данных.

Следует отметить, что кодирование и декодирование данным методом достаточно длительный процесс.