Brevet FR3090148A1 — publié le 20200619

Description Titre de l'invention : PROCÉDÉ DE RECALAGE CARTOGRAPHIQUE MULTIMODAL BASÉ SUR LE COMPORTEMENT RÉPÉTITIF HUMAIN Domaine de l'invention 100011 La présente invention concerne le domaine des services basés sur la géolocalisation, en particulier le domaine de traitement des données de géolocalisation en masse. L'invention concerne un procédé de recalaee cartographique à partir des données de géolocalisation recueillies sur un équipement mobile. Avantageusement, ce procédé exploite le comportement répétitif de la mobilité humaine en fusionnant les informations complémentaires des trajets similaires du passé afin d'obtenir une meilleure estimation dans le cas des données imprécises, irrégulières et éparses. État de la technique [0002] L'analyse de flux de mobilité est une tâche importante clans le domaine des services basés sur la géolocalisation. En effet, elle permet d'avoir une vision macroscopique sur la dynamique des activités économiques et. sociales au niveau d'une ville, voir même d'un pays. Plusieurs acteurs économiques sont intéressés par cette information, notamment les autorités publiques qui peuvent s'en servir pour étudier leurs plans d'aménagement, gérer le trafic routier, les commerçants et. détaillants qui l'utilisent pour leur étude d'implantation, les agences publicitaires qui s'en servent pour le placement de leurs panneaux de publicité, les agences immobilières qui s'en servent pour étudier le prix immobilier, etc. [0003] Les flux de mobilité humain peuvent être approximés par le biais de multiples types de données : la géolocalisation par satellite (Global Positioning System ou GPS, Galileo), les données de signalisation du réseau mobile (Call Data Record), la triangulation de réseau (WiFi, 3G, 4G), les données issues des capteurs inertiels, etc. Dans cette invention, nous nous intéressons à deux types de données de géolocalisation pouvant être facilement collectées sur la plupart des téléphones mobiles d'aujourd'hui : les données GPS et les données issues de la triangulation de réseau. Mais la technique inventée peut s'appliquer à n'importe quel type de données tant qu'il contient une suite de positions horodatées. [0004] Le recalage cartographique, («map rnatching » en anglais), est une procédure im- portante dans l'analyse dc flux de mobilité. En principe, l'utilisateur mobile se déplace sur des axes de transport routiers, mais la mesure de géolocalisation par GPS ou par réseau sur un téléphone mobile est souvent bruitée, ce qui fait que les données de géolocalisation obtenues par ces méthodes ne correspondent jamais parfaitement aux tra- 2 jectoircs réelles de l'utilisateur. Le recalage cartographique permet de projeter une géolocalisation sur une carte digitale en cherchant l'axe routier le plus probable que l'utilisateur devait passer. Cette procédure peut être incrémentale, comme dans le cas des boitiers GPS, ou être en mode différé. [0005] En réalité, le recalage cartographique d'une trajectoire à partir des données de géolo- calisation est un vrai défi technique car la qualité des données varie fortement en fonction des ressources disponibles sur l'équipement mobile (différents types de puce de GPS) ainsi que leurs contraintes techniques, notamment la consommation de batterie. D'un côté, on peut activer la fonction GPS de l'appareil tout le temps pour avoir des trajets très précis, mais cela videra rapidement la batterie de l'appareil. D'un autre côté, si on se base uniquement sur la triangulation de réseau, qui consomme peu d'énergie, on obtient des trajectoires très imprécises car la fréquence d'échantillonnage est faible et la méthode de localisation n'est pas fiable. A cela s'ajoutent multiples aléas de toute nature, que ce soit au niveau matériel que logiciel des systèmes mobiles. Par conséquent, en réalité, entre ces deux extrémités, on a souvent des données très imprécises (les erreurs de localisation pouvant atteindre de l'ordre de kilomètres), irrégulières (la fréquence d'échantillonnage très faible, de l'ordre d'une position toutes les 15 minutes ou plus) et éparses (la distance entre les positions consécutives pouvant être de l'ordre de kilomètres). Les techniques de recalage cartographique existantes, en se reposant sur l'hypothèse des données de haute fréquence, ne fonctionnent pas sous ces conditions réelles de l'environnement mobile. Dans cette invention, nous proposons une nouvelle technique de recalage, simple et efficace, permettant d'obtenir des trajets de bonne qualité, tout en respectant les contraintes techniques de l'environnement mobile. [0006] On fait la différence entre l'estimation de trajectoire, qui consiste à estimer finement la suite de positions d'un objet se mouvant dans l'espace, tel que la trajectoire d'un drone volant, ou la trajectoire d'une personne marchant dans une salle, et le mapmatching, qui consiste à projeter la séquence de données de géolocalisation sur une carte numérique (un réseau routier/ferroviaire), et à estimer la séquence de routes parcourues, par exemple les routes empruntées d'une personne pour aller au travail. Les deux types d'estimation nécessitent des techniques et des types de données bien différentes. L'invention concerne seulement le dernier cas. [0007] 11 existe un ensemble de travaux sur le recalage cartographique à partir des sources d'information complémentaire, par exemple des données issues des capteurs inertiels (gyroscopes, accéléromètres). Ces techniques requièrent des équipements de haute qualité et des données de haute fréquence. La technique inventée ne dépend pas de ces sources d'information complémentaire. [0008] 11 est connu que la mobilité humaine expose un caractère « à queue lourde », 3 c'est-à-dire que les gens ont tendance à se déplacer régulièrement entre très peu de points d'intérêt (par exemple, la maison, le lieu de travail, la salle de sport), et de temps en temps, ils réalisent des « sauts » vers une nouvelle destination (par exemple, un voyage à l'étranger). [0009] L'idée de l'invention se base sur cette forte corrélation spatio-temporelle de la mobilité humaine. En effet, la mobilité humaine est très répétitive. On prend souvent le même chemin pour aller au travail le matin, le même chemin pour rentrer chez soi le soir, le même chemin pour aller au supermarché le samedi, etc. Par conséquent, on peut croiser ces informations des trajets similaires du passé, même si elles sont incomplètes, les interpoler pour avoir le trajet complet (K. Zheng, Y. Zheng, X. Xie, and X. Zhou, -Reducing Unccrtainty of Low-Sampling-Rate Trajectories," in 2012 IEEE 28th International Conference on Data Engineering, 2012, pp. 1144-1155, et L.-Y. Wei, Y. Zhcng, and W.-C. Peng, "Constructing popular routes from unccrtain trajectories," in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '12, 2012, p. 195). [0010] Une approche naïve de map rnatching (Yang et. al., « An improved Map-Matching Algorithm Uscd in Vehicle Navigation System », Proceedings of the 2003 IEEE International Conference on Intelligent Transportation Systems) consiste à considérer le segment de route la plus proche de la géolocalisation comme étant le candidat. Cette approche peut être améliorée par l'application d'un filtre de Kalman. Cette méthode est plus adaptée pour les données de type Floating Car Data. [0011] Une autre approche de map-matching consiste à chercher le chemin qui ressemble géométriquement le plus aux observations en utilisant la distance Fréchet comme mesure de similarité. L'ensemble de travaux décrits dans le brevet W02014143058A1, l'article Brakatsoulas et. at., « On Map-Matching Vehicle Tracking Data », VLDB 2005, page 853-864, l'article Wei et. al., « Map Matching: Comparison of Approaches using Sparse and Noisy Data », SIGSPATIAL 2013, l'article Helmut Alt et. al., Matching planar maps », Journal of Algorithms, 2003, le rapport technique Wei et. al., « Map Matching by Fréchet Distance and Global Weight Optimization », Penne State University, 2013 rentrent dans cette piste. [0012] Parmi les techniques de map-matching existantes, la technique basée sur un modèle de Markov caché (en anglais, Hidden Markov Model) est souvent considérée comme celle la plus avancée aujourd'hui. Le principe de cette approche est de modéliser le déplacement comme étant un processus Markovien dans lequel la séquence des segments de route traversés sont les états inobservables, ou cachés, et les géolocalisations sont les observations visibles de ce processus. En connaissant les lois de probabilité régissant la génération des observations d'un état caché (l'erreur de géolocalisation) et des transitions entre les états (par exemple, l'humain a tendance de choisir la route qui optimise la distance parcourue), on peut estimer la séquence des routes la plus probable pour une séquence d'observations donnée. Le brevet US8645061B2 ainsi que l'article P. Newson and J. Krumrn, -Hidden Markov map matching through noise and sparseness," Pi-oc. 17th ACIVI SIGSPATIAL Im. Conf. Adv. Geogr. Inf. Syst. - GIS '09, no. c, pp. 336-343,2009, décrivent une telle technique. Cette technique a été validée avec les données de fréquence d'1Hz, qui est encore très grande par rapport au spectre de fréquence visée par la présente invention. [0013] Dans l'aride C. Goh, J. Dauwels, and N. Mitrovic, Map-Matching based on Hidden Markov Model for Real-Time Traffic Sensing Applications," 15th Int. IEEE Conf. hztell. Transp. Syst., vol. 117543, pp. 776-781,2012, les auteurs proposent une amélioration de l'algorithme de Newson et al., ainsi que de le rendre incrémentai. Cette méthode intègre d'autre type de données issues des capteurs ainsi que les informations topologiques, telles que l'accélération et l'altitude. [0014] Dans l'article S. Mattheis, K. Khaled Al-Zahid, B. Engelmann, A. Hildisch, S. Helder, O. Lazarevych, D. Mohr, F. Sedlmcier, and R. Zinck, "Putting the car on the map: A scalablc map matching system for the Open Source Cornmunity," Lect. Notes Itzformaties (LN!), Proc. - Ser. Gesellschaft fur Inforzn., vol. P-232, pp. 2109-2119, 2014, les auteurs proposent une implémentation java de l'algorithme de Newson et al. [0015] Le brevet US8457880B1 concerne un procédé de map-matching capable de traiter les données incertaines et intermittentes, en utilisant aussi une approche basée sur un modèle de Markov caché. Il utilise également les données issues des capteurs inertiels (accéléromètres et gyroscopes). [0016] L'article Aly et. al., « semMatch: Road Semantics-based Accurate Map Matching for Challenging Positioning Data », ACM SIGSPATIAL 2015, présente un autre procédé de map matching, toujours en se basant sur un modèle de Markov caché mais utilise en plus les données issues des capteurs inertielles du téléphone. Les auteurs montrent des meilleurs résultats par rapport à la méthode de Newson et al. [0017] Dans le brevet FR3046006 ainsi que l'article F. Asgari, A. Sultan, H. Xiong, V. Gauthier, and M. A. El-Yacoubi, "CT-Mapper: Mapping sparse multimodal cellular trajectories using a multilayer transportation network," Comput. Commun., vol. 95, pp. 69-81, Dec. 2016, les auteurs proposent un procédé d'estimation de trajectoire à partir des données d'appels. Cette procédure nécessite l'infrastructure réseau, les signaux de signalisation ainsi que la connaissance à priori des localisations des stations de base. Notre invention fonctionne avec les données de géolocalisation et ne nécessite aucune information supplémentaire. [0018] Le brevet W02008101925A1 décrit un dispositif et procédé pour détecter la tra- jectoire d'un objet se déplaçant en deux dimensions. Le procédé concerne l'estimation de trajectoire d'une personne. [0019] Le brevet EP2082253B1 décrit un procédé et dispositif d'estimation de trajectoire d'un objet mobile, notamment un véhicule à partir des données GPS. Il comporte une phase d'estimation de vitesse et de cap à partir des données successives, qui ne sont pas envisageable en cas des données très éparses. [0020] Le brevet US9310211B1 décrit un procédé de map matching qui simplement fait appel à un routeur pour relier les segments candidats sur routes. Bien que l'approche soit simple et cela puisse fonctionner avec des données éparses, sa performance dans le cas des données imprécises et irrégulières est discutable car la solution est toujours le chemin le plus court. La présente invention, au contraire, exploite la corrélation spatio-temporelle entre les habitudes de déplacement du passé et permet donc d'obtenir des trajets précis même dans le cas des données imprécises, irrégulières et éparses. [0021] Il existe un ensemble de travaux sur l'analyse de similarité des données trajectoires. Le brevet U59747805B2 et l'article Ranu et. al., « Indexing and matching trajectories undcr inconsistcnt sampling rates », ICDE 2015 proposent une fonction de distance pour mesurer la similarité entre 2 trajets, dans le but d'appariement de trajets. Dans l'article Furtado et. al., « Unvciling movement unccrtainty for robust trajectory similarity analysis », Journal International Journal of Gcographical Information Science Volume 32, 2018 - Issue 1, les auteurs comparent de multiples mesures de similarité de trajet. Ils proposent une nouvelle mesure basée sur la notion du « ti me gcography » consistant à utiliser une éclipse pour représenter du l'incertitude du mouvement. [0022] Solution apportée par l'invention [0023] L'invention concerne, selon son acceptation la plus générale, un système in- formatique et procédé permettant de réaliser un recalage cartographique des données de géolocalisation sur une carte numérique. Bien que la solution décrite soit illustrée par un mode de fonctionnement incrémentai, c'est-à-dire avec les données qui arrivent en temps réel, l'invention peut très bien s'appliquer en mode différé, c'est-à-dire avec un lot de données. [0024] L'invention concerne particulièrement un procédé de recalage cartographique à partir de l'enregistrement sur un serveur d'une succession de données de géolocalisation horodatées transmises par un équipement connecté porté par une personne, comprenant les étapes suivantes : [0025] une première étape de détection de trajet par un procédé de détection de points stationnaires, une deuxième étape de recherche et fusion des habitudes de déplacement similaires du passé, une troisième étape de recherche sur une carte numérique d'une séquence des segments de route qui correspond au déplacement détecté à la deuxième étape, une quatrième étape de détection du mode de transport pris sur chaque 6 segment de route estimé à la quatrième étape. [0026] Selon des variantes de réalisation prises isolément ou en toute combinaison tech- niquement réaliste : [0027] - ladite étape de détection et segmentation des trajets réalisés comporte un traitement informatique consistant en une identification des points stationnaires, une segmentation des données de géolocalisation en trajets. [0028] - ladite étape de recherche et fusion des habitudes de déplacement similaires du passé comporte un traitement informatique consistant à représenter les positions du passé avec l'aide d'une structure de graphe. [0029] - la représentation des positions du passé par une structure de graphe comporte un traitement informatique consistant à appliquer une triangulation de Delaunay sur les positions. [0030] - la représentation des positions du passé par une structure de graphe comporte un traitement informatique consistant à attribuer un poids pour chaque noeud et lien du graphe qui est calculé en fonction de la précision des positions et la distance entre ces dernières. [0031] - ladite étape de recherche et fusion des habitudes de déplacement similaires du passé, et la représentation des positions du passé par une structure de graphe, comporte un traitement informatique consistant à effectuer une recherche d'un noeud candidat sur le graphe pour chaque position du nouveau trajet. [0032] - ladite étape de recherche et fusion des habitudes de déplacement similaires du passé, et selon la revendication 3 caractérisé en ce que la représentation des positions du passé par une structure de graphe, et selon la revendication 7 caractérisé en ce qu'une recherche de candidat sur le graphe pour chaque position du nouveau trajet, comporte un traitement informatique consistant à effectuer une recherche du chemin reliant les candidats consécutifs. [0033] - ladite étape de recherche sur une carte numérique d'une séquence des segments de route comporte un traitement informatique consistant à appliquer un modèle de Markov caché dans lequel les états cachés correspondent aux segments de route, les transitions correspondent aux routes reliant ces segments, à effectuer une recherche des segments candidats d'une manière adaptative selon la précision des données de géolocalisation, et à effectuer un calcul de probabilité de transition prenant en compte à la fois la distance et le nombre de tournants. [0034] - ladite étape de détection du mode de transport comporte un traitement informatique consistant à classifier le mode de transport pris par la personne sur un segment de route en fonction de la vitesse moyenne estimée sur ce segment. [0035] Description détaillée d'un exemple non limitatif de l'invention [0036] La présente invention sera mieux comprise à la lecture de la description qui suit, 7 concernant un exemple non limitatif de réalisation illustré par les dessins annexés où : [0037] [fig.1] la FIG. 1 montre l'architecture matérielle du système pour la mise en oeuvre de l'invention, [0038] [fig.2] la FIG. 2 montre l'architecture fonctionnelle du procédé de recalage carto- graphique, [0039] [fig.3] la FIG. 3 illustre le procédé de recherche et fusion des habitudes de dé- placement similaires, [0040] [fig.4] la FIG. 4 illustre un procédé de recherche de la séquence de routes la plus probable grâce à un modèle de Markov caché. [0041] Contexte général de l'exemple de réalisation décrit [0042] L'invention concerne un système informatique distribué et un procédé, exécuté sur un serveur ou une ferme de calcul, pour fournir à une application tierce une information concernant l'estimation de trajet d'une personne. [0043] Le système informatique (illustré par FIG. 1) inclut un équipement mobile (1) porté par la personne pour qui on veut reconstruire les trajets, un ou plusieurs serveurs de calcul de recalage cartographique (8), une ou plusieurs bases de données de géolocalisation (9) pour stocker des positions et trajets, une base de données cartographiques (7) qui stocke des segments de routes, un ou plusieurs serveurs web (6) pour la réception des données ainsi que l'envoi des résultats à une application tierce (10). La communication entre l'équipement mobile et le système back-end se fait via l'Internet (5) en passant par un réseau téléphonique ou des réseaux Wi-Fi. [0044] La collection des données de géolocalisation s'effectue au niveau de l'équipement mobile. L'inconvénient pour le GPS est qu'il consomme beaucoup d'énergie. Pour minimiser la consommation de batterie de l'équipement mobile, un mode de réalisation consiste à combiner intelligemment lesdites deux méthodes de localisation, en espaçant les appels GPS (2) par multiples localisations par la triangulation de réseau (3, 4), qui consomme significativement moins d'énergie. [0045] Le procédé de recalage automatique de trajet, exécuté sur les serveurs de calcul, reçoit en entrée les données de géolocalisation horodatées et effectue trois étapes suivantes (illustrées par FIG. 2) : [0046] La première étape (101) consiste à segmenter les données de géolocalisation ho- rodatées. Un trajet peut être considéré comme une entité composant de 3 parties : le lieu de départ (un point stationnaire), le déplacement (la partie mobile) et le lieu d'arrivé (un point stationnaire). Ce trajet est approximé, ou discrétisé, par une série temporelle de points de géolocalisation horodatés. La détection d'un trajet commence par la détection des points stationnaires pour retrouver ses extrémités. Selon un mode d'implémentation particulier, un point peut être considéré stationnaire si sa distance à son prédécesseur est plus petit qu'un certain seuil et la durée depuis l'enregistrement 8 de son prédécesseur dépasse un certain seuil. Une fois les points stationnaires détectés, on peut segmenter la séquence de points en différents trajets. [0047] Lorsqu'un nouveau trajet est détecté, la deuxième étape (102) consiste à chercher dans la base de données les séquences de positions ayant les plus fortes similarités avec la séquence observée et à les fusionner. L'algorithme (104-108) exploite la forte corrélation spatio-temporelle des déplacements. En effet, les gens ont l'habitude de prendre le même chemin pour aller aux mêmes endroits qu'ils fréquentent. Plus un segment de route est traversé, plus les observations sont cumulées dans le temps sur ce segment. En conséquence, l'addition des informations complémentaires des déplacements similaires du passé, même si elles sont partielles, permet de reconstruire un trajet complet. A la fin de cette étape, on obtient une séquence de positions qui correspond au trajet détecté. [0048] La troisième étape (103) consiste à projeter cette séquence de positions sur une carte numérique, c'est-à-dire, un réseau routier et ferroviaire. Le but est de chercher une séquence de segments de route qui correspond à la séquence de points. On peut modéliser ce problème avec un modèle de Markov caché dans lequel les segments de route réellement traversés sont les états inobservables (ou cachés) et la séquence de points est des observations. Connaissant le modèle, la recherche de la séquence la plus probable des états cachés ayant conduit à la génération des observations se résout avec l'algorithme de Viterbi. [0049] Dans un mode de réalisation plus avancé, ladite deuxième étape du procédé consiste à chercher et fusionner directement les trajets recalés dans le passé. Cela permet à long terme de ne plus avoir besoin d'une carte pour recaler les déplacements déjà observés et ne passer à la troisième étape que pour les nouvelles habitudes de déplacement. [0050] Dans un autre mode de réalisation, à partir de la séquence de segments de route estimés dans ladite troisième étape, en connaissant le temps de passage pour chaque segment, on peut effectuer une estimation de la vitesse moyenne sur chaque segment. Une simple classification par rapport aux vitesses moyennes des véhicules et les limites de vitesse permet d'en déduire le mode de transport utilisé. [0051] Architecture générale du système mis en oeuvre par l'invention [0052] Le système inclut un serveur ou une ferme de données géographiques assurant des fonctions de recalage de données cartographiques (« map matching ») (8), un ou plusieurs serveurs de stockage de données de géolocalisation (9), une base de données de carte numérique (7). Le serveur assure également la distribution d'une application mobile apte à être installée et exécutée sur un équipement mobile (1) disposant d'un module de géolocalisation tel qu'un téléphone portable, une tablette ou un ordinateur portable. [0053] Le système selon l'invention inclut également un ou plusieurs serveurs web (6) pour 9 recevoir et enregistrer des données de géolocalisation provenant des équipements mobiles (1) et transmettre aux applications tierces (10) des trajets détectés. La communication entre l'équipement mobile et le serveur web se fait via l'Internet (5) par le biais des réseaux 3G, 4G et/ou des réseaux Wi-Fi. [0054] L'application mobile (1) communique via le système d'exploitation mobile avec le module de géolocalisation pour recevoir des données de géolocalisation, qui contient en général des coordonnées de la position estimée, l'heure de la mesure ainsi que sa précision. La géolocalisation peut être réalisée via différentes méthodes : la triangulation satellitaire (système GPS, Gallien) (2), ou la triangulation réseau Wi-Fi (3), 30/40 (4). En raison de la forte consommation de batterie de la localisation par satellite, la présente invention propose une technique de localisation efficace pour obtenir un bon compromis entre la précision et la consommation de batterie. Avantageusement, cette technique applique le principe du géo-repérage en intercalant des appels GPS, qui consomme beaucoup d'énergie, avec la localisation par triangulation de réseau, qui consomme peu d'énergie, cc qui permet de réduire significativement la consommation de batterie. Plus précisément, cela consiste d'abord à définir une zone de rayon R dans laquelle l'équipement est localisé par la triangulation de réseau, de détecter la sortie dudit équipement de la zone, de déclencher un appel GPS pour connaître la position exacte de l'équipement, et enfin définir une nouvelle zone de géorepérage en fonction de la vitesse de déplacement de la personne (soit mesurée par le capteur GPS, soit estimée à partir des données de géolocalisation consécutives) et la précision de la mesure GPS, d'éteindre le capteur GPS pour passer une nouvelle fois au mode géo-repérage, et ainsi de suite. [0055] Les données de géolocalisation sont ensuite stockées par les moyens de stockage internes disponibles sur le téléphone (1). L'application mobile communique avec le module de communication pour transmettre périodiquement les données de géolocalisation horodatées au serveur web (6), qui les envoie par la suite aux serveurs de stockage (9). Pour pouvoir stocker les données provenant d'un grand nombre d'équipements, les données peuvent être distribuées sur un cluster de serveurs de stockage disposant de capacité d'auto-adaptation. [0056] Les serveurs cartographique (8) vérifient périodiquement s'il y a des nouvelles données disponibles. S'il y en a, la base de données (9) est chargée de distribuer les nouvelles données aux multiples serveurs de calcul (8). Chaque serveur traite indépendamment ses données, en interrogeant la base de données de carte (7), et sauvegarde les trajets détectés sur les bases de données (9), qui à leur tour notifient le serveur web (6) pour transmettre ces trajets aux applications tierces (10). Ce mode d'implémentation particulier est très avantageux car il permet de passer à l'échelle facilement en rajoutant des serveurs en fonction de la volumétrie de données à traiter (passage à l'échelle horizontale). [0057] Traitements effectués par le serveur de calcul [0058] Le processus de rccalage cartographique se compose de trois composantes principales : [0059] 1. la détection de trajet (101), 2. la recherche et des habitudes de déplacement similaires observées dans le passé (102), 3 la recherche de la séquence de route la plus probable (103). [0060] Au sens du présent brevet, on désignera par P, une donnée de géolocalisation qui correspond à une position horodatée pour un équipement mobile donné. Le serveur de map matching reçoit donc en entrée, pour chaque équipement mobile, une série temporelle[Math. 1] P P2, 'Pi) [0061] Détection de trajet (101) [0062] La première phase du traitement consiste à transformer la séquence de positions P en une séquence de trajets, qu'on désignera[Math. 2] T = (trahi traj2, ,traji) [0063] . Chaque trajet n'al contient trois parties : le lieu de départ, le déplacement et le lieu d'arrivée. Les lieux de départ et d'arrivée sont des endroits auxquels la personne passe un certain temps, par exemple la maison, le lieu de travail, la salle de sport. On désignera par point stationnaire un tel lieu. Notons qu'un point stationnaire peut correspondre à un mouvement, comme dans le cas d'une salle de sport. [0064] La détection d'un trajet implique une détection des points stationnaires afin de dé- terminer le début et la fin d'un trajet. Cette détection doit être incrémentale car les données arrivent en temps réel sur les serveurs de calcul. Pour cela, on applique une classification basée sur 2 métriques : la distance d et du temps écoulé At entre les données consécutives d d +1. L'idée vient du constat que lorsque la personne est sur un point stationnaire, les données sont clustérisées fortement au tour d'un point et la durée est longue. [0065] Trois classes sont définies : mobile, ralentie, stationnaire. On définit également un point d'encrage d crage pour détecter le début d'une stationnarité. Ce point est en initialisé à la première donnée reçue et mis à jour à chaque nouvelle donnée arrivée. Si la distance est plus grande qu'un seuil Ad- RI 2C D la donnée est qualifiée comme mobile elle point d'encrage est mis à jour d = d Au contraire si encrage 11