УДК 004

АЛГОРИТМ СЖАТИЯ ИЗОБРАЖЕНИЙ БЕЗ ПОТЕРЬ КАЧЕСТВА

Шашков Б.Д.1, Полячкина О.А.2
1Пензенский государственный университет, профессор, кандидат технических наук
2Пензенский государственный университет, магистрант 2го года обучения

Аннотация
В статье рассматривается алгоритм сжатия изображений без потерь качества.

Ключевые слова: алгоритм сжатия изображений


IMAGE COMPRESSION ALGORITHM WITH NO LOSS OF QUALITY

Shashkov B.D.1, Polyachkina O.A.2
1Penza State University, professor, Ph.D. (kandidat nauk)
2Penza State University, 2nd year master degree student

Abstract
This article is about image compression algorithm with no loss of quality.

Рубрика: 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Шашков Б.Д., Полячкина О.А. Алгоритм сжатия изображений без потерь качества // Современные научные исследования и инновации. 2012. № 6 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2012/06/13380 (дата обращения: 30.09.2017).

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

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

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

Шаги алгоритма:

 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 байт.

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


Библиографический список
  1. Тропниченко А.Ю, Тропниченко А.А “Методы сжатия изображений, аудиосигналов и видео: Учебное пособие” – СПб: СПбГУ ИТМО, 2009 г.
  2. Ватолин Д.С Алгоритмы сжатия изображений: “Методическое пособие”  – М.: изд. отдел факультета ВМиК МГУ им. Ломоносова, 1999 г.
  3. Ватолин Д.С, Ратушняк А. и др. “Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео” – М.: ДИАЛОГ-МИФИ, 2002.


Все статьи автора «Ольга Полячкина»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: