Первый вариант алгоритма

Данный алгоритм необычайно прост в реализации. Кодирование длин повторов - от английского Run Length Encoding (RLE) - один из самых ста­рых и самых простых алгоритмов архивации графики. Изображение в нем (как и в нескольких алгоритмах, описанных ниже) вытягивается в цепочку байтов по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байтов. Замена их на пары <счетчик повторений, значение> уменьшает избыточность данных.

Алгоритм декомпрессии при этом выглядит так:

Initialization(...); do {

byte = ImageFile.ReadNextByte(); if(является счетчиком(byte)) { counter = Low6bits(byte)+1; value = ImageFile.ReadNextByte(); for(i=l to counter)

DecompressedFile.WriteByte(value) )

else {

DecompressedFile.WriteByte(byte) ) while (UmageFile.EOF ()) ;

В данном алгоритме признаком счетчика (counter) служат единицы в двух верхних битах считанного файла:

Соответственно оставшиеся 6 бит расходуются на счетчик, который мо­жет принимать значения от 1 до 64. Строку из 64 повторяющихся байт мы превращаем в 2 байта, т. е. сожмем в 32 раза.

Упражнение. Составьте алгоритм компрессии для первого варианта алгоритма RLE.

Алгоритм рассчитан на деловую графику - изображения с большими об­ластями повторяющегося цвета. Ситуация, когда файл увеличивается, для этого простого алгоритма не так уж редка. Ее можно легко получить, при­меняя групповое кодирование к обработанным цветным фотографиям. Для того чтобы увеличить изображение в 2 раза, его надо применить к изобра­жению, в котором значения всех пикселов больше двоичного 11000000 и подряд попарно не повторяются.

Упражнение. Предложите 2-3 примера "плохих" изображений для алгоритма RLE. Объясните, почему размер сжатого файла больше размера исходного файла.

Данный алгоритм реализован в формате PCX. См. пример в приложении 2.

Второй вариант алгоритма

Второй вариант этого алгоритма имеет большую максимальную степень сжатия и меньше увеличивает в размерах исходный файл. Алгоритм декомпрессии для него выглядит так:

Initialization(...); do {

byte = ImageFile.ReadNextByte(); counter = Low7bits(byte)+1; if(если признак повтора(byte)) { value = ImageFile.ReadNextByte(); for (i=l to counter)

CompressedFile.WriteByte(value)

) else {

for(i«=l to counter) {

value = ImageFile.ReadNextByte(); CompressedFile.WriteByte(value) } } while (! ImageFile.EOFO ) ;

Признаком повтора в данном алгоритме является единица в старшем разряде соответствующего байта:

j 0 7 бит___ I Что пропускать I ... Что пропускать I

^ 1 7 бит I Что повторять I

Как можно легко подсчитать, в лучшем случае этот алгоритм сжимает файл в 64 раза (а не в 32 раза, как в предыдущем варианте), в худшем уве­личивает на 1/128. Средние показатели степени компрессии данного алго­ритма находятся на уровне показателей первого варианта.

(Эч Упражнение. Составьте алгоритм компрессии для второго варианта алгоритма RLE.

Похожие схемы компрессии использованы в качестве одного из алго­ритмов, поддерживаемых форматом TIFF, а также в формате TGA.

Характеристики алгоритма RLE:

Степени сжатия: первый вариант: 32, 2, 0,5. Второй вариант: 64, 3, I 128/129. (Лучшая, средняя, худшая степени).

Класс изображений: ориентирован алгоритм на изображения с не-I большим количеством цветов: деловую и научную графику.

помощь в получении кредита

Симметричность: примерно единица.

резиновые заглушки

Характерные особенности: к положительным сторонам алгоритма, по-I жалуй, можно отнести только то, что он не требует дополнительной памяти \ при архивации и разархивации, а также быстро работает. Интересная особен-! ность группового кодирования состоит в том, что степень архивации для не-! которых изображений может быть существенно повышена всего лишь за i счет изменения порядка цветов в палитре изображения.