Brevet FR3052275A1 — publié le 20171208

PROCEDE ET SYSTEME DE DETERMINATION DE CELLULES TRAVERSEES PAR UN AXE DE MESURE OU DE VISUALISATION L'invention concerne un procédé et un système de détermination de cellules situées sur un axe ou un trajet entre un premier point source et un deuxième point. L'invention s'applique dans des systèmes électroniques de perception pour l'aide à la navigation. Ce type de dispositifs est utilisé dans le domaine de l'automobile, de la robotique, du drone, dans les chaînes de production automatisées, etc., dans le but notamment de détecter et de déterminer la position d'un corps matériel susceptible de se trouver sur la trajectoire d'un dispositif en mouvement. On entend par « corps matériel », toute substance ou objet matériel présentant une individualité et pouvant être détecté et identifié par un capteur approprié. Ainsi, sont considérés comme des corps matériels les objets inanimés, qu'ils soient naturels ou artificiels, les végétaux, les animaux, les êtres humains, mais aussi des particules liquides ou solides en suspension dans l'air, comme les nuages, voire des masses liquides ou gazeuses. L'invention peut aussi être utilisée dans le domaine de reconstruction d'images, afin de déterminer les informations à utiliser pour reconstruire une image dans une direction de vision donnée, par exemple selon un axe d'observation ou de vision d'un capteur. Dans le domaine de la perception d'objets, il existe deux principales familles de technique de perception : les méthodes géométriques, qui visent à identifier la géométrie des objets de l'espace environnant, et celles à base de grille d'occupation, qui visent à déterminer si un certain emplacement est occupé par un obstacle, plus généralement par un corps matériel. L'invention relève des techniques à base de grille d'occupation. Pour capturer et interpréter l'environnement, le système de perception emploie des capteurs de distance qui renseignent sur 3052275 2 l'éloignement des obstacles alentours. Ces capteurs de distance peuvent classiquement être : des radars, des capteurs ultrasonores, des imageurs 3D, des systèmes de stéréovision, des LIDARs (Light Detection And Ranging), etc. Pour améliorer la robustesse de la fonction de perception et 5 pour accroître le champ de vision global, le système intègre plusieurs capteurs hétérogènes. Une des difficultés est de déterminer, avec précision et dans un temps de calcul raisonnable, les cellules susceptibles d'être traversées ou observées par un dispositif en déplacement afin de leur associer une information relative à la présence ou à l'absence d'un obstacle. 10 Les contraintes rencontrées sont principalement de deux ordres, le besoin en calcul et le besoin en mémoire. Une grille d'occupation est une partition de l'espace observé en cellules. Pour chaque cellule, on cherche son état. Par exemple, deux issues peuvent être possibles, « occupée » ou « vide. Le niveau de certitude sur 15 l'occupation d'une cellule est alors donné, par exemple, avec la probabilité de l'évènement « O =occupée » noté P(0) et avec le complémentaire P(e)=1-P(0). Dans d'autres applications, on pourra associer à une cellule une valeur ou un paramètre encodant la connaissance d'une autre grandeur spatiale, comme la pollution de l'air, ou la température d'une zone. Les 20 probabilités d'occupation sont, par exemple, estimées à partir de la connaissance de l'environnement extérieur fournie par les capteurs. L'exemple donné en figure 1, représente la mise en oeuvre du framework des grilles d'occupation pour un véhicule 1 équipé d'un capteur de distance 2 à l'aide d'une grille régulière G. Chaque cellule de cette grille 25 représente un fragment de l'espace situé devant le véhicule, et pour chaque cellule la probabilité d'occupation est calculée. Une valeur supérieure à 0,5 indique une certitude plus élevée que la cellule en question soit occupée. Inversement, une valeur inférieure à 0,5 indique que la cellule a plus de chance d'être libre. La probabilité égale à 0,5 indique qu'aucune information 30 pertinente n'est disponible pour se prononcer sur l'état de la cellule. 3052275 3 En fonction des applications, il peut être critique de déterminer les cellules occupées (analyse de trajectoire des obstacles, suivi de cible, etc.) ou les cellules vides (planification de déplacement, évitement, etc.). L'avantage du framework des grilles d'occupation est qu'avec une unique 5 modélisation de l'environnement plutôt simple on représente les deux types d'informations. Sur la figure 2, un modèle de capteur 1D est utilisé pour l'évaluation de l'occupation d'une cellule. Ce modèle de capteur connu de l'homme du métier permet l'évaluation de l'occupation dans une grille 1D 10 représentée sur la gauche de la figure 2. Les informations d'occupation 1D sont ensuite mappées dans un modèle 2D, partie droite de la figure 2. Cela nécessite en premier lieu de positionner le capteur S dans la grille, puis la cible F et de déterminer toutes les cellules traversées par la demi-droite [SF] dans la grille. Lorsque plusieurs capteurs sont utilisés, pour chacune des 15 cellules l'information est alors fusionnée avec celle des autres capteurs ayant une information pertinente pour la cellule en question. En 1D ou en 2D, les cellules dont l'information d'occupation (probabilité d'occupation, par exemple) est à mettre à jour se situent entre S et F et aussi au-delà de F, ceci du fait de l'incertitude liée à la précision de mesure du capteur. 20 Un des problèmes pour le calcul de grilles d'occupation 2D ou 3D, lorsque l'on utilise plusieurs capteurs hétérogènes positionnés en différents emplacements de l'espace étudié, est que le besoin en calcul explose. En effet, pour chaque mesure le profil d'occupation 1D correspondant à une cellule est calculé, puis ce profil 1D est mappé et fusionné dans une grille de 25 dimension plus grande. Les grandeurs manipulées sont en général des probabilités et des distances, traditionnellement exprimées à l'aide de nombre réels. Ces nombres réels sont la plupart du temps représentés à l'aide de nombres flottants qui imposent au système numérique d'être capable de supporter des opérations arithmétiques flottantes. Par ailleurs, et 30 indépendamment de toute représentation numérique, le problème de mapping est intrinsèquement délicat car il met en oeuvre du calcul exploitant 3052275 4 de l'information à différentes résolutions spatiales. En effet, la position des capteurs et leurs réponses sont, la plupart du temps, connues à des résolutions spatiales supérieures à celle de la grille. La représentation des distances à l'aide de nombres flottants est alors souvent utilisée, car elle 5 permet de s'abstraire dans le calcul de considération sur la précision des informations spatiales. Différentes méthodes sont connues de l'art antérieur pour la détermination de cellules occupées dans des grilles et aussi pour la manière d'obtenir l'information renseignant une cellule. 10 Le document intitulé « A Fast Voxel Traversai Algorithm for Ray Tracing" de A. W. John Amanatides, Eurographics, 1987, divulgue un algorithme de tracé de ligne dans un environnement 2D ou 3D. Cet algorithme consiste à évoluer sur l'équation paramétrique de droite 2D ou 3D et à collecter l'ensemble des cellules traversées. Cet algorithme requiert 15 néanmoins une opération flottante à chaque itération (passage à la cellule suivante). Le document de A. Hornung, K. M. Wurm, M. Bennewitz, C. Stachniss, and W. Burgard intitulé "OctoMap: an efficient probabilistic 3D mapping framework based on octrees" publié dans Autonomous Robots, 20 2013, décrit une méthode pour représenter des grilles d'occupation tridimensionnelles. Le framework général permet l'intégration continue d'information de capteurs et décrit comment les informations sensorielles sont mappées dans l'environnement. La méthode exploite alors les travaux d'Amanatides précités pour le mapping de l'information d'environnement. 25 L'algorithme décrit dans le document de J.E. Bresenham intitulé « Algorithm for computer control of a digital plotter », IBM Systems Journal, 1965, permet de tracer une ligne sur un écran. L'objectif de l'algorithme est d'être ultra performant, et de donner un résultat satisfaisant à l'oeil. D'un point de vue mathématique, le principe consiste à déterminer tous les pixels 30 (cellules) traversés par une ligne (mesure capteur). Cet algorithme ne nécessite que des opérations entières sans multiplication ni division. En 3052275 5 revanche, certains pixels traversés par la ligne ne seront pas affichés, et certains pixels affichés ne sont pas mathématiquement traversés par la ligne. La demande de brevet FR1558919 du demandeur décrit une méthode permettant de réaliser la fusion de l'information d'occupation au 5 niveau d'une cellule. Cette technique permet de construire le résultat de la fusion au moyen d'opérations arithmétiques uniquement. En revanche, la méthode ne décrit pas comment résoudre le problème du mapping de l'information 2D ou 3D en arithmétique entière. Dans la demande de brevet W02013189482, une représentation 10 des grilles d'occupation à l'aide de quadtree est proposée. L'usage des quadtree pour les grilles d'occupation 2D pour les applications automobiles est motivée pour principalement deux raisons : - Les capteurs ne travaillent pas forcément aux mêmes résolutions, et il peut être judicieux d'avoir une structure de données hiérarchique qui 15 permette un traitement de l'information multi-résolution, - Les applications n'exploitent pas nécessairement l'information à la même résolution (freinage urgence, vs navigation par exemple). La difficulté technique résolue par cette méthode permet de construire une information de plus basse résolution à partir d'une information de plus faible 20 résolution. Elle ne décrit pas comment le mapping de l'information est réalisé à quelque résolution que ce soit. Il est donc important de disposer d'une méthode permettant de déterminer, simplement et avec un nombre faible de ressources de calcul, les coordonnées des cellules dont on souhaite mettre à jour la valeur de 25 probabilité d'occupation ou une valeur représentative du contenu de la cellule traversée. Dans la suite de la description, l'expression « cellule traversée » désigne une cellule qui est traversée ou observée par le champ de vision d'un capteur ou d'un observateur. 30 Une fonction d'erreur Err() est définie comme une fonction qui permet de calculer une valeur d'erreur représentative de la position d'au 3052275 6 moins une coordonnée d'un point appartenant à une grille d'occupation par rapport à un trajet défini dans un espace d'observation. Des exemples seront donnés par la suite. A cet effet, l'invention vise à fournir une méthode de détermination 5 des cellules nécessitant moins de ressources que les méthodes proposées dans l'art antérieur. L'invention permet aussi d'optimiser la phase de mapping de l'information de l'occupation dans une grille, quelque que soit sa dimension, 1D, 2D, 3D, etc., pour la rendre beaucoup moins contraignante pour l'architecture de calcul, plus rapide tout en assurant une précision par 10 rapport aux approches flottantes traditionnelles. L'invention concerne un procédé pour déterminer les coordonnées de cellules ci susceptibles d'être traversées dans un espace d'observation représenté par une grille G ayant un premier pas de résolution RG, une cellule étant représentée par des sommets et des segments reliant ces 15 sommets caractérisé en ce qu'il comporte au moins les étapes suivantes : - Définir les coordonnées d'un point M en utilisant un espace discrétisé à l'aide d'un pas spatial ô, le pas spatial ô étant inférieur au pas de résolution RG de la grille G, la taille des cellules étant définie par taille(c) = r - ô, r E N, le point M de coordonnées (I,m) dans cet 20 espace discrétisé se situe dans l'espace continu au point (x,y), où x = 1. y = m - ô' - Initialiser une fonction d'erreur Err() représentative de la position d'au moins une coordonnée d'un sommet V de la cellule cs contenant le point source S par rapport à un trajet défini dans l'espace 25 d'observation, le trajet reliant un point source S à un point final F, - Calculer la valeur d'erreur Errd() obtenue pour au moins un premier sommet V de la cellule de la grille en cours d'observation, - Etudier la valeur de l'erreur Errd(V) calculée par rapport à une valeur de référence et déterminer le côté traversé de la cellule observée par 30 le trajet [SF] et la cellule suivante ci_otraversée, 3052275 7 - Utiliser cette cellule suivante ci+i et un premier sommet Vi+1 de cette cellule comme point de départ et réitérer les étapes jusqu'à atteindre au moins la cellule cF contenant le point final F, - Etablir la liste {ci} des cellules traversées sur le trajet [SF] et utiliser les 5 cellules pour caractériser un objet sur le trajet. L'objet peut être un obstacle se trouvant sur le trajet, les cellules sont alors renseignées par une valeur de probabilité d'occupation. L'objet peut être une image que l'on souhaite reconstituer et la cellule sera renseignée par un paramètre représentatif de l'image dans le champ de 10 vision du capteur. L'invention concerne aussi un dispositif pour déterminer les coordonnées de cellules ci susceptibles d'être traversées dans un espace d'observation représenté par une grille G ayant un premier pas de résolution, une cellule étant représentée par des sommets et des côtés ou segments 15 reliant ces sommets, caractérisé en ce qu'il comporte au moins les éléments suivants : - Un ou plusieurs capteurs adaptés à mesurer les coordonnées d'un point mesuré dans le pas de résolution de la grille situé à une distance de la cible F, 20 - Un module de discrétisation des coordonnées mesurées avec un pas de résolution spatial b inférieur au pas RG de résolution de la grille, - Un module de traitement des coordonnées discrétisées adapté à exécuter les étapes du procédé selon l'invention. D'autres caractéristiques, détails et avantages de l'invention 25 apparaîtront mieux à la lecture de la description donnée à titre illustratif et nullement limitatif et faite en référence aux figures qui représentent : - Figure 1, une représentation du modèle d'environnement défini avec une grille d'occupation, - Figure 2, une représentation du mapping d'occupation, 30 - Figure 3A, 3B, une illustration de la recherche de cellules traversées, et figure 3C, le cas de la méthode selon l'invention, 3052275 8 - Figure 3D, 3E , un exemple de recherche de cellules traversées dans un cône défini par un capteur, - Figure 4, un exemple d'étapes du procédé selon l'invention, - Figure 5, un calcul de la représentation entière, 5 - Figure 6, une représentation du domaine englobant, - Figure 7A à 7F, un exemple de parcours d'arbre, - Figure 8, une représentation des coordonnées entières en 3D et figure 9, le passage en coordonnées sphérique, - Figures 10A, 10B, 10C, une représentation de grilles pour la taille de 10 l'environnement, et - Figure 11, un exemple de dispositif pour la mise en oeuvre du procédé selon l'invention. Afin de mieux faire comprendre l'objet de l'invention, l'exemple qui suit est donné à titre illustratif et nullement limitatif pour la détection 15 d'obstacles dans le cas d'une voiture équipée d'une caméra permettant de détecter des obstacles pouvant être présents sur son trajet. Les grilles d'occupation sont une discrétisation de l'espace observé en cellules. Le mapping d'information capteurs « mono-cible » nécessite de pouvoir rapidement trouver les cellules traversées par une 20 droite. Soit S(xs,ys) la position du capteur situé sur la voiture, et F(xF,yF) la cible détectée par le capteur. Les cellules traversées par le segment [SF] doivent subir une mise à jour de l'occupation. Le point M(x,y) est sur la ligne contenant le segment [SF] si et seulement si : Err(M) = (y - y,) ' (xF, - xs) - (x - xs) ' (yp, - Ys) = 0 25 On peut ensuite remarquer que si deux points A et B sont situés de part et d'autre de la ligne, alors on obtient Err(A) et Err(B) avec des signes opposés. Cette propriété permet de déduire un algorithme itératif de recherche des cellules traversées comprenant les étapes suivantes: A1) On initialise pour cela l'algorithme de recherche à la cellule c=cs où Cs 30 est la cellule contenant le point S, comme sur la figure 3A. On suppose que 3052275 9 l'on a parcouru un certain nombre de cellules, et qu'on se situe maintenant dans une cellule traversée c, B1) On calcule alors les erreurs des sommets de Vx, Vy et Vxy de la cellule c, figure 3B : 5 Si Err(Vxy) =0, alors la prochaine cellule est cxy, Sinon, si Err(V,) et Err(Vy) ont des signes opposés, alors la prochaine cellule traversée est cx, Sinon, la prochaine cellule traversée est cy, C1) On continue l'itération jusqu'à ce que la cellule c égale cF la cellule 1 0 contenant le point F. On peut remarquer que l'algorithme suppose (xF-xs)>0 et (yF-Ys)>0. Les autres cas d'inflexion de droites (pentes négatives ou autres) peuvent se déduire facilement de ce premier cas. La principale limitation de cet algorithme est qu'il requiert 15 l'évaluation de la fonction d'erreur en trois points à chaque itération, cette fonction d'erreur nécessitant elle-même plusieurs opérations flottantes. Pour pouvoir calculer les cellules traversées par une ligne dans une grille d'occupation sans recourir au calcul flottant, le procédé selon l'invention utilise une représentation entière (discrète) de l'espace. La 20 principale difficulté réside dans le fait que la discrétisation de la grille elle- même n'est pas suffisante pour le calcul des intersections cellules/ligne. En effet, la position des capteurs peut être connue à une résolution plus importante que celle de la grille. L'idée proposée dans cette invention consiste à exploiter, pour la 25 recherche des cellules traversées, une discrétisation plus fine que celle de la grille pour garantir une précision équivalente à celle obtenue à l'aide de la méthode flottante présentée en figure 3C, tout en n'effectuant que des opérations arithmétiques entières simples et obtenir un gain en temps de calcul et diminuer les ressources nécessaires pour le calcul. On suppose 30 pour cela que l'espace observé est discrétisé à l'aide d'un pas spatial Ô constant, par exemple. Ce pas spatial est la plus petite dimension 3052275 10 représentable dans cet espace discrétisé, et par conséquent les cellules de la grille d'occupation ont des côtés qui doivent être un multiple de Ô. Si la taille des cellules est c, on a : taille(c) = r - ô, r E N Un point de l'espace de coordonnées (I,m) dans cet espace discrétisé se 5 situe dans l'espace continu au point (x,y), avec : x = 1 - ô y = m - 8. Le point S est alors représenté par ses coordonnées (Is, ms) et le point F par ses coordonnées (IF,mF). Toutes les informations spatiales sont alors manipulées avec une précision égale à Ô. Pour résoudre le problème 10 présenté sur la figure 3C, on considère un point M(I, m). Le point M appartient à la droite [SF] si et seulement si : Errd(M) = (m - ms) - (1F - 1s) - (1-1s) - (mF - ms) = 0 (1) Si on note V, le sommet initial d'une cellule, VI, V, et VI, les sommets d'une cellule comme présenté sur la figure 3C, il est possible d'écrire : Errd(Vi) = Errd(V) - Am 15 Errd (Vm) = Errd(V) + Al (2) Errd (Vim) = Errd(Vi) + Al où A/ = n (/F - /a) et Am = r - (mF - ma). Ces quantités sont constantes et peuvent être calculées une fois pour toute la recherche sur la ligne SF. De la définition d'Errd(M) d'une part, et des équations permettant le calcul itératif des erreurs Errd(V1), Errd(V') et Errd(Vim) d'autre part, on peut déduire 20 un algorithme de calcul itératif pour la recherche des cellules traversées par la ligne ou droite [SF] : A2) On commence par trouver la cellule contenant S, puis on initialise la fonction d'erreur à E = Errd(V) à l'aide de l'équation (1), V est le coin inférieur gauche de la cellule dans l'exemple donné, 25 B2) On calcule ensuite les erreurs des autres sommets à l'aide des équations (2), 3052275 11 En comparant, par exemple, le signe des erreurs calculées on détermine la prochaine cellule traversée, de manière analogue à l'algorithme de recherche de cellule précité : Si Errd(Vim)=0, alors c = cim et E = Errd(Vim) 5 Si Errd(Vim) et Errd(V1) sont de signes opposés, alors c = ci et E = Errd(V1) Sinon c = cm et E = Errd(Vm), C2) On continue l'itération jusqu'à la dernière cellule contenant le point F. On a supposé que Am et AI étaient positifs pour cet exemple. Sans sortir du cadre de l'invention, il serait possible d'appliquer ces étapes en les adaptant 10 à des cas où la pente de la droite est négative ou d'autres cas. Ces autres cas se déduisent immédiatement de ce qui précède. Il est aussi possible de considérer non plus le signe de l'erreur calculée, mais la valeur de l'erreur que l'on compare à une valeur de référence. Ce nouvel algorithme de calcul des cellules traversées ne suppose qu'une 15 seule évaluation de la fonction Errd(M), appliquée au sommet inférieur gauche V de la cellule contenant le point de départ, dans l'exemple donné. L'erreur des autres points testés est calculée uniquement de manière incrémentale à l'aide des équations (2). Cet algorithme met en oeuvre deux multiplications et cinq additions signées pour l'initialisation, puis uniquement 20 des additions signées à mesure que l'on parcourt les cellules. Toutes les opérations sont en arithmétique entière. Le procédé permet avantageusement de diminuer le temps de calcul et les ressources nécessaires. A l'issue de ces étapes, le résultat du procédé se traduit sous la 25 forme d'une liste de cellules {ci}, de leurs coordonnées dans la grille G, qui vont être renseignées par une information de probabilité d'occupation, par exemple, ou encore par un paramètre encodant une grandeur spatiale. Les figures 3D et 3E illustrent un exemple de recherche de cellules en regardant non plus le signe de l'erreur calculée mais la valeur de 30 l'erreur. 3052275 12 La figure 3D schématise la distribution d'une erreur pour une erreur d'un sommet compris entre un minimum m et un maximum M. Les cellules représentées avec un rond sont sélectionnées pour la plage d'erreur 0 Err 50 W > 1092(50) + c/ W > 16 Seuls les 16 premiers bits de la représentation entière sont nécessaires pour représenter simultanément une position dans la grille, et un calcul de traversée de grille en entier précis au 50ème de la taille des cellules. Nous avons vu que dans la méthode, il faut commencer par calculer l'erreur 20 initiale qui nécessite deux produits entiers. Les résultats de ces produits peut entraîner la manipulation de nombres dont la largeur excède les W bits de la représentation, ce qui pose problème pour la mise en oeuvre pratique. 3052275 19 Si on regarde plus précisément l'expression de Errd(V), on voit que les quantités (m-me) et (I-le) sont majorées par r=2w-cl et que les quantités (mt-ms) et (Iris) sont majorées par 2w. Si on note T la largeur totale nécessaire pour manipuler les produits on a alors : (T - 1) = 2 - W - cl T + d - 1 W= 5 Le produit ne doit pas excéder T-1 et non pas T, car le résultat des produits peut être signé dans le cas général. En reprenant l'exemple précédent, et en supposant que l'unité arithmétique entière utilisée manipule des nombres sur T=32 bits maximum, pour une grille de profondeur 10, on obtient W=(32+10-1)/2=21. La précision maximale 10 utilisable est W=21 bits. On a alors un calcul de traversée de grille précis à 1 pour 221-10, soit précis au 2048ème. Enfin on remarque que pour le calcul des quantités Am et Al, les mêmes remarques s'appliquent pour la largeur des nombres et la précision du calcul de traversée. La résolution du problème en trois dimensions se généralise 15 directement à partir de la résolution en deux dimensions présentée précédemment. L'idée est d'appliquer ce qui précède à la projection de la ligne 3D sur les trois plans de l'espace z=0 (plan Oxy), x=0 (plan Oyz) et y=0 (plan Oxz). Soit V(I, m, n) un point 3D en coordonnées entières. On forme alors les trois 20 quantités : Errd xy(V) = (m - ms) - (lt - 1,) - (1 - 1,) - (mt - ms) Errd yz(V) = (n - ris) - (mt - ms) - (m - ms) - (nt - ris) Errd ,z(V) = (1 - 1,) - (nt - ris) - (n - ris) - (lt - ls) De manière analogue à ce qui précède en 2D, en notant V, VI, Vm, Vn, Vm, Vin, Vmn, Vimn les sommets d'une cellule tridimensionnelle, comme sur la figure 8. On a alors : Errd xy (V1) = Errd xy(V) - Am Errd xy(Vm) = Errd xy(V) + A/ Errd xy (V1m) = Errd xy(Vi) + A/ 2 3052275 20 Errd_yz(11m) Errd_yz(Vn) Errd yz(Vmn) Errd xz(Vn) Errd xz(V1) Errd xz(V1n) = Errd yz(V) - An = Errd yz(V) + Am = Errd_yz (Vm) + Am = Errd xz(V) - A/ = Errd xz(V) + An = Errd xz(Vn) + An Où A/ = r - (it - /s), Am = r - (mt - ms) et An = r - (nt - ris). De la même façon, on peut ainsi déterminer de façon itérative les estimations d'erreur des différents sommets de la cellule. En regardant le signe des erreurs face par face d'une cellule tridimensionnelle, il sera alors possible de 5 déterminer de manière analogue au cas 2D quelle sera la prochaine cellule traversée par le segment [SF]. Les capteurs de distances utilisés renvoient naturellement de l'information exprimée dans leur repère propre. Ce repère propre est le plus souvent un repère sphérique centré sur le capteur. Le repère sphérique 10 utilisé est décrit sur la figure 9, sur le modèle rayon, longitude, latitude. On suppose que le capteur retourne les trois informations D, a, w : - D : distance de la cible - a : longitude mesurée à partir de l'axe des x - w : latitude, mesurée depuis le plan équatorial 15 Ces informations sont retournées par le capteur sous la forme de champ de bits entiers, à une précision variable d'un capteur à l'autre. La conversion en coordonnées cartésiennes nécessite les calculs suivants : x = D - cos (a) - cos (w) Y = D - cos (a) - sin (w) z = D - sin (a) Le calcul des fonctions trigonométriques et des multiplications flottantes résultantes est très souvent coûteux à réaliser sur un processeur de calcul 20 embarqué. Par ailleurs, pour exploiter les coordonnées entières présentées précédemment, il faut en plus effectuer la transformée : 3052275 21 D - cos(a) - cos(w) + R u = 2w y 2R D - sin (w) + R uz = 2w 2R où R désigne la portée maximale du capteur (xmin=-R et xmax=R, de même pour les autres axes). Le calcul des coordonnées entières nécessite une division flottante supplémentaire. Selon une variante de réalisation, le procédé va calculer les 5 coordonnées entières au moyen d'une étape intermédiaire, qui est le calcul de l'écart au centre, en entier. On introduit pour cela le point K, qui est le centre du repère. On a alors : xmin xmax 2 Ymin Ymax 2 Zmin Zmax ZK Soit, en coordonnées entières : 2 ux2W-1 Ux ux 2W-1 Y ux2W-1 uz Les équations de transformations en coordonnées entières présentées 10 précédemment deviennent alors: ux 2w 2R D - cos (a) - sin (w) + R XK YK Ux - Ux D 2w-1 - cos(a) - cos(w) uY uÿ - u = D 2w-1 - sin (w) qui peuvent être réécrites sous la forme : ux-ux =DD Tx(Ct D T.yTz(a(w:) Uy Uy Uz Liz = 2w-1 - cos (a) - sin (w) Uz- Uz D 3052275 22 Le procédé consiste alors à pré-calculer les fonctions trigonométriques Tx(a,w), Ty(a,w) et Tz(w). Les résultats sont stockés dans une table en entier pour n'avoir à calculer à l'exécution qu'une multiplication entière pour obtenir l'écart au centre en coordonnées entières. Les valeurs de cette table sont 5 alors comprises entre -2w-1/R et 2W-1/R et vont nécessiter d'être stockées sur un champ de bits d'au plus W bits. Si on regarde plus précisément la largeur de l'information de distance renvoyée par le capteur L, on voit que R=2L et que les valeurs de trigonométries peuvent être stockées sur des entiers signés de W-L bits. Par 10 exemple si W=32 bits, et L=16 bits, on va pouvoir tabuler la trigonométrie sur des entiers signés de 16 bits. De plus, on remarque alors que la quantité D/R est comprise entre -1 et 1, ainsi que les produits de fonctions trigonométriques. L'écart au centre est ainsi compris entre -2w-1 et 2W-1, et est donc représentable à l'aide d'un entier 15 W bits signé. Le calcul de la coordonnée entière revient à rajouter 2w1 à la valeur d'écart pour former une quantité comprise entre 0 et 2w. La transformation du repère sphérique (figure 9) vers le repère cartésien en coordonnées entières ne nécessite alors qu'une multiplication et une addition entière par composante. 20 La taille des tables de trigonométries va dépendre de la sensibilité angulaire du capteur utilisé, mais on peut par exemple typiquement avoir pour un capteur ayant un champ de vision de 100° horizontal x 50° vertical précis au degré, une table de 100x50=5000 valeurs entières. Pour L=16 bits pour la distance, et W=32 pour la résolution entière du calcul de mapping, cela 25 implique de stocker les valeurs sur 16 bits (2 octets) soit des tables de l'ordre de 10Ko pour les coordonnés x et y, 100 octets pour la coordonnée z. Pour des modèles plus résolus, la taille des tables peut devenir prohibitive, il est alors possible de diminuer le besoin en mémoire, au prix d'une multiplication entière supplémentaire en séparant les variables. Par exemple 30 pour TX on a : 3052275 23 2(w-1)/2 - cos(a) 2"-1)/2 - cos(w) Tx(a,w) = \/7 \77 La taille des tables est réduite alors drastiquement au prix d'une perte en précision. Dans ce qui a été présenté précédemment, on a supposé que le domaine d'étude de la grille couvrait toute la portée du capteur. Le domaine 5 de définition DG de la grille d'occupation contient ainsi tout le domaine Dc couvert par le capteur de portée maximale R, comme présenté sur la figure 10A. Dans un cas plus général, on voudra fixer le domaine de définition de la grille indépendamment de la portée du capteur. En effet, la taille de la 10 grille est souvent davantage déterminée par l'application que par les caractéristiques physiques du capteur. On pourra par exemple vouloir étudier un domaine de 50mx50m alors qu'on utilise un capteur avec une portée de 200m. La situation correspondante est présentée sur la figure 10B. On considère une grille de côté 2R, où R est la portée maximale exploitée du 15 capteur. La distance maximale visible du capteur est alors Rmax et on a : Rmax > R. Pour une grille de côté 2R, on commence par filtrer les informations de capteurs qui sont en dehors de la sphère de rayon R. Le problème est que les points de la sphère de rayon R ne sont alors pas tous représentables en 20 coordonnées entières, car certains points peuvent être dans la sphère mais en dehors de la grille. La distance maximale Dmax atteignable dans la grille est obtenue en chaque sommet de la grille et vaut Dmax = -'12 - R. En normalisant l'expression précédente par cette nouvelle valeur, on obtient alors : 2W-1 cos(a) - cos(w) K Ux. - Ux. = D -'12 - R 2w-1 - cos (a) - sin (w) uY uÿ - u = D K Uz-Uz -'12 - R 2w-1 - sin (w) = D -'12 - R 3052275 24 En multipliant haut et bas par -\77 on obtient : D 2w-2 - -'77 - cos(a) - cos(w) R 2w-2 - -\17 - cos (a) - sin (w) R 2w-2 - -'12 - sin (w) D On vérifie aisément que comme Dmax = V2 - R, les coordonnées sont comprises entre -2W-1 et 2W-1 et que ces nombres sont représentables sur des entiers signés de W bits. En revanche, la propriété très intéressante que 5 permet cette normalisation par V2 est que si le bit de poids fort est nul, c'est- à-dire que la coordonnée calculée est comprise entre -2w-2 et 2W-2 , et dans la grille. En effet, normaliser par Dmax = V2 - R revient à placer les points dans une grille de 2V2 - R de côté. C'est-à-dire comme précédemment, une grille dont le bord est circonscrit au cercle de rayon Dmax. Or la grille dans laquelle 10 on cherche à placer les informations est, elle, de côté 2R. En plaçant la grille circonscrite et inscrite comme sur la figure 10C, on prouve que le côté de la grille inscrite (2R) est égal à la moitié de la diagonale de la grille circonscrite. Cette demi-diagonale vaut -'77 - Dmax = -\77 - V2 - R = 2R. Par conséquent, la coordonnée 32 bits à la plus grande distance dans la 15 grille circonscrite est à (Dmax, Dmax), soit à une distance de -\/7 - Dmax. Or on sait que cette coordonnée sera représentée sur W bits entiers. Comme V2 - Dmax = 2R, on voit que les coordonnées inférieures qui sont positionnées à au plus R, sont inférieures à V2 - Dmax/2 et donc représentable sur un entier signé de W-1 bits. 20 Le résultat du calcul des coordonnées entières peut donc se résumer à : A3) Former le produit Distance X Trigonométrie, B3) Vérifier que le bit de poids fort est nul, sinon le point n'est pas dans la grille, mais dans la sphère de rayon R, C3) Multiplier le résultat par 2 (décalage d'un rang à gauche) pour obtenir 25 une coordonnée entière de W bits, et rajouter la coordonnée du centre (2W-1). uY uÿ - u = D Uz - Uz 3052275 25 En conclusion le paramétrage ainsi défini permet de fixer la taille de l'environnement indépendamment de la portée du capteur, tout en garantissant la taille finale de la représentation. La résolution spatiale sera alors un peu plus faible (bit de poids faible toujours à 0) mais le calcul entier 5 ne nécessitera pas plus de bits et respectera la contrainte de largeur W. La figure 11 illustre un exemple de système de recherche de cellules selon l'invention donné dans le cas d'un capteur équipant le véhicule 1. Le capteur 100 est positionné sur le véhicule 1 et a une portée et un champ de vision donnés. Le capteur 100 transmet les paramètres mesurés 10 D, a, w correspondant à une première mesure de distance à un obstacle F, à un premier bloc 101 de traitement des données. Le premier bloc 101 est adapté à transformer les coordonnées sphériques en des coordonnées cartésiennes, ux, uy, u7. Les coordonnées transformées sont ensuite transmises à un module 102 de discrétisation des coordonnées sur la grille 15 fine avec un pas de Ô. Les coordonnées « discrétisées » sont traitées par un algorithme embarqué dans le module 103 qui exécute les étapes de l'algorithme de recherche de cellules. L'algorithme Al va rechercher les cellules traversées en considérant une erreur nulle par rapport à une droite. L'algorithme A2 va tenir compte d'une valeur d'erreur comprise dans un 20 intervalle d'erreur donné et l'algorithme A3 va rechercher des cellules traversées dans un cône défini par l'axe de vision du capteur. En sortie du module de recherche des cellules 103, une liste des cellules sélectionnées {ci} est transmise par exemple à un opérateur ou un système d'alerte ou d'affichage 110. 25 Le module 102 comporte un algorithme permettant de représenter dans le domaine numérique un nombre entier tel qu'il a été décrit ci-dessus, afin de représenter sur un nombre de bits donnés la position réelle des coordonnées des points ou d'une cellule. Le système comprend une mémoire interne 105 comprenant les 30 tables trigonométriques Tx, Ty, Tz utilisées pour la transformation des 3052275 26 coordonnées du repère sphérique au repère cartésien. Cette mémoire peut être figée initialement. Il comporte aussi une base de données 106 contenant la position des capteurs. La mémoire peut être renseignée de manière statique ou bien 5 être mise à jour en temps réel afin de prendre en compte le déplacement des capteurs. Les étapes qui viennent d'être décrites peuvent être modifiées pour être mises en oeuvre pour la détermination de cellules susceptibles d'être occupées et selon un parcours ou un trajet d'une voiture comprenant 10 un ensemble de segments de droite par exemple, un trajet non linéaire. La mesure peut être réalisée en prenant comme référence, non pas une droite, mais un axe appartenant au cône d'ouverture du capteur de détection. Le paramètre utilisé pour déterminer le signe de l'erreur pourra être une valeur prédéfinie. 15 L'exemple est décrit pour l'acquisition des données avec un capteur. Les étapes pourront être réitérées sur plusieurs capteurs, les résultats provenant des différents capteurs pouvant être fusionnés selon une méthode connue de l'art antérieur, par exemple, en utilisant le procédé décrit dans la demande de brevet FR1558919 du demandeur. 20 Sans sortir du cadre de l'invention, le procédé peut aussi être utilisé pour déterminer les cellules à utiliser pour la reconstitution d'une image en trois dimensions. L'invention décrite dans ce document permet la réalisation d'un système de perception de l'environnement 2D ou 3D construit à l'aide de 25 plusieurs capteurs de distances hétérogènes placés en différents emplacements. La particularité du système est qu'il emploie notamment pour le mapping des informations d'occupation, une représentation numérique hiérarchique compatible avec l'arithmétique entière traditionnelle disponible dans la majorité des systèmes de calcul. Le calcul du mapping est alors 30 réalisé de façon extrêmement efficace avec de l'arithmétique entière 3052275 27 uniquement, et avec la même précision spatiale que les approches flottantes de référence. De plus l'invention est compatible avec des structures de grilles qui comprennent des cellules de tailles différentes. Cela permet par exemple de 5 définir des grilles d'occupation dont la résolution est adaptée à celles des capteurs, en particulier dont la résolution diminue à mesure que l'éloignement des cellules augmente. REVENDICATIONS1 - Procédé pour déterminer les coordonnées de cellules ci susceptibles d'être traversées dans un espace d'observation représenté par une grille G ayant un premier pas de résolution RG, une cellule étant représentée par des sommets et des segments reliant ces sommets caractérisé en ce qu'il comporte au moins les étapes suivantes : - Définir (401) les coordonnées d'un point M en utilisant un espace discrétisé à l'aide d'un pas spatial ô, le pas spatial ô étant inférieur au pas de résolution RG de la grille G, la taille des cellules étant définie par taille(c) = r - ô, r E N, le point M de coordonnées (I,m) dans cet espace discrétisé se situe dans l'espace continu au point (x,y), où = 1 - Y = m - ô' - Initialiser (404) une fonction d'erreur Err() représentative de la position d'au moins une coordonnée d'un sommet V de la cellule cs contenant le point source S par rapport à un trajet défini dans l'espace d'observation, le trajet reliant un point source S à un point final F, - Calculer (407) la valeur d'erreur Errd() obtenue pour au moins un premier sommet V de la cellule de la grille en cours d'observation, - Etudier la valeur de l'erreur Errd(V) calculée par rapport à une valeur de référence et déterminer le côté traversé de la cellule observée par le trajet [SF] et la cellule suivante ci+1 traversée, - Utiliser (408) cette cellule suivante ci+1 et un premier sommet V 41 de cette cellule comme point de départ et réitérer les étapes jusqu'à atteindre au moins la cellule cF contenant le point final F, - Déterminer (405) la liste {ci} des cellules traversées sur le trajet [SF] et utiliser lesdites cellules pour caractériser un objet sur le trajet [SF]. 2 - Procédé selon la revendication 1 dans lequel le trajet considéré est une droite [SF], le point source S correspond à la position d'un capteur de 3052275 29 détection d'un obstacle, et caractérisé en ce que l'on exécute les étapes suivantes : - On désigne un sommet initial V, - On considère un point M(I, m) dans l'espace discrétisé, 5 - On détermine VI, Vm et Vim les sommets d'une cellule contenant le point M, - On détermine les valeurs d'erreurs: Errd(Vi) = Errd(V) - Am o Errd(Vm) = Errd(V) + A/ Errd(Vim) = Errd(Vi) + A/ où A/ = r - (1F - 1,) et Am = r - (mF - ms), 10 - En comparant le signe des erreurs calculées on détermine la prochaine cellule traversée, de la manière suivante: o Si Errd(Vim)=0, alors c = ch et E = Errd(Vim), o Si Errd(Vim) et Errd(V1) sont de signes opposés, alors c = ci et E = Errd(VI), 15 o Sinon c = cm et E = Errd(Vm), - On continue l'itération jusqu'à la dernière cellule contenant le point F. 3 - Procédé selon la revendication 1 caractérisé en ce que l'on définit une valeur d'erreur comprise entre m et M, on sélectionne les cellules pour 20 lesquelles m Err 4 - Procédé selon la revendication 3 caractérisé en ce que l'on détermine la valeur de l'erreur Errd(V) et on recherche les cellules dont l'erreur est comprise entre -D(V)*m Err 5 - Procédé selon l'une des revendications précédentes caractérisé en ce que l'on représente les coordonnées des points selon des nombres entiers et 3052275 30 on détermine les indices de la cellule contenant une position (ux, uy, Liz) en exécutant un décalage constant à droite par dimension de la grille. 6 - Procédé selon la revendication 5 caractérisé en ce que l'on représente 5 une position réelle d'un point à l'aide d'un entier i compris entre 0 et 2W-1, où W est compris entre 0 et L, L correspondant à la plus grande longueur de la grille d'occupation et on utilise uniquement les W bits de poids fort de la représentation des coordonnées en coordonnées entières pour exécuter les étapes du procédé. 10 7 - Procédé selon la revendication 6 caractérisé en ce que l'on détermine les coordonnées entières d'un point M à partir de coordonnées sphériques en calculant l'écart au centre du repère K 2w-1 - cos(a) - cos(w) K Ux Ux = D avec les coordonnées sphériques données en sortie de capteur avec D la 15 distance de la cible, a la longitude mesurée à partir de l'axe x, co la latitude mesurée depuis le plan équatorial, R désigne la portée maximale du capteur, UxK - 2W-1 K U = 2W-1. Y UzK - 2W-1 20 8 - Procédé selon l'une des revendications précédentes caractérisé en ce que pour une grille de côté 2R, on filtre les informations de capteurs qui sont en dehors de la sphère de rayon R avant d'exécuter les étapes du procédé. u - u = D Y uÿ R 2w-1 - sin (w) K Uz- Uz = D R R 2w-1 - cos (a) - sin (w) 3052275 31 9 - Procédé selon la revendication 7 caractérisé en ce que l'on normalise les coordonnées par une valeur Dmax = V2 - R. 10 - Dispositif pour déterminer les coordonnées de cellules ci susceptibles 5 d'être traversées dans un espace d'observation représenté par une grille G ayant un premier pas de résolution, une cellule étant représentée par des sommets et des côtés ou segments reliant ces sommets, caractérisé en ce qu'il comporte au moins les éléments suivants : - Un ou plusieurs capteurs (101) adaptés à mesurer les coordonnées 10 d'un point mesuré dans le pas de résolution de la grille situé à une distance de la cible F, - Un module (103) de discrétisation des coordonnées mesurées avec un pas de résolution spatial b inférieur au pas RG de résolution de la grille, 15 - Un module (104) de traitement des coordonnées discrétisées adaptées à exécuter les étapes du procédé selon l'une des revendications 1 à 9. 11 - Dispositif selon la revendication 10 caractérisé en ce qu'il comporte un 20 module (102) de transformation des coordonnées mesurées dans un repère sphérique en coordonnées cartésiennes. 12 - Dispositif selon l'une des revendications 10 ou 11 caractérisé en ce que l'espace d'observation est défini par un capteur embarqué sur un véhicule (1) 25 en déplacement et en ce qu'une cellule sélectionnée est renseignée par une valeur de probabilité d'occupation par un obstacle.