Что такое технология распознавания изображений? Распознавание изображений (некоторые также называют «компьютерным зрением») это технология, которая создана получать, обрабатывать, анализировать, и понимать изображения реального мира, с целью предоставить цифровую или символьную информацию. Что вы сказали? Не беспокойтесь. Мы понимаем, что это сложно. Позвольте перефразировать: когда вы загружаете свою фотографию, или фотографию ваших друзей на Facebook, все лица будут распознаны и пользователи будут автоматически отмечены: это и называется распознаванием изображений. Хорошо, это звучит намного понятнее Прекрасно! Потому что сейчас будет еще сложнее… Компьютерное зрение – очень широкая область компьютерных наук, так как сюда вовлечено множество аспектов, таких как машинное обучение, интеллектуальный анализ данных, расширение базы знаний, распознавание шаблонов, и другие. Исследования в данной области привели к технологиям, которые имитируют человеческое зрение. И для того, чтобы создать программное обеспечение, способное видеть, вам для начала понадобится пара линз. Что вы имеете в виду? Я имею в виду, что для того, чтобы обработать изображение, вам для начала нужно его снять с помощью камеры. Затем, программное обеспечение извлекает из него необходимую информацию, и после этого, совершает действия, основываясь на полученных данных. До недавних пор, цифровые камеры были неприлично дорогими, имели очень низкое разрешение, и распознавание изображений было невозможно совершать в режиме реального времени. Но с приходом мобильных телефонов и высокоскоростных камер, возможности стали безграничны. Например, знали ли вы, что несколько лет назад Японская компания создала робота, который мог играть в «камень, ножницы, бумага» и побеждать в 10 из 10 случаях. Это невозможно… Я так не думаю. Вот ссылка на это видео. Робот использует высокоскоростные камеры для распознавания движения руки человека. Анализируя шаблоны движения руки со скоростью 500 кадров в секунду, робот способен немедленно реагировать в ответ, и в результате выигрывать. Чтобы этого добиться, камера захватывает изображение очертаний руки, формирует объект и отравляет информацию программному обеспечению, которое распознает шаблон и генерирует реакцию робота в ответ. Объект руки человека формируется 60 мс, и затем робот выполняет все вышеперечисленное за 1 мс. Хорошо, но я думал, что речь пойдет о мобильных … Не беспокойтесь, мы дойдем и до этого. Одной из самых вызывающих и перспективных областей является обработка и распознавание изображений для имитации человеческого зрения: восприятия изображения, обработки и дальнейшей реакции. Это именно то, что делает робот на предыдущем примере: он воспринимает изображение путем захвата картинки, понимает, что делает человек, и реагирует, выполняя ответный ход. Конечно, мы, разработчики программного обеспечения, более заинтересованы в той части программы, где происходит распознавание шаблона. Так как же воспринимающая часть на самом деле работает? Ответ весьма прост - «математика». Самое важное направление в алгоритмах распознавания шаблонов - вероятностная классификация. Когда изображение сравнивается с набором других сохраненных изображений, задается значение (вероятность) для каждого другого изображения, с которым оно совпадает. Комбинируя несколько алгоритмов вероятностных классификаций, которые применяются к тому же набору изображений, называемых «ансамблем», предоставляется итоговая оценка для каждого изображения, которая затем используется программой для предположения, на какие изображение это похоже. Как вы могли представить, это довольно сложно для мобильного устройства. Вы можете подумать, что мощность процессора является проблемой. Так и есть! И самое тонкое место - база данных изображений, с которыми сравнивается оригинал. На примере робота, о котором уже говорилось, Вы можете иметь только ограниченное количество изображений (камень, ножницы, бумага), с которыми можно работать, но в примере с распознаванием изображений в Facebook, невозможно сохранять лица каждого человека, кто зарегистрирован в социальной сети на мобильном устройстве (это не совсем тот способ, по которому работает данная функция; Facebook сохраняет уникальный хэш для каждого человека, используя определенные характеристики лица как основу, но пример был предоставлен исключительно для того, чтоб объяснить идею). Чтоб решить эту и другие проблемы, распознавание изображений обычно выполняется на стороне сервера, где процессорная мощность, либо место для хранения данных не представляет проблем. Мобильные устройства могут просто отправлять изображение, и нейронная сеть или оборудование обработают запрос. Одну минуту! Я видел, как это работает на мобильных устройствах без соединения с интернетом Да, но тут только часть правды. Мобильному устройству все еще необходимо отправлять изображения на сервер, также как и серверу необходимо хранить их. Как только изображения окажутся там, сервер обработает изображение, сгенерирует намного меньший хэш, и вернет обратно в приложение. И затем, к примеру, вы можете зайти в режим полета и увидеть изображение на камере телефона, сравнение будет сделано в режиме оффлайн. Спасибо за все эти объяснения. Теперь поговорим о деле А, так вы хотите знать, как применить распознавание изображений на деле? Конечно, для вас не станет сюрпризом, что у распознавания изображений есть потенциал произвести революцию во всем мире. В области здравоохранения, например, IBM начали использовать технологию распознавания изображений для обработки большого количества медицинских данных. Это может помочь врачам диагностировать болезни быстрее и с большей точностью. Baidu разработали прототип DuLight: продукт для распознавания объектов, который поможет слепым «видеть» с помощью снимков всего, что их окружает и передавая обработанные данные через наушник. Однако, на продукцию в области искусственного интеллекта обычно налагаются этические и законодательные ограничения. Возьмем, к примеру, автомобильную индустрию и беспилотные автомобили от Google. Технология готова, но предстоит еще долгий процесс, прежде чем эти машины появятся на рынке. Хорошо, но я не планирую строить беспилотный автомобиль – что может технология распознавания изображений дать моему бизнесу? Честно говоря, многое! Существует множество мелкомасштабных методов применения технологии распознавания изображений для получения преимуществ. Так как мы говорим о мобильных устройствах, давайте рассмотрим некоторые примеры использования технологии распознавания изображений в мобильной связи. Одним из крупнейших игроков в этой области является Blippar: платформа для визуального обнаружения, которая позволяет пользователям сканировать объекты и получать их описание, что делает физический мир интерактивным игровым полем. Для любителей растений существует LeafSnap, для любителей вина - Delectable. Но существуют и такие маркетинговые компании, такие как Makeup Genius, TrackMyMaccas, и SnapFindShop, на которые стоит взглянуть. Эти брэнды применяют распознавание изображений для изучения социального обмена и привлечения пользователей. Так вы говорите, что технология распознавания изображений может помочь мне привлечь клиентов? Так как мы говорим о мобильных технологиях, слово «привлечение» так или иначе, всплыло бы в течение разговора. Мир приложений вращается вокруг привлечения пользователей: если вы не преуспели в этом, то есть шанс, что пользователь просто никогда не вернется к использованию вашего приложения. Распознавание изображений даст вашему приложению огромные возможности для расширения, поскольку технология позволит Вам выйти за пределы мобильного устройства в физический мир пользователя. Ваше приложение сможет предоставить что-то более материальное, что позволит создать сильную эмоциональную связь. И так как эмоции тесно связаны с памятью, у вас есть шанс создать незабываемое впечатление о Вашем бизнесе. http://www.softacom.ru/ru_imagesrecognition
  • 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 Добавить метки

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

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

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

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

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

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

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

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

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

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

Я продолжаю серию статей посвящённую тематике pattern recognition, computer vision и machine learning. Сегодня я вам представляю обзор алгоритма, который носит название eigenface.

В основе алгоритма лежит использование фундаментальных статистических характеристик: средних (мат. ожидание) и ковариационной матрицы ; использование метода главных компонент . Мы также коснёмся таких понятий линейной алгебры, как собственные значения (eigenvalues) и собственные вектора (eigenvectors) (wiki: , eng). И вдобавок, поработаем в многомерном пространстве.
Как бы страшно всё это не звучало, данный алгоритм, пожалуй, является одним из самых простых рассмотренных мною, его реализация не превышает нескольких десятков строк, в тоже время он показывает неплохие результаты в ряде задач.


Для меня eigenface интересен поскольку последние 1.5 года я занимаюсь разработкой, в том числе, статистических алгоритмов обработки различных массивов данных, где очень часто приходится иметь дело со всеми вышеописанными «штуками».

Инструментарий

По сложившейся, в рамках моего скромного опыта, методике, после обдумывания какого-либо алгоритма, но перед его реализацией на С/С++/С#/Python etc., необходимо быстро (насколько это возможно) создать математическую модель и опробовать её, что-нибудь посчитать. Это позволяет внести необходимые коррективы, исправить ошибки, обнаружить то, что не было учтено при размышлении над алгоритмом. Для этого всего я использую MathCAD . Преимущество MathCAD в том, что наряду с огромным количеством встроенных функций и процедур, в нём используется классическая математическая нотация. Грубо говоря, достаточно знать математику и уметь писать формулы.

Краткое описание алгоритма

Как и любой алгоритм из серии machine learning, eigenface необходимо сначала обучить, для этого используется обучающая выборка (training set), представляющая собой изображения лиц, которые мы хотим распознать. После того как модель обучена, мы подадим на вход некоторое изображение и в результате получим ответ на вопрос: какому изображению из обучающей выборки с наибольшей вероятностью соответствует пример на входе, либо не соответствует никакому.

Задача алгоритма представить изображение как сумму базисных компонент (изображений):

Где Ф i – центрированное (т.е. за вычетом среднего) i-ое изображение исходной выборки, w j представляют собой веса и u j собственные вектора (eigenvectors или, в рамках данного алгоритма, eigenfaces).

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

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

За более подробным описанием я советую обращаться к списку External links википедии.

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

Создание модели

Для составления обучающей выборки использовалась Olivetti Research Lab"s (ORL) Face Database . Там имеются по 10 фотографий 40 различных людей:

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

FaceNums задаёт вектор номеров лиц, которые будут использоваться в обучении. varNums задаёт номер варианта (согласно описанию базы у нас 40 директорий в каждой по 10 файлов изображений одного и того же лица). Наша обучающая выборка состоит из 4х изображений.
Далее мы вызываем функцию ReadData. В ней реализуется последовательное чтение данных и перевод изображения в вектор (функция TwoD2OneD):

Таким образом на выходе имеем матрицу Г каждый столбец которой является «развёрнутым» в вектор изображением. Такой вектор можно рассматривать как точку в многомерном пространстве, где размерность определяется количеством пикселей. В нашем случае изображения размером 92х112 дают вектор из 10304 элементов или задают точку в 10304-мерном пространстве.

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

Функция AverageImg считает и возвращает вектор средних. Если мы этот вектор «свернём» в изображение, то увидим «усреднённое лицо»:

Функция Normalize вычитает вектор средних из каждого изображения и возвращает усреднённую выборку:

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

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

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

Собственные значения на самом деле показывают дисперсию по каждой из осей главных компонент (каждой компоненте соответствует одна размерность в пространстве). Посмотрите на правое выражение, сумма данного вектора = 1, а каждый элемент показывает вклад в общую дисперсию данных. Мы видим, что 1 и 3 главные компоненты дают в сумме 0.82. Т.е. 1 и 3 размерности содержат 82% всей информации. 2ая размерность свёрнута, а 4ая несёт 18% информации и нам она не нужна.

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

Модель составлена. Будем тестировать.

Мы создаём новую выборку из 24 элементов. Первые 4ре элемента те же, что и в обучающей выборке. Остальные это разные варианты изображений из обучающей выборки:

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

На выборке из 24 показанных выше объектов эффективность классификатора 100%. Но есть один ньюанс. Если мы подадим на вход изображение, которого нет в исходной базе, то всё равно будет вычислен вектор w и найдено минимальное расстояние. Поэтому вводится критерий O, если минимальное расстояние < O значит изображение принадлежит к классу распознаваемых, если минимальное расстояние > O, то такого изображения в базе нет. Величина данного критерия выбирается эмпирически. Для данной модели я выбрал O = 2.2.

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

Из 24 образцов имеем 4 ложных срабатывания. Т.е. эффективность составила 83%.

Заключение

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

Например, у нас в качестве классификатора применяется простой distance classifier. Однако мы могли бы применить более совершенный алгоритм классификации, например



( , часть 6.1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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


Эластичная деформация - совмещение пикселей на исходном и новом изображении





Оптический поток (неэластичная деформация). Отображение неизвестного изображения на известное, один и тот же человек. Слева направо: неизвестное изображение, изображение из базы данных, неизвестное изображение, в котором блоки заменены блоками из известного изображения.


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


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

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

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

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


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



Схема Марковской модели, пример последовательности наблюдений O и последовательности состояний S

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

Для распознавания изображений хорошо показали себя двумерные СММ. В них за «значение» принимается содержание квадратика изображения со стороной в несколько пикселей. Состояние – это положение этого квадратика на изображении. Изображение плотно покрыто решёткой таких состояний (причём границы соседних квадратиков могут частично перекрываться, что даёт лучший результат распознавания). Матрица переходов построена таким образом, что возможны переходы только между состояниями, которые соседствуют на двумерной решётке изображения. То есть, квадратик с кончиком носа будет искаться между щеками и ртом, но никак не за ухом, и если нос на неизвестном изображении будет найден левее, то левее будут искаться и соседние квадратики – щёки, нос, подбородок и т.п.








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

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

Таким образом, СММ – это почти идеальная распознавалка изображений:

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

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



Выход нейронной сети при распознавании - чётко видна разница между распознанным классом (s11) и всеми остальными. Марковские модели так не умеют.

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

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



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



Архитектура свёрточной нейронной сети. Свёрточные (convolutional) и усредняющие (subsampling) слои.

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

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

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

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


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

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

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

Из описания архитектуры свёрточных сетей, посмотрим, что они могут делать:

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

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

Вот и всё с основными способами распознавания изображений (на примере распознавания лиц). Для других видов изображения принципы распознавания те же самые, адаптированные к своей области, к своим наборам признаков.

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

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