Aventuras na programação e desenvolvimento de GPS: um tutorial geoespacial

Tudo isso começou em uma caminhada em Zbevnica há mais de 10 anos. Eu tinha meu novo GPS comigo e um amigo meu tinha um GPS conectado a um telefone Windows ME. A caminhada foi ótima, mas quando voltamos para nossos carros, ficamos surpresos ao ver que um GPS dizia que tínhamos caminhado 6,2 km, enquanto o outro informava 6,7 ​​km. Um afirmou que nosso ganho de elevação (ou seja, a soma de todas as partes de subida de nossa caminhada) foi de 300m, enquanto o outro relatou como 500m.

Sendo um programador (e eventualmente um programador GIS), fiquei imediatamente intrigado com o problema. Eu disse a mim mesmo: “isso não deve ser tão difícil de consertar com um script simples”. Afinal, as trilhas de GPS são apenas uma lista de tuplas na forma de (latitude, longitude, elevação) , certo?

Bem, na verdade não.

E assim começou minha excursão ao fascinante mundo das trilhas de GPS, erros de rastreamento e, de forma mais geral, programação GIS.

Sistemas de Informação Geoespacial (GIS) é um domínio enorme e complexo, abrangendo projeções de mapas e datums geodésicos), processamento de dados raste e vecto e sensoriamento remoto. Uma introdução abrangente a este domínio estaria muito além do escopo deste artigo. E como o foco em um problema específico pode ser uma maneira útil de se apresentar a um novo domínio de qualquer maneira, apresentarei alguns desafios específicos de GIS que encontrei e algumas soluções possíveis; nomeadamente:

• Como reconhecer, entender e corrigir programaticamente erros de rastreamento de GPS
• Como calcular e derivar informações úteis adicionais de trilhas de GPS

Para começar, as trilhas de GPS não são apenas uma série de tuplas (latitude, longitude, elevação) . Muitos dispositivos habilitados para GPS também fornecem metadados como hora, frequência cardíaca e assim por diante. Alguns dispositivos GPS fornecem até informações sobre a precisão dos dados; também conhecido como “diluição de precisão”. Mas, infelizmente, a maioria dos dispositivos de GPS - especialmente os de baixo custo que dominam o mercado - não fornecem essas informações e ficamos com o desafio de deduzir a precisão do dispositivo por conta própria (e, idealmente, corrigir de acordo, sempre que possível ).

Vamos começar com um algoritmo possível para detectar dispositivos GPS de baixo custo (como a maioria dos smartphones) que geralmente possuem dados de GPS de baixa qualidade.

Erros de elevação e idiossincrasias

Se você mora em certas partes do mundo, pode ter notado algo estranho na precisão da elevação do GPS ao gravar trilhas com seu smartphone. Quando você verifica as elevações, elas são registradas consistentemente como mais altas ou mais baixas (por um valor constante) do que a elevação correta. Por exemplo, moro em Višnjan (Croácia) e meu Android continua me dizendo que estou cerca de 35 a 40 metros acima da elevação real.

Por exemplo, aqui está um gráfico de elevação GPS de uma curta caminhada que fiz alguns meses atrás:

Duas coisas a serem observadas aqui.

Primeiro, a “colina” na primeira parte dos dados de GPS gravados foi totalmente fabricada pelo dispositivo . Enquanto o gráfico parece indicar que o ponto mais alto da nossa caminhada estava a apenas algumas centenas de metros do início, na realidade foi cerca de 4 km depois.

Em segundo lugar, o que talvez seja mais importante (e não visível no gráfico) é que todo o gráfico é impreciso . Os valores de altitude foram consistentemente relatados como sendo cerca de 30 a 40 metros mais altos do que na realidade, como discutiremos com mais detalhes mais adiante neste artigo.

Este é o tipo de coisas que podem acontecer com dispositivos GPS baratos. E quando podemos detectar que a pista tem esses erros, podemos deduzir que o dispositivo é provavelmente um GPS de baixa qualidade, portanto, pode-se esperar que também tenha outros erros – não apenas erros de elevação – que são comuns a esses dispositivos.

Erros de elevação de inicialização

Existem essencialmente duas técnicas que os dispositivos GPS empregam para determinar a altitude: “altitude GPS” (conforme relatado ao dispositivo pelo sistema de satélite GPS) e “altitude barométrica” (calculada pelo dispositivo com base nas leituras de pressão barométrica). Nenhum é perfeito.

Os valores de altitude do GPS podem ter muitos pequenos erros (normalmente na faixa de +/- 10m), o que pode ser particularmente problemático se decidirmos posteriormente calcular o ganho de elevação cumulativo. A altitude barométrica, por outro lado, é sensível não apenas à altitude, mas também às condições climáticas, que podem introduzir seu próprio conjunto de imprecisões.

Alguns dispositivos, portanto, empregam uma abordagem híbrida, usando leituras barométricas para registrar a elevação, mas usando leituras de GPS para ajudar a (re)calibrar esses valores, para ajudar a contabilizar mudanças climáticas (pressão) e assim por diante. Com esses dispositivos, ao iniciar a pista, a elevação barométrica pode estar completamente errada, mas ao recalibrar com mais e mais dados de satélite GPS, os dados de elevação se tornam mais confiáveis. Portanto, não é incomum que tais dispositivos encontrem o tipo de erro de inicialização “fake hill” que observamos anteriormente em nosso gráfico de elevação.

Imprecisões de elevação de GPS contínuas

Para explicar o erro consistente no relatório de altitude, precisamos retornar à geografia do nosso ensino fundamental. Os professores de geografia costumam explicar que a Terra não é uma esfera, mas um elipsóide. Se isso fosse, de fato, estritamente verdadeiro, a altitude seria fácil de calcular matematicamente. Mas isso não. A Terra é irregular; na realidade, é mais como uma batata parecida com um elipsóide do que um elipsóide perfeito, o que significa que para o desenvolvimento de GIS você precisa de um conjunto de dados de altitude detalhado para quase todos os pontos da Terra. Na geodésia, esse elipsóide de referência (também conhecido como datum) é uma superfície matematicamente definida que se aproxima do geóide, a figura “mais verdadeira” da Terra.

Além disso, é importante reconhecer que mesmo esses dados são meras aproximações da forma real da superfície da Terra. Alguns funcionam melhor em certas partes do mundo e outros funcionam melhor em outras. Como exemplo, a imagem abaixo (gerada usando minha biblioteca Ruby) mostra como a Terra difere de um dos modelos elipsóides mais usados ​​(o datum WGS84). Porções pretas representam partes da Terra acima, e brancas representam partes da Terra abaixo, o elipsóide ideal (contornos continentais e insulares mostrados em vermelho).

Você pode ver que a Índia está abaixo do elipsóide WGS84 com a parte sul sendo o mínimo absoluto (quase -100 metros!) e a Europa está acima dele.

Como os dispositivos GPS de baixa qualidade não empregam tais dados, eles estão apenas calculando a elevação assumindo um elipsóide perfeito. Daí a sua imprecisão consistente.

Detectando e corrigindo erros de elevação do GPS

No desenvolvimento de aplicativos de GPS, a detecção de que um dispositivo que gravou nossa trilha tem esses tipos de erros pode ser feito usando o conjunto de dados Earth Gravitational Model EGM2008, também conhecido como conjunto de dados “geoid undulations”. Com o EGM2008, podemos aproximar a diferença entre a superfície real da Terra e o elipsóide ideal.

Mas para saber se nossa trilha GPS tem esse erro, precisamos de mais uma coisa – a elevação real . Um banco de dados público que pode ser útil para este propósito é o Shuttle Radar Topography Mission (SRTM). O SRTM é um banco de dados baseado em raster que fornece valores de elevação em uma resolução de aproximadamente a cada 30m (no equador) para os EUA e a cada 90m para o resto do mundo. Por exemplo, ao calcular os valores de SRTM para pontos na trilha acima, surge um gráfico diferente (a linha azul):

Um pequeno incômodo aqui são as bordas ásperas do gráfico, mas isso é facilmente suavizado. Observe que ao suavizar perdemos pouca (ou nenhuma) precisão, pois o próprio SRTM está apenas fornecendo pontos discretos em posições equidistantes, entre os quais precisamos interpolar em qualquer caso. Aqui está uma versão do gráfico anterior com uma sobreposição de linha vermelha representando os dados SRTM suavizados:

Tudo isso pode ser feito facilmente, aliás, usando minhas bibliotecas GPS Python:

• srtm.py: um analisador python para dados de elevação Shuttle Radar Topography Mission (SRTM)
• gpxpy: uma biblioteca python simples para analisar e manipular arquivos GPX (GPX, o GPS Exchange Format, é um formato de dados XML leve para dados GPS)

Para usuários Ruby, há também minha biblioteca analisadora Geoelevations.rb para ondulações SRTM e EGM2008.

Tendo detectado essas anomalias, dependendo do tipo de software com o qual estamos trabalhando, podemos (a) corrigir automaticamente os erros ou (b) simplesmente informar ao usuário que foram detectadas imprecisões em seus dados de elevação.

Além disso, como existem diferentes algoritmos que podem ser usados ​​para corrigir programaticamente esses erros de elevação do GPS, podemos dar ao usuário a opção de selecionar qual algoritmo empregar (por exemplo, o usuário deseja que usemos apenas os dados suavizados do SRTM "como está" ou o usuário deseja que usemos os dados SRTM para ajudar a corrigir as elevações relatadas pelo dispositivo).

Suavizando a pista e removendo outliers

Se um jogador de futebol usasse um dispositivo GPS e gravasse um jogo, a pista resultante seria uma bagunça. O campo de jogo seria densamente preenchido com uma pista composta por muitas curvas fechadas, acelerações e desacelerações.

Felizmente, a maioria dos casos em que as pessoas usam o GPS não terão esse mesmo padrão – as linhas de rastreamento do GPS (e acelerações) serão relativamente suaves. Nesses casos, os pontos erráticos em nossa trilha podem ser presumidos como induzidos por erros e, portanto, esses valores discrepantes podem ser razoavelmente removidos com uma função de suavização.

Como desenvolvedor de GIS, a suavização é mais comumente alcançada iterando pelos pontos e alterando as coordenadas com base nos valores das coordenadas vizinhas. Por exemplo, podemos alterar cada latitude e longitude com um algoritmo como o seguinte:

 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

Quanto maior o coeficiente, maior o impacto do ponto vizinho correspondente na localização modificada do ponto atual. Os coeficientes que uso neste exemplo (0,3, 0,4, 0,3) são um tanto arbitrários, mas na maioria dos casos você vai querer que a soma seja igual a 1,0. (Uma abordagem mais sofisticada, por exemplo, seria usar a distância entre os pontos e então, quanto mais próximo o ponto, maior o coeficiente correspondente.)

Aqui está um exemplo de uma faixa com muitos erros aleatórios:

Observe como a pista não segue bem o caminho, tem muitas curvas fechadas e irregulares e às vezes se desvia completamente do caminho esperado.

Após algumas iterações de “suavização”, essa mesma faixa é transformada em:

Embora isso seja muito melhor, ainda é reconhecidamente imperfeito. Observe que ainda há lugares (principalmente perto do meio do caminho) onde a pista ainda sai da estrada.

Há outras coisas que você pode tentar. Em certas regiões, e para certos aplicativos de GPS, você também pode usar os dados do OpenStreetMap (OSM) para tentar adivinhar o caminho certo e então “encaixar” os pontos nesta nova linha. Embora isso muitas vezes possa ser útil, também pode ser imperfeito, como nos casos em que os dados do OSM contêm duas linhas paralelas (por exemplo, uma rodovia e uma estrada próxima) ou muitos caminhos próximos.

Nesses casos, uma possível solução seria tentar detectar o tipo de atividade, utilizando algumas das técnicas discutidas adiante neste artigo. Se pudermos deduzir, por exemplo, que a trilha era uma trilha de caminhada e tivermos a opção de encaixar em uma rodovia ou caminho próximo, podemos assumir com segurança que a caminhada foi ao longo do caminho e não da rodovia.

Observe também que, embora este exemplo demonstre a suavização de coordenadas de superfície (ou seja, longitude/latitude), a suavização pode ser uma técnica igualmente válida para eliminar aberrações em dados de elevação ou temporais, ou mesmo em dados de frequência cardíaca e cadência de bicicleta.

Exemplos de benefícios adicionais e usos de suavização podem incluir:

• Calculando o ganho total de elevação. Para calcular o ganho de elevação total em uma pista não basta apenas somar todos os pequenos “saltos” para cima, pois eles geralmente contêm pequenos erros. Suavizar a elevação antes de fazer a soma muitas vezes pode ajudar a aliviar esse problema.
• Remoção de forasteiros. Após a “suavização”, pontos muito distantes da pista podem ser detectados mais facilmente. Muitas vezes, eles podem ser considerados valores discrepantes e o usuário pode ser solicitado a perguntar se eles devem ser removidos.

Há um tipo de problema em que esse algoritmo falha: em alguns casos, o GPS registrará um caminho suave, mas o caminho será “deslocado” por uma diferença constante em alguma direção. Nesses casos, a suavização pode suavizar ainda mais a linha, mas não corrigirá esse erro de deslocamento.

Um problema adicional menos óbvio, mas significativo, com a técnica de suavização simplista que descrevemos é que a transformação modifica todos (ou quase todos) os pontos no caminho, mesmo aqueles que podem não estar errados. Embora esta abordagem mais simples tenda a ser uma solução razoável para o usuário médio de GPS, algoritmos de suavização mais sofisticados são certamente empregáveis ​​na programação GIS. Em alguns casos, pode até ser melhor simplesmente remover outliers sem realizar nenhuma suavização dependendo do usuário, dispositivo e aplicativo.

Detectando a velocidade máxima

Detectar a velocidade máxima de uma trilha é bastante simples se tivermos as coordenadas e carimbos de data/hora de todos os pontos da rota. Basta calcular as velocidades entre os pontos e encontrar o valor mais alto. Parece direto.

Mas lembre-se, estamos lidando com dispositivos GPS de baixo custo e não confiamos totalmente nos dados, o que pode ter ramificações significativas para nosso cálculo. Se um dispositivo registra uma localização a cada 5 metros e em um ponto comete um erro ao perder o ponto por 10 metros, então essa parte da pista pode parecer 3x mais rápida do que era!

Uma abordagem comum no mundo do desenvolvimento de GIS é extrair todas as velocidades entre os pontos e, em seguida, apenas remover os 5% superiores (ou seja, usar o percentil 95) esperando que os 5% eliminados representem a maioria dos erros. Mas isso é reconhecidamente não científico e não garante resultados corretos. Na minha experiência com essa técnica, tentei valores diferentes para percentis e descobri que alguns funcionaram bem para um dispositivo GPS, alguns funcionaram bem para outros. Alguns funcionam bem para caminhadas e outros para ciclismo. Mas, na maioria dos casos, os resultados simplesmente não pareciam certos para mim.

Depois de tentar muitos algoritmos, o que funcionou para mim foi simples: adicionar outro filtro para remover extremos, não apenas por velocidade, mas também por distância, como segue:

1. Classifique os pontos por distância entre vizinhos e remova os 5% superiores.
2. (Opcional:) Suavize a pista (horizontal e/ou verticalmente).
3. Classifique os pontos por velocidade entre os vizinhos e remova os 5% superiores.

Pela minha experiência, esse algoritmo produz resultados bastante confiáveis, mesmo para faixas de dispositivos GPS baratos com erros aleatórios.

Tipo de atividade de dedução

Em muitos casos, a velocidade média é suficiente para determinar o tipo de atividade. Se a velocidade média for 5kmh, por exemplo, provavelmente é uma pista de caminhada/caminhada, enquanto se a velocidade média for 30kmh, provavelmente é uma pista de ciclismo e assim por diante.

Mas se a velocidade média for de 12 kmh, você não pode ter certeza se o usuário estava andando de mountain bike ou correndo. Nesses casos, a velocidade máxima às vezes pode ajudar a diferenciar os dois tipos de atividades. Especificamente, podemos usar o fato de que os corredores raramente atingem uma velocidade maior que o dobro da média, enquanto os ciclistas o fazem regularmente (por exemplo, ao descer uma ladeira em um caminho não muito desafiador).

Assim, uma pista com uma velocidade média de 12kmh e uma velocidade máxima de 18kmh provavelmente foi registrada durante a corrida, enquanto uma pista com uma velocidade média de 12kmh e uma velocidade máxima de 30kmh provavelmente foi registrada durante o mountain bike. (É claro que devemos ter certeza de que nossa velocidade máxima calculada está correta, para que isso funcione de maneira confiável.)

Porcentagem de céu visível: um proxy inteligente para detecção de erros de GPS

A precisão de cada medição GPS (ou seja, latitude, longitude e elevação) depende muito do número de satélites que estavam visíveis no momento da gravação. Então, se pudéssemos determinar de alguma forma quantos satélites estavam “à vista” no momento de cada gravação, poderíamos usar isso como uma forma de aproximar a precisão dessa gravação. Se de alguma forma soubéssemos, por exemplo, que todos os satélites GPS necessários estavam à vista, poderíamos supor um alto grau de precisão para os dados GPS correspondentes. Por outro lado, se de alguma forma soubéssemos que nenhum satélite GPS estava à vista, poderíamos supor que os dados são propensos a erros.

Mas antes de ficar muito animado, considere a complexidade de tentar resolver esse problema de GIS. Antes de tudo, você precisa saber com qual(is) sistema(s) de satélite GPS seu dispositivo é capaz de se comunicar. Há o Sistema de Posicionamento Global original baseado nos EUA, o europeu Gallileo e o sistema russo GLONASS. Alguns dispositivos funcionam com todos esses tipos de satélite, mas muitos não. E muitos dispositivos nem mesmo informam quais sistemas eles usam.

Mas há uma maneira inteligente de contornar essa complexidade e obter uma aproximação grosseira do número de satélites à vista: use a porcentagem do céu visível como um proxy para o número de satélites visíveis . Céu menos visível significa que nosso GPS pode “ver” (ou ser visto) por menos satélites. Mas como podemos calcular a porcentagem do céu visível em qualquer ponto da Terra? A solução é bem simples: podemos calcular a linha do horizonte ao nosso redor usando os dados do SRTM discutidos anteriormente.

Por exemplo, este é o horizonte se você estiver no vale abaixo de Triglav (o pico mais alto da Eslovênia) conforme calculado usando SRTM:

(Para os interessados, meu código para criar esta imagem pode ser encontrado aqui.)

Esta imagem é basicamente composta por camadas de gráficos de elevação equidistantes vistas de um ponto central. Quanto mais escura a área azul, mais distante a camada de elevação; quanto mais clara a área azul, mais próxima a camada de elevação. Os pontos mais altos desenhados representam a linha do horizonte. Se um satélite GPS estiver abaixo dessa linha no céu, nosso dispositivo provavelmente não pode ver (ou ser visto) por ele. (Observe, no entanto, que embora a imagem seja desenhada como um retângulo achatado, na realidade você precisaria de algum conhecimento básico de geometria esférica para calcular adequadamente a área abaixo do horizonte.)

Outra coisa a ter em mente é que isso não é uma bala de prata para detectar erros de elevação do GPS. Em primeiro lugar, a maior parte da Terra não é montanhosa e, mesmo quando o são, está em nossa psicologia superestimar as elevações; a porcentagem real do céu visível é superior a 75% na grande maioria das regiões habitadas . Mas, no entanto, esse método pode ser útil em certas situações, como caminhadas nas montanhas, onde você pode passar de um desfiladeiro profundo (com má recepção de GPS) para um cume de montanha (onde a recepção de satélite provavelmente é muito melhor). Embora esse método não seja uma medida absoluta de quantos erros a faixa possui, pode ser um indicador útil de quais partes da sua faixa podem ser mais propensas a erros do que outras.

Embrulhar

Discutimos alguns dos tipos mais comuns de erros de rastreamento de GPS esperados com dispositivos GPS de baixo custo. Fornecemos uma compreensão do que os causa, bem como algumas técnicas de programação GIS para corrigi-los.

Em alguns casos, podemos corrigir a pista com um alto grau de confiança. Em outros casos, podemos pelo menos alertar o usuário para partes da trilha que parecem questionáveis. Nos casos em que não temos certeza, há sempre a opção de permitir que o próprio usuário conserte a pista, auxiliado por imagens aéreas e mapas. Nossas estimativas probabilísticas podem ajudar a destacar as partes da pista onde detectamos uma maior probabilidade de erros.

Em muitos casos, as técnicas que descrevemos podem ser uma “solução de 80%” satisfatória, fornecendo aos usuários de dispositivos GPS de baixo custo um nível razoável de melhoria automatizada da precisão de suas trilhas GPS.