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

Обновлено: 30.06.2024

Приняла: кандитдат технических наук , доцент Джаманбаев М.А.

Образ, класс — классификационная группировка в системе классификации, объединяющая (выделяющая) определенную группу объектов по некоторому признаку.

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

– формирование конкретных образов объектов и обобщенных образов классов;

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

– самообучение, т.е. формирование кластеров объектов на основе анализа неклассифицированной обучающей выборки;

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

– измерение степени адекватности модели;

– решение обратной задачи идентификации и прогнозирования (обеспечивается не всеми моделями).

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

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

В литературе, посвященной проблеме обучения распознавания образов (ОРО), часто вместо понятия образа вводится понятие класса.

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

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

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

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

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

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

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

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

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

Такой интегральный критерий предложен в математической модели системно-когнитивного анализа и реализован в системе "Эйдос".

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

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

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

Поэтому этот процесс реализуется в три этапа:

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

2. Присвоение кластерам статуса обобщенных классов, для формирования обобщенных образов которых используются конкретные объекты, входящие именно в эти кластеры.

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

Как только произнесено или написано слово "модель", сразу неизбежно возникает вопрос о степени ее адекватности.

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

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

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

Интегральная валидность – это средневзвешенная достоверность идентификации по всем классам и распознаваемым объектам.

Дифференциальная валидность – это способность модели верно идентифицировать объекты в разрезе по классам.

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

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

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

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

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

Рисунок 1- Проблема распознования образов

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

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

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

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

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

В результате обучения распознающая система должна приобрести способность:

1. Относить объекты к классам, к которым они принадлежат (идентифицировать объекты верно).

2. Не относить объекты к классам, к которым они не принадлежат (неидентифицировать объекты ошибочно).

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

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

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

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

Файлы: 1 файл

сема мпт.doc

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

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

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

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

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

Аудитория социальных сетей растёт гиганскими темпами. Согласно результатам исследования ComScore, в мае 2009 года аудитория пользователей одной только Facebook в США насчитывала 70,28 млн человек. И это практически в два раза выше аналогичного показателя за май 2008 года.

Работа инженера будет заключаться в том, чтобы организовать процесс передачи пользователям нераспознанных визуальных или звуковых образов в виде MMS, поп-апов на сайтах, символов CAPTCHA на формах в блогах и др., верификации полученных данных и отправке распознанного слова или образа обратно системе ИИ [6, c. 487].

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

2. Горбань А., Россиев Д. Нейронные сети на персональном компьютере. //Новосибирск, Наука, 1996. – C 114 – 119.

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

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

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

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

7. Минский М., Пейперт С. Персептроны. - М.: Мир, 2007. - 261 с.

8. Растригин Л. А., Эренштейн Р. Х. Метод коллективного распознавания. 79 с. ил. 20 см., М. Энергоиздат, 2006. – 80 с.

9. Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации // Распознавание, классификация, прогноз. Математические методы и их применение. Вып. 1. - М.: Наука, 2007. - С. 176-200.

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

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

1. Задача распознавания

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

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

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

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

1.1 Основные понятия и определения

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

которые называются классами объектов. Над каждым объектом А производится N измерений, результаты которых называются признаками данного объекта. Таким образом, каждый объект изображается вектором признаков в N-мерном пространстве, которое называется пространством признаков.

На вход распознающей системы поступает последовательность векторов признаков соответствующих набору объектов А1, …, Аn,… из . Последовательность (1.1) называется обучающей последовательностью, или обучающей выборкой.

Задача распознавания может быть в общем виде сформулирована следующим образом: необходимо по обучающей выборке построить решающее правило, то есть правило, которое для любого объекта А (возможно, не совпадающего ни с одним из А1, …, Аn) позволяло бы на основе вектора х(А) указать, какому из классов принадлежит объект А.

Постановку задачи можно еще более детализировать, рассматривая отдельно три случая: детерминированная задача распознавания, вероятностная задача распознавания и самообучение (автоматическая классификация). Остановимся подробнее на вероятностной задаче распознавания.

1.2 Вероятностная задача распознавания

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

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

Очевидно, распределение случайной величины будет иметь плотность:

(этот факт следует из формулы полной вероятности).

Байесовским решающим правилом называется решающее правило, минимизирующее средний риск отнесения объектов k-го класса в i-й класс.

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

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

Тогда оптимальное разбиение состоит из множеств:

что соответствует решающему правилу: х относится к если

для всех (1.2)

Итак, мы имеем вид решающего правила, минимизирующего функционал среднего риска.

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

- оценивание плотностей распределения,

- непосредственное восстановление параметров оптимального решающего правила.

Рассмотрим в отдельности оценивание плотностей распределения.

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

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

2.1 Основные понятия, определения, теоремы

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

Пусть - повторная выборка с плотностью p(x). Парзеновская оценка плотности p(x) есть функция

, (2.1)

где k(y) – некоторая заданная функция, называемая ядром оценки (2.1), - неотрицательная числовая последовательность.

Если ядро k(y) удовлетворяет условиям

то (2.1) есть плотность распределения.

Докажем следующие теоремы:

Пусть выполнены условия на ядро k и :

Если функция p(x) непрерывна в точке х, то

геометрический распознавание непараметрический парзеновский

Разобьем здесь область интегрирования на два множества и - произвольное положительное число.

Первое слагаемое не превосходит величины

а второе не превосходит

Отсюда следует, что

Устремляя n к бесконечности, получаем в силу условий (2.2)-(2.4) получаем:

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

Пусть х – точка непрерывности плотности p(x) и выполнены условия теоремы (2.1). тогда - асимптотически несмещенная оценка величины p(x), то есть

Если, кроме того

то - состоятельная оценка, то есть

Соотношение (2.5) непосредственно следует из теоремы (1).

второе слагаемое в правой части стремиться к нулю при .

;

а так как - независимые одинаково распределенные случайные величины, то

Так как функция удовлетворяет условиям теоремы (2.1), то

При N=1 следующие функции удовлетворяют условиям (2.7)

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

где x – вектор с компонентами . Условия (2.4), (2.6) выполнены для последовательностей вида

где а – некоторая константа.

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

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

Работа выполняется в пакете Microsoft Excel, так как этот пакет один из наиболее пригодных для решения подобных задач.

На интервале [-4;9] с шагом 0,2 построим графическое изображение истинного значения плотности распределения по заданной нам функции при .

Полученный результат представлен на рис. 1:

Рис. 1. График заданной плотности распределения

Для оценивания ее строим повторную (обучающую) выборку, соответствующую данной плотности распределения. В качестве ядра k(y) выберем функцию

Проверим, удовлетворяет ли при N=1 функция условиям теорем (2.1) и (2.2).

(a)

где а – некоторая константа,

(b) ,

(c)

(d) Функция непрерывна во всех точках х,

(e) .

Таким образом, условия теорем выполнены, и оценка является асимптотически несмещенной оценкой величины p(x) (в силу условий (а)-(d)), то есть

и состоятельной оценкой (в силу условий (а)-(е)), то есть

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

Рис. 2. График сравнения оценки плотности распределения с ее истинным значением при

Рис. 3. График сравнения оценки плотности распределения с ее истинным значением при

Рис. 4. График сравнения оценки плотности распределения с ее истинным значением при

Рис. 5. График сравнения оценки плотности распределения с ее истинным значением при

Наиболее удачная оценка получается при (см. рис. 6)

Рис. 6. График сравнения оценки плотности распределения с ее истинным значением при

Также вид оценки зависит от повторной выборки. Графики, полученные при изменении значений обучающей выборки при неизменном представленны на рис. 6-8.

Рис. 7. График сравнения оценки плотности распределения с ее истинным значением для повторной выборки (1)

Рис. 8. График сравнения оценки плотности распределения с ее истинным значением для повторной выборки (2)

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

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

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

3. Булдаков В. М., Кошкин Г. М. Рекуррентное оценивание условной плотности вероятности и линии регрессии по зависимой выборке. Материалы V научн. конф. По математике, I. Томск, 1974, 135-136.

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

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

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

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

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

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

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

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

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

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

Существующие классические методы фильтрации могут быть применены в широком спектре задач. Наиболее распространенным классическим методом является преобразование Фурье, однако он не используется в изображениях в чистом виде [3,4]. Однако для анализа изображений часто бывает недостаточно простого одномерного преобразования, и требуется гораздо более ресурсоемкое двумерное преобразование:

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

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

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

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

С математической точки зрения изображение является двумерной матрицей значений яркости. Однако при переходе от одной его части к другой, даже такие статистики первого порядка, как гистограммы значительно меняются. Существует набор классических функций, применяемых в вейвлет преобразованиях [5]: вейвлет Хаара, вейвлет Морле, вейвлет Добеши и т.д. Хорошим примером применения вейвлет анализа является задача поиска блика в зрачке глаза, где вейвлетом является сам блик.

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

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

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

Рассмотренные фильтры могут решить большинство задач, однако не стоит забывать о менее распространенных, но используемых в локальных задачах [6]: итерационные фильтры, курвлет и бамблет преобразования и т.д.

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

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

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

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

Вудс Р., Гонсалес Р. Цифровая обработка изображений //М.: Техносфера. — 2005.
Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB //М.: Техносфера. — 2006. — Т. 616. — С. 6.
Дж Т., Гонсалес Р. Принципы распознавания образов. — 1978.
Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. Статистические проблемы обучения. — 1974.
Дремин И. М., Иванов О. В., Нечитайло В. А. Вейвлеты и их использование //Успехи физических наук. — 2001. — Т. 171. — № . 5. — С. 465-501.
Шапиро Л., Стокман Д. Компьютерное зрение //М.: Бином. Лаборатория знаний. — 2006. — Т. 752.

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

1. Задача распознавания

1.1 Основные понятия и определения

1.2 Вероятностная задача распознавания

Очевидно, распределение случайной величины будет иметь плотность:

(этот факт следует из формулы полной вероятности).

Тогда оптимальное разбиение состоит из множеств:

что соответствует решающему правилу: х относится к если

Итак, мы имеем вид решающего правила, минимизирующего функционал среднего риска.

оценивание плотностей распределения,

непосредственное восстановление параметров оптимального решающего правила.

Рассмотрим в отдельности оценивание плотностей распределения.

2. Непараметрические парзеновские оценки плотностей

2.1 Основные понятия, определения, теоремы

Пусть - повторная выборка с плотностью p(x). Парзеновская оценка плотности p(x) есть функция

Если ядро k(y) удовлетворяет условиям

то (2.1) есть плотность распределения.

Докажем следующие теоремы:

Пусть выполнены условия на ядро k и :

Если функция p(x) непрерывна в точке х, то

геометрический распознавание непараметрический парзеновский

Разобьем здесь область интегрирования на два множества и - произвольное положительное число.

Первое слагаемое не превосходит величины

а второе не превосходит

Отсюда следует, что

Устремляя n к бесконечности, получаем в силу условий (2.2)-(2.4) получаем:

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

Если, кроме того

то - состоятельная оценка, то есть

Соотношение (2.5) непосредственно следует из теоремы (1).

второе слагаемое в правой части стремиться к нулю при .

а так как - независимые одинаково распределенные случайные величины, то

Так как функция удовлетворяет условиям теоремы (2.1), то

При N=1 следующие функции удовлетворяют условиям (2.7)

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

где x – вектор с компонентами . Условия (2.4), (2.6) выполнены для последовательностей вида

где а – некоторая константа.

2.2 Исследование парзеновских оценок плотностей на практике

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

Полученный результат представлен на рис. 1:

Рис. 1. График заданной плотности распределения

Проверим, удовлетворяет ли при N=1 функция условиям теорем (2.1) и (2.2).

где а – некоторая константа,

Функция непрерывна во всех точках х,

и состоятельной оценкой (в силу условий (а)-(е)), то есть

Рис. 2. График сравнения оценки плотности распределения с ее истинным значением при

Рис. 3. График сравнения оценки плотности распределения с ее истинным значением при

Рис. 4. График сравнения оценки плотности распределения с ее истинным значением при

Рис. 5. График сравнения оценки плотности распределения с ее истинным значением при

Наиболее удачная оценка получается при (см. рис. 6)

Рис. 6. График сравнения оценки плотности распределения с ее истинным значением при

Рис. 7. График сравнения оценки плотности распределения с ее истинным значением для повторной выборки (1)

Рис. 8. График сравнения оценки плотности распределения с ее истинным значением для повторной выборки (2)

Список литературы

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

Булдаков В. М., Кошкин Г. М. Рекуррентное оценивание условной плотности вероятности и линии регрессии по зависимой выборке. Материалы V научн. конф. По математике, I. Томск, 1974, 135-136.

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

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

Читайте также: