Метод сжатия статических изображений на основе алгоритма Хаффмана

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

Например, одной из областей применения методов сжатия изображений является медицина, где важно с применением минимальных ресурсов передавать и хранить в медицинских информационных системах диагностическую информацию: снимки КТ, МРТ, УЗИ и другие исследования. Методы сжатия изображений активно применяются в интернет-магазинах, где скорость загрузки снимков товаров на странице с ассортиментом является ключевой.

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

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

Разработаны различные форматы файлов изображений, каждый из которых предназначен для определенных задач и использует в своей реализации собственные способы сжатия и сохранения информации. Например, формат JPEG [2; 3] используется для сжатия с потерями, формат PNG предназначен для сжатия изображений без потерь.

Для сжатия без потерь используются алгоритмы RLE1 [4], алгоритм Хаффмана2 [5], словарные алгоритмы [6], алгоритм унарного кодирования3.

Метод сжатия статических изображений на основе алгоритма Хаффмана

Чтобы максимально использовать возможности алгоритмов и нивелировать их недостатки, авторами предложен гибридный метод сжатия изображений, основанный на методе Хаффмана. В разработанном методе улучшение производится за счет первичной обработки изображения другим методом сжатия, а именно словарным методом LZW4 [7]. Формальная постановка задачи в виде IDEF0-диаграммы представлена на Рисунках 1–3.

Рисунок 1. IDEF0-диаграмма верхнего уровня A0 Источник: здесь и далее рисунки выполнены авторами.

Диаграмма уровня A1 (Рисунок 2) иллюстрирует общую структуру гибридного метода сжатия: преобразование изображения в байтовую строку, этап сжатия и создание итогового файла с сжатым изображением.

Рисунок 2. Детализированная IDEF0-диаграмма первого уровня

Диаграмма уровня A2 (Рисунок 3) раскрывает детали этапа сжатия, выделяя первичную обработку изображения методом LZW, построение таблицы частот символов, генерацию дерева Хаффмана и повторное кодирование методом Хаффмана.

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление», выпуск 2 за 2025 год

Рисунок 3. Детализированная IDEF0-диаграмма уровня A2

Предложенный гибридный метод должен минимизировать зависимость коэффициента сжатия информации от особенностей входных изображений.

Словарные алгоритмы сжатия , например LZW (Lempel-Ziv-Welch), применяют словарь для замены повторяющихся последовательностей данных более короткими символами. Цель таковых – нахождение повторяющихся участков данных и замена их кодами из словаря. Такой подход позволяет достичь уменьшения размера исходного сообщения. При LZW применяется один проход для кодирования данных, создания таблицы частот пикселей сжимаемого изображения не требуется. Использование алгоритма LZW позволяет удалить избыточность из последовательности пикселей и заменить повторяющиеся подстроки уникальными кодами, что значительно уменьшает размер исходного изображения.

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

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

Разработанный гибридный метод сжатия состоит из следующих этапов:

• 1)    получение данных сжимаемого изображения в виде байтовой строки, которая будет использоваться в качестве входных данных для алгоритма LZW;

• 2)    выполнение первичного сжатия изображения алгоритмом LZW;

• 3)    нахождение таблицы частот символов;

• 4)    построение дерева Хаффмана на основе вычисленной таблицы частот символов;

• 5)    выполнение повторного сжатия изображения алгоритмом Хаффмана;

• 6)    создание файла со сжатым изображением для его распаковки.

Таким образом, использование первичной обработки изображения в гибридном методе сжатия позволяет подготовить данные для метода Хаффмана путем уменьшения коли-

Метод сжатия статических изображений на основе алгоритма Хаффмана чества обрабатываемых символов. Такой подход приводит к более эффективному сжатию и увеличению общей степени сжатия.

Разработано программное обеспечение с демонстрацией работы гибридного метода сжатия изображений. В качестве языка программирования использовался Python5. Выбор данного языка обусловлен поддержкой объектно-ориентированной парадигмы программирования и наличием большого количества сторонних библиотек. Для работы с массивами битов при сжатии данных методом Хаффмана использовалась библиотека bitarray6, для отображения прогресса этапов сжатия и распаковки изображений – библиотека progress7, для получения списка файлов, доступных для сжатия, – модуль subprocess8.

В качестве входных данных разработанный программный комплекс получает путь до изображения в формате BMP, TIFF, PNG или JPEG, а также путь до директории, куда необходимо сохранить сжатое и распакованное изображения. На выходе в директории с результатами создаются два файла с расширениями .bin (для сжатого изображения) и .bmp (для распакованного). В консоль выводится подробная информация об этапах сжатия и распаковки изображения, размеры исходного и полученного файлов, итоговая степень сжатия.

В разработанном методе на первом этапе проводится первичное сжатие изображения методом LZW. В процессе обработки пикселей входного изображения создается словарь повторяющихся цепочек байтов. Выделенные последовательности пикселей заменяются на уникальные коды фиксированной длины. Размер кода зависит от количества заменяемых последовательностей (чем длиннее код, тем больше цепочек байтов можно заменить на первом этапе метода). Тот же словарь повторяющихся цепочек пикселей используется при распаковке сжатого изображения.

На втором этапе подсчитывается количество каждого уникального кода в полученной байтовой строке и строится таблица частот символов.

Третий этап заключается в построении дерева Хаффмана. Задача этапа – присвоение часто встречающимся символам более коротких кодов, редко встречающимся – более длинных. В отличие от классического дерева Хаффмана в разработанном методе за один символ принимается не один байт, а уникальный код, состоящий из заданного числа байтов.

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

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

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление», выпуск 2 за 2025 год

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

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

Размер информации для распаковки – показывает, какую часть сжатого изображения занимает информация, необходимая для восстановления исходного файла. Чем выше этот показатель, тем бо΄льшую долю от сжатого файла занимают метаданные. Большой объем информации для распаковки может не дать достичь высокой степени сжатия изображения.

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

Результаты сравнения по степени сжатия предложенного гибридного метода сжатия статических изображений без потерь методом LZW и методом Хаффмана приведены в Таблице 1 и на Рисунке 4.

Таблица 1

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

Изображение	Метод LZW, %	Гибридный метод, %	Метод Хаффмана, %
sunrise.bmp	83,01	75,29	69,91
mars.bmp	84,61	78,30	71,59
wheat.bmp	77,67	70,52	68,02
forest.bmp	44,52	54,23	67,77
girl.bmp	40,84	48,05	59,23

Источник: здесь и далее таблицы составлены авторами.

Очевидно, что степень сжатия зависит от типа данных: метод LZW лучше работает с длинными последовательностями одинаковых пикселей, показывая наивысшую степень сжатия для изображений sunrise.bmp (83,01 %), mars.bmp (84,61 %) и wheat.bmp (77,67 %). Метод Хаффмана, напротив, демонстрирует лучшие результаты для изображений с неравномерным распределением цветов, пример forest.bmp (67,77 %) и girl.bmp (59,23 %).

Гибридный метод является универсальным решением, которое позволяет минимизировать зависимость от особенностей входных изображений. Например, для изображения forest.bmp он показывает степень сжатия 54,23 %, что выше, чем у метода LZW (44,52 %), но ниже, чем у метода Хаффмана (67,77 %). В то же время для изображения mars.bmp его результат (78,30 %) уступает методу LZW (84,61 %), но превосходит метод Хаффмана (71,59 %).

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

Метод сжатия статических изображений на основе алгоритма Хаффмана

Сравнение методов по степени сжатия изображений

Рисунок 4. Сравнения методов сжатия статических изображений без потерь по степени сжатия Источники:

– URL: ;

– URL: ;

– URL: ;

– URL: ;

Результаты сравнения методов сжатия статических изображений без потерь по количеству информации, необходимой для распаковки изображений, приведены в Таблице 2 и на Рисунке 5.

Таблица 2

Результаты сравнения методов сжатия по размеру информации для распаковки изображений

Изображение	Метод LZW, %	Гибридный метод, %	Метод Хаффмана, %
sunrise.bmp	0,53	41,20	0,51
mars.bmp	0,77	41,81	0,72
wheat.bmp	0,76	39,07	0,88
forest.bmp	0,25	33,50	0,73
girl.bmp	2,72	39,05	6,59

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление», выпуск 2 за 2025 год

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

Рисунок 5. Сравнение методов сжатия статических изображений без потерь по количеству информации для распаковки