Object Detection: как написать Hello World приложениe
Прочитав серию от Adam Geitgey Machine Learning is fun, захотелось написать свою Hello World программу, которая может и не является настолько весёлой как та, что получилась у Адама, но достаточна познавательна в плане алгоритмов машинного обучения, проста в реализации и, надеюсь, будет интересна тем, кто посматривает в сторону машинного обучения.
Программа предназначена для распознавания припаркованных автомобилей на изображении, написана на Питоне, крайне проста, всего лишь пара десятков строк кода и разобраться в ней по силам даже тем, кто имеет минимальный опыт работы с Питоном. Для упрощения задачи мы будем пытаться распознать только фронтальную часть автомобиля. Под словом «распознать» имеется ввиду вычисление геометрических координат прямоугольников (маркеров), обрамляющих автомобили. Для запуска программы помимо наличия Питона на компьютере, нужна библиотека DLIB, которая представляет собой набор реализаций всевозможных алгоритмов, связанных с обработкой изображений, инструкцию по инсталляции можно найти по этой ссылке.
Результат работы программы: красные прямоугольники, обрамляющие автомобили на изображении
В качестве алгоритма мы будем использовать старый добрый (и в тоже время достаточно простой) HOG алгоритм, предложенный Dalal and Triggs в 2005 году. Алгоритм долгое время носил почётное звание state-of-art и, будучи обученным даже на небольшом наборе данных, показывает впечатляющие результаты. Сейчас свёрточные нейронные сети (CNN) позволяют более качественно распознавать объекты, но они гораздо сложнее и требуют серьёзных вычислительных ресурсов, что для нашего простенького Hello World приложения, конечно же, не подходит.
Краткое описание алгоритма
HOG (Histogram Oriented Gradients) алгоритм является классическим алгоритмом обучения с учителем (supervised learning) и состоит из двух этапов: обучения модели (learning) и применение полученной модели к новым данным (prediction). Алгоритм использует слайдинг окно, которое, перемещаясь по изображению, генерирует вектор признаков (feature vector). На этапе обучения модели сгенерированный вектор признаков используется в качестве входных данных для SVM классификатора. Участки изображения, обрамленные в красные прямоугольники, представляют наш целевой объект — автомобиль (positive labels), вся остальная часть изображения — negative labels. Далее, на этапе prediction, обученная модель для каждого положения слайдинг окна формирует число (score), описывающее вероятность того, что участок изображения, ограниченный координатами окна, является изображением автомобиля и если это число превышает некое пороговое значение, то автомобиль найден.
На первый взгляд ничего сложного, вся магия заключается в том, как сформировать вектор признаков, более детально алгоритм мы рассмотрим чуть позже.
За основу нашего приложения мы возьмём пример программы на Питоне из библиотеки DLIB (с косметическими изменениями), а именно object_detector.py, программа выполняющая распознавание лиц на изображении.
Подготовка данных для программы
Первым делом подготавливаем набор данных. Для обучения модели алгоритма нам понадобятся изображения и разметка (labeled images). В качестве изображений подойдут обычные фотографии, сделанные с вебкамеры или смартфона. Для разметки изображения библиотека DLIB предоставляет инструмент — imglab, простая программа, позволяющая тот минимум, который нам необходим — обозначить объекты на наших изображениях (найти её можно в папке tools/imglab). Результатом работы imglab является XML файл, с набором координат прямоугольников, обрамляющих наши автомобили.
Итоговый набор данных для нашей программы включает: 16 фотографий, с общим числом автомашин на фотографиях 90, для обучения модели и тестового набора данных — 4 фотографий и 39 автомашин. Кроме это нам нужны два XML файла: один с разметкой для тренировочных данных, второй — для тестовых. Разметка для тестовых данных нужна для того, чтобы оценить качество работы алгоритма. Оба этих файла генерируются программой imglab, описанной выше.
Запуск программы
Выполнение программы состоит из 3 частей: 1) загрузка размеченных изображений, 2) конфигурация SVM классификатора и запуск обучения модели 3) прогон тестовых изображений с использованием модели, обученной на предыдущем шаге.
Лог выполнения программы:
$ python car_detector.py car_images … … objective: 5.09864 objective gap: 0.0208394 risk: 0.0422724 risk gap: 0.00520985 num planes: 105 iter: 424 Training complete. Trained with C: 4 Training with epsilon: 0.01 Trained using 4 threads. Trained with sliding window 84 pixels wide by 76 pixels tall. Upsampled images 1 time to allow detection of small boxes. Saved detector to file detector.svm Training accuracy: precision: 1, recall: 1, average precision: 1 Testing accuracy: precision: 0.975, recall: 1, average precision: 0.996795 Showing detections on the images in the examples folder... Processing file: car_images/test-market-car-park.jpg Number of cars detected: 21 Hit enter to continue Processing file: car_images/test-cars-park-1.jpg Number of cars detected: 15 Hit enter to continue Processing file: car_images/test-image-1.jpg Number of cars detected: 2 Hit enter to continue Processing file: car_images/test-image-5.jpg Number of cars detected: 2 Hit enter to continue
Оценить качество распознавания объектов на тестовых изображениях нам помогают две метрики: Precision и Recall, и обе эти метрики формируются нашей программой.
Небольшое отступление для тех, кто слышал об этих терминах из мира статистики только краем уха. Применительно к нашей задаче они означают следующее: Precision — отношение количества корректно распознанных объектов к общему число распознанных объектов (среди которых могут быть и некорректные). Recall — отношение количества корректно распознанных объектов ко всем корректным объектам в тестовом наборе.
Precision = TP/(TP+FP) Recall = TP/(TP+FN)
TP — количество корректно распознанных объектов (True Positive)
FP — количество объектов распознанных ошибочно (False Positive)
FN- количество нераспознанных объектов (False Negative)
Более подробно почитать по этим метрикам можно на Википедии и на Quore. Возвращаясь к результатам программы, мы видим, что Precision = 0.975 и Recall = 1, что выглядит очень достойно для того объёма обучающих данных, который мы использовали, и время выполнения программы занимает считанные секунды (!), это вам не дни и недели необходимые для обучения CNN :) Теперь разберёмся, как получились эти числа:
Precision = TP/(TP+FP) = 39/(39+1) = 0.975
Recall = TP/(TP+FN) = 39/(39+0) = 1
Как мы видим, решетка на крыше автомобиля (на изображенни вверху), была распознана как автомобиль, что и привело к ухудшению Precision метрики (FP=1). Пофиксить эту проблему можно увеличением количества данных для обучения или тюнингом SVM классификатора.
Исходный код и данные для программы можно найти на гитхабе.
Описание HOG алгоритма
По большому счёту алгоритм состоит из двух частей: экстракция вектора признаков из данных (изображения) и обучение модели. В плане обучения модели ничего нового нет, используется SVM классификатор, вся новизна (а это 2005 год) сосредоточена в процедуре формирования вектора признаков, его описанию и будет посвящена оставшаяся часть статьи.
Слайдинг окно и image pyramid
Для анализа изображения алгоритм использует слайдинг окно размером 128×64 пикселей. Окно перемещается по изображению и формирует вектор признаков для каждого положения окна. Это отлично работает для случаев, когда наш объект идеально вписывается в окно, что встречается далеко не всегда. Для решения этой проблемы используется так называемая пирамида изображений (image pyramid). Слайдинг окно сканирует изображение несколько раз, после каждого прохода изображение сжимается, при этом размер окна остаётся неизменным — 128×64 пикселей. Визуально это можно представить как пирамиду из изображений.
Вычисление градиента изображения
Градиент изображения позволяет выделить наиболее важные части изображения и завуалировать менее важные. Под важностью понимается изменение яркости пикселей. Для вычисления градиента используются фильтры, которые применяются к изображению, авторы алгоритма пробовали разные фильтры, и оказалось, что наилучшие результаты получаются при использовании простых фильтров:
(1) −1 0 1
(2)
-1
0
1
Слева оригинальное изображение, по центру применён фильтр по вертикали-2, справа фильтр по горизонтали-1
Первый фильтр формирует градиент по горизонтали, второй — по вертикали, для получения модуля и направления вектора градиента используем стандартные вычисления:
Вычисление гистограммы градиентов
Изображение разделяется на ячейки размером 8×8, то есть 64 пикселя в ячейке, с каждым пикселем ассоциировано 2 значения, описывающие градиент: направление вектора градиента и его модуль. С учетом размеров слайдинг окна у нас получается 17*8=128 ячеек на окно, для каждой ячейки формируется гистограмма градиентов, которая представляет собой обычный массив, состоящий из 9 элементов (9 bins), другими словами, происходит распределение модулей
Наверное, сразу же возникают вопросы, почему диапазон
Нормализация
Гистограмма градиентов, полученная на предыдущем шаге, меняется в зависимости от освещённости объекта. Увеличение освещённости в 2 раза приведёт к пропорциональному увеличению величины градиентов гистограммы, такая вариативность от освещения может серьёзно повлиять на качество обучения модели. В идеале освещённость не должна влиять на гистограмму и для этой цели используется нормализация, а именно преобразование гистограммы градиентов в юнит вектор (для тех, кто подзабыл — это вектор с модулем равным единице). В нашем случае гистограмма представляет собой вектор размерностью 9 и что бы преобразовать его в юнит вектор нужно проделать следующие вычисления:
Результирующий вектор:
Этот подход будет работать, но авторы алгоритма предложили идею, которая работает лучше, а именно, нормализовать не отдельную гистограмму, а блок размером 2×2, состоящий из 4 ячеек. Работает это следующим образом: блок перемещается по изображению с перекрытием (см. Пример ниже), для каждого положения блока выполняется конкатенация гистограммы градиентов для ячеек в блоке и выполняется нормализация результирующей гистограммы.
В итоге для каждой ячейки формируется 4 гистограммы, и общая размерность вектора признаков для слайдинг окна составляет: 15*7*9*4 = 3780
Пример визуализации HOG дескриптора для фронтальной части автомобиля:
Надеюсь, статья получилась достаточно интересной и сподвигнет читателя на дальнейшее изучение ML.
Полезные ссылки:
- Navneet Dalal and Bill Triggs: Histograms of Oriented Gradients for Human Detection
- DLIB library
- Adam Geitgey: Machine Learning is Fun!
- Google releases Object Detection API
