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

Методы автоматического распознавания образов и их реализация в системах оптического распознавания текстов (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. Это информационные задачи, состоящие из двух этапов:

a. Приведение исходных данных к виду, удобному для распознавания.

b. Собственно распознавание – указание принадлежности объекта определенному классу.

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

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

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

5. В этих задачах возможна «плохая информация» - информация с пропусками, разнородная, косвенная, нечеткая, неоднозначная, вероятностная.

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

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

2. Задача автоматической классификации – разбиение множества объектов (ситуаций) по их описаниям на систему непересекающихся классов (таксономия, кластерный анализ, обучение без учителя).

3. Задача выбора информативного набора признаков при распознавании.

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

5. Динамическое распознавание и динамическая классификация – задачи 1 и 2 для динамических объектов.

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

Понятие образа.

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

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

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

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

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

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

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

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

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

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

Геометрический и структурный подходы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Гипотеза компактности.

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

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

Сама гипотеза компактности превратилась в признак возможности удовлетворительно решения задач распознавания.

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

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

Обучение и самообучение, адаптация и обучение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Более сложной задачей является задача понимания речи, которая сопряжена с выявлением смысла акустического сигнала. В этом случае выход подсистемы распознавания речи служит входом подсистемы понимания высказываний. Автоматическое распознавание речи (системы АРР) является одним из направлений технологий обработки естественного языка.

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

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

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

Одним из основных параметров является ошибка распознавания слов (ОРС). Этот параметр представляет собой отношение количества нераспознанных слов к общему количеству произнесенных слов.

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

1) размер словаря,

2) режим речи,

3) стиль речи,

4) предметная область,

5) дикторозависимость,

6) уровень акустических шумов,

7) качество входного канала.

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

С малым размером словаря (до 100 слов),

Со средним размером словаря (от 100 слов до нескольких тысяч слов),

С большим размером словаря (более 10 000 слов).

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

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

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

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

Многие системы автоматического распознавания речи являются дикторозависимыми. Это предполагает предварительную настройку системы на особенности произношения конкретного диктора.

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

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

Во-вторых, положением и характеристиками акустических приемников.

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

На рисунке представлены основные компоненты системы распознавания речи:

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

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

Синтез речи по тексту. Основные понятия

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

Рисунок 1.

Кусок лекций взять у Олега

Рассмотрим особенности эмпирического подхода на примере распознавания частей речи. Задача состоит в присвоении словам предложения меток: существительное, глагол, предлог, прилагательное и тому подобное. Кроме этого, необходимо определять некоторые дополнительные признаки существительных и глаголов. Например, для существительного – число, а для глагола – форму. Формализуем задачу.

Представим предложение в виде последовательности слов: W=w1 w2…wn, где wn – случайные переменные, каждая из которых получает одно из возможных значений, принадлежащих словарю языка. Последовательность меток, назначаемых словам предложения, представим последовательностью X=x1 x2 … xn, где xn – случайные переменные, значения которых определены на множестве возможных меток.

Тогда задача распознавания частей речи состоит в поиске наиболее вероятной последовательности меток x1, x2, …, xn по заданной последовательности слов w1, w2, …, wn. Иными словами, необходимо найти такую последовательность меток X*=x1 x2 … xn, которая обеспечивает максимум условной вероятности P(x1, x2, …, xn| w1 w2.. wn).

Перепишем условную вероятность P(X| W) в следующем виде P(X| W)=P(X,W) / P(W). Так как требуется найти максимум условной вероятности P(X,W) по переменной X, получим X*=arg x max P(X,W). Совместную вероятность P(X,W) можно записать в виде произведения условных вероятностей: P(X,W)=произведение по и-1 до н от P(x i |x1,…,x i -1 , w1,…,w i -1) P(w i |x1,…,x i -1 , w1,…,w i -1). Непосредственный поиск максимума данного выражения представляет собой сложную задачу, так как при больших значениях n поисковое пространство становится очень большим. Поэтому вероятности, которые записаны в этом произведении, аппроксимируют более простыми условными вероятностями: P(x i |x i -1) P(w i |w i -1). В этом случае полагают, что значение метки x i связано только с предыдущей меткой x i -1 и не зависит от более ранних меток, а также что вероятность слова w i определяется только текущей меткой x i . Указанные предположения называют марковскими, а для решения задачи привлекают теорию марковских моделей. С учетом марковских предположений можно записать:

X*= arg x1, …, xn max П i =1 n P(x i |x i -1) P(wi|wi-1)

Где условные вероятности оцениваются на множестве обучающих данных

Поиск последовательности меток Х* осуществляют с помощью алгоритма динамического программирования Витерби. Алгоритм Витерби может рассматриваться как вариант алгоритма поиска на графе состояний, где вершинам соответствуют метки слов.

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

Так, при наличии 200 меток точность назначения примерно равна 97%. Долгое время имперический анализ выполнялся с помощью стохастических контекстно-свободных грамматик. Однако для них характерен существенный недостаток. Он заключается в том, что различным грамматическим разборам могут назначаться одинаковые вероятности. Это происходит из-за того, что вероятность грамматического разбора представляется в виде произведения вероятностей правил, участвующих в разборе. Если в ходе разбора используются различные правила, характеризуемые одинаковыми вероятностями, то это и порождает указанную проблему. Лучшие результаты дает грамматика, учитывающая лексику языка.

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

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

Лекция № 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. Сигнал ошибки при гармоническом входном воздействии для модели с нечетким регулятором, содержащим две входные лингвистические переменные.

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

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

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

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

Рис. 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).

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

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

Традиционно задачи распознавания образов включают в круг задач искусственного интеллекта .

Направления в распознавании образов

Можно выделить два основных направления :

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

Формальная постановка задачи

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

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

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

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

Методы распознавания образов

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

Второй подход - найти контур объекта и исследовать его свойства (связность, наличие углов и т. д.)

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

Перцептрон как метод распознавания образов

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

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

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

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

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

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

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

Программы распознавания образов

См. также

Примечания

Ссылки

• Юрий Лифшиц. Курс «Современные задачи теоретической информатики» - лекции по статистическим методам распознавания образов, распознаванию лиц, классификации текстов
• Journal of Pattern Recognition Research (Журнал исследования распознавания образов)

Литература

• Дэвид А. Форсайт, Джин Понс Компьютерное зрение. Современный подход = Computer Vision: A Modern Approach. - М.: «Вильямс» , 2004. - С. 928. - ISBN 0-13-085198-1
• Джордж Стокман, Линда Шапиро Компьютерное зрение = Computer Vision. - М.: Бином. Лаборатория знаний, 2006. - С. 752. - ISBN 5947743841

• А.Л.Горелик, В.А.Скрипкин , Методы распознавания, М.: Высшая школа, 1989.
• Ш.-К. Чэн , Принципы проектирования систем визуальной информации, М.: Мир, 1994.

Wikimedia Foundation . 2010 .

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

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

Англ. recognition, image; нем. Gestalt alterkennung. Раздел математической кибернетики, разрабатывающий принципы и методы классификации и идентификации объектов, описываемых конечным набором признаков, характеризующих их. Antinazi. Энциклопедия… … Энциклопедия социологии

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

- (техн.), научно техническое направление, связанное с разработкой методов и построением систем (в том числе на базе ЭВМ) для установления принадлежности некоторого объекта (предмета, процесса, явления, ситуации, сигнала) к одному из заранее… … Энциклопедический словарь

РАСПОЗНАВАНИЕ ОБРАЗОВ - раздел математической кибернетики, разрабатывающий и методы классификации, а также идентификации предметов, явлений, процессов, сигналов, ситуаций всех тех объектов, к рые могут быть описаны конечным набором нек рых признаков или свойств,… … Российская социологическая энциклопедия

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