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

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение Высшего профессионального образования

«Нижегородский государственный педагогический университет имени Козьмы Минина»

(Мининский университет) КУРСОВАЯ РАБОТА МАТЕМАТИЧЕСКАЯ ТЕОРИЯ РАСПОЗНАВАНИЯ ОБРАЗОВ Денисенко Ольга Александровна Студентка 6 курса, группы ИЗС-10

факультет МИФ Специальность 50 202.65 «Информатика»

Научный руководитель:

Годяева А.Е.

2013 год

ВВЕДЕНИЕ

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

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

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

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

Можно выделить два основных направления в распознавании образов ^- Ту Дж., Гонсалес Р. Принципы распознавания образов, М. 1978.:

· изучение способностей к распознаванию, которыми обладают живые существа, объяснение и моделирование их;

· развитие теории и методов построения устройств, предназначенных для решения отдельных задач в прикладных целях.

Объект исследования: основы теории распознавания образов.

Предмет исследования: характеристика систем и задач математической теории распознавания образов.

Цель исследования: раскрыть сущность теории распознавания образов.

Задачи исследования:

· дать понятие теории распознавания образов, определить его значение;

· рассмотреть основные задачи, возникающие при разработке систем распознавания образов;

· классифицировать систему распознавания образов реального времени;

· показать сущность математической теории распознавания образов.

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ РАСПОЗНАВАНИЯ ОБРАЗОВ

1.1 Основные понятия теории распознавания образов и ее значение

Распознавание образов — это наука о методах и алгоритмах классификации объектов различной природы. Лепский А. Е., Броневич А. Г. Математические методы распознавания образов: Курс лекций.- 2009.

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

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

В процессе биологической эволюции многие животные с помощью зрительного и слухового аппарата решили задачи распознавания образов достаточно хорошо. Создание искусственных систем распознавания образов остаётся сложной теоретической и технической проблемой. Необходимость в таком распознавании возникает в самых разных областях — от военного дела и систем безопасности до оцифровки всевозможных аналоговых сигналов.

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

Под классом образов понимается некоторая категория, определяемая рядом свойств, общих для всех ее элементов.

Образ — это описание любого элемента как представителя соответствующего класса образов.

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

Очевидное, но совсем уж «бесхитростное» решение задачи распознавания заключается в применении к отдельным предъявленным образам ряда простых тестов для выделения признаков каждого класса. Совокупность этих тестов должна различать все допустимые образы из разных классов. Например, рассмотрим пять английских букв: COINS. Эти буквы можно классифицировать, применив тесты на наличие таких признаков, как замкнутая кривая, изгиб, двойной изгиб, вертикальный отрезок, короткий отрезок.

Если следовать такому интуитивному подходу, то построение автоматической системы распознавания образов может показаться довольно простой задачей. Не существует, однако, общей теории, позволяющей определить, какие из всего множества мыслимых тестов следует применить к предъявленным образам. Очень ограниченное количество или небрежный выбор тестов не дадут возможности получить характеристики предъявленных для распознавания образов, достаточные для отнесения их к соответствующим классам. Слишком много тестов, с другой стороны, необоснованно усложняют вычисления, осуществляемые в процессе дальнейшего анализа. Отсутствует какое-либо общее правило для получения неких ориентиров, способствующих определению набора таких тестов. Подобный подход чрезмерно зависит от опыта и технической интуиции разработчика и поэтому часто не дает удовлетворительного решения задач распознавания образов, встречающихся в практической деятельности.

Математическая теория распознавания, включая её применение к разнообразным прикладным задачам, является одной из наиболее активно развивающихся областей математики и математической кибернетики. Концепция теории распознавания лежит в основе современных информационных систем, реализованных путём применения новейших компьютерных технологий. Интерес к проблеме распознавания продолжает быстро расти из-за расширяющегося круга задач в областях техники, вычислительной математики и кибернетики, теории информации, физики, химии, лингвистики, биологии, медицины.

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

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

Можно выделить несколько направлений использования методов распознавания образов:

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

— распознавание изображений, полученных в различных частотных диапазонах (оптическом, инфракрасном, радиочастотном, звуковом) и анализ сцен;

— распознавание речи;

— медицинская диагностика;

— системы безопасности;

— классификация, кластеризация и поиск в базах данных и знаний (в том числе и в Интернет-ресурсах). Лепский А. Е., Броневич А. Г. Математические методы распознавания образов: Курс лекций.- 2009.

1.2 Основные задачи, возникающие при разработке систем распознавания образов

При постановке задач распознавания стараются пользоваться математическим языком, стараясь, в отличие от теории искусственных нейронных сетей, где основой является получение результата путем эксперимента, заменить эксперимент логическими рассуждениями и математическими доказательствами Файн В. С. Опознавание изображений, М. 1970.

Задачи, возникающие при построении автоматической системы распознавания образов, можно обычно отнести к нескольким основным областям.

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

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

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

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

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

Лепский А.Е., Броневич А. Г. в своей работе основные задачи теории распознавания образов формулируют следующим образом:

— математическое описание образов;

— выбор наиболее информативных признаков (алфавита признаков и словаря признаков);

— описание классов распознаваемых образов;

— нахождение оптимальных решающих процедур (методов классификации);

— оценка достоверности классификации образов. Лепский А. Е., Броневич А. Г. Математические методы распознавания образов: Курс лекций.- 2009.

Одним из решений задачи распознавания образов является структурный или синтаксический метод.

математический образ реальный система

ГЛАВА 2. ОБЩАЯ ХАРАКТЕРИСТИКА СИСТЕМ И ЗАДАЧ РАСПОЗНАВАНИЯ ОБРАЗОВ

2.1 Синтаксический подход к распознаванию образов

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

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

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

«Язык», который обеспечивает структурное описание образов в терминах множества непроизводных элементов и операций композиции этих элементов, называют «языком описания образов».

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

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

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

Различные отношения, определенные между подобразами, или операции композиции, обычно могут быть выражены логическими и (или) математическими операциями. Если, например, в качестве единственного отношения (операции композиции) для описания образов выбрать «конкатенацию» (конкатенацией элементов, а и b называется составленная из них цепочка аb), то при непроизводных элементах прямоугольник будет представлен цепочкой aaabbсcсdd.

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

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

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

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

Систему синтаксического распознавания образов можно считать состоящей из трех основных частей, а именно: из блока предобработки, блока описания или представления объекта и блока синтаксического анализа. Блок предобработки осуществляет, во-первых, функции кодирования и аппроксимации и, во-вторых, функции фильтрации, восстановления и улучшения объекта. Исходный объект сначала кодируется или аппроксимируется так, чтобы это было удобно для дальнейшей обработки. Черно-белое изображение, например, можно кодировать при помощи решетки (или матрицы), состоящей из нулей и единиц, а кривую можно аппроксимировать отсчетами в дискретные моменты времени или конечным набором коэффициентов Фурье. Н. С. Пискунов «Дифференциальное и интегральное исчисления», Москва, «Наука», 1972 г. Затем используют методы фильтрации, восстановления и (или) улучшения для ликвидации шума, восстановления искажений и (или) улучшения качества закодированных (или аппроксимированных) объектов. Обычно предполагают, что на выходе предпроцессора имеются объекты относительно «хорошего качества». Каждый подвергнутый предобработке объект затем представляют в виде структуры языкового типа (например, цепочки). Этот процесс представления объекта состоит, во-первых, из сегментации и, во-вторых, из выделения непроизводных элементов (признаков). Чтобы представить объект через его подобразы, нужно этот объект сегментировать и в то же время идентифицировать (или выделить) в нем непроизводные элементы. Другими словами, каждый подвергнутый предобработке объект разделяется на части и непроизводные элементы на основе заранее заданных синтаксических операций (или операций композиции).

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

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

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

Одно из самых удивительных чудес природы — способность человека думать и обобщать. Одно из самых страстных желаний современной науки — научить думать компьютеры. В частности — различать образы, на что пока способен только мозг органических существ.

На заре создания систем искусственного интеллекта и споры о том, «мыслят» ли компьютеры или смогут ли они когда-либо это делать, были одними из самых горячих. Сейчас многое проясняется, становится понятным, что, несмотря на необычайный прогресс электроники, пределом возможностей систем искусственного интеллекта являются возможности интеллекта естественного. Другими словами: не стоит соперничать с природой, столь совершенной и гармоничной системой, а вот воссоздать способность человеческого мозга к анализу и обобщению информации — это вполне конкретная и во многом реальная задача, которой на протяжении последних десятилетий занимаются ученые различных специальностей: от нейрохирургов до классических математиков, инженеров программного обеспечения. Один из главных результатов на этом сложном пути — это практика распознавания образов.

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

2.3. Классификация систем распознавания образов реального времени

В основе любой классификации лежат определенные классификационные признаки (принципы). Так, Горелик А. Л., Скрипкин В. А. в своей работе Горелик А. Л., Скрипкин В. А. Методы распознавания. — М.: Высш. шк, 2004. — 261 с. в качестве квалификационного признака используются свойства информации, которая применяется в процессе распознавания. Однако такая классификация не отражает всех характеристик системы реального времени (РВ), поэтому была разработана классификация по свойствам управления систем распознавания образов (СРО) в процессе распознавания (Рис. 1).

Рис. 1. Классификация СРО РВ

Принцип классификации по контролю времени распознавания образов разделяет СРО, на неконтролируемые по времени (т.е. не системы РВ и поэтому не отражены на рисунке 1), гибкие системы РВ и жёсткие системы РВ. Жёсткие СРО РВ характеризуются наличием жёстких сроков для каждого случая распознавания (в них обязательно необходимо укладываться). Гибкие СРО РВ отличаются тем, что нарушения сроков распознавания нежелательны, но допустимы. К неконтролируемым по времени системам относятся такие системы, которые проектируются для распознавания каких-либо объектов без конкретных сроков.

Если в качестве принципа классификации использовать влияние выходных результатов распознавания на управление системой, то СРО РВ можно разделить на системы без обратной связи и с обратной связью. Системы без обратной связи в самом простейшем случае можно описать в виде: Y = f (X) (Рис. 2).

Рис. 2. СРО РВ без обратной связи

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

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

Yt = f (Xt, Yt-1), Xt = f (Xt, Yt-1)

где t — текущий момент распознавания.

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

Рис. 3. СРО РВ с обратной связью

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

Принцип классификации по автономности разделяет СРО РВ в соответствии со стандартом POSIX.13−2003:

* минимальные системы РВ;

* управляющие системы РВ;

* специализированные системы РВ;

* универсальные системы РВ.

Отличия данных систем обусловлены усложнением с программной точки зрения и поддержки аппаратных средств. Так минимальные системы РВ должны работать в составе АСУ, а универсальные системы являются самодостаточными.

2.4 Значение и некоторые задачи математической теории распознавания образов Математическая теория распознавания образов возникла, должно быть, одновременно с теорией искусственного интеллекта, являясь одним из ее разделов. Специалисты по распознаванию образов пытаются построить алгоритмы, повторяющие элементы человеческого мышления (прежде всего абстрактного) и предшествующего ему обучения на конкретных примерах. По-видимому, одна из первых задач распознавания образов была сформулирована в работах биолога Ф. Розенблатта Ф. Розенблатт. Принципы нейродинамики. Перцептроны и теория механизмов мозга. Издательство: Мир/Год издания- 1965 г., посвященных имитации зрительного анализатора. Потребовалось построить алгоритм распознавания простейших изображений — например, цифр или букв. И до сих пор задачи такого рода остаются в распознавании образов наиболее популярными.

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

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

Более интересны математические задачи, связанные с дискретной оптимизацией, с теорией сложности алгоритмов, статистическими задачами принятия решений. Допустим, для обучения предоставлен некий материал. В случае медицинской диагностики это может быть обширная база данных по обследованию больных и здоровых людей. Задача состоит в том, чтобы на ее основе построить алгоритм, некое решающее правило, которое можно впоследствии использовать для диагностики. Причем главной проблемой является экстраполяционная (обобщающая) способность этого правила: с какой вероятностью оно будет правильно классифицировать нового пациента, данные о котором не использовались при обучении? По мере развития теории распознавания образов появляются все более совершенные алгоритмы и математические утверждения, позволяющие прогнозировать, что при каких-то условиях заданный алгоритм будет выдавать именно те значения, которые мы ожидаем. Как раз в этом направлении и удается получать довольно любопытные результаты. Здесь следует упомянуть заслуги советских математиков В. Н. Вапника, А. Я. Червоненкиса, Ю. И. Журавлева и др. Свердловская школа распознавания образов, родоначальником которой является профессор Вл.Д.Мазуров, является одной из ведущих в России. Разработанная здесь теория комитетных алгоритмов распознавания опирается на результаты Сергея Николаевича Черникова и Ивана Ивановича Еремина по теории линейных неравенств и математического программирования.

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

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

Само распознавание является достаточно разработанным вариантом такой теории, поскольку позволяет разрешать ее основную задачу — синтезировать и выбирать алгоритмические средства для извлечения полезной информации из данных.

К постановке задачи распознавания прибегают в тех случаях, когда трудно строить формальные теории и применять математические методы, что происходит обычно по двум причинам:

а) уровень формализации соответствующей предметной области или доступная информация таковы, что не могут составить основу для синтеза математической модели, отвечающей классическим математическим или математико-физическим канонам и допускающей изучение классическими аналитическими или численными методами;

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

Потребность в синтезе моделей алгоритмов распознавания в первую очередь определялось необходимостью фиксировать каким-то образом класс алгоритмов при выборе оптимальной или хотя бы приемлемой процедуры решения конкретной задачи. В свою очередь, попытки построения таких моделей породили интерес к собственно «математическим» свойствам алгоритмов распознавания, в особенности их строгого обоснования. Оказалось, что получение описания класса алгоритмов распознавания представляют собой задачу, сходную с построением классического определения алгоритма.

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

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

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

Алгоритм распознавания при этом рассматривается как суперпозиция двух операторов. Первый из этих операторов — распознающий — в качестве ответов формирует элементы, называемые оценками, а второй — по оценкам определяет окончательные ответы.

Методология распознавания используется в информатике в двух качествах:

· во-первых, по прямому назначению для решения задач распознавания в классическом смысле;

· во-вторых, как средство точного исследования плохо определенных задач.

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

Любому специалисту в своей практической деятельности приходится изучать зависимости между различными параметрами исследуемых объектов, процессов и систем. Из всех способов задания зависимостей наиболее удобным является аналитический способ задания зависимости. Однако, на практике специалист чаще всего получает зависимости между исследуемыми параметрами экспериментально. В этом случае ставится натурный эксперимент, изменяются значения параметров на входе системы, изменяются значения параметров на выходе системы. Результаты измерения заносятся в таблицу. В результате проведения натурного эксперимента получаем зависимости между исследуемыми параметрами в виде таблицы, т. е. получаем, так называемую, табличную функцию. Задача, возникающая перед исследователем, состоит в отыскании соответствующего аналитического выражения для функции, т. е. распознать табличную функцию. Для этой цели могут быть употреблены тригонометрические ряды, поскольку есть уверенность, что эта функция приближенно и достаточно точно может быть выражена суммой конечного числа первых членов ее ряда Фурье. Весь вопрос заключается в нахождении коэффициентов Фурье функции. Н. С. Пискунов «Дифференциальное и интегральное исчисления», Москва, «Наука», 1972 г.

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

Приближенное представление функции в виде многочлена Фурье требует отыскания первых коэффициентов Фурье Рис. 1.

Приведем алгоритм решения задачи.

1. Задается функция в интервале .

2. Интервал делится на п равных частей с помощью точек

.

3. Вводятся значения входных параметров (xi, yi)

4. Вычисляются коэффициенты ak, bk

где .

5. Получаем приближенное выражение функции в виде тригонометрического многочлена

.

Принимая во внимание особенности множителей coskxi и sinkxi, берут п чаще всего равным 12 или 24. Мы здесь возьмем п=12.

Вычисляем коэффициенты ak, bk.

Так как соs0=1

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

Что же касается будущего идеи искусственного интеллекта… Уже сегодня много говорится о так называемых квантовых вычислениях и квантовых компьютерах. Возможно, когда квантовые машины станут реальностью, мы и подойдем к решению этой задачи.

ЗАКЛЮЧЕНИЕ

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

Можно заметить, что похожие действия наблюдаются в биологии, в живой природе, а иногда даже в неживой. Кроме того, распознавание постоянно встречается в технике. А если это так, то, очевидно, следует считать механизм распознавания всеобъемлющим.

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

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

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

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

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

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

1. Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. — М.: Наука, 2004. — 384 с.

2. Бермант А. Ф., Араманович И. Г. Краткий курс математического анализа. — М.: Наука, 1971 г.

3. Бородаенко Д. Н. Распознавание образов // Распознавание образов и искусственный интеллект. 2001. http://www.ocrai.narod.ru (26.12.2007).

4. Боровиков В. STATISTICA. Искусство анализа данных на компьютере: Для профессионалов. — СПб.: Питер, 2003. 688 с.

5. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. М: Наука, 1974.

6. Воронцов К. В. Лекции по статистическим (байесовским) алгоритмам классификации, 2008.

7. Горелик А. Л., Гуревич И. Б., Скрипкин В. А. Современное состояние проблемы распознавания. Издательство: Радио и связь. 1985, 160 с.

8. Горелик А. Л., Скрипкин В. А. Методы распознавания. М.: Высш. шк, 2004. 261 с.

9. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации// Проблемы кибернетики. М.: Наука, 2005. Вып. 33. С. 5−68

10. Журавлев Ю. И. Избранные научные труды. Изд. Магистр, 2002. — 420 с.

11. Каримов Р. Н. Обработка экспериментальной информации. Уч. Пособие. Ч. 3. Многомерный анализ. СГТУ, Саратов, 2000, 108 с.

12. Ким Дж, Мьюллер Ч. У. и др. Факторный, дискриминантный и кластерный анализ. Пер. с англ. М.: Финансы и статистика, 1989, 215 с.

13. Лепский А. Е., Броневич А. Г. Математические методы распознавания образов: Курс лекций.- 2009.

14. Лиховидов В. Н. Практический курс распознавания образов. — Владивосток: издательство ДВГУ, 1983.

15. Мазуров Вл.Д. Математические методы распознавания образов. Учебное пособие. 2010 г., 101 с.

16. Мазуров В. Д. Комитеты систем неравенств и задача распознавания // Кибернетика, 2004, № 2. С. 140−146.

17. Математические методы распознавания образов // Доклады 11-й Всероссийской конференции. — 2003. — 18 апр. — С.18.

18. Н. С. Пискунов «Дифференциальное и интегральное исчисления», Москва, «Наука», 1972 г.

19. Потапов А. С. Распознавание образов и машинное восприятие. — С-Пб.: Политехника, 2007. — 548 с

20. Распознавание, классификация прогноз. Математические методы и их применение. — М.: Наука, 1989 г.

21.Ту Дж., Гонсалес Р. Принципы распознавания образов. — М.: Мир, 1978, 411 с.

22. Файн В. С. Опознавание изображений, М. 1970

23. Фихтенгольц Г. М. Основы математического анализа. М.: Гостехиздат, 1956.

24. Фихтенгольц Г. М. «Курс дифференциального и интегрального исчисления», том III, Москва, «Наука», 1969 г.

25. Ф. Розенблатт. Принципы нейродинамики. Перцептроны и теория механизмов мозга. Издательство: Мир.1965 г.

26. Фу К. Структурные методы в распознавании образов. — М.: Мир, 2005. — 144 с.

27. Фу. К. Последовательные методы в распознавании образов и обучении машин/ К. Фу. — М.: Наука, 1971. — 355 с.

28. Фукунага К.

Введение

в статистическую теорию распознавания образов/ К. Фукунага — М.: Наука, 1979. — 267 с.

29. Эдвард А. Патрик. Основы теории распознавания образов. Пер. с англ. Под ред. Б. Р. Левина. Издательство: М.: «Советское радио» .1980. 864 с.