10. Основные морфологические алгоритмы

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

Выделение границ.

Граница множества А, которую будем обозначать β(А), может быть выделена путем выполнения сначала операции эрозии А по В, а затем получения разностного множества между А и результатом его эрозии, т.е.

,

где В — подходящий примитив.

На рис. 2.29 иллюстрируется механизм выделения границы. Здесь приведены простой двоичный объект, примитив В и результат применения соотношения.

Заполнение областей.

Рассмотрим алгоритм заполнения области, основанный на операциях дилатации, дополнения и пересечения множеств. На рис. 2.30 исходное множество А состоит из граничных точек некоторой области, образующих 8-связный замкнутый путь. Задача состоит в том, чтобы, начав с некоторой точки р внутри этой границы, заполнить единичными значениями всю область.

Если принять соглашение, что все точки, кроме граничных, имеют значения 0, то в качестве начального шага присвоим значение 1 точке р. К заполнению области единицами приведет следующая рекуррентная процедура:

, k = 1,2,3, (2.20)

где X₀ = р, а В – симметричный примитив, показанный на рис. 2.30, в. Данный алгоритм останавливается на k шаге итерации, когда X_k = X_k-1. Объединение множеств X_k и A содержит границу области вместе с ее внутренним заполнением.

При отсутствии дополнительного контроля процесс дилатации привел бы к заполнению единицами всего поля изображения. Однако коррекция на каждом шаге области по формуле 2.20 ограничивает результат операции только внутренностью интересующей области.

На рис. 2.31, а приведено изображение, состоящее из белых кругов с черными пятнами внутри. Подобное изображение могло быть получено в результате порогового преобразования изображения сцены, в которой присутствуют полированные сферические объекты (например, подшипниковые шарики). Темные пятна внутри кругов могли возникнуть в результате отражений. Задача состоит в устранении этих отражений путем заполнения светлых областей.

На рис. 2.31, а нанесена точка, выбранная внутри одного из кругов, а на рис. 13, б показан результат заполнения соответствующей области. Наконец, рис. 13, в демонстрирует результат заполнения всех таких областей.

Выпуклая оболочка.

Множество А называется выпуклым, если отрезок прямой, соединяющий любые две точки А, целиком лежит внутри А. Выпуклая оболочка Н произвольного множества S – это наименьшее выпуклое множество, содержащее S. Разность множеств H\S называется дефектом выпуклости S. Выпуклая оболочка и дефект выпуклости полезны для построения описания объектов. Здесь мы представим простой морфологический алгоритм построения выпуклой оболочки С(А) исходного множества А.

Обозначим Вⁱ, i = 1, 2, 3, 4 четыре примитива, показанные на рис. 2.32, а. Описываемая процедура состоит в применении рекуррентного соотношения

(2.21)

Для (см. рис.2.32, б) , где индекс «сход» указывает на момент сходимости . Тогда выпуклая оболочка А есть множество

. (2.22)

Другими словами, процедура состоит в итеративном применении к множеству А HM-преобразования по примитиву B¹, объединении с множеством А и повторении этих шагов (преобразования и объединения) до тех пор, пока происходят изменения; результат обозначается D¹. Затем такие же действия повторяются в применении к А преобразования по примитиву В² и так далее. Объединение четырех полученных множеств Dⁱ дает в результате выпуклую оболочку множества А.

Рис. 2.32 иллюстрирует процедуру, задаваемую соотношениями (2.21) и (2.22). На рис. 2.32,а показаны примитивы, используемые для построения выпуклой оболочки. Начало координат каждого находится в его центре. Знаки × на элементах примитивов указывают, что значения этих пикселей не важны. Иначе говоря, эквивалентом в множестве А для данного примитива признается такая область с размерами 3×3 пикселя, значения в которой совпадают с конфигурацией нулей (белое поле) и единиц (темное поле) в этом примитиве вне зависимости от значений пикселей на позициях, отмеченных знаком ×. Конкретно, для каждого примитива используется маска с нулем в центре и тремя единицами вдоль одной из сторон квадрата, остальные пиксели не учитываются. С учетом обозначений на рис. 2.32, а, примитив Вⁱ получается из В^i-1 поворотом на угол 90° по часовой стрелке.

На рис. 2.32, б показано множество А, для которого требуется построить выпуклую оболочку. Начиная с после четырех итераций применения соотношения (2.19) приходим к множеству, показанному на рис. 2.32, в. Затем полагаем и вновь с помощью (2.19) приходим к множеству, показанному на рис. 2.32, г (в этом случае сходимость происходит уже за два шага). Следующие два результата получаются аналогичным образом. В конце строится объединение множеств из рис. 2.32, в – 2.32, е, которое и является искомой выпуклой оболочкой (рис. 2.32, ж). На рис. 2.32, з обозначен вклад, который вносит в это составное множество каждый из применявшихся примитивов.

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