18.6. КОНТУРНАЯ СЕГМЕНТАЦИЯ

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

 

Аппроксимация кривых

 

Методы аппроксимации кривых, описанные в разд. 18.3, можно использовать для контурной сегментации путем подбора аналитически заданной кривой к совокупности точек контурного препарата, полученного с помощью детектора перепадов. Если имеется априорная информация относительно ожидаемой формы объекта, например известно, что это прямоугольник или окружность, то в качестве аппроксимирующей кривой нужно взять прямоугольник или окружность. Или же можно попытаться применить аппроксимацию полиномами, используя описанные в разд. 18.3 итеративные методы подбора прямых линий. Метод подбора кривых достаточно хорошо подходит для объектов с простой структурой. Трудности возникают, когда изображение содержит множество перекрывающихся объектов и точки перепадов образуют ветвистые структуры.

 

Прослеживание контуров

 

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

Рис. 18.6.1. Примеры прослеживания внешних контуров: а – начальная точка расположена вверху слева; б – начальная точка расположена внизу справа.

После того как жук пересечет черный элемент, он поворачивается налево и переходит к следующему элементу. Если этот элемент черный, жук снова поворачивается налево, если же элемент оказывается белым, то жук поворачивается направо. Эта процедура продолжается до тех пор, пока жук не вернется в исходную точку. Декартовы координаты точек перехода с черного на белое или с белого на черное дают местоположение границы. На рис. 18.6.1, а выступающий элемент в нижнем правом углу объекта, обладающий восьмисвязностью со своим ближайшим соседом, не включен в границу. Заметим, однако, что этот выступающий элемент на рис. 18.6.1, б включен в границу объекта, но здесь начальная точка передвинута. Таким образом, определение границы зависит от точки начала движения. Другая трудность связана с наличием «дыр» внутри объекта, которые жук может пропустить. Проблемы такого характера можно преодолеть, снабдив жука некоторой памятью и интеллектом, что позволит ему запоминать свои прошлые шаги и возобновлять прослеживание, если данный путь оказывается ошибочным. Описанный алгоритм чаще всего применяется к яркостным изображениям, подвергнутым пороговому ограничению, но данную идею легко можно распространить и на многоградационные изображения. Один из подходов состоит в том, что граничная точка отмечается, если разница яркостей соседних элементов изображения достаточно велика. В результате жук формирует контуры по ходу своего движения.

 

Соединение точек перепадов

 

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

Метод соединения точек перепадов, разработанный Робертсом [54], основан на тех же основных принципах, что и большинство других методов такого связывания.

Рис. 18.6.2. Примеры соединения точек перепадов по правилу Робертса: а - соединение точек перепадов; б - исключение множественных соединений и замена их мостиками из прямых линий.

В методе Робертса аналоговые значения градиентов (разностей яркости соседних элементов) анализируются блоками размером  элемента. Элемент с наибольшим в блоке значением модуля градиента считается пробной контурной точкой, если это значение больше порога. Затем к значениям градиента около этой пробной точки подбираются линии длиной в пять элементов с ориентацией «север», «восток», «юг» и «запад». Если отношение наилучшей аппроксимации к наихудшей больше второго порога, то пробная контурная точка объявляется действительной и ей приписывается ориентация, соответствующая наилучшей аппроксимации.

Рис. 18.6.3. Правила соединения точек перепадов [56].

Далее к парам контурных точек подбираются прямые линии, если эти точки расположены в смежных блоках размером  элемента и если направление каждой линии находится в диапазоне  относительно ориентации контура в каждой контурной точке. Точки, не удовлетворяющие критериям соединения, отбрасываются. Типичная граница, полученная на этом этапе, будет содержать, как видно из рис. 18.6.2, а, разрывы, и множественные соединения точек. Маленькие треугольники исключаются вычерчиванием наибольшей стороны, а маленькие четырехугольники заменяются их наибольшей диагональю (рис. 18.6.2, б). Короткие выступающие линии также уничтожаются. На этом этапе короткие разрывы заменяются мостиками из прямых линий. Этот вид соединения точек перепада можно использовать для широкого класса детекторов перепадов. В работе [55] подобный метод применен для соединения точек, полученных с помощью детектора перепадов Хюккеля.

Рис. 18.6.4 Пример построения контуров с использованием алгоритма соединения точек перепада [56]: а - без соединения; б — с соединением.

Робинсон [56] предложила простой, но эффективный алгоритм соединения, при использовании которого точки перепада, полученные с помощью детектора, дающего возможность определить, ориентацию перепада в системе восьми курсовых направлений, исследуются по блокам из 3x3 элементов (рис. 18.6.3). Точка перепада в центре области считается действительной контурной точкой, если ее соседи по соответствующим направлениям принадлежат к перепадам надлежащей ориентации. Рис. 18.6.4 иллюстрирует возможность данного способа удалять явно посторонние перепады фона. Применение окон большего размера было бы полезно, однако с увеличением размера окна количество возможных связей действительного контура будет быстро расти.