Определение 6:

Набор идущих подряд точек изображения одного цвета называется серией.Длина этого набора точек называется длиной серии.

В таблице, приведенной ниже, заданы два вида кодов:

Коды завершения серий — заданы с 0 до 63 с шагом 1.
Составные (дополнительные) коды — заданы с 64 до 2560 с шагом 64.

Каждая строка изображения сжимается независимо. Мы считаем, что в нашем изображении существенно преобладает белый цвет, и все строки изображения начинаются с белой точки. Если строка начинается с черной точки, то мы считаем, что строка начинается белой серией с длиной 0. Например, последовательность длин серий 0, 3, 556, 10, ... означает, что в этой строке изображения идут сначала 3 черных точки, затем 556 белых, затем 10 черных и т.д.

На практике в тех случаях, когда в изображении преобладает черный цвет, мы инвертируем изображение перед компрессией и записываем информацию об этом в заголовок файла.

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

for(по всем строкам изображения) {
Преобразуем строку в набор длин серий;
    for(по всем сериям) {
        if(серия белая) {
            L= длина серии;

            while(L > 2623) { // 2623=2560+63
                L=L-2560;
                ЗаписатьБелыйКодДля(2560);
            }
            if(L > 63) {
                L2=МаксимальныйСостКодМеньшеL(L);
                L=L-L2;
                ЗаписатьБелыйКодДля(L2);
            }
            ЗаписатьБелыйКодДля(L);
            //Это всегда код завершения
        }
        else {
            [Код аналогичный белой серии,
            с той разницей, что записываются
            черные коды]
        }
    }
    // Окончание строки изображения
}

Поскольку черные и белые серии чередуются, то реально код для белой и код для черной серии будут работать попеременно.

В терминах регулярных выражений мы получим для каждой строки нашего изображения (достаточно длинной, начинающейся с белой точки) выходной битовый поток вида:

((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>)+

[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]

Где ()* — повтор 0 или более раз, ()+.— повтор 1 или более раз, [] — включение 1 или 0 раз.

Для приведенного ранее примера: 0, 3, 556, 10... алгоритм сформирует следующий код: <Б-0><Ч-3><Б-512><Б-44><Ч-10>, или, согласно таблице, 001101011001100101001011010000100 (разные коды в потоке выделены для удобства). Этот код обладает свойством префиксных кодов и легко может быть свернут обратно в последовательность длин серий. Легко подсчитать, что для приведенной строки в 569 бит мы получили код длиной в 33 бита, т.е. коэффициент сжатия составляет примерно 17 раз. Вопрос к экзамену: Во сколько раз увеличится размер файла в худшем случае? Почему? (Приведенный в характеристиках алгоритма ответ не является полным, поскольку возможны большие значения худшего коэффициента сжатия. Найдите их.)

Изображение, для которого очень выгодно применение алгоритма CCITT-3. (Большие области заполнены одним цветом).

Изображение, для которого менее выгодно применение алгоритма CCITT-3. (Меньше областей, заполненных одним цветом. Много коротких “черных” и “белых” серий).

Заметим, что единственное “сложное” выражение в нашем алгоритме: L2=МаксимальныйДопКодМеньшеL(L) — на практике работает очень просто: L2=(L>>6)*64, где >> — побитовый сдвиг L влево на 6 битов (можно сделать то же самое за одну побитовую операцию & — логическое И).

Содержание раздела