Выделение контуров — определение набора пикселей, которые проходят на границе между двумя областями изображения. Отслеживание контуров (векторизация) — представление граничных точек контура последовательностью из множество точек контура. Описание контуров — определение линий, которыми аппроксимируется последовательность из множество точек контура.
Выделение контуров
Теория
Под контуром изображения будем понимать точки, между которыми происходит изменение значений яркости яркости.
Изменение яркости характеризуется высотой скачка – 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) возникает в том случае, когда черная серия текущей строки полностью покрывается белой серией предыдущей строки.
- Для ситуации «продолжение» (б) характерно частичное перекрытие черных серий обеих строк.
- Если две соседние черные серии текущей строки покрываются черной серией предыдущей строки, возникает ситуация «ветвление» (в).
- Ситуация «слияние» (г)выявляется в том случае, когда черная серия текущей строки касается двух соседних черных серий предыдущей строки.
- Ситуация «конец» (д)возникает, когда белая серия текущей строки полностью покрывает черную серию предыдущей строки.
Информация о каждой точке, а также рассмотренные ситуации позволяют создавать контуры . Подробнее см. Алгоритм векторизации чертежа, а также Сканирующие алгоритмы.
Описание контуров
- Способы описания контуров.
- Кусочно-линейная аппроксимация.
- Аппроксимация сплайнами.
- Функция кривизны.
- Перегиб.
- Особые точки контуров.
Полезные ссылки:
Автор: Николай Свирневский