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

Методы распознавания образов. Часть 1 · Dmitriy Azarov

Математические методы распознавания образов
Sun, Mar 29, 2015

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

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

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

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

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

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

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

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

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

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

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

Если рассмотреть 2 класса объектов: взрослые и дети. В качестве признаков можно выбрать рост и вес.

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

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

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

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

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

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

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

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

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

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

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

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

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

Далее рассмотрим различные методы относящиеся к разным группам.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

Источник: https://oxozle.com/2015/03/29/metody-raspoznavaniya-obrazov-chast-1/

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

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

Худайберганов Т. Р., Адинаев Х. С., Артикбаев М. А. Математические методы распознавания образов // Техника. Технологии. Инженерия. — 2017. — №2.1. — С. 45-47. — URL https://moluch.ru/th/8/archive/57/2318/ (дата обращения: 02.03.2020).



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

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

Annotation: This article is written on the mathematical methods of pattern recognition, efficiency and improving recognition. Also, there is a speech about the role of information technologies and their achievements. These advantages of the Bayesian approach and perceptron algorithm.

Keywords: information and communication technologies, resources, portal, e-learning, multimedia presentations, animations, static images, dynamic images, global, mapping, modeling, differential training, individual training, distance learning.

Распознавание образов – это научная дисциплина, целью которой является классификация объектов по нескольким категориям или классам. Объекты называются образами. [1,38]

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

https://www.youtube.com/watch?v=EBnQ_6U8bxE

Задача распознавания образов является основной в большинстве интеллектуальных систем. Рассмотрим примеры интеллектуальных компьютерных систем. [2,124]

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

2. Символьное распознавание – это распознавание букв или цифр.

a. Optical Character Recognition (OCR);

b. Ввод и хранение документов;

c. Pen Computer;

d. Обработка чеков в банках;

e. Обработка почты.

3. Диагностика в медицине.

a. Маммография, рентгенография;

b. Постановка диагноза по истории болезни;

c. Электрокардиограмма.

4. Геология.

5. Распознавание речи.

6. Распознавание в дактилоскопии (отпечатки пальцев), распознавание лица, подписи, жестов.

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

Будем использовать следующую модель задачи классификации. Ω — множество объектов распознавания (пространство образов). : Ω — объект распознавания (образ). g() — Ω  M, M={1,2,…,m} — индикаторная функция, разбивающая пространство образов на Ω на m непересекающихся классов Ω1, Ω2 ,…,Ωm. Индикаторная функция неизвестна наблюдателю.

X — пространство наблюдений, воспринимаемых наблюдателем (пространство признаков). x(): Ω  X – функция, ставящая в соответствие каждому объекту  точку х() в пространстве признаков.

Вектор х() — это образ объекта, воспринимаемый наблюдателем. В пространстве признаков определены непересекающиеся множества точек KiX, i = 1,2,…, m, соответствующих образам одного класса.

g(x): X  M — решающее правило – оценка для g() на основании x(), то есть g(x)= g(x()).

Пусть хj = x(j), j = 1,2,…, N – доступная наблюдателю информация о функциях g() и x()но сами эти функции наблюдателю неизвестны. Тогда (gj,,xj), j = 1,2,…,мN – есть множество прецедентов.

задача заключается в построении такого решающего правила g(x), чтобы распознавание проводилось с минимальным числом ошибок. Обычный случай – считать пространство признаков евклидовым, т.е. Х = R1. Качество решающего правила измеряют частотой появления правильных решений.

Обычно его оценивают, наделяя множество объектов Ω некоторой вероятностной мерой. Тогда задача записывается в виде minP{ g(x())≠g()}.[4,98]

Классификация на основе байесовской теории решений.

Байесовский подход исходит из статистической природы наблюдений.

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

Цель состоит в разработке такого классификатора, который будет правильно определять наиболее вероятный класс для пробного образа. Тогда задача состоит в определении “наиболее вероятного” класса.

Задано М классов Ω1, Ω2,…, ΩM , а также P (Ωi|x), i=1,2,…,M вероятность того, что неизвестный образ, представляемый вектором признаков x, принадлежит классу Ωi P (Ωi|x) называется апостериорной вероятностью, поскольку задает распределение индекса класса после эксперимента (a posteriori – т.е. после того, как значение вектора признаков x было получено).

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

Такое правило классификации по максимуму апостериорной вероятности называется Байесовским: если P (Ω1|x)> P (Ω2|x), то х классифицируется в Ω1, иначе в Ω2.

Таким образом, для Байесовского решающего правила необходимо получить апостериорные вероятности P (Ωi|x), i=1,2. Это можно сделать с помощью формулы Байеса.[3,62]

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

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

после предъявления последнего снова предъявляется первый. Процесс обучения заканчивается, когда нейрон правильно классифицирует все прецеденты. Обозначим Wt весовой вектор после t-й итерации, а xt – прецедент, предъявляемый на t-й итерации.

Основной шаг алгоритма состоит в предъявлении прецедента очередного прецедента очередного прецедента xi+1.

На данном рисунке gt (x) — дискриминантная функция после t — го шага алгоритма; Wt — весовой вектор после t-го шага алгоритма.[4]

Таким образом, задача заключается в построении линейного классификатора в (l+1)M — мерном пространстве так, чтобы каждый из (M — 1)N векторов-прецедентов лежал в положительном полупространстве. Если вектора в исходной задаче разделимы, то это можно сделать с помощью алгоритма персептрона.

Литература:

  1. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. Стохастические проблемы обучения. – М.: Наука, 1974.
  2. Владимиров В.С. Уравнения математической физики. – М.: Наука, 1988.
  3. Вероятность и математическая статистика: Энциклопедия / Под ред. Ю.В. Прохорова. – М.: Большая российская энциклопедия, 2003.
  4. Воронцов К.В. Математические методы обучения по прецедентам. Курс лекций (ФУПМ, МФТИ). – www.ccas.ru/voron/teaching.html.
  5. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. – М.: Мир, 1985.

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

Анализ методов распознавания образов | Статья в журнале… Метод 4. Байесовскийподход к принятию решения.

Согласно теореме Байеса [5] вероятность принадлежности высказывания d классу c выражается следующим образом.

Рис. 2. Евклидово пространствопризнаков двух классов. Таким образом — первая проблема распознавания

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

Чтобы ограничить пространстворешений в соответствии с априорными знаниями в данной статье мы описываем метод максимума апостериорнойвероятности (MAP)

Это может быть вычислено следующим образом. (1.3). Применяя правилоБайеса, уравнение (1.3) примет вид.

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

Метод опорных векторов (SVM) предложен Vapnik [8]. SVM преобразует входной вектор в многомерное пространствопризнаков, а затем получает…

Байесовской сетью (БС) является графическая модель, отображающая вероятностные

Таким образом, количество ячеек в ТУВ дискретной вершины БС равно произведению

При этом количественная оценка апостериорныхвероятностейвозможных диагнозов может…

Таким образом, данные разделены на K кластеров.

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

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

https://www.youtube.com/watch?v=hMd7MyR03Es

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

Анализ методов распознавания образов | Статья в журнале… Примером этой группы служит байесовскийметод принятия решения.

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

Задача построения решающегоправила в условиях полной апостериорной неопределенности достаточно проблематична.

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

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

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

Источник: https://moluch.ru/th/8/archive/57/2318/

Biz-books
Добавить комментарий