Алгоритмы сжатия изображений без потерь. Ccitt Group 3, Сжатие по Хаффману.
Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока,
которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко —цепочку большей длины. Для сбора статистики требует двух проходов по изображению.
Коэффициенты компрессии: 8, 1,5, 1 (Лучший, средний, худший коэффициенты).
Использование: Практически не применяется в чистом
виде. Обычно используется как один из этапов
компрессии в более сложных схемах.
Симметричность: 2 (за счет того, что требует двух проходов по массиву сжимаемых данных).
Характерные особенности: Единственный алгоритм, который не увеличивает размера исходных данных в худшем случае (если не считать необходимости хранить таблицу перекодировки вместе с файлом).
CCITT Consultative Committee International Telegraph
and Telephone
Последовательности подряд идущих черных и белых точек в нем заменяются числом, равным их количеству.
Каждая строка сжимается независимо, если строка начинается с черной точки, то считаем, что она начинается белой серией длиной 0. Например, последовательность длин серий 0, 3,556,10,.. означает, что в строке идут сначала 3 черных, 556 белых, 10 черных точек и т.д.
А этот ряд, уже в свою очередь, сжимается по Хаффману с фиксированной таблицей.
Коэффициенты компрессии: лучший коэффициент стремится в пределе к 213.(3), средний 2, в худшем случае увеличивает файл в 5 раз.
Класс изображений: Двуцветные черно-белые изображения, в которых преобладают большие пространства, заполненные белым цветом.
Симметричность: Близка к 1.
Характерные особенности: Данный алгоритм
чрезвычайно прост в реализации, быстр и может быть легко реализован аппаратно.
Этот алгоритм c фиксированными таблицами кодирования построенными с помощью классического алгоритма Хаффмана реализован в формате TIFF. Значения вероятностей появления для конкретных длин серий были получены путем анализа большого количества факсимильных изображений.
Алгоритмы сжатия изображений без потерь. Lz 77, lzss .
LZ77 и LZ78 являются универсальными алгоритмами сжатия, в которых словарь формируется на основании уже обработанной части входного потока, т.е. адаптивно. Принципиальным отличием является лишь способ формирования фраз. В модификациях первоначальных алгоритмов эта свойство сохраняется. Поэтому словарные алгоритмы Зива-Лемпела разделяют на два семейства — алгоритмы типа LZ77 и алгоритмы типа LZ78. Иногда также говорят о словарных методах LZ1 и LZ2.
Если некий исследователь существенно изменял какой-то алгоритм, относимый к семейству LZ, то в названии полученной модификации к строчке «LZ» обычно дописывалась первая буква его фамилии, например: алгоритм LZB, автор Белл (Bell).
Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 году , но сам алгоритм разработан не позднее 1975 года.
Является «родоначальником» целого семейства словарных схем — так называемых алгоритмов со скользящим словарем, или скользящим окном. В LZ77 в качестве словаря используется блок уже закодированной последовательности. Как правило, по мере выполнения обработки положение этого блока относительно начала последовательности постоянно меняется, словарь «скользит» по входному потоку данных.
Характеристики алгоритмов семейства LZ77:
Степени сжатия: определяются данными, обычно 2...4.
Типы данных: алгоритмы универсальны
Симметричность по скорости: примерно 10:1; если алгоритм обеспечивает хорошее сжатие, то декодер обычно гораздо быстрее кодера.
LZSS.Эта модификация LZ77 была предложена в 1982 году Сторером (Storer) и Жимански (Szymanski) Идея алгоритма заключается в добавление к каждому указателю и символу однобитового префикса , позволяющего различать эти объекты.
В потоке сжатых данных идет либо пара <счетчик, смещение относительно текущей позиции>, либо просто <счетчик> «пропускаемых» байт и сами значения байтов (как во втором варианте алгоритма RLE). При разархивации для пары <счетчик, смещение> копируются <счетчик> байт из выходного массива, полученного в результате разархивации, на <смещение> байт раньше, а <счетчик> (т.е. число равное счетчику) значений «пропускаемых» байт просто копируются в выходной массив из входного потока.
