Программы, которые доступны нам сегодня для автомобильной навигации оказывают большую помощь водителям. Они помогают нам ориентироваться в незнакомой местности и объезжать пробки. Это большой труд людей со всего мира, который сделал нашу жизнь проще. Но нельзя останавливаться на достигнутом, технологии идут вперед и качество программ также должно расти.
Сегодня, на мой взгляд, одна из проблем навигационных устройств – это то, что они не ведут пользователя по полосам. Эта проблема увеличивает время в пути, пробки и аварийность. Недавно google maps начали отображать разметку дороги перед поворотом, что уже хороший результат, но и тут можно многое улучшить. Карты не знают на какой полосе сейчас находится машина, средствами gps узнать это проблематично, у gps слишком большая погрешность для этого. Если бы мы знали текущую полосу, то знали бы скорость движения по полосами и могли бы задолго подсказывать пользователю в явном виде, на какую полосу и когда ему лучше перестроиться. Например, навигатор говорил бы “Продолжайте держаться этой полосы до перекрестка” или “Перестройтесь на крайнюю левую полосу”.
В этой статье мы попробуем рассказать, как мы пытаемся определять перестроения, текущую полосу движения автомобиля, повороты, обгоны, а также другие маневры с помощью машинного обучения по данным акселерометра и гироскопа.
Рекомендовать перестроения, можно не только в случае, если движение по полосе медленное, скажем, из-за того, что с левой полосы поворачивают машины. Также, рекомендовать перестроиться можно в том случае, если на текущей полосе авария. Сейчас аварии и дорожные проблемы наносятся пользователями вручную. Можно было бы сделать алгоритм, который бы наносил их на карту автоматически, смотря на маневры машин. Если автомобили в одном и том же месте массово совершают объезд, то, видимо, там произошла какая-то проблема. Зная это, система могла бы предупреждать водителей, перестроиться на другую полосу заранее, если они ее уже не занимают.
Еще одна проблема, связанная с достаточно низкой точностью gps во дворах, это то, что на извилистых дорожках придомовых территорий достаточно сложно определить положение машины. Положение выдается с точностью плюс минус 10 метров и непонятно прошла ли уже машина поворот или нет. А в незнакомом дворе это критично, ведь мы ориентируемся на навигатор, а он по сути не всегда знает, где мы находимся сейчас. Если бы могли достоверно точно определять поворот, то могли бы вести пользователя не только по gps, а помогать системе позиционирования данными о поворотах и точно знали бы где находится пользователь.
Gps также не сразу может определить разворот машины. Она должна проехать несколько метров назад перед тем, как будет понятно, что был совершен маневр. Если бы мы могли определить разворот сразу, то новый перестроенный маршрут был бы у пользователя намного быстрее.
Перестроение в карман с основной дороги также в случае Gps является спорным моментом, только по ее данным сейчас сложно сказать, перестроился ли пользователь или нет, особенно если карман не глубокий. Если бы был алогоритм, который бы альтернативным способом сообщал эту информацию, то комбинируя ее с Gps, точность можно было бы заметно повысить.
Как предполагается решить эти проблемы?
В свободное время я и несколько студентов Computer Science Center делаем проект с открытым исходным кодом по определению дорожных событий с помощью акселерометра и гироскопа. В итоге мы хотим сделать доступную библиотеку с открытой лицензией, которая позволит, принимая на вход данные от сенсоров мобильного телефона или какого то другого устройства, выдавать на выходе такие события как перестроение на другую полосу, обгон, объезд препятствия, поворот и разворот. Пользователю библиотеки останется реализовать switch в своей программе и правильным образом реагировать на те или иные события.
Использовать библиотеку, по идее, могут не только телефоны, но и, скажем, устройства на базе микроконтроллеров, осуществляющие мониторинг транспорта. Скажу сразу, что мы в середине пути и пока нет уверенности, что мы сможем определять все события, но кажется, у нас может что-то получиться.
Как вообще выглядят различные события, если их отобразить на графике?
События обозначены прерывистыми вертикальными линиями:
Оставим активными только ось y для акселлерометра (боковые перегрузки, верхний график) и ось z гироскопа (вращение машины, вид сверху, нижний график), можно заметить как повороты и развороты сопровождаются увеличенными боковыми перегрузками и увеличивающимся вращением вокруг оси Z. При перестроении гироскоп и акселерометр быстро меняют свои показатели с положительного на отрицательное.
Кажется, что человек, глядя на эти графики, может более менее понять, какой тип события имел место, соответственно, у классификтора на базе алгоритма машинного обучения проблем также возникнуть не должно.
Что было уже реализовано.
Мы собрали первоначальные данные: это около 1000 километров видеозаписей и телеметрии, собранной с телефона по дорогам Санкт-Петербурга и Москвы.
Сделали окружение для удобной работы с видео и данными, которое выглядит вот так:
Оно состоит из трех частей. В самом верху просмотр видео с движением машины. В центре располагается график, на котором можно смотреть данные с акселерометра, гироскопа и текущую скорости. В окне внизу можно модифицировать данные скриптом (coffescript) налету для отображения на графике (например, нам нужен сглаженный график).
Помимо этого дэшбоард предоставляет возможность размечать события на видео, сохранять их в файл и видеть их потом отмеченными на графике с аннотациями.
Возможно, кто-то из вас в своих задачах также сопоставляет видеоряд с данными сенсоров, либо просто смотрит на данные сенсоров. Если это так, вам может пригодится дэшборд, в котором мы работаем github.com/blindmotion/dashboard. Он достаточно удобен, позволяет масштабировать, видоизменять данные налету скриптом и у него открытая лицензия, а значит его можно свободно использовать и модифицировать.
Мы также сделали нормализатор для акселерометра и гироскопа.
Телефон может быть расположен как угодно в салоне машины, при этом его положение может меняться. Нам нужно привести все данные к одному знаменателю для передачи нашей модели. Для этого человек из нашей команды написал нормализатор, библиотеку, которая вне зависимости от ориентации устройства всегда выдает ось z перпендикулярно Земле, ось x совпадает с направлением движения автомобиля, а ось y перпендикулярна направлению движения является касательной к Земле. Выглядит это как то так:
Для того, чтобы это работало мы вначале ориентируемся на вектор земного притяжения и строим матрицу поворота таким образом, чтобы наша ось z после поворота совпадала с этим вектором. Матрица вращения для правильной ориентации x и y строится чуть более сложным способом.
До нормализации данные выглядят так:
На графике акселлерометра мы видим, что ось X (на графике ax; a – акселлерометр, g — гироскоп) имеет почти постоянно значение примерно равное 10g, что неправильно, так как ось Х — параллельна Земле. Выполняем нормализацию и получаем такой график:
Теперь все на своих местах, значение по оси Z (az) равно 10g, а X и Y соответствующие значения для движения автомобиля.
Нормализатор может пригодиться также в других проектах, не связанных с классификацией событий на дороге, но связанных с обработкой данных от сенсоров.
Сдалали классификатор
Сейчас для классификации используется feedforward neural network с тремя hidden layers и выглядит все это примерно так:
На вход подаются 66 элементов:
20 – показания акселерометра по нормализованной оси Х (боковое ускорение)
20 – показания акселерометра по нормализованной оси Y (продольное ускорение)
20 – показания гироскопа по нормализованной оси Z (вращение вокруг оси перпендикулярной Земле)
5 – показания спидометра gps
1 – время всего маневра
В такой конфигурации, на первый взгляд, получается оптимальное соотношение входных данных и результата, хотя добавление других осей совсем немного улучшает точность.
Более подробно о том, как организовано обучение
Как я уже говорил, на вход подаются показания акселерометра и гироскопа и их ровно по 20 элементов каждого. То есть берем промежуток времени, для этого промежутка берем показания акселерометра по оси Х, по оси Y и гироскопа по оси Z. У нас получается три массива данных и в них не обязательно 20 элементов изначально. К 20 же мы приводим их экстраполяцией или интерполяцией.
Я говорил про промежуток времени. Как его выбрать? Вот есть у нас данные за день. Выше я говорил про дэшборд, в котором мы делаем разметку событий. То есть, говоря простым языком, указываем там, что с 12:00:34 по 12:00:41 у нас было перестроение налево. Так указываем все произошедшие события и получаем некоторое множество событий (events). Помимо событий, все остальное простанство занимает idle, то есть те отрезки времени, в течение которых не было ни перестроений, ни поворотов, ни каких-либо других событий.
Получив множество событий таким образом мы потом последовательно каждым из этих событий обучаем модель. Передаем ей данные события и говорим, что вот это был обгон, скажем.
Модель также учится тому, что такое отсутствие событий. Весь оставшийся промежуток времени, где нет событий, мы делим на какие-то промежутки и также даем модели, говоря, что вот тут ничего нет.
На рисунке изображен этот процесс. Вверху линия – это данные по оси времени. Вот у нас ничего не было (idle), потом пошло событие (event), потом снова ничего, еще одно событие, и снова ничего. Ниже этой линии семплы (желтые квадраты), которые передаются модели для обучения.
Допустим обучили, что дальше? Перейдем к определению событий на новых данных, то есть, классификации.
Имея уже обученную сеть мы можем классифицировать события с ее помощью. Мобильный телефон передает нам постоянный поток данных от датчиков. Мы храним историю всех показаний за последние 30 секунд и передаем эту историю нашей модели в надежде на то, что она сможет там что то найти. Передаются отрезки длиной 2, 4, 6, 8, 10, 15, 20, 25, 30 секунд (образно) и для каждого из отрезков определяется вероятность того или иного события предсказанного моделью.
Например, отрезки:
[с “текущее время” по “2 секунды назад”] – вероятности: idle 51%, поворот налево 23%, поворот направо 52%
[текущее время — 4 секунды назад] – idle 62%, поворот налево 21%, поворот направо 60%
[текущее время — 6 секунды назад] – idle 50%, поворот налево 27%, поворот направо 91%
[текущее время — 8 секунды назад] – idle 52%, поворот налево 17%, поворот направо 72%
Здесь для отрезка времени с текущего момента до 6 секунд назад модель выдает вероятность 91% для поворота направо. Скажем, это больше нашего threshold 90% и мы добавляем на карту событий событие поворот направо для этого времени.
В итоге у нас получается карта отклассифицированных событий, из которой мы можем попробовать сделать вывод о том, какие события все же происходили. На практике одно и то же событие, если делать измерения с шагом в пол секунды по каждому из интервалов (то есть через каждые пол секунды мы повторяем изложенный выше алгоритм с отрезками) может быть определено несколько раз (на рисунке изображено 2 раза, два зеленых event в центре рисунка). Чтобы разобраться с ними воспользуемся алгоритмом кластеризации. Я использовал density-based clustering (DBSCAN). Идея его примерно такая:
То есть, если нам предсказали в какой-то точке 8 раз то, что тут есть перестроение налево то мыпонимаем, что да, перестроение действительно было. На рисунке горизонтальная ось – это скажем время, а красные точки – это определенное моделью перестроение налево для разных отрезков близких друг к другу.
Результаты работы классификтора:
Результаты работы можно визуально сравнить, увидев разметку событий, сделанную человеком и алгоритмом.
События размеченные человеком:
И моделью:
Тут видно что модель пропустила перестроение налево после первого поворота направо и добавила перестроение налево после поворота налево. Но, посмотрев видео, там эта ситуация кажется спорной, траектория действительно похожа на перестроение налево :) Ну и дальше пропустила поворот и в момент парковки машины решила, что я поворачиваю.
Вот видео этого участка (лучше смотреть в hd, чтобы было видно график):
Какова же точность классификатора? Для test set цифры следующие:
Тут приводятся цифры для всех событий, которые были сделаны машиной за два часа: все перестроения, повороты, обгоны. Число правильно и неправильно определенных событий.
Test set – это данные, на которых мы не учились и по которым не корректировали никак нашу модель и алгоритм кластеризации.
Correct type:
59 – столько событий было определено корректно
Wrong type:
16 – столько событий было определено, но не корректно
False positive:
17 – столько событий нейронная сеть выдумала сама, на самом деле их быть не должно
False negative:
26 – события, которые не были определены моделью, но которые на самом деле есть
Correct percent
0.5 – процент точности включая False negative
0.6413043478260869 – процент точности не включая False negative. Метрика с таким подходом: “пропустила что-то и бог с ним, лишь бы неправильно не говорила”
В целом неплохо, учитывая что всего событий 10 (5 разных, которые делятся на левые и правые), то генератор случайных чисел выдавал бы нам точность порядка, скажем 10 процентов точности. А тут 50, что уже хорошо.
Конечно, цифры пока не позволяют говорить об использовании библиотеки в реальном времени, но уже позволяет собирать аггрегированную статистику и на ее основе делать какие-то выводы, но в плане реального времени ошибок пока еще много.
Под реальным временем я понимаю то, что работая на телефоне или другом устройстве, алгоритм надежно сможет говорить программе, что только что было произведено перестроение. Под агрегированной статистикой я понимаю некий алгоритм на сервере, который собирает эти события со всех устройств и делает на основе этого какие-то выводы.
Есть большое поле для улучшений и думаю что месяцев через 6-9 алгоритм может стать вполне пригодным и для использования в реальном времени.
Как выглядят разные события глазами нейронной сети
Вот так обобщенно выглядят события глазами нейронной сети. Это сильно обобщенное представление, на самом деле внутри оно намного более многогранно, но приведя к одной плоскости получается примерно такая картина:
Это графики бокового ускорения (помним, ось Y). Верхний ряд — это перестроения: налево и направо. Можно увидеть что при перестроении ускорение меняется от одной строны к другой.
Нижний ряд – повороты налево и направо, ускорение возрастает до какого-то значения и потом к концу маневра убывает.
Где посмотреть на проект
Проект находится здесь github.com/blindmotion/docs/wiki и мы были бы рады, если бы он пригодился вам. Он состоит из достаточно большого количества частей, каждая из них в отдельном репозитории, документация же по вышеобозначенной ссылке.
Что дальше
Дальше мы планируем улучшать классификатор, чтобы он мог точнее определять события. Когда это произойдет, то, наверное, мы попробуем сделать простое приложение для андроида, которое будет проговаривать произошедшее событие. Скажем, вы перестроились или повернули и приложение сообщило об этом.
Как вы можете помочь
Наш проект – это проект с открытым исходным кодом. Прежде всего вы можете помочь нам данными. Если вы можете установить на свой телефон видеорегистратор и программу для записи значений датчиков и включать их тогда, когда вы едете, мы были бы очень признательны и добавили бы вас в список контрибьюторов данных на гитхабе. Данные от других людей нам сильно нужны, потому что у вас скорее всего другой телефон, другая машина и другой стиль вождения. Это позволит модели учиться на различных данных.
Также нам можно помочь с разметкой этих данных в нашем дэшборде, это не самое увлекательное занятие, нужно на видео размечать такие события как перестроения, повороты и прочее, но если у вас есть желание помочь таким образом – то welcome :)
Ну и конечно же вы можете принять участие в разработке самой модели и конечной библиотеки. Для работы над моделью порог вхождения – это возможность самостоятельно сделать модель, которая бы работала примерно так же как существующая или лучше по параметрам точности. Откуда брать уже размеченные данные для собственной модели я, естественно, расскажу.
Если вы хотите помочь каким то из способов – смело пишите в приват или на гитхаб или на электронную почту alexander996@yandex.ru.
Буду рад ответить на ваши вопросы в комментариях :) Спасибо за внимание.
FAQ.
Мы не ставим перед собой цель определять ямы и неровности на дорогах, это уже было сделано до нас :) но в целом на базе этой платформы, кажется, что это делается несложно.
Автор: lamerman
