Просто о сложном: распознавание образов в логистике

8/05/2010
Подписка RSS

OpenCV, анализ изображений
В статье рассказывается о том, почему простые вещи кажутся сложными, сложные - простыми и как побывать внутри роботизированного глаза.

Мир стремительно меняется. Настолько стремительно, что начинаешь бояться устареть сразу после рождения. Несколько лет назад секвенирование генома было задачей десятилетия, а сегодня ПЦР-анализаторы есть в каждой биотехнологической лаборатории. Вчера высокомерные европейские аналитики шутили по поводу китайской отсталости, а сегодня все ведущие биотехнологические компании называют Китай самым перспективным рынком и одним из важнейших центров развития новых технологий.

Вот и с анализом изображений и "роботизированным зрением" та же история. Кажется, что это технически недоступная область, которой занимаются исключительно японские технологические гиганты для потехи и самоутверждения. Немного заглянув за кулисы, я был искренне удивлён тому, насколько эта область стала доступнее каждому из нас: начиная от систем распознавания лиц и улыбок в фотоаппаратах и заканчивая прикладными средствами анализа изображений.

Изучая информацию о том, как собрать данные для моделирования транспортных сетей, я задался вопросом: насколько реалистично создать программу оптического анализа плотности потока транспорта по имеющейся видеозаписи? Своеобразный глаз+мозг, который сможет посчитать количество автомашин, проходящих в единицу времени в заданном направлении. Термин "реалистично" для дилетанта применительно к программному коду я трактую просто: можно ли уложиться в 100-200 строк кода на языке высокого уровня.

Литературный поиск меня приободрил с первой же минуты: множество студенческих проектов, использующих открытую библиотеку компании Intel OpenCV, говорят о том, что область оптического анализа перестала быть уделом избранных. Итак, какие задачи нужно решить, чтобы почувствовать себя всевидящим транспортным оком? 

Отделение фона от изображения

Необходимо определить сцену, являющуюся фоном, выбрать в ней "операционную область" (ROI, region of interest). После этого, можно проводить операцию "вычитания" фона из общего изображения. Основная проблема заключается в том, что нам не известно, является ли любой из кадров видео сценой, свободной от движущихся объектов. Это означает, что в качестве фона необходимо брать первый попавшийся кадр, а после этого собирать статистику и обновлять информацию о фоне, чтобы минимизировать влияние "фантомных" прохожих и автомобилей.

ФонСцена с пешеходом и автомобилями

Генерализация и фильтрация

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

Высокая генерализацияСредняяМалая

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

Высокий порог фильтраСредний порогМалый порог

Определение объектов (морфологический анализ)

Определить объекты - значит их оконтурить, соединить разделённые по разным причинам контуры в один объект, классифицировать (определить, какие контуры относятся к каким объектам).

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

Выбор интересующих объектов

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

Подсчёт плотности потока

После выполненных преобразований у нас для каждого кадра видео есть набор объектов, которые можно считать автомобилями. Чтобы вычислить плотность потока, мы могли бы использовать автоматизированные средства, позволяющие осуществлять два действия:

  • промаркировать каждый контур и связать его с конкретным автомобилем;
  • осуществлять отслеживание событий входа и выхода автомобилей в кадр.

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

Как выбрать эту характеристическую точку? Изначально в качестве такой точки нами использовался "центроид" контура (на рисунке ниже отмечен красным). Эта точка является центром масс системы материальных точек единичной массы, размещённых в вершинах выпуклой оболочки. Оказалось, что треки особой точки автомашин, движущихся в разных направлениях, могут накладываться. Это связано с некорректно выбранным положением камеры для съёмки проезжей части (с высоты 5-этажного дома, перпендикулярно самой трассе). В связи с этим, в качестве особых точек (отмечены на рисунке синим) были выбраны самые нижние границы контуров, соответствующих колёсам автомобилей. Для этого из центроида был опущен перпендикуляр на нижнюю границу, с возможностью его продолжения до абсолютного минимума по всем точкам нижней границы. В средней части сцены эти особые точки никогда не пересекаются для двух рядов автомобилей.

В качестве детекторов были выбраны две площадки в центре сцены. Критерием проезда новой машины являлось прохождение особой точкой контура заданной области не раньше, чем через N кадров после предыдущего контура.

Результаты работы программы можно посмотреть на видео, где отображены площадки для распознавания особых точек и показаны треки особых точек. Счётчики фиксируют количество машин, прошедших в обоих направлениях. В самом начале видео видно, что в качестве фона было захвачено изображение пешехода, которое постепенно "вымывается" после накопления статистики.

Казавшиеся экзотическими ещё 10 лет назад методы анализа изображений, могут быть использованы в рутинных задачах логистики, частично заменив дорогостоящие датчики и иные управленческие инструменты. Традицонным приложением описанных методик является анализ транспортных потоков, в том числе, на железнодорожном транспорте. Подсчёт количества пешеходов на тротуаре или остановке общественного транспорта, анализ числа посетителей торгового центра, более точный, чем число чеков. Анализ материальных потоков на производстве, выявление аварийных ситуаций (например, падение упаковок с конвейера). По видеоданным камер складских комплексов в режиме реального времени можно отслеживать готовность сборки заказов в зоне погрузки, проверять количество палет, поставленных в грузовики.

Если говорить о задачах операционной оптимизации, то одним из базовых, наиболее часто используемых инструментов в производственных цехах, центрах обслуживания клиентов, зонах комплектации заказов является анализ путей перемещения персонала в течение рабочего дня для минимизации потерь времени (так называемые "диаграммы спагетти", spaghetti chart). Если соединить особые точки (центроиды или минимумы) на представленном ранее видео, это и будет простейшая "диаграмма спагетти" для автомобилей.

Методы анализа перемещений транспортных средств открывают и необычные творческие перспективы. Например, в проекте Toyota iQ font:

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

P.S. По ссылке доступен исходный код программы на языке Python для использования с библиотекой OpenCV