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

$Отслеживающие алгоритмы$ $Отслеживающие алгоритмы$

Теория

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

Изменение яркости характеризуется высотой скачка – f₀, углом наклона – θ и координатой центра наклонного участка – x₀. Перепад яркости считается контуром, если его высота и угол наклона превосходят некоторые пороговые значения.

На следующем рисунке производные df/dх1 и df/dх2 характеризуют скорости изменения яркости в направлениях x1 и х2. Для вычисления производной по произвольному направлению используется градиент яркости:

Модуль градиента и угол его ориентации α рассчитываются по формулам:

Суть алгоритмов

Наиболее общий способ поиска градиентов яркости на изображении — обработка значений яркости f (x,y) с помощью скользящей маски-фильтра.

В каждой точке изображения (x,y) вычисляется отклик фильтра G, который есть дискретным аналогом производной яркости:

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

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

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

Оператор Превитта оперирует с областью изображения 3х3:

Оператор Собеля похож на оператор Превитта, различие заключается в использовании весового коэффициента 2 для средних элементов:

Рассмотренные выше маски применяются для получения составляющих градиента Gx и Gy. Для вычисления величины градиента эти составляющие необходимо использовать совместно:

Результаты обработки методами Превитта и Собеля продемонстрированы ниже:

$Отслеживающие алгоритмы$ $Отслеживающие алгоритмы$

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

Возможны 2-а подхода к решению этой задачи:

отслеживание каждого контура на изображении по отдельности;
сканирование всего изображения секущей полосой и соотнесения точек вдоль полосы соответствующим контурам по информации о каждой точке.

Пример первого подхода — «алгоритм жука»

«Жук» начинает сканирование с первой точки изображения. При обнаружении точки контура (черная), он переходит в режим отслеживания. В этом режиме «жук» поворачивает налево, если точка черная, иначе — направо. Процедура повторяется до тех пор, пока «жук» не вернется в исходную точку. Координаты точек перехода с черного на белое и с белого на черное и описывают границу объекта. Причем, точки описывают контур в порядке его обхода.

По «классическому алгоритму жука» может быть пропущен примыкающий контур

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

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

Дискретное представление кривой в виде последовательности точек с координатами $⟨ x, y ⟩$ крайне неэффективно. Более эффективным является представление с помощью цепных кодов (chain code), например, $8$ возможными направлениями перемещения вектора обхода контура. Подробнее см. Способы описания контуров.

Алгоритм сканирования всего изображения секущей полосой

Полоса сканирования перемещается вдоль оси Y. В ней одновременно хранятся две строки изображения (текущая и предыдущая).

Анализируются X-координаты черных серий обеих строк в порядке их возрастания (слева направо) и выявляются пять ситуаций, которые могут возникнуть:

Ситуация «начало» (a) возникает в том случае, когда черная серия текущей строки полностью покрывается белой серией предыдущей строки.
Для ситуации «продолжение» ( $б$ ) характерно частичное перекрытие черных серий обеих строк.
Если две соседние черные серии текущей строки покрываются черной серией предыдущей строки, возникает ситуация «ветвление» ( $в$ ).
Ситуация «слияние» (г)выявляется в том случае, когда черная серия текущей строки касается двух соседних черных серий предыдущей строки.
Ситуация «конец» (д)возникает, когда белая серия текущей строки полностью покрывает черную серию предыдущей строки.

Информация о каждой точке, а также рассмотренные ситуации позволяют создавать контуры . Подробнее см. Алгоритм векторизации чертежа, а также Сканирующие алгоритмы.

$Отслеживающие алгоритмы$

Автор: Николай Свирневский