Лекции / Лекция 11
.doc//Лекция 11// Методы сжатия графических данных. Алгоритм группового кодирования.
RLE схемы битового, байтового и пиксельного уровней
Различие между этими способами кодирования заключается в формировании пакетов, соответствующих группам символов.
Большинство форматов графических файлов в зависимости от уровня обрабатываемых данных выделяют 3 класса RLE схем.
RLE-схемы битового уровня
Кодируют в группы биты строк развертки, игнорируя при этом границы байтов и слов. Используются только для обработки монохромных, т.е. однобитовых изображений, содержащих достаточное количество битовых групп.
RLE схемы битового уровня кодируют в группу от 1 до 128 битов, создавая из них однобайтовые пакеты. 7 младших битов этого байта – это счетчик группы, старший бит содержит значение группы.
7 – ой бит – (0/1), значение группы
6-0 – ой биты – счетчик группы (0-127)
|
Зн-е |
Счетчик |
||||||
|
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
0 |
99(в двоичном коде) |
||||||
|
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
0 |
127(в двоичном коде) |
0 |
71(в двоичном коде) |
||||||||||||
|
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
RLE-схемы байтового уровня
Кодируют в группы одинаковые байтовые значения, игнорируя отдельные биты и слова.
Используются для изображений, в которых каждый пиксель содержит 8 бит информации.
RLE кодирует группы байтов в 2-х байтовые пакеты
1-ый байт – счетчик группы(0-255)
2-ой байт – значение группы (0-255)
|
99(в двоичном коде) |
0(в двоичном коде) |
||||||||||||||
|
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
(возможно 256 цветов)
|
255(в двоичном коде) |
0(в двоичном коде) |
43(в двоичном коде) |
0(в двоичном коде) |
||||||||||||||||||||||||||||
|
7 |
|
|
|
|
|
|
0 |
7 |
|
|
|
|
|
|
0 |
7 |
|
|
|
|
|
|
0 |
7 |
|
|
|
|
|
|
0 |
300 черных пикселей
Существует схема 2-х байтового кодирования, позволяющая хранить в потоке закодированных данных – литералы – незакодированные группы байтов.
В такой схеме 7 младших битов 1-го байта пакета содержат счетчик группы, а старший бит 1-го байта – тип группы:
1 – закодированная группа
0 – литеральная группа, т. е следующие байты должны читаться напрямую из закодированных данных изображения в количестве, указанном счетчиком группы +1.
1-ый байт 1-127 – счетчик
2-ой байт 0-255 – значение группы
|
|
счетчик группы |
значение группы |
|||||||||||||
|
1 |
99(в двоичном коде) |
0(в двоичном коде) |
|||||||||||||
|
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
закодированная группа
|
|
счетчик значений |
|
|||||||||
|
0 |
|
зн1 |
зн2 |
зн3 |
… |
||||||
|
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
7 0 |
7 0 |
7 0 |
7 0 |
литеральная группа
Эффективно для изображений, содержащих 1 байт информации на пиксель.
RLE-схемы пиксельного уровня
Применяется, когда для хранения одного пиксельного значения используется два или более смежных байтов изображения.
На пиксельном уровне биты игнорируются, а байты принимаются во внимание только для идентификации цветового канала. Размер закодированного пакета зависит от размера пиксельных значений , подлежащих кодированию.
|
счетчик |
значение |
||
|
99 |
0 |
0 |
255 |
|
7 0 |
7 0 |
7 0 |
7 0 |
RGB – 100 синих пикселей
1-ый байт – счетчик (0-255)
2-ой байт – пиксель 1-го канала (0-255)
3-ий байт – пиксель 2-го канала (0-255)
4-ый байт – пиксель 3-го канала (0-255)
Сведения о количестве битов или байтов в пикселе записаны в заголовке файла изображения, там же сведения о схеме кодирования.
В RLE схемах пиксельного уровня счетчик содержит сведения о количестве пикселей, а не о количестве байтов.
Существуют литеральные группы пиксельного уровня.
Самый старший бит 1-го байта группы содержит указатель на то, является ли группа литеральной. 7 младших битов этого байта содержат счетчик группы. Остальные 3 байта информации содержат значения группы.
Если старший бит установлен в 1, то это закодированная группа. Закодированные группы декодируются посредством чтения значения группы и повторения его столько раз, сколько указано в счетчике +1.
Если самый старший бит установлен в 0, то он указывает на литеральную группу, т.е. следующие байты в количестве, указанном в счетчике группы +1, должны читаться напрямую из закодированных данных. В литеральных группах максимальное значение счетчика 128 байт.
Применение литеральных RLE групп при обработке потока данных, содержащих много одно- и 2-хпиксельных групп более эффективно, чем кодирование этих групп, т.к. позволяет избежать отрицательного сжатия, т.е. увеличения объема данных в процессе сжатия.
RLE схемы с использованием флага
При этом способе для представления группы используется не 2, а 3 байта.
1-ый байт – флаговое значение, указывает на то, что следующие 2 байта являются частью закодированного пакета
2-ой байт – счетчик группы
3-ий байт – значение группы
Если в процессе кодирования встречаются группы, состоящие из 1, 2х или 3х символов, то эти данные не кодируются, а непосредственно записываются в поток сжатых данных.
|
флаг |
счетчик |
значение |
|
255 |
0 |
2 |
Для значения флага выбирают значение, которое редко встречается.
При декодировании флаговое значение анализируется прочитанный символ, если это флаговое значение, то следующий байт обрабатывается как счетчик, 3-ий байт – как значение. Результат записывается в выходной поток данных.
Если прочитанный символ не является флаговым значением, то он записывается в выходной поток напрямую.
Минимальный размер группы, пригодный для кодирования таким способом возрастает с 3 до 4 одинаковых символов.
Если поток незакодированных данных содержит значение символов, равное флаговому значению, то этот символ должен быть закодирован в 3-х байтовый пакет. Алгоритмы RLE используют такие флаговые значения, которые в потоке несжатых данных встречаются крайне редко.
RLE пакеты вертикального повторения
Многие RLE схемы для повышения эффективности сжатия используют пакеты повторения строк развертки, называемые пакетами вертикального повторения. Этот пакет не хранит реальных данных строк развертки, он лишь указывает на то, что необходимо повторить предыдущую строку.
Пакет вертикального повторения, если содержит 1 байт информации, то это счетчик группы =0, указывает на то, что строка должна быть повторена 1 раз. Если за этим байтом следует значение, то это значение повторяющихся строк развертки.
Т.е. одним пакетом, состоящим из счетчика группы + значением, можно описать количество повторяющихся строк.
100 строк развертки белых пикселей, в строке – 12380 пикселей
1 строка – 5 пакетов по 256 пикселей
|
1 пакет |
2 пакет |
3 пакет |
4 пакет |
5 пакет |
|
пакет вертик.повт-ия |
||||||
|
счетчик |
зн-ие |
|
|
|
|
|
|
|
|
|
сч-к |
Кол-во повт-ий |
|
255 |
255 |
… |
|
|
|
|
|
|
… |
* |
0 |
98 |
В данном примере:
10 байт – описывается сама строка
1 байт – маркер конца строки
2 байта – пакет вертикального повторения (всего 13 байт)