Сжатие факсимильных изображений

Сжатие изображений без потерь

Стандарты на передачу изображений по общественным коммутируемым телефонным сетям разработаны Международным Телекоммуникационным Союзом (ITU-T), ранее известным как Международный Консультативный Комитет по Телефонии и Телеграфии (CCITT). Один из первых стандартов на передачу изображений без потерь относится к передаче факсимильных изображений. Изображения, используемые в таком приложении, являются битоновыми, т.е. каждая точка принимает одно из двух значений: белое или черное, и, соответственно, эти значения представляются с помощью 1 бита: 0 соответствует черной точке, а 1 – белой.

В любом битоновом изображении имеются большие области одного цвета (черного или белого). Например, на рис.1 показано несколько точек в строке битонового изображения.

Рисунок 1 – Пример линии битонального изображения

Нетрудно видеть, что шесть последовательных точек изображения имеют один и тот же цвет. Такую группу точек одного цвета будем называть серией из шести точек со значением равным 0. В двоичной форме данный фрагмент линии имеет вид 100000010100. Стандарт сжатия факсимильных изображений использует так называемое кодирование длин серий с последующим кодированием кодом Хаффмана. В нашем случае записанная последовательность преобразуется в последовательность пар (1,1) (6,0) (1,1) (1,0) (1,1) (2,0), в которых первый элемент является длиной серии, второй элемент указывает значение элементов, из которых состоит серия. Эта последовательность далее кодируется кодом Хаффмана для пар (серия, значение). Это кодирование обеспечивает более компактную запись исходного битонового изображения.

Две версии стандартов сжатия факсимильных изображений используют следующие алгоритмы кодирования:

• Модифицированный код Хаффмана. Изображение рассматривается как последовательность строк и к каждой строке применяется кодирование длин серий, т.е. каждая строка изображения преобразуется в последовательность пар (серия, значение). К этой последовательности применяется кодирование по Хаффману. Для кодирования серий из черных и белых точек используются разные коды Хаффмана, так как статистические характеристики этих серий совершенно разные. Используется фиксированный код Хаффмана, заданный таблицей, т.е. он не изменяется от изображения к изображению. Для целей обнаружения ошибок, в конце строк помещается признак EOL (конец строки).

• Кодирование с предсказанием. Значения точек в предыдущей строке используются как предсказанные значения для точек текущей строки. Для этого, начиная со второй строки, вычисляется сумма по модулю 2 точек текущей и предыдущей строк. Эта сумма затем кодируется методом длин серий с последующим кодированием кодом Хаффмана. В конце строки помещается признак EOL (конец строки). Для предотвращения распространения ошибок кодирование с предсказанием применяется попеременно с модифицированным кодом Хаффмана.

Эти подходы обеспечивают хорошее сжатие (от 20:1 до 50:1) для графических документов типа писем. Эти же алгоритмы в принципе могут быть применены для кодирования полутоновых черно-белых изображений (черно-белых фотографий). В этом случае каждой точке изображения соответствует 1 байт, и длины серий в строках изображения оказываются короткими (1-2 точки), и кодирование в соответствии с описанным стандартом оказывается неэффективным.