×Закрыть

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), другими словами, происходит распределение модулей 64-х градиентов на 9 элементов массива. Выполняется это следующим образом: 9 элементов массива пронумеровываются с 0 до 160 с шагом 20, т.е. 0, 20, 40 и т. д. Величина модуля градиента распределяется между двумя соседними ячейками пропорционально вектору направления градиента. Например, если вектор направления градиента 90 градусов и модуль равен 120, тогда в ячейки 80 и 100 добавляются по 60.

Наверное, сразу же возникают вопросы, почему диапазон 0-180, ведь направление вектора может быть в диапазоне 0-360 (или другими словами 0-/+180), зачем нужна гистограмма градиентов и т. д. По первому вопросу короткий ответ — из практики. После массы тестов, проведённых авторами алгоритма, следует, что если используется диапазон 0-180, т. е. знак вектора игнорируется, то величина ошибки распознавания минимальна. По второму вопросу, преобразование градиентов для пикселя в гистограмму градиентов преследует 2 цели: уменьшить размерность вектора признаков (feature vector), что должно благотворно сказаться на SVM классификаторе, и основная цель — повысить generalization нашего вектора признаков. Что под этим имеется ввиду, если изображение подвергается небольшой геометрической деформации, то это слабо сказывается на гистограмме градиентов, в том числе и благодаря нормализации гистограммы градиентов, описанной ниже.

Нормализация

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

Результирующий вектор:

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

В итоге для каждой ячейки формируется 4 гистограммы, и общая размерность вектора признаков для слайдинг окна составляет: 15*7*9*4 = 3780

Пример визуализации HOG дескриптора для фронтальной части автомобиля:


Надеюсь, статья получилась достаточно интересной и сподвигнет читателя на дальнейшее изучение ML.

Полезные ссылки:

  1. Navneet Dalal and Bill Triggs: Histograms of Oriented Gradients for Human Detection
  2. DLIB library
  3. Adam Geitgey: Machine Learning is Fun!
  4. Google releases Object Detection API

26 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

спасибо большое за статью. Давай еще!

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

Спасибо, постараюсь исправиться :)

Статья, конечно полезная... Узкому кругу лиц ;)
Не пойму, что она делает ЗДЕСЬ?
Мне кажется, ей место на хабре. С соответствующими тегами

Здесь нынче больше смузи и трактора обсуждают. Таков местный итэшниг.

Особенно если учесть что на хабре, есть система которая говорит всем и конкретно каждому, что вы должны всем вылизывать всем жопу за плюсики. А если вкус говна не нравиться то идти нахер

Потому что статья очень техническая.

пока что ничего не понял, но спасибо за статью. Будем разбираться ©

Для начала порекомендовал бы обзорный курс по ML на курсиере www.coursera.org/learn/machine-learning (намбер ван, без шуток!), многие вещи становатся понятными. Из минус знаю только один, все задания на матлабе/октаве, потом прийдется переучиваться на питон:)

Очень интересная тема, спасибо за статью

Спасибо!

Для тих, хто тільки починає розбиратися в ML
codeguida.com/post/739

Спасибо. Насколько реально использовать такой подход для работы с видео? Будет ли приложение успевать обрабатывать кадры и более-менее адекватно находить интересующие объекты на видео?

Имеется в виду потоковое видео?
Или уже записанное?
Думаю с записанным проблемы не будет

Записанное видео можно обрабатывать можно скольк угодно долго. Вопрос в потоковом, — «смотреть» на парковку и отправлять на телефон новых заезжающих путь к пустому месту :)

Отсканировать номер въезжающих не проблема. А с местами на парковке — нафига там 30 фпс для обработки?

Смотреть надо раз в минуту, например. Или раз в 10 секунд. Прикручиваете систему, смотрите сколько обрабатывается у вас кадр и выбираете оптимальный шаг. Как написали — зачем вам 30 проверок в секунду? К тому тут один из вопросов — а на чем это будет крутиться? На Атоме в защищеном корпусе на улице или на i9 c 64Гб опертивки?

Про 30фпс я и не писал, это уже дофантазировали. Итоговый ответ на начальный вопрос (насколько я понимаю) — да. Работать с видео можно, весь момент в частоте обрабатываемых кадров.

Задачу наверное лучше решать комплексно, мне кажется ;)
Возьмем ту же парковку (стоянку) как абстрактный пример.
1) На въезде на парковку ставится датчик въезда-выезда
2) По его срабатыванию спустя какое-то время задержки (опытным путем определить максимальное-среднее время на парковку) запустить расчет.

В Австралии на парковках над каждым местом стоят простые устройства, которые определяют, когда место занято и сколько уже машина стоит.
По истечении льготного времени (3 часа) устройство загорается фиолетовым цветом.
Когда место свободно — зеленым, занято — красным.
Это на паркингах в ТЦ.
И ничего распознавать не надо.
Но статья интересная, надо будет попробовать «Нелло ИИ» на кошках ;)

Но статья интересная, надо будет попробовать «Нелло ИИ» на кошках ;)

Ты главное их с собаками не путай.

прикрутите gstreamer. дергайте один два фрейма в секунду-отправляйте на распознавание. на i3 будет в реалтайме. быстрее и качественнее результат будет конечно на нейронке, но там важен подготовленный датасет с сэмплами авто. поэтому в разработке будет дольше, но результаты качественнее и быстрее.

Приличные датасеты бабла хорошего стоят. Сам собирать затрахаешься.

Никто не говорил что будет легко — только про результат, если _хороший_ датасет.

Так вот подготовить такой датасет — это в 10 раз больше работы, чем собственно код написать.

Я думаю побольше.
+ попробуй код написать который будет понимать что на картинке котик)

Подписаться на комментарии