Разработка программных средств по распознаванию образов

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

Рубрика Программирование, компьютеры и кибернетика
Вид дипломная работа
Язык русский
Дата добавления 20.05.2013
Размер файла 2,3 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

3

Дипломная работа

Разработка программных средств по распознаванию образов

Содержание

ВВЕДЕНИЕ

1. РАСПОЗНАВАНИЕ ОБРАЗОВ: ИДЕИ, ТЕХНОЛОГИИ, ПРОБЛЕМЫ И ПЕРСПЕКТИВЫ

1.1 Теория распознавания образов

1.2 Методики распознавания образов: преимущества и недостатки

1.2.1 Интенсиональные методы

1.2.2 Методы, основанные на оценках плотностей распределения значений признаков

1.2.3 Методы, основанные на предположениях о классе решающих функций

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

1.2.5 Лингвистические (структурные) методы

1.2.6 Экстенсиональные методы

1.2.7 Метод сравнения с прототипом

1.2.8 Метод k ближайших соседей

1.2.9 Алгоритмы вычисления оценок

1.2.10 Коллективы решающих правил

1.3 Проблемы и перспективы распознавания образов

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

2.1 Характеристика предметной области

2.2 Предмет разработки и функциональные требования

2.3 Информационное обеспечение программных средств

3. РАЗРАБОТКА ПРОГРАММНЫХ СРЕДСТВ ПО РАСПОЗНАВАНИЮ ОБРАЗОВ

3.1 Назначение и цель создания

3.2 Требование к программным средствам

3.3 Описание функциональных возможностей и схем диалога

4. ОБОСНОВАНИЕ ЭКОНОМИЧЕСКОЙ ЭФФЕКТИВНОСТИ ПРОЕКТА

4.1 Общие положения

4.2 Методика расчета критериев эффективности

4.3 Расчет затрат на создание и функционирование электронного ресурса дистанционного обучения

4.4 Расчет экономии от функционирования электронного ресурса дистанционного обучения

5 БЕЗОПАСНОСТЬ И ЭКОЛОГИЧНОСТЬ ПРОЕКТА

5.1 Общие положения по безопасности проекта

5.2 Безопасность, эргономика и техническая эстетика рабочего места инженера-программиста

5.3 Создание условий для организации режима труда и отдыха при работе с ПЭВМ

5.4 Экологичность проекта

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

Приложение

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

ВВЕДЕНИЕ

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

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

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

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

Для достижения данной цели необходимо было решить следующие задачи:

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

- провести исследование предметной области и выбрать технологию проектирования;

- разработать программное средство по распознаванию образов;

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

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

- загружать документы в электронном виде различных форматов;

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

- выполнять определенные пользователем действия за установленное количество этапов (проходов);

- сохранять полученное изображение (образ) в новом виде.

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

1. РАСПОЗНАВАНИЕ ОБРАЗОВ: ИДЕИ, ТЕХНОЛОГИИ, ПРОБЛЕМЫ И ПЕРСПЕКТИВЫ

1.1 Теория распознавания образов

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

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

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

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

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

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

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

В основной задаче распознавания образа о построении решающих функций D используются закономерные связи между характеристиками Х и S, обнаруживаемые на обучающей выборке, и некоторые дополнительные априорные предположения, например следующие гипотезы: характеристики Х для реализаций образов представляют собой случайные выборки из генеральных совокупностей с нормальным распределением; реализации одного образа расположены «компактно» (в некотором смысле); признаки в наборе Х независимы и т.д.

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

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

Предположим, что известны n1 наблюдений из генеральной совокупности A1, n2 наблюдений из генеральной совокупности А2 и т.д., nm наблюдений из генеральной совокупности Am, m ? 2. Дана также выборка z = (z1, ..., zn). Задача Р. о. состоит в определении, какой из генеральных совокупностей Aj, j = 1, 2,..., m, принадлежит выборка z. При этом обычно принимается предположение о том, что распределения P (•) совокупностей Aj принадлежат некоторому семейству {P (И, *)} распределений, зависящих от векторного параметра И, так что Pj (*) = Р j,•), где Иj неизвестны.

Если заданы потери Lij, которые несёт наблюдатель, относя выборку 2 к совокупности (образу) Aj, когда она на самом деле принадлежит Ai, то сформулированная задача может рассматриваться и решаться с помощью методов теории статистических игр [стратегией природы здесь является набор (И1, ..., Иm, j), где j указывает номер совокупности, к которой относится z]. В этом случае возможно отыскание оптимальных «решающих функций», минимизирующих в том или ином смысле потери наблюдателя.

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

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

1.2 Методики распознавания образов: преимущества и недостатки

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

Основная типология методов распознавания образов:

- методы, основанные на принципе разделения;

- статистические методы;

- методы, построенные на основе «потенциальных функций»;

- методы вычисления оценок (голосования);

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

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

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

Выделяют два основных способа представления знаний:

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

- экстенсиональное, с помощью конкретных фактов (объекты, примеры).

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

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

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

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

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

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

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

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

1.2.1 Интенсиональные методы

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

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

1.2.2 Методы, основанные на оценках плотностей распределения значений признаков

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

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

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

1.2.3 Методы, основанные на предположениях о классе решающих функций

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

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

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

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

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

Логические методы распознавания образов базируются на аппарате алгебры логики и позволяют оперировать информацией, заключенной не только в отдельных признаках, но и в сочетаниях значений признаков. В этих методах значения какого-либо признака рассматриваются как элементарные события [104].

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

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

1.2.5 Лингвистические (структурные) методы

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

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

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

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

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

1.2.6 Экстенсиональные методы

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

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

1.2.7 Метод сравнения с прототипом

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

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

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

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

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

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

1.2.8 Метод k ближайших соседей

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

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

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

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

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

1.2.9 Алгоритмы вычисления оценок

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

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

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

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

- правила вычисления близости объектов по отдельным признакам;

- правила вычисления близости объектов в подпространствах признаков;

- степень важности того или иного эталонного объекта как диагностического прецедента;

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

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

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

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

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

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

1.2.10 Коллективы решающих правил

В завершение обзора методов распознавания образов остановимся еще на одном подходе. Это так называемые коллективы решающих правил (КРП).

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

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

Сравним описанные выше методы распознавания образов и оценим степень их адекватности сформулированным в разделе 3.3.3 требованиям к моделям СОУ для адаптивных АСУ сложными системами.

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

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

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

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

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

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

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

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

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

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

Это задачи:

- определения информационного вклада признаков в информационный портрет обобщенного образа;

- кластерно-конструктивный анализ обобщенных образов;

- определение семантической нагрузки признака;

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

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

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

- классификация методов распознавания;

- области применения методов распознавания;

- классификация ограничений методов распознавания.

Таблица 1.1 Сводная таблица классификации методов распознавания, сравнения их областей применения и ограничений

Классификация методов распознавания

Область применения

Ограничения (недостатки)

Интенсиальные методы распознавания

Методы, основанные на оценках плотностей распределения значений признаков (или сходства и различия объектов)

Задачи с известным распределением, как правило, нормальным, необходимость набора большой статистики

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

Методы, основанные на предположениях о классе решающих функций

Классы должны быть хорошо разделяемыми, система признаков -- ортонормированной

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

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

Задачи небольшой размерности пространства признаков

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

Лингвистические (структурные) методы

Задачи небольшой размерности пространства признаков

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

Экстенсиальные методы распознавания

Метод сравнения с прототипом

Задачи небольшой размерности пространства признаков

Высокая зависимость результатов классификации от меры расстояния (метрики). Неизвестность оптимальной метрики

Метод k ближайших соседей

Задачи небольшой размерности по количеству классов и признаков

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

Алгоритмы вычисления оценок (голосования) АВО

Задачи небольшой размерности по количеству классов и признаков

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

Коллективы решающих правил (КРП)

Задачи небольшой размерности по количеству классов и признаков

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

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

1.3 Проблемы и перспективы распознавания образов

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

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

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


Подобные документы

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

    лабораторная работа [1,4 M], добавлен 28.11.2021

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

    дипломная работа [1,1 M], добавлен 13.12.2013

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

    дипломная работа [554,8 K], добавлен 06.04.2014

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

    реферат [26,7 K], добавлен 10.10.2014

  • Нормативные и правовые акты, регламентирующие применение современных программных средств в документационном обеспечении управления в Российской Федерации. Анализ программных средств для внедрения системы электронного документооборота в ООО "СЛМ-Монтаж".

    дипломная работа [163,2 K], добавлен 10.05.2015

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

    дипломная работа [2,4 M], добавлен 07.02.2013

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

    дипломная работа [1,5 M], добавлен 10.06.2013

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

    курсовая работа [462,2 K], добавлен 15.01.2014

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

    курсовая работа [645,2 K], добавлен 05.04.2015

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

    лекция [352,8 K], добавлен 09.03.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.