3.5. Кодирование с переменной длиной кодовой последовательности

Существует несколько способов кодирования, позволяющих еще больше сжать информацию о бинарных изображениях. Одним из широко распространенных является кодирование с переменной длиной кодовой последовательности. Этот метод основан на том, что вдоль любой просматриваемой в данный момент строки обычно обнаруживаются длинные цепочки нулей и единиц. Поэтому вместо передачи отдельных битов информации мы можем посылать длины подобных цепочек. Код с переменной длиной для строки изображения есть просто [1, 4, 3, 2, 4].

есть просто [1, 4, 3, 2, 4].

Для обозначения начала каждой строки нужно ввести специальный признак. Кроме того, принимается соглашение относительно того, с чего начинается строка (с нуля или единицы). Если строка начинается с противоположного символа, то первым символом кода устанавливается нуль.

Условимся, что представляет собой цепочку в строке и что первая цепочка в каждой строке есть цепочка нулей. (Таким

образом, все четные цепочки будут соответствовать единицам на изображении.) Пусть количество цепочек в строке. Как использовать коды с переменной длиной для быстрого вычисления требуемых геометрических характеристик? Ясно, что площадь — просто сумма кодов цепочек, соответствующих единицам на изображении

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

Отсюда нетрудно найти вертикальное положение геометрического центра

Но как быть с вертикальной проекцией Вспомните: каждое

Рис. 3.9. Горизонтальная проекция, которая сопоставляет каждой строке количество элементов изображения, принимающих значение «единица». Эту проекцию легко найти из изображения, кодированного кодом переменной длины. Достаточно просуммировать в каждом ряду коды с четными номерами.

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

Теперь рассмотрим первые разности значений вертикальной проекции

Их, очевидно, можно получить на основе информации, содержащейся не в самом изображении, а в первых горизонтальных разностях изображения:

Первая разность имеет перед самим изображением то преимущество, что она отлична от нуля только в начале каждой цепочки. Она равна там, где значение элемента изображения меняется с 0 на 1, и -1 там, где оно изменяется с 1 на 0 (рис. 3.10). Мы можем локализовать эти места, вычислив суммарные коды

или рекурсивно После этого для получения первой разности вертикальной проекции необходимо найти разность между числом суммарных кодов равных с нечетным к и числом суммарных кодов равных с четным к

Из полученных первых разностей сама вертикальная проекция определяется простым суммированием

или рекурсивно Пример расчетов приведен на рис. 3.10. Зная вертикальную проекцию, нетрудно найти горизонтальное положение геометрического центра

В упражнении 3.8 показывается, что диагональную проекцию можно получить путем, аналогичным тому, который мы использовали для получения вертикальной проекции.

Рис. 3.10. Первые разности вертикальной проекции, вычисляемые с помощью проекции первых разностей для строк изображения.

Сама вертикальная проекция находится затем суммированием результата слева направо.