Optimisation des trames NMEA pour GPS

A télécharger :

• PDF : Rapport du programme GPS sur PDA (NMEA) (3663 téléchargements )
• Excel VBA pour traitement trames GPS NMEA (523 téléchargements )
• Programme de Geofencing (avec sources) (965 téléchargements )
• SharpMap Mobile (609 téléchargements )

Executive summary

Mission

Analyse du marché de la téléassistance en Europe et principalement en France pour le développement d’un Bracelet Électronique pour l’Autonomie (BEA).

Étude, conception et développement des programmes préalable de ce projet de Recherche et Développement subventionné par la DGE (Direction Générale des Entreprises).

Au niveau technique, ma problématique principale fut d’optimiser les trajets GPS de manière à renvoyer les points les plus significatifs d’un parcours piéton.

Utilisateurs cibles

La solution s’adresse à toutes les personnes dépendantes qui puissent être confronté à des situations critiques nécessitant une aide médicale ou une prise en charge spécifique.

Le marché

Le marché de la téléassistance est en pleine croissance (10% par an) en France mais aussi dans toute l’Europe. D’ici à 2020, environ 30% des européens auront plus de 60 ans. En France, 225 000 nouveaux cas de personnes par an sont touchés par la maladie d’Alzheimer ou des maladies apparentés. La population de personnes dépendantes augmentera de 40 à 70% d’ici à 2040.

Outils

Projet développé sous Visual Studio en .NET à l’aide du langage C# pour une plateforme cible tournant sous Windows Mobile 6 avec le Compact Framework .NET version 3.5.

Introduction

Le nombre de personnes dépendantes dans le monde est en constante augmentation (1 nouveaux cas toutes les 7 secondes dans le monde). En Europe, plus particulièrement, la population âgée augmente dans tous les pays et la France, notamment, ne fait pas exception. Les changements de la société comme la réduction du nombre des aidants, l’allongement de la durée de vie, la diminution du nombre des professionnels de santé font que la téléassistance va prendre une place de plus en plus importante dans la vie de chacun, à la condition qu’elle réussisse à répondre aux défis du monde d’aujourd’hui.

Ainsi, le marché de la téléassistance est en pleine croissance. Dans ce contexte, des solutions basées sur les technologies de géolocalisation précises pourront permettre d’assurer la sécurité, que ce soit des personnes autonomes présentant une fragilité ou des personnes à forte dépendance. L’analyse de l’existant a montré qu’un bracelet montre porté au poignet est mieux à même de détecter les situations critiques grâce à un capteur de stress et à l’étude des activités quotidiennes d’une personne.

C’est pourquoi, Atos Origin ayant détecté cette opportunité souhaite développer un bracelet électronique qui puisse répondre aux besoins des malades et des aidants afin de prévenir les situations critiques (fugues, errances, chutes…).

C’est ainsi que le projet BÉA (Bracelet Electronique pour l’Autonomie) est né. Projet labellisé par 2 pôles de compétitivité Aerospace Valley et Cancer Bio Santé et subventionné dans le cadre du 7^ème appel à projet du FUI (Fonds Unique Interministériel).

C’est au sein de ce projet que j’ai évolué lors de mon stage de 6 mois à Atos Origin Integration qui a débuté le 01 mars 2009, stage s’intégrant bien à ma double formation (INSA – IAE) en nécessitant des compétences transversales à la fois en informatique et en management.

La première partie de mon stage exploitait les compétences acquises au cours de la formation en management de l’innovation à l’IAE, j’ai évalué les opportunités de marché pour la sureté des personnes âgées dépendantes. J’ai réalisé une étude de marché complète qui met en relief les débouchés éventuels et les recommandations à suivre. J’ai notamment du réaliser un dossier complet pour une demande de subventions auprès de la DGE.

Par la suite, j’ai réalisé les spécifications de la plateforme à développer ainsi qu’un programme sur PDA fonctionnant sous Windows Mobile. Ce programme permet de :

• récupérer les informations provenant de la puce GPS et de les compresser au maximum notamment en diminuant le nombre de points contenu dans un trajet pour limiter la bande passante utilisée ainsi qu’optimiser l’autonomie de la batterie
  
• Enregistrer les fichiers dans différents formats (NMEA, GPX, NMEA Optimisé)
  
• Afficher la cartographie correspondante au trajet en cours
  
• Afficher la constellation satellite (nombre de satellites, puissance du signal et positionnement)
  
• Afficher la boussole indiquant la direction actuelle
  

C’est donc cette 2^ème partie technique représentative de la formation d’ingénieur INSA que se propose d’illustrer ce rapport.

Étude sur les trajets GPS

La présentation du projet BÉA met en relief un enjeu majeur : la maitrise de l’autonomie du bracelet ainsi que de la bande passante pour l’envoi des données.

C’est ainsi que j’ai été chargé d’étudier les données GPS afin de minimiser le nombre de points significatifs d’un trajet. Travail essentiel pour la version 2 du bracelet où un programme complet sera développé par Atos Origin et devra prendre en compte l’ensemble des contraintes indiquées dans la partie précédente.

Dans ce contexte, j’ai d’abord choisi de réaliser un programme sous VBA à l’aide de Microsoft Excel afin d’analyser les trajets GPS. J’ai choisi de commencer sous Excel car je ne disposais pas encore de l’IDE Visual Studio permettant de développer en .NET (étant donné que la demande d’installation sur mon poste n’avait pas encore aboutie).

Le format NMEA

Les traces brutes GPS sont sauvegardées au format NMEA. La norme NMEA 0183 est une spécification pour la communication entre équipements marins dont les équipements GPS. Elle est définie et contrôlée par la National Marine Electronics Association (NMEA).

Type de trames

Il existe plus d’une trentaine de trames GPS différentes. Le type d’équipement est défini par les deux caractères qui suivent le $. Le type de trame est défini par les caractères suivants jusqu’à la virgule. Par exemple :

$GPRMC,180432,A,4027.027912,N,08704.857070,W,000.04,181.9,131000,1.8,W,D*25

est une trame GPS de type RMC. Chaque trame a sa syntaxe propre, mais selon le cas elles peuvent ou doivent se terminer, après le *, par une somme de contrôle qui permet de vérifier que la trame n’a pas été endommagée avant sa réception.

La trame RMC est une trame très courante qui donne les informations essentielles (RMC veut dire Recommended Minimum sentence C) :

Ce type de trame RMC donne les informations minimum recommandées dont les informations essentielles dont j’ai besoin pour l’étude des traces GPS.

Compression des trames

Le fait de ne prendre en compte que les trames RMC permet déjà d’optimiser la taille des fichiers NMEA : un fichier NMEA de 2621 lignes contient 306 lignes de trames RMC soit une optimisation de l’ordre de 88%.

Cependant, le programme final lira les informations de la puce GPS, où on récupère directement chaque information (latitude, longitude, altitude…), le but est alors d’optimiser le nombre de coordonnées (latitude, longitude) pour ne renvoyer que celles significatives.

Minimisation du nombre de points

Afin de renvoyer un minimum de données, il a fallu réfléchir à un algorithme permettant de minimiser le nombre de points. La solution retenue est simple mais néanmoins efficace : si la personne se dirige dans la même direction (par exemple 0° nord) pendant une certaine durée, l’algorithme devra prendre le premier et le dernier point et supprimer tous les points intermédiaires. Un GPS renvoyant généralement les coordonnées toutes les secondes (fréquence d’1 hertz), cette solution permet de supprimer un nombre non négligeable de points.

Pour l’illustrer, prenons un exemple :

Si on zoome un peu en haut à droite, on remarque toute une série de points alignés qui indique que l’appareil contenant la puce GPS se dirigeait dans la même direction pendant quelques secondes. Sur le morceau de chemin ci-dessous, les points en rouge sont ceux à supprimer ou plutôt à ignorer par le programme lors de la capture en temps réel des points et les points en bleu sont ceux à garder.

Malgré sa simplicité, cet algorithme permet une optimisation de l’ordre de 19%. En effet, il a été testé sur 18 trajets routiers dont les fichiers NMEA ont été récupérés et la moyenne du pourcentage d’optimisation global est de 19,11%.

Illustration 9 : Résultats trajets routiers optimisés

Cependant, à terme cet algorithme sera mis à contribution sur des trajets piétonniers, et son efficacité dépend du type de trajet, si l’utilisateur a un comportement balbutiant alors l’optimisation ne sera pas très efficace.

Nous avons donc testé l’algorithme sur un trajet piétonnier arbitraire qui contient 306 trames RMC, on obtient alors 293 trames RMC dans le fichier optimisé soit une optimisation de l’ordre de 4,25%. Toutefois ce pourcentage est relatif car ce trajet possède un nombre relativement faible de coordonnées GPS et cela s’explique par le fait qu’il ne dure que 5 minutes. On peut faire l’hypothèse que sur un trajet beaucoup plus long et donc plus représentatif, le nombre de points sera beaucoup plus conséquent et le pourcentage d’optimisation aussi.

Néanmoins, ce trajet piétonnier a permis de mettre en évidence le fait qu’on pouvait encore améliorer l’optimisation, j’ai donc rajouté dans le programme un paramètre appelé « seuil ». Ce paramètre est expliqué et illustré par la suite.

Algorithme d’optimisation

Comme illustré précédemment, on se base sur la « direction » (en anglais «bearing ») entre 2 coordonnées GPS ce qui permet de supprimer les points intermédiaires qui auraient la même direction que les points précédents. Le code ci-dessous montre une partie de l’algorithme d’optimisation :

Illustration 10: Portion de l’algorithme d’optimisation en VBA

On remarque que le programme prend une valeur appelée « Seuil », cette valeur permet d’être plus « indulgent » concernant les points n’ayant pas la même direction. Cela permet de supprimer des points que l’on ne considère pas significatifs. Par exemple, pour une personne se déplaçant vers 180° soit le sud, on pourra considérer, par exemple, que tous les points entre 170° et 190° ne représentent pas un changement significatif de direction. Dans le code en VBA, ce seuil est exprimé en pourcentage (pour 10% avec une valeur de référence de 180°, on ignore les points entre 162° et 198°).

D’autre part, le programme calcule le « bearing » (ou direction) entre chaque paire de points. J’ai choisi de le calculer manuellement bien qu’il soit présent normalement dans les trames RMC pour la simple et bonne raison que, parfois, le GPS ne le calcule pas ou mal :

Illustration 11 : Bearing incorrect dans les trames RMC

On remarque que, parfois, le calcul ne se fait tout simplement pas, il m’a donc paru plus fiable de le recalculer. D’autre part, face aux nombreux types de puces GPS existantes n’ayant pas le même format de trame, on ne peut pas forcément savoir avec certitude où se trouve le « bearing » correct.

Illustration 12 : Calcul du « bearing » (ou direction) en VBA

Après avoir crée les macros Visual Basic, j’ai testé le programme afin de vérifier que les coordonnées optimisées étaient cohérentes. Pour faire la comparaison, j’ai utilisé un outil de visualisation disponible sur Internet appelé GPS visualizer (http://www.gpsvisualizer.com). Cet outil m’a permis de constater que le trajet optimisé est similaire au trajet initial.

On remarque tout de suite les limites de cet outil, on ne peut pas voir précisément les points ni le nombre de points ce qui ne permet pas de faire une comparaison efficace. Par la suite, je me suis servi d’un outil libre écrit en Java beaucoup plus précis que j’ai modifié pour les besoins de l’analyse: Prune GPS.

Interface graphique en VBA

Le programme sous VBA contient plusieurs modules :

• CalculBearing qui permet le calcul de la direction mais aussi des fonctions utiles comme passer de degrés à radians, passer du format degrés-minutes vers le format décimal, etc.
• EcrireFicGPRMC qui permet à partir d’une feuille de calcul, d’écrire l’ensemble des trames RMC dans un fichier
• EcrireLatLon qui renvoie la latitude et longitude décimale dans un fichier
• EcireOptimLatLon qui écrit les latitudes et longitudes optimisés dans un fichier
• LireFicNMEA qui lit un fichier NMEA et qui parse les trames RMC en remplissant les feuilles de calcul
  

Une fois toutes ces fonctions effectuées et validées, j’ai décidé de créer une interface graphique de manière à faciliter l’utilisation des macros.

L’interface graphique se lance dès que le fichier Excel est ouvert.

L’interface donne l’accès à six fonctionnalités, la plus importante est sans doute l’écriture dans un fichier des latitudes et longitudes optimisées. Lorsque l’utilisateur sélectionne cette dernière option, d’autres paramètres s’affichent :

L’utilisateur peut indiquer divers paramètres :

• GPS Visualizer permet de formater les données de manière à ce qu’elles soient directement lisibles sur le site (http://www.gpsvisualizer.com)
  
• Récursif : par défaut le calcul est non récursif (itératif), une fonction récursive a été réalisé de manière à supprimer les bugs, on peut considérer que si les résultats du calcul itératif et récursif sont égaux alors le calcul est « correct » car les algorithmes sont indépendants en théorie. Il faut savoir que, si l’option Récursif est sélectionnée, alors l’option échantillonnée et la sélection du seuil ne sont plus possibles (le seuil par défaut est à 0) car la fonction récursive est dépourvue de ces fonctionnalités.
• Échantillonné simule un échantillonnage des donnés : si pas de changement de cap alors on écrit une position toutes les 5 secondes, si changement de cap on écrit toutes les secondes. Ceci afin de simuler l’utilisation finale réelle car on peut très bien imaginer une personne immobile depuis un certain temps et, dans ce cas, le programme ne renverrait jamais sa position.
• « Seuil » permet d’indiquer le seuil de tolérance en pourcentage utilisé lors de la comparaison de la direction des différentes paires de points

Un autre menu, le menu 6 est un menu d’aide permettant notamment de récapituler les différentes fonctionnalités offertes par le programme à l’utilisateur :

Le programme sur PDA

Le travail effectué sous VBA m’a permis de valider les différentes fonctions utilisées afin de faciliter au maximum la transition sous le langage .NET. J’ai donc réalisé un « prototype » sur PDA pour l’analyse et la compression des trajets GPS ainsi que l’affichage de ces trajets. Ce prototype est présenté dans cette partie.

Les modules

Le programme sur PDA est basé sur 2 modules :

• Le module Location qui gère le dialogue avec la puce GPS en utilisant l’outil « GPS Intermediate Driver ». C’est en fait une couche d’abstraction matérielle qui permet d’accéder à n’importe quel GPS (interne ou lié à un port de communication sur Smartphone).
  
• Le module GPS Tracker qui contient la classe pour l’optimisation, l’interface graphique, la classe pour l’exportation vers le format GPX, la classe gérant le tableau pour l’affichage des coordonnées GPS
  

GPS Intermediate Driver

« GPS Intermediate Driver » fournit des fonctionnalités aux applications qui utilisent des appareils GPS. Il le fait en fournissant une couche intermédiaire pour l’interrogation du GPS. Cet outil permet aux développeurs d’écrire du code qui fonctionne avec tout type de matériel GPS.

Sans ce type d’outil

Sans des outils comme « GPS Intermediate Driver », les applications accèdent généralement au matériel GPS par l’intermédiaire d’un port COM. Selon le type de matériel, ce port COM peut être un véritable port série, auquel le matériel GPS est connecté par l’intermédiaire d’un câble série. Mais cela peut aussi être un port série « virtuel » rattachés au matériel GPS grâce à un périphérique, SDIO, Bluetooth, ou autres.

Avec la plupart des dispositifs GPS, une fois la connexion effectuée directement sur ce port, celle-ci est exclusive, de sorte qu’une seule application à la fois peut interagir avec le matériel GPS.

Ce type de connexion permet d’accéder aux données NMEA brutes qu’il faut ensuite « parser » (ou filtrer) afin de récupérer les informations voulues.

Avantages de ce type d’outil

Avec un outil comme « GPS Intermediate Driver », les applications ne dialoguent plus directement avec le matériel GPS. Le pilote se charge de le faire.

Ainsi « GPS Intermediate Driver » offre deux avantages principaux:

• Il permet à plusieurs applications d’utiliser le matériel GPS en même temps.
• Il n’est plus nécessaire que chaque application parse les données NMEA provenant du GPS car l’API fournit par « GPS Intermediate Driver » analyse elle-même les chaînes NMEA du GPS et renvoie directement les informations parsées.
  

D’autre part, ces atouts font qu’il n’est plus nécessaire que l’utilisateur indique à chaque application à quel port est connecté le matériel GPS. Car « GPS Intermediate Driver » récupère directement l’information par l’intermédiaire du panneau de configuration du terminal.

Diagramme de classes

Le module « Location » est un module d’exemple de l’utilisation du pilote « GPS Intermediate Driver ». Il permet d’accéder aux données GPS et de déclencher un événement dès que des données sont reçues qui sont ensuite traitées par l’application « GPS Tracker » pour mettre à jour les données et effectuer les traitements.

GPS Tracker

Le projet BÉA a nécessité le développement d’un programme sur PDA afin d’exploiter les données récupérées du GPS intégré. Ce programme sur PDA fonctionne sur Windows Mobile avec le Compact Framework version 3.5 de .NET. L’environnement de développement utilisé fut Visual Studio 2009. La suite de ce chapitre présente les principaux composants de ce programme.

Informations

L’onglet « Infos » permet de voir, en temps réel, différentes informations :

• nom de la puce GPS (constructeur) ;
• activation ou non du GPS (On ou Off) ;
• la latitude décimale ;
• la longitude décimale ;
• un tableau récapitulatif des coordonnées au format degrés-minutes (ddmm.mmmm) ainsi que le temps pour chacune de ces coordonnées.
  

Illustration 19 : Code pour la mise à jour des « TextBox » de latitude et longitude en C#

A chaque nouvelle position, si celle-ci est valide et cohérente, on l’ajoute au tableau « eventLog » de type « ListView ». Cela permet à l’utilisateur de revoir l’ensemble des coordonnées GPS déjà traitées.

Illustration 20 : Portion de code pour la mise à jour de la liste des positions GPS en C#

Logs

L’onglet « logs » permet, comme son nom l’indique, de gérer les logs ou fichiers de sortie générés par le programme. Il existe différents types de sorties :

• GPX qui est un fichier XML spécifique pour les coordonnées GPS, ouvert et compatible avec la plupart des programmes ;
• GPRMC qui est une des trames d’un fichier NMEA standard, c’est la « Recommended minimum specific GPS/Transit data » qui contient notamment la longitude et la latitude au format degrés-minutes ainsi que la direction (Nord, Sud, Est, Ouest) ;
• un fichier « optimisé«  qui permet de renvoyer une liste de latitude et longitude soit au format GPRMC (si la case « visu » est cochée) soit une liste brute séparée par des virgules.
  

Le fichier de sortie « optimisé » se base sur un seuil. Il suffit de renseigner la case « Seuil » pour le spécifier. Il y a 2 types de seuil :

• en pourcentage si la valeur rentrée est inférieur à 1 ou qu’elle contient le symbole ‘%‘ (exemple : 5%, 10%, 15% ou 0.05, 0.1, 0.15…etc) ;
• en degrés si la valeur rentrée est supérieur ou égale à 1.

  

Illustration 22 : Portion de code pour la mise à jour de la taille des fichiers de « Logs » en C

Seuil

Pour mieux comprendre, l’algorithme permettant de minimiser le nombre de points d’un trajet se base sur une logique simple : Si entre plusieurs points la « direction » reste constante, alors le programme garde le premier et le dernier point de l’ensemble des points composant cette portion de trajet. Le seuil va permettre d’être plus « indulgent » sur cette direction de manière à supprimer encore plus de points. Si un seuil est spécifié alors la direction de référence sera modulée en fonction de ce seuil :

Illustration 23 : Optimisation en temps réel en C# sous .NET

La principale difficulté de cette partie fut de « convertir » le code VBA d’Excel qui prenait en entrée un ensemble de coordonnées GPS déjà fournies dans un tableau vers un code C# qui puisse traiter les coordonnées au fur et à mesure en temps réel. Une des solutions fut d’utiliser une variable statique pour stocker la direction précédente.

Illustration 24 : Utilisation de la classe « Optim » en C#

Signal

Cette partie permet de visualiser les informations des satellites captés par le GPS :

• La partie haute montre le positionnement des satellites, le point du milieu indique le zénith ;
• La partie basse montre la puissance du signal pour chacun des satellites.

Illustration 26 : Portion de code pour la generation des signaux satellites en C#

Boussole

Comme son nom l’indique, affiche la direction actuelle du PDA en se basant sur les données GPS. L’utilisation du driver « GPS Intermediate Driver » fait que la récupération de la direction est extrêmement simple. Ce qui n’aurait pas été le cas si j’avais travaillé directement avec les données NMEA. L’image pour la boussole a été récupérée sur Internet, elle n’est pas forcément libre de droit mais il est très simple de la changer dans le programme.

Illustration 28 : Affichage de la boussole et positionnement du point de déplacement en C#

Route

Cette partie fut une des plus longues à implémenter, elle affiche une carte de la France et dessine les points GPS au fur et à mesure sur celle-ci. Pour se faire, le programme utilise une libraire appelée «
SharpMap » qui a été « portée » sur le Compact Framework 3.5 de .NET. Cette carte permet plusieurs choses :

• de zoomer (ZoomIn et ZoomOut)
• de se déplacer sur la carte (Pan)

Le menu, en bas à gauche, permet aussi de :

• centrer automatiquement la vue sur l’ensemble du chemin parcouru grâce au bouton « centrer »
• charger une carte au format NMEA
• sauvegarder une carte au format GPX contenant les points optimisés (en fonction du seuil indiqué dans la partie « Logs »)

D’autre part, si l’utilisateur clique sur un point de la carte sans avoir sélectionner les options de « Zoom » ou de « Pan », alors un label s’affiche en bas de la carte et renvoie les coordonnées du point sélectionné.

Le choix de l’utilisation de la librairie SharpMap a été longuement réfléchi, j’ai d’abord tenté d’effectuer l’affichage des coordonnées GPS sans aucune librairie. J’ai malheureusement été confronté à différents problèmes et notamment celui de la transformation de la latitude et longitude décimales pour qu’elle s’affiche dans un cadre graphique en C#.

Par la suite, pour des raisons de pérennité du programme, j’ai décidé de faire appel à une librairie libre. Mon choix s’est porté sur SharpMap car cette librairie est librement utilisable même dans un programme payant (grâce à sa licence LGPL). D’autre part, une partie du code avait déjà été porté sur le Compact Framework .NET pour les applications embarquées.

J’ai utilisé une carte « shapefile » de la France pour l’affichage du trajet. La possibilité de concaténer différentes couches de « shapefile » fait que l’utilisateur peut avoir accès à des informations complémentaires visibles sur la carte (tel que les routes, les fleuves, etc). Pour le prototype, j’ai choisi de garder une carte très simple donc de taille restreinte. Celle-ci n’affiche que les régions. J’ai aussi ajouté une carte mondiale pour une utilisation faite en dehors de la France, à terme.

Illustration 30 : Partie du code pour « centrer » la carte au niveau du parcours en C#

SharpMap

SharpMap est un moteur de rendu cartographique qui permet à partir de différentes sources de données SIG d’en obtenir le rendu graphique dans la projection souhaitée. SharpMap est écrit en C#, basé sur le framework .Net 2.0 et distribué sous la licence « GNU Lesser General Public License ». Le moteur de rendu peut être utilisé pour les clients légers, riches et même mobiles avec une librairie allégée.

Les bases de l’utilisation de SharpMap consistent à définir les différentes couches de données, les styles qui leurs correspondent, la projection et le niveau d’affichage de la carte. La génération de la carte utilise l’API GDI+ pour afficher les éléments cartographiques et laisse un large choix pour la personnalisation du style de chaque couche. SharpMap permet de faire la conversion entre les coordonnées graphiques et les coordonnées spatiales afin de pouvoir interagir avec la carte.

Diagramme de classes

La classe sans doute la plus importante de ce diagramme est « Optim » c’est elle qui est chargée de déterminer, en temps réel, les coordonnées GPS à sauvegarder ou à supprimer en fonction de la direction de référence. Elle calcule le « cap » (direction ou bearing en anglais) pour déterminer, en fonction du seuil, si les nouvelles coordonnées GPS sont significatives ou non.

Transmission des données en ASN.1

Suite au développement des différentes parties du programme, j’ai intégré une solution de transmission des données au format ASN.1 (toujours dans un souci d’optimisation) développé par un collègue stagiaire. J’ai donc modifié le programme en sauvegardant l’ensemble des données optimisés dans un tableau qui est ensuite encodé au format ASN.1 et envoyé à un serveur écrit en Java. Ce serveur décode les données ASN.1 transmises et écrit dans un fichier les latitudes et longitudes des coordonnées GPS.

J’ai comparé les données en entrée et en sortie afin de valider la transmission des données ASN.1. Nous avons ensuite fait une démonstration à notre responsable : Mr Pascal PEDIRODA qui s’est déroulée avec succès.

Analyse des résultats

Suite au développement du programme sur PDA, il semblait nécessaire de trouver un seuil pertinent afin de modéliser un trajet piéton avec un minimum de points. Le but étant d’optimiser la bande passante et le trafic généré par le PDA.

Outil de visualisation et analyse des trajets

Comme évoqué précédemment, l’outil Web GPS visualizer n’est pas très approprié pour l’analyse des points. En effet, il n’affiche que les lignes et ne montre pas les détails de chaque point. La carte du programme sur PDA répond en partie à ce problème en affichant les points d’une couleur différente mais n’offre pas beaucoup de fonctionnalités en ce qui concerne les détails de ces points.

Ainsi, après de multiples recherches, j’ai finalement trouvé un outil libre appelé Prune GPS. Il affiche le détail de chaque point et constitue un outil très complet.

Prune GPS

Prune est une application pour la visualisation, l’édition et la conversion des données GPS.

Prune est capable de charger des données textuelles (par exemple, séparées par des tabulations ou des virgules) ou XML. Cette application permet d’afficher, de modifier (par exemple supprimer des points) et sauvegarder les données GPS. Elle peut également exporter les données au format GPX ou KML. Prune est écrite en Java et est publiée sous licence GNU GPL.

Modification de Prune GPS

Pour les besoins du projet et de l’analyse, il a fallu que je compare les chemins optimisés avec le chemin initial. Or Prune n’a pas vraiment été développée dans ce but. J’ai donc fait plusieurs modifications afin de pouvoir faire une comparaison plus efficace.

Choix des couleurs pour chaque trajet

La première difficulté est que Prune ne permettait pas de choisir différentes couleurs pour différents trajets. J’ai donc rajouté cette fonctionnalité de manière à pouvoir comparer plus facilement 2 trajets différents.

Illustration 34 : Choix de la couleur du trajet et récupération des points discordants en Java

Calcul automatique du pourcentage de discordance

Afin d’éviter de vérifier à l’œil nu pour chaque trajet si la discordance est trop importante ou non, j’ai décidé de faire un calcul automatique du pourcentage de discordance basé à la fois sur le nombre de points « discordants » c’est-à-dire en dehors du trajet de référence mais aussi sur l’éloignement de ces points par rapport aux points de référence.

Sur l’image ci-dessous, on voit la version modifié de Prune, en rouge le trajet optimisé et en bleu le trajet de référence. On voit alors s’afficher un pourcentage de compression, le nombre de points en dehors du trajet de référence et un pourcentage de discordance pour ce trajet optimisé.

Illustration 35 : Affichage de 2 trajets avec Prune modifié (en bleu le trajet de référence)

Pour le calcul des points en dehors, je récupère l’équation de la droite entre 2 points GPS du trajet optimisé et je vérifie que les points du trajet initial vérifient l’équation de cette droite de manière à être sûr que la droite optimisée passe par ces points.

En conséquent, plus le seuil est grand et forcément, plus il y a de points du trajet de référence qui se trouvent en dehors.

Analyse et détermination du seuil « idéal »

Une fois les modifications faites de Prune, j’ai été chargé de déterminer un seuil « idéal » qui puisse être un bon compromis entre un nombre minimal de points tout en restant fidèle au trajet initial. J’ai commencé par exécuter le programme avec différents seuils dont voici les résultats :

On remarque que les seuils en degrés donnent de meilleur résultat étant donné qu’ils sont constants et ne dépendent pas du « cap » de référence précédent. Les résultats démontrent que, si l’on souhaite optimiser la compression et minimiser la discordance alors le seuil de 5° semble être le meilleur compromis.

Cependant, si la compression s’avère être un critère un peu plus important, la meilleure solution semble être le seuil de 12° :

En effet, graphiquement, on remarque une très bonne concordance avec le trajet initial (ici en bleu) et un très bon taux de compression (plus de 50%) avec 143 points pour un trajet initial de 306 points. D’autre part, si l’on fait la différence entre ce taux de compression et le taux de discordance, c’est la valeur pour laquelle on obtient le meilleur résultat.

Dès que l’on augmente le taux de 1° soit 13° la concordance graphique n’est plus présente bien que le taux de discordance soit encore convenable (7.05%), cela se vérifie graphiquement :

On remarque que les lignes du graphique optimisé (en rouge) ne suivent pas parfaitement celle du graphique initial (en bleu) ce qui est particulièrement vrai dans les boucles.

Afin de valider l’analyse du programme et les hypothèses précédentes, j’ai effectué des tests sur un deuxième parcours constitué de 1433 points dont voici les résultats :

On constate que le pourcentage de compression est relativement élevé et que le ratio entre le pourcentage de compression et celui de discordance reste le plus élevé pour un seuil de 5°.

Glossaire et mots clefs

Références bibliographiques

1Insee

2DREES

3La prise en charge des personnes âgées dépendantes

4Le marché de la dépendance

5Annexe technique DGE

6Accueil de personnes âgées

Références webographiques

1Gpsinformation.org

Adresse du site web : http://www.gpsinformation.org/dale/nmea.htm

2Wikipedia

Adresse du site web : http://fr.wikipedia.org/wiki/NMEA

3Codepedia

Adresse du site web :

http://www.codepedia.com/1/The+GPRMC+Sentence

4Aviation formulary

Adresse du site web :

http://williams.best.vwh.net/avform.html

5Movable type

Adresse du site web :

http://www.movable-type.co.uk/scripts/latlong.html

6Different degree formats

Adresse du site web :

http://home.online.no/~sigurdhu/Deg_formats.htm

7Tma.dk

Adresse du site web :

http://www.tma.dk/gps/

8NMEA output structure

Adresse du site web :

http://bse.unl.edu/adamchuk/web_ssm/

9Codeproject – location from cell id

Adresse du site web :

http://www.codeproject.com/KB/mobile/DeepCast.aspx#5

10GPS visualizer

Adresse du site web :

http://www.gpsvisualizer.com/

11Prune GPS

Adresse du site web :

http://activityworkshop.net/software/prune/

Annexes

Documents de présentation

Présentation globale

Architecture globale

Projet BEA version 1

Projet BEA version 2