Гибридный алгоритм сжатия дискретно-тоновой графики | Прикладная дискретная математика. 2014. № 7 (Приложение).

Представлен гибридный алгоритм - быстрый алгоритм сжатия без потерь информации, предназначенный для обработки изображений с резкими цветовыми переходами (дискретно-тоновых изображений). Гибридный алгоритм является соединением двух алгоритмов: специальной реализации RLE, способной выявлять как вертикальную, так и горизонтальную избыточность, и сдвигового алгоритма, который относится к семейству словарных методов сжатия. Сдвиговый алгоритм осуществляет замену трёх байтов, кодирующих цвет пикселя, на однобайтовую ссылку на пиксель с таким же цветом, встречавшимся ранее. Представленная реализация RLE способна выявлять области пикселей одного цвета трёх типов: вертикальные, горизонтальные линии и прямоугольники. Рассмотрены комбинированные алгоритмы, предполагающие последовательное выполнение гибридного алгоритма и некоторых известных алгоритмов сжатия. При этом каждый из результирующих наборов данных гибридного алгоритма обладает специфическим типом избыточности и поэтому сжимается по отдельности на втором этапе выполнения комбинированного алгоритма. Проводится практическое сравнение комбинированных алгоритмов между собой, а также с известными алгоритмами. Как показало тестирование, комбинированный алгоритм, основанный на гибридном алгоритме и zlib, позволяет значительно увеличить степень сжатия дискретно-тоновых изображений при приемлемых временных затратах.