Brevet FR2907581A1 — publié le 20080425

Procédé et dispositif d'estimation d'une trajectoire décrite par un véhicule L'invention concerne le domaine technique général de la localisation et du suivi d'entités mobiles. Elle concerne plus particulièrement un procédé et dispositif d'estimation d'une trajectoire décrite par un objet mobile, notamment un véhicule. Une solution connue de localisation est celle développée par la société QuanticTM pour les véhicules automobiles. Cette solution repose sur l'utilisation des informations de vitesse et de caps fournies par le système GPS (Global Positionning System) pour effectuer le suivi d'un véhicule automobile et déterminer différents paramètres de la trajectoire suivie par cette entité. La méthode de détermination procède à une intégration de la mesure de vitesse fournie par le GPS afin d'approcher la trajectoire de l'entité en mouvement. Elle est relativement complexe à mettre en oeuvre. Elle ne peut être mise en oeuvre dans un dispositif à faible ressource tel qu'un téléphone mobile. En outre, la méthode de détermination de la trajectoire utilisée dans cette solution est tributaire des informations fournies par le GPS, les changements de direction n'étant par exemple détectés que grâce aux informations de cap fournies. Cette méthode d'approximation de trajectoire n'est donc pas applicable dans le cas où l'information fournie est une simple information de position. Il apparaît donc un besoin de fournir une solution simple de suivi d'une entité mobile, permettant d'approximer la trajectoire suivie par cette entité à partir de positions géographiques successivement occupées par cette entité et susceptible d'être mise en oeuvre dans dispositif à faibles ressources en calcul et/ou en mémoire tel qu'un téléphone mobile. L'invention concerne un procédé d'estimation d'une trajectoire décrite par un objet mobile, à partir d'une succession de positions géographiques obtenues pour ledit objet, le procédé comprenant, - une étape de détermination d'une valeur de vitesse de déplacement dudit objet à partir d'une position courante et d'une position précédente, - une étape de détermination d'une droite courante qui est, selon la valeur de vitesse déterminée, soit une première droite définie par ladite position courante et ladite position précédente, soit une deuxième droite obtenue par approximation linéaire d'un ensemble comprenant au moins deux positions dont ladite position courante et une position précédente. Le procédé permet d'approximer de manière simple, notamment au moyen d'un 2907581 2 ensemble de droites, la trajectoire de l'objet à suivre, et ce uniquement à partir de positions géographiques obtenues pour l'objet mobile. Les techniques d'approximation linéaires d'un ensemble de points sont en effet simples à mettre en oeuvre. La trajectoire peut ensuite être reconstituée à partir de segments de droite appartenant 5 aux droites déterminées. En outre, l'approximation de la trajectoire par des droites s'opère, pour un point donné de la trajectoire, en tenant compte de la vitesse de l'objet à ce point de la trajectoire. La méthode d'approximation selon l'invention repose en effet sur la constatation que plus un véhicule roule lentement, et plus la trajectoire qu'il effectue 10 est susceptible de comporter des changements de direction rapides et/ou amples. Selon l'invention, la droite courante choisie pour l'approximation de la trajectoire au point courant, et donc le mode d'approximation pour ce point, est fonction de la vitesse de l'objet. Il est donc possible simplement d'adapter la précision de l'approximation à la sinuosité possible de la trajectoire de l'objet. 15 Selon un mode de réalisation du procédé selon l'invention, lorsque la valeur de vitesse déterminée est supérieure à un premier seuil de vitesse, le procédé comprend une étape de détermination d'une valeur d'angle associée à la valeur de vitesse et d'une différence d'angle de pente entre la première et la deuxième droite, la droite 20 courante correspondant à la deuxième droite lorsque ladite différence est inférieure à la valeur d'angle déterminée et à la première droite lorsque ladite différence est supérieure à la valeur d'angle associée. Il est ainsi possible de déterminer, en fonction de la sinuosité réelle de la trajectoire, quel est le mode d'approximation le plus approprié. 25 Selon un mode de réalisation, le procédé selon l'invention comprend une étape initiale de mémorisation d'une échelle de valeurs de seuil de vitesse de déplacement dudit objet et d'une valeur d'angle associée à chaque intervalle de valeurs de vitesse séparant deux valeurs de seuil successives, la valeur d'angle déterminée étant 30 constituée par la valeur d'angle associée à l'intervalle de valeurs de seuil dans lequel se trouve la valeur de vitesse déterminée. De cette manière, la sinuosité réelle de la trajectoire peut être comparée avec un à la vitesse de la trajectoire afin de déterminer quelle est la droite la plus appropriée pour l'approximation de la trajectoire. Il s'en suit que la précision des calculs, et donc les ressources en calcul nécessaires, est adaptée 35 aux caractéristiques réelles de la trajectoire. Le rapport précision / coût est amélioré. 2907581 3 Selon un mode de réalisation du procédé selon l'invention, lorsque la valeur de vitesse déterminée est inférieure au premier seuil de vitesse, la droite courante est la première droite. 5 Selon un mode de réalisation du procédé selon l'invention, les positions géographiques obtenues pou l'objet mobile sont déduites des positions géographiques d'un terminal mobile de télécommunication fournies par un réseau de télécommunication auquel accède ledit terminal. Ce mode de réalisation convient donc particulièrement à une mise en oeuvre peu coûteuse de l'invention. 10 En corolaire, l'invention concerne un dispositif d'estimation d'une trajectoire décrite par un objet, à partir d'une succession de positions géographiques obtenues pour ledit objet, le dispositif comprenant, - des moyens de détermination d'une valeur de vitesse de déplacement dudit 15 objet à partir d'une position courante et d'une position précédente, - des moyens de détermination d'une droite courante qui est, selon la valeur de vitesse déterminée, soit une première droite définie par ladite position courante et ladite position précédente, soit une deuxième droite obtenue par approximation linéaire d'un ensemble comprenant au moins deux positions dont ladite position courante et 20 ladite position précédente. Selon un mode de réalisation, le dispositif selon l'invention comprend des moyens pour accéder à un réseau de télécommunication, lesdites positions géographiques étant déduites des positions géographiques d'un terminal mobile de télécommunication fournies par ce réseau. 25 Le dispositif selon l'invention est avantageusement intégré dans un terminal de télécommunication. De la sorte, il est possible d'estimer la trajectoire de toute entité mobile solidaire d'un tel terminal mobile. En variante, le dispositif selon l'invention est intégré dans un serveur de traitement de données connecté à un réseau de télécommunications via lequel sont obtenues les positions géographiques d'un terminal 30 mobile accédant à ce réseau. L'invention a également pour objet un support d'enregistrement comprenant un programme comportant des instructions de programme pour la mise en oeuvre des étapes du procédé selon l'invention lorsque ledit programme est chargé et exécuté 35 dans un système informatique. 2907581 4 D'autres buts, caractéristiques et avantages de l'invention apparaîtront à travers la description qui va suivre, donnée uniquement à titre d'exemple non limitatif, et faite par référence aux dessins annexés dans lesquels: 5 - la figure 1 représente de manière schématique un système adapté à la mise en oeuvre de l'invention, - la figure 2 illustre certaines des étapes du procédé selon l'invention, et - la figure 3 est un ordinogramme d'un mode de réalisation du procédé selon l'invention. 10 L'invention est décrite dans l'exemple particulier de sa mise en oeuvre au moyen d'un réseau de télécommunication cellulaire. En effet, une information de position du véhicule est aisément déduite d'une information sur la position géographique d'un terminal de télécommunication, placé dans ou sur le véhicule et accédant au réseau 15 cellulaire. En effet, la position géographique d'un tel terminal est connue du réseau lorsque celui-ci accède au réseau et cette position géographique est donc susceptible d'être fournie par ce réseau. Cependant l'invention est susceptible d'être mise en oeuvre au moyen de tout dispositif capable d'obtenir une information de position sur un véhicule à suivre. 20 La figure 1 représente de manière schématique un système adapté à la mise en oeuvre de l'invention. Ce système comprend un réseau de télécommunication cellulaire 5, un premier terminal de télécommunication 10 accédant à ce réseau, un serveur 20 de traitement de données accédant à ce réseau, ainsi qu'un deuxième terminal de télécommunication 30 accédant à ce réseau. Dans le mode de réalisation décrit, le 25 serveur 30 est un serveur de gestion de flotte de véhicules. Le terminal 10 est placé dans ou sur un véhicule 15 pour lequel le suivi de trajectoire est effectué. Ce véhicule peut être tout type de véhicule: un véhicule automobile, un bateau, etc. Tout dispositif accédant au réseau 5, notamment un des terminaux mobiles 10 30 ou 30 ou le serveur 20, est susceptible de mettre en oeuvre le procédé selon l'invention. Le procédé est en particulier adapté pour être mis en oeuvre dans un téléphone mobile. Dans la suite de la description, les notations mathématiques suivantes sont 35 utilisées pour les différentes variables: 2907581 5 P(k) keme position géographique du véhicule 15, k entier, kE[O,kmax], mesurée dans un espace à deux dimensions, P(k)=(x(k),y(k)); TP tableau utilisé pour mémoriser une ou plusieurs positions géographiques successives du véhicule 15; 5 V(k) vitesse du véhicule 15 entre les positions P(k) et P(k-1); VS(i) valeur de seuil de vitesse pour i entier, iE[O,imax], ces valeurs étant telles que VS(i) VS(0); d(k) distance entre Pmem et P(k); dtota, distance totale parcourue entre P(0) et P(k); Dc(k) droite courante associée à P(k); 15 DR(k) droite obtenue par régression linéaire d'une partie des points contenus dans le tableau TP; D1(k) droite, dite droite instantanée, définie par les points P(k) et P(k-1); aR(k) valeur en angle de la pente de la droite DR(k), mesurée par 20 exemple en radians et appartenant à l'intervalle [0,2*7[; al(k) valeur en angle de la pente de la droite D1(k), mesurée par exemple en radians et appartenant à l'intervalle [0,2*7[; Les valeurs de seuil de vitesse VS(i) définissent une échelle de valeurs. Cette 25 échelle de valeur est de préférence adaptée à la gamme de vitesses possibles pour le véhicule. Par exemple: si le véhicule est une voiture susceptible de rouler de 0 à 180 km/h, l'échelle de valeurs de vitesse choisie va couvrir cette gamme. Les seuils de vitesse sont par exemple définis comme suit: 30 VS(0)= 5km/h VS(1)= 10km/h VS(2)= 30km/h VS(3)= 50km/h VS(4)= 90km/h 35 VS(5)= 130km/h 2907581 6 VS(6)= 180km/h De préférence, les valeurs de seuil sont choisies d'autant plus rapprochées les unes des autres que la vitesse est faible, de manière à apporter plus de précision dans la méthode d'estimation de la trajectoire à de faibles vitesses du véhicule. 5 La méthode d'approximation utilisée dans le procédé selon l'invention suppose en effet la détection des changements de direction du véhicule et la définition de seuils de détection. Or plus un véhicule roule lentement, et plus la trajectoire qu'il effectue est susceptible de comporter des changements de direction rapides et amples. Par contre, 10 à vitesse élevée, le véhicule n'effectue que des changements de direction progressifs et faibles en amplitude d'angle. Les valeurs d'angle 0(i) associées à chaque intervalle [VS(i), VS(i+1)] sont donc choisies de manière à correspondre à l'angle maximal de changement de direction au-delà duquel l'approximation en segment de droite de la trajectoire du véhicule doit faire 15 apparaître un changement de direction, c'est-àdire un changement de la droite courante porteuse du segment courant. Sur des parties de trajectoire comportant des changements de direction importants en amplitude, un nombre élevés de segments de droite sera nécessaire pour approximer correctement la trajectoire du véhicule. Sur toute la partie de la 20 trajectoire où l'amplitude en angle du changement de direction reste en deçà de cette valeur, la trajectoire du véhicule pourra être approximée par un segment de droite unique. Les valeurs d'angle associées sont choisies par exemple comme suit: 25 30 Le fait de corréler les valeurs maximales d'angle à la vitesse effective du véhicule, permet d'adapter la précision de l'approximation à la vitesse du véhicule. Seules les parties de trajectoires qui le nécessitent vont faire l'objet d'un degré élevé de précision dans l'approximation, par augmentation du nombre de segments de 35 droites utilisés pour approximer la trajectoire. Les ressources en calcul et mémoire O(0)= 30 9(1)= 25 9(2)= 20 9(3)= 10 9(4)= 5 9(5)= 2 2907581 7 sont donc limitées à ce qui est nécessaire pour l'obtention d'une précision d'approximation donnée. Il en résulte un bon rapport précision / ressources. Les étapes 300 à 390 du procédé selon l'invention sont décrites plus en détail 5 par référence à la figure 3. Le procédé s'exécute de manière itérative entre les étapes 300 et 390. En particulier, après obtention à l'étape 300 d'une nouvelle position géographique courante P(k), une droite courante Dc(k) associée à cette position courante P(k) est déterminée lors des étapes 305 à 382, cette droite courante étant fonction de cette position courante et d'au moins une des positions précédemment 10 obtenues. A l'initialisation du procédé, la valeur de la variable k est égale à zéro, le tableau TP est vide et les valeurs des différentes variables sont mises à zéro, notamment la valeur de dtota,. A la première exécution de l'étape 300, une nouvelle position géographique P(0) 15 est obtenue par un dispositif de mesure. Dans le mode de réalisation décrit, la position du véhicule 15 est la position géographique d'un terminal mobile 10 placé dans ou sur le véhicule 15, position telle que fournie par le réseau de télécommunication 5 auquel accède ce terminal mobile 10. Tout autre dispositif apte à fournir la position géographique du véhicule est également approprié. 20 Dans le mode de réalisation où c'est le serveur 20 qui met en oeuvre le procédé selon l'invention, la position du terminal 10 est transmise au serveur 20 à travers le réseau 5. A l'étape 305 cette nouvelle position P(0) est mémorisée dans le tableau TP. Le point Pmem est modifié en vue de la prochaine itération avec les coordonnées du point 25 P(0). Etant donné qu'il faut au minimum deux positions géographiques pour déterminer une droite courante, les étapes 310 à 382 ne sont exécutées que lorsqu'au moins deux positions géographiques ont été obtenues à l'étape 300. En conséquence, suite à la première exécution de l'étape 300, l'étape 390 finale est exécutée, étape lors de 30 laquelle la valeur de la variable k est incrémentée d'une unité: k=1. A la prochaine exécution de l'étape 300, ainsi qu'à toutes les suivantes, une nouvelle position géographique P(k) est obtenue. A l'étape 305 cette nouvelle position P(k) est mémorisée dans le tableau TP. A l'étape 310, la valeur V(k) de vitesse de déplacement du véhicule entre ladite 35 position courante P(k) et la position courante précédente P(k-1) est déterminée. Cette 2907581 8 valeur de vitesse est obtenue en divisant la distance entre ces deux positions par l'intervalle de temps séparant la mesure de P(k) et de celle de P(k-1). Dans le cas où la mesure d'une position géographique du véhicule est espacée de la précédente d'un intervalle de temps constant, il suffit de connaître la valeur de cet intervalle de temps. 5 Dans le cas contraire, il est nécessaire d'obtenir pour chaque position géographique une information d'horodatage de la mesure. A l'étape 320 la valeur V(k) de vitesse déterminée à l'étape 310 est comparée avec la valeur de seuil VS(0). Si V(k) est inférieure à VS(0), on passe à l'étape 330, sinon, le point Pmem est modifié en vue de la prochaine itération avec les coordonnées 10 du point P(k), puis on passe à l'étape 360. A l'étape 330, la distance d(k) entre P(k) et le point Pmem est calculée. A l'étape 340, on compare la distance d(k) avec un seuil 8 correspondant à un seuil de précision sur les mesures des positions géographiques. Si, à l'étape 340, la distance d(k) est inférieure (ou égale) à ce seuil 8, le nouveau 15 point P(k) n'est pas pris en considération: aucune droite courante n'est déterminée et la distance totale parcourue dtota, est inchangée. On passe ensuite à l'étape 390. Si, à l'étape 340, la distance d(k) est supérieure (ou égale) au seuil 8, la nouvelle droite courante est la droite définie par P(k) et Pmem, la distance dtota, étant incrémentée de la valeur de d(k). Puis la position géographique P(k) est mémorisée dans Pmem• On 20 passe ensuite à l'étape 390. A l'étape 360, exécutée suite à l'étape 330, on détermine la droite DR(k) par régression linéaire des points contenus dans le tableau TP. On détermine ensuite la valeur aR(k) en angle de la pente de cette droite DR(k). A l'étape 365, on détermine la droite D1(k) définie par P(k) et P(k-1). On 25 détermine ensuite la valeur al(k) en angle de la pente de cette droite D1(k). A l'étape 370, on détermine une valeur d'angle 0(k) associée à la valeur de vitesse V(k). Cette valeur d'angle est la valeur d'angle associée à l'intervalle [VS(i), VS(i+1)[ dans lequel se trouve la valeur de vitesse V(k) déterminée. A l'étape 375, on compare la valeur absolue de la différence entre aR(k) et al(k) 30 avec la valeur 0(k) déterminée à l'étape 370. Cette comparaison permet de déterminer de quelle manière la trajectoire du véhicule va être approximée. Deux cas se présentent. Si la valeur absolue de la différence est inférieure à 0(k), on passe à l'étape 381. Si la valeur absolue de la différence est supérieure à 0(k), on passe à l'étape 382. En cas d'égalité entre la valeur absolue de la différence et 0(k), on exécute 35 indifféremment l'étape 381 ou l'étape 382. 2907581 9 A l'étape 382, la distance dtota, est incrémentée de la valeur de la distance entre le premier point du tableau TP et le point P(k-1), la droite courante D(k) associée au point P(k) étant la droite passant par les points P(k) et P(k-1). Puis la position géographique P(k-1) est mémorisée dans Pmem en vue d'une prochaine itération. Les points du 5 tableau autres que P(k-1) et P(k) sont supprimés de ce tableau. On passe ensuite à l'étape finale 390. A l'étape 381, la droite courante D(k) associée au point P(k) est la droite DR(k) déterminée précédemment. La distance dtota, reste inchangée, elle ne sera mise à jour que lors d'une prochaine exécution de l'étape 382, 350 ou 390. On passe ensuite à 10 l'étape finale 390. A l'étape 390, la valeur de l'indice k de la position courante est incrémentée. De préférence, lorsque cette valeur est supérieure à une valeur de seuil kmax correspondant à la taille maximale du tableau TP, une partie au moins de la trajectoire correspondant aux points de TP est approximée par la droite définie par le premier et 15 le dernier point de cette partie de la trajectoire, la distance dtota, étant incrémentée de la valeur de la distance entre le premier et le dernier point de cette partie de la trajectoire. Les points du tableau faisant partie de la trajectoire ayant fait l'objet de cette approximation sont ensuite supprimés du tableau TP, à l'exception du dernier point de cette partie de trajectoire. 20 Dans une variante simplifiée, si la valeur de k est supérieure à kmax, seul le premier point du tableau TP sera supprimé à cette étape, la distance dtota, étant incrémentée de la valeur de la distance entre le premier et le deuxième point du tableau. Suite à l'étape 390, le procédé reprend à l'étape 300 en vue de la prochaine 25 itération. La figure 2 illustre les différents cas de figure correspondant aux étapes qui viennent d'être décrites. Cette figure représente la trajectoire d'un véhicule dans un espace à deux dimensions x, y. Les différents positions obtenues sont notées P(0) à 30 P(7). Dans la première partie de la trajectoire formée par les points P(0) à P(3), le véhicule roule lentement et effectue un virage important vers la droite. Ce cas de figure correspond au cas V(k) REVENDICATIONS 1. Procédé d'estimation d'une trajectoire décrite par un objet mobile (15), à partir d'une succession de positions géographiques obtenues pour ledit objet, le procédé comprenant, - une étape de détermination d'une valeur (V(k)) de vitesse de déplacement dudit objet à partir d'une position courante (P(k)) et d'une position précédente (P(k-1 )), - une étape de détermination d'une droite courante (Dc(k)) qui est, selon la valeur de vitesse déterminée, soit une première droite (D1(k)) définie par ladite position courante et ladite position précédente, soit une deuxième droite (DR(k)) obtenue par approximation linéaire d'un ensemble comprenant au moins deux positions dont ladite position courante et une position précédente. 2. Procédé selon la revendication 1, dans lequel, lorsque la valeur de vitesse déterminée est supérieure à un premier seuil de vitesse (VS(0)), le procédé comprend une étape de détermination d'une valeur d'angle (0(k)) associée à la valeur de vitesse et d'une différence d'angle de pente entre la première et la deuxième droite, la droite courante correspondant à la deuxième droite lorsque ladite différence est inférieure à la valeur d'angle déterminée et à la première droite lorsque ladite différence est supérieure à la valeur d'angle associée. 3. Procédé selon la revendication 2, comprenant une étape initiale de définition d'une échelle de valeurs (VS(i)) de seuil de vitesse de déplacement dudit objet et d'une valeur d'angle (0(i)) associée à chaque intervalle ([VS(i), VS(i+1)[) de valeurs de vitesse séparant deux valeurs de seuil successives, la valeur d'angle déterminée (0(k)) étant constituée par la valeur d'angle (0(i)) associée à l'intervalle de valeurs de seuil dans lequel se trouve la valeur de vitesse (V(k)) déterminée. 4. Procédé selon l'une quelconque des revendications 2 à 3, dans lequel, lorsque la valeur de vitesse déterminée est inférieure au premier seuil de vitesse (VS(0)), la droite courante est la première droite. 5. Procédé selon l'une quelconque des revendications 1 à 4, lesdites positions géographiques étant déduites des positions géographiques d'un terminal mobile de télécommunication fournies par un réseau de télécommunication auquel accède ledit terminal. 6. Dispositif d'estimation d'une trajectoire décrite par un objet (15), à partir d'une succession de positions géographiques obtenues pour ledit objet, le dispositif 2907581 14 comprenant, - des moyens de détermination d'une valeur (V(k)) de vitesse de déplacement dudit objet à partir d'une position courante (P(k)) et d'une position précédente (P(k-1)), 5 - des moyens de détermination d'une droite courante (Dc(k)) qui est, selon la valeur de vitesse déterminée, soit une première droite (D1(k)) définie par ladite position courante et ladite position précédente, soit une deuxième droite (DR(k)) obtenue par approximation linéaire d'un ensemble comprenant au moins deux positions dont ladite position courante et ladite position précédente. 10 7. Dispositif selon la revendication 6, comprenant des moyens pour accéder à un réseau de télécommunication, lesdites positions géographiques étant déduites des positions géographiques d'un terminal mobile de télécommunication fournies par ce réseau. 8. Terminal (10, 30) de télécommunication comprenant un dispositif selon la 15 revendication 7. 9. Serveur (20) de traitement de données, comprenant un dispositif selon la revendication 7, le dispositif étant connecté audit réseau de télécommunications et apte à recevoir via ledit réseau lesdites positions géographiques dudit terminal mobile de télécommunication. 20 10. Support d'enregistrement comprenant un programme comprenant des instructions de programme pour la mise en oeuvre des étapes du procédé selon l'une quelconque des revendications 1 à 5 lorsque ledit programme est chargé et exécuté dans un système informatique.