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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 02:19, 29 апреля 2016.
Open book.svg Авторство
Чичварин Н. В.
Согласовано: 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 (В)).

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

См. также