Взлом 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. Объект имеет случайное месторасположение на изображении.
Первый и очень важный шаг – необходимо создать обучающую выборку. Здесь можно пойти двумя путями. Подать на обучение заранее составленную базу изображений (например, лиц) или же сгенерировать на основе одного эталонного объекта заданное количество случаев. Нам подходит последний вариант, тем более, что для генерации выборки на основе одного объекта в OpenCV есть модуль createsamples. В качестве фоновых изображений (т.е. изображений на которых отсутствует искомый объект), используется пара сотен картинок космоса (пример выше).
В зависимости от заданных параметров, модуль берёт эталонный объект, применяет к нему различные деформации (поворот, цвет, добавляется шум), далее выбирает фоновое изображение и располагает случайным образом на нём объект. Получается следующее:
В реальных задачах надо ориентироваться на объём обучающей выборки в районе 5000. Я сгенерировал 2000 таких объектов.
Теперь необходимо создать каскад классификаторов для имеющейся базы объектов. Для этого используем модуль haartraining. В него передаётся много параметров, самыми важными из которых являются количество классификаторов в каскаде, минимальный необходимый коэффициент эффективности классификатора (minimum hit rate), максимально допустимая частота ложных срабатываний (maximum false alarm). Параметров гораздо больше и тот, кто решит повторить эксперимент сможет более подробно познакомиться с ними здесь.
После долгого ожидания программа выдаёт обученный каскад в виде xml файла, который может использоваться непосредственно для детекта объектов. Чтобы протестировать его, мы снова генерируем 1000 объектов по принципу, описанному на первом этапе, создавая тем самым проверочную выборку.
Для тестирования каскада используется модуль performance. Скармливая ему проверочную выборку и каскад, после нескольких секунд мы можем наблюдать в консоли такую картину:
Прежде всего, посмотрите на время (значение «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).
Сегодня мы рассмотрим алгоритм (точнее, более правильно считать это методикой, т.к. она объединяет в себе множество алгоритмов), который стоит на стыке таких областей, как 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).
