Участник:MariaAleshina/Поиск устойчивых зависимостей в движении транспортных потоков города Москвы
Материал из MachineLearning.
| На странице изложена примерная структура будущей статьи посвященной исследованию задачи поиска устойчивых зависимостей в движении транспортных средств города Москвы студенткой Марией Алёшиной в рамках работы над дипломом |
Содержание |
Предпосылки
Постановка задачи
Работа состоит в анализе данных (в частности в поиске некоторых зависимостей) движения транспортного потока города Москвы на основе данных, полученных с видеокамер сервиса Яндекс.Карты. Конкретнее, можно разделить задачу на несколько этапов. Для начала требуется скопировать видео с Яндкс.Карт и сохранить его в формате, удобном для дальнейшей обработки. Далее следует этап обработки видео. В результате требуется по видео определить такой набор параметров, как количество полос дороги, скорость потока, плотность потока и некоторые другие. Поскольку эти параметры, очевидно, не постоянны, в результате для оценки каждого парамера по данным с одной камеры можно построить временной ряд. Следующая задача состоит в одновременном (ну или почти одновременном) сборе данных с нескольких камер и построении для них временных рядов. Анализируя эти временные ряды для различных камер, появляется возможность установить некоторые закономерности в движении по Москве ("графу дорог"). Например возможно спрогнозировать образование пробок, заторов и других ситуаций в различных частях Москвы.
Требуемый результат
Юрий Викторович, если честно, то я не знаю, что тут писать...)
Этапы решения задачи
Решение задачи делится на несколько этапов:
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 соседних кадра (в принципе можно брать кадры через один или даже через два), на основе которых формируется третье изображение, как попиксельная разность первых двух. Специфика видео, используемого в данной работе такова, что цвет одно и того же пикселя фона может немного отличаться от кадра к кадру, соответственно в результирующем изображении цвет этого пикселя не будет нулем. Поэтому кроме вычитания, необходимо сделать изображение монохромным с некоторым порогом. Все пиксели, цвет которых выше этого порога, становятся черными, все остальные - белыми. Порог - это тоже параметр, который необходимо подобрать так, чтобы движущиеся объекты были довольно четкими, но при этом чтобы было как можно меньше шумов. Задачу удаления шумов также можно решить различными другими алгоритмами, например медианным сглаживанием.
- Из-за плохого качества и медленной работы видео существует несколько проблем. Во-первых, очень много шума. Но с этим можно успешно бороться. Во-вторых, из-за того, что видео поток на Яндексе подгружается часто очень медленно, мы получаем несколько подряд идущих одинаковых кадров, что значит, что их разность - это пустой кадр.
- Вычитание фона
- Другая, более "умная" стратегия - сформировать фон, а потом вычесть этот фон из каждого кадра, в результате останутся только движущиеся объекты, не принадлежащий фону.
- Фон формируется на основе некоторого набора кадров. Количество кадров - параметр.
- Было реализовано два алгоритма выделения фона.
- Первый и самый простой можно кратко описать так: данный пиксель изображения считать фоном, если он не изменялся (а точнее изменялся в заданном небольшом диапазоне) на протяжении нескольких кадров. Параметром данного алгоритма является не только количество кадров, но и порог, определяющий допустимый диапазон изменения цвета пикселя.
картинки
- Далее приводится второй более "умный" алгоритм.
- Формируем изображение-разность первого и второго кадра. Считаем его изначально фоном. Но на этом изображении естественно будут пятна от движущихся машин. Получили своеобразную маску, которую накладываем на первый кадр. Далее берем разность второго и третьего кадров. На получившемся изображении тоже будут пятна от переместившихся машин, но эти пятна будут уже в другом месте. После этого, делаем попиксельную логическую операцию "И" или умножение для двух изображений-разностей. В результате получаем новую маску. В результате такого последовательного добавления точек, получаем фон. Далее фон последовательно вычитается из каждого кадра, таким образом выделяются движущиеся объекты.
(вставить картинки)
- Медианная фильтрация
- Естественно, полученное таким образом изображение содержит множество шумов. Кроме того, движущиеся объекты состоят из некоторого числа связных пятен. А для дальнейшей обработки желательно, чтобы каждая машина была представлена на изображении в виде одно связного пятна. Для решения этих двух проблем одновременно была применена медианная фильтрация.
- Опишем алгоритм работы медианного фильтра. Требуемое изображение загружается в память, далее производится проход по всем его пикселям с каким-то окном. Ширина окна - параметр фильтра. Обычно берут окно размера 3х3, 5х5 или 7х7 (для данной задачи как показала практика, нет смысла брать окно больше). Далее для каждого такого набора из 9ти, 25ти или 49ти пикселей вычисляется среднее значение цвета. Этим цветом заливается весь квадрат. В результате происходит эффективное удаление шума, а связные пятна, находящиеся на маленьком расстоянии друг от друга (то есть которые с большой вероятностью принадлежат одной машине) сливаются. Но здесь опять же возникает проблема. Машины, которые проезжают близко друг к другу (например по разным полосам), с большой вероятностью сливаются в одно связное пятно. Кроме того, машины, которые находятся еще далеко, распознаются как шум и удаляются. Но если для подсчета параметров потока поставить отсечку ближе к нижнему левому углу, то это перестает быть проблемой.
- Алгоритм FloodFill(заливки)
- Следующая стадия обработки видео - выделение отдельных связных пятен (машин, движущихся объектов). Эта задача была решена с помощью простой функции FloodFill, реализованной в OpenCV. Принцип работы этой функции прост. Работа происходит с монохромным изображением. Белые пиксели обозначают фон, черные пиксели принадлежат движущимся объектам (машинам). Производится проход по пикселям изображения, пока не попадется черный пиксель. Вызываем функцию FloodFill, передавая ей как параметр координаты черного пикселя. Функция производит заливку связной области, содержащей заданный пиксель заданным цветом (отличным от черного). Таким образом в результате формируется изображение, на котором все связные пятна (машины) раскрашены в разные цвета.
картинка
Выделение одного и того же движущегося объекта на разных кадрах
После того, как проведена первичная обработка и на каждом кадре выделены движущиеся объекты, необходимо решить задачу поиска одного и того же объекта на каждом кадре.
Вот несколько возможных методов решения этой задачи.
- Можно воспользоваться тем, что по мере движения очертания машины меняются с точностью до размеров. Соответственно можно отдельно сохранить область изображения, соответствующую одной машине, пропорционально увеличивать или уменьшать ее и наложением искать совпадения на последующих (или предыдущих) кадрах.
- Другой способ основан на том, что для данного видео ряда есть возможность указать вектор движения потока (или несколько, если дорога с двусторонним движением или большим числом полос). Кроме того, можно вычислить, как изменяются размеры объекты при приближении и удалении от камеры. Соответственно на каждом кадре есть возможность для каждого связного пятна (машины) указать область изображения, в котором с большой вероятностью окажется машина на следующем кадре. После выделения такой области, переходим к следующему кадру и смотрим, какую часть зоны занимает пятно (машина). С помощью параметра-порога определяем, принадлежат ли пятна на первом и втором кадрах одной и той же машине.
Сбор информации о потоке и построение временных рядов для различных параметров движения
Следующий этап работы - расчет параметров потока.
На каждом изображении требуется поставить некую черту, отсечку и считать число проехавших через нее машин. Так же необходимо сделать привязку кадров к времени, чтобы считать количество проходящих машин в минуту (или другую единицу времени), скорость потока по каждой полосе и т.д..
Для достаточно больших видео появляется возможность построения временного ряда для каждого такого параметра. Например для каждой минуты можно посчитать число проехавших через отсечку машин и построить соответствующий график.
