Brevet FR2783068A1 — publié le 20000310

Procédé pour obtenir une modélisation tridimensionnelle d'un ensemble de blocs de bâtiments La présente invention concerne un procédé pour construire efficacement une modélisation en trois dimensions d'un ensemble de blocs de bâtiments à partir de deux images stéréoscopiques aériennes ou prises par satellite de cet ensemble et une carte de cette ville. L'invention s'applique particulièrement bien pour la planification de réseaux de radiocommunication cellulaires. Un tel réseau comme par exemple un réseau GSM (Global System for Mobile communication) comporte une pluralité de stations de base réparties géographiquement. Chacune de ces stations est destinée à la couverture radio d'une zone géographique déterminée appelée cellule. La zone géographique que couvre effectivement une station de base donnée dépend de l'environnement géographique et en particulier de la présence de structures humaines dans cet environnement, qui influent sur les radiocommunications. Aussi, afin de disposer de façon optimale les stations de base de sorte qu'un mobile soit toujours en mesure de communiquer avec une station de base, il est nécessaire de connaître l'emplacement et les dimensions de ces structures. Les procédés de modélisation d'ensembles de bâtiments existants cherchent à extraire chacun des bâtiments constitutifs de cet ensemble. On peut citer par exemple les articles suivants à titre d'état de l'art: a " Application of Semi-Automatic Building Acquisition " de Eberhard Gulch de l'université de Bonn, paru dans l'ouvrage Automatic Extraction of Man-Made Objects from Aerial and Space Images, aux éditions Birkhauser Verlag. * " TOBAGO - a topology builder for the automated generation of building models " de Armin Gruen et Hanbin Dan, tous deux de I'université de Zrich, I'article étant paru lui aussi dans l'ouvrage Automatic Exctraction of Man-Made Objects from Aerial and Space Image, aux éditions Birkhauser Verlag. Ces deux méthodes sont des approches semi-automatiques dans lesquelles un opérateur doit manuellement pointer les contours de chaque bâtiments dans l'image aérienne ou satellitaire. L'inconvénient majeur de ce type d'approche est le temps nécessaire pour sa mise en oeuvre. On peut en effet estimer à plusieurs dizaines de secondes le temps nécessaire à l'extraction d'un unique bâtiment. Ce temps devient bien sûr prohibitif pour l'extraction de l'ensemble en entier. Afin de palier cet inconvénient majeur, le procédé selon l'invention a pour idée de base de s'intéresser aux blocs de bâtiments constitutifs de cet ensemble plutôt qu'aux bâtiments indépendamment les uns des autres. Plus précisemment, I'invention a pour objet un procédé pour construire une modélisation tridimensionnelle d'un ensemble de blocs de bâtiments à partir d'une paire d'images stéréoscopiques calibrée représentant cet ensemble, et d'une représentation plane de type carte le représentant, la paire d'images stéréoscopiques calibrées en question et la représentation plane de type carte étant associées. Le procédé comporte en outre les étapes suivantes: ò extraction de l'empreinte au sol des blocs de bâtiments à partir de la représentation plane de type carte, * calcul d'une hauteur caractéristique pour chacun des blocs de bâtiments à partir de la paire d'images stéréoscopiques calibrés, * calcul d'une représentation de l'altitude du terrain associé à l'ensemble, construction d'une modélisation tridimensionnelle de chacun des blocs de bâtiments contenus dans l'ensemble, à partir des empreintes au sol, des hauteurs caractéristiques, et de la représentation de l'altitude du terrain. L'invention et ses avantages seront mieux compris dans la présentation qui va être faite de quelques unes de ses mises en oeuvre, en référence aux figures annexées. La figure 1 représente un enchaînement des différentes étapes constitutives du procédé selon l'invention. La figure 2 illustre l'étape du procédé selon l'invention consistant à linéariser les contours des objets par la méthode de Douglas-Peucker. La figure 3 illustre le problème de la fusion des composantes connexes. Les étapes référencées 1 à 4 sur la figure 1 consistent à extraire des contours (ou empreintes au sol) de blocs de bâtiments, sur une représentation plane de l'ensemble de bâtiments à traiter. Cette représentation plane est préférentiellement une carte numérisée, et elle sera appelée dans la suite indifféremment par l'un ou l'autre terme. La numérisation d'une carte papier peut entraîner des imperfections sur cette carte, comme par exemple des différences de couleurs dues au capteur. Pour les traitements ultérieurs, il est nécessaire de supprimer ces différences de couleurs qui sont dues au capteur et non à des caractéristiques sémantiques. Ainsi, on ne doit avoir qu'une seule couleur pour les rues et les avenues, une seule couleur pour les blocs de bâtiments etc. Pour ce faire, une quantification colorimètrique est mise en oeuvre à l'étape référencée 1 sur la figure 1. Une telle quantification peut être réalisée par plusieurs algorithmes différents. On peut citer à titre d'exemple l'algorithme dit " K-means ", décrit dans l'ouvrage Pattern Recognition Principles, de Julius T. Tou et Rafael C. Gonzales, paru aux éditions Addison-Wesley, en 1974. Avec un tel algorithme, il est nécessaire de préciser en entrée le nombre de classes que l'on veut obtenir. Ce nombre peut par exemple être renseigné manuellement par l'opérateur, en fonction du nombre de couleurs qu'il voit effectivement sur la carte numérisée. Le résultat de cette étape du procédé selon l'invention est une image comportant un nombre restreint de couleurs, chaque couleur correspondant à une classe d'objets dans la réalité qui est représentée. On a ainsi, une classe (c'est-à-dire une couleur) pour les rues, les avenues, les places etc. (appelée ci- après, classe " fond "), une classe pour les blocs de bâtiments (dénommée classe " bâtiments "), une classe pour les informations diverses comme les écritures signalétiques (classe " divers ") etc. Ces trois classes sont les classes principales utilisées par le procédé décrit, mais il est possible d'ajouter d'autres classes sans pour autant sortir du cadre de l'invention. Notamment, il est possible que l'étape de classification nécessite plusieurs classes pour les blocs de bâtiments. En effet, dans le cas d'une agglomération urbaine importante, il peut arriver que les différentes communes ou les différents arrondissement d'une même commune soient représentées avec des couleurs substantiellement différentes. Dans ce cas néanmoins, de façon préférentielle, ces différentes classes seront regroupées en une unique classe " bâtiments " afin de faciliter la suite du procédé. La deuxième étape du procédé selon l'invention, référencée 2 sur la figure 1, consiste à extraire les contours des différents objets qui composent la carte. Plusieurs possibilités de mises en oeuvre sont possibles. On peut par exemple citer des techniques classiques d'extraction de contours comme par exemple l'algorithme dit de Canny-Deriche (ou de Deriche), ou des méthodes basés sur des contours actifs, ce dernier concept étant présenté dans l'article " Snakes: active contour models " paru dans l'ouvrage Proceeding ICCV-1987). Ces différentes méthodes étant accessibles à l'homme du métier, nous ne rentrerons pas plus dans leur description. Préférentiellement, afin de faciliter la mise en oeuvre des techniques d'extraction de contours, il est possible de mettre en oeuvre une sousétape de calcul des composantes connexes présentes dans la carte numérisée. Ce calcul est lui aussi un calcul classique en analyse d'images. Dans la mesure o la carte numérisée a subi préalablement une quantification colorimètrique, le choix de la méthode de calcul des composantes connexes est indifférent: toutes les méthodes donneront le même résultat. L'étape suivante, référencée 3 sur la figure 1, consiste à effectuer une vectorisation linéaire des contours contenus dans la carte. Autrement dit, on recherche à présenter les contours des objets comme étant une succession de segments de droite, chaque objet (i.e. blocs de bâtiment, rues etc.) étant alors représenté comme un polygone. Là encore, plusieurs algorithmes peuvent être mis en oeuvre pour réaliser cette linéarisation. On peut par exemple citer la méthode Douglas- Peucker illustrée par la figure 2. Sur la figure 2, les points P1, P2 et P3 forment un triangle quelconque que l'on cherche à rendre linéaire. On calculer pour ce faire la flèche F, que l'on compare à un seuil. On comprend aisément que si cette flèche F1 est inférieure à un seuil donné et suffisamment faible, cela signifie que les points P1, P2 et P3 peuvent être considérés comme alignés. On peut alors remplacer les segments [P1; P2] et [P2; P3] par un unique segment [P1 P3]. On traite alors le point suivant, P4 en considérant la flèche F2 du triangle formée par les deux segments [P1; P3] et [P3; P4]. Ainsi, de façon incrémentale, on construit un contour linéarisé de chacune des composantes connexes présentes dans la carte. L'étape suivante, référencée 4 sur la figure 1, consiste à améliorer la carte numérisée. La figure 3 permet de comprendre le problème qui se pose à I'issue des étapes précédentes. Elle représente deux composantes connexes C1 et C2, ou plus généralement deux objets, séparées l'une de l'autre par un ensemble de pixels. On remarque par ailleurs que deux des cotés de ces composantes connexes sont alignés. Il existe alors deux possibilités 5. les composantes connexes sont séparées par une rue, les composantes connexes forment un seul bloc de bâtiments et les pixels séparants ces deux composantes connexes appartiennent à la classe correspondant aux inscriptions (c'est-à-dire à la classe " divers "). Autrement dit, il y avait sur la carte originale, à cet endroit- là, une inscription, par exemple un nom de quartier ou de monument, qui a laissé un " vide " lors des traitements précédents. Afin de distinguer ces deux cas, on part d'un des segments formant un coté d'une des composantes connexes, par exemple, le segment s, et l'on avance pixel par pixel dans la direction donnée par le segment s. Pour chaque pixel ainsi traversé, on regarde la classe à laquelle il appartient. Il suffit de rencontrer un seul pixel appartenant à la classe correspondant aux rues, avenues etc. (C'est-à-dire à la classe " fond ") pour considérer que les deux composantes connexes C1 et C2 doivent rester disjointes. Dans le cas contraire, les deux composantes connexes sont fusionnées. Lors de cette étape d'amélioration, d'autres traitements peuvent être mis en oeuvre afin d'améliorer la qualité des empreintes au sol des blocs de bâtiments que l'on extrait. L'étape référencée 5 sur la figuré 1 consiste à extraire les hauteurs des blocs de bâtiments. Un bloc de bâtiments donné présente bien évidemment plusieurs hauteurs différentes dans le cas général, c'est-à-dire en principe une hauteur par bâtiment contenu dans le bloc. Autrement dit, le but de cette étape est de calculer une hauteur caractéristique du bloc de bâtiments correspondant à chacune des composantes connexes présentes dans la carte. Chaque composante connexe est définie par un polygone. Dans un premier temps, il est nécessaire de faire la correspondance entre les polygones extraits de la représentation plane de type carte, et les contours dans les images stéréoscopiques. Pour cela, il faut déterminer quelle transformation géométrique, plus précisément, quelle similitude permet d'effectuer la correspondance entre les points de la représentation plane de type carte et les points des images stéréoscopiques. Cette sous-étape peut être réalisée en déterminant, par exemple manuellement, une pluralité de couples de points, point de carte / point d'image stéréoscopique. Trois points permettent d'avoir une connaissance suffisante de la similitude permettant de passer de la carte à une image stéréoscopique et vice-versa. Ces couples de points sont préférentiellement des points caractéristiques, comme des centres de carrefour. Connaissant cette similitude, la correspondance entre chaque polygone extrait dans la carte, et le polygone correspondant dans une des deux images stéréoscopiques est automatisable de façon immédiate. Ensuite, pour chacun de ces polygones, on calcule par triangulation les coordonnées tridimensionnelles d'un ensemble de points se situant à l'intérieur de ce polygone. Dans la mesure o l'on a disposition une paire d'images stéréoscopiques calibrées en plus de l'image représentant la carte, ce calcul ne pose pas de problèmes à l'homme de l'art. Cet ensemble de points peut bien sûr être l'intégralité des points contenus dans le polygone traité. Il peut aussi s'agir d'un ensemble de points choisis aléatoirement parmi cette intégralité afin de minimiser le temps de traitement. À partir de cet ensemble de coordonnées tridimensionnelles, on peut par exemple calculer la hauteur du bloc de bâtiments comme étant la hauteur moyenne calculée sur cet ensemble de points. Afin de tenir compte d'importantes disparités de hauteurs, dues notamment à des cours intérieurs au sein d'un bloc de bâtiment, on peut mettre en oeuvre un procédé statistique plus sophistiqué éliminant du calcul de la moyenne, les points aberrants, c'est-à-dire dont l'altitude ne peut raisonnablement pas être une altitude de bâtiments car étant trop peu élevée. D'autres choix peuvent être fait comme prendre la hauteur maximale, la hauteur minimale, la hauteur modale etc. L'étape référencée 6 sur la figure 1 consiste à extraire l'altitude du sol. Cette étape peut être mise en oeuvre au moins de deux façons différentes en fonction du degré de précision désiré du modèle tridimensionnel final. Selon une première mise en oeuvre, on procède à un échantillonnage de points appartenant à la classe " fond ". Cet échantillonnage peut par exemple être un tirage aléatoire uniformément réparti parmi les points de la classe " fond ". À partir de cet échantillonnage, on calcule ensuite une altitude moyenne. Selon une seconde mise en oeuvre, on procède d'abord à une triangulation, par exemple une triangulation de Delaunay, du terrain, et on réalise le procédé décrit pour la première mise en oeuvre dans chacun des triangles obtenus, de façon indépendante. La première mise en oeuvre suppose que le terrain est suffisamment plat dans l'aire représentée par l'image traitée pour qu'il puisse être modélisé par un plan horizontal. La seconde hypothèse permet de mieux s'adapter à la réalité au détriment d'un calcul supplémentaire. Connaissant l'empreinte au sol (i.e. le contour selon un plan horizontal) des blocs de bâtiments, une hauteur caractéristique pour chacun de ceux-ci ainsi que l'altitude du sol, chaque bloc de bâtiments est parfaitement connu et donc automatiquement modélisable. 1 il! REVENDICATIONS 1) Procédé pour construire automatiquement une modélisation tridimensionnelle d'un ensemble de blocs de bâtiments à partir d'une paire d'images stéréoscopiques calibrée représentant ledit ensemble, et d'une représentation numérique plane de type carte représentant ledit ensemble, ladite paire d'images stéréoscopiques calibrées et ladite représentation numérique plane de type carte étant associées, et ledit procédé comportant les étapes suivantes: 10. extraction de l'empreinte au sol desdits blocs de bâtiments à partir de ladite représentation numérique plane de type carte, * calcul d'une hauteur caractéristique pour chacun desdits blocs de bâtiments à partir de ladite paire d'images stéréoscopiques calibrés, * calcul d'une représentation de l'altitude du terrain associé audit ensemble, À construction d'une modélisation tridimensionnelle de chacun des blocs de bâtiments contenus dans ledit ensemble, à partir desdites empreintes au sol, desdites hauteurs caractéristiques, et de ladite représentation de l'altitude du terrain. 2) Procédé selon la revendication précédente, caractérisé en ce que ladite extraction de l'empreinte au sol desdits blocs de bâtiments est réalisée par les étapes suivantes: ò quantification colorimétrique de ladite représentation numérique plane de type carte, * extraction des contours des objets contenus dans ladite représentation numérique plane de type carte, linéarisation desdits contours, amélioration desdits contours pouvant aboutir à la réduction du nombre desdits objets, chacun desdits objets résultants correspondant à une desdites empreintes au sol. 3) Procédé selon la revendication précédente, caractérisé en ce que l'étape d'extraction de contours est précédée d'une étape de calcul de composantes connexes. 4) Procédé selon l'une des revendications précédentes, caractérisé en ce que l'association entre ladite paire d'images stéréoscopiques calibrées et ladite représentation numérique plane de type carte est effectuée par pointé d'une pluralité de points dans ladite représentation numérique plane de type carte et des points correspondants dans une des images de ladite paire d'images stéréoscopiques calibrées, afin de déterminer la similitude existant entre ladite représentation numérique plane de type carte et ladite paire d'images stéréoscopiques calibrées. ) Procédé selon l'une des revendications précédentes caractérisé en ce que ladite représentation de l'altitude est une altitude moyenne. 6) Procédé selon l'une des revendications 1 à 4, caractérisé en ce que ladite représentation de l'altitude est effectuée par triangulation, par exemple de Delaunay, du terrain associé audit ensemble de blocs de bâtiments.