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éo localisation 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 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 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 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 MRP), soit compatibles avec une utilisation temps réel mais insuffisamment précises (par exemple, 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, 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é 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 nœuds 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 conditionnel aléatoire gaussien est représenté par un maillage de nœuds dans ledit plan associé, lesquels nœuds sont définis par les données de nœuds, 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 nœuds 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 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 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 nœud donné, à partir d'une valeur tirée de la différence entre la hauteur du nœud donné et une hauteur calculée à partir des coordonnées du nœud donné, des données de pente du nœud donné et des coordonnées des points les plus proches du nœud donné, et une deuxième composante spatiale calculée, pour un nœud donné, à partir d'une valeur tirée de la différence entre les données de nœud du nœud donné et de données de nœud calculées à partir des coordonnées du nœud donné, des données de nœud des nœuds les plus proches du nœud donné et des coordonnées des nœuds les plus proches du nœud donné,

- le calculateur est en outre agencé pour appliquer un champ conditionnel aléatoire gaussien comprenant une composante temporelle calculée, pour un nœud donné et un instant donné, à partir des données de nœud du nœud donné et des données de nœud du nœud donné à un instant précédent l'instant donné,

- le calculateur 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 et les données de nœuds,

- 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 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 nœud le plus proche du point donné et des données de nœud du nœud le plus proche du point donné, - 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 d'une part un vecteur de données de nœud 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.

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 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 nœuds 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 conditionnel aléatoire gaussien est représenté par un maillage de nœuds dans ledit plan associé, lesquels nœuds sont définis par les données de nœuds,

c) retourner les données de probabilité d'appartenance à une surface de référence et/ou certaines au moins des données de nœuds 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 :

- le champ conditionnel aléatoire gaussien comprend une première composante spatiale calculée, pour un nœud donné, à partir d'une valeur tirée de la différence entre la hauteur du nœud donné et une hauteur calculée à partir des coordonnées du nœud donné, des données de pente du nœud donné et des coordonnées des points les plus proches du nœud donné, et une deuxième composante spatiale calculée, pour un nœud donné, à partir d'une valeur tirée de la différence entre les données de nœud du nœud donné et de données de nœud calculées à partir des coordonnées du nœud donné, des données de nœud des nœuds les plus proches du nœud donné et des coordonnées des nœuds les plus proches du nœud donné,

- le champ conditionnel aléatoire gaussien comprend en outre une composante temporelle calculée, pour un nœud donné et un instant donné, à partir des données de nœud du nœud donné et des données de nœud du nœud donné à un instant précédent l'instant donné, - 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 nœuds,

- l'opération b) comprend :

bl) une étape d'initialisation,

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 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 nœud le plus proche du point donné et des données de nœud du nœud le plus proche du point donné,

- 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 nœud d'information) et de données de matrice d'information) à partir de la première composante spatiale et de la deuxième composante spatiale, et

- le calcul de l'opération b3) comprend l'utilisation de la composante temporelle. 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 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

- la figure 4 représente un exemple de mise en œuvre 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.

La présente description est de nature à faire intervenir des éléments susceptibles de protection par le droit d'auteur et/ou le copyright. Le titulaire des droits n'a pas d'objection à la reproduction à l'identique par quiconque du présent document de brevet ou de sa description, telle qu'elle apparaît dans les dossiers officiels. Pour le reste, il réserve intégralement ses droits.

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 œuvre dans le cadre de l'invention. Cette Annexe est mise à part dans un but de clarification, et pour faciliter les renvois. Elle est 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 MRP, mais n'ont pas d'application dans le domaine des véhicules autonomes. Ils ont connu quelques utilisations, par exemple par Lu et al. dans "A hybrid conditional random field for estimating the underlying ground surface from airborne lidar data " IEEE Transactions on Geoscience and Remote Sensing, vol. 47, pp. 2913-2922, Aug 2009 ou par Wang et al. dans "A dynamic conditional random field model for object segmentation in image séquences" in 2005 IEEE Computer Society Conférence on Computer Vision and Pattern Récognition (CVPR'05), vol. 1, pp. 264-270 vol. 1, June 2005. 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, 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 classifïer 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 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 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 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 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. 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 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 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.

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 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 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 discrimination des nuages de points de données obtenus à faible altitude. 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 nœuds dans un plan bidimensionnel centré sur le véhicule. Chaque nœud 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 nœud 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 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 nœud doit avoir la même classification dans deux nuages de points de données discriminés consécutifs,

Le voisinage spatial, qui implique que des nœuds 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 nœuds) et des variables cachées (comme la hauteur des points et/ou nœuds 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 nœuds du maillage.

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 immédiatement antérieur au nuage de points de données particulier. Dans l'exemple décrit ici le voisinage temporel est donc formé, pour un nœud 24 du plan temporel 20 par le nœud 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 nœud 26 sera explicité plus bas.

Le nœud 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 œuvre une boucle de calcul qui permet d'évaluer la valeur de la variable cj. Aux fins de ces calculs, chaque point de données 28 est associé au nœud 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, l'équation [20] concerne le voisinage spatial et l'équation [30] concerne le voisinage temporel.

Dans l'équation [10], Wl 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 nœud Gi donné, et 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 nœud 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 nœud 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 nœud 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 nœuds Gi. Ainsi, chaque carré de maillage contient les points de données les plus proches du nœud Gi au centre du carré de maillage considéré.

Dans l'équation [20], W2 est un facteur de normalisation, β est un facteur de pondération, Vi désigne l'ensemble des nœuds voisins d'un nœud Gi donné, et Fij est une matrice définie par la formule [25] de l'Annexe A. L'application de la matrice Fij à Gj revient à estimer la hauteur du nœud Gj à l'emplacement du nœud d'indice i, en tenant compte de de la pente sxj et syj de Gj, et des distances entre le nœud Gj et le nœud Gi. Ainsi l'équation [20] détermine une valeur tirée de la différence entre la hauteur de chacun des nœuds et la hauteur qu'auraient les nœuds voisins en ces nœuds. Dans l'exemple décrit ici, les voisins spatiaux sont les 8 nœuds les plus proches de chaque nœud 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 nœuds, ou supérieur à 8. Toujours en variante, l'équation [20] pourrait comprendre un facteur de pondération pour chaque nœud voisin Gj, par exemple du type noyau Gaussien.

Dans l'équation [30], W3 est un facteur de normalisation, γ est un facteur de pondération, Qi désigne une matrice de transition du nœud Gi pour le nuage de points de données immédiatement antérieur au nuage de points de données courant à l'état du nœud 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 nœud Gi ^t_1 ou pour tenir compte d'un changement de la hauteur du sol dans le temps (due par exemple des vagues dans une application maritime). Pour tenir compte du fait que le véhicule se déplace, la détermination du nœud Gi ^M 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 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 Gi ^t_1 est alors calculée par interpolation du maillage transformé à l'emplacement du nœud Gi. Pour les nœuds pour lesquels aucune information n'était disponible, c'est-à-dire correspondant à une zone non visitée par le véhicule, Gi ^t_1 est marqué comme indéfini, de sorte que le couple Gi- Gi ^t_1 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 nœud d'un nuage encore plus ancien. Néanmoins, l'utilisation d'un seul voisin temporel suffit à forcer la cohérence pour les nœuds 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, à 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, chaque nœud se voit affecter un modèle Gaussien pour l'état du sol, chaque nœud 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 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 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 mettre en œuvre ces calculs.

Dans une opération 300, le calculateur 6 exécute une fonction InitQ. 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 partant d'un autre maillage a priori, non plat, la fonction InitQ initialiserait les vecteurs Gmi en fonction de cet autre maillage. Cette initialisation sera également effectuée à chaque fois qu'un nouveau nœud (c'est-à-dire un nœud à un emplacement qui n'a été 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.

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 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 œuvre de la fonction EM(). 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é, tous les nœuds 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 nœuds d'indice i de la boucle courante d'indice t. La deuxième boucle consiste à répéter la première boucle avec les nœuds mis à jour, en faisant donc varier l'indice k, jusqu'à ce qu'une condition de convergence soit remplie.

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 ou en partie en parallèle sur un processeur graphique, dont les qualités sont connus pour ces applications. 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 nœud d'indice i, et évalue pour chacun d'entre eux une probabilité cj qu'il stocke dans le vecteur C[k]. La 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-l,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). 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 nœud Gmi déplacé à l'emplacement du point de données. L'exponentielle avec les facteurs σΐ et σ2 permettent de converger rapidement vers 1 lorsque la différence est proche de zéro. Dans l'exemple décrit ici, σΐ est fixé à 0,05m et σ2 est fixé à 0,5m. Ces valeurs permettent de donner plus d'importance 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. 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-l,t) de l'itération précédente, ainsi que le vecteur Z 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 formule linéaire en présence du modèle Gaussien. 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-l,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 β a été fixé à 0,5, et le facteur de pondération γ 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.

L'indice i est alors testé pour déterminer si tous les nœuds 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. Lorsque tous les nœuds 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.

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 à converger, ou sur une condition de convergence propre, par exemple la comparaison entre G(k,t) et G(k-l,t). 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.

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 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 nœuds du maillage avec ceux-ci. 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.