Привет, Хабр! Я Сергей Дождиков, руководитель аналитики заказной разработки. Недавно мы провели работу над мобильным приложением, которое позволяет регистрировать беговые тренировки и контролировать показатели в ходе тренировки и по окончании. Хочу поделиться с вами алгоритмом, который мы для этого разработали и рассказать, как решили возникшие сложности.

Если кратко. Можно улучшить вычисление суммарного подъема и спуска спортсмена в ходе беговой тренировки путем сглаживания профиля маршрута методом взвешенного скользящего среднего. В статье предложен способ взвешивания. Исходные данные для проверки алгоритма (обезличенные маршруты тренировок) подготовил Денис Варин (руководитель разработки бэкэнд для заказной разработки нашей команды).

Проблема

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

Часто мобильные приложения вычисляют подъем и спуск на основе геокоординат точек маршрута тренировки. А именно на основе высоты над уровнем моря. Проблема заключается в том, что гражданские реализации систем спутниковой навигации (GPS, ГЛОНАСС и др.) определяют высоту со значительной погрешностью - несколько метров или десятков метров. Таким образом, простое суммирование перепадов высот по маршруту тренировки дает неприемлемую ошибку и, как следствие, неадекватные показатели подъема и спуска бегуна в ходе тренировки.

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

Способ вычисления подъемов и спусков должен быть пригоден для использования в режиме, близком к реальному времени. Это важно для оперативной визуализации и контроля беговой тренировки.

Природа погрешности геокоординат (если интересно). Основную погрешность в определение геокоординат вносят следующие факторы:

  • погрешности в аппаратуре навигационного спутника;

  • погрешности в определении координат самого навигационного спутника;

  • задержка сигнала на трассе от навигационного спутника к потребителю (отражение сигнала от предметов, задержка в тропосфере и ионосфере и т.п.);

  • погрешности в аппаратуре потребителя (мобильном устройстве);

  • «закрытость» пространства на местности (навесы, козырьки, высокие здания, густые кроны деревьев, горы и т.п.);

  • небольшая высота навигационных спутников над горизонтом;

  • особенности взаимного расположения навигационных спутников относительно потребителя (попадание спутника в «тень» относительно потребителя, например, под эстакадой, под навесом);

  • искусственная погрешность, вносимая в координаты.

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

  • широту (Latitude);

  • долготу (Longitude);

  • высоту над уровнем моря (Altitude);

  • горизонтальную точность (Accuracy);

  • вертикальную точность (VerticalAccuracy).

Показатель вертикальной точности позволяет задать интервал [Altitude‑VerticalAccuracy; Altitude+VerticalAccuracy], в котором с уверенностью 68% (по данным реализации на 2022 г.) находится реальная высота мобильного устройства на уровнем моря. Можно предположить, что высота описываются случайной величиной, распределенной по нормальному закону N(Altitude, VericalAccuracy).

Идея решения

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

  • удаленности точки на маршруте от уточняемой (чем дальше от уточняемой точки, тем меньше вес данной точки);

  • погрешности высоты в точке (чем больше погрешность, тем меньше вес точки).

За основу был взят распространенный метод взвешенного скользящего среднего (англ. Weighted moving average). И был модифицирован в части:

  • способа задания окна усреднения;

  • весов точек в окне усреднения.

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

Рисунок 1 - Окно усреднения.
Рисунок 1 - Окно усреднения.

Алгоритм вычисления суммарного подъема, спуска маршрута беговой тренировки:

1. Для каждой i-й уточняемой точки маршрута i = 1…N вычислить взвешенную высоту wA(i) по следующей формуле:

wA(i)=\sum_{j \in ER(i)} Altitude_{j} \frac{cW(i,j)+cA(j)}{2},(1)

где

  • ER(i)=\big\{ k \in [1;N]:(L_i-R) < L_k < (L_i+R) \big\}– множество порядковых номеров точек маршрута, попадающих в R-окрестность i-й уточняемой точки (включая саму уточняемую точку);

  • L_i– дистанция i-й точки от начала маршрута беговой тренировки (по маршруту тренировки);

  • Altitude_j– высота j-й точки из атрибутов геокоординат точки;

  • cW(i,j)=\frac{1}{\mid i - j\mid + 1} * \frac{1}{\sum_{k \in ER(i)} \frac{1}{\mid i - k\mid + 1}}

    весовой коэффициент удаленности j-й точки от уточняемой i-й точки в окне усреднения cW(i,j)\in(0;1);

  • cA(j)=\frac{1}{AltitudeAccuracy_j} * \frac{1}{\sum_{k \in ER(i)} \frac{1}{AltitudeAccuracy_k}}

    весовой коэффициент погрешности высоты j-й точки cA(j)\in(0;1).

2. Просуммировать подъемы относительно уточненных высот точек маршрута по следующей формуле:

elev=\sum_{i=2}^N dW(i), (2)

где

  • dW(i) =\begin{cases}wA(i)-wA(i-1) & 0.02 < \frac {wA(i)-wA(i-1)}{L_i-L_{i-1}} < 0.4 \\0 & иначе\end{cases}

    подъем на отрезке [L_{i-1};L_i]маршрута беговой тренировки (отрезок с углом подъема <2% считается горизонтальным, с углом >= 40% – не беговой тренировкой или специальной беговой тренировкой).

3. Просуммировать спуски по формуле, аналогичной формуле (2).

Замечания к алгоритму.
Размер окрестности R существенно влияет на уточнение высот. Если предположить, что координаты точки маршрута на местности описываются случайной величиной, распределенной по нормальному закону N(Altitude, HorizontalAccuracy), то целесообразно установить R=3 \sigma =3 HorizontalAccuracy. При типовом (распространенном) значении HorizontalAccuracy = 10 м R = 30 м. Большие значения R позволяют лучше сгладить «выбросы» высот. Но растет риск снижения адекватности оценки профиля местности. Проще говоря, теряется информация о реальных резких перепадах высот на маршруте тренировки (например, в холмистой местности, в парке с лестницами и т.п.). Проверка алгоритма на практике показала, что хорошим значением является R = 50...60 м.

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

Бег по местности с продольным уклоном менее 2% считается бегом по горизонтальной поверхности. Бег по местности с продольным уклоном более 40% считается другим видом бега (т.н., «горный бег»). В этом случае тренировка имеет существенные отличия от обычной беговой тренировки.

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

Проверка на практике

Описанный выше алгоритм был реализован в виде приложения на Java и опробован на обезличенных беговых тренировках. Ниже приведено несколько показательных примеров (см. рисунки 2-7). На них изображен профиль высоты на маршруте беговой тренировки:

  • исходные данные высоты по геокоординатам с учетом погрешности (вертикальные желтые линии);

  • уточненные значения высот (разноцветная ломаная):

    • горизонтальные участки - отмечены зеленым цветом;

    • исключаемые участки (слишком крутые) - белым;

    • подъемы - красным;

    • спуски - синим.

Беговая тренировка вокруг пруда (см. рисунок 2). Местность - горизонтальная, без значимых подъемов и спусков. Спортсмен сделал три круга. «Выбросы» высоты, по-видимому, обусловлены отражением сигнала навигационных спутников от одного высокого здания, расположенного вблизи маршрута. Суммарный подъем - 11 м, спуск - 12 м. По «сырым данным» суммарный подъем - 204 м, спуск - 198 м.

Рисунок 2 - Вокруг пруда.
Рисунок 2 - Вокруг пруда.

Беговая тренировка в городе (см. рисунок 3). Местность - горизонтальная, без значимых подъемов и спусков. «Выброс» высоты, по-видимому, обусловлен эстакадой, под которой пробежал спортсмен. «Выброс» высоты сглажен и частично исключен из учета подъемов и спусков. Суммарный подъем - 26 м, спуск - 17 м. По «сырым данным» суммарный подъем - 50 м, спуск - 45 м.

Рисунок 3 -  Под эстакадой.
Рисунок 3 - Под эстакадой.

Пример практической невозможности повышения адекватности вычисления подъемов и спусков на основе только данных геолокации приведен на рисунке 4. Беговая тренировка в центре большого города. Местность - относительно горизонтальная, без резких подъемов и спусков. Несколько затяжных спусков. Большое количество «выбросов» высоты, по-видимому, обусловлено большим количеством зданий и других объектов, искажающих сигнал навигационных спутников за счет отражений. Суммарный подъем - 545 м, спуск - 639 м. По «сырым данным» суммарный подъем - 653 м, спуск - 655 м. Очевидно, подъемы и спуски не соответствуют действительности.

Рисунок 4 - В центре большого города.
Рисунок 4 - В центре большого города.

Беговая тренировка вокруг пруда (см. рисунок 5). Местность - относительно горизонтальная, без резких подъемов и спусков. Несколько затяжных не крутых подъемов и не крутых спусков. Суммарный подъем - 12 м, спуск - 11 м. По «сырым данным» суммарный подъем - 165 м, спуск - 169 м.

Рисунок 5 - Пруд, подъемы, спуски.
Рисунок 5 - Пруд, подъемы, спуски.

Беговая тренировка в гористой местности (см. рисунок 6). Возможно, крутой начальный отрезок обусловлен спуском бегуна по лестнице с высокого этажа здания или нахождением бегуна «в тени» (навесов здания). «Выброс» хорошо обработан алгоритмом. На рисунке 7 - отдельно показан начальный участок тренировки. Суммарный подъем - 56 м, спуск - 49 м. По «сырым данным» суммарный подъем - 101 м, спуск - 72 м.

Рисунок 6 - Тропа в гористой местности.
Рисунок 6 - Тропа в гористой местности.
Рисунок 7 - Начальный участок предыдущего маршрута (см. рисунок 6 выше).
Рисунок 7 - Начальный участок предыдущего маршрута (см. рисунок 6 выше).

Заключение

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

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


  1. Moskus
    27.09.2022 17:24
    +3

    Я правильно понимаю, что вы сравниваете данные до фильтрации с теми же данными после? А не с заведомо более точными данными, полученными каким-то иным способом?

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


    1. DoSergeyV Автор
      27.09.2022 18:04

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


      1. Moskus
        27.09.2022 18:10
        +1

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

        Это технический ресурс, вас поймут, не бойтесь подробностей. А вот в обратном случае, могут заподозрить в том, что показать кроме фильтруемых данных вам нечего (как это обычно бывает).


        1. DoSergeyV Автор
          27.09.2022 19:21

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


          1. Moskus
            27.09.2022 22:07
            +1

            При чём тут мобильное приложение? Графики сглаживания тоже не из него, вы же метод описываете. Метрологически значимая верификация без сравнения с заведомо более точными данными - невозможна.


          1. larasage
            28.09.2022 08:37

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


            1. DoSergeyV Автор
              28.09.2022 09:55

              Хороший вариант. Рассматривался. Но есть ограничения: санкции, необходимость постоянного доступа в Интернет, условия пользования сервисами Strava. Кроме того, маршрут может отсутствовать или совадать частично.


            1. Moskus
              28.09.2022 17:11

              И это также будет сравнением с набором с тем же порядком погрешности, а не с меньшим. Это тоже метрологически безграмотно для оценки метода.


              1. larasage
                29.09.2022 10:28

                Можно увидеть Ваш расчет погрешностей для обоих методов?


  1. Aspos
    27.09.2022 18:22

    Ещё один вариант -- купить спутниковые карты высот с точностью в метр. Есть карты выстот с которых уже здания и деревья повырезали. Они чуть дороже.
    На сервере можно проецировать тракторию на плоскость карты, обсчитывать перепады высот точно.
    Только там тоже надо будет чуть сглаживать иначе пути под мостом и т.п.


    1. DoSergeyV Автор
      27.09.2022 19:08

      Соглашусь. Это - перспективный вариант. Хотя и у него есть свои недостатки. Требуется постоянный доступ мобильного приложения в Интернет в ходе тренировки. Дополнительная нагрузка на сервер.


      1. Sazonov
        28.09.2022 10:32

        Зачем постоянный? Один раз сделать пост-процессинг.


        1. DoSergeyV Автор
          28.09.2022 10:37

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


          1. Sazonov
            30.09.2022 11:36

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


    1. larasage
      28.09.2022 08:41

      А эти карты актуальны для всей поверхности Земли? Или только для "цивилизованных" мест?


  1. mikelavr
    28.09.2022 10:29

    Пару лет пользовался для тренировок спортивными часами от Garmin без барометра. Неизвестно, как они сделали усреднение высоты по данным от GPS, но оно точно есть. Потом перешел на часы той же фирмы, но с барометром.

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

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

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

    К сожалению в телефоны барометр ставят очень редко.


    1. DoSergeyV Автор
      28.09.2022 10:41

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


    1. ITMatika
      28.09.2022 12:32

      С барометром тоже всё не так гладко, например, когда пересекаешь холодные реки/овраги. Сумму высот насчитывает гораздо больше фактических.


      1. mikelavr
        28.09.2022 14:27

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


        1. ITMatika
          29.09.2022 09:36

          Часы мочить не нужно.
          Когда катаешь по горным серпантинам на веле - аналогично, особенно в ветреный день, давление и высоты скачут очень прилично.


  1. Mishootk
    28.09.2022 20:21

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