Алгоритмы сжатия изображений не рассматриваются в отрыве от классов изображений. Классом изображений будем называть совокупность изображений, применение к которым алгоритма архивации дает качественно одинаковые результаты. В данном случае разработанный алгоритм предназначен для класса изображений с небольшим количеством цветов и отсутствием плавных переходов цвета. Сюда относится деловая графика, всевозможные диаграммы и схемы.
Как и для большинства алгоритмов сжатия без потерь, будем представлять изображение как цепочку байт по строкам растра. Палитрой будем называть упорядоченную последовательность всех цветов, присутствующих в сжимаемом изображении.
Пусть каждый пиксел цвета кодируется смещением от предыдущего пиксела того же цвета. Кодирование всех цветов, в таком случае, становится избыточным. Избавимся от кодирований одно цвета, предполагая, что все пространство, не занятое закодированными цветами, занято им. Назовем этот цвет фоном. Очевидно, что предварительный анализ, назначающий наиболее часто встречающийся цвет фоном, может существенно повысить эффективность сжатия. Цвет фона будет стоять первым в палитре и далее никак не учитывается в алгоритме.
Шаги алгоритма:
1. Анализ изображения. Найдем наиболее часто встречающийся цвет и запишем его первым в палитру
2. Каждый последующий цвет будет кодироваться цепочкой вида:
{<смещение от начала файла><смещение от предыдущего байта данного цвета>*.. }
3. В конец цепочки будет записано два нулевых символа, так как смещение нулевой длины не может существовать
4. Повторение шага 2 до тех пор, пока в палитре есть цвета
5. Цепочки одного цвета из исходного файла будет выглядеть как цепочки смещений длиной 1. Заменим их на структуру вида:
{<нулевой символ><длина цепочки>}
Временная сложность алгоритма O(n). Симметричность, то есть отношение времени кодирования ко времени декодирования, алгоритма приблизительно равна единице.
Для иллюстрации работы представленного алгоритма рассмотрим следующий пример. Для наглядности приводимых ниже расчетов, сделаем следующее допущение: каждый цвет кодируется одним байтом. Следовательно, можно закодировать 255 цветов. Деловая графика, на которую направлен данный алгоритм, как правило, является 2-х или 4-х битными изображением. Поэтому в программной реализации может использовать 2 или 4 бита для кодирования одного цвета. Смещение также будем кодировать одним байтом.
Возьмем исходную последовательность, которая советуют классу изображений, к которому предлагается использовать разрабатываемый алгоритм:
AAABBBBBBBBAAAAAAAAAAAAAAAACCCCAAAABBСBA
Длина исходной последовательность – 40 байт.
Предположим, что был проведен предварительный анализ входной последовательности и, на основе него, была построена палитра цветов. Получим:
A – цвет фона,
ABC – палитра,
0 – управляющий символ.
Сжимаемая последовательность перед 5ым шагом:
4| 1| 1| 1 |1 |1 |1 |1| 25|1|2| 0| 0|29|1|1|1|7
Сжимаемая последовательность после 5го шага:
4|0|7|25|1|2|0|0|29|0|3|7
В сжатый файл, в итоге, будут записаны следующие данные:
A|B|C|4|0|7|25|1|2|0|0|29|0|3|7
Длина сжатой последовательности – 15 байт.
Ключевым отличием данного алгоритма от других алгоритмов сжатия изображении без потерь качества является то, что размеры исходного файла не увеличиваются при кодировании даже в случае плохо подходящих изображений. Это обусловлено тем, что наиболее часто встречающийся цвет не кодируется, а остальные пикселы цветов кодируются одним или менее символами. При увеличении количества цветов коэффициент сжатия в худшем случае будет стремиться к единице, но не превышать ее.
Библиографический список
- Тропниченко А.Ю, Тропниченко А.А “Методы сжатия изображений, аудиосигналов и видео: Учебное пособие” – СПб: СПбГУ ИТМО, 2009 г.
- Ватолин Д.С Алгоритмы сжатия изображений: “Методическое пособие” – М.: изд. отдел факультета ВМиК МГУ им. Ломоносова, 1999 г.
- Ватолин Д.С, Ратушняк А. и др. “Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео” – М.: ДИАЛОГ-МИФИ, 2002.