Алгоритм группового кодирования или RLE

Алгоритм сжатия, поддерживающийся большинством растровых форматов (tif, wmp и т.д.).Этот алгоритм позволяет сжимать данные любых типов независимо от содержащейся в них информации. Сама информация влияет лишь на полноту сжатия. RLE не достигает большой степени сжатия (3:1), но выполняется легко и быстро, является альтернативой сложным методам.

Суть метода: RLE уменьшает физический размер повторяющихся строк символов. Такие повторяющиеся строки называются группами и обычно кодируются в 2-х байтах.

1 байт определяет количество символов в группе и называется счетчиком группы. Кодируемая группа содержит от 1 до 128 или от 0 до 256 символов, что записывается в счетчик группы как количество символов – 1(т.к. считают с 0).

2 байт содержит значение символов группы и называется значением группы.

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

ААА.....АА 14А – RLE-пакет

Этот код сгенерированный для представления символов называется RLE пакетом.

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

2 255 2 0 0 255 5 0 8 байт

255 255 255 0 0 0 255 0 0 0 0 0 0 13 байт

Для кодирования в RLE требуется минимум 2 байта.

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

Группа из одиночных символов, закодированная с помощью RLE-пакета, займет в 2 раза больше памяти, чем непосредственное представление этих данных.

Групповое кодирование не является форматом файла. Это метод кодирования, который может быть включен в некоторые графические форматы (gif, tif, jpeg)

Варианты группового кодирования

Обычно с помощью RLE данные изображения кодируются последовательно, по линиям развертки слева направо.

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

Чтобы избежать перекрестного кодирования, RLE-кодировщики всегда останавливаются в конце каждой строки развертки растровых данных.

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

//Ещё одно преимущество построчного кодирования – программа легко воспроизводит любую часть изображения.//

Второй способ избежать перекрестного кодирования создать таблицу строк развертки.

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

//23.11.04. Лекция 8//