Морфология на базе кусочно-линейной интерполяции

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

Данная морфология, сходная по духу с морфологией Пытьева, но основанная на несколько ином способе описания формы.

Содержание

Кусочно-линейная интерполяция одномерная функция

Рассмотрим задачу построения кусочно-линейной интерполяции одномерной функции Пусть на отрезке $[a,b]$ заданы $n+1$ опорных (узловых) точек: $a\le x_{0}<x_{1}<{\ldots}< x_{n}\le b$. Пусть, кроме того, известны значения некоторой функции $f(x)$ в этих точках. Как известно, значение кусочно-линейной интерполяционной функции на каждом отрезке интерполяции $[x_{i}, x_{i+1}]$ имеет вид

$$ \begin{gather}\tag{1} I(x)=f(x_{i})(x-x_{i})+f(x_{i+1})(x-x_{i+1}). \end{gather} $$

На рис. 8 показаны результаты интерполяции функции $f(x)$ на отрезке [$x_{i}, x_{i+1}$]. При этом отдельно показаны вклады значений $f(x_{i})$ и $f(x_{i+1}),$ имеющие вид соответственно линейно убывающей от $f(x_{i}) $ до нуля и линейно возрастающей от нуля до $f(x_{i+1})$ функций.


Сгруппировав вместе вклады в общую функцию значений $f(x_{i})$, это выражение можно переписать в форме, аналогичной выражению Пытьева для «формы» функции (1):

$$I(x)=\sum _{i} f(x_{i}){} L_{i}(x_{i},x),$$

$$ \begin{gather}\tag{2} L_{i}(x_{i},x) = \begin{cases} \frac{(x-x_{i-1})}{(x_{i}-x_{i-1})},& x\in [x_{i-1},x_{i}];\cr \frac{(x-x_{i+1})}{(x_{i}-x_{i+1})},& x\in [x_{i},x_{i+1}];\cr 0,& x\notin [x_{i-1},x_{i+1}].\cr \end{cases} \end{gather} $$

На рис. 9 показан вид опорных функций $L_{i}(x_{i},x)$, напоминающих шалаш или двускатную крышу.

6-2-8.jpg 6-2-9.jpg
Кусочно-линейная интерполяция функции на отрезке Опорная функция кусочно-линейной интерполяции

Легко заметить, что предложенная Ю.П. Пытьевым схема морфологического сравнения функций «по форме» на основе морфологического коэффициента корреляции в формальном отношении полностью применима и к проективной морфологии на базе кусочно-линейной интерполяции. Рассмотрим сперва одномерный случай. Пусть на отрезке $[a,b]$ определена кусочно-линейная (ломаная) функция $f(x)$. Примем множество локальных экстремумов данной функции в качестве опорного множества кусочно-линейной интерполяции и рассмотрим интерполяцию некоторой другой функции $g(x)$ по точкам из этого множества. Заметим, что построение интерполяции по фиксированному набору точек всегда может быть рассмотрено как оператор проецирования. Это позволяет определить коэффициент морфологической корреляции, подобный морфологическому коэффициенту корреляции Пытьева, следующим образом:

Коэффициент морфологической корреляции

$$ K(g,f) = \frac{\min(\vert \vert {P_f}(g)\vert \vert ,\vert \vert g\vert \vert)} {\max(\vert \vert {P_f}(g)\vert \vert ,\vert \vert g\vert \vert )}, $$

$$ \begin{gather}\tag{3} {P_f}(g)=\sum _{i} g(x_{i}){}L_{i}(x_{i},x), \end{gather} $$

$$\{x_{i}\}= \textrm{lextr}\,(f(x)),$$ где $L_{i}(x_{i},x)$ - опорные функции типа (2); lextr,($f(x))$ - множество локальных экстремумов функции $f(x)$. Далее мы можем назвать $\textit{модельное множество}$ $$\textbf{M}=\left\{\sum _{i} a_{i}{}L_{i}(x_{i},x): a_{i}\in {R} \right\}.$$

«формой» функции $f(x).$ Это позволяет осуществлять операцию «сравнения функций по форме»: чем больше значение коэффициента морфологической корреляции (3), тем больше «сходство по форме» функции $g(x)$ с $f(x)$.

6-2-10.jpg 6-2-11.jpg
Проекция функции на «форму», определяемую множеством

собственных экстремумов

Проекция функции на «форму», определяемую экстремумами

другой функции

На рис. 10 показан пример проекции гладкой одномерной функции на кусочно-линейную «форму», определяемую множеством ее собственных экстремумов. Как видно, кусочно-линейная интерполяционная функция $I(x)=I(f(x))$ не сильно отличается от исходной гладкой функции $f(x)$, следовательно, морфологический коэффициент корреляции $K(f,I(f))$ должен быть близок к максимальному значению. На рис. 11 показан пример проекции другой гладкой функции $g(x)$ на кусочно-линейную «форму», определяемую множеством локальных экстремумов отличной от нее функции $f(x)$ (рис.10). Из-за несовпадения положения локальных экстремумов проекция ${P_f}(g)$ оказывается существенно отличной от $g(x)$. «Пики» и «впадины» исходной функции оказываются в проекции в значительной степени «срезаны», это уменьшает ее размах, и как следствие коэффициент корреляции $K(g,I(f))$ должен принимать существенно меньшие значения.

Кусочно-линейная аппроксимация

Рассмотрим теперь задачу кусочно-линейной аппроксимации двумерной функции. Эта задача несколько сложнее, поскольку произвольный набор точек двумерной плоскости, в отличие от любого набора опорных точек на прямой, не является естественным образом упорядоченным, вследствие чего выбор соседних точек для формирования опорной функции вида (2) оказывается не столь тривиальным.


Часто применяется, например, решение этой задачи, основанное на построении триангуляции Делоне. Пусть на прямоугольной области двумерной числовой плоскости $[a,b]\times [c,d]$ заданы $n$ опорных (узловых) точек $\textbf{X}=\{x_{i},y_{i}\}: a\le x_{i}\le b, с\le y_{i}\le d, \,i=1,\ldots, n$. Пусть, кроме того, известны значения некоторой функции $f(x,y)$ в этих точках. Будем далее считать, что триангуляция Делоне для данного опорного множества точек \textbf{X} всегда может быть построена, и соответствующий граф триангуляции Делоне обозначается $D$(\textbf{X}). На рис. 12} показан пример такой триангуляции.


Выражение для кусочно-линейной интерполяции с использованием триангуляции имеет вид, аналогичный выражению (4):

$$ \begin{gather}\tag{4} I(x,y)=\sum _{i} f(x_{i},y_{i}){}L_{i}(x_{i},y_{i},x,y), \end{gather} $$

где $L_{i}(x_{i},y_{i},x,y)$ - двумерная опорная функция, похожая на шатер или многоскатную крышу (рис. 13).

6-2-12.jpg 6-2-13.jpg
Пример триангуляции Делоне Опорная функция двумерной кусочно-линейной интерполяции

Для двумерного случая определения морфологического коэффициента корреляции и «формы» функции могут быть даны сходным образом:


$$K(g,f) = \frac {\min(\vert \vert {P_f}(g)\vert \vert ,\vert \vert g\vert \vert )} {\max(\vert \vert {P_f}(g)\vert \vert ,\vert \vert g\vert \vert )}, $$

$${P_f}(g) = \sum _{i} g(x_{i},y_{i}){}L_{i}(x_{i},y_{i},x,y), $$

$$\{\langle x_{i},y_{i}\rangle \}= {\textrm{lextr} 2}\,(f(x,y)), $$

$$\textbf{M} = \left\{\sum _{i} a_{i}{}L_{i}(x_{i},y_{i},x,y): a_{i}\in {R}\right\}, $$


где $L(x_i , y_i , x , y)$ - опорные функции; lextr2,$(f(x,y))$ - множество локальных экстремумов кусочно-линейной функции $f(x,y)$; \textbf{M} - «форма» кусочно-линейной функции $f(x,y)$. Таким образом, мы получили некоторое альтернативное определение «формы» двумерной функции, основанное не на кусочно-постоянной аппроксимации Пытьева, а на кусочно-линейной интерполяции.

На рис. 14 - 16 представлены примеры вычисления интерполяционной проекции различных авиационных изображений зданий на кусочно-линейную форму. Как видно из представленных примеров, даже в случае использования небольшого числа опорных точек для описания формы эталона, проекции изображений, сходных по форме с эталоном, претерпевают существенно меньшие относительные изменения по сравнению с проекциями изображений, имеющих значительные отличия по форме от эталона.

6-2-14.jpg

Вычисление интерполяционной проекции изображения на собственную кусочно-линейную форму: $\textit{а}$ - расположение значимых экстремумов; $\textit{б}$ - соответствующая триангуляция; $\textit{в}$ - кусочно-линейная интерполяционная проекция

6-1-15.jpg

Примеры вычисления интерполяционной проекции на кусочно-линейную форму: $\textit{а}$ - форма, определяемая триангуляцией по значимым экстремумам эталона; $\textit{б}$ - эталонное изображение объекта; $\textit{в}$ - проекция эталона на форму; $\textit{г}$ - тестовое изображение объекта; $\textit{д}$ - проекция тестового изображения на форму; $\textit{е}$ - изображение другого объекта; $\textit{ж}$ - проекция другого объекта на форму эталона

6-2-16.jpg

Примеры вычисления интерполяционной проекции на кусочно-линейную форму: $\textit{а}$ - форма, определяемая триангуляцией по значимым экстремумам эталона; $\textit{б}$ - эталонное изображение объекта; $\textit{в}$ - проекция эталона на форму; $\textit{г}$ - тестовое изображение объекта; $\textit{д}$ - проекция тестового изображения на форму; $\textit{е}$ - изображение другого объекта; $\textit{ж}$ - проекция другого объекта на форму эталона

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

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

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