Выделение, отслеживание и описание контуров

Автор: | 30.07.2018

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

Выделение контуров

Теория

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

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

На следующем рисунке производные 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) возникает в том случае, когда черная серия текущей строки полностью покрывается белой серией предыдущей строки.
  • Для ситуации «продолжение» (б) характерно частичное перекрытие черных серий обеих строк.
  • Если две соседние черные серии текущей строки покрываются черной серией предыдущей строки, возникает ситуация «ветвление» (в).
  • Ситуация «слияние» (г)выявляется в том случае, когда черная серия текущей строки касается двух соседних черных серий предыдущей строки.
  • Ситуация «конец» (д)возникает, когда белая серия текущей строки полностью покрывает черную серию предыдущей строки.

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

Описание контуров

 

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *