Порождающие грамматики. Структурно-лингвистический подход

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

Назовем $\textit{алфавитом}$ множество образующих

$$ \textbf{X}=\{X_{1},{\ldots},X_{n}\}\subseteq \Omega . $$

$\textit{Грамматическим высказыванием}$ ($\textit{предложением}$) назовем любую упорядоченную последовательность элементов алфавита произвольной конечной длины $k$:

$$ \textbf{Y}=\langle Y_{1},{\ldots},Y_{k}\rangle : Y_{1}\in \textbf{X}, {\ldots}, {Y}_{k} \in \textbf{X}. $$

Множество всех возможных высказываний в алфавите \textbf{X} обозначим через $\textbf{M}(\textbf{X})$. Введем операцию $\textit{подстановки}$ "$\to$", замещающую одну заданную последовательность символов на другую:

$$ \textbf{A}\to \textbf{B}: \textbf{A},\textbf{B}\in \textbf{M}(\textbf{X}). $$

При помощи этой операции можно записать $\textit{правило вывода}$ $R$, замещающее некоторую последовательность символов на некоторую другую последовательность в любом высказывании, в котором она встретилась:

$$ R(\textbf{A}\to \textbf{B}), \textbf{A},\textbf{B}\in \textbf{M}(\textbf{X}) \Rightarrow \forall \textbf{Y}_{1},\textbf{Y}_{2}\in \textbf{M}(\textbf{X}): R(\langle \textbf{Y}_{1},\textbf{A},\textbf{Y}_{2}\rangle {\to }\langle \textbf{Y}_{1},\textbf{B},\textbf{Y}_{2}\rangle ). $$

Алфавит $\textbf{X}$, набор правил вывода $\textbf{R}$ и множество исходных высказываний (постулатов) $\Theta \in \textbf{M}$($\textbf{X}$) вместе определяют $\textit{грамматику} \textrm{Г}=\{\textbf{X},\textbf{R},\Theta \}$. Высказывание $\textit{Y}$ называется $\textit{правильным высказыванием}$ в рамках грамматики Г, если в $\Theta $ существует такой постулат, последовательно применяя к которому правила из $\textbf{R}$, можно на некотором шаге вывода получить (вывести) высказывание $\textbf{Y}$. $\textit{Выводимость} \textbf{Y}$ в Г обозначается

$$ \textbf{Y}\leftarrow \textrm{Г}. $$

Множество всех утверждений, выводимых в Г (множество всех правильных высказываний данной грамматики), обозначим как $\textbf{M}(\Gamma)=\{ \textbf{Y}: \textbf{Y} \leftarrow \Gamma\}$. Его также можно описать предикатом $M(\textbf{Y},\Gamma )=\{\textbf{Y}\leftarrow \Gamma \}$.

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

Пусть теперь $\textbf{L}$ является $\textit{структурным описанием}$ прообраза $L=\delta (\textbf{L})$. Тогда задачу структурного морфологического анализа изображения можно вновь описать как задачу $\textit{структурно-лингвистического анализа}$

$$ \phi _{\textrm{Ф}}(A)=\delta (\textbf{L}), \epsilon _{\textrm{Ф}}(A)=\textbf{L}: \textrm{Ф}(A,\textbf{L})=K(A,\delta (\textbf{L}))\cdot M(\textbf{L},\Gamma )\to \max (\textbf{L}), $$

то есть требуется найти наилучшие в смысле критерия $K(A,\delta (\textbf{L}))$ $\textit{описание}$ $\textbf{L}$ $\textit{и прообраз}$ $\delta L$ $\textit{образа}$ $A$ $\textit{в грамматике}$ Г. Легко убедиться в том, что морфологический оператор $\phi _{\textrm{Ф}}(A)$ будет проектором на $\textbf{M}$(Г).

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


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

  1. ☝ К началу
  2. ☜ Изображение как структура
Личные инструменты
Пространства имён

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