Первый вариант.
Данный алгоритм достаточно прост в реализации. Групповое кодирование (от английского Run Length Encoding (RLE)) - один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.
В данном алгоритме признаком счетчика служат единицы в двух верхних битах считанного файла. Соответственно оставшиеся 6 бит расходуются на счетчик, который может принимать значения от 1 до 64. Строку из 64 повторяющихся байтов мы превращаем в два байта, т.е. сожмем в 32 раза.
Алгоритм рассчитан на деловую графику - изображения с большими областями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, применяя групповое кодирование к обработанным цветным фотографиям. Для того чтобы увеличить изображение в два раза, его надо применить к изображению, в котором значения всех пикселей больше двоичного 11000000 и подряд попарно не повторяются.
Данный алгоритм реализован в формате PCX.
Теперь рассмотрим второй вариант алгоритма.
Второй вариант этого алгоритма имеет больший максимальный коэффициент архивации и меньше увеличивает в размерах исходный файл. Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта.
Как можно легко подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в худшем увеличивает на 1/128. Средние показатели степени компрессии данного алгоритма находятся на уровне показателей первого варианта.
Похожая схема компрессии использована в качестве одного из алгоритмов, поддерживаемых форматом TIFF, а также в формате TGA.
Название алгоритм получил по первым буквам фамилий его разработчиков - Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байт.
Cчитываются последовательно символы входного потока и проверяется, есть ли в созданной таблице строк такая строка. Если строка есть, то мы считываем следующий символ, а если строки нет, то мы заносим в поток код для предыдущей найденной строки, заносим строку в таблицу и начинаем поиск снова.
На практике для хранения таблицы используется хэш-таблица. Таблица состоит из 8192 (213) элементов. Каждый элемент содержит <код предыдущей подстроки; добавленный символ; код этой строки>. Ключ для поиска длиной в 20 бит формируется с использованием двух первых элементов, хранимых в таблице как одно число (key). Младшие 12 бит этого числа отданы под код, а следующие 8 бит под значение символа.
В качестве хэш-функции при этом используется: Index(key)=((key >> 12) ^ key) & 8191;
Где >> - побитовый сдвиг вправо (key >> 12 - мы получаем значение символа), ^ - логическая операция побитового исключающего ИЛИ, & - логическое побитовое И.
Таким образом, за считанное количество сравнений, мы получаем искомый код или сообщение, что такого кода в таблице нет.
Лучший коэффициент, очевидно, будет получен для цепочки одинаковых байт большой длины (т.е. для 8-битного изображения, все точки которого имеют, для определенности, цвет 0). При этом в 258 строку таблицы мы запишем строку "0, 0", в 259 - "0, 0, 0", ... в 4095 - строку из 3809 (=4095-256) нулей. При этом в поток попадет 3810 кодов, включая код очистки. Следовательно, посчитав сумму арифметической прогрессии от 1 до 3809 (т.е. длину сжатой цепочки) и поделив ее на 3810*12/8 (в поток записываются 12-битные коды), мы получим лучший коэффициент компрессии.
Худший коэффициент будет получен, если мы ни разу не встретим подстроку, которая уже есть в таблице (в ней не должно встретиться ни одной одинаковой пары символов).
LZW реализован в форматах GIF и TIFF.
Алгоритм разработан группой экспертов в области фотографии(Joint Photographic Expert Group). В целом алгоритм основан на дискретном косинусоидальном преобразовании (в дальнейшем ДКП), применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения применяется обратное преобразование.
ДКП раскладывает изображение по амплитудам некоторых частот, таким образом, при преобразовании мы получаем матрицу, в которой многие коэффициенты либо близки, либо равны нулю. Кроме того, человеческая система цветового восприятия слабо распознает определенные частоты. Поэтому можно аппроксимировать некоторые коэффициенты более грубо без заметной потери качества изображения.
Для этого используется квантование коэффициентов (quantization). В самом простом случае - это арифметический побитовый сдвиг вправо. При этом преобразовании теряется часть информации, но могут достигаться большие коэффициенты сжатия.
Существенными положительными сторонами алгоритма является то, что:
1) Задается степень сжатия.
2) Выходное цветное изображение может иметь 24 бит/пиксел.
Отрицательными сторонами алгоритма является то, что:
1) При повышении степени сжатия изображение распадается на отдельные квадраты (8x8). Это связано с тем, что происходят большие потери в низких частотах при квантовании, и восстановить исходные данные становится невозможно.
2) Проявляется эффект Гиббса - ореолы по границам резких переходов цветов.
Не очень приятным свойством JPEG является также то, что нередко горизонтальные и вертикальные полосы на дисплее абсолютно не видны, и могут проявиться только при печати в виде муарового узора. Он возникает при наложении наклонного растра печати на горизонтальные и вертикальные полосы изображения. Из-за этих сюрпризов JPEG не рекомендуется активно использовать в полиграфии, задавая высокие коэффициенты. Однако при архивации изображений, предназначенных для просмотра человеком, он на данный момент незаменим.
Как стандарт ISO JPEG начинает все шире использоваться при обмене изображениями в компьютерных сетях. Поддерживается алгоритм JPEG в форматах Quick Time, PostScript Level 2, Tiff 6.0 и на данный момент занимает видное место в системах мультимедиа.
JBIG - это метод компрессии изображений, разработанный группой экспертов, работающей под эгидой ISO и ITU-T (Joint Bi-level Experts Group). Он разработан специально для сжатия однобитных черно-белых изображений. Например, факсов или отсканированных документов. В принципе может применяться и к 2-х, и к 4-битовым картинкам. Форматы, поддерживающие этот метод компрессии создаются конкретно для каждой задачи. Один из распостранненых форматов, поддерживающий JBIG - это формат SPIFF, разработанный JPEG коммитетом.
Алгоритм разбивает их на отдельные битовые плоскости. JBIG позволяет управлять такими параметрами, как порядок разбиения изображения на битовые плоскости, ширина полос в изображении, уровни масштабирования. Последняя возможность позволяет легко ориентироваться в базе больших по размерам изображений, просматривая сначала их уменьшенные копии. Настраивая эти параметры, можно использовать описанный выше эффект "огрубленного изображения" при получении изображения по сети или по любому другому каналу, пропускная способность которого мала по сравнению с возможностями процессора. Распаковываться изображение на экране будет постепенно, как бы медленно "проявляясь". При этом человек начинает анализировать картинку задолго до конца процесса разархивации.
Алгоритм построен на базе Q-кодировщика, патентом на который владеет IBM. Q-кодер так же, как и алгоритм Хаффмана, использует для чаще появляющихся символов короткие цепочки, а для реже появляющихся - длинные. Однако, в отличие от него, в алгоритме используются и последовательности символов.