Brevet FR2724021A1 — publié le 19960301

La présente invention se rapporte aux procédés qui permettent de suivre des mobiles dans un environnement bruité pour en reconstituer la trajectoire et obtenir une estimation correcte de leur position instantanée. On est souvent amené à déterminer la trajectoire d'un ou de plusieurs mobiles, en vue essentiellement d'effectuer une poursuite de ces mobiles, en utilisant un ensemble de capteurs, par exemple des hydrophones suspendus à des bouées dans le cas de mobiles marins. Les signaux reçus par les capteurs sont souvent fortement boités, ce qui entraine aussi bien des fausses alarmes que des non détections. En considérant alors l'ensemble des couples instants successifs/ mesures successives correspondant à une succession d'évènements détectés, chaque évènement détecté peut correspondre soit à une fausse alarme, soit à une source dont on cherche à déterminer l'évolution temporelle. Cette source est caractérisée à chaque instant par sa position X, sa vitesse V et son accélération A. Bien entendu une source donnée n'est pas nécessairement détectée à chaque instant, ce qui correspond à une non détection. La situation la plus intuitive correspond à un mobile caractérisé par ses coordonnées en deux ou trois dimensions sur lesquelles on effectue une poursuite à partir de mesures successives de sa position eUou de sa vitesse. Les paramètres X, V, A sont alors de dimensions 2 ou 3. Il peut s'agir par exemple d'un réseau de bouées dans lequel chaque bouée comporte un ou plusieurs capteurs qui permettent d'obtenir à des instants successifs des mesures de la position et éventuellement de la vitesse des mobiles observés. Ces capteurs sont alors par exemple du type sonar et permettent d'obtenir des mesures de natures très diverses telles que la distance, I'azimut, le temps de retard, L'écart Doppler, etc. Ces mesures sont préalablement fusionnées pour obtenir des positions potentielles.Comme bien entendu les capteurs peuvent délivrer des signaux conduisant à de fausses alarmes ou à des non détections, I'un des problèmes que tente de résoudre l'invention est d'associer chaque mesure d'un capteur à un mobile poursuivi ou de rejeter cette mesure en la considérant comme une fausse alarme, ceci pour reconstituer la succession des mesures permettant d'obtenir la trajectoire du mobile. Dans un cas particulier la source que l'on cherche à poursuivre est formée par la mesure elle-même, ce qui est le cas par exemple lorsque l'on procède à un pistage de raies fréquentielles à partir de mesures de fréquences élémentaires. Dans ce cas X, V, A sont des dimensions 1. Les approches classiques permettant de réaliser une association temporelle des données dérivent souvent des techniques de suivi radar, comme par exemple celles présentées par Y. Bar-Shalom & T.E. Fortmann dans 'Tracking and Data Association", Academic Press, 1988. Ces méthodes nécessitent d'utiliser une hypothèse sur un modèle sous-jacent à la trajectoire du mobile, en propageant un vecteur d'état entre deux instants successifs. Lorsque plusieurs types de trajectoires sont possibles, il faut les évaluer en parallèle et choisir le modèle le plus probable. On a proposé plus récemment, afin de faciliter les opérations lorsque les conditions de détection sont plus difficiles, par exemple lorsque les mobiles manoeuvrent etlou sont difficilement détectables, d'autres méthodes permettant d'estimer la trajectoire du mobile dans un espace multidimensionnel discrétisé. Dans ces méthodes, on scinde l'espace d'état, correspondant aux positions et aux vitesses représentatives des mobiles en un maillage de cellules élémentaires représentant toutes les valeurs possibles. A un instant donné, on évalue la probabilité de présence du mobile dans une portion de l'espace. On effectue ensuite le suivi du mobile sans explosion combinatoire en utilisant un algorithme de programmation dynamique particulier. Ces procédés sont particulièrement utilisables pour suivre des mobiles faiblement lumineux, comme décrit par Y. Bamiv dans "Dynamic Programming Solution for Detecting Dim Moving Targets", IEEE Trans. onAES, vol. 21, n" 1, pp.144-156,1985 et par Y. Barniv & O. Kella dans "Dynamic Programming Solution for Detecting Dim Moving Targets", IEEE Trans. on AES, vol. 23, n" 6, pp. 776-787, 1987, ou bien pour effectuer un suivi de fréquence, comme décrit par R.L. Streit & R.F.Barrett dans "Frequency Line Tracking Using Hidden Markov Models", IEEE Trans. on ASSP, vol. 38, n" 4, pp. 586-598, 1990, ou encore pour effectuer une imagerie infra-rouge, comme décrit par J. Arnold, S. Shaw & H. Pastemack dans "Efficient Target Tracking Using Dynamic Programming", IEEE Trans. on AES, vol. 29, n" 1, pp.44-56,1993, et aussi pour utiliser une réseau de bouées activées, comme décrit par F. Martinerie dans "Multiple Target Tracking Using Hidden Markov Modelling in a Distributed Sensor Network Context" et dans "Procédé de trajectographie de mobiles dans un environnement bruité", brevet déposé par la demanderesse le 20 mars 1992 sous le n" 9203362. Ces procédés présentent des limitations qui proviennent de la résolution du maillage de l'espace des coordonnées, laquelle est rendue nécessaire pour obtenir un nombre fini d'état à chaque instant. Par ailleurs, même si on limite l'explosion combinatoire c'est à dire la croissance exponentielle du coût de calcul en fonction du temps, le volume des calculs, rendu nécessaire par la recherche globale de la trajectoire, devient très vite prohibitif. Pour éviter l'utilisation d'un tel maillage et obtenir une limite de résolution dépendant uniquement de la précision des mesures tout en limitant l'explosion combinatoire, I'invention propose un procédé de suivi de mobiles en environnement bruité, du type consistant à utiliser une succession temporelle d'ensembles de points de mesure affectés de probabilités pour déterminer parmi les trajectoires passant par ces points celle qui a la meilleure probabilité d'existence caractérisé en ce qu'il consiste, à évaluer également pour chaque ensemble de points de mesure une non détection affectée d'une probabilité, à déterminer sur une longueur correspondant à L instants de mesure successifs toutes les portions de trajectoires passant par tous les points de mesure et toutes les non détections ainsi que les probabilités de ces portions de trajectoire, à effectuer ensuite la même détermination sur la longueur L prise avec l'instant de mesure suivant le dernier instant de l'évaluation précédente, à éliminer les portions de trajectoires non compatibles entre ces deux déterminations successives pour obtenir d'autres portions de trajectoire de longueur L + 1 associées elles-mêmes à une probabilité et à itèrer ce processus jusqu'à obtenir au moins une trajectoire complète associée à une probabilité. D'autres particularités et avantages de l'invention apparaîtront clairement dans la description suivante présentée à titre d'exemple non limitatif en regard des figures annexées qui représentent: - la figure 1, un diagramme du déroulement du procédé selon l'invention; - la figure 2, un exemple de construction d'une portion de trajectoire; - la figure 3, un exemple de recouvrement entre des portions de trajectoire; et - la figure 4, un exemple de reconstitution d'une trajectoire réelle. En se référant à la figure 1, dans laquelle les blocs représentent des traitements de signaux numériques qui peuvent etre effectués par n'importe quel ordinateur, par exemple du type PC, convenablement programmé, on dispose en provenance des capteurs et pour chaque instant de mesure d'un ensemble de mesures physiques qui sont appliquées à un dispositif 101 qui permet la fusion de ces données pour obtenir à chaque instant de mesure un ensemble d'évènements détectés correspondant aux mesures, dans le plan et dans l'espace, des positions, ou des positions et des vitesses, des mobiles qui sont à l'origine des signaux émis par les capteurs. Le traitement permettant d'obtenir la fusion de ces données est connu en soi, en particulier dans les techniques sonar.Ce traitement permet donc d'obtenir ces mesures ainsi que la probabilité que chaque mesure provienne effectivement d'une source et non du bruit. En l'absence d'autres renseignements ces mesures seront considérées comme équiprobables mais on peut avoir des probabilités différentes si on dispose de renseignements particulier, en particulier si les capteurs ont des caractéristiques différentes. En outre le traitement peut éventuellement amener à une non détection. Celle-ci est également associée à une probabilité qui dépend des caractéristiques des capteurs, probabilité de détection Pd et probabilité de fausse alarme Pfa attribuée à ces capteurs, et des mesures à cet instant. Généralement cette non détection est obtenue par le complément à une des probabilités des autres détections à l'instant de mesure. A titre d'exemple, on sait qu'à partir d'un capteur mesurant conjointement les azimuts et les distances d'une source avec une probabilité de détection Pd, on peut déterminer des positions possibles du mobile et une probabilité associée à ces positions. A partir d'au moins deux capteurs distincts permettant de mesurer les distances et les écarts Doppler, on peut obtenir les positions et les vitesses instantanées possibles des mobiles. Les mesures et les probabilités associées déterminées ainsi par le dispositif 101 sont mémorisées sur L instants de mesure successifs dans une mémoire 102. Cette mémoire 102 permet donc de foumir à un dispositif de combinaison 103 les L dernières mesures ainsi mémorisées, afin de déterminer toutes les portions de trajectoires de longueur L qu'il est possible de construire. On a représenté sur la figure 2 certaines parties de ces trajectoires entre les mesures correspondant à 3 instants successifs 1, 2, 3. II y a donc ainsi 2 mesures 1, 2 mesures 2, et 2 mesures 3. Ce dispositif de combinaison 103 détermine donc toutes les portions de trajectoires de longueur L qui passent à chaque instant, soit par une des mesures de cet instant (trait plein), soit par une non détection (trait pointillé). Le nombre total de sorties est donc proportionnel au nombre de mesures à chaque instant augmenté d'une non détection éventuelle. La figure a été limitée à 3 instants successifs pour faciliter sa visibilité, mais il est préférable dans un exemple de réalisation pratique de prendre L=6 quand on a des mesures de position seules, et L=5 quant on a des mesures de position et de vitesse. Un tel choix permet d'inclure au plus deux non détections sur chaque portion de trajectoire et d'obtenir l'accélération et la variation de cette accélération. Pour éviter de multiplier les possibilités, et donc les besoins en puissance de calcul, on peut en outre réduire le nombre de portions de trajectoires considérées en ne conservant que celles qui passent par au moins 4 mesures si les mesures élémentaires sont des positions (donc au plus L-4 non détections) et celles qui passent par au moins 3 mesures si les mesures élémentaires sont des positions et des vitesses (donc L-3 non détections). De même, dans le cas où les mesures portent sur des positions et des vitesses, on peut utiliser des tests de compatibilité entre évènements détectés successifs, pour écarter les portions de trajectoire sur la base de la compatibilité d'une variation de vitesse entre deux détections successives compte tenu des caractéristiques dynamiques des mobiles, qui sont connues de manière éventuellement grossière mais suffisante pour éliminer des mesures aberrantes telle qu'une accélaration incompatible avec la tenue mécanique du mobile ou la puissance de son moteur. Chaque portion de trajectoire ainsi retenue est ensuite appliquée à un dispositif de calcul des probabilités 104, qui permet d'évaluer la probabilité pour qu'un mobile parcourt cette portion de trajectoire. Si une portion de trajectoire examinée se termine par une non détection à l'instant courant, on considère que le traitement n'a apporté aucune information nouvelle et la probabilité de passage par cette portion de trajectoire est prise comme égale à la probabilité de non détection de la mobile à l'instant courant, soit: P(portion~trajectoire)= p (1) Si la portion de trajectoire examinée se termine sur une nouvelle position à l'instant courant, on peut alors évaluer la vraisemblance d'une trajectoire complète se terminant sur cette position. De manière préférentielle, I'invention propose de considérer comme peu probable une variation d'accélération, et donc de rendre a priori plus probable un mouvement uniformément accéléré.Ainsi les manoeuvres du mobile restent toujours possibles mais elles sont moins probables que l'absence de manoeuvres. Dans ces conditions, on peut alors utiliser une Gaussienne centrée en variation d'accélération nulle, et la probabilité de chaque portion de trajectoire s'exprime par: P(portion~trajectoire)=pOKexp avec pO = probabilité a priori pour que la mesure à l'instant courant soit une mesure de la cible = = variation d'accélération aa = écart type K = facteur de normalisation. Selon que l'on veut rendre plus ou moins probable les variations d'accélération; on prendra un écart type a, plus ou moins grand en fonction surtout des connaissances sur les mobiles. Le facteur pO dépend surtout du nombre de capteurs (nombre de bouées par exemple) mis en oeuvre. Le choix de cette fonction permet de rendre plus probable des trajectoires simples, mais il serait possible d'en utiliser d'autres favorisant des trajectoires "simples", telles qu'un mouvement uniforme par exemple. Pour calculer la variation d'accélération a a' on applique les équations de la mécanique classique en utilisant les évènement détectés successifs les plus récents possibles, et en se fondant sur le fait que; selon que l'on dispose ou non des mesures de vitesse, il est nécessaire d'utiliser les 3 ou les 4 dernières mesures non nulles pour obtenir cette variation d'accélération. Ainsi avec seulement les 4 dernières mesures de position, on appliquera les calculs donnés par le tableau suivant, où t sont les temps, v les vitesses, a les accélérations et aa les variations d'accélérations: Lorsque l'on dispose aussi des mesures de vitesse, on utilisera les 3 dernières mesures, en appliquant les calculs suivants qui exploitent de plus un certaine redondance de l'information pour vérifier la compatibilité entre les mesures de vitesse et les vitesses estimées: Ayant ainsi obtenu les portions de trajectoires sur L instants successifs, on détermine de la même manière les portions de trajectoire sur L instants successifs puis avec l'instant d'après.Ces portions se recouvrent donc sur L-1 instants successifs, et les trajectoires devant être continues, il faut que les portions successives des trajectoires ainsi calculées se raccordent, ce qui revient à dire que les L-1 premières positions d'une portion de trajectoire suivante doivent être identiques aux L-1 dernières positions d'une portion de trajectoire précédente. Dans ce cas, la probabilité de transition entre les portions de trajectoire est identique pour toutes les portions compatibles. Par souci de simplification, on prendra cette probabilité égale à 1. Si les trajectoires ne se recouvrent pas, la transition est impossible et la probabilité de transition est nulle. On a représenté sur la figure 3 un exemple de recouvrement entre portions de trajectoires sur 5 instants successifs, dans lequel le trait continu correspond à une portion de trajectoire A sur 4 points définie à l'instant 4, le trait discontinu correspond à une portion de trajectoire à l'instant 5 compatible avec A, et le trait en pointillé à une portion de trajectoire à l'instant 5 incompatible avec A et présentant une non détection à l'instant 3. La probabilité d'une trajectoire complète est alors le produit des probabilités de chaque portion de trajectoire calculées dans le dispositif 104 par la probabilité de transition entre deux portions successives, qui vaut 1 si les portions sont compatibles et 0 dans le cas contraire. Le problème de la recherche des trajectoires optimales (c'est-àdire de plus forte probabilité) se prête à une formalisation connue par modèles de Markov cachés: - les portions de trajectoire de longueur L correspondent chacune à une valeur possible de l'état X à l'instant k; - L'ensemble des mesures des L derniers instants constitue l'observation Ok à l'instant k; - la probalité Bi(Ok) que l'observation Ok ait été émise par l'état i est interprétée comme la probabilité que le mobile soit passé par la portion de trajectoire représentée par l'état i ; elle est calculée comme décrit plus haut; - la probabilité de transition Aij entre les états i et j, probabilité de passer d'une portion de trajectoire à la suivante, est à 1 si les trajectoires sont compatibles, ou à 0 dans le cas contraire; - la probabilité a priori xj de commencer dans l'état i permet d'initialiser la recherche sur le début de la trajectoire si on dispose de cette information; à défaut toutes les positions initiales sont équiprobables. A partir de la donnée du modèle X = (, A, B) et des observations O (o1...ok), la succession d'états X = ..... .xi) la plus probable expliquant les observations est celle qui maximise la probabilité: P(O,X/h) = x,lB,l(ol)A,1 ,x2Bx2(02)Ax2,x3.. . Bxk(ok) (5) On obtient donc la succession optimale de portions de trajectoire décrivant la trajectoire du mobile parmi les mesures en cherchant la succession de portions de trajectoires compatibles qui maximise cette expression. L'invention propose pour cela d'utiliser l'algorithme de programmation dynamique connu sous le nom d'algorithme de Viterbi et décrit par G.D. Forney dans 'The Viterbi Algorithm", Proc. of the IEEE, vol.61 ,n0 3, 1973, qui permet une résolution efficace de ce problème. Cet algorithme qui est mis en oeuvre dans l'organe 105 procède de manière itérative, en évitant l'explosion combinatoire. A chaque instant, et pour chaque portion de trajectoire considérée, il calcule la probabilité de tous les chemins compatibles avec cette portion. La probabilité d'un nouveau chemin est le produit de la probabilité de l'ancien chemin et de la probabilité de la nouvelle portion de trajectoire compatible. Seul le meilleur chemin trouvé est conservé, en gardant sa probabilité et la trace de l'ensemble des portions de trajectoire qui le composent. On obtient donc un meilleur chemin possible pour chaque portion de trajectoire terminale possible (c'est-à-dire pour chaque portion de trajectoire se terminant sur une détection de l'instant courant). Ces nouveaux chemins sont utilisés pour l'itération suivante. A la fin du traitement, on choisit le chemin ayant la plus forte probabilité parmi tous les chemins terminaux (soit un chemin par portion de trajectoire possible au dernier instant). Les portions de trajectoire successives qui forment ce chemin permettent de reconstruire immédiatement la trajectoire complète du mobile comme on l'a représenté sur l'exemple de la figure 4, où les 3 carrés noirs 401 sont les capteurs, les croix les mesures, la ligne en pointillés la trajectoire réelle obtenue par d'autres moyens pour qualifier le procédé et la ligne discontinue la trajectoire calculée. On remarque l'excellente concordance de la trajectoire calculée et de la trajectoire réelle. L'initialisation du système est inutile, puisque le choix de la piste la plus probable est automatique; on peut cependant l'utiliser si l'on dispose d'informations antérieures sur le mobile ce qui permet de raccourcir la durée du traitement. Afin de réduire l'explosion combinatoire, on utilise avantageusement des heuristiques fondés sur des connaissances a priori sur le comportement du mobile qui permettent de limiter le coût de calcul de la méthode. La combinatoire de tous les chemins de longueur L à chaque instant peut être elle aussi réduite en exploitant plusieurs propriétés. Sur les L mesures considérées à chaque instant, seules les 3 ou 4 dernières détections sont absolument nécessaires pour calculer la probabilité d'observation; on peut donc ignorer toute information supplémentaire. Les chemins sont donc construits de manière arborescente à partir de l'instant courant en remontant dans le passé jusqu'à avoir 3 ou 4 mesures utilisables. Les vitesses et accélérations sont calculées au cours de la construction du chemin, sur 2 ou 3 mesures. Des seuils sur la vitesse et l'accélération permettent d'éliminer dès ce moment des combinaisons de mesures qui sont totalement impossibles. Tous les chemins qui en découlent en raison de la combinatoire sont aussi éliminés. Un grand nombre de cas sont ainsi écartés, bien que l'impact de cette heuristique dépende de la valeur des seuils. Les transitions sont autorisées uniquement entre des chemins qui se recouvrent. Lorsqu'une portion de chemin recouvre une portion de chemin qui n'était pas possible à l'instant précédent (c'est-à-dire tous les chemins qui y passent étaient rejetés), alors il est inutile d'approfondir la recherche, et le chemin courant est rejeté. Enfin, un seuillage classique sur les probabilités des chemins est appliqué. Ceci permet d'éliminer tout chemin dont la probabilité cumulée est inférieure d'un certain pourcentage à celle du chemin le plus probable, sans grand danger pour l'optimalité du résultat. On peut traiter le cas où il y a plusieurs mobiles comme une simple extension du cas où le mobile est unique. Comme l'algorithme de Viterbi permet de connaître la succession la plus probable entre les états, et donc la trajectoire la plus probables, si un autre mobile est présent, et que sa trajectoire ne présente pas de recouvrement avec la précédente (cas le plus général), celle sera aussi détectée par l'algorithme de suivi. II s'agit cependant d'un fonctionnement sous-optimal. Une autre procédure, ne permettant pas un traitement en temps réel, consisterait à extraire le chemin d'un mobile déjà détectée et à itérer le processus. En l'absence de mobile, aucun chemin continu n'apparaîtra vraisemblable. L'invention ainsi décrite permet d'effectuer un suivi de trajectoire en associant à chaque instant le mobile à une mesure de capteur, au lieu de l'associer à une cellule de maillage. On évite ainsi l'utilisation d'un maillage sur l'espace des coordonnées des mobiles. La seule limite de résolution est alors la précision des mesures. L'utilisation des modèles de Markov cachés tels que décrits par L.R. Rabiner & B.H. Juang dans "An Introduction to Hidden Markov Models", IEEE ASSP Mag., jan. 1986, et l'utilisation de l'algorithme de Viterbi permettent de suivre les trajectoires des mobiles manoeuvrants tout en limitant l'explosion combinatoire, et il n'est pas nécessaire de connaître la position initiale de la mobile. La différence par rapport au système décrit par P. Depalle, G. Garcia & X.Roder dans 'Tracking of Partials for Additive Sound Synthesis Using Hidden Markov Models", IEEE ICASSP, pp.225-228, 1993, consiste à prendre en compte les non détections, ce qui permet d'éviter la suppression des pistes lorsque la mesure disparaît à un instant donné. Ainsi on n'évalue pas une trajectoire complète, mais on construit les portions successives de trajectoire en qualifiant ces portions en évaluant leur déviance par rapport à une trajectoire simple, c'est-à-dire par exemple une trajectoire rectiligne uniforme ou un mouvement uniformément accéléré. II est possible d'intégrer dans le calcul des contraintes sur les vitesses et les changements de cap ou d'accélération que peuvent effectuer les mobiles et le trajet global résulte alors de la meilleure succession des portions de trajectoire par application de l'algorithme de Viterbi, connu aussi sous le nom de programmation dynamique. L'absence d'hypothèse à long terme autorise toutes les manoeuvres du mobile. Ainsi le procédé selon l'invention est capable de suivre un mobile en présence de bruit, même si ce mobile n'est pas détecté à chaque instant. L'espace position/vitesse n'est pas représenté par un ensemble discret ce qui limite la résolution uniquement à celle de la précision des mesures. On ne conserve pas de vecteur d'état ce qui évite d'initialiser la position du mobile et permet de suivre plus facilement les mobiles qui manoeuvrent. REVENDICATIONS 1. Procédé de suivi de mobiles en environnement bruité, du type consistant à utiliser une succession temporelle d'ensembles de points de mesure affectés de probabilités pour déterminer parmi les trajectoires passant par ces points celle qui a la meilleure probabilité d'existence caractérisé en ce qu'il consiste à évaluer également pour chaque ensemble de points de mesure une non détection affectée d'une probabilité, à déterminer (103) sur une longueur correspondant à L instants de mesure successifs toutes les portions de trajectoires passant par tous les points de mesure et toutes les non détections ainsi que les probabilités (104) de ces portions de trajectoire, à effectuer ensuite la même détermination sur la longueur L prise avec l'instant de mesure suivant le dernier instant de l'évaluation précédente, à éliminer (105) les portions de trajectoires non compatibles entre ces deux déterminations successives pour obtenir d'autres portions de trajectoire de longueur L + 1 associées elles-mêmes à une probabilité et à itèrer ce processus jusqu'à obtenir au moins une trajectoire complète associée à une probabilité. 2. Procédé selon la revendication 1, caractérisé en ce qu'il consiste à obtenir plusieurs trajectoires complètes, à retenir celle affectée de la plus forte probabilité. 3. Procédé selon l'une quelconque des revendications 1 et 2, caractérisé en ce qu'il consiste à déterminer les probabilités des portions de trajectoires en favorisant les évolutions simples des mobiles. 4. Procédé selon la revendication 3, caractérisé en ce qu'il consiste à favoriser un mouvement uniformément accéléré. 5. Procédé selon la revendication 4, caractérisé en ce qu'il consiste à favoriser un mouvement uniforme. 6. Procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce qu'il consiste à éliminer les portions de trajectoire correspondant à des mouvements incompatibles avec les caractéristiques des mobiles. 7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce qu'il consiste à déterminer la compatibilité entre les portions de trajectoire successives utilisant un modèle de Markov caché. 8. Procédé selon la revendication 7, caractérisé en ce qu'il consiste à traiter le modèle de Markov avec l'algorithme de Viterbi.