Покоряем высоты для велонавигатора 2ГИС / forpes.ru

Главная
Покоряем высоты для велонавигатора 2ГИС

Покоряем высоты для велонавигатора 2ГИС +42

08.06.2022 09:00

akravchuk97 38 5700 Источник

26 мая 2ГИС зарелизил велонавигатор. Почитать про него можно тут. Одна из фич велонавигатора — график высот для построенного маршрута. С помощью него:

перечисляем;
как хорошо;
пользователю становится от него;
и выглядит чётко.

Эта статья о том, как мы получаем этот график:

Поймём, в чем задача

Дороги на карте 2ГИС рисуются по дорожному графу. Ребро графа — это участок дороги. Вершины графа — перекрёстки. Посмотрим на примере (место на карте):

Как видно из примера, геометрия ребра графа — это ломаная. Она хранится в таком виде: LineString (55 44, 55 43, 54 42), где через запятую идут координаты точек ребра (lat, lon). Почитать, что за LineString и что такое WKT можно на вики.

Нам нужно, чтобы геометрия ребра LineString (55 44, 55 43, 54 42) обогатилась высотами, то есть превратилась во что-то такое: LineString (55 44 100, 55 43 200, 54 42 300), где 100, 200, 300 — высоты в соответствующих точках.

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

Как используем данные GPS для получения высот

Пользователи 2ГИС, используя навигатор, присылают нам свои GPS-координаты. Смартфоны отдают нам обезличенные данные (lat, lon, alt). В будущем по пришедшему запросу (lat, lon) мы хотим возвращать высоту alt.

В одном квадратном метре континуум уникальных точек (lat, lon) (у float’ов конечная точность, но всё равно это очень много уникальных точек!). И не стоит надеяться, что два float’а (lat, lon), которые к нам придут в запросе, будут находиться среди наших наблюдений (lat, lon, alt). Поэтому данные (lat, lon, alt) нужно уметь индексировать по (lat, lon).

Для индексации мы используем пиксельную сетку от Гугла (прочитать про неё и проекцию меркатора можно в доке Google Maps и на вики). Если на пальцах, то мы покрываем карту такой пиксельной сеткой:

То есть у нас есть отображение

$f: (lat, lon) \longrightarrow (pix_x, pix_y)$

Видно, что точки с разными координатами могут попадать в один и тот же пиксель. Например, точки попали в пиксель .

Размер пикселя — варьируемая величина. В примере выше он около 30 метров.

В будущем мы хотим приписывать пикселю высоту в нём, например, брать среднюю высоту от точек, которые в него попали. Брать пиксель слишком большим — плохо. Если пиксель размером с Новосибирск, то на весь Новосибирск будет одно значение высоты. Слишком маленький пиксель тоже плохо, так как в слишком маленькие пиксели попадает слишком мало точек, данные о высотах получатся слишком шумными и будет много «пустых» пикселей.

У такой координатной сетки есть проблемы. На разных широтах размер пикселя будет разным (см. этот пункт на вики). Например, в Новосибирске размер пикселя может быть 5 метров, а в Москве — 6.

Есть способы индексации, которые устойчивы к этому. Например, от Убера (почему он не подошёл нам, станет ясно чуть позже).

Мы перешли от наблюдений вида (lat, lon, alt) к наблюдениям вида (pix_x, pix_y, alt). Теперь нам нужно присвоить каждому пикселю его высоту. В одном пикселе может находиться много различных наблюдений (lat1, lon1, alt1), (lat2, lon2, alt2), .... И это хорошо, потому что GPS штука шумная, и агрегации помогают его потушить. В каждом пикселе возьмем медиану высот от наблюдений, которые туда попали. Запомним также количество наблюдений в каждом пикселе, потом пригодится.

Цвет означает значение высоты: краснее — выше, зеленее — ниже. Берём медиану, а не среднее, чтобы лучше бороться с выбросами.

Ура, мы научились «красить» пиксели! Посмотрим на разукрашенный Владивосток:

Видно, что мы не красим те места, в которых никто не ездит (например, море :)). То есть сейчас, когда к нам придёт запрос (lat,lon), мы пойдём в соответствующий пиксель и возьмем оттуда значение высоты.

Небольшая мудрость между делом. Когда данных много, можно считать приближённые статистики, чтобы запросы кушали меньше ресурсов. Например, percentille_approx для медианы. Не тратим ману на то, чтобы быть точнее в пятом знаке после запятой :)

Проблемы при раскраске пикселей

Посмотрим на очевидные проблемы, которые могут возникать при раскраске пикселей:

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

Проблем несколько, решение одно — свёртки! Идея: будем смотреть не только на значение высоты в пикселе, но и на его окрестность. Введем обозначения для матриц и ядер, которые будут использоваться дальше:

— матрица, в которой элемент — это высота в соответствующем пикселе;
— количество наблюдений, по которым была посчитана высота в данном пикселе;
— ядро, которое мы будем призывать, когда нужно будет где-нибудь получить сумму;
— ядро учёта близости. Когда мы считаем высоту в данном пикселе, мы с бо́льшим весом учитываем значение высоты в нём и с меньшим — значение высоты в окрестности этого пикселя.

На схеме матрицыи нарисованы как матрицы $3\times 3$ . На самом деле, это большие матрицы (у нас же очень большая «раскрашенная» высотами картинка). Мы используем ядра $5\times 5$ , здесь — $3\times 3$ , чтобы я не умер от рисования.

Если в матрицев пикселе стоит None, то встоит 0. Считаем, что $None\cdot 0 = 0$ .

Решаем проблемы 1 и 3: пропуск и резкий переход

Перед тем, как переходить к формулам, дам немного интуиции.

— высота, — количество наблюдений, по которым считалась медиана.

Пусть мы не знаем высоту в пикселе с вопросиком. Как мы можем восстановить её значение? Можно написать такое выражение:

$a_\color{red}{?}=\sum w_i a_i, \sum w_i=1$

где— значения высот из окрестности неизвестного пикселя. Выражение говорит нам, что мы пытаемся восстановить значение пикселя по соседям с некоторыми весами. Как выбрать весаБудем отталкиваться от двух утверждений:

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

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

Интуиция дана, теперь покажу, как такое организовать:

В матрицеуже не может быть пикселей с так как $None\cdot 0=0$ .

Свернём матрицус ядром:

Теперь свернём матрицус ядром:

И поэлементно разделим матрицу $(A*C)\star k_d$ на матрицу $C\star k_d$ :

Здесь, что называется, нужно посмотреть на ответ (*) и понять, что он значит. Несколько фактов:

Матрицаимеет размерность метров.
Матрица(количеств) имеет размерность «штуки». Сейчас считаем «штуки» размерными :).
Ядро весовсчитаем безразмерным.

Мы получили размерность $\frac{\text{метры} \cdot \text {штуки}}{\text{штуки}} = \text{метры}$ . Это размерность высот.

Если посмотреть повнимательнее, то значение в пикселе равно взвешенному среднему значению высот в окрестности данного пикселя. Вес тем больше, чем ближе сосед и чем по большему количеству наблюдений в нём получена высота. Звучит как то, что нужно :).

Там, где делим на ноль, выставляем значениевысоты. Деление на ноль означает, что в окрестности пикселя нет ни одного значения высоты $\Rightarrow$ мы ничего не знаем о высоте в пикселе.

Проблема с пропусками решилась — пропуск заполнится, если в окрестности есть пиксели с заполненной высотой.

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

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

Например, перед всеми вычислениями с матрицами сделать $C_{ij} = min(C_{ij}, 1000)$ . Теперь матрица $[(A*C) \star k_d] \backslash [C\star k_d]$ — это наша матрица с высотами. Обозначим её $A_{final}=[(A*C) \star k_d] \backslash [C\star k_d]$

То есть получение высоты для ребра сейчас будет выглядеть так:

Переводим координаты (lat, lon) в (pix_x, pix_y).
Значение высоты в (pix_x, pix_y) спрашиваем в матрице $A_{final}$ .

Разбираемся с проблемой №2: как бороться с выбросами в пикселе

Вспомним, как учат искать выбросы в выборке в школе:

$z_{score} = \frac{x - \overline{X}}{\sigma_X}, |z_{score}| > thr \Rightarrow \ outlier$

В наших обозначениях— это значение высоты в пикселе, а выборка— это окрестность этого пикселя.

Лайк, если тоже обожаешь считать статистики по выборкам из 9 элементов :). А вообще, явные выбросы ловятся даже такой небольшой выборкой.

Заметим, что пиксели не входят в выборкуравноправно. Пусть один пиксель был посчитан по миллиону наблюдений, а второй — по десяти наблюдениям. Первый пиксель представляет гораздо большее количество наблюдений, поэтому в принятии решения мы должны опираться больше на значение высоты именно в первом пикселе . В этом нам поможет матрица, в которой записаны количества наблюдений.

Попробуем сообразить выражение для $z_{score}$ через наши матрицы и ядра.

$\overline{X}$ :

Заметим, что в текущей постановке мы пытаемся определить, верим мы пикселю или нет, поэтому свёртки с ядромиспользовать не будем. Опять поумножаем, посворачиваем и поделим:

$[(A\star C) \star k_s] \backslash [C\star k_s]$ — это матрица, где в пикселе написана оценка высоты, посчитанная по его окрестности. В терминах формулы $z_{score} = \frac{x - \overline{X}}{\sigma_X}$ элементы матрицы $[(A\star C) \star k_s] \backslash [C\star k_s]$ — это.

Тогда по формуле среднее = сумма/количество элементов получим матрицу $\overline{X}$ :

$\sigma_X:$

По формуле из школы:

$\sigma_X = \sqrt{(\frac{1}n \sum_i (x_i - \overline{X})^2)}$

Решение, которое сразу приходит в голову:

из матрицы $[(A\star C) \star k_s] \backslash [C\star k_s]$ вычтем матрицу $\overline{X}$ . Возведём в квадрат, ядромсделаем сумму, потом поделим наи возьмём корень. Мы так и сделаем, но сначала оговорка. В формуле для стандартного отклонения $\overline{X}$ одинаковое для каждого. А в нашем случае каждомусоответствует свой $\overline{X_i}$ :

Наш выбор.

Считать формулу для стандартного отклонения по-честному — долго, потому что ~~потому~~ питон. Пока мы обходимся векторными арифметическими операциями и свёртками. Это быстро. Но даже «поломанное» выражение всё равно хорошо детектит выбросы. Тогда $\sigma_{X}$ можем записать как:

Операции возведения в квадрат и взятия корня поэлементные ~~сегодня без жордановых форм.~~ Дальше матрица $z_{score}$ получается из матриц $[(A\star C) \star k_s] \backslash [C\star k_s]$ , $\overline{X}$ , $\sigma_X$ поэлементными вычитаниями и делениями.

Таким образом для каждого пикселя мы научились приближённо считать его $z_{score}$ , а значит, научились отметать выбросы. В пикселе-выбросе полагаем $A_{ij}=None, C_{ij}=0$ .

На всякий случай уточню, что сначала мы убираем выбросы (проблема 2), а затем начинаем лечить проблемы 1 и 3.

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

Осталось сказать, что обрабатывать матрицу $A_{final}$ целиком не надо. Все пиксели земного шарика не поместятся в оперативке. $A_{final}$ разбивается на тайлы (подматрицы размера $256\times 256$ пикселей), в которых у нас есть точки GPS — так она и хранится на диске. Все матричные операции выше проделываются над тайлами. Для корректной обработки крайних пикселей при обработке тайла подтягиваются его соседи.

Высотные развязки и тоннели

Проблему высотных развязок и тоннелей проще всего показать на конкретном месте:

Автомобили, которые едут по мосту и под ним, будут иметь одинаковые координаты (lat, lon). При этом значения высот, которые они будут отдавать, сильно отличаются. Кроме того, под мостом GPS может работать хуже. Тогда возможно несколько неприятных вариантов:

По мосту едет сильно больше машин, чем под мостом.

Для тех, кто на мосту, всё ок. У тех, кто едет под мостом, в графике высот будет резкий подъём, а затем резкий спуск.

Под мостом едет сильно больше машин, чем по мосту

Для тех, кто едет под мостом, всё ок. У тех, кто едет по мосту в графике высот будет резкий спуск, а затем резкий подъем;

Сверху и снизу машин плюс-минус поровну.

И те, и другие не будут рады графику высот, который увидят :)

Посмотрим на карту 2ГИС в каком-нибудь месте с высотной развязкой:

По карте сразу понятно, что одна дорога идет над другой.

Так нарисовать получилось не случайно. Каждое ребро графа содержит целочисленное поле zet_level. Оно помогает нарисовать одну дорогу над другой в случае, когда дороги пересекаются по широте и долготе, но одна дорога проходит над другой. Как раз наш случай.

edge1.zet_level > edge2.zet_level $\Rightarrow$ рисуем edge1 поверх edge2

То есть в наших данных есть информация, что одно ребро находится над другим ребром. Используем её, чтобы решить проблему с высотными развязками.

Алгоритм будет строиться вокруг простого утверждения:

Алгоритм

Каждое ребро графа состоит из точек. Присвоим каждой точке графа zet_level, равный zet_level’у её ребра:

Точку ребра назовем плохой, если в её окрестности есть точки с zet level’ами, отличными от zet level’а этой точки. Хорошей — иначе. Пример:

Пример классификации точек на плохие-хорошие для трёх рёбер:

Для хорошей точки мы можем доверять высоте, для плохой — нет. Высоту для плохой точки нужно корректировать. Как корректировать плохую точку? Будем аппроксимировать ее высотами хороших точек.

Изначнем обход в ширину нашего графа.
Если ушли отслишком далеко, из такой точки не продолжаем обход.
Если дошли до хорошей точки, то запоминаем её высоту и расстояние отдо неё по графу:. Если отможно дойти донесколькими путями, то взаписываем минимум из расстояний.
Когда обход закончен, у нас есть набор точек. Высоту в точкеполучим взвешенным усреднением высот в точках(чем дальше, тем меньше вес).

Заметим, что важно брать именно расстояние по графу, а не евклидово расстояние между точками. В примере выше $euler\_dist(p_0, p_3) < euler\_dist(p_0, p_1)$ , но мы не взяли точкудля аппроксимации. Это хорошо, потому чтолежит на более «высоком» ребре, чем точка. Мы не взяли её, потому что до неё нет короткого пути по графу. А если бы считалось евклидово расстояние, то точкаиспользовалась бы для корректировки.

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

Решим эту проблему введением виртуальных точек на ребре.

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

Точкиплохие, так как в их окрестностях лежат точки с другим zet level (зелёные точки на жёлтом ребре).

Точкихорошие, так как в их окрестностях лежат только точки с теми же zet level, что и у них (точки).

Таким алгоритмом лечатся не все высотные развязки. Плохую точку может быть просто нечем аппроксимировать (панорама).

Тут мудрость Конфуция не работает. Пойдём вперед — окажемся под мостом. Назад — тоже. В точках, которые не можем скорректировать, считаем, что не знаем значения высоты. Честно говорим об этом пользователю:

Тоннели

Внутри тоннелей не ловит GPS — это хорошо видно на второй картинке. Тепловая карта точек GPS (чем ярче, тем больше ездили) демонстрирует, что из тоннелей ничего не приходит. А точки GPS, которые попадают на тоннель — это либо шум с соседних дорог, либо загулявшие пешеходы, которые идут над тоннелем.

2ГИС рисует тоннели особым образом (прозрачненько), а значит, у нас есть информация о том, что данное ребро графа — тоннель. В рёбрах-тоннелях заполняем высоты None.

Актуализируем данные высот

Перестроенные рёбера

В дорожном графе 2ГИС могут быть неточности. Например, ребро в графе может быть смещено относительно реальной дороги:

В этом примере красно-жёлтые точки — это то, где ездят люди (GPS), а синим нарисованы ребра, где они должны ездить, согласно нашему графу. Такие расхождения мы исправляем, но ещё не до всех добрались. В этом примере нужно выделенные рёбра подвинуть вправо и вниз.

Так же, например, в графе могут отсутствовать какие-то дороги:

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

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

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

Актуализация данных высот

Напомню, что данные о высотах хранятся в матрице $A_{final}$ :

Когда автомобили начнут ездить по свежепостроенной дороге, у неё не появится высот, если не обновлять матрицу. Поэтому раз в несколько месяцев будем обновлять $A_{final}$ с учётом новых наблюдений и, соответственно, будем обновлять дорожный граф.

Как понять, что становится лучше

Я рассказал о нескольких алгоритмах. Как понять, что они улучшают ситуацию относительно решения «в лоб»?

Это большая боль в этой задаче. У нас нет возможности получить точные значения высот для всех рёбер в каком-нибудь городе. В терминах машинного обучения это значит, что у нас нет $y_{ground \_ truth}$ для подсчета честных метрик. Будем изворачиваться :)

Есть открытые источники с данными о высотах. Им верить можно не всегда, данные о высотах в них зачастую неактуальны (если построили новую высокую дорогу, в источнике это не отразится). Но есть области на карте, где новые дороги не строились много лет, и мы об этом точно знаем. В таких областях мы можем взять из открытых источников перепады высот в качестве $ground \ truth$ и сравнить с перепадами высот, которые получились у нас.
Также на помощь приходят различные прокси-метрики качества, посчитанные по графу. Приведу пример одной из них. Пусть есть ребро длиной 5 метров, а перепад высот между его крайними точками — 100 метров. В реальности такое ребро просто не может встретиться. А из-за выбросов в GPS — запросто. При работе над алгоритмами очистки выбросов можно считать долю ребер, у которых отношение перепада высот к длине больше некоторого порога, $\frac{|\Delta alt|}{length} > thr$ . Если этот процент уменьшается, это косвенно сигнализирует нам, что новый алгоритм очистки выбросов лучше предыдущего.
Корректировка высотных развязок. Можно самим наковырять пару сотен высотных развязок. Для каждой развязки можно добыть фотографий, чтобы понять, как она выглядит, и на глаз прикинуть, сколько метров между дорогами «над» и «под». Затем посмотреть, что предсказывалось до корректировки и после. И делать выводы о том, насколько корректировка улучшает ситуацию.

Потянулись, улыбнулись,

Рефлексируем

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

Спасибо за внимание!

Титры…

Сцена после титров

Приручаем GPS

Возьмем какое-нибудь место на карте, в котором нет перепадов высот. Например, это (панорама).

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

Значения высот разбились на два кластера-гауссианы. Расстояние между центрами этих кластеров около 35 метров. Но рядом нет никакой горы в 35 метров!

Кластеризуем значения высот (ого, мне наконец-то пригодился EM-алгоритм! :))

Кластеризация говорит, что во втором кластере лежит ~20% наблюдений. — основной. Авносит шум. То есть сейчас каждое пятое наблюдение вносит шум.

Данные (lat, lon, alt) высчитываются на устройстве из спутниковых сигналов и показаний других сенсоров телефона, а затем отдаются нам (почитать про разные приложения для измерения высоты).

Сырых наблюдений со спутников у нас нет, то есть телефон здесь для нас — чёрный ящик, который перемалывает сигналы GPS и показания других сенсоров в. Отсюда напрашивается очевидная гипотеза: один кластер чёрных ящиков перемалывает одним способом, а второй — другим. Например, одни Android’ы могут считать высоту относительно геоида, а другие — относительно эллипсоида WGS. Либо у одной группы телефонов у высоты один «ноль», а у другой группы — другой. Либо отвалился какой-то сенсор и есть режим работы без этого сенсора, который возвращает другие значения. Это мои догадки, они могут быть неправильными :)

Перейдем к фактам:

Есть два кластера. Размер второго сильно меньше размера первого, но он нам портит жизнь, потому что вносит шум.
Два кластера возникают из-за того, что черный ящик из-за каких-то факторов (версия чего-нибудь, отвалился/прицепился барометр, просто софт разный и т.д., сейчас это не важно) может вычислять высоту двумя разными способами.
По имеющимся у нас данным с телефона мы не можем однозначно сказать, из какого кластера к нам пришла высота.
Маленький кластер нужно убрать!

Помимо значения высоты alt к нам так же приходит значение altitude accuracy. На самом деле, получаемая высота — это не точечное значение, а отрезок, в котором с некоторой вероятностью находится значение высоты.

То есть если к нам пришло alt = 50m и altitude accuracy=5m , это надо интерпретировать как «высота, вероятно, лежит в круге с центром 50 метров и радиусом 5 метром». Чем больше altitude accuracy, тем меньше смартфон уверен в отдаваемой высоте.

Рассмотрим такую гипотезу:

— телефон находится в нормальном состоянии.

— когда у телефона нет какого-то сенсора, например, не работает барометр. И из-за этого он вычисляет высоту другим способом.

Если у телефона что-то не работает, логично предположить, что он должен быть меньше уверен в значениях выдаваемых высот. То есть altitude accuracy` должно быть больше. Проверим это. Фильтранём высоты по $altitude \ accuracy < 4$ (в графиках с кластерами выше фильтровалось по $altitude \ accuracy < 10$ ):

Огонь, горбик второго кластера стал меньше! Сейчас ~10% высот находятся во втором кластере, раньше было 20%. То есть для большого количество телефонов показания с большим altitude accuracy можно интерпретировать не как «высота такая-то $\pm$ 5 метров», а как «у меня свистанула фляга и я пошел во второй кластер».

Сейчас мы рисовали гистограмму высот для всех моделей телефонов в кучу. Посмотрим на гистограммы высот в разрезе отдельных моделей телефонов.

$model\_id$ —некоторой конкретной модели телефона, например, Samsung Galaxy S22 Ultra или HUAWEI DUA-L22. Есть модели телефонов, у которых почти все наблюдения лежат только в «правильном» кластере:

Более жесткая фильтрация по accuracy на такие модели почти не влияет. А есть те, у кого почти все только в «неправильном», они делятся на два типа:

1. Фильтрация по accuracy полностью убирает «плохие» наблюдения с таких телефонов.

Фильтрация оставляет плотность почти такой, какая была.

Есть и такие, у кого и в том и в том кластере $\pm$ поровну. Здесь тоже два типа:

1. Фильтрация по accuracy оставляет только «хороший» кластер:

2. Фильтрация почти не меняет соотношение количества объектов в кластерах.

Сейчас мы можем разбить все модели телефонов на несколько классов:

Отдают правильный кластер.
Отдают неправильный кластер. Неправильные наблюдения фильтруются более жестким accuracy.
Отдают неправильный кластер. Неправильные наблюдения не фильтруются.
Отдают оба кластера. Неправильный кластер фильтруется.
Отдают оба кластера. Неправильный кластер не фильтруется.

Напомню картинку, когда мы фильтровали по accuracy все модели телефонов и получили меньший «горбик» второго кластера:

Теперь становится очевидно, что этот горбик остается из-за моделей телефонов классов 3 и 5. Выкинем такие модели и снова построим график с кластерами:

Успех, второй кластер почти испарился!

Но испарился он не бесплатно. Количество высот, которые мы используем, уменьшилось после манипуляций с более жёсткой фильтрацией по accuracy и фильтрацией моделей телефонов. Теперь оно составляет ~70% от изначального количества данных. Напомню, что изначально в «шумном» кластере лежало ~ 20% от всех данных. То есть на 20% отфильтрованного шума приходится 10% отфильтрованных наблюдений из правильного кластера. Здесь за одного битого пол небитых дают! Звучит неплохо :)

Напоследок отмечу, что расстояние между центрами кластеров может быть разным, в зависимости от выбранной точки Земли. Например, высоты первого кластера могут быть в среднем выше высот второго кластера на 30 метров в Новосибирске, но ниже на 15 метров в Москве.

Теперь точно всё, спасибо!

Комментарии (38)

oracle_schwerpunkte
08.06.2022 09:32
#24419494
+2
Вот бы еще маршрут можно было бы построить для велосипедов , который не превышал бы заданного уклона - ) Гораздо легче ехать полчаса в горку 7%, чем пытаться забраться в лоб на 18%.
1. BellaLugoshi
  08.06.2022 10:13
  #24419674
  +1
  пардон, я статью не читал, но я так и подумал, что всё делается для построения маршрута с ограничением уклона, для некоторых моделей электротранспорта это важно, странно что это и не реализовано, если судить по вашему комментарию.

Kekmefek
08.06.2022 09:36
#24419516
+3
Видно, что мы не красим те места, в которых никто не ездит (например, море :)

А зимой?)

Касаемо велонавигатора - для катающихся за городом рекомендую попробовать OsmAnd. В городах же 2gis лучшие.
1. SamaRazor
  08.06.2022 18:26
  #24421400
  Позанудствую - osmand - это просто враппер для Open Street Map (OSM) под Android (AND). Юзайте osm с любым враппером ;)
  1. Kekmefek
    09.06.2022 08:21
    #24422790
    +3
    Назвать OsmAnd "просто враппером", это конечно мощно с вашей стороны.
    
    Честно я не встречал более богатого на функционал картографического приложения для android, чем OsmAnd, даже среди коммерческих приложений.
    
    SamaRazor
    09.06.2022 22:15
    #24426034
    Ну, какой бы отличный там не был функционал, основная полезность карт в их точности, а именно геодату и, сотвественно, точность/детальность предоставляет OSM. Когда у гугла, дубльгиса и яндекса карты собственные, и гуй собственный.
    
    Kekmefek
    10.06.2022 06:49
    #24426532
    +1
    основная полезность карт в их точности
    
    Так я не про карты, а про приложения для пользования ими. Карту можно и напечатать)
1. Samid777
  09.06.2022 14:29
  #24424440
  +2
  Зимой обычно высота уровня моря примерно как раз и равна высоте уровня моря. Тоже можно не красить.

Tkachenko-Ivan
08.06.2022 10:18
#24419710
+1
Круто, присмотрюсь к определению высоты в пропущенных квадратах на основе вашего подхода со свёрткой. А кригинг рассматривали для той же задачи?
1. akravchuk97 Автор
  09.06.2022 05:36
  #24422550
  +1
  Мы разные способы сглаживания/интерполяции смотрели, но конкретно кригинг нет. Остановились на свёртках потому что это оочень дёшево вычислительно (для нас здесь это супер важно потому что данных - тьма), а заметной разницы в сравнении с более дорогими подходами не заметили

maledog
08.06.2022 10:57
#24419840
+7
Как по мне, так перепады высот это наименьшая из проблем. Лично я при прокладывании маршрута стараюсь пользоваться следующими правилами:
- минимум "колец" и транспортных развязок;
- минимум левых поворотов если нельзя избежать, то выбирать места где много автомобилистов поворачивают налево, или где удобно пользоваться пешеходными переходами.
- избегать мест где автомобили стоят в пробке
- избегать улиц, где остается только 1.5-2 полосы из-за припаркованных автомобилей.
- выбирать улицы с наименее интенсивным движением, при этом чтобы хорошо просматривалась правая сторона, чтобы не приходилось налетать на пешеходов выскочивших из-за кустов, или выезжающих автомобилистов выставивших пол капота на мою полосу.
1. akravchuk97 Автор
  09.06.2022 05:38
  #24422554
  +1
  Спасибо за столько конструктивных предложений! Про минимум левых поворотов - прям в сердечко:) Передам Ваши предложения в команду, которая занимается построением маршрутов
  1. DentonJC
    10.06.2022 09:27
    #24426776
    А они сами катаются хоть?

Akr0n
08.06.2022 11:02
#24419870
+3
Пользователи 2ГИС, используя навигатор, присылают нам свои GPS-координаты.

То есть для каждого пользователя 2ГИС на сервер постоянно пишется его «обезличенный» трек?? А если я не использую режим навигатора? Если не включаю отображение пробок?

i9i6
08.06.2022 11:11
#24419896
Всё бы ничего, но во Владивостоке одна велодорожка и на ней нет перепад высот. А если ездить по реальным маршрутам - перепадов всё равно не избежать. Если тебе нужно добраться с одной сопки до другой - прямой(кратчайший) путь и будет путём с минимальными перепадами.

Kwent
08.06.2022 11:46
#24420018
+9
Отличная статья, интересные решения, приятно читается, спасибо, пишите еще :)
1. adeshere
  08.06.2022 23:24
  #24422250
  +5
  Да, точно!
  
  Я читал Хабр с чужого компа, и специально залогинился, чтобы проплюсовать автора. Очень прозрачно, на понятном для всех примере изложены идеи, с которыми надо быть "на ты" при обработке реальных данных: сглаживание, фильтрация выбросов, и т.д. Но главное спасибо все-таки за так называемые "чудеса": двухмодальность распределения и "проблему мостов". Многие учебные курсы либо умалчивают о том, что в практической работе такие "чудеса" могут (и встречаются!) на каждом углу, либо упоминают об этом вскользь, так как считается, что подобная "проза жизни" недостойна внимания высокой теории. А ведь это на самом деле чуть ли не главное, чему надо учить всех, кто перешагнул самый-самый базовый уровень! Я много лет работаю с геофизическими временными рядами, и могу утверждать, что подобные "чудеса" - почти наверняка могут встретиться в любом, даже самом идеальном (казалось бы!) наборе данных. Нам-то понятно, что нет никакого смысла заниматься глубокомысленным анализом формальных статистик, пока данные не проверены на наличие аномалий такого рода. А вот в учебных курсах об этом пишут и говорят гораздо меньше, чем стоило бы. На этом фоне статья - это просто луч света в подземном царстве ;-) Так как в ней ненавязчиво, но очень доходчиво описана как рутинность таких проблем, так и методология работы с ними:
  
  1) обнаружить "странный" эффект;
  2) проанализировать (систематизировать);
  3) проинтерпретировать (докопаться до причин);
  4) учесть или исправить.
  
  Благодаря этому статья о решении конкретной задачи фактически превратилась в прекрасное наглядное пособие, которое дополнит любой учебник по анализу данных!
  
  Мое восхищение автору ;-)
  1. akravchuk97 Автор
    09.06.2022 05:40
    #24422558
    Спасибо! Да, в этой задаче (да как и в любой другой:)) было столько такой "рутины", что об этом было просто невозможно молчать:)
1. akravchuk97 Автор
  09.06.2022 05:38
  #24422556
  +1
  Спасибо!

Tarakanator
08.06.2022 14:57
#24420716
А вы не думали получать данные с пульсометра?
И вам информация(если я еду медленно, на высоком пульсе, значит еду в горку)
И мне (нужно приложение которое одновременно и маршрут покажет и пульс)
1. DentonJC
  10.06.2022 09:55
  #24426870
  И мощностномер ещё
  1. Tarakanator
    10.06.2022 10:05
    #24426898
    мощностномер реально редкая штука и обычно вроде не к смартфонам их цепляют. А фитнес браслеты распространены.

un7ikc
08.06.2022 15:32
#24420798
Интересно, вот только заметил одно, нет:
- спуск
- Крутой спуск
вместо этого - ровный участок, проверил это на обратном маршруте где был подъем и крутой подъем.

DrMefistO
08.06.2022 15:38
#24420820
+2
Извините, но не "выезжаем", а "по коням".

А так, спасибо за эту крутую функцию!

DevilDimon
08.06.2022 17:07
#24421154
+2
Статья огонь! Приятно видеть, что навигатор догоняет лучшие мировые решения и перегоняет их.

(Однако идея вставлять в статью панорамы от главного конкурента - не самая лучшая, надеюсь, это троллинг)
1. akravchuk97 Автор
  09.06.2022 05:48
  #24422564
  +2
  Спасибо!
  
  Да почему, панорамы не троллинг:) У нас нет такой фичи, а для "погружения" в конкретное место это отличный инструмент. В статье хотелось в первую очередь сделать более понятно для читателя. Ну и не думаю, что эффект от статьи может хоть как-то конкурировать с рекламными бюджетами Яндекса;)

DoubleTwelve
08.06.2022 17:07
#24421158
+2
по поводу 35 м, может быть связано с разной конвенцией у производителя телефонов, т.к. есть gps sea level и geoid sea level, который не эквиваленты: https://www.esri.com/news/arcuser/0703/geoid1of3.html
1. akravchuk97 Автор
  09.06.2022 05:50
  #24422568
  Да, вполне, спасибо. Интересно как тогда в таком случае интерпретировать эффект с повышением accuracy ????

unwrecker
08.06.2022 17:12
#24421186
+1
А можно списочек телефонов с хорошией/плохой точностью GNSS?

denisshabr
08.06.2022 22:33
#24422144
+1
Какие классные ваши внутренние скриншоты с облаком точек! Прямо как в ушедшей Strava, помогало найти секретные тропы и дорожки, которых нет ни на одних картах.

Хорошо бы увидеть список "плохих" смартфонов с gps, с разбивкой по кластерам. Чтобы знать, что не покупать.
1. akravchuk97 Автор
  09.06.2022 06:37
  #24422626
  Слушайте, спасибо, что написали про облака точек. Мне сейчас показалось, что было бы отлично, если бы такой слой был и в нашем приложении. Передам эту идею нужным людям:)
  
  Не ограничивайте себя в выборе телефонов:) Перепады будут правильными и в случае первого и в случае второго кластера, просто эти два кластера нельзя перемешивать друг с другом:)
  1. Kekmefek
    09.06.2022 09:10
    #24422940
    У яндекса кстати есть такое облако в "народных картах".
    
    Будет очень классно если это будет и у 2гис.

Soukhinov
08.06.2022 22:58
#24422192
сделать $C_{ij} = max(C_{ij}, 1000)$ .

Вы, наверное, имели в виду $C_{ij} = \min(C_{ij}, 1000)$ .
1. akravchuk97 Автор
  09.06.2022 05:55
  #24422572
  Да, описка. Исправил. Спасибо!

funca
09.06.2022 01:25
#24422390
+1
Я слышал, что погрешность определения высоты у бытовых GPS приемников может быть на порядок больше погрешности определения горизонтальных координат. Отчасти это связано с физикой, отчасти с двойным назначением самой системы. Вот тут например https://support.garmin.ru/support/solutions/articles/26000045353 пишут, что +-120 метров это в принципе нормально. А какой точности вы собираетесь достичь используя описанную методику?
1. akravchuk97 Автор
  09.06.2022 06:05
  #24422584
  +1
  В этой задаче нам по сути не важна абсолютная высота. Для того, чтобы увидеть перепады достаточно знать разницу между высотами в двух точках, т.е. относительную высоту. Мы сравнивали наши перепады с перепадами в данных, которые были получены при помощи топографической съемки и высоты в них считаются как раз относительно геоида. Смотрели в куче разных мест. Никакого "криминала" в +-120м не замечали. Различия в пределах пары метров на несколько км. длины пути в основном были
  1. funca
    09.06.2022 11:26
    #24423592
    +1
    Если погрешность в пару метров с точностью до известной константы, получается ваши самокатчики на пару с алгоритмом способны заменить дорогущую топосьемку (или у методики для такого применения есть какие-то принципиальные ограничения)?

Gemerus
09.06.2022 01:27
#24422398
Маршрут строит довольно "необычно", с точки зрения велосипедиста это интересная фича, кататься по разным улицам. Но, меня малость удивило, что приложение, при привязки к ВК, умудрилось подтянуть УДАЛЁННУЮ несколько лет назад фотогфию....да и данные о подписках и подписчиках тоже очень старые.

Покоряем высоты для велонавигатора 2ГИС +42

Поймём, в чем задача

Как используем данные GPS для получения высот

Проблемы при раскраске пикселей

Решаем проблемы 1 и 3: пропуск и резкий переход

Разбираемся с проблемой №2: как бороться с выбросами в пикселе

Высотные развязки и тоннели

Алгоритм

Тоннели

Актуализируем данные высот

Перестроенные рёбера

Актуализация данных высот

Как понять, что становится лучше

Рефлексируем

Сцена после титров

Приручаем GPS

Комментарии (38)

akravchuk97 Автор

akravchuk97 Автор

akravchuk97 Автор

akravchuk97 Автор

akravchuk97 Автор

akravchuk97 Автор

akravchuk97 Автор

akravchuk97 Автор

akravchuk97 Автор