Общая характеристика структурных методов распознавания

Во многих случаях апостериорная информация о распознаваемых объектах или явлениях содержится в записях соответствующих сигналов (электрокардиограмм, энцефалограмм, отраженных от целей радиолокационных сигналов, инфракрасных сигналов, порождаемых функционирующими объектами, акустических сигналов работающих машин и механизмов и т. д.). Традиционно для определения признаков (например, диагностических в задачах медицинской и технической диагностики) используется разложение в ряды по ортогональным функциям. При этом в качестве признаков берутся коэффициенты разложения (в частности, ряда Фурье, полиномов Эрмита, Лежандра, Чебышева, разложения Карунена — Лоэва и т. д.). Возможно использование в качестве признаков и некоторых характерных элементов экспериментальных кривых (точки минимума, максимума и др.), например электрокардиограммы (рис. 8.1), содержащей типичные структурные элементы — зубцы (экстремальные точки) Р, Q, R, S, связанные со стадиями сердечной деятельности, или отраженные от движущегося объекта радиолокационные сигналы, структура которых однозначно определяется конструкцией объекта и динамикой его движения (центра масс и относительно центра масс).

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

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

В то же время структурные методы распознавания не только не препятствуют использованию ЭВМ в системах распознавания, но, наоборот, создают для этого благоприятные возможности, связанные с тем, что они базируются на теории формальных языков*. Одной из первоначальных задач лингвистов, работающих в данной области, было создание «вычислительных» грамматик, способных описывать естественные языки для того, чтобы научить машину «понимать» естественные языки в целях машинного перевода и существенного усовершенствования процесса общения человека и машины. Данная задача пока не решена, однако некоторые результаты исследований привели к разработке компиляторов в языках программирования, теории абстрактных автоматов и структурных методов распознавания. Поскольку последние представляют собой побочный продукт исследований, цель которых — обучить машины «понимать» естественные языки, они весьма экономно, эффективно (с точки зрения затрат машинного времени) реализуются на ЭВМ.

*Формальные языки базируются на математических моделях грамматик, разработанных американским лингвистом Н. Хомским и при исследовании естественных языков (английского, французского и др.).

Рис. 8.1

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

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

В процессе распознавания информацию о структуре объекта можно использовать следующим образом.

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

*Этот подход реализован в классе алгоритмов, основанных на вычислении оценок (АВО) (см. § 7.6).

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

Подобное задание (индуктивного порождения) некоторого класса объектов называют обобщенным индуктивным определением. Оно осуществляется по следующей схеме: 1) задаются некоторые (исходные) объекты описываемого класса; 2) задаются некоторые правила, позволяющие из уже определенных объектов получать другие объекты этого класса; 3) к объектам данного класса относят только те объекты, которые получены согласно п. 1 и 2 этой схемы. Формализацией интуитивного представления об индуктивно порождаемом множестве является понятие исчисления, т. е. дедуктивной системы способа задания множества путем указания исходных элементов и правил вывода, каждое из которых описывает, как строить новые элементы из исходных и уже построенных. Поскольку речь идет о построении некоторого описания, предполагается использование для этого языка. Поэтому об исчислении можно говорить как о некоторой знаковой системе, создаваемой с помощью образования всех синтаксически правильных символических выражений из букв алфавита системы — языка исчисления, т. е. его термов (слов) и формул (предложений), — и процесса вывода потенциально значимых (истинных) формул исчисления из некоторого фиксируемого в том же языке набора формул-аксиом. Под синтаксисом понимают совокупность типов сочетания слов и моделей построения словосочетаний и предложений*.

*Для проблем, связанных с процессами индуктивного порождения множеств, решающее значение имела работа американского математика Э. Поста (1897 — 1954) [27], в которой было предложено понятие дедуктивной системы, пригодной для порождения произвольных перечислимых множеств слов. Главная идея его работы состоит в том, что выражения или высказывания логической системы или языка, в каком бы виде они не представлялись, в конечном счете есть не что иное, как цепочки символов из некоторого конечного алфавита. Таким образом, любая математическая система, по существу, является набором правил, устанавливающих, каким образом некоторые последовательности символов могут быть преобразованы в другие последовательности символов. Э. Пост показал, что система преобразований последовательностей сводится к семейству очень конкретных и простых операций над символами.

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