Общая характеристика задач распознавания образов и их типы. Методы распознавания образов Системы обработки изображений и распознавания образов

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

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

Цель работы: изучить историю систем распознавания образов.

Указать качественные изменения произошедшие в области распознавания образов как теоретические, так и технические, с указанием причин;

Обсудить методы и принципы, применяемые в вычислительной технике;

Привести примеры перспектив, которые ожидаются в ближайшем будущем.

1. Что такое распознавание образов?

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

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

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

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

Определения

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

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

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

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

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

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

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

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

Примеры задач распознавания образов: - Распознавание букв;

Методы автоматического распознавания образов и их реализация в системах оптического распознавания текстов (Optical Character Recognition - OCR-системы) - одна из самых прогрессивных технологий искусственного интеллекта. В развитии этой технологии российские ученые занимают ведущие позиции в мире.

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

Аббревиатура OCR иногда расшифровывается как Optical Character Reader - устройство оптического распознавания символов или автоматического чтения текста. В настоящее время такие устройства в промышленном использовании обрабатывают до 100 тыс. документов в сутки.

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

Перечислим особенности предметной области, существенные с точки зрения OCR-систем:

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

Автоматическое чтение печатных и рукописных текстов является частным случаем автоматического визуального восприятия сложных изображений. Многочисленные исследования показали, что для полного решения этой задачи необходимо интеллектуальное распознавание, т. е. «распознавание с пониманием».

Выделяются три принципа, на которых основаны все OCR-системы.

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

Ведущие российские OCR-системы: FineReader; FineReader Рукопись; FormReader; CunieForm (Cognitive Technologies), Cognitive Forms (Cognitive Technologies) .

Система FineReader выпускается компанией ABBYY, которая была основана в 1989 г. Разработки компании ABBYY ведутся в двух направлениях: машинное зрение и прикладная лингвистика. Стратегическим направлением научных исследований и разработок является естественно-языковой аспект технологий в области машинного зрения, искусственного интеллекта и прикладной лингвистики.

CuneiForm GOLD for Windows является первой в мире само-обучаемой интеллектуальной OCR-системой, использующей новейшую технологию адаптивного распознавания текстов, поддерживает много языков. Для каждого языка поставляется словарь контекстной проверки и повышения качества результатов распознавания. Распознает любые полиграфические, машинописные гарнитуры и шрифты, получаемые с принтеров, за исключением декоративных и рукописных, а также очень низкокачественных текстов.

Характеристики систем распознавания образов. Среди ОСЯ-технологий большое значение имеют специальные технологии решения отдельных классов задач автоматического распознавания образов:

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

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

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

Потом строки разбиваются на непрерывные области изображения, которые соответствуют отдельным буквам; алгоритм распознавания выдвигает предположения относительно соответствия этих областей символам, а затем осуществляется выбор каждого символа, в результате чего страница восстанавливается в символах текста, причем, как правило, в заданном формате. ОСЯ-системы могут достигать наилучшей точности распознавания - свыше 99,9 % для чистых изображений, составленных из обычных шрифтов. На первый взгляд такая точность распознавания кажется идеальной, но уровень ошибок все же удручает, потому что, если имеется приблизительно 1500 символов на странице, то даже при коэффициенте успешного распознавания 99,9 % получается одна или две ошибки на страницу. В таких случаях следует воспользоваться методом проверки по словарю, т. е. если какого-то слова нет в словаре системы, то она по специальным правилам попытается найти похожее. Но это все равно не позволяет исправлять 100 % ошибок и требует контроля результатов человеком.

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

Программное обеспечение ОСЯ-системы обычно работает с большим растровым изображением страницы, полученной из сканера. Изображения со стандартной степенью разрешения достигаются сканированием с точностью 9600 п/д. Изображение листа формата A4 при этом разрешении занимает около 1 Мб памяти.

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

Работа с OCR-системами, как правило, не должна вызывать особых затруднений. Большинство таких систем имеют простейший автоматический режим «сканируй и распознавай» (Scan & Read), а также они поддерживают и режим распознавания изображений из файлов. Однако для того чтобы достигнуть лучших из возможных для данной системы результатов, желательно (а нередко и обязательно) предварительно вручную настроить ее на конкретный вид текста, макет бланка и качество бумаги. Страница, расположенная с нарушением границ или перекосом, создает немного искаженные символьные изображения, которые могут быть перепутаны OCR-системой.

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

На данный момент существует огромное количество программ, поддерживающих распознавание текста как одну из возможностей. Лидером в этой области является система FineReader. Последняя версия программы (6.0) теперь имеет средства для разработки новых систем на базе технологии FineReader 6.0. В состав семейства FineReader 6.0 входят: система FineReader 6.0 Professional, FineReader 6.0 Corporate Edition, FineReader Scripting Edition 6.0 и FineReader Engine 6.0. Система FineReader 6.0, кроме того, что знает огромное количество форматов для сохранения, включая PDF, имеет возможность прямого распознавания из PDF-файлов. Новая технология Intelligent Background Filtering (интеллектуальная фильтрация фона) позволяет отсеять информацию о текстуре документа и фоновом шуме изображения: иногда для выделения текста в документе используется серый или цветной фон. Человеку это не мешает читать, но обычные алгоритмы распознавания текста испытывают серьезные затруднения при работе с буквами, расположенными поверх такого фона. Программа FineReader умеет определять зоны, содержащие подобный текст, отделяя текст от фона документа, находя точки, размер которых меньше определенной величины, и удаляя их. При этом контуры букв сохраняются, так что точки фона, близко расположенные к данным контурам, не вносят помех, способных ухудшить качество распознавания текста.

Используя возможности современных программ верстки, дизайнеры часто создают объекты сложной формы, такие как обтекание непрямоугольной картинки многоколоночным текстом. В системе FineReader 6.0 реализована поддержка распознавания таких объектов и их сохранение в файлах формата MS Word. Теперь документы сложной верстки будут точно воспроизведены в данном текстовом редакторе. Даже таблицы распознаются с максимальной точностью, сохраняя при этом все возможности для редактирования.

Система ABBYY FormReader - одна из программ распознавания от фирмы ABBYY, основанная на системе ABBYY FineReader Engine. Эта программа предназначена для распознавания и обработки форм, которые могут быть заполнены вручную. Программа ABBYY FormReader может обрабатывать формы с фиксированной схемой так же хорошо, как и формы, чья структура может меняться. Для распознавания была применена новая технология ABBYY FlexiForm technology.

Ведущие производители программного обеспечения лицензировали российскую информационную технологию для применения со своими продуктами. В популярные программные пакеты Corel Draw (Corel Corporation), FaxLine/OCR & Business Card Wizard (Inzer Corporation) и многие другие встроена OCR-библиотека CuneiForm. Эта программа стала первой в России OCR-системой, получившей MS Windows Compatible Logo.

Система Readiris Pro 7 - профессиональная программа распознавания текста. По словам производителей, данная OCR-система отличается от аналогов высочайшей точностью преобразования обычных (каждодневных) печатных документов, таких как письма, факсы, журнальные статьи, газетные вырезки, в объекты, доступные для редактирования (включая файлы формата PDF). Основными достоинствами программы являются: возможность более или менее точного распознавания картинок, сжатых «по максимуму» (с максимальной потерей качества) методом формата JPEG, поддержка цифровых камер и автоопределения ориентации страницы, поддержка до 92 языков (включая русский).

Система OmniPage 11 - продукт компании ScanSoft. Ограниченная версия этой программы (OmniPage 11 Limited Edition, OmniPage Lite) обычно поставляется в комплекте с новыми сканерами (на территории Европы и США). Разработчики утверждают, что их программа практически со 100%-ной точностью распознает печатные документы, восстанавливая их форматирование, включая столбцы, таблицы, переносы (в том числе переносы частей слов), заголовки, названия глав, подписи, номера страниц, сноски, параграфы, нумерованные списки, красные строки, графики и картинки. Есть возможность сохранения в форматы Microsoft Office, PDF и в 20 других форматов, распознавания из файлов формата PDF и редактирования в этом формате. Система искусственного интеллекта позволяет автоматически обнаруживать и исправлять ошибки после первого исправления вручную. Новый специально разработанный программный модуль «Dcspeckle» позволяет распознавать документы с ухудшенным качеством (факсы, копии, копии копий и т. д.). Преимуществом программы является возможность распознавания цветного текста и корректировки голосом. Версия OmniPage существует и для компьютеров фирмы Macintosh.

• См.: Башмаков А. И., Башмаков И. А. Интеллектуальные информационные технологии.

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

Распознавание символов

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

Рис. 1.7. (см. скан) Комплект шрифта Е-13В Американской банковской ассоциации (American Bankers Association) и формы сигнала, соответствующие отдельным символам набора.

На большинстве чеков, имеющих хождение в настоящее время в Соединенных Штатах, в качестве стилизованных символов используется стандартный комплект шрифта Е-13В Американской банковской ассоциации (American Bankers Association). Как следует из рис. 1.7, этот комплект включает 14 символов, специально адаптированных к сетчатке, содержащей участков, с тем чтобы упростить процесс считывания. Эти символы обычно наносятся особой типографской краской, которая содержит очень

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

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

Существуют также коммерческие варианты устройств для считывания шрифтов разных типов. Так, например, система «Input 80» (рис. 1.8), разработанная компанией Recognition Equipment Incorporated, может считывать информацию, представленную в машинописном, типографском и рукописном виде, непосредственно с оригиналов документов со скоростью до

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

Рис. 1.8. (см. скан) Система распознавания символов «REI Input 80 Model А» компании Recognition Equipment Incorporated, Даллас, штат Техас. На рисунке представлены следующие компоненты системы (по часовой стрелке): блок распознавания, контроллер с программным управлением, печатающее устройство для ввода/вывода данных, построчно-печатающее устройство, блок распознавания, блок магнитной ленты и страничный процессор. Фотография любезно предоставлена Recognition Equipment Incorporated.

Основные особенности работы системы «Input 80» REI заключаются в следующем. Страницы с помощью системы разреженных участков и воздушных эжекторов попадают на ленточный конвейер, который подает их в считывающее устройство. Здесь зеркальце, совершающее высокочастотные колебания, фокусирует луч света высокой интенсивности на символах, подлежащих считыванию; луч пересекает строку печатных символов со скоростью около 7,62 м/с. Второе, синхронизирующее, зеркальце воспринимает световые изображения, представляющие

различные части символа, и проектирует их на «интегральную ретину» - считывающее устройство, выполненное на интегральной схеме; оно состоит из 96 фотодиодов, размещенных в одной кремниевой пластине длиной около 38,1 мм. Это устройство является «глазом» системы. Интегральная ретина кодирует каждый символ, представляя его с помощью матрицы 16X12 ячеек, стандартизует символы, производит коррекцию в соответствии с вариациями их размера, действуя со скоростью до 3600 символов в секунду. Интегральная ретина, кроме того, классифицирует каждую ячейку представления каждого символа в соответствии с принадлежностью к одному из 16 уровней зачерненности.

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

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

Автоматическая классификация данных, полученных дистанционно

Сравнительно недавно возникший в Соединенных Штатах интерес к качеству окружающей среды и состоянию природные ресурсов вызвал к жизни множество приложений методов

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

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

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

На основе спектральных данных, полученных во время рассматриваемого полета, построен байесовский классификатор для образов, подчиняющихся нормальному распределению (см. § 4.3). На рис. 1.9,б приведена машинная выдача результатов

применения такого классификатора для автоматической классификации миогодиапазонных спектральных данных, соответствующих небольшому участку земной поверхности, представленному на рис. 1.9, а. Стрелками отмечены некоторые признаки, представляющие специальный интерес. Стрелка 1 помещена в углу поля зеленой растительности, стрелка 2 обозначает реку. Стрелкой 3 отмечена небольшая живая изгородь, разделяющая два участка обнаженной почвы; эти объекты точно идентифицированы на распечатке. Приток, который также правильно идентифицирован, отмечен стрелкой 4. Стрелка 5 указывает на очень маленький пруд, который на цветной фотографии почти неразличим. При сопоставлении исходного изображения с результатами машинной классификации становится очевидно, что последние весьма точно соответствуют тем выводам, к которым пришел бы человек, интерпретируя исходную фотографию визуально.

Биомедицинские приложения

Как отмечалось в § 1.1, медицина в настоящее время сталкивается с серьезными проблемами, связанными с обработкой информации. Методы распознавания образов с переменным успехом применялись для автоматической обработки данных, полученных с помощью различных технических средств, применяемых в медицинской диагностике, например, таких, как рентгенограммы, электрокардиограммы, электроэнцефалограммы, и анализа и интерпретации вопросников, заполняемых пациентами. Одной из задач, которым уделялось много внимания, является автоматизация анализа и классификации хромосом.

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

Рис. 1.10. (см. скан) Кровяные тельца человека, окрашенные но Гимзе,- препарат, демонстрирующий структуру хромосом. Иллюстрация любезно предоставлена д-ром Нилом Вальдом из Высшей школы здравоохранения Питгсбургского университета, Питтсбург, штат Пенсильвания (Dr. Niel Wald, Graduate Schoo of Public Health, University of Pittsburgh).

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

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

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

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

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

Распознавание отпечатков пальцев

Как мы отмечали в § 1.1, правительственные агентства располагают архивами, в которых хранятся свыше 200 миллионов отпечатков пальцев. Отдел идентификации (The Identification Division) Федерального Бюро Расследований располагает, в частности, самым большим в мире архивом отпечатков пальцев - свыше 160 миллионов. Ежедневно в отдел поступает до 30 тысяч запросов. Для того чтобы справиться с таким объемом работы,

около 1400 технических специалистов и чиновников должны тщательно классифицировать новые отпечатки и затем педантично искать совпадения.

В течение ряда лет ФБР проявляло интерес к разработке автоматической системы идентификации отпечатков пальцев. Примером усилий, предпринятых в этом направлении, служит система-прототип FINDER, разработанная компанией Calspan Corporation по заданию ФБР. Эта система автоматически обнаруживает и локализует признаки, характерные для отпечатка. Признаки, которые обнаруживает система, - это не крупные структурные элементы типа дуг, контуров или завитков, используемых в процессе первичной классификации отпечатков, - это скорее мелкие детали - концы и разветвления бороздок, аналогичные изображенным на рис. 1.11.

Рис. 1.11. Фрагменты - концы бороздок (квадраты) и разветвления (окружности) - используемые системой FINDER при идентификации отпечатков пальцев. Фотография любезно предоставлена мистером К. У. Суонгером из Calspan Corporation, Буффало, штат Нью-Йорк.

На рис. 1.12 приведена блок-схема системы. Вкратце действие системы FINDER можно описать следующим образом. Оператор вводит стандартный бланк отпечатка в автоматическое входное устройство, которое доставляет отпечаток к «глазу» системы - развертывающему устройству и точно размещает под ним отпечаток. Каждый отпечаток подвергается квантованию и представляется матрицей, содержащей 750X750 точек, причем каждая точка кодируется одним из 16 возможных уровней зачерненности. Процесс сканирования осуществляется под управлением универсальной вычислительной машины. На рис. 1.13 приведен пример, показывающий, какой вид принимает отпечаток, пройдя развертывающее устройство.

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

(кликните для просмотра скана)

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

Рис. 1.13. Распечатка участка, полученного на выходе сканирующего устройства. На этом цифровом изображении черные элементы представлены цифрой «0», а белые - «15». Иллюстрация любезно предоставлена мистером

К. У. Суонгером из Calspan Corporation, Буффало, штат Нью-Йорк.

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

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

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

Рис. 1.14. Результаты пропуска данных, представленных на рис. 1.13, через фильтр бороздок-желобков. В данном случае черные точки представлены символами «г». Иллюстрация любезно предоставлена мистером К. У. Суонгером из Calspan Corporation, Буффало, штат Нью-Йорк.

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

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

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

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

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

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

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

Рис. 1.15 Основные компоненты автоматической системы анализа шума.

На рис. 1.15 приведены основные компоненты автоматической системы управления. Представляющие шум сигналы, поступающие от датчиков, которые установлены в энергетической ядерной установке, нормируются, подвергаются предварительной обработке и вводятся в систему распознавания образов. На выходе этой системы воспроизводится решение, характеризующее текущее состояние установки. В нашем случае речь идет о ядерном реакторе с большой плотностью нейтронного потока, предназначенном для производства изотопов: реактор установлен в Окриджской национальной лаборатории (Oak Ridge National Laboratory). В качестве исходных данных для контроля за режимом этого реактора используются результаты измерений нейтронного шума, которые проводятся в среднем трижды в день. Топливный цикл (промежуток времени между перезарядкой топливных элементов) составляет обычно при работе с полной мощностью 22 дня. Блок предварительной обработки на основании этих данных определяет спектральную плотность мощности в диапазоне частот от 0 до 31 Гц с интервалом в 1 Гц. Следовательно, результаты каждого измерения можно представить 32-мерным вектором образа , где - амплитуда спектральной плотности мощности излучения на частоте 0 Гц, - амплитуда на частоте 1 Гц и т. д. Задача в таком случае сводится к построению системы распознавания образов, способной автоматически анализировать подобные образы.

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

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

Рис. 1.16. Типичные спектральные плотности мощности нейтронного излучения, соответствующие нормальному режиму ядерного реактора с большой плотностью нейтронного потока, предназначенного для производства изотопов. Наибольшим пикам на каждом из графиков соответствует значение 1. Истинные значения спектральной плотности можно получить, умножив значения, полученные из графика, на соответствующие масштабные коэффициенты. Они равны: . Графики заимствованы из статьи Гонсалеса, Фрая и Крайтера, IEEE Trans. Nucl. Sci., 21, No. 1, February 1974 (R. C. Gonzales, D. N. Fry, R. C. Kryter, Results in the Application of Pattern Recognition Methods to Nuclear Reactor Core Component Surveillance).

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

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

Рис. 1.17. Спектральные плотности, соответствующие аномальному поведению ядерного реактора с большой плотностью нейтронного потока, предназначенного для производства изотопов. Масштабные коэффициенты в данном случае равны: . Графики заимствованы из статьи Гонсалеса, Фрая и Крайтера, IEEE Trans. Nucl. Sci., 21, No. 1, February 1974 (R. C. Gonzalez, D. N. Fry, R. C. Kryter, Results in the Application of Pattern Recognition Methods to Nuclear Reactor Core Component Surveillance).

Лекция № 17. МЕТОДЫ РАСПОЗНАВАНИЯ ОБРАЗОВ

Различают следующие группы методов распознавания:

Методы функций близости

Методы дискриминантных функций

Статистические методы распознавания.

Лингвистические методы

Эвристические методы.

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

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

Группа эвристических методов объединяет характерные приемы и логические процедуры, используемые человеком при распознавании образов.

Методы функций близости

Методы данной группы основаны на использовании функций, оценивающих меру близости между распознаваемым образом с вектором x * = (x * 1 ,….,x * n ), и эталонными образами различных классов, представленными векторами x i = (x i 1 ,…, x i n ), i= 1,…,N , где i – номер класса образов.

Процедура распознавания согласно данному методу состоит в вычислении расстояния между точкой распознаваемого образа и каждой из точек, представляющих эталонный образ, т.е. в вычислении всех значений d i , i= 1,…,N . Образ относится к классу, для которого значение d i имеет наименьшее значение среди всех i= 1,…,N .

Функция, ставящая в соответствие каждой паре векторов x i , x * вещественное число как меру их близости, т.е. определяющая расстояние между ними может быть достаточно произвольной. В математике такую функцию называют метрикой пространства. Она должна удовлетворять следующим аксиомам:

r (x,y )= r (y,x );

r (x,y ) > 0, если x не равен y и r (x,y )=0 если x=y ;

r (x,y ) <= r (x,z )+ r (z,y )

Перечисленным аксиомам удовлетворяют, в частности, следующие функции

a i = 1/2 , j =1,2,…n .

b i =sum, j =1,2,…n .

c i =max abs (x i ‑ x j * ), j =1,2,…n .

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

Часто в качестве функции близости выбирают среднеквадратическую разность координат распознаваемого образа x * и эталона x i , т.е. функцию

d i = (1/n ) sum(x i j ‑ x j * ) 2 , j =1,2,…n .

Величина d i геометрически интерпретируется как квадрат расстояния между точками в пространстве признаков, отнесенный к размерности пространства.

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

В таком случае d i = (1/n ) sum w j (x i j ‑ x j * ) 2 , j =1,2,…n ,

где w j – весовые коэффициенты.

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

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

Группы близких друг другу точек образов (скопления образов) в пространстве признаков называют кластерами, а задачу выделения таких групп – задачей кластеризации.

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

Методы дискриминантных функций

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

Общий вид линейной решающей функции задается формулой

d (x )=w 1 x 1 + w 2 x 2 +…+ w n x n + w n +1 = Wx +w n

где x - вектор образа, w= ( w 1 , w 2 ,…w n ) – вектор весовых коэффициентов.

В случае разбиения на два класса X 1 и X 2 дискриминантная функция d (x) позволяет осуществить распознавание в соответствии с правилом:

x принадлежит X 1 , если d (x )>0;

x принадлежит X 2 , если d (x )<0.

Если d (x )=0, то имеет место случай неопределенности.

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

Например, если введены три дискриминантные функции, то возможен следующий вариант выделения классов образов:

x принадлежит X 1 , если d 1 (x )>0, d 2 (x )<0, d 3 (x )<0;

x принадлежит X 2 , если d (x )<0, d 2 (x )>0, d 3 (x )<0;

x принадлежит X 3 , если d (x )<0, d 2 (x )<0, d 3 (x )>0.

При этом считается, что для других комбинаций значений d 1 (x ), d 2 (x ), d 3 (x ) имеет место случай неопределенности.

Разновидностью метода дискриминантных функций является метод решающих функций. В нем при наличии m классов предполагается существование m функций d i (x ), называемых решающими, таких, что если x принадлежит X i , то d i (x ) > d j (x ) для всех j не равных i ,т.е. решающая функция d i (x ) имеет максимальное значение среди всех функций d j (x ), j =1,...,n ..

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

Евклидово расстояние между вектором признаков распознаваемого образа x и вектором эталонного образа определяется формулой ||x i ‑ x || = 1/2 , j =1,2,…n .

Вектор x будет отнесен к классу i , для которого значение ||x i ‑ x * || минимально.

Вместо расстояния можно сравнивать квадрат расстояния, т.е.

||x i ‑ x || 2 = (x i ‑ x )( x i ‑ x ) т = x x - 2x x i + x i x i

Поскольку величина x x одинакова для всех i , минимум функции ||x i ‑ x || 2 будет совпадать с максимумом решающей функции

d i (x ) = 2x x i - x i x i .

то есть x принадлежит X i , если d i (x ) > d j (x ) для всех j не равных i .

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

d i (x )=w i 1 x 1 + w i 2 x 2 +…+ w in x n + w i n +1

Она может быть наглядно представлена соответствующей структурной схемой.

Для машины, осуществляющей классификацию по минимуму расстояния имеют место равенства: w ij = -2x i j , w i n +1 = x i x i .

Эквивалентное распознавание методом дискриминантных функций может быть осуществлено, если определить дискриминантные функции как разности d ij (x )= d i (x )‑ d j (x ).

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

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

При этом алгоритм автоматического обучения оказывается весьма простым в сравнении с другими методами распознавания.

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

Процедуры самообученя распознаванию образов

Рассмотрим методы построения дискриминантной функции по заданной (обучающей) выборке применительно к задаче о разделении образов на два класса. Если заданы два множества образов, принадлежащих соответственно классам А и В, то решение задачи построения линейной дискриминантной функции ищется в виде вектора весовых коэффициентов W =(w 1 ,w 2 ,...,w n ,w n +1), обладающего тем свойством, что для любого образа выполняются условия

x принадлежит классу A, если >0, j =1,2,…n .

x принадлежит классу B, если <0, j =1,2,…n .

Если обучающую выборку составляют N образов обоих классов, задача сводится к отысканию вектора w, обеспечивающего справедливость системы неравенств Если обучающую выборку составляют N образов обоих классов, задача сводится к отысканию вектора w , обеспечивающего справедливость системы неравенств

x 1 1 w i +x 21 w 2 +...+x n 1 w n +w n +1 >0;

x 1 2 w i +x 22 w 2 +...+x n 2 w n +w n +1 <0;

x 1 i w i +x 2i w 2 +...+x ni w n +w n +1 >0;

................................................

x 1 N w i +x 2N w 2 +...+x nN w n +w n + 1>0;

здесь x i =(x i 1 ,x i 2 ,...,x i n ,x i n+ 1 ) - вектор значений признаков образа из обучающей выборки, знак > соответствует векторам образов x , принадлежащих классу A, а знак < - векторам x , принадлежащих классу B.

Искомый вектор w существует, если классы A и B разделимы и не существует в противном случае. Значения компонент вектора w могут быть найдены либо предварительно, на этапе, предшествующем аппаратной реализации СРО, либо непосредственно самой СРО в процессе ее функционирования. Последний из указанных подходов обеспечивает большую гибкость и автономность СРО. Рассмотрим его на примере устройства, называемого перцентроном. изобретенного в 1957 году американским ученым Розенблатом. Схематичное представление перцентрона, обеспечивающего отнесение образа к одному из двух классов, представлено на следующем рисунке.

Сетчатка S Сетчатка A Сетчатка R

о о x 1

о о x 2

о о x 3

о (sum)-------> R (реакция)

о о x i

о о x n

о о x n +1

Устройство состоит из сетчатки сенсорных элементов S , которые случайным образом соединены с ассоциативными элементами сетчатки A . Каждый элемент второй сетчатки воспроизводит выходной сигнал только в том случае, если достаточное число сенсорных элементов, соединенных с его входом, находятся в возбужденном состоянии. Реакция всей системы R пропорциональна сумме взятых с определенными весами реакций элементов ассоциативной сетчатки.

Обозначив через x i реакцию i -го ассоциативного элемента и через w i - весовой коэффициент реакции i -го ассоциативного элемента, реакцию системы можно записать как R =sum(w j x j ), j =1,..,n . Если R >0, то предъявленный системе образ принадлежит классу A, а если R <0, то образ относится к классу B. Описание этой процедуры классификации соответствует рассмотренным нами раньше принципам классификации, и, очевидно, перцентронная модель распознавания образов представляет собой, за исключением сенсорной сетчатки, реализацию линейной дискриминантной функции. Принятый в перцентроне принцип формирования значений x 1 , x 2 ,...,x n соответствует некоторому алгоритму формирования признаков на основе сигналов первичных датчиков.

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

Схему перцентрона можно распространить на случай, когда число классов более двух, путем увеличения числа элементов сетчатки R до числа различаемых классов и введение блока определения максимальной реакции в соответствии со схемой, представленной на выше приведенном рисунке. При этом образ причисляется к классу с номером i , если R i >R j , для всех j .

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

Рассмотрим алгоритм действия перцентрона на примере распознавания объектов двух классов: A и B. Объектам класса A должно соответствовать значение R = +1, а классу B - значение R = -1.

Алгоритм обучения состоит в следующем.

Если очередной образ x принадлежит классу A, но R <0 (имеет место ошибка распознавания), тогда коэффициенты w j c индексами, которым соответствуют значения x j >0, увеличивают на некоторую величину dw , а остальные коэффициенты w j уменьшают на dw . При этом значение реакции R получает приращение в сторону ее положительных значений, соответствующих правильной классификации.

Если x принадлежит классу B, но R >0 (имеет место ошибка распознавания), то коэффициенты w j с индексами, которым соответствуют x j <0, увеличивают на dw , а остальные коэффициенты w j уменьшают на ту же величину. При этом значение реакции R получает приращение в сторону отрицательных значений, соответствующих правильной классификации.

Алгоритм таким образом вносит изменение в вектор весов w в том и только в том случае, если образ, предъявляемый на k -ом шаге обучения, был при выполнении этого шага неправильно классифицирован, и оставляет вектор весов w без изменений в случае правильной классификации. Доказательство сходимости данного алгоритма представлено в работе [Ту, Гонсалес]. Такое обучение в конечном итоге (при надлежащем выборе dw и линейной разделимости классов образов) приводит к получению вектора w , обеспечивающего правильную классификацию.

Статистические методы распознавания.

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

P = sum[p (i )·prob(D (x )+i | x классу i )]

где m - число классов,

p (i ) = prob (x принадлежит классу i ) - априорная вероятность принадлежности произвольного образа x к i -му классу (частота появления образов i -го класса),

D (x ) - функция, принимающая классификационное решение (вектору признаков x ставит в соответствие номер класса i из множества {1,2,...,m }),

prob(D (x ) не равно i | x принадлежит классу i ) - вероятность события "D (x ) не равно i " при выполнении условия принадлежности x классу i , т.е. вероятность вынесения ошибочного решения функцией D (x ) для данного значения x , принадлежащего i -му классу.

Можно показать, что вероятность неправильной классификации достигает минимума, если D (x )=i в том и только в том случае, если p (x |i )·p (i )>p (x|j )·p (j ), для всех i+j , где p (x|i ) - плотность распределения образов i -го класса в пространстве признаков.

Согласно приведенному правилу точка x относится к тому классу, которому соответствует максимальное значение p (i ) p (x|i ), т.е. произведение априорной вероятности (частоты) появления образов i -го класса и плотности распределения образов i -го класса в пространстве признаков. Представленное правило классификации называется байесовским, т.к. оно следует из известной в теории вероятности формулы Байеса.

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

Каждый входной сигнал представляет собой 0 или 1. В результате передачи сигнала на выходе канала появляется величина x , на которую налагается Гауссовский шум с нулевым средним значением и дисперсией б.

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

В класс №1 объединим сигналы, представляющие единицы, в класс №2 - сигналы, представляющие нули. Пусть заранее известно, что в среднем из каждой 1000 сигналов a сигналов представляют собой единицы и b сигналов - нули. Тогда значения априорных вероятностей появления сигналов 1-го и 2-го классов (единиц и нулей), соответственно можно принять равными

p(1)=a/1000, p(2)=b/1000.

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

p (x ¦1) =(2piб) -1/2 exp(-(x -1) 2 /(2б 2)),

а плотность распределения в зависимости от значения x образов второго класса, т.е. вероятность получения на выходе величины x при подаче на входе сигнала 0 определяется выражением

p (x ¦2)= (2piб) -1/2 exp(-x 2 /(2б 2)),

Применение байесовского решающего правила приводит к выводу, что передан сигнал класса 2, т.е. передан ноль, если

p (2) p (x ¦2) > p (1) p (x ¦1)

или, более конкретно, если

b exp(-x 2 /(2б 2)) > a exp(-(x -1) 2 /(2б 2)),

Поделив левую часть неравенства на правую, получим

(b /a ) exp((1-2 x )/(2б 2)) >1,

откуда после логарифмирования находим

1-2x > 2б 2 ln(a/b)

x < 0.5 - б 2 ln(a/b)

Из полученного неравенства следует, что при a=b , т.е. при одинаковых априорных вероятностях появления сигналов 0 и 1, образу присваивается значение 0 когда x <0.5, а значение 1, когда x >0.5.

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

Так при a/b =2.71 (что соответствует в 2.71 раза более частой передаче единиц) и б 2 =0.1, образу присваивается значение 0, если x <0.4, и значение 1, если x >0.4. Если информация об априорных вероятностях распределения отсутствует, то могут быть использованы статистические методы распознавания, в основу которых положены иные, отличные от байесовского, правила классификации.

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

Лингвистические методы распознавания образов.

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

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

Пример. Пусть заданы три изображения буквы А, полученные в результате предварительной обработки изображений. Обозначим эти изображения идентификаторами А1, А2 и А3.

Для лингвистического описания представленных образов воспользуемся языком PDL (Picture Description Language). Словарь языка PDL включает следующие символы:

1. Имена простейших изображений (примитивов). Применительно к рассматриваемому случаю примитивы и соответствующие им имена следующие.

Изображения в виде линии, направленной:

вверх и влево (leF t), на север(north)), вверх и вправо (right), на восток(east)).

Имена: L, N, R, E .

2. Символы бинарных операций. {+,*,-} Их смысл соответствует последовательному соединению примитивов (+), соединению начал и окончаний примитивов (*), соединению только окончаний примитивов (-).

3. Правую и левую скобки. {(,)} Скобки позволяют определять последовательность выполненияопераций в выражении.

Рассматриваемые изображения А1, А2 и А3 описываются на языке PDL соответственно следующими выражениями.

T(1)=R+((R-(L+N))*E-L

T(2)=(R+N)+((N+R)-L)*E-L

T(3)=(N+R)+(R-L)*E-(L+N)

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

Очевидно, буква А всегда содержит следующие структурные элементы: левую "ножку", правую "ножку" и головную часть. Назовем эти элементы соответственно STL, STR, TR.

Тогда на языке PDL класс символов А - SIMB A описывается выражением

SIMB A = STL + TR - STR

Левая "ножка" STL всегда есть цепочка элементов R и N, что можно записать так

STL ‑> R ¦ N ¦ (STL + R)¦(STL + N)

(STL есть символ R или N, или цепочка, полученная добавлением кисходной цепочке STL символов R или N)

Правая "ножка" STR всегда есть цепочка элементов L и N, что можно записать так, т.е.

STR ‑> L¦N¦ (STR + L)¦(STR + N)

Головная часть буквы - TR представляет собой замкнутый контур, составленный из элемента E и цепочек типа STL и STR.

На языке PDLструктура TR описывается выражением

TR ‑> (STL - STR) * E

Окончательно получим следующее описание класса букв А:

SIMB A ‑> (STL + TR - STR),

STL ‑> R¦N¦ (STL + R)¦(STL + N)

STR ‑> L¦N¦ (STR + L)¦(STR + N)

TR ‑> (STL - STR) * E

Процедура распознавания в данном случае может быть реализована следующим образом.

1. Выражение, соответствующее образу, сравнивается с эталоннойструктурой STL + TR - STR.

2. Каждому элементу структуры STL, TR, STR, если это возможно, т.е. если описание изображения сравнимо с эталоном, ставится в соответствиенекоторое подвыражение из выражения T(А). Например,

для А1: STL=R, STR=L, TR=(R-(L+N))*E

для А2: STL = R + N, STR = L, TR = ((N + R) - L) * E

для А3: STL = N + R, STR = L + N, TR = (R - L) * E 3.

Выражения STL, STR, TR сравниваются с соответствующими им эталонными структурами.

4. Если структура каждого выражения STL, STR, TR соответствует эталонной, делается вывод о принадлежности образа к классу букв А. Если на каком-либо из этапов 2, 3, 4 обнаруживается несоответствие структуры анализируемого выражения эталону, делается вывод о непринадлежности образа классу SIMB A. Сопоставление структур выражений может проводиться с помощью алгоритмических языков LISP, PLANER, PROLOG и других подобных им языков искусственного интеллекта.

В рассматриваемом примере все цепочки STL составлены из символов N и R, а цепочки STR из символов L и N, что соответствует заданной структуре этих цепочек. Структура TR в рассматриваемых образах также соответствует эталонной, т.к. состоит из "разности" цепочек типа STL, STR, "умноженной" на символ E.

Т.о., приходим к выводу о принадлежности рассматриваемых образов классу SIMB A.

Синтез нечеткого регулятора электропривода постоянного тока в среде «MatLab»

Синтез нечеткого регулятора с одним входом и выходом.

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

Рис.4 Обобщенная функциональная схема системы с двумя лингвистическими переменными.

Рис.5 Принципиальная схема нечеткого регулятора с двумя лингвистическими переменными.

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

1. преобразование входных физических переменных, получаемых от измерительных датчиков с объекта управления во входные лингвистические переменные нечеткого регулятора;

2. обработка логических высказываний, называемых лингвистическими правилами, относительно входных и выходных лингвистических переменных регулятора;

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

Рассмотрим сначала самый простой случай, когда для управления следящим электроприводом вводятся всего две лингвистические переменные:

«угол» - входная переменная;

«управляющее воздействие» - выходная переменная.

Синтез регулятора будем осуществлять в среде «MatLab» с помощью тулбокса «Fuzzy Logic». Он позволяет создавать системы нечеткого логического вывода и нечеткой классификации в рамках среды MatLab, с возможностью их интегрирования в Simulink. Базовым понятием Fuzzy Logic Toolbox является FIS-структура - система нечеткого вывода (Fuzzy Inference System). FIS-структура содержит все необходимые данные для реализации функционального отображения “входы-выходы” на основе нечеткого логического вывода согласно схеме, приведенной на рис. 6.

Рисунок 6. Нечеткий логический вывод.

X - входной четкий вектор; - вектор нечетких множеств, соответствующий входному вектору X;
- результат логического вывода в виде вектора нечетких множеств;Y - выходной четкий вектор.

Модуль fuzzy позволяет строить нечеткие системы двух типов - Мамдани и Сугэно. В системах типа Мамдани база знаний состоит из правил вида “Если x 1 =низкий и x 2 =средний, то y=высокий” . В системах типа Сугэно база знаний состоит из правил вида “Если x 1 =низкий и x 2 =средний, то y=a 0 +a 1 x 1 +a 2 x 2 " . Таким образом, основное отличие между системами Мамдани и Сугэно заключается в разных способах задания значений выходной переменной в правилах, образующих базу знаний. В системах типа Мамдани значения выходной переменной задаются нечеткими термами, в системах типа Сугэно - как линейная комбинация входных переменных. В нашем случаем будем использовать систему Сугэно, т.к. она лучше поддается оптимизации.

Для управления следящим электроприводом, вводятся две лингвистические переменные: «ошибка» (по положению) и «управляющее воздействие». Первая из них является входной, вторая – выходная. Определим терм-множество для указанный переменных.

Основные компоненты нечеткого логического вывода. Фаззификатор.

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

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

Рис.7. Лингвистическая переменная «ошибка».

Лингвистическую переменную «управление» удобнее представить в виде таблицы:

Таблица 1

Блок правил .

Рассмотрим последовательность определения нескольких правил, которые описывают некоторые ситуации:

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

Теперь рассмотрим другой случай: ошибка по положению сильно больше нуля. Естественно мы должны её компенсировать, формируя большой положительный сигнал управления.

Т.о. составлены два правила, которые могут быть формально определены так:

если ошибка = нуль, то управляющее воздействие = нуль.

если ошибка = большая положительная, то управляющее воздействие = большое положительное.

Рис.8. Формирование управления при малой положительной ошибке по положению.

Рис.9. Формирование управления при нулевой ошибке по положению.

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

Таблица 2

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

Дефаззификатор.

Таким образом, результирующее воздействие U будет определяться соответственно выполнению какого-либо правила. Если возникает ситуация, когда выполняются сразу несколько правил, то результирующее воздействие U находится по следующей зависимости:

, где n-число сработавших правил (дефаззификация методом центра области), u n – физическое значение управляющего сигнала, сответствующее каждому из нечетких множеств UBO , UMo , U Z , UMp , UB P . m Un(u) – степень принадлежности управляющего сигнала u к соответствующему нечеткому множеству Un={UBO , UMo , U Z , UMp , UB P }. Существуют также и другие методы дефаззификации, когда выходная лингвистическая переменная пропорциональна самомому «сильному» или «слабому» правилу.

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

Рис.10. Структурная схема системы в среде Matlab .

Рис.11. Структурная схема нечеткого регулятора в среде Matlab .

Рис.12. Переходный процесс при единичном ступенчатом воздействии.

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

Анализ характеристик привода с синтезированным алгоритмом управления показывает, что они далеки от оптимальных и хуже, чем при синтезе управления другими методами (слишком большое время регулирования при единичном ступенчатом воздействии и ошибка при гармоническом). Объясняется это тем, что параметры функций принадлежности выбирались достаточно произвольно, а в качестве входов регулятора использовалась только величина ошибки по положению. Естественно ни о какой оптимальности полученного регулятора не может идти и речи. Поэтому актуальной становится задача оптимизации нечеткого регулятора, с целью достижения им максимально возможных показателей качества управления. Т.е. стоит задача оптимизации целевой функции f(a 1 ,a 2 …a n), где a 1 ,a 2 …a n – коэффициенты, определяющие вид и характеристики нечеткого регулятора. Для оптимизации нечеткого регулятора воспользуемся блоком ANFIS из среды Matlab. Также одним из способов улучшения характеристик регулятора может являться увеличение числа его входов. Это сделает регулятор более гибким и улучшит его характеристики. Добавим еще одну входную лингвистическую переменную – скорость изменения входного сигнала (его производную). Соответственно возрастет и число правил. Тогда принципиальная схема регулятора примет вид:

Рис.14 Принципиальная схема нечеткого регулятора с тремя лингвистическими переменными.

Пусть - значение скорости входного сигнала. Базовое терм-множество Тn определим в виде:

Тn={”отрицательная (ВО)”, “нулевая (Z)”, ”положительная (ВР)”}.

Расположение функций принадлежности для всех лингвистических переменных показано на рисунке.

Рис.15. Функции принадлежности лингвистической переменной «ошибка».

Рис.16. Функции принадлежности лингвистической переменной «скорость входного сигнала» .

В связи с добавлением еще одной лингвистической переменной, количество правил возрастет до 3x5=15. Принцип их составления полностью аналогичен рассмотренному выше. Все они приведены в следующей таблице:

Таблица 3

Нечеткий сигнал управления		Ошибка по положению
Скорость

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

Рис.17. Формирование управления при трех лингвистических переменных.

В связи с увеличением числа входов и соответственно самих правил, усложнится и структура нечеткого регулятора.

Рис.18. Структурная схема нечеткого регулятора с двумя входами.

Добавить рисунок

Рис.20. Переходный процесс при гармоническом входном воздействии для модели с нечетким регулятором, содержащим две входные лингвистические переменные.

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

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

Оптимизация нечеткого регулятора.

Рассмотрим использование генетических алгоритмов для оптимизации нечеткого регулятора. Генетические алгоритмы – адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на подобии генетическим процессам биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы.

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

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

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

1. Инициализация начальной популяции – генерация заданного числа решений задачи, с которых начинается процесс оптимизации;

2. Применение операторов кроссовера и мутации;

3. Условия останова – обычно процесс оптимизации продолжают до тех пор, пока не будет найдено решение задачи с заданной точностью, или пока не будет выявлено, что процесс сошелся (т.е. не произошло улучшения решения задачи за последние N поколений).

В среде Matlab генетические алгоритмы представлены отдельным тулбоксом, а также пакетом ANFIS. ANFIS - это аббревиатура Adaptive-Network-Based Fuzzy Inference System - адаптивная сеть нечеткого вывода. ANFIS является одним из первых вариантов гибридных нейро-нечетких сетей - нейронной сети прямого распространения сигнала особого типа. Архитектура нейро-нечеткой сети изоморфна нечеткой базе знаний. В нейро-нечетких сетях используются дифференцируемые реализации треугольных норм (умножение и вероятностное ИЛИ), а также гладкие функции принадлежности. Это позволяет применять для настройки нейро-нечетких сетей быстрые и генетические алгоритмы обучения нейронных сетей, основанные на методе обратного распространения ошибки. Ниже описываются архитектура и правила функционирования каждого слоя ANFIS-сети.

ANFIS реализует систему нечеткого вывода Сугено в виде пятислойной нейронной сети прямого распространения сигнала. Назначение слоев следующее: первый слой - термы входных переменных; второй слой - антецеденты (посылки) нечетких правил; третий слой - нормализация степеней выполнения правил; четвертый слой - заключения правил; пятый слой - агрегирование результата, полученного по различным правилам.

Входы сети в отдельный слой не выделяются. На рис.23 изображена ANFIS-сеть с одной входной переменной («ошибка») и пятью нечеткими правилами. Для лингвистической оценки входной переменной «ошибка» используется 5 термов.

Рис.23. Структура ANFIS -сети.

Введем следующие обозначения, необходимые для дальнейшего изложения:

Пусть - входы сети;

y - выход сети;

Нечеткое правило с порядковым номером r;

m - количество правил,;

Нечеткий терм с функцией принадлежности , применяемый для лингвистической оценки переменной в r-ом правиле (,);

Действительные числа в заключении r-го правила (,).

ANFIS-сеть функционирует следующим образом.

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

,

где a, b и c - настраиваемые параметры функции принадлежности.

Слой 2. Количество узлов второго слоя равно m. Каждый узел этого слоя соответствует одному нечеткому правилу. Узел второго слоя соединен с теми узлами первого слоя, которые формируют антецеденты соответствующего правила. Следовательно, каждый узел второго слоя может принимать от 1 до n входных сигналов. Выходом узла является степень выполнения правила, которая рассчитывается как произведение входных сигналов. Обозначим выходы узлов этого слоя через , .

Слой 3. Количество узлов третьего слоя также равно m. Каждый узел этого слоя рассчитывает относительную степень выполнения нечеткого правила:

Слой 4. Количество узлов четвертого слоя также равно m. Каждый узел соединен с одним узлом третьего слоя а также со всеми входами сети (на рис. 18 связи с входами не показаны). Узел четвертого слоя рассчитывает вклад одного нечеткого правила в выход сети:

Слой 5. Единственный узел этого слоя суммирует вклады всех правил:

.

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

Рис.24. Рабочая область ANFISedit.

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

Рис.25. Желаемый переходный процесс.

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

Таблица 4

Значение ошибки	Значение управления
Значение ошибки	Значение управления
Значение ошибки	Значение управления

Рис.26. Вид обучающей выборки.

Обучение будем проводить на 100 шагах. Этого более чем достаточно для сходимости используемого метода.

Рис.27. Процесс обучения нейросети.

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

Рис.28. График зависимости управления от ошибки поп положению внутри регулятора.

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

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

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

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

Sun, Mar 29, 2015

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

Рассмотрим общие элементы модели классификации.

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

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

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

Под образом будем понимать наименование области в пространстве признаков, в которой отображается множество объектов или явлений материального мира. Признак - количественное описание того или иного свойства исследуемого предмета или явления.

Пространство признаков это N-мерное пространство, определенное для данной задачи распознавания, где N - фиксированное число измеряемых признаков для любых объектов. Вектор из пространства признаков x, соответствующий объекту задачи распознавания это N-мерный вектор с компонентами (x_1,x_2,…,x_N), которые являются значениями признаков для данного объекта.

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

Примерами задач классификации являются:

• распознавание символов;
• распознавание речи;
• установление медицинского диагноза;
• прогноз погоды;
• распознавание лиц
• классификация документов и др.

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

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

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

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

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

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

где d - размерность вектора признака.

Разделяют 3 группы методов распознавания образов:

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

Классификация по ближайшему среднему значению

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

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

где x(i,j)- j-й эталонный признак класса i, n_j- количество эталонных векторов класса i.

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

Трудности возникнут, если классы будут иметь несколько более сложную структуру, например, как на рисунке. В данном случае класс 2 разделен на два непересекающихся участка, которые плохо описываются одним средним значением. Также класс 3 слишком вытянут, образцы 3-го класса с большими значениями координат x_2 ближе к среднему значению 1-го класса, нежели 3-го.

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

Будем учитывать характеристику «разброса» значений класса - σ_i, вдоль каждого координатного направления i. Среднеквадратичное отклонение равно квадратному корню из дисперсии. Шкалированное евклидово расстояние между вектором x и вектором математического ожидания x_c равно

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

Классификация по расстоянию до ближайшего соседа

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

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

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

Кроме того, решение будет лучше, если искать в базе не одного ближайшего соседа, а k. Тогда при k > 1 обеспечивает наилучшую выборку распределения векторов в d-мерном пространстве. Однако эффективное использование значений k зависит от того, имеется ли достаточное количество в каждой области пространства. Если имеется больше двух классов то принять верное решение оказывается сложнее.

Литература

• M. Castrillón, . O. Déniz, . D. Hernández и J. Lorenzo, «A comparison of face and facial feature detectors based on the Viola-Jones general object detection framework,» International Journal of Computer Vision, № 22, pp. 481-494, 2011.
• Y.-Q. Wang, «An Analysis of Viola-Jones Face Detection Algorithm,» IPOL Journal, 2013.
• Л. Шапиро и Д. Стокман, Компьютерное зрение, Бином. Лаборатория знаний, 2006.
• З. Н. Г., Методы распознавания и их применение, Советское радио, 1972.
• Дж. Ту, Р. Гонсалес, Математические принципы распознавания образов, Москва: “Мир” Москва, 1974.
• Khan, H. Abdullah и M. Shamian Bin Zainal, «Efficient eyes and mouth detection algorithm using combination of viola jones and skin color pixel detection» International Journal of Engineering and Applied Sciences, № Vol. 3 № 4, 2013.
• V. Gaede и O. Gunther, «Multidimensional Access Methods,» ACM Computing Surveys, pp. 170-231, 1998.