Морфологические скелеты. Непрерывная бинарная морфология Непрерывная бинарная морфология

Следуя описанию непрерывной бинарной морфологии, данному Л.М. Местецким [31], примем следующие определения.

Жордановой кривой называется непрерывный инъективный образ окружности при отображении его в евклидову плоскость P=R². Здесь R – множество действительных чисел. Важно, что жорданова кривая не имеет самопересечений. Фигурой называется связная замкнутая область плоскости, ограниченная конечным числом неперсекающихся жордановых кривых. Пусть P – евклидова плоскость с соответствующим расстоянием d(p,q), p,qP. Тогда граница фигуры A определяется как множество точек

A = {p: pP, r>0, D(p,r)  A ,

D(p,r)  A^C },

где A^C = P \ A – дополнение или фон фигуры A; D(p,r) – открытый круг радиуса r с центром в точке p, определяемый выражением

D(p,r) = {q: qP, d(p,q) < rR}.

Пустым или вписанным кругом фигуры A называется круг D(p,r)  A. Максимальным пустым кругом называется пустой круг, который не содержится целиком ни в одном другом пустом круге данной фигуры. Скелетом S(A) фигуры A называется множество центров всех ее максимальных пустых кругов. Радиальной или дистанционной функцией точки pP для фигуры A называется максимальная величина радиуса пустого круга с центром в данной точке:

r_A(p) = { - : pA^C; 0: pA;

argmax_rR {||D(p,r)||:D(p,r)A}: pA}.

Скелетным представлением фигуры является совокупность ее скелета и радиальной функции, определенной в точках скелета

SR(A) = {<p, r_A(p)>: pS(A)}.

Реконструкция фигуры по скелетному представлению в точности совпадает с самой фигурой (рис. 6.1.24):

SR(A) =  _{<p,r>SR(A)} {D(p,r)} = A.

@Рис. 6.1.24. Прямоугольник и его реконструкция по скелетному представлению.

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

Классическая диаграмма Вороного для заданного двумерного точечного множества A определяется как кусочно-линейный граф, задающий разбиение плоскости на замкнутые непересекающиеся ячейки Вороного (множества точек) T_i, каждая из которых содержит все точки плоскости, для которых ближайшей точкой множества A в смысле заданной метрики d является одна и та же точка p_i:

T_i = {p: pP, p_iA,p_jA, p_jp_i, d(p_i,p) < d(p_j,p)}.

Соответствующая точка p_i является для ячейки T_i центром притяжения или сайтом.

В обобщенной диаграмме Вороного в качестве сайтов (центров притяжения) могут рассматриваться не только отдельные точки, но и фигуры (множества точек), например, непрерывные сегменты линий границы. В частности граница многоугольной фигуры представляется в виде (циклически) упорядоченного множества сайтов двух типов: сайтов-точек и сайтов-сегментов. Сайт-точка и сайт-сегмент, имеющие непустое пересечение, называются соседними сайтами. Сайт-точка считается ближайшим сайтом для некоторой точки p, если он является ближайшей точкой границы A к данной точке p. Сайт-сегмент считается ближайшим сайтом для некоторой точки p, если он включает ближайшую точку границы A к данной точке p, причем эта ближайшая точка является ортогональной проекцией точки p на прямую, содержащую данный сайт. Ячейкой Вороного для данного сайта границы является множество точек плоскости, для которых данный сайт является ближайшим.

Сайты называются смежными, если их ячейки Вороного имеют общую невырожденную границу (более одной общей точки). Бисектором пары сайтов называется линия, являющаяся общей границей ячеек двух смежных сайтов. Диаграммой Вороного V(A) многоугольной фигуры A называется объединение бисекторов всех ее сайтов.

Как показано в [31], скелет многоугольной фигуры является подмножеством диаграммы Вороного этой фигуры: S(A)  V(A). При этом скелет включает только бисекторы сайтов, не являющихся соседними.

а) б) в)

@Рис. 6.1.25. Построение непрерывного скелета многоугольной фигуры: а) исходное растровое изображение, б) контур-многоугольник, в) скелет.

а) б) в)

@Рис. 6.1.26. Построение непрерывного скелета многоугольной фигуры: а) исходное растровое изображение, б) контур-многоугольник, в) скелет.

С другой стороны, в [31] также отмечено, что в непрерывном случае скелет фигуры можно определить как множество точек сингулярности (разрыва непрерывности производной) дистанционной функции r_A(p). При этом легко убедиться, что для многоугольной фигуры функция r_A(p) непрерывна внутри ячеек диаграммы Вороного. Более того, поскольку центры притяжения (сайты) имеют вид отрезков прямых и точек, то двумерная функция r_A(p) внутри соответствующих ячеек Вороного однозначно описывается уравнениями наклонных плоскостей (для сайтов-сегментов) и конусов (расстояние до сайтов-точек). Таким образом, как только вычислена диаграмма Вороного многоугольной фигуры V(A), можно считать, что также известна и кусочно-гладкая дистанционная функция r_A(p).