Любой измерительный прибор, аналоговый или цифровой, показывает результат с определенной погрешностью и шумом.
Погрешность GPS-датчика определяется погрешностью самого датчика и такими факторами, как: ландшафт, скорость движения, количество и положение спутников.
В наше приложение Мы предоставляем пользователю возможность детально просмотреть маршруты его путешествий.
А если отобразить сырые, нефильтрованные данные, то окажется, что маршрут проходит не по дороге, а через здания или по воде, некоторые точки маршрута сильно удалены от соседних или даже отсутствуют части маршрута.
Думаю, ни для кого не секрет, что на рынке есть решения, предоставляющие сервис сопоставления карт. Он выполняет обработку координат и в результате выдает координаты, связанные с дорогой.
Однако ни один сервис не поймет специфику ваших данных, и результат обработки сырых данных может оказаться не лучшим.
В связи с этим мы разработали решение, которое позволило максимально фильтровать и накладывать данные датчиков на дорогах.
Входные данные
На момент разработки OBD-ключ передавал телематические данные на сервер в виде точек, каждая из которых имела следующие параметры:- Координаты, полученные с датчика GPS;
- Скорость, полученная от автомобиля;
- Обороты двигателя, полученные от автомобиля;
- Время конкретной точки.
Отметим, что алгоритм передачи не идеален, но в рамках конкретной задачи мы решили его не менять, т.к.
очевидно, что если передавать баллы по более совершенному алгоритму, то результат только улучшится.
Донгл также собирал такие данные, как: курс (вектор движения) и снижение точности (грубо говоря, точность GPS), но эти данные не передавались на сервер.
Алгоритм
Алгоритм, который мы использовали, можно разделить на две части:- Фильтрация данных;
- Сопоставление карт;
- Частичная обработка.
Мы решили использовать наши знания и сделать фильтрацию данных на стороне собственного сервиса.
Давайте посмотрим на простой пример маршрута: 
На графике показана скорость автомобиля, полученная ключом от автомобиля, и скорость, рассчитанная по GPS. Как видите, на графике много выбросов, как вверх, так и вниз.
На ум сразу приходят стандартные алгоритмы фильтрации: фильтр Калмана, альфа-бета-фильтр.
Мы с ними справились в первую очередь.
Однако такие фильтры показали себя не очень хорошо.
Причин этому было несколько: низкая частота и абсолютная неоднородность данных (сложно выбрать один модифицированный алгоритм с подходящей ошибкой), наличие преобразований входящих данных было недопустимо.
Очень простой линейный фильтр скорости показал себя намного лучше во время тестирования.
Суть алгоритма очень проста: для всех соседних точек вычисляем скорость с помощью GPS и сравниваем ее со скоростью, полученной от автомобиля, и если различия превышают допустимую погрешность, то выбрасываем одну из точек.
Вот псевдокод:
`for i in range(1, len(data)):
velocity_gps = calc_dist(data[i - 1].
lat, data[i - 1].
lon, data[i].
lat, data[i].
lon) / (data[i] - data[i - 1])
velocity_vehicle = (data[i - 1].
speed + data[i].
speed) / 2
relative_error = abs(velocity_gps - velocity_vehicle) / (velocity_vehicle)
if relative_error > 1.5:
data.remove(data[i])`
В результате фильтрации мы получаем данные без выбросов, при этом точки все равно не попадают на дорогу.
Однако перед процедурой сопоставления карт нам также следует проредить наши данные, поскольку нет смысла передавать 10 точек, лежащих на одной линии, когда для определения линии достаточно двух точек.
Однако не стоит переусердствовать с фильтрацией, поскольку сервис сопоставления карт может счесть наши данные шумом.
Для удаления ненужных точек мы использовали алгоритм Рамера-Дугласа-Пейкера, а точнее его слегка модифицированную версию.
Для пачки точек, упорядоченной по времени, вычисляем расстояние для всех точек до дуги, соединяющей первую и последнюю точки пачки.
Если расстояние от каждой точки меньше определенного значения E, то мы возвращаем только начальную и конечную точки пакета.
В противном случае делим пачку на две части, деление происходит в максимально удаленной от дуги точке, а затем повторяем процедуру.
Сопоставление карт В связи с тем, что карты для наших мобильных приложений и порталов предоставляет сервис Mapbox, было решено использовать их сервис сопоставления карт. Но мы сразу уперлись в ограничение — 100 баллов за запрос.
Даже с учетом фильтрации и уменьшения количества точек с помощью алгоритма RDP среднее количество на наших маршрутах составляет 250 точек.
Соответственно, нам нужно обрабатывать пакетно, плюс перекрывая все, т.к.
в некоторых случаях простая пакетная обработка приведет к ошибкам обработки.
Алгоритм пакетирования следующий:
- N – количество точек для перекрывающейся обработки;
- Разрезаем маршрут на отрезки размером не более 100-N;
- Затем мы обрабатываем первую партию;
- Берем последние N точек обработанных данных и вторую партию;
- Продолжаем до последней партии;
- Конечный результат состоит из Обработано1, Обработано2, Обработано3, Обработано4.
Следующей проблемой, с которой мы столкнулись, было определение точности данных.
API Mapbox требует указать точность передаваемых данных, несмотря на то, что в документе этот параметр указан как необязательный.
А если он не будет передан, то будет установлен из значения по умолчанию.
Параметр, отвечающий за точность, — gps_precision. Вот что об этом говорит документация: Целое число в метрах, указывающее предполагаемую точность используемого устройства слежения.
Используйте более высокие числа (5–10) для шумных трасс и меньшие числа (1–3) для чистых трасс.
Значение по умолчанию — 4. Однако на момент разработки сервиса мы не перенесли эти данные с ключа.
Из-за разреженной частоты данных не было возможности использовать алгоритмы определения уровня шума.
Таким образом, мы обработали определенное количество маршрутов и постарались найти наиболее подходящие параметры.
Но как выбрать лучший параметр для 1000 маршрутов? Делать это вручную нецелесообразно.
Оказалось, что этот процесс можно автоматизировать из-за специфики результатов при неудачно выбранном параметре.
Если вы выберете слишком маленькое значение параметра, куски маршрута могут исчезнуть, а если увеличить значение параметра, то появятся лишние петли.
Хорошо подходит для выявления таких случаев.
После обработки 1000 маршрутов и сравнения результатов с помощью алгоритма DTW стало ясно, что лучшие результаты получаются при значениях точности 3, 6, 10 (в разных случаях).
В результате, при отсутствии данных о точности от GPS, мы запускали обработку параллельно с тремя разными gps_precision (3,6,10), а затем выбирали лучший.
Также планировалось добавить отправку параметров разбавления с ключа, что значительно улучшило бы качество сервиса.
Частичная обработка Конечные точки маршрутов часто находятся в местах, где дорога не обозначена на карте (стоянки, дорожки между домами и т.п.
).
Алгоритмы сопоставления карт в таких ситуациях работают не очень хорошо, и хотелось бы максимально точно указать, где пользователь оставил свою машину.
Чтобы решить эту проблему, мы стали обрабатывать не весь маршрут, а только внутренние точки: отбрасываем начало и конец маршрута, затем добавляем к обработанным данным начало и конец исходного маршрута.
Начало и конец определяются так: берем 5% маршрута или часть до того, как скорость автомобиля превысит 10 км/ч.
Конечный результат
В конце хотелось бы продемонстрировать результат обработки маршрута.Как результат маршруты проезжают практически везде по дорогам, исчезли сильные шумы, восстановлены недостающие части маршрутов (езда по кольцу или мосту).
Автор: Кирилл Кульченков, Кульченков32 , старший разработчик программного обеспечения, Bright Box.
Теги: #карты #геолокация #карты открытых улиц #сопоставление карт #Алгоритмы #обработка данных #программирование #Алгоритмы #Геоинформационные услуги #Промышленное программирование
-
Руководство По Покупке Жесткого Диска
19 Oct, 24 -
Жалобы На Выбросы Являются Ложными
19 Oct, 24 -
«Я Обычный Стилус Для Емкостных Экранов»
19 Oct, 24 -
Концепт Xo-3 От Olpc
19 Oct, 24 -
Вебальта. Дата Центр
19 Oct, 24
