Пользователь
0,0
рейтинг
25 августа 2009 в 18:57

В поисках НЛО. Детект объектов на изображении

Взлом captcha это, конечно, интересно и познавательно, но, по большому счёту, бесполезно. Это лишь частный случай задачи, которая возникает в одном из интересных направлений развития IT – распознавание образов (pattern recognition).



Сегодня мы рассмотрим алгоритм (точнее, более правильно считать это методикой, т.к. она объединяет в себе множество алгоритмов), который стоит на стыке таких областей, как Machine Learning и Computer Vision.

С помощью этого алгоритма мы будем искать НЛО (позарился на святое) на изображениях.


Введение



Представленная методика впервые была описана в статье «Rapid Object Detection using a Boosted Cascade of Simple Features», Paul Viola, Michael Jones, 2001. С тех пор получила признание и широкое распространение в своей области. А область применения, не трудно догадаться, это поиск объектов на изображениях или в видеопотоке.

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



Описание методики



AdaBoost

В основе методики лежит алгоритм adaptive boosting’a (адаптивного усиления) или сокращённо AdaBoost. Смысл алгоритма заключается в том, что если у нас есть набор эталонных объектов, т.е. есть значения и класс к которому они принадлежат(например, -1 – нет лица, +1 – есть лицо), кроме того имеется множество простых классификаторов, то мы можем составить один более совершенный и мощный классификатор. При этом в процессе составления или обучения финального классификатора акцент делается на эталоны, которые распознаются «хуже», в этом и заключается адаптивность алгоритма, в процессе обучения он подстраивается под наиболее «сложные» объекты. Посмотреть работу алгоритма можно здесь.

Вообще, AdaBoost очень эффективный и быстрый алгоритм. В своих проектах я использую его для детекта слабых аномалий на фоне сильных помех в различных данных, которые никак не связаны с изображениями и имеют другую природу. Т.е. алгоритм универсален и я советую обратить на него внимание. Он распространён в data mining’e, который нынче популярен на хабре, даже вошёл в «Top 10 algorithms in data mining». Очень познавательная публикация, всем советую.

Haar-like features

Встаёт вопрос как описать картинку? Что использовать в роли признака для классификации? С учётом того, что необходимо делать это быстро и наши объекты могут быть разной формы, цвета, угла наклона… В данной методике используются так называемые haar-like features (далее буду называть их примитивами).



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

Но тут возникает проблема. Даже для небольшого изображения количество накладываемых примитивов очень велико, если взять изображение размером 24х24, то количество примитивов ~180 000. Задача алгоритма AdaBoost выбрать те примитивы, которые наиболее эффективно выделяют данный объект.

Например:



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

Реализация алгоритмов

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

Алгоритм обучения очень долгоиграющая штука. При должном подходе процесс обучения может длиться 3-7 дней. Поэтому мы максимально упростим задачу, т.к. у меня нет ни времени, ни вычислительных средств, чтобы тратить неделю на обучение. На обучения каскада для этой статьи мне понадобился 1 день работы Core 2 Duo.

Следует отметить, что в реализации от OpenCV применялась более совершенная модификация алгоритма AdaBoost – Gentle AdaBoost.

Постановка задачи



С теорией всё. Переходим к практике. Наша задача найти вот это (художник из меня хреновый):



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



При условии что:

1. Объект может иметь разный цвет. ± 50 значений от исходного.
2. Объект может иметь разный размер. Размер может изменяться до 3х раз.
3. Объект имеет разный угол наклона. Угол колеблется в пределах 30°.
4. Объект имеет случайное месторасположение на изображении.

Этап 1. Создание обучающей выборки.



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

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



В реальных задачах надо ориентироваться на объём обучающей выборки в районе 5000. Я сгенерировал 2000 таких объектов.

Этап 2. Обучение



Теперь необходимо создать каскад классификаторов для имеющейся базы объектов. Для этого используем модуль haartraining. В него передаётся много параметров, самыми важными из которых являются количество классификаторов в каскаде, минимальный необходимый коэффициент эффективности классификатора (minimum hit rate), максимально допустимая частота ложных срабатываний (maximum false alarm). Параметров гораздо больше и тот, кто решит повторить эксперимент сможет более подробно познакомиться с ними здесь.

Этап 3. Тестирование каскада



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

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

+================================+======+======+======+
|            File Name           | Hits |Missed| False|
+================================+======+======+======+
|    0001_0032_0126_0138_0066.jpg|     1|     0|     0|
+--------------------------------+------+------+------+
|    0002_0088_0079_0188_0091.jpg|     1|     0|     1|
+--------------------------------+------+------+------+
|    0003_0059_0170_0127_0061.jpg|     0|     1|     0|
+--------------------------------+------+------+------+
|    0004_0035_0143_0134_0065.jpg|     1|     0|     0|
+--------------------------------+------+------+------+
.......
+--------------------------------+------+------+------+
|                           Total|   457|   543|   570|
+================================+======+======+======+
Number of stages: 7
Number of weak classifiers: 34
Total time: 14.114000


Прежде всего, посмотрите на время (значение «Total time»), которое понадобилось для обработки 1000 изображений. С учётом того, что их нужно было считывать с диска, время, затраченное на обработку одного изображения, составляет доли секунды: 14 / 1000 = 14 мс. Очень быстро.

Теперь непосредственно о результатах классификации. «Hits» — это количество найденных объектов; «Missed» это количество пропущенных; «False» — это число ложных срабатываний (т.е. каскад выдал положительный ответ на том участке, где объекта нет). В целом, это плохой результат. :) Точнее так, как пример для данной статьи он удовлетворителен, но для применения в реальных задачах следует более тщательно подходить к созданию обучающей выборки и определения оптимальных параметров для обучения, тогда возможно добиться эффективности 95% с частотой ложных срабатываний 0.001.

Некоторые результаты работы алгоритма:



А вот пару примеров с ложными срабатываниями:



Заключение



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

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

Что почитать в дополнение к указанным источникам:
An empirical analysis of boosting algorithms for rapid objects with an extended set of haar-like features.
Implementing Bubblegrams: The Use of Haar-Like Features for Human-Robot Interaction.

Данная статья показывает, что не нейросетью единой жив pattern recognition. Поэтому в продолжение вышесказанной мысли и в следующей статье хотелось бы поговорить о распознавании объектов с использованием статистического подхода, а именно применением многомерных статистических характеристик изображения и Метода Главных Компонент (Principal Component Analysis, PCA).
Indalo @Indalo
карма
181,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое

Комментарии (36)

  • 0
    впечатляет, интересно как решалась проблема поиска лиц у людей с разным цветом кожи, есть подозрение что примитив может и не подойти.
    • 0
      вполне подходит — кожа людей весьма специфично отражает свет
    • 0
      Тут многое зависит от условий освещения и ракурса. Но из десятков тысяч примитивов какой-то один всё равно будет более эффективным.
  • +1
    У меня более актуальный вопрос. Каким образом распознавать объекты на видео в реальном времени? Насколько трудоемки такие процессы и какие методы могут быть использованы?
    • +1
      Наверное надо сначала вспомнить, что видео — это 24 картинки в секунду(если говорить о фильмах).
      В методе автора поста обработка одной картинки занимала 14 мс, то есть 24 картинки обработаются за 336мс, что меньше секунды. Приведённым методом НЛО можно распознавать и на видео =)
      • +3
        Ура! Очень обнадеживающая информация, а то собираюсь магистерскую делать на тему дополненной реальности, а там распознавание объектов на видео очень важно :)
        • 0
          А можешь потом статью написать по мотивам? Я думаю, многим было бы интересно почитать…
          • 0
            У меня два года на это дело, так что в ближайшее время не ждите… А в будущем — все возможно :)
      • +1
        Понятно что если задействовать достаточные вычислительные ресурсы можно обрабатывать и 240 и 2400 кадров в секунду.
        Но ведь видео это не просто 24 картинки в секунду. Картинки связаны между собой (при онлайн-съемке). Есть ли алгоритмы межкадрового взаимодействия? Когда не просто 24 компьютера обрабатывают 24 картинки в секунду и каждый по отдельности отвечает на вопрос «Есть ли жизнь на Марсе?».
    • 0
      легко
    • 0
      C помощью стандартных каскадов OpenCV для детекции лиц, обычный компьютер вполне справляется с видео
    • 0
      Почитайте статью ссылку на которую я дал в конце. Там они используют методику для поиска робота в видеопотоке. Всё прекрасно работает. :)
  • 0
    Интересно, спасибо :)

    А вот такой вопрос — можно ли применить подобный механизм для задаач сходных с теми что представлены в проекте GalaxyZoo?

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

    • 0
      Насчёт подобного механизма не знаю, но если посмотреть вкупе с другими методами, то автоматический классификатор написать реально. Вопрос только в том насколько он будет эффективен по сравнению с краудсорсингом? Есть ли смысл «заморачиваться»?
  • 0
    У нас в Нижнем на Покровке стоят скульптуры «из прошлого», и как-то у брата мыльница обнаружила лицо на скульптуре мальчика-чистильщика обуви.
    • 0
      А у скульптуры фотографа? Или Козы в начале Покровки? /юмор/
      Вообще же статья довольно интересная, но видимо из-за моей невнимательности и непросвящённости непонятно, в чём координальное отличие от иных алгоритмов распознавания?
    • 0
      Вот это тоже интересно. Какие алгоритмы применяются в камерах? Хотя работают они определённо как-то фиговенько (по-крайней мере в моей:) ).
  • 0
    С огромным нетерпением жду следующей статьи на тему. Очень интересная а главное полезная статья, как раз то что нужно.
    • 0
      Меня в магистрской упомяните?:)
      • 0
        Ну статью на хабре в литературе можно упомянуть :)
  • 0
    Данный алгоритм, кстати, применим и в системах биометрического контроля доступа. Только там набор «семплов», например для пальца, немного другой, но смысл тот же.
  • +6
    А вы уверены что на предпоследней картинке слева вверху ложное срабатывание? :)
    Представте, благодаря этой методике на фотке нашлось настоящее НЛО! :)
    • +1
      В процессе работы над статьёй я понял, что они повсюду! :)
  • 0
    Спасибо автору за статью… интресно было почитать

    вот если что еще ссылка по теме про создание каскада на русском
    www.compvision.hi-tech-info.info/education.php
  • 0
    А не могли бы вы выложить цветные картинки в большом формате куда-нибудь? Я про космические. Понравились очень.
    • 0
      Не помню откуда качал. А как скачал сразу сделал ресайз :(
  • 0
    Скажите, а какую методику лучше использовать, например, для выделения впадин на плоскости? Освещение падает под углом, поэтому одна кромка более светлая, чем фон, другая — более темная. Хотя на глаз впадины легко определяются, непонятно как правильнее распознавать такие объекты автоматически.
    • 0
      Сложно сказать навскидку. Понятно, что нужно ориентироваться на яркость. Для начала я бы попытался получить какую-то трансформанту исходного изображения, чтобы области пониженной яркости выделялись чётко. После чего, если кроме впадин там ничего нет, то нужно сразу искать эти области. Если же кроме впадин там есть ещё объекты, то необходимо завязываться на другие признаки, например форму. По границе впадины и яркой области можно провести дугу, следовательно необходимо определить насколько зетемнённая область апроксимируется дугой. Для этого можно использовать генетические алгоритмы (реализацию можете посмотреть в статьях на хабре, тут для параболы есть) или преобразования хафа с уравнением круга/дуги (я их описывал в своей статье по взлому капчи).

      Ну, в общем, это то, что сразу в голову пришло.
      • 0
        Если ничего больше нет на изображении, то можно попробовать либо привести к полутоновому и детектором границ Канни определить эти самые границы, а затем выделить их с помощью операций дилатации и открытия, либо сразу сделать изображение бинаризованным с помощью метода Отсу, а потом делать по нему адаптивное пороговое преобразование
  • 0
    Хостинг картинок лежит. Без иллюстраций, статья сильно теряет :(
    • 0
      Поправил.
      • 0
        Спасибо! А какие примитивы были выбраны алгоритмом для поиска НЛО?
  • 0
    Хорошая статья, а как можно посмотреть какие примитивы были применены в итоге для распознавания?
  • 0
    Картинки пропали

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