§ 65. Контуры

Определения и обозначения

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

Пиксель контура — пиксель, принадлежащий границе объекта. Его отличают от внутреннего пикселя по соседям: если среди соседних клеток есть фон, пиксель может считаться граничным. Это определение позволяет отделить внешнюю оболочку фигуры от её заполненной середины.

Соседние пиксели — пиксели, соприкасающиеся сторонами либо сторонами и углами. В первом случае говорят о 4-соседстве, во втором — о 8-соседстве. Выбранное правило нужно для проверки, можно ли перейти от одного граничного пикселя к другому: при диагональном соприкосновении разные правила дают разную связность.

Обход контура — последовательный переход от пикселя границы к соседнему пикселю границы. Получается упорядоченный список координат или шагов, описывающий путь вдоль края объекта. Такой порядок нужен, чтобы восстановить контур и проверить, прошёл ли алгоритм всю границу.

Как это устроено

Сначала изображение рассматривают как карту пикселей, в которой каждому пикселю приписан класс: объект или фон. Только после этого можно искать границу, потому что без различения этих классов неизвестно, где заканчивается фигура. Граничными считают пиксели объекта, у которых по принятому правилу соседства обнаруживается фон. Например, если объект — заполненный квадрат 3 × 3 пикселя, а учитываются только соседи по сторонам, центральный пиксель будет внутренним, а остальные — граничными.

Чтобы границу можно было пройти без разрывов, заранее фиксируют правило соседства. При 4-соседстве диагонально соприкасающиеся пиксели не связаны, а при 8-соседстве переход между ними разрешён. Поэтому две части, касающиеся только углами, могут восприниматься как отдельные или как соединённые. Смешивать правила во время работы нельзя: тогда алгоритм сначала будет считать одни переходы допустимыми, а затем другие, и связность контура изменится.

Обход начинают с найденного граничного пикселя, который называют начальным. Затем среди допустимых соседей выбирают следующий пиксель границы и повторяют действие, сохраняя порядок переходов. Чтобы не перескакивать на внутренние клетки или фон, на каждом шаге проверяют и принадлежность объекта, и граничный статус кандидата. Удобно отмечать посещённые пиксели: это помогает видеть пройденный путь и не записывать участок повторно.

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

Вместо хранения всех координат можно записывать направления переходов. Для этого каждому направлению сопоставляют смещение: например, вправо — изменение координаты столбца на 1, влево — на −1. Последовательно применяя смещения к начальной точке, получают пиксели пути; последняя точка замкнутого контура должна совпасть с начальной. Такая цепочка обычно занимает меньше места, чем полная копия изображения, и позволяет сравнивать форму по её границе, хотя результат зависит от начальной точки и принятого правила соседства.

Представление и обход контуров

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

Разбор задач

Задача 1. На бинарном изображении объект занимает квадрат 3 × 3 пикселя. Определите, какие пиксели относятся к контуру, если соседями считаются только пиксели, соприкасающиеся сторонами. Бинарное изображение означает, что каждый пиксель относится либо к объекту, либо к фону. Решим задачу, проверяя, есть ли у пикселя объекта сосед-фон.

1. Обозначим пиксели объекта координатами в таблице 3 × 3, а пиксели за её пределами будем считать фоном.
2. Проверим центральный пиксель: все четыре соседа по сторонам принадлежат объекту, поэтому он внутренний.
3. У каждого из восьми остальных пикселей хотя бы один сосед по стороне находится за пределами квадрата или относится к фону.

Ответ: контур образуют восемь пикселей внешнего кольца; центральный пиксель в него не входит. Если бы правило соседства включало диагонали, проверку нужно было бы выполнить заново, поскольку список соседей каждого пикселя стал бы шире.

Задача 2. В небольшом фрагменте четыре граничных пикселя образуют квадрат: (1, 1), (1, 2), (2, 2), (2, 1). Начальный пиксель — (1, 1), обход идёт по часовой стрелке, диагональные переходы не используются. Нужно записать порядок обхода и проследить направление на каждом шаге. Координаты здесь записаны как (строка, столбец).

1. Из (1, 1) идём вниз к (2, 1): строка увеличивается на 1, столбец не меняется.
2. Из (2, 1) идём вправо к (2, 2), затем вверх к (1, 2).
3. Из (1, 2) возвращаемся в начальную точку (1, 1); отмечаем, что пройдены все четыре стороны квадрата.

Ответ: порядок пикселей — (1, 1), (2, 1), (2, 2), (1, 2), затем возврат в (1, 1). При реальном обходе полезно отмечать посещённые точки и направление входа: это помогает не принять повторный заход за новый участок и не потерять нужное направление.

Задача 3. Для замкнутого контура из точки (4, 5) записаны направления: вправо, вниз, влево, вверх. Восстановите точки пути и проверьте, завершён ли обход. Для простоты каждому направлению соответствует переход на одну клетку, а координаты записаны как (строка, столбец). Следовательно, движение вниз увеличивает строку, а движение вправо — столбец.

1. Начинаем с (4, 5). Шаг вправо даёт точку (4, 6).
2. Шаг вниз приводит в (5, 6), затем шаг влево — в (5, 5).
3. Последний шаг вверх возвращает в (4, 5), то есть к начальной точке.
4. Сверяем направление и условие обхода: пройдены четыре разных стороны, после чего замыкание подтверждено.

Ответ: путь проходит через (4, 5), (4, 6), (5, 6), (5, 5) и возвращается в (4, 5). Совпадение конечной и начальной точек подтверждает замыкание для заданного простого контура, но в более сложном алгоритме также проверяют, что обход не остановился раньше времени.

Типичные ошибки

Считать контуром все пиксели объекта. Так делают, потому что на маленьком изображении внутренние клетки легко принять за часть края. Но контур включает только граничные пиксели, а заполненная середина остаётся областью объекта. Проверь себя: найди у каждой клетки соседей по принятому правилу и исключи клетки, окружённые объектом.

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

Останавливать обход при первом возвращении к началу. Такой способ прост, но точка может встретиться до того, как пройден весь контур. Для проверки учитывай не только координату, но и направление движения или состояние алгоритма. Сверь также, что все нужные участки пройдены, а не повторяется короткая часть пути.

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

Связь с другими темами

Для работы с контуром нужно понимать, как растровое изображение представляется двумерным массивом: тогда пиксели можно находить по строке и столбцу. Также пригодятся условия и циклы, потому что алгоритм проверяет соседей и повторяет шаги обхода. Обход клеток связан с темами алгоритмов поиска по графу, где пиксели выступают вершинами, а разрешённые переходы — связями. Контуры применяют при распознавании изображений, анализе формы объектов и подготовке данных для компьютерного зрения.

Что запомнить

• Контур — граница объекта на изображении.
• Пиксель границы определяется относительно выбранного правила соседства.
• Правило соседства влияет на связность контура.
• Обход контура задаёт упорядоченную последовательность граничных пикселей.
• Условие остановки должно предотвращать преждевременное завершение и зацикливание.
• Последовательность направлений может компактно кодировать форму контура.