Непрерывная бинарная морфология

Материал из Техническое зрение
Версия от 09:40, 27 сентября 2020; JIoku (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Следуя описанию непрерывной бинарной морфологии, данному Л.М. Местецким, примем следующие определения. Жордановой кривой называется непрерывный инъективный образ окружности при отображении его в евклидову плоскость P =${R}^{2}$.

Содержание

Плоская Фигура

Здесь ${R}$- множество действительных чисел. Важно, что жорданова кривая не имеет самопересечений. Фигурой называется связная замкнутая область плоскости, ограниченная конечным числом непересекающихся жордановых кривых. Пусть P - евклидова плоскость с соответствующим расстоянием $d({\textbf{p}}, {\textbf{q}})$, ${\textbf{p}},{\textbf{q}}\in$ P. Тогда граница фигуры $\textbf A$ определяется как множество точек $$ \partial \bf{A} = \{{\textbf{p}}: {\textbf{p}}\in \textbf{P}, \: \forall r>0 \: \textbf{D} ({\textbf{p}},\it{r}) \cap \textbf{A} \ne \emptyset , \: \textbf{D}({\textbf{p}},r) \cap \textbf{A}^{C}\ne \emptyset \}, $$

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

$$ \textbf{D}({\textbf{p}},r) = \{{\textbf{q}}: {\textbf{q}}\in \textbf{P},\: d({\textbf{p}}, {\textbf{q}}) < r\in R\}. $$

Пустой или вписанный круг

Пустым или вписанным кругом фигуры $\textbf{A}$ называется круг $\textbf{D}({\textbf{p}}, r)\subset \textbf{A}$. Максимальным пустым кругом называется пустой круг, который не содержится целиком ни в одном другом пустом круге данной фигуры. Скелетом ${\textbf{S}}(\textbf{A})$ фигуры $\textbf{A}$ называется множество центров всех ее максимальных пустых кругов. Радиальной или дистанционной функцией точки ${\textbf{p}}\in \textbf {P}$ для фигуры $\textbf{A}$ называется максимальная величина радиуса пустого круга с центром в данной точке: $$ r_{A}({\textbf{p}}) = \begin{cases} - \infty , & \mbox{ если } {\textbf{p}}\in \textbf{A}^{C}; \\ 0, & \mbox{ если } {\textbf{p}}\in \partial \textbf{A}; \\ \textrm{arg max}_{r\in R}~\{\vert \vert \textbf{D}({\textbf{p}},r)\vert \vert :\textbf{D}({\textbf{p}},r)\subset \textbf{A}\},& \mbox{ если } {\textbf{p}}\in \textbf{A}\\ \end{cases}. $$

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

Скелетным представлением фигуры является совокупность ее скелета и радиальной функции, определенной в точках скелета, $$ \textbf{SR}(\textbf{A}) = \{\langle{\textbf{p}} , r_{A}({\textbf{p}}){\rangle}: {\textbf{p}}\in \textbf{S}(\textbf{A})\}. $$ Реконструкция фигуры по скелетному представлению в точности совпадает с самой фигурой (рис. 24}): $$ \delta \textbf{SR}(\textbf{A}) = \mathop\cup\limits_{\langle p,r\rangle\in \textbf{SR}(\textbf{A})} \textbf{D}({\textbf{p}},r) = \textbf{A}. $$

Введенные таким образом элементы непрерывной бинарной морфологии полностью аналогичны введенным выше элементам общей монотонной бинарной морфологии,

6-1-24.jpg

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

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

Классическая диаграмма Вороного

Классическая диаграмма Вороного для заданного двумерного точечного множества $\textbf{A}$ определяется как кусочно-линейный граф, задающий разбиение плоскости на замкнутые непересекающиеся ячейки Вороного (множества точек)$\textbf{T}_{i}$, каждая из которых содержит все точки плоскости, для которых ближайшей точкой множества $\textbf{A}$ в смысле заданной метрики $d$ является одна и та же точка $\textbf{p}_{i}$: $$ \textbf{T}_{i} = \{{\textbf{p}}: {\textbf{p}}\in \textbf{P},\: {\textbf{p}}_{i}\in\textbf{A},\: \forall {\textbf{p}}_{j}\in \textbf{A},\: {\textbf{p}}_{j}\ne {\textbf{p}}_{i},\: d({\textbf{p}}_{i},{\textbf{p}}) < d({\textbf{p}}_{j},{\textbf{p}})\}. $$ Соответствующая точка ${\textbf{p}}_{i}$ является для ячейки $\textbf{T}_{i}$ центром притяжения или сайтом.

Обобщенная диаграмма Вороного

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

6-1-25.jpg

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

6-1-26.jpg

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

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

Cкелет многоугольной фигуры

Скелет многоугольной фигуры является подмножеством диаграммы Вороного этой фигуры: $\textbf{S}(\textbf{A})\subset \textbf{V}(\textbf{A})$. При этом скелет включает только бисекторы сайтов, не являющихся соседними.


С другой стороны, в непрерывном случае скелет фигуры можно определить как множество точек сингулярности (разрыва непрерывности производной) дистанционной функции $r_{A}({\textbf{p}})$. При этом легко убедиться, что для многоугольной фигуры функция $r_{A}({\textbf{p}})$ непрерывна внутри ячеек диаграммы Вороного. Более того, поскольку центры притяжения (сайты) имеют вид отрезков прямых и точек, то двумерная функция $r_{A}({\textbf{p}})$ внутри соответствующих ячеек Вороного однозначно описывается уравнениями наклонных плоскостей (для сайтов-сегментов) и конусов (расстояние до сайтов-точек). Таким образом, понятно, что как только вычислена диаграмма Вороного многоугольной фигуры $\textbf{V}(\textbf{A})$, то можно считать, что также известна и кусочно-гладкая ${\textit{дистанционная функция}}$ $r_{A}({\textbf{p}})$.

Полезные ссылки

  1. ☝ К началу
  2. ☜ Морфологические скелеты
Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты