Содержание к диссертации
Введение
ГЛАВА I Современное состояние и перспективы развития метода структурного распознавания образов .
1.1 Основные понятия и определения метода структурного распознавания образов 13
1.2 Задачи и методы структурного распознавания образов 18
1.3 Сегментация - начальный этап структурного представления образов 22
1.4 Формальные языки и грамматики как средство анализа структуры образов 26
I.4.I Цепочные грамматики 26
1.4.2 Графовые грамматики 31
ГЛАВА II Структурное представление экспшмшталъных кривых .
2.1 Классификация методов сегментации экспериментальных кривых 35
2.2 Формализация метода формирования примитивов экспериментальных кривых 41
2.2.1 Способ реализации оператора выделения и дискретизации примитивов 45
2.2.2 Способ реализации оператора структурного представления экспериментальных кривых 48
2.3 Оценка объема информации при структурном представлении экспериментальных кривых 51
ГЛАВА III Система автоматизированного распознавания структуры эюзпериментальных кривых (САРСЭК).
3.1 Функциональное назначение и принцип построения САРСЭК. 58
3.2 Критерии выбора параметров аппаратного комплекса САРСЭК 66
3.3 Синтез оптимальной структуры аппаратного комплекса САРСЭК . 70
3.4 Описание функционирования блока сегментации экспериментальных кривых и оценка его точности . 81
3.5 Вычислительное устройство определения составных параметров кривых 93
3.6 Язык структурного описания экспериментальных кривых (ЯСОЭК) 95
3.6.1 Грамматика ЯСОЭК и ее структура 99
3.6.2 Элементы атрибутной грамматики и их семантика . 101
3.6.3 Основные свойства и особенности ЯСОЭК . 107
3.7 Модель синтеза грамматики ЯСОЭК 109
3.7.1 Начальное структурное представление примитивов . 110
3.7.2 Структурное описание подобразов кривых 112
3.7.3 Алгоритм автоматического синтеза атрибутной грамматики. 115
3.8 Оценка сложности дерева структуры кривой 119
3.9 Алгоритм структурного распознавания экспериментальных кривых 125
ГЛАВА ІV Экспгошентальные результаты применения САРСЭК .
4.1 Описание функционирования САРСЭК 133
4.2 Анализ и сравнительная оценка вычислительной сложности метода структурного распознавания кривых с другими методами теории распознавания 139
4.3 Экспериментальное применение САРСЭК для задач виброакустической диагностики двигателей внутреннего сгорания.146 4.4 Экспериментальное применение САРСЭК для автоматизащш
обработки реоэнцефалографической информации 156
Заключение .172
Литература 178
Приложения 188
- Основные понятия и определения метода структурного распознавания образов
- Классификация методов сегментации экспериментальных кривых
- Функциональное назначение и принцип построения САРСЭК.
- Анализ и сравнительная оценка вычислительной сложности метода структурного распознавания кривых с другими методами теории распознавания
Основные понятия и определения метода структурного распознавания образов
В настоящее время в теории распознавания образов созданы различные методы распознавания: статистические [II, 20, 21, 52, 64], логические [36, 37], алгебраические [47, 48, 59, 60]- позволяющие решать различные задачи распознавания образов.
В последние десятилетия в арсенал методов теории распознавания прибавился структурный метод распознавания [ill] , который позволяет производить детальный анализ структур и определить законы строения их. Появление нового метода в теории распознавания, безусловно, расширяет и дополняет смысл ее основных терминов и понятий. В связи с этим , целесообразно проанализировать их смысл и определений, которые могут быть использованы как в структурных, так и в неструктурных методах распознавания. Заметим, что к последним мы отнесем все те методы распознавания, которые прямым или косвенным образом не исследуют структуру самих распознаваемых образов.
Известно, что любая теория оперирует своими определениями, понятиями, терминами, от широты охвата которых зависит гибкость, -подвижность самой теории и ее взаимосвязность с другими. Эти определения и понятия являются элементами данной теории. Подобными основными элементами языка теории распознавания являются понятия "образ", "признак", "примитив", "подобраз", "структура" и т. д. Понятие "образ" широко используется как в повседневной речи, так и в теории распознавания, но только в последнем этому понятию придается более точный смысл.
Исходя из анализа различных литератур по теории распознавания образов [3, II, 14, 20, 21, 106, 117] можно сказать, что существуют эквивалентные определения понятия "образ". Так, согласно Г52, 91, 117] под образом понимается отображение совокупности общих признаков, присущих всем объектам данного множества или класса. Например, автор работы 117 говорит: "То общее, что объединяет объекты в класс и называют образом". В других источниках [II, 21] образ определяется как множество класс любых объектов, объединяемых общими свойствами. Например, в [її] отмечается, что "классом будем называть множество предметов и явлений, объединяемых некоторыми общими свойствами". Авторы [її] оговариваются, что понятие "класс" тождественно понятию "образ". В [107] приведено более уточненное определение понятия "образ": "Образ, применительно к теории опознания, есть отображение общих и относительно устойчивых признаков, определенный набор значений которых характеризует данный класс объектов". Здесь уточнение заключается в том, что в понятие "общие свойства" входят не только те свойства, признаки, которые тождественны для всех представителей классов, но и те свойства, признаки, роль и функций которых одинаковы для всех объектов - "общие и относительно устойчивые признаки".
Все вышеприведенные определения понятия "образ" по своей су -ти, с точки зрения методов распознавания, являются эквивалентными. Эквивалентность заключается в единстве понятий "класс", "признак", и метрическом характере процедуры распознавания.
К понятию "признак" обычно относят те величины, которые являются наиболее существенными для определения простых или сложных свойств объектов. Признаки исследуемых объектов обычно допускают измерению и численному выражению их значений. На основе этих значений и их диапазона изменений, производят распознавание объектов.
Дальнейшее развитие теории распознавания связано с решением более сложных задач, таких, как распознавание человеческой речи, определение различных изображений реальных объектов, распознавание шумов электродвигателей и различных акустических сигналов. Решение этих задач способствовали появлению различны алгоритмов и методов распознавания. Одним из таких методов распознавания является структурный метод [35, 38, IIIJ .
Б структурном методе распознавания начальный этап процедуры распознавания начинается с выделения отдельных непроизводных элементов или примитивов образа.
Примитивами называют исходный элемент образа, из совокупности которых можно строить определенные его части или фрагменты. Отдельные примитивы обозначим через z , а их множество через Z--\zi0 z ...,?.....г] Примитивы zL представляют собой элементарные объекты или простейшие строительные блоки, определяемые следующими типами характеристик: первый тип - это структурный признак примитива, которому ставится в соответствие признак $ = А {г) ; Второй тип - это связь примитива с другими примитивами. Множество связей различных примитивов образуют структуру связей примитивов.
Классификация методов сегментации экспериментальных кривых
Экспериментальные кривые (ЭК) являются одной из форм представления результатов эксперимента над исследуемыми объектами и подавляющее их большинство обладают внутренней структурой, отдельные фрагменты которых связаны с процессами, происходящимися в объектах. Для того, чтобы описать и анализировать формы таких кривых с помощью структурных методов распознавания, требуется предвори-тельно выделить отдельные участки кривых, несущие информацию о событиях имеющие место в исследуемых объектах. Такая процедура называется сегментацией кривых и представляет начальный этап формирования словаря языка структурного описания ЭК. В результате сегментации кривых формируются объектные примитивы. Они соответствуют элементарным частям исследуемых ЭК и образуют терминальные символы грамматики языка описания структуры кривых.
В силу последовательного характера развития процессов, про-исходящиеся в исследуемых объектах, фрагменты ЭК являются носителями упорядоченных последовательностей событий и находятся в отношение сцпления (ос ) друг с другом.
При сегментации ЭК обычно стремятся к тому, чтобы объектные примитивы характеризовали этапы смены состояния процессов, происходящие в исследуемых объектах или указывали моменты появления некоторых "особых" событии. При этом, необходимо наилучшим образом удовлетворить требования к формированию объектных примитивов (см. 1,3), Однако, ЭК как правило не имеют четкие границы между отдельными своими фрагментами и в целом изменчивость их форм, даже одного и того же класса, могут быть веема широкими. Поэтому выполнение этапа сегментации с соблюдением вышеприведенных требований и выбора вида или формы объектных примитивов являются сложной задачей. Эта задача зачастую решается исходя из анализа особенностей форм исследуемых кривых, опыта и интуиции самих исследователей [I, III]. Анализ литератур [I, 43, 80, 121] показал, что имеются различные методы сегментации ЭК. Они могут быть разделены на три группы [22]. Рассмотрим эти методы (см,рис. 2.1).
Контурные методы сегментации. К данной группе можно отнести методы сегментации, основанные на учет различных особенностей геометрических форм и топологических признаков кривых [43, 96, 129]. Если кривая многоэкстремальная, то сегментацию можно осуществить по экстремальным точкам. Такой способ сегментации ЭК имеет простую аппаратную реализацию и примитивы могут быть легко интерпретированы в содержательных терминах предметной области. Однако, ЭК имеющая на своих растущих участках точек перегиба, излома или изменчивую форму вершины, ее сегментация по экстремальным точкам затруднена, т.к. здесь требуется знать не только значения кривой в ее экстремальных точках, но и значения ряда, возможно и всех, точек лежащих на межэкстремальных участках. В таких случаях для сегментации ЭК более подходящими являются методы слежения контура кривой. К ним относятся методы проведения касательных к точкам ле жащих на контуре ЭК (градиентный метод) и метод учета изменения кривизны кривой [43, 96, 128, 129]. Однако, эти методы сегментации имеют малую помехоусточивость и если кривая высокочастотная (более десятки кГц) , то объем исходных данных резко увеличивается. Кроме того, аппаратная реализация метода учета изменения кривизны ЭК относительно сложная. Поэтому на практике для сегментации кривых обычно предпочтение дается градиентному методу при условии, что кривая представляет низкочастотный сигнал и шумы сведены к минимуму.
Процедуру сегментации также можно произвести исходя из анализа топологических признаков кривых. Под топологическими признаками кривой имеют в виду те признаки, которые инвариантны к гоммоморф-ным преобразованиям. К ним можно отнести число связных между собой отдельных фрагментов кривой, отношение площадей отдельных фрагментов к общей площади кривой за период ее повторения и т.д. Учет тополлогических свойств ЭК дают более обобщенные признаки и позволяют анализировать "глобальные" свойства структур кривых [129].
Аналитические методы сегментации. Другой подход к сегментации кривых основан на применения различных алгоритмов приближения функций к ЭК [6]. Эти алгоритмы могут быть выполнены в виде программ на ЦВМ или в виде функциональных вычислительных кодирующих преобразователей (ФВКП)[31, 103]. Сложность этих алгоритмов зависит не только от особенностей исследуемых кривых, но и от типа выбранной для аппроксимации ЭК базисной функции.
Широко применяемыми системами базисных функций \Ч\ допус кающие как ортогональные, так и неортогональные представления ЭК являются алгебраические полиномы 1, 19t it , и тригономе трические функции / , sin t , cos t , sln2t В зависимости от конкретного вида базисной функции можно строить различные ал - 39 -проксиматоры и они могут быть использованы в качестве устройства сегментации.
Так, в лолиномальных аппроксиматорах для аппроксимации ЭК используются полиномы с различными порядками такие, как полиномы Лагранжа, Ньютона, Чебышева, ортогональные полиномы Уолыпа, Хаара и реализованы в виде аналоговых, цифровых и аналого-цифровых устройств [31, 76, 102, 103], Заметим, что на практике с целью обеспечения достаточной точности аппроксимации и несложной аппаратной реализации, в основном используют полиномы нулевого и первого порядка.
К аппроксиматорам реализующим полиномы нулевого порядка относятся ступенчатые аппроксиматоры [102], аппроксимирующие кривую x(t) с помощью ступенчатой функции Ш„) =TX(tn){i[in-]-i[t„J} , (2.1) гдел( ]- значение функции в момент времени tn , і г+7 = Ji npiL І7, - единичная функция. u J lо при. t 0 Причем, X(t) - и %щ\ -const . В полиномальных аппроксиматорах, в общем случае, кривая на заданном отрезке [0,т\ заменяется некоторым обобщенным многочленом где \pLU) ( 1,2,---,/1)- независимая на интервале [0,т] система функций, cL - действительные коэффициенты.
Функциональное назначение и принцип построения САРСЭК.
В существующих системах распознавания образов [21, 36, 48, 49, 52], процедура распознавания выполняется на базе измеренных численных значений признаков образа или вычисленных значений распределения вероятностей этих признаков. Эти системы главным образом предназначены для классификации исследуемых образов и выработки решения типа "да", "нет", "не знаю" о принадлежности или непринадлежности рассматриваемых образов к определенному классу. Иначе говоря, в этих системах распознавание образов осуществляется по количественным характеристикам признаков.
Между тем, на практике зачастую возникает задача не только оценки количественных, но и качественных характеристик образов, что позволяет давать более полную оценку распознаваемым образам и тем самым, исключать отнесении одних классов образов к другим в случае значительной пересекаемости классов. Поэтому распознающая система должна быть способной анализировать количественно - качественные характеристики образов, выявлять различные связи отдельных фрагментов образов и законы их композиции.
Предлагаемая в данной работе САРСЭК является одним из примером таких систем. Основное функциональное назначение системы заключается в компактном представлении исходной информации о форме кривых с помощью объектных примитивов, в автоматическом формировании словаря языка структурного описания кривых и создание эталонных структурных описаний ЭК, решение задач структурного распознавания и классификации кривых в терминах их структурных признаков.
Исследования последних лет показывают [56], что системы, распознающие структуры образов, могут быть построены на базе языков структурно-лингвистического типа и языков формальных грамматик. Принципы построения таких систем могут быть основаны на упрощенной модели компиляторов (см.рис.3.1J [71].
Для лучшего понимания функционального назначения системы и решаемых ею задач, процесс структурного распознавания ЭК удобно рассмотреть как взаимодействие отдельных процессов согласно рис.ЗД. В нашем случае, под исходным языком подразумевается квантованные и дискретизованные значения исходной кривой, а в качестве блока лексического анализа (ША)- блок сегментации ЭК (БСЭК), который предназначен для автоматического выделения и формирования объектных примитивов (лексемов). -бифункциональным аналогом блока синтаксического анализа (ECAJ в нашей системе является блок структурного анализа (БСА). Этот блок преобразует цепочки объектных примитивов в такую их последовательность, которая адекватно отражает исходную форму исследуемой кривой. Процесс такого преобразования осуществляется упорядочиванием объектных примитивов в соответствии с заданной грамматикой. Выходной информацией для БСА является деревовидное описание структуры текущих ЭК.
Блоком генератора кодов в рассматриваемой системе блок сравнения эталонного дерева (р) структуры ЭК с деревом структуры Д) текущих кривых. Выходная информация блока сравнения деревьев является решением системы о результатах распознавания структуры ЭК. Таким образом, исходя из вышеизложенного, обобщенную логическую блок-схему САРСЭК можно представить как показана на рис. 3.2.
Одним из требований к САРСЭК является достаточное ее быстродействие с тем, чтобы выполнения процедур структурного описания и классификации кривых можно было бы сблизить к реальному маштабу времени. С этой целью алгоритмы функционирования некоторых блоков системы целесообразно реализовать аппаратно. В связи с этим, возникает проблема аппаратной реализации каких именно блоков системы. Для этого, как нам думается, необходимо исходить из следующих соображений:
во-первых, анализируя функционирования системы необходимо выделить те операции, которые занимают много машинного времени. Например, одной из таких операций является операция фильтрации, которая в среднем занимает 4-5 минут машинного времени. Далее, определить принадлежность этих операций к конкретному блоку системы согласно рис, 3.2;
Анализ и сравнительная оценка вычислительной сложности метода структурного распознавания кривых с другими методами теории распознавания
Анализ и сравнительная оценка вычислительной сложности метода структурного распознавания кривых с другими методами теории распознавания Процедура анализа структуры кривой и построение ее ДС дает -возможность выявить взаимосвязь между различными простыми и сложными элементами кривых как одного, так и разных классов. При этом на результат классификации кривых может повлиять изменение признаков хотя бы на одной из одноименных терминальных или нетерминаль-ных вершин текущего дерева $ относительно эталонного $ . В силу этого решение о принадлежности текущих кривых к какому-либо классу можно принять на основе установления к-изоморфности узлов деревьев 3 и на любом их уровне.
Методика структурного распознавания кривых, предложенная в данной работе, имеет некоторую аналогию с эталонными методами распознавания образов, согласно которых вводятся различные меры сходства между эталонными и текущими образами, подлежащие распознаванию. В связи с этим, сравнительная оценка между методом структурного распознавания кривых, предложенного в данной работе и эталонными методами распознавания образов в некоторой степени может быть оправдана.
В эталонных методах идеальным решением задачи распознавания является такое, при котором все реализации, относящиеся к одному классу, преобразовались бы в одну эталонную реализацию. При таком отображении, для обучения достаточно показать по одной эталонной реализации каждого класса. Построение такого пространства эталонов является достигаемым только в случаях очень простых задач распознавания. При этом, вычисление меры сходства осуществляется по всей заранее фиксированной совокупности признаков.
На практике большинство задач распознавания требует дифференциации классов образов, у которых пространства признаков пересекаются. В таких случаях очень часто число эталонов принимается равным числу реализации образов в обучающейся последовательности. Это обстоятельство накладывает некоторый отпечаток на эталонные методы при классификации. Б эталонных методах начальным этапом обучения распознаванию классов образов является выбор меры сходства кодовых описаний об разов между собой. При этом образы рассматриваются как У -мерные векторы в гиперпространстве и мера сходства должна обладать свой ством функции расстояния в этом гиперпространстве. Таких фукций в литературе известно множество [16, 20, 21, 35, 42] . Однако, извест но из 55 , что все меры сходства дают почти одинаковые результаты при классификации. Поэтому для оценки сложности меры сходства мож но взять широко применяемую метрическую меру близости - евклидово расстояние , где М - число признаков, %э , А с признаки сравниваемых объектов. Решающее правило при этом имеет вид: d = min{\\dje\\\ , э,С = 1,г,--,11 3 с
Для простоты предполагается, что выполнена процедура нормирования векторов признаков.
В современных ЦВМ соотношение по длительности вычисления между основными арифметическимлоперациями сложения, вычитания, умножения, деления и извлечения корня определяется как I, I, 2, 4 и 6, соответственно [61]. Используя эти данные и формулу (4.IJ определим число машинных операций, необходимых для вычисления евклидова расстояния между двумя классами. В переводе на арифметические операции (ар.оп.) при анализе jvj -признаков согласно формуле (4.1) нужно осуществить М операций вычитания, 2Щ операций умножения, М операций сложения и 6 операций вычисления корня. Всего будет (4М+6) ар.оп. Тогда для вычисления евклидова расстояния между У классами массива эталонов требуется затратить Н ( М + б) ар.on. Далее для сравнения значений евклидова расстояния и выбора среди ff классов наиболее близкого к анализируемому необходимо выполнить Hitfy /2- ар. on. Таким образом, общая вычислительная сложность Сэ (Mt ЇЇ) определения класса принадлежности образа при использовании в качестве меры сходства евклидова расстояния составляет: С3{М,Н) = МШп+Ь)+№-1)/я\ (4.2) Затрата такого количества операций необходима каждый раз при распознавании новых образов.
Теперь рассмотрим вычислительную сложность методов классификации, основанных на использовании формулы Байеса. Формула Бай-еса имеет вид [55]: Н0-Р(о,/хіхг-- ) Х0ЯіЯуАм , (4,3; где і,= РСОк)9 Х Р ihK), Х (Х 0ф(кя)Г п (хм10к)/р(х„) Л0- величина априорной вероятности класса /f , (#=4,2. ,,..,//), Р( iK) - условная вероятность того, что признак Xt- (і= і , 2 ,..., /vj) присутствует в классе 0К , p(xL)- вероятность наличия признака X; во всех классах. Формула Байеса дает возможность определить условную вероят ность существования класса 0ц при наличии признаков Xf, Хг,..., Xw по величине априорной вероятности Х0-Р(0К) и произведение коэффи циентов влияния признаков Xt , Ха, Хм
С появлением каждого нового объекта обучение распознающей системы, основанной на использовании формулы Байеса, требует постоянного уточнения вероятностей р (0К) t Н ІІ К) » P( t)« При этом предполагается, что объекты анализируемого массива достаточно полно представляют различаемые классы.
Похожие диссертации на Разработка и исследование системы автоматизированного распознавания структуры экспериментальных кривых
