Метод водоразделов (Сегментация)

	Авторство
		Чичварин Н. В.
	Согласовано: 29.04.2016

Статья по учебной дисциплине
Название дисциплины:	Обнаружение и распознавание сигналов
Раздел:	8. Распознавание и идентификация сигналов на физическом уровне
Глава:	8.1 Предварительная обработка изображений
Преподаватель:	Чичварин Н. В.

Метод водоразделов -- один из основных алгоритмов наращивания областей, рекурсивно выполняющих процедуру группировки пикселей в подобласти по заранее заданным критериям.

Концепции

Данный метод включает в себя следующие три базовых концепции:

• Обнаружение и устранение разрывов;
• Пороговая обработка;
• Обработка областей;

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

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

• точки локального минимума;
• точки, находящиеся на склоне, с которых вода сливается к центру водоема;
• точки, находящиеся на гребне возвышенности.

Линии, образованные точками-гребнями, представляют собой линии водоразделов, поэтому основной задачей данного метода является именно поиск линий водоразделов.

Алгоритм

1. В местах локального минимума образуем «дырки», через которые вода начнет заполнять трехмерную поверхность.

2. Если вода с двух сторон гребня готова объединиться в один бассейн, устанавливаем перегородку.

3. Когда над водой останутся только загородки, останавливаем алгоритм.

Полученные таким образом перегородки и есть требуемые линии водоразделов.

На рис. 1. приведено пошаговое выполнение алгоритма. На верхнем левом рисунке показан оригинальный «рельеф» некоторого изображения, на нижем правом – результат работы алгоритма.

Рис. 1. Пример работы алгоритма водоразделов.

Водораздел путем дилатации

Рис. 2. Построение водоразделов методом дилатации.

Другой простейший способ построения перегородок – использование морфологической дилатации. Пример использования этого способа приведен на рис. 2.

В качестве примитива в данном случае используется матрица 3*3 элемента.

Во время работы алгоритма используются два правила:

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

На рис. 2 (А) показаны две начальные области. При применении дилатации к областям (рис. 2 (Б)) их площадь увеличивается. На следующем шаге (рис. 2 (В)) наращиваемые области готовы слиться в одну – значит необходимо установить перегородку. После того, как точки раздела найдены, им присваивается значение равное максимальной яркости + 1. Это предотвращает слияние областей в ходе работы алгоритма. Важно отметить, что полученные линии водораздела являются связными компонентами, не имеющими разрывов в линиях сегментации.

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

Водораздел с маркерами

Маркер представляет собой связную компоненту, принадлежащую изображению. Будем различать внешние (соответствуют фону) и внутренние (относящиеся к объекту) маркеры.

Рис. 3. Пример водораздела с использованием маркеров.

Процедура выбора маркера состоит из двух главных шагов:

1. предобработка;
2. выработка критериев, которым должны удовлетворять маркеры.

Пусть внутренний маркер определен как область со следующими критериями:

• окружена точками с большим значением яркости;
• ее точки образую компоненту связности;
• все точки имеют одинаковое значение яркости.

Внутренние маркеры, найденные по этим 3 правилам, показаны на рис. 3 (Б) светло-серым цветом.

Далее применяем алгоритм сегментации по водоразделам с тем ограничением, что в качестве локальных минимумов рассматриваются только локальные маркеры.

В итоге получим изображение, гораздо лучше читаемое по сравнению с исходным изображением (рис. 3 (В)).

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

См. также

• Морфологические методы
• Пороговые методы
• Текстурные методы