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

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

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

Содержание 1 Предпосылки 2 Постановка задачи 3 Этапы решения задачи 3.1 Получение видео-ряда с одной камеры 3.2 Обработка исходных данных 3.3 Выделение одного и того же движущегося объекта на разных кадрах 3.3.1 Решение 1. По точечное сравнение объектов 3.3.2 Решение 2. Построение матриц схожести 3.4 Сбор информации о потоке и построение временных рядов для различных параметров движения 3.4.1 Привязка к реальному времени 3.4.2 Подсчет количества транспортных средств 3.4.3 Подсчет средней скорости потока 3.4.4 Выводы 4 Текущие результаты 5 Ссылки на литературу

Предпосылки

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

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

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

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

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

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

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.

В данной работе производится обработка не самого .AVI файла, а кадров, из которых он состоит. С помощью программы VirtualDub на основе .AVI файла формируется последовательность фреймов (картинок в .BMP формате), дальнейшая обработка производится уже с ними.

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

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

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

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

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

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

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

Было реализовано два алгоритма выделения фона.

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

Далее приводится второй более "умный" алгоритм.

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

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

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

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

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

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

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

Выделение одного и того же движущегося объекта на разных кадрах

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

Вот несколько возможных методов решения этой задачи.

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

• Другой способ основан на том, что для данного видео ряда есть возможность указать вектор движения потока (или несколько, если дорога с двусторонним движением или большим числом полос). Кроме того, можно вычислить, как изменяются размеры объекты при приближении и удалении от камеры. Соответственно на каждом кадре есть возможность для каждого связного пятна (машины) указать область изображения, в котором с большой вероятностью окажется машина на следующем кадре. После выделения такой области, переходим к следующему кадру и смотрим, какую часть зоны занимает пятно (машина). С помощью параметра-порога определяем, принадлежат ли пятна на первом и втором кадрах одной и той же машине.

Наконец-то эта задача решена! Было реализовано несколько алгоритмов.

Решение 1. По точечное сравнение объектов

Перед тем как решать задачу необходимо составить некоторое признаковое описание каждого пятна. Поэтому на первом кадре каждому черному пятну (движущемуся объекту) ставится в соответствие структура.

struct Spot
{
   int* x; //абсциссы точек, составляющих пятно 
   int* y; //ординаты точек, составляющих пятно
   CvScalar color; // цвет пятна
   int pixelnum; // количество точек в пятне
   int* speed; // скорость пятна при переходе от кадра к кадру
   bool up; // параметр, показывающий, с какой стороны от разделительной полосы находится пятно
   bool out; // вышло ли пятно за кадр (true, если машина уехала из кадра)
   bool counted; // посчитали ли мы уже эту машину? параметр, необходимый при подсчете количества машин
   double wholespeed; // средняя скорость машины на видеозаписи
};

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

Задача решена при помощи следующего алгоритма:

• Для первого кадры видео последовательности:
  • С помощью функции FloodFill закрасить все отдельные пятна разными цветами
  • Создать список существующих пятен. Каждое пятно имеет довольно большой список параметров. Основные из них - список координат точек, составляющих данное пятно, и цвет.
• Цикл. Для каждого следующего кадра
  • Найти черное пятно
  • В списке существующих пятен найти кандидата на совпадение. Далее возможны 2 ситуации.
    • Если кандидат найден, то обновляются данные о соответствующем пятне в списке. Цвет рассматриваемого пятна равен цвету кандидата.
    • Если кандидат не найден, то формируется новый элемент списка пятен. Пятну присваиваем новый цвет (вычисляется случайным образом)
  • Окрашиваем рассмотренное пятно в установленный цвет.
  • Переходим к следующему черному пятну и повторяем цикл
  • После просмотра всех пятен, смотрим, есть ли объекты, для которых на новом кадру не нашлось совпадений. Такие объекты считаются машинами, уехавшими из кадра. Они исключаются из дальнейшего рассмотрения.

Теперь рассмотрим самый важный вопрос. Как сравнивать пятна?
В реализованном алгоритме пятна сравниваются по точечно. Примем несколько гипотез:

1. За время между двумя кадрами машина не может сдвинуться больше, чем на определенное число пикселей.
2. Для каждого отдельного видеоряда мы можем и должны вручную найти разделительную полосу на дороге и определить вектора движения машин в обе стороны.

В соответствии с этими гипотезами, делаем следующее.
Сначала для каждого видеоряда необходимо вручную найти функцию (это линейная функция), описывающую разделительную полосу дороги, а так же указать, в какую сторону движутся машину по одну и по другую сторону от разделительной полосы.
Далее приступаем к непосредственному сравнению пятен. Рассматриваем 2 пятна. Одно классифицируемое (назовем его для краткости "Пятно1") и одно уже занесенное в список пятен, а значит присутствующее на предыдущем кадре ("Пятно2"). Наша задача определить, является ли "Пятно1" на текущем кадре тем же движущимся объектом, что и "Пятно2" на предыдущем кадре. "Пятно2" попиксельно сдвигается на вектора длин 0, 3, 6, 9, 12, 15. Все они имеют одно и то же направление. Это направление движения потока. Данный вектор заранее рассчитан для данного видеоряда. После сдвига происходит по точечное сравнение "Пятна2" (сдвинутого) и "Пятна1". Вычисляется величина, определяющая степень схожести объектов по формуле:

,

где hits - число совпавших точек, pixelnum1 и pixelnum2 - число точек в сравниваемых пятнах.
Если среди полученных величин самая большая превосходит заранее заданный порог ε = 0.85, то совпадение найдено. Иначе начинаем обработку следующего пятна.
Так же важно то, что в кандидаты мы выбираем только те пятна, который находят с той же стороны от разделительной полосы, что и классифицируемое пятно. При большом количестве движущихся объектов это помогает значительно сократить время работы алгоритма.

Достоинства

• Данный алгоритм довольно прост в реализации
• На "хороших" видеозаписях он показывает довольно неплохие результаты. Их можно оценить в следующих разделах, когда речь пойдет о подсчете параметров движения потока.

Недостатки

• Учитывая огромный объем обрабатываемой информации, данный алгоритм не в состоянии решить задачу за реальное время.

Решение 2. Построение матриц схожести

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

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



Здесь Square - величина, определяющая соответствие по площади(предположение: размер машины от кадра к кадру не должен значительно изменяться), Vector - по направлению (предположение: машины должны двигаться параллельно разделительной полосе), Length - по длине вектора (предположение: за время между двумя кадрами машина не может уехать на большое расстояние), - веса, причем
Кроме того, величины Square, Vector, Length имеют тип double и лежат в промежутке [0, 1], где значение 1 - объекты полностью совпадают по данному критерию.
Параметры необходимо некоторым образом настраивать. Сделать это можно, использовав два одинаковых кадра. При решении такой задачи заранее известен ответ. Максимум по каждой строке должен содержаться на диагонали матрицы. Исходя из этого настройку весов можно провести с использованием нейронной сети.
После того, как матрица сравнений построена, необходимо на ее основе решить поставленную задачу. В таблице в каждой строке выбирается максимальное число. То есть для каждого существующего объекта-машины на старом кадре выбирается наиболее похожий объект на новом кадре.
Здесь возможен ряд проблем:

• В строке нет максимума (2 и более чисел имеют одинаковые и при этом максимальные значения).
• Все числа в строке близки к 0 (ни один кандидат не подходит)

После проведения нескольких экспериментов, было выяснено, что такие проблемы на "хороших" видеозаписях возникают крайне редко. Обычно они связаны с очень плохим качеством видео.

Сбор информации о потоке и построение временных рядов для различных параметров движения

Следующий этап работы - расчет параметров потока для одной видеозаписи. Рассчитываются такие параметры, как количество проехавших машин и средняя скорость потока.

Привязка к реальному времени

Для расчета скорости необходима привязка видеозаписи к реальному времени. На некоторых видеозаписях на Яндекс.Картах в правом верхнем углу выводится реальное время. Но считывать цифры с видеозаписи - довольно трудоемкая отдельная задача. Кроме того, время есть не на всех камерах. Поэтому предлагается другой способ привязки кадров к реальному времени. Используется следующая особенность видеозаписей: ровно через каждые 2 минуты видеозапись прерывается, пользователю предлагается нажать на кнопку, чтобы продолжить просмотр. Значит, существует возможность посчитать количество кадров за 2 минуты. Если это число разделить на 120 (количество секунд в двух минутах), то мы получим количество кадров в одной секунде. Среди этих кадров будут повторяющиеся (т.к. качество видеозаписи не самое лучшее).

Подсчет количества транспортных средств

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

Каждая видеозапись содержит изображение дороги с двусторонним движением. На предыдущем этапе была выделена разделительная полоса. Теперь на каждой части дороги необходимо обозначить область, в которой транспортные средства с помощью нашего алгоритма выделяются лучше всего, а следовательно область, в которой их можно посчитать. Практически на любой видеозаписи границы областей удобно определять горизонтальными линиями. То есть другими словами, просто ставится отсечка и считается число машин, прошедших через эту отсечку.
Теперь начнем подсчет. Если движущийся объект попал в область (хотя бы одна его точка оказалась внутри области), то прибавляем к счетчику машин единицу и устанавливаем флаг counted в значение true. Теперь, если на следующем шаге мы обнаружим ту же самую машину в заданной области, то просто не будем ее считать.
Теперь оценим, на сколько наш алгоритм ошибается. Вот данные, полученные при обработке одной видеозаписи, продолжительность которой 17 минут. В таблице приведены значения, полученные программно и посчитанные вручную. Внизу отображен график, показывающий различия между реальными и программно полученными данными.

Количество машин на видео	Количество машин, посчитанных в программе

       22,00				24,00

       25,00				27,00

       19,00				21,00

       20,00				21,00

       18,00				20,00

       15,00				15,00

       21,00				21,00

       23,00				24,00

       20,00				21,00

       16,00				17,00

       22,00				24,00

       24,00				24,00

       23,00				23,00

       26,00				28,00

       25,00				25,00

       20,00				20,00

       24,00				26,00

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

Всего проехало машин – 363. Посчитано 381. 

Ошибка = 381-363/381 = 0.047.

Подсчет средней скорости потока

Выводы

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

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

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

На данный момент практически завершена работа над первым и вторым этапами. А именно, есть возможность выкачивать видео с Яндекс.Карт и почти завершен этап покадровой обработки видео. В данное время ведется активная работа над выделением одних и тех же машин на разных кадрах.

Проблема выделения одних и тех же машин на разных кадрах решена для "хороших" видеозаписей. Проблему представляют видеозаписи, на которых машины либо стоят, либо медленно движутся плотным потоком.

Для "хороших" видеозаписей так же создан алгоритм подсчета количества проехавших машин и скорости потока. Кроме того есть возможность строить временные ряды для данных параметров потока.

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

• Р. Гонсалес, Р. Вудс, «Цифровая обработка изображений»
• O'Reilly «Learning OpenCV: Computer Vision with the OpenCV Library»
• http://opencv.willowgarage.com/documentation/cpp/index.html