Метод группового кодирования RLE

Наиболее распространенный алгоритм сжатия, поддерживается большинством распространенных файловых форматов. Этот алгоритм позволяет сжимать данные любых типов, невзирая на содержащуюся в них информацию. Хотя сама информация влияет на полноту сжатия. Без потерь степень сжатия 3:1; 4:1. RLE уменьшает физический размер повторяющихся строк символов. Такие повторяющиеся строки называются группами и кодируются в 2х байтах. Первым определяет количество символов в группы и называется счетчиком группы. Группа обычно содержит от 1 до 128 или от1 до 256 символов. В счетчик эта информация записывается в количестве -1, т. к. отсчет начинается с 0. 2й байт содержит значение символа группы (от 0 до 255).. Новый пакет генерир-ся снова, когда измерится группа или когда кол-во символов в группе превысит значение счётчика

АААААА ВВВВ ХХ ТТТ

5А 3В 1Х 2Т

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

Данные изображ-ия обычно кодир-ся последовательно.Растер кодир-ся,начиная с верхнего лев угла по оси Х слева направо к нижн правому углу. Альтернатив схемы позволяют записывать закодир-ые данные по высоте растора(т.е. по оси Y),а также кодируют растр зигзагом.

Иногда встречаются варианты группового RLE-кодир-ия с потерями: отбрасывают данные в процессе кодир-ия(обычно младший бит в каж пикселе),что серьёзно увеличивает степень сжатия изображ-ия,но примен-ся только в многоцветных изображ-х. RLE-кодировщик должен останавливаться в конце каждой строки развертки растровых данных. Построчное кодир-е требует меньшего размера буфера и предотв-ет проблему перекрестного кодир-я. Перекрестное кодирование – слияние строк развертки, происходящее из-за того, что в процессе кодирования различие между строками исчезает. При выйгрыше в нескол байтов в процессе сжатия без маркера конца строки FB значительно усложняется процесс декодирования инф-ии, а также нарушается базовый принцип организации растрового изображ-ия в виде строк развёртки. Программа-кодировщик помещает в закодированные данные маркер конца строки развёртки, чтобы программа-декодировщик могла распознать начало строки развертки. Этот маркер предст собой уникальный пакет, точно определённый спецификацией RLE. Обычно маркер конца строки развёртки им длину 1 байт. Другой способ определения в блоке закодированного данного начала строки любой строки развертки является создание таблицы строк развертки. Таблица содержит по одному элементу любой строки. Для этого, чтобы найти RLE – пакет определяющий строки развертки, программа- декодирования читает смещение, записывая в таблице и воспроизводит исходные данные. Инф-я о смещении начала каждой строки развертки в файле.

RLE-схема битового уровня

Битового уровня – кодируют в группы биты строк развертки, игнорируя при этом границы байтов и слов. Используются только при обработке монохромных изображений, которые содержат достаточное количество битовых групп. RLE-схемы битового уровня кодируют в группы только до 128 одинаковых битов, создавая из них однобайтовый пакет. 7 младших битов этого байта содержат счетчик группы, самый старший бит – значения группы (0 или 1). РИС.

RLE-схема байтового уровня

Байтового уровня – эти схемы кодируют в группы одинаковые байтовые знчения, игнорируя при этом отдельные биты и границы слов. RLE-сх байтового ур кодируют в 2-х байтовый пакет: 1-ый байт – счетчик группы(0-255)

2-ой байт – значение группы (0-255). Используемая схема 2х байтового кодирования, позволяет хранить в потоке данных как закодированные, так и не закодированные группы. Незакодированные группы – литералы. В этом случае 1-7 бит 1- го байта пакета содержит счетчик группы, а самый старший бит 1-го байта – тип группы: 1- закодированная группа, она декодируется путем чтения значений группы и повторений столько раз, сколько указано в счетчике (+1).

0 – литеральная группа, т. е следующие байты должны читаться на прямую из закодированных данных изображения в количестве, указанном счетчиком группы (+1). РИС

Группа- указывает, сколько пикселей подряд будут считаны. RLE-сх байтового ур эффективны для данных изображения, кот хран-ся в виде 1 байта на пиксель.