Структурное распознавание

Суть структурного распознавания можно определить следующим образом.

Признаками (в рамках этого направления) считаются подобразы – так называемые непроизводные элементы и отношения между ними. Говоря о средстве описания объектов в терминах непроизводных элементов и их отношений, употребляют понятие "язык". Правила этого языка, определяющие способы построения объекта из непроизводных элементов, называют "грамматикой". В соответствии с грамматикой такого языка объект представляется предложением в этом языке.

Распознавание, в основном состоит из следующих этапов:

1) определение непроизводных элементов и их отношений для конкретных типов объектов;

2) проведение синтаксического анализа предложения, представляющего объект, с тем, чтобы установить, может ли некоторая фиксированная грамматика породить имеющееся описание объекта (этот анализ называют грамматическим разбором).

Указанную грамматику можно определить ("вывести"), используя априорные сведения об образах либо проанализировав выборочное множество образов.

Можно считать, что система структурного распознавания состоит из трех основных частей (см. на рис. ниже):

На этапе предварительной обработки предъявленный для распознавания объект подвергается, во-первых, некоторому рациональному кодированию и аппроксимации, и, во-вторых, фильтрации, восстановлению и улучшению качества. Прежде всего входной объект кодируется или аппроксимируется таким образом, чтобы дальше с ним было удобно работать. Так, например, черно-белое изображение можно закодировать с помощью сетки (или матрицы) нулей и единиц, а сигнал можно аппроксимировать его выборочными значениями, соответствующими различным моментам времени, или разложением в ряд Фурье. Для того чтобы повысить эффективность обработки на последующих стадиях работы, на этом этапе часто также прибегают к какой-нибудь разновидности "сжатых данных". Затем при по мощи какого-либо варианта методов фильтрации, восстановления и/или улучшения качества изображения проводится устранение шума, искажений и/или повышение качества закодированного (или аппроксимированного) объекта. Предполагается, что на выходе блока предварительной обработки воспроизводятся об разы "достаточно хорошего качества".

Каждый объект, подвергнутый предварительной обработке, представляется затем некоторой структурой языкового типа (например, цепочкой или графом). Процесс получения представления объекта включает две процедуры: а) разбиение ("сегментация") объекта, б) выделение признаков -- непроизводных элементов.

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

Система должна обладать способностью обнаруживать синтаксические связи, существующие в объекте. Решение о синтаксической правильности представления объекта (т.е. о принадлежности его к определенному классу, задаваемому определенной синтаксической системой или грамматикой) вырабатывается "синтаксическим анализатором", иначе называемым "блоком грамматического разбора". При выполнении синтаксического анализа (грамматического разбора) анализатор обычно воспроизводит полное синтаксическое описание объекта в виде дерева грамматического разбора, если соответствующий объект является синтаксически правильным. В противном случае объект либо отклоняется, либо подвергается анализу с помощью других заданных грамматик, позволяющих описывать другие классы изучаемых объектов.

Одна из самых распространенных в распознавании процедур - это сопоставление с эталоном. Цепочка непроизводных элементов, представляющая поданный на вход системы объект, сопоставляется с цепочками непроизводных элементов, представляющими все эталонные объекты или объекты обучающей выборки. Распознаваемый объект с помощью выбранного критерия согласия или подо бия относится к тому классу, к которому принадлежит и эталонный объект, обнаруживший наилучшее согласие с ним. Иерархическая структурная информация при этом практически игнорируется. В то же время полный разбор цепочки, представляющей распознаваемый объект, позволяет полностью изучить его иерархическое структурное описание. Между этими двумя крайностями заключена масса промежуточных подходов. В частности, можно сформировать набор тестов для проверки наличия или отсутствия определенных подобразов или непроизводных элементов, так же как комбинации и тех, и других. Результаты такой про верки, которую можно проводить с помощью процедур просмотра таблиц, построения дерева решения или логического анализа, используются для выработки классификационного решения. Отметим, что каждый из этих тестов может являться и процедурой сопоставления с эталоном, и процедурой грамматического разбора, определенными для поддерева, представляющего подобраз. Обычно вы бор конкретной процедуры распознавания зависит от специфических особенностей задачи (на него, естественно, влияют и опыт пользователя, и наличие соответствующих прикладных программ). Если распознавание требует работы с полным описанием объекта, то необходим грамматический разбор. В других случаях полного разбора можно избежать, ограничившись более простыми методами.

Для того чтобы получить грамматику, характеризующую структурную информацию об изучаемом классе объектов, требуется блок вывода грамматики обеспечивающий вывод соответствующей грамматики по заданному набору обучающих объектов, представленных описаниями структурного типа. (В настоящее время этот этап, как правило, выполняется разработчиком системы "вручную".) Эта процедура аналогична обучению в других методах распознавания. Структурное описание соответствующего класса формируется в процессе обучения на примерах реальных выборочных объектов этого класса. Такое описание в форме грамматики используется затем для представления объектов и синтаксического анализа. В более общем случае обучение может предусматривать определение наилучшего набора непроизводных элементов и получение соответствующего структурного описания классов объектов или явлений.