Как работает алгоритм группового кодирования
- Если вы внимательно посмотрите на растровое изображение, то обнаружите, что пикселы одного цвета часто оказываются рядом друг с другом. Если начать с левого верхнего угла изображения и исследовать пикселы каждой строки, выписывая последовательно их значения слева направо, то можно заметить, что картинка состоит из множества отрезков, в которых повторяется одно и то число. Количество пикселов в отрезке будем называть длиной отрезка.
- Начиная с первой строки, программа группового кодирования просматривает значения пикселов слева направо и ищет отрезки повторяющихся пикселов. Всякий раз, когда встречаются три или более идущих подряд пикселов с одинаковым значением, программа заменяет их парой чисел: первое число указывает длину отрезка, второе – значение пикселов. Число, определяющее длину отрезка, будем называть меткой отрезка. На рисунке такие метки обозначены треугольниками.
- Чтобы идентифицировать серии неповторяющихся значений пикселов, программа также вставляет метки (на рисунке представлены квадратиками), указывающие количество таких значений в серии. Зарезервированный бит необходим для того, чтобы можно было отличить метку отрезка, от метки серии неповторяющихся значений. Например, в 8-ми битах можно специфицировать последовательности длиной до 127 пикселов (максимальное число, представимое 7-ю битами); восьмой бит в каждой метке может отличать отрезок от серии неповторяющихся пикселов. В нашем примере благодаря RLE-сжатию размер строки уменьшился с 32 до 19 байт, т.е. на 40 процентов. Точно так же обрабатывается каждая строка пикселов, и отрезки одинаковых значений пикселов сжимаются во всем изображении.
- Графическая программа декодирует изображение, считывая сжатый файл и восстанавливая отрезки повторяющихся значений пикселов. Заметим, что восстановленное изображение полностью совпадает с оригиналом.
2015-09-06
205
