Sun, Mar 29, 2015

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

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

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

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

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

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

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

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

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Tutorial

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

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

Эта статья задумана для того, чтобы человек, который никогда не занимался методами распознавания изображений, смог в течении 10-15 минут создать у себя в голове некую базовую картину мира, соответствующую тематике, и понять в какую сторону ему копать. Многие методы, которые тут описаны, применимы к радиолокации и аудио-обработке.
Начну с пары принципов, которые мы всегда начинаем рассказывать потенциальному заказчику, или человеку, который хочет начать заниматься Optical Recognition:

• При решении задачи всегда идти от простейшего. Гораздо проще повесить на персону метку оранжевого цвета, чем следить за человеком, выделяя его каскадами. Гораздо проще взять камеру с большим разрешением, чем разрабатывать сверхразрешающий алгоритм.
• Строгая постановка задачи в методах оптического распознавания на порядки важнее, чем в задачах системного программирования: одно лишнее слово в ТЗ может добавить 50% работы.
• В задачах распознавания нет универсальных решений. Нельзя сделать алгоритм, который будет просто «распознавать любую надпись». Табличка на улице и лист текста - это принципиально разные объекты. Наверное, можно сделать общий алгоритм(вот хороший пример от гугла), но это будет требовать огромного труда большой команды и состоять из десятков различных подпрограмм.
• OpenCV - это библия, в которой есть множество методов, и с помощью которой можно решить 50% от объёма почти любой задачи, но OpenCV - это лишь малая часть того, что в реальности можно сделать. В одном исследовании в выводах было написано: «Задача не решается методами OpenCV, следовательно, она неразрешима». Старайтесь избегать такого, не лениться и трезво оценивать текущую задачу каждый раз с нуля, не используя OpenCV-шаблоны.

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

Список приведённых тут методов не полон. Предлагаю в комментариях добавлять критические методы, которые я не написал и приписывать каждому по 2-3 сопроводительных слова.

Часть 1. Фильтрация

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

Бинаризация по порогу, выбор области гистограммы

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




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

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

Классическая фильтрация: Фурье, ФНЧ, ФВЧ

Классические методы фильтрации из радиолокации и обработки сигналов можно с успехом применять во множестве задач Pattern Recognition. Традиционным методом в радиолокации, который почти не используется в изображениях в чистом виде, является преобразование Фурье (конкретнее - БПФ). Одно из немногих исключение, при которых используется одномерное преобразование Фурье, - компрессия изображений . Для анализа изображений одномерного преобразования обычно не хватает, нужно использовать куда более ресурсоёмкое двумерное преобразование .

Мало кто его в действительности рассчитывает, обычно, куда быстрее и проще использовать свёртку интересующей области с уже готовым фильтром, заточенным на высокие (ФВЧ) или низкие(ФНЧ) частоты. Такой метод, конечно, не позволяет сделать анализ спектра, но в конкретной задаче видеообработки обычно нужен не анализ, а результат.


Самые простые примеры фильтров, реализующих подчёркивание низких частот (фильтр Гаусса) и высоких частот (Фильтр Габора).
Для каждой точки изображения выбирается окно и перемножается с фильтром того же размера. Результатом такой свёртки является новое значение точки. При реализации ФНЧ и ФВЧ получаются изображения такого типа:

Вейвлеты

Но что если использовать для свёртки с сигналом некую произвольную характеристическую функцию? Тогда это будет называться "Вейвлет-преобразование ". Это определение вейвлетов не является корректным, но традиционно сложилось, что во многих командах вейвлет-анализом называется поиск произвольного паттерна на изображении при помощи свёртки с моделью этого паттерна. Существует набор классических функций, используемых в вейвлет-анализе. К ним относятся вейвлет Хаара , вейвлет Морле , вейвлет мексиканская шляпа , и.т.д. Примитивы Хаара, про которые было несколько моих прошлых статей ( , ), относятся к таким функциям для двумерного пространства.


Выше приведено 4 примера классических вейвлетов. 3х-мерный вейвлет Хаара, 2х-мерные вейвлет Мейера, вейвлет Мексиканская Шляпа, вейвлет Добеши. Хорошим примером использования расширеной трактовки вейвлетов является задачка поиска блика в глазу, для которой вейвлетом является сам блик:

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

Корреляция

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

Фильтрации функций

Интересным классом фильтров является фильтрация функций. Это чисто математические фильтры, которые позволяют обнаружить простую математическую функцию на изображении (прямую, параболу, круг). Строится аккумулирующее изображение, в котором для каждой точки исходного изображения отрисовывается множество функций, её порождающих. Наиболее классическим преобразованием является преобразование Хафа для прямых. В этом преобразовании для каждой точки (x;y) отрисовывается множество точек (a;b) прямой y=ax+b, для которых верно равенство. Получаются красивые картинки:


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

Фильтрации контуров

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

Чаще всего используется именно Кэнни, который хорошо работает и реализация которого есть в OpenCV (Собель там тоже есть, но он хуже ищёт контуры).

Прочие фильтры

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

Но эти преобразования весьма специфичны и заточены под редкие задачи.

Часть 2. Логическая обработка результатов фильтрации

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

Морфология

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

Контурный анализ

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

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

Особые точки

Особые точки это уникальные характеристики объекта, которые позволяют сопоставлять объект сам с собой или с похожими классами объектов. Существует несколько десятков способов позволяющих выделить такие точки. Некоторые способы выделяют особые точки в соседних кадрах, некоторые через большой промежуток времени и при смене освещения, некоторые позволяют найти особые точки, которые остаются таковыми даже при поворотах объекта. Начнём с методов, позволяющих найти особые точки, которые не такие стабильные, зато быстро рассчитываются, а потом пойдём по возрастанию сложности:
Первый класс. Особые точки, являющиеся стабильными на протяжении секунд. Такие точки служат для того, чтобы вести объект между соседними кадрами видео, или для сведения изображения с соседних камер. К таким точкам можно отнести локальные максимумы изображения, углы на изображении (лучший из детекторов, пожалуй, детектор Хариса), точки в которых достигается максимумы дисперсии, определённые градиенты и.т.д.
Второй класс. Особые точки, являющиеся стабильными при смене освещения и небольших движениях объекта. Такие точки служат в первую очередь для обучения и последующей классификации типов объектов. Например, классификатор пешехода или классификатор лица - это продукт системы, построенной именно на таких точках. Некоторые из ранее упомянутых вейвлетов могут являются базой для таких точек. Например, примитивы Хаара, поиск бликов, поиск прочих специфических функций. К таким точкам относятся точки, найденные методом гистограмм направленных градиентов (HOG).
Третий класс. Стабильные точки. Мне известно лишь про два метода, которые дают полную стабильность и про их модификации. Это SURF и SIFT . Они позволяют находить особые точки даже при повороте изображения. Расчёт таких точек осуществляется дольше по сравнению с остальными методами, но достаточно ограниченное время. К сожалению эти методы запатентованы. Хотя, в России патентовать алгоритмы низя, так что для внутреннего рынка пользуйтесь.

Часть 3. Обучение

ретья часть рассказа будет посвящена методам, которые не работают непосредственно с изображением, но которые позволяют принимать решения. В основном это различные методы машинного обучения и принятия решений. Недавно Яндыкс выложил на Хабр курс по этой тематике, там очень хорошая подборка. Вот оно есть в текстовой версии. Для серьёзного занятия тематикой настоятельно рекомендую посмотреть именно их. Тут я попробую обозначить несколько основных методов используемых именно в распознавании образов.
В 80% ситуаций суть обучения в задаче распознавания в следующем:
Имеется тестовая выборка, на которой есть несколько классов объектов. Пусть это будет наличие/отсутствие человека на фотографии. Для каждого изображения есть набор признаков, которые были выделены каким-нибудь признаком, будь то Хаар, HOG, SURF или какой-нибудь вейвлет. Алгоритм обучения должен построить такую модель, по которой он сумеет проанализировать новое изображение и принять решение, какой из объектов имеется на изображении.
Как это делается? Каждое из тестовых изображений - это точка в пространстве признаков. Её координаты это вес каждого из признаков на изображении. Пусть нашими признаками будут: «Наличие глаз», «Наличие носа», «Наличие двух рук», «Наличие ушей», и.т.д… Все эти признаки мы выделим существующими у нас детекторами, которые обучены на части тела, похожие на людские. Для человека в таком пространстве будет корректной точка . Для обезьяны точка для лошади . Классификатор обучается по выборке примеров. Но не на всех фотографиях выделились руки, на других нет глаз, а на третьей у обезьяны из-за ошибки классификатора появился человеческий нос. Обучаемый классификатор человека автоматически разбивает пространство признаков таким образом, чтобы сказать: если первый признак лежит в диапазоне 0.5 По существу цель классификатора - отрисовать в пространстве признаков области, характеристические для объектов классификации. Вот так будет выглядеть последовательное приближение к ответу для одного из классификаторов (AdaBoost) в двумерном пространстве:


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

Простой случай, одномерное разделение

Разберём на примере самый простой случай классификации, когда пространство признака одномерное, а нам нужно разделить 2 класса. Ситуация встречается чаще, чем может представиться: например, когда нужно отличить два сигнала, или сравнить паттерн с образцом. Пусть у нас есть обучающая выборка. При этом получается изображение, где по оси X будет мера похожести, а по оси Y -количество событий с такой мерой. Когда искомый объект похож на себя - получается левая гауссиана. Когда не похож - правая. Значение X=0.4 разделяет выборки так, что ошибочное решение минимизирует вероятность принятия любого неправильного решения. Именно поиском такого разделителя и является задача классификации.


Маленькая ремарка. Далеко не всегда оптимальным будет тот критерий, который минимизирует ошибку. Следующий график - это график реальной системы распознавания по радужной оболочке. Для такой системы критерий выбирается такой, чтобы минимизировать вероятность ложного пропуска постороннего человека на объект. Такая вероятность называется «ошибка первого рода», «вероятность ложной тревоги», «ложное срабатывание». В англоязычной литературе «False Access Rate ».
) АдаБуста - один из самых распространённых классификаторов. Например каскад Хаара построен именно на нём. Обычно используют когда нужна бинарная классификация, но ничего не мешает обучить на большее количество классов.
SVM ( , , , ) Один из самых мощных классификаторов, имеющий множество реализаций. В принципе, на задачах обучения, с которыми я сталкивался, он работал аналогично адабусте. Считается достаточно быстрым, но его обучение сложнее, чем у Адабусты и требуется выбор правильного ядра.

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

И напоследок

Что почитать?
1) Когда-то мне очень понравилась книга «Цифровая обработка изображений» Б. Яне, которая написана просто и понятно, но в то же время приведена почти вся математика. Хороша для того, чтобы ознакомиться с существующими методами.
2) Классикой жанра является Р Гонсалес, Р. Вудс " Цифровая обработка изображений ". Почему-то она мне далась сложнее, чем первая. Сильно меньше математики, зато больше методов и картинок.
3) «Обработка и анализ изображений в задачах машинного зрения» - написана на базе курса, читаемого на одной из кафедр ФизТеха. Очень много методов и их подробного описания. Но на мой взгляд в книге есть два больших минуса: книга сильно ориентирована на пакет софта, который к ней прилагается, в книге слишком часто описание простого метода превращается в математические дебри, из которых сложно вынести структурную схему метода. Зато авторы сделали удобный сайт, где представлено почти всё содержание - wiki.technicalvision.ru Добавить метки

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

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

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

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

Энциклопедичный YouTube

1 / 4

Введение в распознавание образов

Р.В. Шамин. Лекция № 6 Сети Хопфилда и Хемминга в задачах распознавания образов

[ДДШ-2016]: Нейронные сети и современное компьютерное зрение

Лекция 9. Экспоненциальное сглаживание. Распознавание образов: метод к-го ближайшего соседа

Субтитры

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

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

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

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

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

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

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

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

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

Некоторые методы распознавания графических образов

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

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

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

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

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

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

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

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

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

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

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

Предыдущая статья: Чему равна скорость света Следующая статья: Углерод — характеристика элемента и химические свойства