Участник:MariaAleshina/Поиск устойчивых зависимостей в движении транспортных потоков города Москвы

Материал из MachineLearning.

Версия 13:29, 13 мая 2010

На странице изложена примерная структура будущей статьи посвященной исследованию задачи поиска устойчивых зависимостей в движении транспортных средств города Москвы студенткой Марией Алёшиной в рамках работы над дипломом

Предпосылки

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

Работа состоит в анализе данных (в частности в поиске некоторых зависимостей) движения транспортного потока города Москвы на основе данных, полученных с видеокамер сервиса Яндекс.Карты. Конкретнее, можно разделить задачу на несколько этапов. Для начала требуется скопировать видео с Яндкс.Карт и сохранить его в формате, удобном для дальнейшей обработки. Далее следует этап обработки видео. В результате требуется по видео определить такой набор параметров, как количество полос дороги, скорость потока, плотность потока и некоторые другие. Поскольку эти параметры, очевидно, не постоянны, в результате для оценки каждого парамера по данным с одной камеры можно построить временной ряд. Следующая задача состоит в одновременном (ну или почти одновременном) сборе данных с нескольких камер и построении для них временных рядов. Анализируя эти временные ряды для различных камер, появляется возможность установить некоторые закономерности в движении по Москве ("графу дорог"). Например возможно спрогнозировать образование пробок, заторов и других ситуаций в различных частях Москвы.

Требуемый результат

Этапы решения задачи

Решение задачи делится на несколько этапов:

1) Получение исходных данных с одной камеры
Выкачивание видео с сервиса Яндекс.Карты и сохранение его в формате, удобном для дальнейшей обработки (например .avi). Объем информации (длительность видео) должен быть достаточно велик.
2) Обработка исходных данных
Покадровая обработка полученного видеофайла. Нужно попробовать несколько вариантов обработки - вычитание кадров, медиана и т.п. Создание нового видео, на основе которого можно производить непосредственно анализ и/или вычисление необходимых параметров.
3) Получение необходимой информации из видеофайла
Оценка параметров движения потока в каждый момент времени. Например плотность потока, скорость потока и другие. Возможно необходимо оценить эти переметры отдельно для каждой полосы дороги. Оценка количества полос на дороге. (как?)
4) Построение временных рядов для полученных параметров движения
Возможно анализ этих временных рядов, выявление закономерностей, связанных с изменением времени суток, дней недели. Это зависит от объема информации, которую придется обрабатывать
5) Сбор информации с нескольких камер
Возможно единовременно
6) Комплексный анализ ситуации на дорогах Москвы на основе информации с различных камер
Например прогнозирование дорожной ситауции в какой-то конкретной точке Москвы на основе информации с близлежищих камер.

Получение видеоряда с одной камеры

Перед тем, как начать обработку данных, необходимо их получить. Изначальный видео поток, который необходимо обрабатывать, находится на серверах Яндекса. Найти или получить прямой ссылки на поток не удалось, поэтому было принято решение сохранять видео с помощью видео грабберов. Среди множества программ, была выбрана Camtasia Studio, которая позволяет не только снимать определенную часть экрана, но и сохранять видео в различных форматах. Существует так же одна небольшая проблема. Для того, чтобы не перегружать сервер, ровно раз в минуту видео поток на Яндекс.Картах останавливается, появляется стрелочка с надписью "Смотреть дальше". Так как для полноценного анализа данных требуется обрабатывать видео большой длины (сильно больше, чем минута), то появляется необходимость раз в минуту программно нажимать на эту стрелочку. В недрах интернета была найдена программа Сlickermann, которая позволяет программно управлять мышью. С помощью этой программы были сделаны следующие действия: раз в минуту происходит нажатие на стрелочку, после чего курсор мыши сразу отодвигается в другую часть экрана, чтобы не попадать в видеозапись. Все необходимые координаты задаются в ручную. В результате с помощью все той же Camtasia Studio видео сохраняется в формате .AVI, как в самом удобном для обработки. Пока примерная длина видео составляет 20 минут. Для полноценного анализа движения транспортных средств в Москве необходимо будет "снять" видео на пару часов.

Здесь есть несколько неприятностей. Видеопоток имеет очень плохое качество, скорость загрузки с сервера оставляет желать лучшего. Поэтому fps получаемого .AVI файла иногда слишком мало. В идеале хотелось бы получить ссылку непосредственно на поток, тогде проблемы с зависанием видео решились бы. Но пока непонятно, как это сделать.

Обработка исходных данных

Слудеющим этапом после формировки .AVI файла является его обработка. Уже давно написано множество алгоритмов, библиотек и даже целых систем по обработке изображений в целом и видео в частноти. Так что есть множество путей решения поставленной задачи. Был выбран следующий путь.

Для обработки видео была написана программа в среде Visual Studio 6.0 на языке С++ c использованием библиотеки OpenCV (CV = Computer Vision). Это довольно большая разрабатываемая бибилиотека, в которой реализовано множетсво алгоритмов обработки изображений, удобно сделана раота с видео и даже представлена пара алгоритмов по Machine Learning.

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

• Покадровая разность

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

Вот как выглядит результат работы этого простого алгоритма.

• Вычитание фона

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

  Фон формируется на основе некоторого набора кадров. Количество кадров - параметр.

  Итак, вот в общих словах используемый алгоритм выделения фона:

  Формируем изображение-разность первого и второго кадра. Считаем его изначально фоном. Но на этом изображении естественно будут пятна от движущихся машин. Получили своеобразную маску, которую накладываем на первый кадр. Далее берем разность второго и третьего кадров. На получившемся изобажении тоже будут пятна от переметившихся машин, но эти пятна будут уже в другом месте. После этого, делаем попиксельную логическую операцию "И" или умножение для двух изображений-разностей. В результате получаем новую маску. В результате такого последовательного добавления точек, получаем фон. Далее фон последовательно вычитается из каждого кадра, таким образом выделяются движущиеся объекты.

(вставить картинки)

• Mедианная фильтрация

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

Опишем алгоритм работы медианного фильтра. Требуемое изображение загружается в память, далее производится проход по всем его пикселям с каким-то окном. Ширина окна - параметр фильтра. Обычно берут окно рамера 3х3, 5х5 или 7х7 (для данной задачи как показала практика, нет смысла брать окно больше). Далее для каждого такого набора из 9ти, 25ти или 49ти пикселей вычисляется среднее значение цвета. Этим цветом заливается весь квадрат. В результате происходит эффективное удаление шума, а связные пятна, находящиеся на маленьком расстоянии друг от друга (то есть которые с большой вероятностью принадлежат одной машине) сливаются. Но здесь опять же возникает проблема. Машины, которые проезжают близко друг к другу (например по разным полосам), с большой вероятностью сливаются в одно связное пятно.

(картинки, картинки)

• Алгоритм FloodFill(заливки)

  Следующая стадия обработки видео - выделение отдельных связных пятен (машин, движещихся объектов). Эта задача была решена с помощью простой функции FloodFill, реализованной в OpenCV.

Получение информации

Построение временных рядов для полученных параметров движения

Текущие результаты

Ссылки на файлы

Ссылки на литературу