Структурные методы в распознавании образов

Введение

Структурный (синтаксический) подход был предложен для того, чтобы представлять иерархическую информацию, содержащуюся в каждом образе, т.е. описывать образ при помощи более простых подобразов, а каждый подобраз снова описывать ещё более простыми подобразами и т.д. [4]. Разумеется, применение этого подхода оправдано только в том случае, когда распознавать выбранные простейшие подобразы, называемые непроизводными элементами, легче, чем сами образы. Язык, обеспечивающий структурное описание образов в терминах непроизводных элементов, иногда называют языком описания образов. Правила композиции непроизводных элементов обычно задают при помощи так называемой грамматики языка описания образов. Процесс распознавания осуществляется после идентификации непроизводных элементов и составления описания объекта и состоит в грамматическом разборе (синтаксическом анализе) предложения, описывающего объект.

Структурный подход к распознаванию образов даёт возможность описывать большое число сложных объектов путём использования небольшого множества непроизводных элементов и грамматических правил (правил подстановки). Грамматическое правило может быть применено любое число раз, так что оказывается возможным очень компактно выразить основные структурные характеристики бесконечного множества предложений. Различные отношения, определённые между подобразами, обычно могут быть выражены логическими и (или) математическими операциями [4].

Система синтаксического распознавания образов.

Систему синтаксического распознавания образов можно считать состоящей из трёх основных частей: блока предварительной обработки, блока описания (представления) объекта и блока синтаксического анализа. Обычно предполагается, что объекты на выходе блока предобработки представлены в “достаточно хорошем” качестве. Затем каждый подвергнутый предобработке объект представляют в виде структуры языкового типа. Этот процесс представления объекта состоит, во-первых, из сегментации, и, во-вторых, из выделения непроизводных элементов (признаков). Иными словами, каждый объект после предобработки делится на части и непроизводные элементы на основе заранее заданных синтаксических операций (или операций композиции) и получает своё представление через множество непроизводных элементов и определённые синтаксические операции. Решение о том, является ли представление объекта синтаксически правильным (т.е. принадлежит ли он к классу объектов, описываемых данным синтаксисом или данной грамматикой), принимается блоком синтаксического анализа. По ходу синтаксического анализа этот блок может давать полное синтаксическое описание объекта в терминах грамматических единиц или дерева синтаксического анализа (если представление объекта синтаксически правильное). В противном случае объект либо исключают из рассмотрения, либо анализируют на основе других заданных грамматик, которые, может быть, описывают другие возможные классы рассматриваемых образов [4].

Для того, чтобы получить грамматику, описывающую структурную информацию класса образов, необходимо устройство вывода грамматики, позволяющее восстановить её по заданному множеству объектов в виде, подобном языковому. Функции этого устройства аналогичны процессу обучения в дискриминационных системах распознавания образов. В результате обучения на рассматриваемых объектах формируется структурное описание этого класса. Затем полученное в виде грамматики описание используется для описания образов и синтаксического анализа.

Блок-схема системы синтаксического распознавания образов изображена на рис.8.

Введение в формальные языки

Языки и порождающие грамматики.

Порождающая грамматика есть четвёрка G =( V_N, V_T, P, S ), где V_N и V_T - основной и вспомогательный словари (или множества переменных) соответственно, P - конечное множество правил вывода или правил подстановки, символ  - начальный символ. Объединение V_T и V_N составляет полный словарь V грамматики G, V_T ∩ V_N =Ø . Правила подстановки из P обозначаются как α → β , где α и β - цепочки символов из V, причём α содержит хотя бы один символ из V_N.

Часто используются следующие обозначения [4]:

1. Σ ^* - множество всех конечных цепочек символов из конечного множества Σ , включая λ - цепочку нулевой длины, Σ ⁺ = Σ ^* -λ .

2. xⁿ - цепочка, состоящая из n раз написанной цепочки x.

3. |x| - длина цепочки, т.е. число символов в цепочке.

4. - цепочка η непосредственно порождает цепочку γ, если η =ω ₁ α ω ₂, γ =ω ₁ β ω ₂ и α → β - элемент P.

.   - цепочка η порождает цепочку γ , если существует такая последовательность цепочек ζ ₁, ζ ₂, …, ζ _N, что η = ζ ₁, γ = ζ _N и ζ _i ζ _{i +1}.

Язык, порождаемый грамматикой G, есть

L ( G ) = { x / x V ^* _T, x - такая цепочка, что }.        (2.1)

Если G - порождающая грамматика, то L ( G ) называется формальным языком.

Типы порождающих грамматик (по Хомскому).

) Грамматики типа 1 (грамматики непосредственно составляющих).

Правила подстановки грамматик типа 1 имеют следующий вид:

ζ ₁ A ζ ₂ → ζ ₁ β ζ ₂,                                         (2.2)

 

где A V_N, ζ ₁, ζ ₂, β V ^* и β ≠ λ .

Это означает, что цепочку A можно заменить на β в контексте ζ ₁, ζ ₂.

Языки, порождаемые грамматиками типа 1, называются языками типа 1 или языками непосредственно составляющих.

) Грамматики типа 2(бесконтекстные грамматики).

Правила подстановки таких грамматик имеют вид:

A → β ,                                               (2.3)

 

где A V_N и β V ⁺. Следует заметить, что такие правила подстановки позволяют заменять вспомогательный символ A на цепочку β независимо от контекста, в котором встречается A.

Языки, порождаемые грамматиками типа 2, называются языками типа 2 или бесконтекстными языками.

) Грамматики типа 3 (автоматные или регулярные).

Правила подстановки грамматик типа 3 имеют вид

A→ aB или A→ b,                                           (2.4)

 

где A, B V_N и a, b V_T. Заметим, что A, B, a, b - одиночные символы V.

Языки, порождаемые грамматиками типа 3, называются языками типа 3 или автоматными (регулярными).

Кроме этих трёх типов грамматик, существует ещё один тип грамматик - грамматики типа 0 (неограниченные). Этот тип характеризуется отсутствием каких-либо ограничений на вид правил подстановки: любые цепочки могут стоять как слева, так и справа от стрелки. Однако для использования этот класс слишком широк, так как даже вопрос о том, порождается ли некоторая цепочка данной грамматикой типа 0, вообще говоря, неразрешим.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: