Содержание к диссертации
Введение
Глава 1 Обзор состояния предметной области 8
1.1 Методы подсчета числа пешеходов с использованием датчиков 8
1.2 Методы подсчета пешеходов в видеопоследовательности 11
1.2.1 Модели движения 11
1.2.2 Модели признаков 13
1.2.3 Комбинированные модели 15
1.2.4 Другие модели 15
1.3 Методы обнаружения отдельных людей методами компьютерного зрения 16
1.4 Методы мультиагентного моделирования 19
1.5 Основные подходы к моделированию мобильности 23
1.6 Выводы по главе 1 24
Глава 2 Определение входных данных для моделирования мобильности по данным камер видеонаблюдения 25
2.1 Метод определения входных данных для ассимиляции и идентификации моделей мобильности 25
2.2 Характеристики камер видеонаблюдения 30
2.2.1 Камеры наружного наблюдения 30
2.2.2 Камеры внутреннего наблюдения 32
2.3 Определение характеристик потоков людей 36
2.3.1 Подсчет количества людей для внутренних камер 36
2.3.2 Выделение отдельных людей 38
2.3.3 Выделение траекторий отдельных людей 42
2.3.4 Подсчет людей на видео 44
2.4 Подсчет количества людей для наружных камер наблюдения 47
2.5 Обработка видео с подвижных камер 49
2.6 Выводы по главе 2 53
Глава 3 Метод многомасштабного моделирования городской мобильности 55
3.1 Многомасштабная модель мобильности населения 55
3.2 Процедура ассимиляции данных в многомасштабную модель 58
3.3 Метод агрегации измерений 60
3.4 Статистические модели предсказания потока агентов на основе распределенной сети камер видеонаблюдения 63
3.5 Обоснование требований к конфигурации распределенной сети наблюдения для задач краткосрочного прогнозирования на основе синтетических данных 67
3.6 Методы балансировки потоков при ограниченном наборе камер 70
3.7 Выводы по главе 3 72
Глава 4 Примеры применения для городских задач 74
4.1 Расчет пешеходных потоков для массового мероприятия 74
4.2 Ежедневная городская мобильность 77
4.2.1 Извлечение данных с камер наружного наблюдения 77
4.2.2 Моделирование пешеходного перекрестка 79
4.3 Моделирование посетителей парка 83
4.4 Расчет мобильности на основе электронных карт оплаты для Санкт-Петербурга 85
4.5 Расчет мобильности во время проведения массового мероприятия 90
4.6 Выводы по главе 4 95
Заключение 97
Список источников 98
Печатные издания на русском языке 98
Печатные издания на английском языке 98
Ресурсы сети Интернет 105
Приложение А 107
Приложение Б 108
- Методы мультиагентного моделирования
- Обработка видео с подвижных камер
- Обоснование требований к конфигурации распределенной сети наблюдения для задач краткосрочного прогнозирования на основе синтетических данных
- Расчет мобильности на основе электронных карт оплаты для Санкт-Петербурга
Методы мультиагентного моделирования
Основным подходом к воспроизведению динамики пешеходов на локальном уровне (масштабы зданий, парков и фрагментов улиц), а также на уровне урбанизированных территорий (масштабы от муниципальных образований и районов до городской агломерации в целом) является мультиагентное моделирование, параметры которого могут быть настроены на основе данных видеоаналитики. Масштаб воспроизводимого процесса определяет конкретные реализации моделей, которые могут быть как максимально детализированными, т.е. описывать поведение агентов на микроуровне, так и достаточно обобщенными, описывающими агрегированные потоки агентов. Наиболее детализированные модели, работающие на микроуровне, в качестве базовых алгоритмов управления динамикой агентов используют алгоритмы на базе RVO (Reciprocal velocity obstacles) [97], Social Force [50] или их модификаций. Шаг по времени для таких моделей обычно составляет доли секунды, поэтому при большом числе агентов они являются вычислительно трудоемкими. Вычислительная трудоемкость при проведении моделирования зависит в том числе и от логики самих агентов. Реализация логики для мультиагентных моделей может привести к еще более значительному повышению нагрузки на вычислительную систему, так как при реализации даже простейших правил поведения необходимо собирать дополнительные параметры для каждого агента (например, оценивать зону видимости, количество объектов определенного типа по близости и т.п.), выполнять дополнительные проверки и осуществлять корректировку поведения (обычно это параметры скорости и направления). В итоге качество мультиагентных моделей и их компьютерных реализаций оценивается по совокупности критериев, среди которых можно выделить следующие [18]:
- Гибкость реализации. В самых простых вариантах пакет (или библиотека) мультиагентного моделирования реализуют только один алгоритм поведения агентов, в котором можно регулировать ограниченное число параметров (например, скорость агентов). В более продвинутых вариантах пакетов реализуется несколько альтернативных вариантов алгоритмов. Наиболее гибкие решения позволяют реализовывать пользовательские алгоритмы.
- Качество/объем документации. Качество документации во многом определяет возможности использования пакета моделирования на практике. Особенно важно наличие набора примеров, описывающих типовые ситуации моделирования, которые встречаются на практике. Предпочтительным вариантом является наличие специализированных форумов для разработчиков, а также открытой интернет-платформы для публикации пользователями разработанных ими моделей.
- Журналирование результатов моделирования. Объем собираемых данных и качество реализации их сбора определяют, с одной стороны, скорость моделирования (большое число фиксируемых параметров замедляет процесс моделирования), а с другой — возможности последующего анализа с целью получения полезной информации. Некоторые пакеты позволяют выводить агрегированные результаты моделирования в графическом виде, например, в форме теплокарт.
- Средства анализа результатов моделирования. В результате моделирования формируются ряды параметров, из которых впоследствии в результате статистического анализа извлекается полезная информация. Возможности пакетов в этом плане разнятся от практически отсутствия каких-либо методов обработки до весьма сложных методик проверки статистических гипотез. Большинство пакетов ограничиваются базовыми описательными статистиками, такими как среднее и дисперсия.
- Скорость моделирования. Скорость моделирования, как правило, оценивается в форме соотношения реального и модельного времени. Для количества агентов порядка нескольких тысяч хорошие реализации позволяют моделировать их поведение в близком к реальному времени с возможностью динамической визуализации. В конкретных случаях скорость зависит от геометрии пространства, плотности агентов и характеристик компьютера. Как упоминалось выше, сложная логика поведения или большой объем собираемых характеристик негативно влияют на общую скорость работы программы моделирования. Важной возможностью пакетов являются запуск моделирования в пакетном режиме без вывода текущих результатов на экран.
- Адаптация агентов. Данное свойство определяется интеллектуальностью агентов, которая может заключаться в простейших реакциях на препятствия или действия других агентов либо основываться на сложных правилах самообучения с постепенным изменением поведения в процессе моделирования.
- Самоорганизация агентов. Следуя даже простейшим индивидуальным правилам, агенты могут демонстрировать признаки самоорганизации. В основном эти правила реализуются при взаимодействии агентов за счет организации обратной связи. Однако такие возможности не заложены по умолчанию во все пакеты моделирования, хотя коллективное поведение и возникающие при этом паттерны поведения толпы представляют значительный интерес для исследователей. Основные идеи самоорганизации заключаются в формировании агентами сложных геометрических структур, имеющих признаки интеллектуального планирования, но без централизованного контроля или прямой связи между агентами.
В настоящее время разработано и представлено на рынке программного обеспечения значительное число пакетов, библиотек и даже специализированных языков для многоагентного моделирования [4]. По указанным выше критериям наибольшие оценки имеют следующие пакеты [18, 4]: MASON, Repast и NetLogo.
MASON (акроним от "Multi-agent Simulator Of Neighbourhoods / Networks") [28] является пакетом общего назначения для мультиагентного моделирования, который ориентирован в первую очередь на скорость выполнения, и возможности запуска прогона большого числа агентов в пакетном режиме. Помимо скорости, важным преимуществом пакета является интеграция со сторонними библиотеками эволюционных вычислений с различными вариантами обучения агентов.
Repast (акроним от "REcursive Porous Agent Simulation Toolkit") [75] является хорошо зарекомендовавшей себя платформой для мультиагентого моделирования, ориентированной на пользователей разного уровня. Пакет поддерживает 2D- и ЗО-моделирование с возможностью динамической визуализации сцен, логированием, построением графиков и статистической обработкой результатов на базе языка R. Пакет поддерживает удобный ввод данных из XML-файлов и пакетный запуск сценариев. Repast включает модуль для создания нейронных сетей, который может быть использован для обучения агентов. Для этих же целей реализован ряд дополнительных пакетов с генетическими алгоритмами. Из минусов пакета можно отметить необходимость достаточно глубокого знания Java для реализации специфических функций, не входящих в стандартный набор пакета.
В отличие от большинства других решений, NetLogo [ 104] является специализированным языком для моделирования агентов, программы на котором выполняются в собственной интегрированной среде моделирования. За счет своей простоты платформа NetLogo является достаточно популярной, однако относительно медленной и сложной для расширения. Платформа хорошо подходит для начинающих программистов, что обеспечивается во многом за счет функциональных свойств языка программирования и близости многих языковых конструкций к естественному текстовому описанию процессов. К недостаткам пакета можно отнести отсутствие полноценной поддержки объектно-ориентированного подхода.
Отдельно стоит отметить такой инструмент имитационного моделирования, как AnyLogic [2], который является отечественной разработкой, и за счет модульной структуры позволяет моделировать широкий класс явлений и процессов, включая поведение агентов. Для задач моделирования локальной мобильности хорошо подходит встроенный пакет Pedestrian Library, ориентированные на потоки пешеходной мобильности в «физической» окружающей среде. К достоинствам пакета относится наличие встроенных редакторов модельного окружения, высокоуровневый интерфейс блочного описания логики агентов, наличие множества примеров (см. сайты runthemodel.com и cloud.anylogic.com), хорошая документация и возможность расширения пактов за счет программирования на Java. К недостаткам можно отнести ориентацию пакета на коммерческое применение, а не на исследовательские и научные задачи.
В итоге ключевым фактором при выборе платформы для мультиагентного моделирования является набор профессиональных навыков пользователя и, в ряде случаев, степень нестандартности задачи. Многие задачи могут быт решены стандартными средствами в рамках графического интерфейса или входных файлов без привлечения программирования. Некоторые задачи требуют специфических алгоритмов, описывающих поведение агентов, которые не реализованы в стандартных модулях существующих пакетов. Для продвинутых пользователей наиболее предпочтительными вариантами являются пакеты MASON и Repast, однако по скорости разработки и наглядности результатов лучшим выбором являются NetLogo и AnyLogic. Учитывая, что проведенные исследования ориентированы в первую очередь на пешеходную мобильность как таковую, а не на принципы самоорганизации или обучение агентов, основные эксперименты были проведены с использованием пакета AnyLogic, который обладает всем необходимым набором инструментов и в наибольшей степени относительно других решений обеспечивает промышленные стандарты качества реализации.
Обработка видео с подвижных камер
На фестивале VK Fest 2016 [125] было записано видео с подвижных камер в момент прохождения через толпу у сцены. Эксперимент был поставлен с целью определения применимости различных методов для получения пространственно-временной структуры толпы в ответ на воздействие - прохождение через нее. Проход через толпу осуществлялся параллельно сцене на различном удалении от нее отдельными людьми, а также группам. Запись производилась от первого лица на камеры GoPro с креплением на голове. Пример кадра видео приведен на рисунке 2.26.
На данный момент существует очень небольшое число методов для обработки видео от первого лица. Фактически тема приобрела популярность только после появления Google Glass [122]. Основные идеи, рассматриваемые в статьях на основе данных видео от первого лица: распознавание объектов, трекинг, распознавание типа активности, анализ внимания [19]. Большое количество исследований было произведено в робототехнике для видео от первого лица, но практически отсутствуют исследования с участием толпы. Например, существует подход Visual Odometry / Ego-motion для определения ориентации/расстояния в пространстве [27] по видеоизображению. В работе [58] робот находил оптимальный путь в толпе внутри помещения с использованием дополнительной информации о своем положении, при этом его угол обзора был круговым. Для решения задач в области робототехники практически во всех работах используется дополнительная информация: определение местоположения по ГЛОНАСС/GPS, лидары, радары, камеры с углом обзора 360 градусов, а также стереокамеры. Хорошие результаты по трекингу пешеходов были достигнуты в работе [41], но в ней использовалось видео с двух видеокамер с учетом их местоположения. Исходя из существующих подходов, было определено несколько основных подходов к анализу.
Получение траекторий людей при расхождении толпы позволяет изучить взаимодействие с толпой. При расхождении толпы перед человеком с камерой возможно получить траектории людей, а также произвести их анализ и моделирование с использованием модели Social force [50]. Толпа на видео является плотной и статической, что существенно могло бы облегчить получение траекторий. Было выяснено, что непосредственно основной момент расхождения людей остается за кадром. В тех случаях, когда впереди идет еще один человек, также не всегда возможно определить факт расхождения толпы в месте прохода. В части случаев толпа не меняет своего положения, проход осуществляется по свободному месту. Отдельно следует отметить, что выделение траекторий зависит от возможности различения отдельных людей, но из-за высокой плотности толпы не во всех случаях можно успешно использовать выделение людей. На рисунке 2.27 представлен пример ситуации, когда головы людей видно с сильным перекрытием.
Обработка лиц позволяет получить дополнительную информацию об участниках фестиваля. Для видео было успешно произведено выделение лиц методом Виолы-Джонса [129]. Используя комбинацию метода обнаружения с трекингом, возможно отобрать фотографии отдельных лиц, смотрящих в кадр. На основе таких фотографий возможно применение различных методов обработки таких как оценка схожести лиц, поиск похожих лиц, определение пола, оценка возраста, оценка эмоционального состояния (например, с применением Face API Microsoft Cognitive Services [119]). Также на основе сервисов распознавания лиц, подобным FindFace [121], возможно определение страниц в социальной сети ВКонтакте [115].
Получение траектории камеры для восстановления сцены позволяет оценить пространственную структуру статической толпы. Получение траектории камеры возможно с применением подхода визуальной одометрии [67]. Для применения визуальной одометрии была произведена калибровка камер с использованием калибровочной мишени. Калибровка необходима, так как видео содержит сильные нелинейные искажения, связанные с использованием широкоугольного объектива, характерного для камер GoPro. При быстром движении камеры, например, при повороте головы, видео получается смазанным, а особенности затвора камер, добавляют искажения сдвига (rolling shutter), которых возможно избежать только при использовании «глобального затвора». Так как толпа является достаточно статичной, а момент расхождения людей остается за кадром, можно применить алгоритмы компьютерного зрения в рамках подхода Structure from motion (SfM), методы для восстановления ЗО-сцены. Для работы методов необходима обработка на графических процессорах, но даже в этом случае затрачиваемое время может быть значительным. Были протестированы различные программ варианты для построения моделей:
PFTrack [123]
Agisoft PhotoScan [116]
Pix4Dmapper [124]
решение на основе MATLAB
CMPMVS[51]
CMVS-PMVS[118]
Программы PFTrack, Pix4Dmapper позволили выделить траекторию камеры лишь на небольших участках видео из-за быстрых движений, связанных с ним искажений, а также отсутствия статических объектов для привязки. Программой Agisoft PhotoScan на протяженном маршруте камеры, удалось построить только небольшой участок. Подход с использованием CMVS-PMVS позволил достигнуть лучших результатов, но по полученным моделям все равно не получилось выделить структуру толпы, дополнительная калибровка камеры позволила только незначительно улучшить результаты. Расчет производился на видеокарте NVidia GeForce GTX 650 со скоростью примерно 20 кадров в час. Пример полученных 3D моделей приведен на рисунке 2.28.
Были рассмотрен метод одновременной локализации и построения карты (Simultaneous localization and mapping, SLAM), который тоже не привел к хорошим результатам. Подход SLAM позволяет одновременно определять положение камеры и производить пространственную привязку. Рассматривались алгоритмы ORB-SLAM2 [73] и LSD-SLAM [40] для откалиброванного видео, как наиболее популярные и широко используемые в робототехнике. Результаты LSD-SLAM, на тестовом видео позволяет различать даже небольшие детали (рисунок 2.29), но при использовании реального видео выяснилось, что алгоритм очень требователен к качеству видеоизображения. Из-за недостатков камер, а также организации съемки получаемая траектория теряется всего через несколько кадров, также, как и в случае ORB-SLAM2. Использование стереокамер или камер с «глобальным затвором» позволило бы существенно улучшить результат.
Таким образом были рассмотрены методы для получения структуры толпы для случая использования подвижной камеры, а также определены требования к камерам и организации съемки для успешного применения методов обработки видеоизображения. Для успешной съемки необходимо использование дорогостоящих специализированных камер с «глобальным затвором», камера не должна резко перемещаться на протяжении всей съемки, что делает невозможным ее крепление на голове. С учетом данных факторов для решения поставленной задачи целесообразнее использовать неподвижно закрепленные камеры.
Обоснование требований к конфигурации распределенной сети наблюдения для задач краткосрочного прогнозирования на основе синтетических данных
Для определения требований к расстановке камер, было выполнено моделирование на синтетических данных с помощью среды AnyLogic. Так как для данных, описанных в главе 2, характерно прохождение потока людей через длинный коридор, была выбрана соответствующая конфигурация в среде AnyLogic (рисунок 3.10). Моделирование производилось для постоянного потока людей 1000 человек в час и 10 человек в час при постоянной скорости агентов 1 м/с. Точка входа А располагалась в левой части прохода, точка выхода В - в правой. Точки измерения А1, А2 располагались на расстоянии 5 и 10 метров от входа, остальные точки измерения 1-8 располагались через каждые 15 метров.
Для точки выхода были построены модели линейной регрессии, аналогичные приведенным ранее на основе входа и одной из точек измерения. Полученные коэффициенты детерминации для различных точек измерения и периодов агрегирования приведены в таблице 3.2, а для потока 10 человек в час — в таблице 3.3. Цветом выделены максимумы в столбцах таблиц. Таким образом, с увеличением периода агрегирования данных и увеличением расстояния точность падает, при уменьшении потока тенденция сохраняется. Важно отметить, что моделирование производилось при постоянном потоке, переменный поток дополнительно внесет ошибки в моделирование. Для эксперимента, приведенного в главах 2-3, расстояния между камерами оказалось слишком большим для моделирования потока людей. Более точный результат мог бы быть достигнут на малых периодах агрегирования в диапазоне секунд, но применение такого малого периода не находит практического применения.
Для того чтобы выяснить как встречные потоки людей влияют на применимость статистических моделей, была поставлена серия экспериментов в среде AnyLogic. Использовалась конфигурация перекрестка с точкой выхода справа, точкой входа - слева. Моделировался выходной поток на основе входного, прохождению которого мешал другой поток (рисунок 3.11).
По результатам моделирования были получены коэффициенты детерминации (таблица 3.4). С увеличением потока, который мешает прохождению входящему, точность падает, но при различных конфигурациях потоков это происходит по-разному. При встречном потоке людей точность падает гораздо быстрее, чем при пересечении потоков.
Расчет мобильности на основе электронных карт оплаты для Санкт-Петербурга
Полученные данные для расчета мобильности представлены списком транзакций, произведенных по электронным картам оплаты в метро Санкт-Петербурга за месяц. Информация о каждой транзакции включает время, станцию отправления, тип карты, номер карты. При этом данные не содержат целевых станций, так как станции, на которых выходят пассажиры не фиксируются. Если принять допущение, что в конце дня каждый пассажир возвращается на исходную станцию, не пользуется наземным общественным транспортом в течение дня для перемещения между станциями метро и не используют разные карты в течении дня, то возможно произвести оценку матрицы корреспонденции. Для каждого пассажира в пределах дня определяется начальная станция, остальные станции по порядку входа сортируются и формируется цепочка перемещений. На основе этих данных были построены шаблоны перемещения, например, шаблон вида «1- 2- 1- 3», означает, что пассажир вошел в метро на станции 1, вышел на станции 2, затем вернулся на станцию 1, доехал до станции 3 и вернулся к начальной станции. На основе цепочек перемещений строится матрица корреспонденции: каждая следующая станция является целевой для предыдущей. При этом не учитываются пассажиры, которые совершили только одну поездку за день, так как по возвращении, скорее всего, использовался другой вид транспорта, а число таких пассажиров мало по сравнению с теми, кто совершил более двух проездок за день. Для дальнейшего использования была получена матрица корреспонденции в разрезе станций по часам в течении дня. Для обработки данных использовалась СУБД Oracle, перемещения по станциям были получены с помощью запросов, приведенных в приложении Б. На рисунке 4.19 приведена матрица корреспонденции.
Для получения колебания численности населения в различных районах на основе полученной матрицы корреспонденции необходимо учесть территориальную связанность, ввиду того, что жители домов, расположенных близко к станциям могут пользоваться метро вне зависимости от деления на районы. Для решения этой задачи были использованы данные УФМС о зарегистрированных жителях по домам. Для каждого дома была осуществлена привязка к станции или группам станций метро на основе минимизации расстояния. Полученные данные были агрегированы по станциям и сопоставлены с данными о мобильности, затем данные были объединены по районам на основе территориального размещения домов. Для данных о мобильности исходная численность населения на 0 часов соответствовала данным УФМС, далее для каждого часа учитывался приток и отток населения для каждого из районов. Для полученного изменения численности был построен индекс по часам для каждого из районов. Индекс лежит в диапазоне [0, 1], где 0 - соответствует оттоку населения, 1 - притоку. Для расчета индекса использовались альтернативные формулы: где і - значение индекса в момент времени t, N - численность населения района в различные моменты времени.
Результаты построения индекса по часам приведены на рисунках 4.20 и 4.21. По результатам работы алгоритма сформирован файл в формате GeoJSON, содержащий полигоны и значения численности населения, индекса.
Таким образом для каждого района были получены изменения численности населения в течении дня. На рисунке 4.22 приведены наиболее характерные виды шаблонов изменения численности, а на рисунке 4.23 приведены данные для всех районов. Видно, что для части районов характерен прирост числа людей в утренние часы, для других — уменьшение числа людей в это же время, два района имеют по два ярко выраженных пика - сначала численность повышается в утренние часы, затем резко снижается до вечернего минимума.
На рисунке 4.24 показан пример моделирования плотности населения на 1 апреля 2015 года для двух срезов времени: 7:00 (естественное распределение плотности) и 18:00 (изменения плотности из-за перемещения людей в течение рабочего дня). А)
На рисунке 4.25 показан пример моделирования мобильности на мезоуровне - линейное перемещение жителей без привязки к конкретному транспорту. Перемещение осуществляется между конкретными зданиями, а перемещающиеся группы жителей показаны красными точками. В приведенном примере исходная плотность распределения не изменяется.
Важным моментом является полная согласованность между макро- и мезоуровнями моделирования. Изменение плотности связано с перемещением людей, которое осуществляется на основе тех же данных.