Методы сжатия изображений

RLE (Run-Length Encoding) – сжатие длинных последовательностей. Самый простой алгоритм сжатия. С большим успехом применяется по сей день на различных потоках данных, но чаще всего в качестве дополнительного алгоритма сжатия. Наиболее эффективен в примитивных малоцветных изображениях, где существуют довольно большие участки кода, передающего один цвет.

Принцип работы алгоритма легко понять на следующем примере. Имеем текст:

аааааааааааабббббббббвапезааааааааааааааааазепккккккккккккккккккккккккк

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

12а9б05вапез17а03зеп25к.

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

LZ – Lempel-Ziv. Это метод словарей, несколько улучшенный алгоритм сжатия изображений, впервые опубликованный в 1977 г. На сегодняшний день LZ-алгоритм и его модификации получили наиболее широкое распространение по сравнению с другими методами сжатия. Принцип в общем похож на RLE. Из повторяющихся участков кода формируется индексированный словарь. А поскольку индекс занимает гораздо меньше места, чем участок кода, получается достаточно эффективный метод сжатия. Основной плюс – сжимаются повторы комбинаций. Основной недостаток – словарь требуется хранить в том же файле. Существует большое число модификаций этого метода LZ – LZW, LZ77, LZSS и т. д.

Вероятностные методы сжатия. В основе вероятностных методов сжатия (алгоритмов Шеннона-Фано (Shannon Fano) и Хаффмана (Huffman) лежит идея построения “дерева”, в котором положение символа на “ветвях” определяется частотой его появления. Каждому символу присваивается код, длина которого тем меньше, чем выше частота появления этого символа. Существуют две разновидности вероятностных методов, различающихся способом определения вероятности появления каждого символа:

- статические (static) методы, использующие фиксированную таблицу частоты появления символов, рассчитываемую перед началом процесса сжатия на основе анализа фрагмента сжимаемого текста;

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

Статические методы характеризуются хорошим быстродействием и не требуют значительных ресурсов оперативной памяти. Они нашли широкое применение в многочисленных программах-архиваторах, например, ARC, ZIP, RAR и т. д.

Дата добавления: 2014-01-06