Microsoft Word Уч пособие 22 09. doc

Кодирование длин серий

Метод кодирования длин серий RLE [52], или групповое кодирование, метод сжатия без потерь информации, является самым простым, понятным и быстрым методом. Он широко применяется при записи графических изображений в файлы [53]. Примерами могут служить кадры мультипликата, выполненного в технике, подобной мультфильмам Диснея, графические изображения (чертежи, плакаты, и др.) и другие, содержащие большие области постоянной яркости или цвета. Серии повторяющихся значений отсчетов кодируются двумя байтами: длиной серии (числом повторяемых отсчетов) и значением яркости отсчета, за счет чего достигается сжатие данных. Первый байт называется счетчиком серии. Второй байт называется значением серии. Эта пара байтов формирует RLE- пакет. При изменении серии и в случае, когда размер серии превышает диапазон счетчика, формируется новый пакет. Например, пусть задана последовательность значений: {0, 0, 100, 100, 100, 200, 200, 200,
200, 200, 200, 170, 170}, соответствующая ей кодовая последовательность 4 пакетов имеет вид: 2,0;3,100;6,200;2,170. 13 байтов последовательности мы заменили 8 байтами потока.
Есть несколько вариантов группового кодирования. Обычно сжатие выполняется вдоль строк изображения, при этом они представляют собой одномерный поток, а не двумерную таблицу данных. При этом растровое изображение кодируется слева направо и сверху вниз, начиная с левого верхнего угла. Альтернативные схемы кодирования RLE разрешают кодировать по столбцам, фрагментами 4x4 элемента и в зигзагообразном порядке (см. JPEG). Определим коэффициент сжатия. При формировании RLE по байтовой схеме, при которой пакет занимает 2 байта, при размере полутонового изображения равном M строк по N столбцов, при восьмиразрядном квантовании коэффициент сжатия равен:
k_сж  NM /(2N_гр ) ,

где
N _гр - общее число серий в изображении, размер которых меньше

максимального значения счетчика серии.
Таким образом, если в изображении все соседние отсчеты отличаются друг от друга, то есть счетчики всех серий равны 1, то код окажется в два раза длиннее, чем объем памяти, занимаемый самим изображением. Но по мере уменьшения вероятности появления новых значений отсчетов, коэффициент сжатия увеличивается.
Этот метод не эффективен при кодировании полутоновых изображений, в которых практически отсутствуют повторяющиеся последовательности уровней яркости. Одна из схем кодирования RLE представлена на рисунке 8.3. В этой схеме для кодирования серии длиной в 1 отсчет используется пакет только в том случае, когда значение отсчета превышает максимальное значение счетчика группы, в противном случае в поток выводится только 1 байт, содержащий значение отсчета. В данном примере выбран размер серии, равный 127, максимальное значение счетчика задано равным 128₁₀=80₁₆. Cтарший бит счетчика равен 1, он является флагом пакета. Остальные 7 разрядов позволяют записать длину серии (размер серии ограничен 127 отсчетами). Если серия одинаковых отсчетов превышает этот размер, то формируется новый пакет. Кроме того, на этой схеме кодирование выполняется по строкам. При этом серия завершается последним отсчетом текущей строки. Алгоритм, представленный на рисунке 8.3 выполняется для каждой строки изображения.
Схема алгоритма декодирования представлена на рисунке 8.4. Обнуляется счетчик строки i. Формируется маска MaskValue, позволяющая выделить счетчик серии. В нашем случае она равна $7F. Считывается байт из потока. Если его значение не меньше FlagRLE, то этот байт содержит значение счетчика в пакете. Следовательно, производится выделение значения счетчика RunCount. Считывается следующий байт из потока, второй байт пакета Curr. В буфер строки выводится RunCount раз значение Curr. Если же значение байта Curr меньше FlagRLE, следовательно, это не пакет, а одиночный отсчет. Значение RunCount устанавливается в 1. В буфер строки выводится одно значение Curr. Счетчик длины строки i увеличивается на RunCount. Эта последовательность операций выполняется, пока значение счетчика остается меньшим длины строки изображения. Для каждой следующей строки снова выполняется алгоритм, представленный на рисунке 8.4.
Недостатком RLE кодирования является низкая помехоустойчивость метода. Изменение яркости вследствие помехи приводит к изменению яркости всей последовательности (штрихи вдоль строк) или к “раздергиванию” строк в случае изменения длины серии вследствие помехи. Достоинством метода является простота его реализации. Этот метод используется в графических форматах BMP, PCX, TIFF и TARGA, как дополнительный в формате JPEG.

Рисунок 8.3 Блок-схема алгоритма кодирования длин серий строки изображения.

Рисунок 8.4 Блок-схема алгоритма декодирования строки изображения по методу RLE.

3.