Проективные морфологии на базе динамического программирования

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

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

Рассмотрим известное решение задачи фильтрации/сегментации зашумленной одномерной функции методом динамического программирования. Пусть наблюдаемая дискретная функция $f(x)$ определена на отрезке $x\in [0,{\ldots},x_{\max}]$, принимает значения на множестве $l=0,{\ldots},N-1$ и представляет собой комбинацию неизвестной исходной функции $v(x)$, принадлежащей некоторому классу функций $V$, и случайного шума $\xi $:

$$ \begin{gather}\tag{1} f(x) = v(x) + \xi \end{gather} $$

Требуется найти такую $\textit{функцию-решение}$ $L(x)\in V$, которая наилучшим образом описывает наблюдения в смысле некоторого $\textit{критерия соответствия}$ $J$:

$$ \begin{gather}\tag{2} L(x): J(f(x),L(x))\to \min(L). \end{gather} $$

Часто используется, например, критерий (3), оптимальный в случае, когда $\xi $ представляет собой гауссов белый шум:

$$ \begin{gather}\tag{3} J(f(x),L(x))= \sum _{x}(f(x)-L(x))^{2}. \end{gather} $$

При этом класс $V$ также может быть задан косвенно - некоторым $\textit{функционалом качества решения}$:

$$ \begin{gather}\tag{4} Q(L(x))\to \min(L). \end{gather} $$

Например, функционалом качества, штрафующим негладкость решения:

$$ \begin{gather}\tag{5} Q(L(x))=\sum _{x}(L'(x))^{2}. \end{gather} $$

Таким образом, в простейшем случае задача фильтрации/сегментации зашумленной функции (1) представляет собой задачу поиска экстремума комбинированного функционала

$$ \begin{gather}\tag{6} \textrm{Ф}(f(x),L(x))= J(f(x),L(x)) + \alpha Q(L(x)) \to \min(L), \end{gather} $$

где $\alpha $ - весовой коэффициент, определяющий целевую значимость качества решения по отношению к степени соответствия получаемого решения наблюдаемым данным.

Для того чтобы задача (6) могла быть решена методом динамического программирования, как функционал соответствия, так и функционал качества решения должны быть представимы в следующей $\textit{рекурсивно-кумулятивной}$ форме:

$$ \begin{gather}\tag{7} J(f(x), L(x))=J(x_{\max}): J(x_{i}) = J(x_{i-1})+\Delta J(x_{i}, L(x_{i}));\: J(0)=\Delta J(0,L(0)). \end{gather} $$

$$ \begin{gather}\tag{8} Q(L(x))=Q(x_{\max}): Q(x_{i}) = Q(x_{i-1})+\Delta Q(L(x_{i-1}), L(x_{i})); \: Q(0)=0, \end{gather} $$ где $\{x_{i}\}$, $i=0,{\ldots},i_{\max}$ - множество дискретных значений аргумента рассматриваемой функции в ее области определения.

Для приведенных выше примеров это будет, соответственно,

$$ \begin{gather}\tag{9} \Delta J(x_{i},L(x_{i}))=(f(x_{i})-L(x_{i}))^{2}; \end{gather} $$

$$ \begin{gather}\tag{10} \Delta Q(L(x_{i-1}),L(x_{i}))=(L(x_{i-1})-L(x_{i}))^{2}. \end{gather} $$

Простейшая реализация решения данной задачи методом динамического программирования (ДП) основана на использовании двумерного$\textit{ аккумулятора}$ $A(x,l)$ размера $(1+i_{\max}) N$, где $N$ - количество элементов дискретизации области значений рассматриваемой функции.

Рассмотрим в качестве примера процедуру $\textit{ДП-реконструкции}$ (фильтрации) гладкой функции следующего вида

$$ \begin{gather}\tag{11} \textrm{Ф}(f(x),L(x))= J(f(x),L(x)) + \alpha Q(L(x)) \to \min(L), \end{gather} $$

где функционалы $J$ и $Q$ описываются выражениями (7)-(11) соответственно.

$\textit{Алгоритм 1}$.

$\textit{Прямой проход динамического программирования}$.

$\textit{Шаг 0}$. Инициализировать значения крайнего левого столбца аккумулятора:

$$ \begin{gather}\tag{12} A(0,l)= \Delta J(0,l), \quad l=0,{\ldots},N-1. \end{gather} $$

$\textit{Шаги }$ $i=1,{\ldots},i_{\max}$. Определить значение каждого следующего столбца аккумулятора по формуле

$$ \begin{gather}\tag{13} A(x_{i},l)=\Delta J(x_{i},l)^{ }+ \min_{t}\{A(x_{i-1},t) + \alpha \Delta Q(t,l)\}, \;t, l=0,{\ldots},N-1. \end{gather} $$

$\textit{Обратный проход динамического программирования.}$

$\textit{Шаг 0}$. Инициализировать значение крайнего правого элемента решения:

$$ \begin{gather}\tag{14} L(x_{\max}) = \textrm{argmin}_{l}\{A(x_{\max}, l)\}, \; l=0,{\ldots},N-1. \end{gather} $$

$\textit{Шаги }$ $i=i_{\max-1},{\ldots},0$. Справа налево определить значение всех следующих элементов решения по формуле:

$$ \begin{gather}\tag{15} L(x_{i}) = \textrm{argmin}_{l}\{A(x_{i},l) + \alpha \Delta Q(l,L(x_{i+1}))\}, \;l=0,{\ldots},N-1. \end{gather} $$

$\textit{Конец алгоритма}$.$\quad\diamondsuit $

В результате описанной процедуры ДП-фильтрации (DP-LSE) будет построено оптимальное решение задачи (3), (5), (6), причем функция $L(x)$ будет "достаточно гладкой".

Пусть теперь необходимо решить задачу $\textit{сегментации}$ наблюдаемой функции $f(x)$ $\textit{на области постоянного значения}$. Это означает, что функция-решение $L(x)$ должна принадлежать классу кусочно-постоянных функций, причем количество и протяженность отрезков (областей) постоянного значения могут быть произвольными.

Описанный выше Алгоритм $1$ позволяет решить задачу $\textit{ДП-сегментации}$, если изменить критерий качества решения (11) на следующий:

$$ \begin{gather}\tag{16} \Delta Q(L(x_{i-1}),L(x_{i}))= \begin{cases} 0,& \mbox{ если } L(x_{i-1})=L(x_{i}),\cr 1,& \mbox{ если } L(x_{i-1})\ne L(x_{i}).\cr \end{cases} \end{gather} $$

Иными словами, штрафной функционал качества решения $Q(L(x))$ в этом случае будет иметь значение, равное числу переходов от одной области постоянного значения к другой. Если при этом выбрать весовой коэффициент $\alpha $ достаточно большим, то любое изменение значения $L(x)$ будет оплачиваться столь дорогим "штрафом", что оно окажется оправданным лишь при достаточном соответствующем уменьшении значения критерия $J(f(x),L(x))$.

В работе [83] показано, что процедура ДП-сегментации типа (11), (16) является алгебраическим проектором. Таким образом, оказывается определена критериальная $\textit{проективная морфология на базе среднеквадратичной ДП-сегментации}$.

Аналогичным образом можно рассмотреть и возможность построения проективной морфологии на базе монотонной ДП-сегментации. Пусть функционал (7) определяется следующими выражениями:

$$ \begin{gather}\tag{17} \Delta J_{\textrm{Open}}(f(x),L(x)) = \begin{cases} +\infty , &\mbox{если }f(x)<L(x);\cr -L(x)^{2}, &\mbox{если }f(x)\ge L(x),\cr \end{cases} \end{gather} $$

$$ \begin{gather}\tag{18} \Delta J_{\textrm{Close}}(f(x),L(x)) = \begin{cases} +\infty ,& \mbox{ если } f(x)>L(x), \cr L(x)^{2},& \mbox{ если } f(x)\le L(x).\cr \end{cases} \end{gather} $$

Тогда решение методом динамического программирования также определяет алгебраические проекторы соответственно DP-Open (17) и DP-Close (18). Доказано что монотонные проекторы являются проекторами вне зависимости от вида функционала качества $Q$. Это позволяет рассматривать $Q$ как аналог структурирующего элемента морфологии Серра и говорить об $\alpha Q$-$\textit{открытии }$и $\alpha Q$-$\textit{закрытии.}$ Действительно, в случае, когда $Q$ определяется выражением 16, решается задача $\textit{морфологической сегментации}$, и результатом является кусочно-постоянная функция, монотонная ДП-морфология дает результат качественно аналогичный морфологии Серра с плоскими структурирующими элементами. В то же время, когда Q определяется выражением 8, решается задача $\textit{морфологической фильтрации}$, и результатом является $\alpha $-гладкая функция, то есть монотонная ДП-морфология дает результат качественно аналогичный морфологии Серра с гладкими (сферическими) структурирующими элементами.

На рис. 12 - 13 представлены примеры одномерной проективной монотонной морфологической фильтрации. На рис. 14 - 15 - примеры среднеквадратичной и монотонной проективной морфологической сегментации. На всех рисунках хорошо видна зависимость сложности морфологического описания данных от значений параметра $\alpha $.

Эксперименты, в частности, показали, что если для любой одномерной функции $f(x)$ применить среднеквадратичную ДП-фильтрацию с некоторым $\alpha $, то любая дальнейшая фильтрация с тем же $\alpha $ более не изменяет полученное решение. %То есть существует такое множество "$\alpha $-стабильных" %функций, для которых обе монотонные $\alpha $-проекции равны %среднеквадратичной $\alpha $-проекции и равны самой исходной функции: %$$ %f(x) = \textrm{Pr}(f(x),J_{\textrm{LSE}},Q,\alpha ) = %\textrm{Pr}_{\textrm{о}}(f(x),J_{\textrm{Open}},Q,\alpha ) = %\textrm{Pr}_{\textrm{с}}(f(x),J_{\textrm{Close}},Q,\alpha ). %$$

6-3-12.jpg

Слева - исходная функция, далее результаты применения операторов ДП-фильтрации: DP-Open ($\alpha =200$) и DP-Close($\alpha =200$)

6-3-13.jpg

Слева - исходная функция, далее результаты применения операторов ДП-фильтрации: DP-Open ($\alpha =1000$) и DP-Close($\alpha =1000$)

$\textit{Критериальная сегментация двумерных кривых методом динамического программирования}$. Алгоритмы того же типа позволяют реализовать критериальную фильтрацию и сегментацию двумерных кривых (контуров бинарных изображений) методом динамического программирования. На рис. 16 и рис. 17 показаны примеры применения операторов монотонной кусочно-линейной сегментации контуров бинарных изображений, реализованных методом динамического программирования, на рис. 18 - пример проективной морфологической сегментации двумерной кривой (контура двумерного бинарного образа) на базе кусочно-линейной интерполяции.

6-3-14.jpg

Слева - исходная функция, далее результаты применения операторов ДП-сегментации: DP-LSE ($\alpha =500$), DP-Open ($\alpha =10000$), DP-Close($\alpha =10000$)

6-3-15.jpg

Слева - исходная функция, далее результаты применения операторов ДП-сегментации: DP-LSE ($\alpha =2000$), DP-Open ($\alpha =100000$), DP-Close($\alpha =100000$)

6-3-16.jpg

Пример контурной морфологической кусочно-линейной сегментации типа "открытие". Показаны результаты применения морфологического оператора при различных значениях структурирующего параметра $\alpha $

6-3-17.jpg

Пример контурной морфологической кусочно-линейной сегментации типа "закрытие". Показаны результаты применения морфологического оператора при различных значениях структурирующего параметра $\alpha $

6-3-18.jpg

Пример критериальной проективной морфологической сегментации контура двумерного бинарного образа при различных значениях структурирующего параметра $\alpha $

Личные инструменты
Пространства имён

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