Регуляризация скелета по Тихонову

Материал из Техническое зрение
Перейти к: навигация, поиск

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

Скелет, полученный с помощью оператора $\mathfrak{I} :F\to \mbox{Sk}$ устойчив на паре метрических пространств $(\Phi ,\Lambda )$ с расстояниями $\rho _\Phi (\cdot ,\cdot )$ и $\rho _\Lambda (\cdot ,\cdot )$, если для всякого $\epsilon >0$ существует такое $\delta (\epsilon )>0$, что для любых двух фигур $F_1 ,F_2 \in \Phi $ из неравенства $\rho _\Lambda (\mbox{Sk}_1 ,\mbox{Sk}_2 )<\delta (\epsilon )$ следует неравенство $\rho _\Phi (F_1 ,F_2 )<\epsilon $, где $\mbox{Sk}_1 =\mathfrak{I} (F_1 )$, $\mbox{Sk}_2 =\mathfrak{I} (F_2 )$.

Оператор построения непрерывного скелета ${\mu}:F\to \mbox{Sk}$ неустойчив на паре метрических пространств $(\Phi ,\Lambda )$, представляющих собой соответственно пространство фигур и скелетных графов с расстояниями: $\rho _\Phi (\cdot ,\cdot )$ - расстояние Хаусдорфа, $\rho _\Lambda (\cdot ,\cdot )$ - топологическое расстояние (например, разность числа ребер скелетных графов).

Рассмотрим пример простейшего устойчивого оператора скелетизации. Назовем $\textit{оператором выделения линейного скелета}$ ${\mu}^0:F\to \mbox{Sk}^0$ такой оператор, который по заданной фигуре $F$ строит скелетный граф, являющийся подграфом ${\mu}(F)$ и представляющий собой непрерывную цепочку ребер максимальной длины: $ \mbox{Sk}^0=e $ (рис. 42 $\it{в}$). Оператор выделения линейного скелета ${\mu}^0:F\to \mbox{Sk}$ устойчив на паре метрических пространств $(\Phi ,\Lambda )$ с расстояниями $\rho _\Phi (\cdot ,\cdot )$ и $\rho _\Lambda(\cdot ,\cdot )$.

6-1-42.jpg

Рис. 42 Регуляризация скелета: $\textit{а}$ - непрерывный скелет; $\textit{б}$ - промежуточный скелет; $\textit{в}$ - устойчивое решение

К сожалению, оператор выделения линейного скелета ${\mu}^0(F)$ не несет достаточной информации о форме для сравнения фигур, хотя и может быть использован как некий численный признак фигуры. Исходный оператор ${\mu}(F)$ неустойчив, что делает его для задач сравнения формы также непригодным. Значит, необходимо найти какой-то промежуточный скелетный оператор (рис. 42 $\textit{б}$) между неустойчивым, содержащим в себе "лишнюю" информацию ${\mu}(F)$ (рис. 42 $\textit{а}$), и устойчивым, но содержащим в себе мало информации ${\mu}^0(F)$ (рис. 42 $\textit{в}$). Для этого используется регуляризация по Тихонову.

Гранично-скелетное представление фигуры

Как известно, с каждой точкой скелета можно связать радиус максимального пустого круга, центром которого данная точка является, то есть задать $\textit{гранично-скелетное представление фигуры}$. По такому представлению можно однозначно восстанавливать исходную фигуру. Это дает возможность определить обратный оператор скелетизации ${\mu}^{-1}(\textrm{Sk})=F$.

Функционал Тихонова

Функционал $$ \Omega (\textrm{Sk},\alpha )=\rho _\Phi (F,{\mu}^{-1}(\textrm{Sk}))^2+\alpha \rho _\Lambda (\textrm{Sk},\textrm{Sk}^0)^2 $$ называется $\textit{функционалом Тихонова}$ для задачи ${\mu}^{-1}(\textrm{Sk})=F$, где $\textrm{Sk}\in \Lambda $ - планарный скелетный граф, $\textrm{Sk}^0={\mu}^0(F)$ - результат действия устойчивого однореберного скелетного оператора, $\rho _\Lambda $ - топологическая мера сходства скелетов, $\rho _\Phi $ - расстояние Хаусдорфа.

Таким образом, задача регуляризации скелета может быть математически строго описана как задача минимизации указанного тихоновского функционала $$ \Omega (\textrm{Sk},\alpha )\to \mathop {\min }\limits_{\textrm{Sk}\in \Lambda } . $$ При малых значениях параметра $\alpha $ решение этой задачи близко к исходной некорректной задаче. При больших $\alpha $ решение устойчивое, но находится дальше от исходной задачи. Приближенный скелет $\textrm{Sk}^\alpha $, найденный как минимум функции $\Omega (\textrm{Sk},\alpha )$, будет зависеть от параметра $\alpha $.

Общее решение этой задачи до сих пор неизвестно. Однако была предложена (но не доказана) достаточно правдоподобная гипотеза о полноте системы функций $\Psi _1 (F,\alpha )$, $\Psi _2 (F,\alpha )$, $\Psi _3 (F,\alpha )$, устраняющих нерегулярности описанных выше трех типов. Она заключается в том, что для любой фигуры $F$ и заданного $\alpha $ найдутся такие параметры $\alpha _1 $, $\alpha _2 $, что решение $\textrm{Sk}^\alpha $ задачи минимизации тихоновского функционала может быть найдено как комбинация функций, устраняющих нерегулярности трех типов с точностями $\alpha _1 $, $\alpha _2 $, $\alpha _3 $ соответственно: $$ \textrm{Sk}^\alpha =\Psi _1 (F,\alpha _1 )\circ \Psi _2 (F,\alpha _2 )\circ \Psi _3 (F,\alpha _3 ). $$ Для фиксированной пары фигур можно упростить фундаментальную постановку регуляризации скелета в терминах "подгонки скелетов".

Для заданных двух фигур $F_1 $ и $F_2 $ найти в некотором смысле наилучшие скелеты фигур $F_1 $ и $F_2 $, близкие в некоторой метрике к непрерывным скелетам фигур $F_1 $ и $F_2 $. То есть построить $\textit{регуляризирущий оператор}$ на основе двух фиксированных фигур ${R} (F_1 ,F_2 )\to (\mbox{Sk}_1 ,\mbox{Sk}_2 )$. Решение похожей задачи без учета нерегулярности с циклами $\Psi _3 $ приведено в работе, где поставлена и решена задача поиска аппроксимирующих фигур с изоморфными скелетами. Например, наилучшими скелетами можно считать изоморфные скелеты некоторых двух фигур, близких по расстоянию Хаусдорфа к исходным $F_1 $ и $F_2 $: $\mbox{Sk}_1 \cong \mbox{Sk}_2 $.


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

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

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