Раздел 2
ТОПОЛОГО-ГЕОМЕТРИЧЕСКАЯ СИСТЕМА МОДЕЛЕЙ
ИЗОБРАЖЕНИЙ и СТРУКТУРА ОБЩЕЙ ЗАДАЧИ СЕГМЕНТАЦИИ
Отсутствие формализованных подходов к оценке точности и качества сегментации,
учитывающих дискретное представление исходных данных и результатов их
обработки, затрудняет разработку эффективных методов сегментации, оценку
результатов их применения и их использования для решения задач построения
связных границ, их аппроксимации и идентификации. Поэтому с целью корректного
моделирования спектра рассматриваемых задач сегментации вводится система
топологических и геометрических моделей областей и линий, а также критерии
качества сегментации; на этой основе формулируются основные задачи, к которым
сводится общая задача сегментации.
2.1. Исходные данные
Исходные данные представлены полутоновым входным изображением некоторой
совокупности из объектов в поле зрения; это изображение задается матрицей
значений яркости на области входного изображения , , , где – узлы прямоугольной
решетки на плоскости с единичным шагом по обеим координатам, образующие которой
параллельны осям координат. Яркость в соответствующих узлах области принимает
значение на интервале целых неотрицательных чисел . При рассмотрении этих узлов
на плоскости, для определенности, будем называть их точками. Изображение
объекта , аналогично входному изображению, представлено распределением яркости
в узлах области изображения , . При этом фоном называется изображение , где .
Иначе говоря, предполагается, что каждый узел, с учетом погрешности
дискретизации, может быть отнесен либо к фону, либо к одному из объектов. На
практике, однако это предположение не всегда справедливо; анализ этой ситуации
производится в разделе 3.
2.2. Базовая система топологических моделей
В топологии, область , лежащая на плоскости, называется односвязной [130], если
непрерывной деформацией любая петля в ней стягивается в точку; подобная область
имеет тип диска (рис. 2.1.а). При этом линейно связное множество с компонентой
границы имеет топологический тип диска с дырками (рис. 2.1.б, в), а ее
фундаментальная группа является свободной группой [162]; такие области
называются неодносвязными.
В практически значимых случаях неодносвязных областей рассматривают замыкание
области с выколотыми дисками (рис. 2.1.б), а сингулярные множества типа "точка"
или "линия" (рис. 2.1.в) не рассматриваются [83], как и случай выколотого
диска, граница которого касается границы заданной области (рис. 2.1.г).
а) б) в) г)
Рис. 2.1. Основные топологические типы областей на плоскости
При этом область , имеющая тип диска с дырками (на рис. 2.1.б имеем )
определяется следующим образом
(2.1)
где – односвязные области,
– операция замыкания.
Диск называется носителем, его граница – внешней границей области, а границы ,
, назовем внутренними.
Рассмотрение диска с дырками исчерпывающим образом определяет топологическую
модель рассматриваемых в задачах сегментации областей на плоскости и,
посредством (2.1) задает их структуру (вложения) и топологическую
классификацию.
Рассмотрим, как описанную топологию (с евклидовой метрикой) можно перенести на
область . Пусть и . Назовем множество -окрестностью узла в . Ясно, что для
всякого узла в число различных его окрестностей конечно, причем для различных
окрестности узла могут совпадать.
Топология объектов поля зрения, проецируемых на плоскость (перпендикулярную
главной оптической оси регистрирующего устройства), и их дискретных аналогов –
изображений, заданных в , существенно различна. Поэтому для моделирования
изображений, обеспечивающего учет топологических свойств объектов в ,
необходимо ввести соответствующие дискретные аналоги.
Узлы и называются [31] 4-связными (рис. 2.2.а), если выполняется условие ;
соответственно, 8-связными (рис. 2.2.б), если имеет место равенство .
а) б)
Рис. 2.2. 4- и 8-связность узла (обозначен серым цветом)
Единичную окрестность узла назовем элементарной. Тогда все узлы единичной
окрестности узла 4-связны с ним, а все узлы в окрестности , , узла – 8-связны с
этим узлом. Если не оговорено иное, будем называть 4-связные узлы смежными.
Множество назовем линейно (4-)связным, если для всякой пары его узлов
существует последовательность смежных узлов с началом в и концом в , которую
назовем путем. Соответственно, 8-связный аналог пути назовем линией и, при
необходимости, будем рассматривать линейную 8-связность. Если в случае областей
на плоскости линейная связность влечет связность, и наоборот, то в пространстве
такая эквивалентность может иметь место для 8-связности, но не выполняться для
4-связности. Поэтому в дальнейшем изложении эти типы связности различаются.
Пополнением линии назовем множество узлов, если в совокупности они образуют
путь. Ясно, что каждый узел пополнения – это один из двух узлов: или , смежных
8-связным узлам и линии, и , введение которого делает последовательность узлов
4-связной, т.е. путем.
Если начальный и конечный узлы пути, линии совпадают (4- или 8-связны,
соответственно), он называется замкнутым (квазизамкнутым); заметим, что оба эти
типа путей составлены из одного и того же множества узлов. Если всякий узел
пути (линии) связен лишь с предшествующим или последующим, путь (линия)
является простым, что на плоскости означает отсутствие самопересечений.
Элементарная окрестность узла включает его и множество смежных ему узлов; для
этих пяти узлов – узел назовем внутренним. Соответственно, узел является
вну