Чейнкод

Чейнкод — это компактный способ представления границ бинарных изображений или контуров объектов в виде последовательности кодовых символов, описывающих направление движения вдоль контура. Является одним из базовых методов цепного кодирования в области компьютерного зрения, цифровой обработки изображений и распознавания образов. Чейнкод позволяет эффективно хранить, передавать и анализировать форму объекта, сводя двумерное описание границы к одномерной последовательности.

История

Метод цепного кодирования был впервые предложен Гербертом Фрименом (Herbert Freeman) в 1961 году в статье «On the Encoding of Arbitrary Geometric Configurations» (IRE Transactions on Electronic Computers). Фримен разработал алгоритм для представления непрерывных кривых и контуров с помощью последовательности направленных отрезков фиксированной длины, соединяющих соседние пиксели. Первоначально метод использовался для обработки изображений в системах автоматического распознавания символов и анализа формы в военной и промышленной разведке. В 1970-е годы, с развитием цифровых сканеров и ЭВМ, чейнкод стал стандартным инструментом в задачах описания формы объектов, а в 1980-е — основой для построения контурных дескрипторов в системах машинного зрения.

Принцип работы

Чейнкод строится на основе бинарного изображения, где объект представлен пикселями одного цвета (например, белого), а фон — другого (чёрного). Процесс кодирования включает несколько этапов:

1. Выделение контура. С помощью алгоритмов трассировки (например, алгоритма «жука» или метода Мура-Неймана) определяется последовательность граничных пикселей объекта. Контур обычно обходится по часовой стрелке или против неё.

1. Выбор системы направлений. Для описания перехода от одного пикселя к соседнему используется фиксированный набор направлений. Наиболее распространены две системы:

• 4-связный чейнкод (4-соседство): допускает движение только по горизонтали и вертикали (вверх, вниз, влево, вправо). Коды: 0 (вправо), 1 (вверх), 2 (влево), 3 (вниз).
• 8-связный чейнкод (8-соседство): дополнительно включает диагональные направления. Коды: 0 (вправо), 1 (вправо-вверх), 2 (вверх), 3 (влево-вверх), 4 (влево), 5 (влево-вниз), 6 (вниз), 7 (вправо-вниз).

1. Генерация последовательности. Начиная с произвольной точки контура, для каждого шага к соседнему пикселю записывается код направления. Полученная последовательность чисел (например, «0 1 2 3 0 7 6 5 4») и есть чейнкод.

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

Классификация

По связности

• 4-связный чейнкод: проще в вычислении, но менее точен для криволинейных контуров. Используется для грубого описания формы.
• 8-связный чейнкод: точнее передаёт геометрию, особенно диагональные участки, но требует больше памяти (коды от 0 до 7 против 0–3).

По способу обхода

• Обычный (абсолютный) чейнкод: коды направлений задаются относительно фиксированной системы координат (например, «вправо» всегда означает движение по оси X в положительную сторону).
• Дифференциальный чейнкод: кодируются изменения направления относительно предыдущего шага. Например, поворот на +1 (влево) или –1 (вправо). Этот вариант более устойчив к поворотам объекта.

По способу представления

• Цепной код Фримена: классический вариант с фиксированной длиной шага (1 пиксель).
• Обобщённый чейнкод: допускает шаги переменной длины или кодирование не только направления, но и расстояния между точками (например, для сглаженных контуров).

Применение

Чейнкод широко используется в задачах, где требуется компактное описание формы объекта:

• Распознавание образов: сравнение контуров объектов (букв, цифр, силуэтов) по их цепным кодам. Например, в системах оптического распознавания символов (OCR) для идентификации шрифтов.
• Сжатие изображений: хранение границ объектов вместо растровых данных позволяет значительно сократить объём памяти для бинарных изображений (например, в факсимильной связи или картографии).
• Анализ формы: вычисление геометрических характеристик (периметр, площадь, кривизна, моменты) на основе последовательности кодов. Чейнкод позволяет быстро оценить компактность, вытянутость или изрезанность контура.
• Компьютерная графика: построение контурных линий на картах, обработка штриховых рисунков, векторизация растровых изображений.
• Робототехника: планирование траекторий движения вдоль границ препятствий или объектов.
• Биометрия: анализ формы отпечатков пальцев, радужной оболочки глаза или силуэта человека.

Достоинства и недостатки

Достоинства

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

Недостатки

• Чувствительность к шуму: одиночные выбросы пикселей на границе приводят к искажению кода.
• Зависимость от масштаба: при изменении размера объекта (увеличении/уменьшении) чейнкод меняется, если не применять нормализацию по длине шага.
• Проблема начальной точки: без нормализации один и тот же контур может быть представлен разными последовательностями.
• Потеря информации о кривизне: для гладких кривых дискретизация по пикселям вносит ошибки, особенно при малых размерах объекта.

Интересные факты

• Чейнкод является основой для многих более сложных контурных дескрипторов, таких как цепные коды с цепями Маркова, фурье-дескрипторы и сигнатуры формы.
• В 1970-х годах метод использовался в советских системах распознавания рукописного текста, например, в аппаратно-программном комплексе «Рута».
• Существует модификация чейнкода — «код Фримена с переменным шагом», где длина шага может быть больше 1 пикселя, что позволяет описывать контуры с меньшей детализацией, но с большей устойчивостью к шуму.
• В задачах сжатия изображений (например, в формате JBIG) цепное кодирование применяется для представления границ областей, что даёт выигрыш в 2–5 раз по сравнению с растровым хранением.

Источники

• Freeman H. On the Encoding of Arbitrary Geometric Configurations // IRE Transactions on Electronic Computers. — 1961. — Vol. EC-10, No. 2. — P. 260–268.
• Гонсалес Р., Вудс Р. Цифровая обработка изображений. — М.: Техносфера, 2012. — Глава 11: Описание формы.
• Jain A. K. Fundamentals of Digital Image Processing. — Prentice Hall, 1989. — Chapter 9: Shape Representation.
• Прэтт У. Цифровая обработка изображений. — М.: Мир, 1982. — Т. 2, Глава 18: Описание и распознавание объектов.