FR 3067474 A1 20181214 FR 1755150 A 20170609 INRIA202.FRD Dispositif informatique pour l'aide à la conduite L'invention concerne le domaine de l'aide à la conduite. Le domaine de l'aide à la conduite comprend l'aide aux véhicules entièrement autonomes et l'aide aux véhicules pilotés avec assistance, avec ou sans conducteur. Ce domaine peut aussi concerner d'autres situations liées à la conduite, comme la gestion de l'environnement, que ce soit sur une route ou dans un environnement industriel. Il existe deux grandes familles de technologies pour les véhicules autonomes : les véhicules autonomes perceptifs, c'est-à-dire capables de se repérer dans n'importe quel environnement, et les véhicules autonomes assistés, c'est-à-dire qui n'ont pas de réelle perception locale de l'environnement. Ces deux familles sont techniquement très distinctes, et font appel à des technologies complètement différentes. Au-delà des techniques distinctes, ces familles de véhicules peuvent être utilisées dans des contextes très différents. Par exemple, un véhicule autonome perceptif est incontournable lorsqu'il n'existe pas ou peu de cartographie de l'environnement d'utilisation, et/ou que la géolocalisation dans cet environnement est complexe. C'est le cas par exemple de nombreuses applications comme dans le domaine de l'agriculture ou de la robotique industrielle. La notion de véhicule autonome sera donc pris dans un sens large, pouvant couvrir des voitures autant que des tracteurs ou autre machine agricole ou un robot capable de se déplacer. L'invention s'intéresse plus particulièrement au domaine des véhicules autonomes perceptifs. Classiquement, ce type de véhicule utilise des moyens pour analyser leur environnement afin de définir les obstacles. Historiquement, ces obstacles étaient détectés par télémétrie laser plan. Ces technologies ont évolué, et intègrent désormais comme source de télémétrie le 30 LIDAR 3D ou encore des caméras stéréo. Cela permet d'augmenter le nombre de points de données, et donc la perception de l'environnement. Cependant, cela pose le problème que, parmi les points de données détectés, de nombreux correspondent au sol, alors que 2 dans les techniques précédentes, tout point de donnée désignait automatiquement un obstacle. Des techniques ont donc été développées afin de déterminer dans un nuage de point 5 obtenu par LIDAR ou autre technique incluant le sol dans les points de données quelles portions correspondent au sol, et quelles portions correspondent à des obstacles. Les techniques connues sont soit précises mais pas temps réel (par exemple les implémentations actuelles utilisant des champs conditionnels de Markov ou MRF), soit compatibles avec une utilisation temps réel mais insuffisamment précises (par exemple, 10 par fitting d'un plan sur le sol). L'invention vient améliorer la situation. A cet effet, l'invention propose un dispositif informatique pour l'aide à la conduite, comprenant une mémoire agencée pour recevoir des données de nuage de points de données dans lesquelles un nuage de points associe, 15 pour un instant donné, des points présentant chacun des coordonnées dans un plan associé au nuage de points et une valeur désignant une hauteur. Le dispositif comprend en outre un calculateur agencé pour accéder à la mémoire et, pour un nuage de points donné, pour calculer d'une part des données de probabilité 20 d'appartenance à une surface de référence associées à chaque point du nuage de point données, et d'autre part des données de noeuds associant une valeur désignant une hauteur et deux valeurs indiquant une pente dans un plan associé au plan du nuage de points donné, en déterminant un champ conditionnel aléatoire gaussien au moyen des données de nuage de points de données correspondant au nuage de points donné, lequel champ 25 conditionnel aléatoire gaussien est représenté par un maillage de noeuds dans ledit plan associé, lesquels noeuds sont définis par les données de noeuds, et pour retourner les données de probabilité d'appartenance à une surface de référence et/ou certaines au moins des données de noeuds et des valeurs désignant une hauteur. Ce dispositif est particulièrement intéressant car il permet de faire une distinction entre sol et obstacles, ainsi que de connaître une hauteur respective des points de données, avec 3 un coût de calcul compatible avec une utilisation en temps réel dans un véhicule autonome. Dans d'autres modes de réalisation, le dispositif pourra présenter une ou plusieurs des 5 caractéristiques supplémentaires suivantes : - le calculateur est agencé pour appliquer un champ conditionnel aléatoire gaussien comprenant une première composante spatiale calculée, pour un noeud donné, à partir d'une valeur tirée de la différence entre la hauteur du noeud donné et une hauteur calculée à partir des coordonnées du noeud donné, des données de pente du noeud donné et des 10 coordonnées des points les plus proches du noeud donné, et une deuxième composante spatiale calculée, pour un noeud donné, à partir d'une valeur tirée de la différence entre les données de noeud du noeud donné et de données de noeud calculées à partir des coordonnées du noeud donné, des données de noeud des noeuds les plus proches du noeud donné et des coordonnées des noeuds les plus proches du noeud donné, 15 - le calculateur est en outre agencé pour appliquer un champ conditionnel aléatoire gaussien comprenant une composante temporelle calculée, pour un noeud donné et un instant donné, à partir des données de noeud du noeud donné et des données de noeud du noeud donné à un instant précédent l'instant donné, - le calculateur est agencé pour appliquer un algorithme d'espérance-maximisation pour 20 calculer les données de probabilité d'appartenance à une surface de référence et les données de noeuds, - le calculateur est agencé, après une étape d'initialisation, pour appliquer l'algorithme d'espérance-maximisation en alternant une étape de calcul d'espérance et une étape de calcul de maximisation- le calculateur est agencé pour exécuter l'étape de calcul 25 d'espérance en mettant à jour les données de probabilité d'appartenance à une surface de référence d'un point donné du nuage de points donné à partir d'une valeur de distance à référence tirée de la différence entre la valeur désignant une hauteur du point donné et d'une hauteur calculée à partir des coordonnées du point donné, des coordonnées du noeud le plus proche du point donné et des données de noeud du noeud le plus proche du point 30 donné, 4 - le calculateur est agencé pour mettre à jour des données de probabilité d'appartenance à une surface de référence d'un point donné du nuage de points donné en fonction du signe de la valeur de distance à référence, - le calculateur est agencé pour exécuter l'étape de calcul de maximisation en calculant 5 d'une part un vecteur de données de noeud d'information et des données de matrice d'information à partir de la première composante spatiale et de la deuxième composante spatiale, et - le calculateur est en outre agencé pour exécuter l'étape de calcul de maximisation à partir de la composante temporelle. 10 L'invention concerne également un procédé informatique pour l'aide à la conduite qui comprend les opérations suivantes : a) recevoir des données de nuage de points de données dans lesquelles un nuage de points associe, pour un instant donné, des points présentant chacun des coordonnées dans 15 un plan associé au nuage de points et une valeur désignant une hauteur, b) pour un nuage de points donné, calculer d'une part des données de probabilité d'appartenance à une surface de référence associées à chaque point du nuage de point données, et d'autre part des données de noeuds associant une valeur désignant une hauteur et deux valeurs indiquant une pente dans un plan associé au plan du nuage de points 20 donné, en déterminant un champ conditionnel aléatoire gaussien au moyen des données de nuage de points de données correspondant au nuage de points donné, lequel champ conditionnel aléatoire gaussien est représenté par un maillage de noeuds dans ledit plan associé, lesquels noeuds sont définis par les données de noeuds, 25 c) retourner les données de probabilité d'appartenance à une surface de référence et/ou certaines au moins des données de noeuds et des valeurs désignant une hauteur. Dans d'autres modes de réalisation, le procédé pourra présenter une ou plusieurs des caractéristiques supplémentaires suivantes : 30 - le champ conditionnel aléatoire gaussien comprend une première composante spatiale calculée, pour un noeud donné, à partir d'une valeur tirée de la différence entre la hauteur du noeud donné et une hauteur calculée à partir des coordonnées du noeud donné, des 5 données de pente du noeud donné et des coordonnées des points les plus proches du noeud donné, et une deuxième composante spatiale calculée, pour un noeud donné, à partir d'une valeur tirée de la différence entre les données de noeud du noeud donné et de données de noeud calculées à partir des coordonnées du noeud donné, des données de noeud des noeuds 5 les plus proches du noeud donné et des coordonnées des noeuds les plus proches du noeud donné, - le champ conditionnel aléatoire gaussien comprend en outre une composante temporelle calculée, pour un noeud donné et un instant donné, à partir des données de noeud du noeud donné et des données de noeud du noeud donné à un instant précédent l'instant donné, 10 - l'opération b) comprend l'application d'un algorithme d'espérance-maximisation pour calculer les données de probabilité d'appartenance à une surface de référence et les données de noeuds, - l'opération b) comprend : bl) une étape d'initialisation, 15 b2) une étape de calcul d'espérance, et b3) une étape de calcul de maximisation, les étapes b2) et b3) étant répétées sur la base des résultats des étapes précédentes jusqu'à ce qu'une condition de convergence soit remplie, - l'opération b2) comprend la mise à jour les données de probabilité d'appartenance à une 20 surface de référence d'un point donné du nuage de points donné à partir d'une valeur de distance à référence tirée de la différence entre la valeur désignant une hauteur du point donné et d'une hauteur calculée à partir des coordonnées du point donné, des coordonnées du noeud le plus proche du point donné et des données de noeud du noeud le plus proche du point donné, 25 - l'opération b2) comprend la mise à jour des données de probabilité d'appartenance à une surface de référence d'un point donné du nuage de points donné en fonction du signe de la valeur de distance à référence, - l'opération b3) comprend le calcul d'un vecteur de données de noeud d'information) et de données de matrice d'information) à partir de la première composante spatiale et de la 30 deuxième composante spatiale, et - le calcul de l'opération b3) comprend l'utilisation de la composante temporelle. 6 D'autres caractéristiques et avantages de l'invention apparaîtront mieux à la lecture de la description qui suit, tirée d'exemples donnés à titre illustratif et non limitatif, tirés des dessins sur lesquels : - la figure 1 représente un diagramme schématique d'un dispositif selon invention et des 5 données qu'il traite, - la figure 2 représente un schéma en exemple du modèle de données utilisé par le dispositif de la figure 1, - la figure 3 représente un exemple d'une boucle de fonctionnement du dispositif de la figure 1, et 10 - la figure 4 représente un exemple de mise en oeuvre d'une fonction de la figure 3. Les dessins et la description ci-après contiennent, pour l'essentiel, des éléments de caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la présente invention, mais aussi contribuer à sa définition, le cas échéant. 15 20 En outre, la description détaillée est augmentée de l'annexe A, qui donne la formulation de certaines formules mathématiques mises en oeuvre dans le cadre de l'invention. Cette Annexe est mise à part dans un but de clarification, et pour faciliter les renvois. Elle est 25 partie intégrante de la description, et pourra donc non seulement servir à mieux faire comprendre la présente invention, mais aussi contribuer à sa définition, le cas échéant. Les champs conditionnels aléatoires (ci-après CRF) constituent une alternative aux MRF, mais n'ont pas d'application dans le domaine des véhicules autonomes. Ils ont connu 30 quelques utilisations, par exemple par Lu et al. dans "A hybrid conditional random field for estimating the underlying ground surface from airborne Mar data," IEEE Transactions on Geoscience and Remote Sensing, vol. 47, pp. 2913-2922, Aug 2009 ou 7 par Wang et al. dans "A dynamic conditional random field model for object segmentation in image sequences" in 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), vol. 1, pp. 264-270 vol. 1, June 2005. 5 Lu et al concerne la caractérisation d'un sol à partir d'images prises par un LIDAR aérien, en définissant des variables aléatoires discrètes qui représentent l'appartenance ou pas d'un point particulier au sol. Ce type de modèle n'est manifestement pas compatible avec les véhicules autonomes, pour lesquels l'acquisition de données est réalisée beaucoup plus près du sol, ce qui a pour conséquence une discrimination plus complexe à réaliser, 10 ainsi que la présence de parties masquées, que ce soit par le véhicule lui-même ou par tout obstacle dans la ligne de mire du capteur. De plus, Lu et al. utilise un apprentissage supervisé pour classifier les obstacles à l'aide d'extraction de caractéristiques, ce qui coûteux et inadapté à une application de navigation avec des obstacles variés comme la conduite autonome. Wang et al est lui spécifique à la segmentation de séquences 15 d'images, ce qui le rend également inapplicable au domaine des véhicules autonomes. La Demanderesse a découvert un moyen d'adapter les CRF au contexte des véhicules autonomes afin de discriminer dans un nuage de points ceux qui sont relatifs au sol, et ceux qui appartiennent à des obstacles, et cela en temps réel. Par temps réel, on entend un 20 dispositif qui présente une puissance de calcul économiquement raisonnable et peut être embarqué dans un véhicule, et est capable de traiter les points de données plus rapidement que la fréquence d'acquisition des points de données. La figure 1 représente un diagramme schématique d'un dispositif 2 selon invention. Le 25 dispositif 2 comprend une mémoire 4 et un calculateur 6. Dans le cadre de l'invention, la mémoire 4 peut être tout type de stockage de données propre à recevoir des données numériques : disque dur, disque dur à mémoire flash (SSD en anglais), mémoire flash sous toute forme, mémoire vive, disque magnétique, stockage 30 distribué localement ou dans le cloud, etc. Les données calculées par le dispositif peuvent être stockées sur tout type de mémoire similaire à la mémoire 8, ou sur celle-ci. Ces données peuvent être effacées après que le dispositif ait effectué ses tâches ou conservées. 8 La mémoire 4 reçoit des données de nuage de points de données 8 à une fréquence correspondant à la fréquence d'acquisition du capteur du véhicule autonome dans lequel le dispositif 2 est installé. En variante, le dispositif 2 peut être déporté et communiquer avec le véhicule autonome par tout moyen approprié. Le calculateur 6 traite les données 5 de nuage de points et retourne des données de nuage de points de données discriminé 10, dans lesquelles chaque point de données est identifié comme appartenant au sol ou à un obstacle. De manière optionnelle, une hauteur par rapport au sol peut être annexée à chaque point de données du nuage de points de données discriminé. Les données de nuage de points de données 8 comme les données de nuages de points de données discriminé 10 10 sont toujours couplées à un marqueur de temps, qui permet de déterminer à quel moment l'acquisition des données a été réalisée. En variante, le calculateur 6 peut également retourner une carte d'élévation du sol sous forme d'une grille de points, avec la pente associée à chaque point de la grille. 15 Le calculateur 6 est un élément accédant directement ou indirectement à la mémoire 4. Il peut être réalisé sous la forme d'un code informatique approprié exécuté sur un ou plusieurs processeurs. Par processeurs, il doit être compris tout processeur adapté aux calculs décrits plus bas. Un tel processeur peut être réalisé de toute manière connue, sous la forme d'un microprocesseur pour ordinateur personnel, d'une puce dédiée de type 20 FPGA ou SoC (« system on chip » en anglais), d'une ressource de calcul sur une grille, d'un microcontrôleur, ou de toute autre forme propre à fournir la puissance de calcul nécessaire à la réalisation décrite plus bas. Un ou plusieurs de ces éléments peuvent également être réalisés sous la forme de circuits électroniques spécialisés tel un ASIC. Une combinaison de processeur et de circuits électroniques peut également être 25 envisagée. La figure 2 représente un schéma en exemple du modèle de données utilisé par le dispositif de la figure 1. La Demanderesse a découvert qu'un champ conditionnel aléatoire spatio-temporel (ci-après STCRF) permet de résoudre les problèmes liés à la 30 discrimination des nuages de points de données obtenus à faible altitude. 9 Dans l'exemple décrit ici, le sol est modélisé sous la forme d'un champ aléatoire conditionnel représenté par un maillage de noeuds dans un plan bidimensionnel centré sur le véhicule. 5 Chaque noeud a des coordonnées propres dans ce plan et se voit associer une variable aléatoire continue cachée sous la forme d'un triplet comprenant une hauteur, une pente selon un premier axe du plan bidimensionnel, et une pente selon un second axe du plan bidimensionnel. Ainsi, pour un noeud d'indice i et de coordonnées nxi et nyi, la variable aléatoire continue cachée est notée Gi=(hi,sxi,syi)T. Les mesures contenues dans les 10 données de nuage de points de données 8 représentent des triplets de coordonnées (xj, yj, zj) qui sont adaptées au repère du plan bidimensionnel. Le STCRF est basé sur trois groupes de voisinages interdépendants : - Le voisinage temporel, qui implique qu'un même noeud doit avoir la même 15 classification dans deux nuages de points de données discriminés consécutifs, - Le voisinage spatial, qui implique que des noeuds très proches spatialement ont normalement des hauteurs similaires, et - Le voisinage réel, qui comprend des observations (par exemple une classification préalable de certains points et/ou noeuds) et des variables cachées (comme la 20 hauteur des points et/ou noeuds et une probabilité d'appartenance au sol). La modélisation via ce STCRF permet de déterminer, pour chaque point donné, la valeur de la probabilité de son appartenance au sol, ainsi que la hauteur pour les noeuds du maillage. 25 Ainsi, comme on peut le voir sur la figure 2, pour un nuage de points de données particulier, les données du STCRF se répartissent sur des plans temporels 20 et 22. Le plan temporel 20 représente le maillage pour le nuage de points de données particulier, et le plan temporel 22 représente le maillage pour le nuage de points de données 30 immédiatement antérieur au nuage de points de données particulier. 10 Dans l'exemple décrit ici le voisinage temporel est donc formé, pour un noeud 24 du plan temporel 20 par le noeud 26 qui lui correspond dans le plan temporel 22. La manière dont il est tenu compte du déplacement du véhicule pour déterminer le noeud 26 sera explicité plus bas. 5 Le noeud 24 est entouré d'un ensemble de points de données 28. Comme décrit plus haut, chaque point de données 28 a des coordonnées (xj, yj, zj) qui représentent une mesure ici obtenue par LIDAR). Une variable aléatoire binaire cj est associée à chaque mesure. Comme on le verra plus bas, le dispositif 2 met en oeuvre une boucle de calcul qui permet 10 d'évaluer la valeur de la variable cj. Aux fins de ces calculs, chaque point de données 28 est associé au noeud Gi dont il est le plus proche selon une mesure métrique. Les trois voisinages sont réunis dans une distribution de Gibbs sous la forme de trois équations [10], [20] et [30] de l'Annexe A. L'équation [10] concerne le voisinage réel, 15 l'équation [20] concerne le voisinage spatial et l'équation [30] concerne le voisinage temporel. Dans l'équation [10], W1 est un facteur de normalisation, a est un facteur de pondération, Mi désigne l'ensemble des points de données qui sont associés à un noeud Gi donné, et 20 Hij est une matrice définie par la formule [15] de l'Annexe A. La multiplication de la matrice Hij par Gi revient à estimer la hauteur du noeud Gi au point de données d'indice j, en tenant compte de la pente sxi et syi de Gi et des distances entre le noeud Gi et le point de données d'indice j. Ainsi l'équation [10] détermine une valeur tirée de la différence entre la hauteur de la mesure de chacun des points de données et la hauteur qu'aurait le 25 noeud le plus proche en ces points, la variable cj influant selon que chaque point de données est associé au sol ou pas. Dans l'exemple décrit ici, la sélection des points de données du voisinage réel est réalisée en décalant la grille de maillage et en la centrant sur les noeuds Gi. Ainsi, chaque carré de maillage contient les points de données les plus proches du noeud Gi au centre du carré de maillage considéré. 30 Dans l'équation [20], W2 est un facteur de normalisation, p est un facteur de pondération, Vi désigne l'ensemble des noeuds voisins d'un noeud Gi donné, et Fij est une matrice 11 définie par la formule [25] de l'Annexe A. L'application de la matrice Fij à Gj revient à estimer la hauteur du noeud Gj à l'emplacement du noeud d'indice i, en tenant compte de de la pente sxj et syj de Gj, et des distances entre le noeud Gj et le noeud Gi. Ainsi l'équation [20] détermine une valeur tirée de la différence entre la hauteur de chacun des 5 noeuds et la hauteur qu'auraient les noeuds voisins en ces noeuds. Dans l'exemple décrit ici, les voisins spatiaux sont les 8 noeuds les plus proches de chaque noeud donné. Cela donne un bon compromis entre nombre d'itérations nécessaires pour converger et quantité de calcul nécessaire pour chaque étape. En variante, le voisinage spatial pourrait être réduit à 4, voire 2 noeuds, ou supérieur à 8. Toujours en variante, l'équation [20] pourrait 10 comprendre un facteur de pondération pour chaque noeud voisin Gj, par exemple du type noyau Gaussien. Dans l'équation [30], W3 est un facteur de normalisation, y est un facteur de pondération, Qi désigne une matrice de transition du noeud Gi pour le nuage de points de données 15 immédiatement antérieur au nuage de points de données courant à l'état du noeud Gi pour le nuage de points de données courant. Dans l'exemple décrit ici, la matrice Qi est choisie égale à la matrice identité, mais elle pourrait être différente pour introduire du bruit qui correspondrait à un intervalle de confiance sur les mesures qui ont permis d'interpoler le noeud Git-lou pour tenir compte d'un changement de la hauteur du sol dans le temps (due 20 par exemple des vagues dans une application maritime). Pour tenir compte du fait que le véhicule se déplace, la détermination du noeud Gi" est faite en transformant le maillage du le nuage de points de données immédiatement antérieur au nuage de points de données courant en fonction des données de déplacement et de changement d'orientation du véhicule. Ces données peuvent être tirées d'une unité de mesure inertielle, et/ou de 25 données GPS, et/ou de données d'un odomètre ou d'autres méthodes utilisant d'autres capteurs (odométrie visuelle, SLAM laser, etc.). La valeur de Git1 est alors calculée par interpolation du maillage transformé à l'emplacement du noeud Gi. Pour les noeuds pour lesquels aucune information n'était disponible, c'est-à-dire correspondant à une zone non visitée par le véhicule, Git1 est marqué comme indéfini, de sorte que le couple Gi- Git1 30 n'est pas pris en compte, tandis que les zones qui disparaissent suite à la transformation peuvent être écartées ou stockées dans une cartographie de long terme. Dans d'autres variantes, le voisinage temporel pourrait inclure un noeud d'un nuage encore plus ancien. 12 Néanmoins, l'utilisation d'un seul voisin temporel suffit à forcer la cohérence pour les noeuds qui se trouvent dans une zone devenue aveugle du fait de la survenance d'un obstacle comme un autre véhicule, ou par le déplacement du véhicule autonome lui-même. En variante, le voisinage temporel et l'équation [30] pourraient être omis, a 5 condition d'accepter de perdre la cohésion temporelle, et de subir des zones d'ombre dynamiques en fonction des obstacles rencontrés. L'invention repose sur la transformation d'un maillage a priori en un maillage qui maximise la probabilité a posteriori selon la formule [40] de l'Annexe A. Pour cela, 10 chaque noeud se voit affecter un modèle Gaussien pour l'état du sol, chaque noeud Gi étant représenté par un vecteur moyen Gmi et une matrice de covariance Mi. Pour simplifier les calculs, ces relations sont réécrites avec d'une matrice Pi qui est l'inverse de la matrice de covariance Mi et un vecteur Xi qui est égal au produit de la matrice Pi et du vecteur moyen Gmi. Une fois la matrice Pi et le vecteur Xi déterminés, Gmi peut être défini selon 15 la formule [50] de l'Annexe A. Afin d'approcher la pleine distribution sur G, un algorithme d'espérance-maximisation itératif est exécuté pour déterminer la matrice Pi et le vecteur Xi, dans lequel l'étape d'espérance estime la distribution de probabilité sur la distribution de classification des 20 points de données Ci, et une étape de maximisation utilise cette distribution pour estimer la distribution d'état du sol. Ces deux étapes sont répétées en boucle jusqu'à ce qu'une condition de convergence soit atteinte. La figure 3 représente un exemple d'une fonction exécutée par le calculateur 6 pour 25 mettre en oeuvre ces calculs. Dans une opération 300, le calculateur 6 exécute une fonction Init(). Dans l'exemple décrit, le maillage de départ est plat. Cette fonction initialise donc les vecteurs Gmi de G(0) avec une hauteur et des pentes nulles. Cela initialise donc également X(0) à 0. En 30 partant d'un autre maillage a priori, non plat, la fonction Init() initialiserait les vecteurs Gmi en fonction de cet autre maillage. Cette initialisation sera également effectuée à chaque fois qu'un nouveau noeud (c'est-à-dire un noeud à un emplacement qui n'a été 13 traité dans aucune des boucles précédentes) est défini pour un nuage de points de données, lorsque le véhicule se déplace. La matrice de covariance Mi est initialisée avec des coefficients diagonaux importants, de sorte que ces valeurs d'initialisation n'influencent pas le résultat final l'algorithme mais permettent d'accélérer sa convergence. 5 Une boucle est alors exécutée jusqu'à l'arrêt du fonctionnement du véhicule autonome, avec dans une opération 310 l'incrémentation d'un indice t, dans une opération 320 l'exécution d'une fonction Rec() qui reçoit un nuage de point de données courant et stocke les mesures correspondantes dans un vecteur Z, et dans une opération 330 l'exécution 10 d'une fonction EM() qui détermine le vecteur G(t) en recevant comme arguments le vecteur Z et le vecteur G(t-1) de la boucle précédente. La figure 4 représente un exemple de mise en oeuvre de la fonction EM(). 15 Dans une opération 400, la fonction EM() s'initialise en définissant un indice i à 0 et un indice k à 1, en déterminant P(t-1) et X(t-1) à partir de G(t-1) et en définissant l'indice de boucle courante t. Deux boucles sont alors lancées. La première boucle parcourt, pour un indice k donné, 20 tous les noeuds d'indice i et mettre à jour la probabilité C[], le vecteur X[i] et la matrice P[i]. Le vecteur C[] contient donc, pour un indice k donné, les probabilités de tous les noeuds d'indice i de la boucle courante d'indice t. La deuxième boucle consiste à répéter la première boucle avec les noeuds mis à jour, en faisant donc varier l'indice k, jusqu'à ce qu'une condition de convergence soit remplie. 25 Bien que la présentation de la Figure 4 soit présentée sous forme itérative, par la nature même des calculs qu'elles contiennent, les opérations de la première boucle pourraient être réalisées en parallèle. Dit autrement, pour un indice k fixé, la première boucle associée à chaque indice i pourrait être parallélisée, et être par exemple exécutées toutes 30 ou en partie en parallèle sur un processeur graphique, dont les qualités sont connus pour ces applications. 14 Ainsi, la probabilité C est mise à jour dans une opération 410 par une fonction Est() qui reçoit comme argument le vecteur Z et le vecteur X[i]. La fonction Est() sélectionne l'ensemble des points de données du vecteur Z qui sont associés au noeud d'indice i, et évalue pour chacun d'entre eux une probabilité cj qu'il stocke dans le vecteur C[k]. La 5 probabilité cj est calculée selon la formule [60] de l'Annexe A. Pour la première itération de la fonction Est(), lorsque X[i](k-1,t) n'existe pas, c'est X[i](t-1) qui est utilisé. Dans le cas où le sol serait considéré comme mouvant temporellement, cette variation pourrait être prise en compte et appliquée à X[i](t-1). 10 Cette formule revient à déterminer une valeur tirée de la distance entre la mesure zj d'un point de données et la hauteur estimée du noeud Gmi déplacé à l'emplacement du point de données. L'exponentielle avec les facteurs al et a2 permettent de converger rapidement vers 1 lorsque la différence est proche de zéro. Dans l'exemple décrit ici, al est fixé à 0,05m et a2 est fixé à 0,5m. Ces valeurs permettent de donner plus d'importance 15 aux points de données dont la hauteur est faible et permet de converger pour la partie basse des obstacles (qui ne sont donc pas du sol). En variante, la formule lorsque la différence de la formule [60] de l'Annexe A est négative pourrait fixer une valeur de cj égale à 1. 20 Une fois l'étape d'espérance terminée avec l'opération 410, l'étape de maximisation est exécutée avec des opérations 420 et 430. Dans l'opération 420, une fonction XMax() reçoit comme arguments le vecteur C[], le vecteur X[i](t-1) et le vecteur X[i](k-1,t) de l'itération précédente, ainsi que le vecteur Z 25 et met à jour le vecteur X[i](k,t) de l'itération courante en appliquant la formule [70] de l'Annexe A. La formule [70] de l'Annexe A revient à faire une maximisation des formules [10], [20] et [30] pour le vecteur X[i], la formulation exponentielle de ces dernières permettant une 30 formule linéaire en présence du modèle Gaussien. 15 De manière similaire, dans l'opération 430, une fonction PMax() reçoit comme arguments le vecteur C[], la matrice P[i](t-1) et la matrice P[i](k-1,t) de l'itération précédente, ainsi que le vecteur Z et met à jour le vecteur P[i](k,t) de l'itération courante en appliquant la formule [80] de l'Annexe A. Comme pour la formule [70] de l'Annexe A, la formule [80] de l'Annexe A revient à faire une maximisation des formules [10], [20] et [30] pour la matrice P[i], la formulation exponentielle de ces dernières permettant une formule linéaire en présence du modèle Gaussien. Dans l'exemple décrit ici, le facteur de pondération a a été fixé à 1, le facteur de pondération p a été fixé à 0,5, et le facteur de pondération y a été fixé à 0,2. Ces facteurs de pondération pourraient être fixés autrement et correspondent à l'importance que l'on souhaite donner aux voisinages respectifs dans la détermination de la solution. 15 L'indice i est alors testé pour déterminer si tous les noeuds ont été mis à jour pour la boucle d'indice k courant dans une opération 440. Si ce n'est pas le cas, alors l'indice i est incrémenté dans une opération 450 et les opérations 410 à 440 sont répétées. 20 Lorsque tous les noeuds ont été mis à jour, l'estimation pour l'itération courante de chaque vecteur Gmi, stockés dans un tableau G(k,t), est calculée dans une opération 460 qui reçoit comme arguments le vecteur X(k,t) courant et la matrice P(k,t) courante. Cela est réalisé en appliquant la formule [90] de l'Annexe A, qui correspond à la transposition à l'itération courante de la formule [50] de l'Annexe A. 25 Enfin, une fonction Conv() est exécutée dans une opération 470. La fonction Conv() détermine si la fonction EM() a convergé, ou s'il est nécessaire de faire une autre itération. Cette détermination peut être basée sur le nombre d'itérations, la Demanderesse ayant constaté que, pour les paramètres décrits ci-dessus, 10 itérations suffisent toujours à 30 converger, ou sur une condition de convergence propre, par exemple la comparaison entre G(k,t) et G(k-1,t). 5 10 16 Lorsqu'une nouvelle itération est nécessaire, l'indice k est incrémenté dans une opération 480 et l'indice i est remis à zéro dans une opération 490, et la boucle reprend avec l'opération 410. Sinon, la fonction EM() se termine en retournant le tableau G(k,t) dans une opération 499. 5 L'exemple décrit ici a été validé avec des nuages de points de données obtenus par LIDAR, au moyen d'un LIDAR Velodyne HDL64 monté sur une Renault Zoe ainsi qu'avec 3 LIDARs Ibeo Lux. En variante, d'autres sources de nuages de points pourraient être utilisées comme des caméras stéréo ou caméra de profondeur de type Kinect ou 10 autres. En outre, pour réduire les calculs, le voisinage réel pourrait être réduit en tenant compte de la distance au véhicule. En effet, par nature, le LIDAR retourne énormément de points près du véhicule, puis de moins en moins au fur et à mesure que l'angle de tir augmente. En variante, le nombre de voisins pourrait être conservé, mais utilisé pour accélérer la convergence en forçant la cohérence des noeuds du maillage avec ceux-ci. 15 Pour accélérer la convergence, les points très proches du véhicule pourraient également avoir une hauteur forcée à celle du véhicule. Enfin, la grille décrite ici est à motif carrés, mais elle pourrait être adaptée à la technologie de capture des nuages de points de données, par exemple être une grille polaire à motifs circulaires. 17 5 Annexe A = exp(- Ei a EiEmi ci Ilzi - HiiGi112) Hi] = [1 xi - nxi yi - [10] [15] [20] = exp(- Ei EiEvi II Gi - F Gi 112) W2 1 nxj - nxi nyj - nyi [25] H ij = [0 1 0 0 0 1 10 [30] = 14+3 exp( - Ei y liGi - QiGit-1112) [40] {g mi} = ar gmaxg» (G = {g i}IC , Z, Gt-1)) 15 [50] Gmi = Xi - H ij X[i](k - 1, t)) > 0 (z1-1119([1](k-1,t))2) exp si cj = 20-12 [60] exp sinon 2ci22 [70] X [i] (k, = a EiEmi + j9EiEvi FiiTx[]](k, + yQiT X[i](t - 1) 20 [80] P[n(k, = a EiEmi cp-HiTHij + j9EiEvi F pw(k, t)Fij + y Q iT P [i] (t - 1)(2i [90] Gm[i](k,t) = P[i](k,0-1X[i](k, REVENDICATIONS1. Dispositif informatique pour l'aide à la conduite, comprenant une mémoire (4) agencée pour recevoir des données de nuage de points de données (8) dans lesquelles un nuage de points associe, pour un instant donné (t), des points présentant chacun des coordonnées (xi, yi) dans un plan associé au nuage de points et une valeur désignant une hauteur (zi), caractérisé en ce qu'il comprend en outre un calculateur (6) agencé pour accéder à la mémoire (4) et, pour un nuage de points donné, pour calculer d'une part des données de probabilité d'appartenance à une surface de référence (cj) associées à chaque point du nuage de point données, et d'autre part des données de noeuds (hi, sxi, syi) associant une valeur désignant une hauteur (hi) et deux valeurs indiquant une pente (sxi, syi) dans un plan associé au plan du nuage de points donné, en déterminant un champ conditionnel aléatoire gaussien (CRF) au moyen des données de nuage de points de données (8) correspondant au nuage de points donné, lequel champ conditionnel aléatoire gaussien (CRF) est représenté par un maillage de noeuds dans ledit plan associé, lesquels noeuds sont définis par les données de noeuds (hi, sxi, syi), et pour retourner les données de probabilité d'appartenance à une surface de référence (cj) et/ou certaines au moins des données de noeuds (hi, sxi, syi) et des valeurs désignant une hauteur (zi). 2. Dispositif selon la revendication 1, dans lequel le calculateur (6) est agencé pour appliquer un champ conditionnel aléatoire gaussien (CRF) comprenant une première composante spatiale calculée, pour un noeud donné (Gi), à partir d'une valeur tirée de la différence entre la hauteur (hi) du noeud donné (Gi) et une hauteur (HijGi) calculée à partir des coordonnées du noeud donné (nxi, nyi), des données de pente (sxi, syi) du noeud donné (Gi) et des coordonnées (xj, yj) des points les plus proches (Mi) du noeud donné (Gi), et une deuxième composante spatiale calculée, pour un noeud donné (Gi), à partir d'une valeur tirée de la différence entre les données de noeud du noeud donné (Gi) et de données de noeud (FijGj) calculées à partir des coordonnées du noeud donné (nxi, nyi), des données 18 19 5 3. 10 4. 15 5. 20 6. 25 7. 30 de noeud (Gj) des noeuds les plus proches (Vi) du noeud donné (Gi) et des coordonnées (xj, yj) des noeuds les plus proches (Gj) du noeud donné (Gi). Dispositif selon la revendication 2, dans lequel le calculateur (6) est en outre agencé pour appliquer un champ conditionnel aléatoire gaussien (CRF) comprenant une composante temporelle calculée, pour un noeud donné (Gi) et un instant donné (t), à partir des données de noeud du noeud donné et des données de noeud du noeud donné à un instant précédent l'instant donné (Gi(t-1)). Dispositif selon l'une des revendications précédentes, dans lequel le calculateur (6) est agencé pour appliquer un algorithme d'espérance-maximisation pour calculer les données de probabilité d'appartenance à une surface de référence (cj) et les données de noeuds (hi, sxi, syi). Dispositif selon la revendication 4, dans lequel le calculateur (6) est agencé, après une étape d'initialisation, pour appliquer l'algorithme d'espérance-maximisation en alternant une étape de calcul d'espérance et une étape de calcul de maximisation. Dispositif selon la revendication 5, dans lequel le calculateur (6) est agencé pour exécuter l'étape de calcul d'espérance en mettant à jour les données de probabilité d'appartenance à une surface de référence (cj) d'un point donné du nuage de points donné à partir d'une valeur de distance à référence (dzj) tirée de la différence entre la valeur désignant une hauteur (zj) du point donné et d'une hauteur (HijXi) calculée à partir des coordonnées du point donné (xj, yj), des coordonnées (nxi, nyi) du noeud le plus proche du point donné et des données de noeud (hi, nxi, nyi, sxi, syi) du noeud le plus proche du point donné. Dispositif selon la revendication 6, dans lequel le calculateur (6) est agencé pour mettre à jour des données de probabilité d'appartenance à une surface de référence (cj) d'un point donné du nuage de points donné en fonction du signe de la valeur de distance à référence (dzj). 20 8. Dispositif selon la revendication 3 et la revendication 7, dans lequel le calculateur (6) est agencé pour exécuter l'étape de calcul de maximisation en calculant d'une part un vecteur de données de noeud d'information (Xi(k,t)) et des données de matrice d'information (Pi(k,t)) à partir de la première composante 5 spatiale et de la deuxième composante spatiale. 9. Dispositif selon la revendication 8, dans lequel le calculateur (6) est en outre agencé pour exécuter l'étape de calcul de maximisation à partir de la composante temporelle. 10 10. Procédé informatique pour l'aide à la conduite, caractérisé en ce qu'il comprend les opérations suivantes : a) recevoir des données de nuage de points de données (8) dans lesquelles un nuage de points associe, pour un instant donné (t), des points présentant 15 chacun des coordonnées (xi, yi) dans un plan associé au nuage de points et une valeur désignant une hauteur (zi), b) pour un nuage de points donné, calculer d'une part des données de probabilité d'appartenance à une surface de référence (cj) associées à chaque point du nuage de point données, et d'autre part des données de 20 noeuds (hi, sxi, syi) associant une valeur désignant une hauteur (hi) et deux valeurs indiquant une pente (sxi, syi) dans un plan associé au plan du nuage de points donné, en déterminant un champ conditionnel aléatoire gaussien (CRF) au moyen des données de nuage de points de données (8) correspondant au 25 nuage de points donné, lequel champ conditionnel aléatoire gaussien (CRF) est représenté par un maillage de noeuds dans ledit plan associé, lesquels noeuds sont définis par les données de noeuds (hi, sxi, syi), c) retourner les données de probabilité d'appartenance à une surface de référence (cj) et/ou certaines au moins des données de noeuds (hi, sxi, syi) 30 et des valeurs désignant une hauteur (zi).