Лекция 4 Синтаксический подход к распознаванию образов

 

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

Пример. Изображение на рисунке можно описать иерархическими структурами.

 

 

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

Различные отношения, определенные между подобразами, или операции композиции, обычно могут быть выражены логическими и (или) математическими операциями. Если, например, в качестве единственного отношения (операции композиции) для описания образов выбрать “конкатенацию” (конкатенацией элементов a и и называется составленная цепочка ab), то при непроизводных элементах

 

прямоугольник будет представлен цепочкой aaabbсcсdd. Точнее, если использовать знак плюс для обозначения операции «конкатенация начала одного элемента к концу другого», то прямоугольник будет представлен предложением а + а + а + b + b + c + с + с + d

Древовидная структура этого предложения

Пример структурного описания цифры 9

 

 

Систему синтаксического распознавания образов можно считать состоящей из трех основных частей, а именно: из блока предобработки, блока описания или представления объекта и блока синтаксического анализа. Блок предобработки осуществляет, во-первых, функции кодирования и аппроксимации и, во-вторых, функции фильтрации, восстановления и улучшения объекта.

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

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

В качестве примера приведём фрагменты языка описания изображений PDL (Picture Description Language). Определены непроизводные элементы

 

 

, имеющие различающиеся головную и хвостовую точки, а также четыре бинарных оператора соединения элементов в цепочки:

 

 

головная точка примыкает к хвостовой точке ;

 

хвостовая точка примыкает к хвостовой точке ;

 

головная точка примыкает к головной точке ;

 

 

головная точка примыкает к головной точке и хвостовая точка примыкает к хвостовой точке .

 

Простейшей формой распознавания является, по-видимому, «сравнение с эталоном». Цепочка непроизводных элементов, представляющая исходный объект, сравнивается с цепочками непроизводных элементов, представляющих каждый эталонный образ. Из этих образов выбирается тот, который наиболее «согласован» или «близок» к исходному объекту в соответствии с некоторым заданным критерием.

Языки описания образов