Приключения в программировании и разработке GPS: Учебное пособие по геопространственной информации

Все началось с похода в Збевницу более 10 лет назад. У меня был с собой новый GPS, а у моего друга GPS был подключен к телефону с Windows ME. Поход был отличным, но когда мы вернулись к нашим машинам, мы были удивлены, увидев, что один GPS заявил, что мы прошли 6,2 км, а другой сообщил о 6,7 км. Один утверждал, что наш набор высоты (т. е. сумма всех подъемов в гору) составил 300 м, а другой — 500 м.

Будучи программистом (и, в конечном счете, программистом ГИС), я сразу же был заинтригован этой проблемой. Я сказал себе: «Это не должно быть так сложно исправить с помощью простого скрипта». В конце концов, треки GPS — это просто список кортежей в виде (широта, долгота, высота) , верно?

Ну не совсем.

Так началось мое путешествие в увлекательный мир GPS-треков, ошибок отслеживания и, в более общем плане, программирования ГИС.

Геопространственные информационные системы (ГИС) — это огромная и сложная область, охватывающая картографические проекции и геодезические данные), обработку растровых и векторных данных и дистанционное зондирование. Всестороннее введение в эту область выходит далеко за рамки этой статьи. И поскольку сосредоточение внимания на конкретной проблеме часто может быть полезным способом познакомиться с новой областью, я представлю несколько конкретных проблем ГИС, с которыми я столкнулся, и некоторые возможные решения; а именно:

• Как распознавать, понимать и программно исправлять ошибки GPS-трекинга
• Как рассчитать и получить дополнительную полезную информацию из треков GPS

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

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

Ошибки высоты и идиосинкразии

Если вы живете в определенных частях мира, вы, возможно, заметили что-то странное в точности высоты GPS, когда вы записываете треки на свой смартфон. Когда вы проверяете высоты, они последовательно записываются как выше или ниже (на постоянную величину), чем правильная высота. Например, я живу в Вишняне (Хорватия), и мой Android постоянно сообщает мне, что я примерно на 35-40 метров выше фактической высоты.

Например, вот график высот по GPS из короткого похода, который я совершил несколько месяцев назад:

Здесь следует отметить две вещи.

Во-первых, «холм» в первой части записанных данных GPS был полностью сфабрикован устройством . Хотя график, казалось бы, указывает на то, что самая высокая точка нашего похода находилась всего в нескольких сотнях метров от начала, на самом деле это было примерно на 4 км позже.

Во-вторых, что, возможно, более важно (и не видно на графике), так это то, что весь график неточен . Значения высоты постоянно сообщались примерно на 30-40 метров выше, чем они были на самом деле, как мы обсудим более подробно далее в этой статье.

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

Ошибки повышения при запуске

По сути, существует два метода, которые устройства GPS используют для определения высоты: «высота GPS» (сообщается устройству спутниковой системой GPS) и «барометрическая высота» (рассчитывается устройством на основе показаний атмосферного давления). Ни то, ни другое не идеально.

Значения высоты GPS могут иметь много небольших ошибок (обычно в диапазоне +/- 10 м), которые могут быть особенно проблематичными, если позже мы решим вычислить кумулятивный прирост высоты. С другой стороны, барометрическая высота чувствительна не только к высоте, но и к погодным условиям, которые могут вносить свой собственный набор неточностей.

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

Постоянные неточности высоты GPS

Чтобы объяснить постоянную ошибку в сообщениях о высоте, нам нужно вернуться к географии нашей начальной школы. Учителя географии обычно объясняют, что Земля не сфера, а эллипсоид. Если бы это было на самом деле строгой правдой, высоту было бы легко вычислить математически. Но это не так. Земля неправильная; на самом деле это больше похоже на картофелину, напоминающую эллипсоид, чем на идеальный эллипсоид, а это означает, что для разработки ГИС вам нужен подробный набор данных о высоте почти для каждой точки на земле. В геодезии эталонный эллипсоид (известный как система отсчета) представляет собой математически определенную поверхность, которая аппроксимирует геоид, «более истинную» фигуру Земли.

Более того, важно признать, что даже эти датумы являются лишь приблизительными значениями фактической формы поверхности Земли. Одни работают лучше в одних частях мира, другие — в других. В качестве примера на изображении ниже (сгенерированном с использованием моей библиотеки Ruby) показано, как Земля отличается от одной из наиболее часто используемых моделей эллипсоидов (датума WGS84). Черные части представляют части Земли вверху, а белые представляют части Земли внизу, идеальный эллипсоид (контуры континентов и островов показаны красным).

Вы можете видеть, что Индия находится ниже эллипсоида WGS84 с южной частью, являющейся абсолютным минимумом (почти -100 метров!), а Европа выше него.

Поскольку устройства GPS низкого качества не используют такие данные, они просто вычисляют высоту, предполагая идеальный эллипсоид. Отсюда и их последовательная неточность.

Обнаружение и исправление ошибок высоты GPS

При разработке приложения GPS обнаружение того, что устройство, записавшее наш трек, имеет такие типы ошибок, может быть выполнено с использованием набора данных Earth Gravitational Model EGM2008, также иногда называемого набором данных «волнистости геоида». С помощью EGM2008 мы можем аппроксимировать разницу между фактической поверхностью земли и идеальным эллипсоидом.

Но чтобы узнать, есть ли на нашем GPS-треке эта ошибка, нам нужна еще одна вещь — реальная высота над уровнем моря. Общедоступной базой данных, которая может быть полезна для этой цели, является Shuttle Radar Topography Mission (SRTM). SRTM — это растровая база данных, которая предоставляет значения высот с разрешением примерно каждые 30 м (на экваторе) для США и каждые 90 м для остального мира. Например, при вычислении значений SRTM для точек на приведенном выше треке появляется другой график (синяя линия):

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

Между прочим, все это можно легко сделать с помощью моих библиотек GPS Python:

• srtm.py: парсер python для данных о высоте Shuttle Radar Topography Mission (SRTM)
• gpxpy: простая библиотека Python для анализа файлов GPX и управления ими (GPX, формат обмена GPS, представляет собой облегченный формат данных XML для данных GPS)

Для пользователей Ruby есть также моя библиотека парсера Geoelevations.rb для SRTM и EGM2008 undulations.

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

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

Сглаживание дорожки и удаление выбросов

Если бы футболист носил GPS-устройство и записывал игру, в результате трек был бы беспорядочным. Игровое поле будет плотно заполнено трассой, состоящей из множества крутых поворотов, ускорений и торможений.

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

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

 points[n].latitude = points[n-1].latitude * 0.3 + points[n].latitude * .4 + points[n+1].latitude * .3 points[n].longitude = points[n-1].longitude * 0.3 + points[n].longitude * .4 + points[n+1].longitude * .3

Чем больше коэффициент, тем больше влияние соответствующей соседней точки на измененное положение текущей точки. Коэффициенты, которые я использую в этом примере (0,3, 0,4, 0,3), несколько произвольны, но в большинстве случаев вы хотите, чтобы их сумма равнялась 1,0. (Более сложный подход, например, заключался бы в использовании расстояния между точками, а затем, чем ближе точка, тем больше соответствующий коэффициент.)

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

Обратите внимание, что трасса плохо следует по траектории, имеет много крутых и неровных поворотов, а иногда и вовсе отклоняется от ожидаемого пути.

После нескольких итераций «сглаживания» эта же дорожка преобразуется в:

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

Есть и другие вещи, которые вы можете попробовать. В некоторых регионах и для определенных приложений GPS вы также можете использовать данные OpenStreetMap (OSM), чтобы попытаться угадать правильный путь, а затем «привязать» точки к этой новой линии. Хотя это часто может быть полезно, это также может быть несовершенным, например, в случаях, когда данные OSM содержат две параллельные линии (например, шоссе и близлежащую дорогу) или множество близких путей.

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

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

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

• Вычисление общего прироста высоты. Чтобы вычислить общий прирост высоты на треке, недостаточно просто суммировать все небольшие «скачки» в гору, потому что они часто будут содержать небольшие ошибки. Сглаживание высоты перед суммированием часто может помочь решить эту проблему.
• Удаление выброса. После «сглаживания» точки, находящиеся слишком далеко от трассы, могут быть легко обнаружены. Затем часто можно предположить, что они являются выбросами, и пользователю может быть предложено спросить, следует ли их удалить.

Есть одна проблема, когда этот алгоритм не работает: в некоторых случаях GPS запишет ровный путь, но путь будет «смещен» на постоянную разницу в каком-то направлении. В таких случаях сглаживание может еще больше сгладить линию, но не исправит эту ошибку сдвига.

Еще одна, менее очевидная, но существенная проблема описанного нами упрощенного метода сглаживания состоит в том, что преобразование изменяет все (или почти все) точки на пути, даже те, которые могут не быть ошибочными. Хотя этот более простой подход, как правило, является разумным решением для среднего пользователя GPS, более сложные алгоритмы сглаживания, безусловно, применимы в программировании ГИС. В некоторых случаях может быть даже лучше просто удалить выбросы, не выполняя никакого сглаживания в зависимости от пользователя, устройства и приложения.

Определение максимальной скорости

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

Но помните, что мы имеем дело с недорогими GPS-устройствами и не полностью доверяем данным, что может существенно повлиять на наши расчеты. Если устройство записывает местоположение каждые 5 метров и в какой-то момент ошибается, сместив точку на 10 метров, то эта часть трека может показаться в 3 раза быстрее, чем было на самом деле!

Один из распространенных подходов в мире разработки ГИС состоит в том, чтобы извлечь все скорости между точками, а затем просто удалить первые 5% (т. е. использовать 95-й процентиль), надеясь, что исключенные 5% представляют собой большинство ошибок. Но это, по общему признанию, ненаучно и не гарантирует правильных результатов. Экспериментируя с этой техникой, я пробовал разные значения процентилей и обнаружил, что некоторые из них хорошо работают для одного устройства GPS, а другие — для других. Некоторые подходят для пеших прогулок, а другие для езды на велосипеде. Но в большинстве случаев результаты меня просто не устраивали.

Перепробовав множество алгоритмов, у меня сработало просто: добавить еще один фильтр для удаления экстремумов не только по скорости, но и по расстоянию, следующим образом:

1. Отсортируйте точки по расстоянию между соседями и удалите верхние 5%.
2. (Необязательно:) Сгладьте дорожку (по горизонтали и/или по вертикали).
3. Отсортируйте точки по скорости между соседями и удалите верхние 5%.

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

Вывод вида деятельности

Во многих случаях средней скорости достаточно для определения вида активности. Например, если средняя скорость составляет 5 км/ч, это, вероятно, пешеходная/походная дорожка, тогда как если средняя скорость составляет 30 км/ч, это, вероятно, велосипедная дорожка и так далее.

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

Соответственно, трек со средней скоростью 12 км/ч и максимальной скоростью 18 км/ч, вероятно, был записан во время бега, тогда как трек со средней скоростью 12 км/ч и максимальной скоростью 30 км/ч, вероятно, был записан во время катания на горном велосипеде. (Конечно, мы должны быть уверены, что наша расчетная максимальная скорость верна, чтобы это работало надежно.)

Процент видимого неба: умный прокси для обнаружения ошибок GPS

Точность каждого измерения GPS (т.е. широты, долготы и высоты) очень сильно зависит от количества спутников, которые были видны в момент записи. Поэтому, если бы мы могли каким-то образом определить, сколько спутников находилось «в поле зрения» во время каждой записи, мы могли бы использовать это как способ приблизить точность этой записи. Если бы мы каким-то образом знали, например, что все необходимые спутники GPS находятся в поле зрения, мы могли бы предположить высокую степень точности соответствующих данных GPS. И наоборот, если бы мы каким-то образом знали, что в поле зрения нет спутников GPS, мы могли бы предположить, что данные подвержены ошибкам.

Но прежде чем вы слишком воодушевитесь, подумайте о сложности попытки решить такую ​​проблему ГИС. Прежде всего, вам необходимо знать, с какими спутниковыми системами GPS может обмениваться данными ваше устройство. Есть оригинальная система глобального позиционирования США, европейская система Gallileo и российская система ГЛОНАСС. Некоторые устройства работают со всеми этими типами спутников, но многие — нет. И многие устройства даже не сообщают, какие системы они используют.

Но есть хитрый способ обойти эту сложность и получить приблизительное количество видимых спутников: использовать процент видимого неба в качестве показателя количества видимых спутников . Менее видимое небо означает, что наш GPS может «видеть» (или быть видимым) меньшее количество спутников. Но как мы можем вычислить процент видимого неба в любой точке Земли? Решение на самом деле довольно простое: мы можем рассчитать линию горизонта вокруг нас, используя данные SRTM, которые обсуждались ранее.

Например, это горизонт, если Вы находитесь в долине под Триглавом (самая высокая вершина Словении), рассчитанный с помощью SRTM:

(Кому интересно, мой код для создания этого изображения можно найти здесь.)

Это изображение в основном состоит из слоев равноудаленных графиков высот, если смотреть из центральной точки. Чем темнее синяя область, тем дальше слой высот; чем светлее синяя область, тем ближе слой высот. Самые высокие нарисованные точки представляют собой линию горизонта. Если спутник GPS находится ниже этой линии на небе, наше устройство, вероятно, не может его видеть (или быть видимым). (Обратите внимание, однако, что хотя изображение нарисовано как сплющенный прямоугольник, в действительности вам потребуются некоторые базовые знания сферической геометрии, чтобы правильно вычислить площадь ниже горизонта.)

Еще одна вещь, о которой следует помнить, это то, что это не серебряная пуля для обнаружения ошибок высоты GPS. Во-первых, большая часть Земли не гористая, и даже если они гористые, в нашей психологии преувеличивать высоту; фактический процент видимого неба превышает 75% в подавляющем большинстве населенных регионов . Но, тем не менее, этот метод может быть полезен в определенных ситуациях, например, в горных походах, когда вы можете перейти из глубокого каньона (с плохим приемом GPS) в горный хребет (где прием спутников, вероятно, намного лучше). Хотя этот метод не является абсолютной мерой количества ошибок в дорожке, он может быть полезным индикатором того, какие части вашей дорожки могут быть более подвержены ошибкам, чем другие.

Заворачивать

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

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

Во многих случаях методы, которые мы обрисовали в общих чертах, могут быть удовлетворительным «решением 80%», предоставляя пользователям недорогих GPS-устройств разумный уровень автоматического повышения точности их GPS-треков.