10.2. Морфологические операции в дискретном пространстве

Обычно -мерные дискретные данные упорядочиваются в соответствии с  целочисленными параметрами, образуя некоторую пространственную структуру. Если эти параметры изменяются регулярным образом (например, номера столбцов и строк в дискретном изображении), структура может быть представлена в виде решетки. Построим двумерную решетку следующим образом: определим в  два линейно независимых вектора  и . Решеткой назовем множество вершин всех возможных векторов вида , где , — целые числа. Примеры наиболее распространенных решеток приведены на рис. 10.12.

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

Рис. 10.12. Примеры решеток:1-квадратная, 2-прямоугольная, 3-гексагональная

На рис. 10.13, а слева приведено три возможных задания соседства для прямоугольной решетки: соседство через стороны решетки, через узлы решетки и через стороны и узлы. Если мы примем первое определение соседства, то обнаружим, что белое поле в правой части рисунка состоит из двух частей, не связанных между собой. Следовательно, их должна разделять связная область черного цвета. Между тем такой области нет, поскольку точки черного контура тоже не связаны между собой. Если воспользуемся вторым определением соседства, получим не менее парадоксальную ситуацию: теперь точки и вне и внутри связного контура принадлежат односвязной области. Та же ситуация возникает и при третьем определении соседства.

Рис. 10.13. Соседство и связность: и - прямоугольная решетка; б — гексагональная решетка

Один из способов устранения этого противоречия состоит в том, чтобы определять по-разному соседство для белых и черных областей, скажем, для белых через стороны, а для черных - через узлы. Но тогда одни и те же операции, выполненные на изображениях, инвертированных друг относительно друга по яркости, могут приводить к различным результатам. Другой способ состоит в выборе типа решетки, не создающего вовсе этой проблемы. К такому типу относится гексагональная решетка (рис. 10.13, б). Поэтому ниже будем пользоваться этой решеткой.

Влияние анизотропии дискретного пространства демонстрирует рис. 10.14. Здесь показано поведение функции , вычисленной для объекта, представляющего дискретную аппроксимацию равностороннего треугольника на гексагональной решетке. В качестве структурного элемента используется дискретный аналог круга радиусом  - гексагон , где  - длина стороны гексагона (см. рис. 10.14,а слева). В первом случае (рис. 10.14, а) стороны треугольника параллельны базисным векторам решетки ,   и вектору , задающему третье главное направление решетки [10.2]. Во втором случае (рис. 10.14, б) треугольник повернут на угол 90°.

Рис. 10.14. Влияние ориентации на функцию формы объекта. Белым обозначены точки, исчезающие на первом шаре ; светло-серым - на втором ; темно-серым — на третьем : черным — на четвертом

Эти особенности необходимо учитывать при реализации введенных выше морфологических операций в дискретном пространстве. Существует ряд операций, которые можно определить и в непрерывном пространстве, однако их применение имеет практический смысл только на решетках. Одна из таких операций нам уже известна. Это НМ-преобразование. НМ-преобразование, использующее различные структурные элементы, позволяет выделять особые точки на изображении. Например, точки разветвления линий на гексагональной решетке могут появляться только в конфигурациях, приведенных на рис. 10.15, причем конфигурации 1-2, 3-8 и 9-14 идентичны с точностью до поворота вокруг центральной точки. Поэтому НМ-преобразование с использованием структурных элементов, построенных на базе конфигураций 1, 3 и 9, позволяет выявить любые точки разветвления.

Рис. 10.15. Конфигурации, соответствующие точкам разветвления на гексагональной решетке

 

Вычисление количества связных компонент

 

Полостями множества  называются связные компоненты множества . На гексагональной решетке количество связных компонент  и количество полостей  множества  связаны соотношением

,                               (10.18)

где символом  обозначено количество конфигураций , встречающихся в множестве . Доказательство этого утверждения можно найти в [10.2, р.185]. Если компоненты  не содержат полостей, то  просто равно их количеству, поскольку в этом случае  состоит из одной связной компоненты и, следовательно, . Но, подсчета связных компонент как мы видели раньше, НМ-преобразование выделяет в исходном множестве точки, окрестность которых совпадает со структурным элементом. Используя в НМ-преобразовании структурные элементы, приведенные на рис. 10.16, получим

          (10.19)

Рис.10.16. Структурные элементы, используемые для подсчета связанных компонент(точкой обозначено начало)

 

Утончение и утолщение

 

Операция утончения (thinning) определяется как

,                                             (10.20)

а операция утолщения (thickenning) — как

                                        (10.21)

где  — структурный элемент, состоящий из двух непересекающихся подмножеств и .

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

Так же как и ранее, введем последовательность структурных элементов  и обозначим

                                  (10.22)

последовательные утончения и

                           (10.22')

последовательные утолщения множества  с помощью последовательности структурных элементов .

Рис. 10.17. Утончение и утолщение: а - серыми кружками помечено исходное множество; б - черными кружками помечен результат HM-преобразования посредством структурного элемента , а крестиками - результат HM-преобразования посредством структурного элемента  (начало структурного элемента - кружок с точкой в центре); в — утончение;

г — утолщение

Изучим результат последовательных утончений множествa  посредством последовательности структурных элементов , где  отличаются друг от друга поворотом вокруг центральной точки (рис. 10.18). На крайнем правом рисунке показан установившийся результат последовательных утончений, который при последующих утончениях не изменяется.

Рис. 10.18. Последовательные утончения

Приведенный пример демонстрирует применение операции утончения для построения скелетона (или скелета) множества . Понятие скелетона (или скелета) достаточно интуитивно. На этом уровне его иногда пытаются описать с помощью качественной модели «степного пожара». Представим себе степной массив, покрытый сухой травой. Допустим, что одновременно вдоль всей границы массива вспыхивает огонь, распространяющийся во всех направлениях с одинаковой скоростью. В первый момент фронт распространения огня совпадает с границей. По мере его распространения различные участки фронта встречаются друг с другом и в местах встречи фронтов огонь будет гаснуть. Вот эти места самогашения огня и образуют "скелетон" массива (рис. 10.19).

Для непрерывного двумерного пространства в работе [10.2] сформулированы следующие свойства точек скелетона множества :

- если точка  является точкой скелетона, и  — наибольший круг с центром в точке , содержащийся в , то невозможно найти содержащийся в  больший круг (не обязательно с центром в точке ), содержащий ;

- круг  касается границы множества  в двух или более точках.

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

Рис. 10.19. Формирование линии гашения огня

Рис. 10.20. К определению скелетона. Максимальные круги

Из этого определения (и из рис. 10.20) следует одно замечательное свойство скелетона: если каждой точке скелетона сопоставить значение радиуса максимального круга, центром которого она является, то по скелетону можно восстановить множество , его породившее:

,

где  - радиус максимального круга для точки - скелетона,  - круг единичного радиуса. Отметим без доказательства еще одно важное свойство скелетона: если множество  связно, то его скелетон  тоже является связным множеством.

К сожалению, скелетон множества, заданного на дискретной решетке, только приближенно напоминает скелетон непрерывного множества. Более того, для одного и того же множества результат построения скелетона посредством последовательных утончений может быть различным в зависимости от порядка структурных элементов в последовательности (топологические свойства скелетона, такие как количество связных компонент, точек разветвления, ветвей, концевых точек и тому подобное при этом сохраняются). Это снова связано с анизотропией дискретного пространства. Тем не менее применение дискретного скелетона иногда оказывается чрезвычайно полезным. Так, скелетонизацию часто используют при обработке чертежей или распознавании символов для сведения линий к единичной ширине. Построение скелетона фоновой компоненты изображения, содержащего некоторое множество объектов, позволяет сегментировать его на участки, каждый из которых можно интерпретировать как зону влияния (жизненное пространство) объекта. Статистический анализ размеров, ориентации и количества соседей таких зон применяется при анализе прочностных характеристик материалов, при исследовании поведения популяций микроорганизмов и развития лесных массивов. Множество примеров применения операций утончения, утолщения и построенной на них скелетонизации можно найти в [10.2, 10.4].