Распознавание изображений является важным и интересным разделом компьютерной науки, имеющим самые различные применения в реальной жизни. Так, распознавание изображений может применяться для задачи распознавания автомобильных номеров, идентификации наличия пешеходов на дороге, поиска и распознавания лиц на фотографиях, системах для управления каким-либо устройством жестами, проведения автоматического контроля качества на производстве - и это только очень небольшое подмножество практических применений распознавания изображений. Поэтому неудивительно, что интерес исследователей в области computer science и искусственного интеллекта к распознаванию изображений появился еще в 60-х годах 20 века и эта область науки активно развивается до сих пор.
Существует множество формулировок для задачи распознавания изображений, и определить ее однозначно достаточно сложно. Например, можно рассматривать распознавание изображений как задачу поиска и идентификации на исходном изображении некоторых логических объектов.
Распознавание изображений обычно является сложной задачей для компьютерного алгоритма. Это связано, в первую очередь, с высокой вариативностью изображений отдельных объектов. Так, задача поиска автомобиля на изображении является простой для человеческого мозга, который способен автоматически идентифицировать у объекта наличие важных для автомобиля признаков (колеса, специфическая форма) и при необходимости «достаивать» картинку в воображении, представляя недостающие детали, и крайне сложной для компьютера, так как существует огромное количество разновидностей автомобилей разных марок и моделей, имеющих во многом разную форму, кроме того, итоговая форма объекта на изображении сильно зависит от точки съемки, угла, под которым он снимается и других параметров. Также немаловажную роль играет освещение, которое оказывает влияние на цвет полученного изображения, а также может делать незаметными или искажать отдельные детали.
Таким образом, основные трудности при распознавании изображений вызывают:
- · Вариативность предметов внутри класса
- · Вариативность формы, размера, ориентации, положения на изображении
- · Вариативность освещения
Для борьбы с этими трудностями на протяжении истории развития распознавания изображений были предложены самые различные методы, и в настоящее время в этой сфере уже удалось добиться существенного прогресса.
Первые исследования в области распознавания изображений были опубликованы в 1963 году Л.Робертсом в статье «Machine Perception Of Three-Dimensional Solids», где автор сделал попытку абстрагироваться от возможных изменений в форме предмета и сконцентрировался на распознавании изображений простых геометрических форм в условиях различного освещения и при наличии поворотов. Разработанная им компьютерная программа была способна идентифицировать на изображении геометрические объекты некоторых простых форм и формировать их трехмерную модель на компьютере.
В 1987 году Ш.Улманом и Д.Хуттенлохером была опубликована статья «Object Recongnition Using Alignment» где они также сделали попытку распознавания объектов относительно простых форм, при этом процесс распознавания был организован в два этапа: сначала поиск области на изображении, где находится целевой объект, и определение его возможных размеров и ориентации (“alignment”) с помощью небольшого набора характерных признаков, и затем попиксельное сравнение потенциального изображения объекта с ожидаемым.
Однако попиксельное сравнение изображений имеет множество существенных недостатков, таких как его трудоемкость, необходимость наличия шаблона для каждого из объектов возможных классов, а также то, что в случае попиксельного сравнения может осуществляться только поиск конкретного объекта, а не целого класса объектов. В некоторых ситуациях это применимо, однако в большинстве случаев все же требуется поиск не одного конкретного объекта, а множества объектов какого-либо класса.
Одним из важных направлений в дальнейшем развитии распознавания изображений стало распознавание изображений на основе идентификации контуров. Во многих случаях именно контуры содержат большую часть информации об изображении, и в то же время рассмотрение изображения в виде совокупности контуров позволяет его существенно упростить. Для решения задачи поиска контуров на изображении классическим и наиболее известным подходом является детектор Кэнни (Canny Edge Detector), работа которого основана на поиске локального максимума градиента .
Другим важным направлением в области анализа изображений является применение математических методов, таких как частотная фильтрация и спектральный анализ. Данные методы применяются, например, для сжатия изображений (JPEG сжатие) или повышения его качества (фильтр Гаусса). Однако, поскольку данные методы не связаны непосредственно с распознаванием изображений, более подробно они здесь рассматриваться не будут.
Еще одна задача, которая часто рассматривается в связи с задачей распознавания изображений - это задача сегментации. Основная цель сегментации - это выделение на изображении отдельных объектов, каждый из которых затем может быть отдельно изучен и проклассифицирован. Задача сегментации значительно упрощается, если исходное изображение является бинарным - то есть состоит из пикселей только двух цветов. В этом случае задача сегментации часто решается с применением методов математической морфологии . Суть методов математической морфологии заключается в представлении изображения как некоторого множества двоичных значений и применении к этому множеству логических операций, основные среди которых это перенос, наращивание (логическое сложение) и эрозия (логическое умножение). С применением данных операций и их производных, таких как замыкание и размыкание, появляется возможность, например, устранить шум на изображении или выделить границы. Если подобные методы применяются в задаче сегментации, то наиболее важной их задачей становится как раз таки задача устранения шума и формирования на изображении более-менее однородных участков, которые затем легко найти с помощью алгоритмов, аналогичных поиску связных компонент в графе - это и будут искомые сегменты изображения.
Что касается сегментации RGB-изображений, то одним из важных источников информации о сегментах изображения может стать его текстура. Для определения текстуры изображения часто применяется фильтр Габора , который был создан в попытках воспроизвести особенности восприятия текстур человеческим зрением. В основе работы данного фильтра лежит функция частотного преобразования изображения.
Другое важное семейство алгоритмов, используемых для распознавания изображений - это алгоритмы, основанные на поиске локальных особенностей. Локальные особенности представляют собой некоторые хорошо различимые области изображения, которые позволяют соотнести изображение с моделью (искомым объектом) и определить, соответствует ли данное изображение модели и, если соответствует, определить параметры модели (например, угол наклона, примененное сжатие и т.д.). Для качественного выполнения своих функций локальные особенности должны быть устойчивы к афинным преобразованиям, сдвигам и т.д. Классическим примером локальных особенностей являются углы, которые часто присутствуют на границах различных объектов. Наиболее популярным алгоритмом для поиска углов является детектор Харриса .
В последнее же время все большей популярностью пользуются методы распознавания изображений, основанные на нейронных сетях и глубоком обучении. Основной расцвет этих методов наступил после появления в конце 20 века сверточных сетей (LeCun, ), которые показывают значительно лучшие результаты в распознавании изображений по сравнения с остальными методами. Так, большая часть лидирующих (и не только) алгоритмов в ежегодном соревновании по распознаванию изображений ImageNet-2014 использовала в том или ином виде сверточные сети.
- 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).
Третий класс. Стабильные точки. Мне известно лишь про два метода, которые дают полную стабильность и про их модификации. Это и . Они позволяют находить особые точки даже при повороте изображения. Расчёт таких точек осуществляется дольше по сравнению с остальными методами, но достаточно ограниченное время. К сожалению эти методы запатентованы. Хотя, в России патентовать алгоритмы низя, так что для внутреннего рынка пользуйтесь.
Часть 3. Обучение
ретья часть рассказа будет посвящена методам, которые не работают непосредственно с изображением, но которые позволяют принимать решения. В основном это различные методы машинного обучения и принятия решений. Недавно Яндыкс выложил на Хабр по этой тематике, там очень хорошая подборка. Вот оно есть в текстовой версии. Для серьёзного занятия тематикой настоятельно рекомендую посмотреть именно их. Тут я попробую обозначить несколько основных методов используемых именно в распознавании образов.В 80% ситуаций суть обучения в задаче распознавания в следующем:
Имеется тестовая выборка, на которой есть несколько классов объектов. Пусть это будет наличие/отсутствие человека на фотографии. Для каждого изображения есть набор признаков, которые были выделены каким-нибудь признаком, будь то Хаар, HOG, SURF или какой-нибудь вейвлет. Алгоритм обучения должен построить такую модель, по которой он сумеет проанализировать новое изображение и принять решение, какой из объектов имеется на изображении.
Как это делается? Каждое из тестовых изображений - это точка в пространстве признаков. Её координаты это вес каждого из признаков на изображении. Пусть нашими признаками будут: «Наличие глаз», «Наличие носа», «Наличие двух рук», «Наличие ушей», и.т.д… Все эти признаки мы выделим существующими у нас детекторами, которые обучены на части тела, похожие на людские. Для человека в таком пространстве будет корректной точка . Для обезьяны точка для лошади . Классификатор обучается по выборке примеров. Но не на всех фотографиях выделились руки, на других нет глаз, а на третьей у обезьяны из-за ошибки классификатора появился человеческий нос. Обучаемый классификатор человека автоматически разбивает пространство признаков таким образом, чтобы сказать: если первый признак лежит в диапазоне 0.5
Существует очень много классификаторов. Каждый из них лучше работает в какой-то своей задачке. Задача подбора классификатора к конкретной задаче это во многом искусство. Вот немножко красивых картинок на тему.
Простой случай, одномерное разделение
Разберём на примере самый простой случай классификации, когда пространство признака одномерное, а нам нужно разделить 2 класса. Ситуация встречается чаще, чем может представиться: например, когда нужно отличить два сигнала, или сравнить паттерн с образцом. Пусть у нас есть обучающая выборка. При этом получается изображение, где по оси X будет мера похожести, а по оси Y -количество событий с такой мерой. Когда искомый объект похож на себя - получается левая гауссиана. Когда не похож - правая. Значение X=0.4 разделяет выборки так, что ошибочное решение минимизирует вероятность принятия любого неправильного решения. Именно поиском такого разделителя и является задача классификации.
Маленькая ремарка. Далеко не всегда оптимальным будет тот критерий, который минимизирует ошибку. Следующий график - это график реальной системы распознавания по радужной оболочке. Для такой системы критерий выбирается такой, чтобы минимизировать вероятность ложного пропуска постороннего человека на объект. Такая вероятность называется «ошибка первого рода», «вероятность ложной тревоги», «ложное срабатывание». В англоязычной литературе «False Access Rate ».
) АдаБуста - один из самых распространённых классификаторов. Например каскад Хаара построен именно на нём. Обычно используют когда нужна бинарная классификация, но ничего не мешает обучить на большее количество классов.
SVM ( , , , ) Один из самых мощных классификаторов, имеющий множество реализаций. В принципе, на задачах обучения, с которыми я сталкивался, он работал аналогично адабусте. Считается достаточно быстрым, но его обучение сложнее, чем у Адабусты и требуется выбор правильного ядра.
Ещё есть нейронные сети и регрессия. Но чтобы кратко их классифицировать и показать, чем они отличаются, нужна статья куда больше, чем эта.
________________________________________________
Надеюсь, у меня получилось сделать беглый обзор используемых методов без погружения в математику и описание. Может, кому-то это поможет. Хотя, конечно, статья неполна и нет ни слова ни о работе со стереоизображениями, ни о МНК с фильтром Калмана, ни об адаптивном байесовом подходе.
Если статья понравится, то попробую сделать вторую часть с подборкой примеров того, как решаются существующие задачки ImageRecognition.
И напоследок
Что почитать?1) Когда-то мне очень понравилась книга «Цифровая обработка изображений» Б. Яне, которая написана просто и понятно, но в то же время приведена почти вся математика. Хороша для того, чтобы ознакомиться с существующими методами.
2) Классикой жанра является Р Гонсалес, Р. Вудс " Цифровая обработка изображений ". Почему-то она мне далась сложнее, чем первая. Сильно меньше математики, зато больше методов и картинок.
3) «Обработка и анализ изображений в задачах машинного зрения» - написана на базе курса, читаемого на одной из кафедр ФизТеха. Очень много методов и их подробного описания. Но на мой взгляд в книге есть два больших минуса: книга сильно ориентирована на пакет софта, который к ней прилагается, в книге слишком часто описание простого метода превращается в математические дебри, из которых сложно вынести структурную схему метода. Зато авторы сделали удобный сайт, где представлено почти всё содержание - wiki.technicalvision.ru Добавить метки
Я продолжаю серию статей посвящённую тематике 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. Однако мы могли бы применить более совершенный алгоритм классификации, например
Сканирование изображения и обнаружение в нем объектов - задача № 1 в обработке картинок и компьютерном зрении. Поиск по запросу « автоматическое распознавание изображений » на Google Академии выдаст множество статей со сложными уравнениями и алгоритмами от начала 90-х и до наших дней. Это говорит о том, что указанная проблема занимает ученых с самого появления веб-поиска, но она пока не решена.
Основатель cognitiveSEO Рэзван Гаврилас считает , что в ближайшем будущем Google изменит алгоритмы ранжирования изображений, что повлияет на поиск и фактически на поисковую оптимизацию во всем мире. Эту тему Рэзван развивает в данной статье.
Почему умение распознавать объекты в изображениях важно для мирового digital-сообщества?
По мнению эксперта, обнаружение объектов на картинках станет неким дополнительным фактором ранжирования. К примеру, изображение синей собаки будет неразрывно связано с ключевым словом «синяя собака», а не «рыжая собака».
Для SEO это имеет два важных последствия:
- количество нерелевантных результатов при поиске по определенному ключевому слову будет меньше (в зависимости от того, что находится на изображении),
- распознавание объектов в картинке поможет связать контент страницы с этим изображением. Если на странице много фотографий синих собак и других вещей, связанных с собаками, то рейтинг этой страницы, как посвященной собакам, будет выше.
Ещё один вопрос - станет ли распознавание образов началом «новой эры» для манипуляций с объектами на картинках, как новой теневой техники SEO? Нет, потому что алгоритмы поисковых систем в наши дни легко обнаружат такой вид спама.
Google, искусственный интеллект и распознавание изображений
В 2010 году Стэндфордским университетом был впервые проведен конкурс ILSVRC (ImageNet large-scale visual recognition challenge), в рамках которого программисты демонстрируют возможности разрабатываемых ими систем распознавания объектов на изображении.
ILSVRC включает три основных этапа:
- классификация,
- классификация с локализацией,
- обнаружения.
В первом случае оценивается возможность алгоритма создавать правильные «подписи» к изображению (маркировка), локализация предполагает выделение основных объектов на изображении, похожим образом формулируется и задача обнаружения, но тут действуют более строгие критерии оценки.
В случае с обнаружением алгоритм распознавания должен описать сложное изображение с множеством объектов, определяя их местонахождение и точно идентифицируя каждый из них. Это значит, что если на картинке кто-то едет на мопеде, то программное обеспечение должно суметь не просто различить несколько отдельных объектов (например, мопед, человека и шлем), но и правильно расположить их в пространстве и верно классифицировать. Как мы видим на изображении ниже, отдельные предметы были определены и классифицированы верно.
Любая поисковая система с наличием подобной возможности затруднит, чьи-либо попытки выдать фотографии людей на мопедах за фото водителей Porsche посредством манипуляций с метаданными. Алгоритм, способный распознавать объекты, довольно продвинутый и сможет разобрать любое, в том числе и самое сложное изображение.
В 2014 году конкурс ILSVRC выиграла команда GoogLeNet. Название образовано из слов Google и LeNet - одна из реализаций свёрточной нейронной сети . Подобная сеть может быстро обучаться, а также выдавать результаты даже при наличии небольшого объёма памяти за счёт более чем десятикратного сокращения числа параметров, по сравнению с большинством других моделей компьютерного зрения.
Под термином «нейронные сети» подразумеваются искусственные нейронные сети (ИНС), являющиеся вычислительными моделями, основанными на принципах обучения и распознавания образов. Пример работы алгоритма обнаружения объекта приведен ниже:
Команда GoogLeNet использует определенный тип ИНС - сверточную нейронную сеть, принцип работы которой заключается в том, что отдельные нейроны реагируют на разные (но перекрывающиеся) области в поле зрения. Эти области можно сопоставить воедино, чтобы получить более сложный образ. По словам Рэзвана Гавриласа, это напоминает работу со слоями в редакторе изображений.
Одним из плюсов сверточной нейронной сети является хорошая поддержка перевода - любого типа движения объекта из одного пространства в другое. Инфраструктура DistBelief умеет выделять объект независимо от того, где он находится на картинке.
Ещё одна полезная возможность инфраструктуры - масштабная инвариантность, согласно которой, свойства объектов не меняются, если масштабы длины умножаются на общий множитель. Это означает, что инфраструктура DistBelief должна четко распознавать изображение, к примеру, «апельсина», независимо от того, большой ли он (на обоях для рабочего стола) или крошечный (на иконке). В обоих случаях объект оранжевый и классифицируется как «апельсин».
Необходимо сказать и о принципе Хебба, согласно которому происходит обучение искусственных нейронных сетей. В книге «Организация поведения: нейропсихологическая теория» постулат Хебба звучит следующим образом: «Если аксон клетки А находится достаточно близко, чтобы возбуждать клетку B, и неоднократно или постоянно принимает участие в ее возбуждении, то наблюдается некоторый процесс роста или метаболических изменений в одной или обеих клетках, ведущий к увеличению эффективности А, как одной из клеток, возбуждающих В».
Рэзван Гаврилас немного упрощает цитату: «Клетки, которые возбуждаются вместе, связываются вместе». В случае с ИНС «клетки» стоит заменить на «нейроны». Выстраивая дальнейшую аналогию, можно сказать, что программное обеспечение будет в состоянии обучать себя, чтобы постоянно совершенствоваться.
Google рекрутирует специалистов в области искусственного интеллекта и распознавания изображений
Собственную технологию распознавания образов Google создает на основе сторонних разработок, например, для этого была приобретена компания-стартап DNNresearch , занимающаяся исследованиями в области распознавания объектов и голоса. DNNresearch представляет собой стартап, на момент поглощения в его штате числились три человека, автоматически ставшие сотрудниками Google. Им выделен грант на поддержку работы в области нейронных сетей. Новые технологии Google может применить для улучшения качества поиска по картинкам.
Согласно стратегии компании Google, многие решения с открытым исходным кодом остаются доступны для других компаний. Это делается для развития рынка. Как считает Рэзван, зачем душить конкурентов, когда вы можете позволить себе купить его спустя некоторое время?
Ещё одно интересное приобретение Google - компания DeepMind , в которую инвестировано 400 миллионов долларов. Это и многие другие приобретения направлены в первую очередь на то, чтобы привлечь в Google квалифицированных специалистов, а не какие-то готовые решения. Подобные шаги по покупке компаний - свидетельство гонки Google, Facebook и других интернет-компаний за «мозгами» для дальнейших разработок в области искусственного интеллекта.
Google+ уже использует обнаружение объектов в картинках. На очереди Google Поиск?
На самом деле, алгоритм обнаружения изображений на основе нейронной сети уже больше года работает в Google+. Часть кода программного обеспечения представленного на ILSVRC, использовалась для улучшения алгоритмов Google+, а именно - для поиска конкретных типов фотографий.
Технология распознавания изображений от Google имеет следующие особенности:
- Алгоритм Google учитывает соответствие объектов на веб-изображениях (крупный план, искусственное освещение, детализация) с объектами на естественных фотографиях (средний план, естественный свет с тенями, разная степень детализации). Другими словами - цветок должен оставаться цветком даже на изображениях с другим разрешением или условий освещения.
- Некоторые специфические визуальные классы выведены за рамки общих единиц. Например, в большом списке из наименований цветов, которые различает алгоритм, отмечены некоторые отдельные растения, например, гибискус или георгин.
- Алгоритму распознавания изображений Google также удалось научиться работать с абстрактными категориями объектов, выделяя то или иное количество картинок, которые могли бы быть отнесены к категориям «танец», «еда», «поцелуи». Это занимает куда больше времени, чем простое выявление соотношений «апельсин - апельсин».
Классы с разным значением также обрабатываются хорошо. Пример - «автомобиль». Это точно снимок автомобиля, если на нём мы видим весь автомобиль? Считается ли изображение салона машины фотографией автомобиля или уже чем-то другим? На оба вопроса мы бы ответили утвердительно, также поступает и алгоритм распознавания Google.
Нельзя не отметить, что система распознавания изображений пока ещё недоработана. Однако даже в «сыром» виде алгоритм Google на голову выше всех предыдущих разработок в сфере компьютерного зрения.
Технология распознавания изображений - часть Графа знаний Google?
Новый алгоритм Google - часть «машинного обучения», которое отчасти реализовано в Графе знаний. В нем находятся entities - объекты, предназначенные для замещения символов, которые не могут встречаться в «чистом» виде в HTML-тексте, например, символа «
Каждый объекты и каждый класс объектов получают уникальный код, благодаря чему животное «ягуар» никогда не перепутается с одноименной маркой автомобиля. На основе этих кодов алгоритм распознавания может пользоваться базой знаний. Фактически Google создает «умный поиск», который понимает и переводит ваши слова и изображения в реальные символьные объекты.
Как технология обнаружения объекта в изображениях может повлиять на SEO?
Возможность распознавания изображений может быть полезна везде, где требуется узнать, что находится на картинке.
С точки зрения обычного SEO умение распознавать изображения является огромным шагом вперед. Это способствует повышению качества контента, так как обмануть поисковик с помощью неверной маркировки фотографий или их огромного количества становится почти невозможно.
Хороший визуальный контент (то есть высокое качество изображения, четко видимые объекты, актуальность фото), вероятно, будет играть важную роль во всем, что касается визуального поиска.
Если вы хотите, чтобы ваш рисунок был первым среди изображений по запросам «Yellow Dog», то оптимизацию придется начать с указания типа вашего снимка и перечисления содержащихся в нем объектов.
Заключение
Способность человека распознавать множество объектов и распределять их по категориям является одной из самых удивительных возможностей зрительного восприятия, компьютерных аналогов которой пока не придумано. Однако Google уже делает шаги вперед, например, ему уже принадлежит патент на автоматическое масштабное видеораспознавание объектов с 2012 года.
Итак, по мнению Рэзвана Гавриласа, органические результаты поиска Google в ближайшем времени подвергнутся изменению. Поисковик перейдет «от строк к вещам», фактически интегрировав в поисковый ландшафт свой Граф знаний. Изменятся и алгоритмы поиска, которые, вероятно, будут связаны с фактическими объектами в содержании и определении того, как эти объекты будут связаны друг с другом.
Что такое технология распознавания изображений? Распознавание изображений (некоторые также называют «компьютерным зрением») это технология, которая создана получать, обрабатывать, анализировать, и понимать изображения реального мира, с целью предоставить цифровую или символьную информацию. Что вы сказали? Не беспокойтесь. Мы понимаем, что это сложно. Позвольте перефразировать: когда вы загружаете свою фотографию, или фотографию ваших друзей на 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
