Brevet FR2794554A1 — publié le 20001208

La présente invention concerne un procédé de détection et de modélisation de constructions humaines à partir d'un modèle numérique d'élévation. L'invention s'applique particulièrement à la modélisation de structures humaines telles des bâtiments dans de tels modèles numériques d'élévation. Un modèle numérique d'élévation est une structure de données ayant la forme d'un tableau donnant en regard de deux coordonnées l'altitude du point de terrain correspondant à ces deux coordonnées. Il s'agit donc d'une discrétisation du terrain dont la précision dépend fortement de la technologie adoptée pour construire le modèle d'élévation. L'état de l'art dans le domaine de la détection et de la modélisation de structures humaines est essentiellement basé sur des techniques de recherches de primitives. On peut consulter sur ce sujet l'article de Yves Léchervy, Christian Louis et Olivier Monga intitulé "Crestlines contribution to the automatic building extraction" dans l'ouvrage Automatic Extraction of Man-Made Objects from Aerial and Space Images (Il), Monte Verità, 1997, aux éditions Birkhauser Verlag, ETH Zurich. Ces techniques se basent en premier lieu sur des méthodes de calcul de gradient. On peut citer à titre d'exemple d'une telle méthode, la méthode dite de Canny ou de Canny-Deriche. Cette méthode est par exemple présentée dans l'article de J. F. Canny intitulé "A Computational Approach to Edge Detection", IEEE transactions on Patterns Analysis and Machine Intelligence, novembre 1987. À partir du gradient ainsi calculé, on procède généralement à une étape de chaînage des données, afin d'obtenir une représentation vectorielle des objets ainsi détectés. Ensuite, on met en oeuvre une étape de comparaison (ou matching, en anglais) entre ces objets et un ensemble d'objets contenus dans une bibliothèque de référence et qui sont autant de modèles d'objets que l'on cherche à détecter puis modéliser. Néanmoins, une telle approche comporte une limitation majeure puisqu'elle suppose une connaissance a priori des objets que l'on cherche à détecter. Or du fait de l'extrême variété des différentes structures humaines que l'on peut avoir à détecter, cette limitation est extrêmement pénalisante. Le but de la présente invention est de proposer une méthode d'extraction d'empreintes au sol d'objets, et notamment de structures humaines, dans un modèle numérique de terrain, qui ne fasse aucune hypothèse sur les formes et la topologie des objets à détecter. Le procédé conforme à l'invention comporte les étapes consistant à: * faire évoluer un ensemble de contours actifs obéissant à une loi d'évolution, mémoriser les positions de chacun desdits contours actifs lorsque celui-ci rempli une première condition d'arrêt, - faire de nouveau évoluer ledit ensemble de contours actifs selon ladite loi d'évolution, stopper l'évolution desdits contours actifs lorsque ceux-ci remplissent une seconde condition d'arrêt. Ce procédé étant mis en oeuvre par un système de traitement de l'information. Les différents avantages et caractéristiques de l'invention apparaîtront de façon plus claire dans la description qui va suivre en référence aux figures annexées. La figure 1 illustre l'enchaînement des différentes étapes du procédé selon l'invention. Les figures 2a, 2b, 2c et 2d schématisent l'application du procédé de l'invention à un exemple imaginaire. Le procédé selon l'invention repose sur la notion de contours actifs, et plus précisément de contours actifs géodésiques que l'on fait évoluer par une méthode de propagation dite "de courbes de niveaux" (ou "level- set method" en anglais). Les contours actifs géodésiques sont par exemple décrit dans l'ouvrage intitulé "Level Sets Methods" de J. A. Sethian, paru aux éditions Cambridge University Press, en 1996. D'une façon très générale, la méthode des courbes de niveaux consiste à considérer une courbe évoluant avec le temps dont l'évolution est déterminée par une équation de la forme Au = c.IVu!, at avec u qui représente la carte des distances associée à cette courbe, t qui représente le temps (ou les itérations dans le cas d'un système à temps discret), Vu qui représente le gradient de la carte de distance (et |Vu| est son module), et c qui est un paramètre appelé vitesse. La carte de distances d'une courbe associe à chaque point de l'espace la distance qui le sépare de cette courbe. Cette distance est signée, de sorte que l'on peut caractériser la courbe comme le lieu des points o la carte de distances change de signe. L'intersection de cette carte des distances avec l'image traitée est appelée isocontour 0, et c'est lui qui donne à la fin de l'évolution le contour des objets détectés dans cette image. Le contour actif est représenté par cette intersection. La vitesse c est fonction de l'image. Par analogie, on dit qu'il forme un champ de force qui attire le contour actif dans le lieu des points formant un minimum local d'énergie. Plus précisément, cette vitesse c est minimale à proximité d'un contour d'un objet de l'image, de sorte que le contour actif n'évolue plus lorsqu'il se trouve sur un de ces bords (c'est-à-dire qu'il l'a alors détecté). À l'inverse, le contour actif évolue lorsqu'il se trouve loin d'un tel contour. Le procédé selon l'invention consiste à utiliser un tel contour actif pour la détection d'objets, et notamment de structures humaines, dans un modèle numérique d'élévation. Selon cette méthode, le modèle numérique d'élévation est considéré comme une image numérique dont la valeur de chaque pixel représente l'élévation du terrain à l'endroit correspondant à ce pixel. Selon une première mise en oeuvre de l'invention, la vitesse c peut être de la forme: c = + kLe terme1est appelé "terme d'attache aux données". l + k2.1l ' 1 + k2' IVll Dans cette équation, IVII est le module du gradient de l'image I représentant le modèle numérique d'élévation traité, tandis que k1 et k2 sont deux paramètres. L'image numérique I représente le modèle numérique d'élévation. La valeur de chaque pixel est égale à l'élévation du point correspondant dans le modèle numérique d'élévation. Le gradient IV peut être calculé par n'importe laquelle des nombreuses méthodes de l'état de l'art. Notamment, il peut être calculé par l'algorithme de Canny- Deriche, précédemment évoqué. Le paramètre k1 peut être assimilé à la vitesse de propagation du contour actif. Sa valeur peut être déterminée expérimentalement. Typiquement, k: est compris dans l'intervalle [-0.3; 0.3], et on peut préférentiellement choisir k =+0. 1. Le paramètre k2 représente un degré d'attache aux données de l'image. Plus sa valeur est élevée, plus l'évolution du contour actif sera influencée par l'image I. Inversement, plus sa valeur est faible, plus le contour actif évoluera de façon autonome, indépendamment de l'image I. Là encore, la valeur adéquate peut être déterminée de façon expérimentale. Typiquement, cette valeur est choisie dans l'intervalle [0; 0.8], et on choisira préférentiellement k2=0.1. Selon une deuxième mise en oeuvre du procédé selon l'invention, la force c est déterminé par l'équation: k k3 divIl l) C +k2 +k2 1+k2. lvI( 1+k:.li Ce deuxième terme qui apparaît à la suite du premier introduit dans la première mise en oeuvre est appelé terme de diffusion. Son rôle est de lisser le contour actif en pénalisant sa longueur de sorte que l'on tende, au fil de son évolution, vers un contour de longueur minimale. Le terme divjv-Zl représente la courbure du contour, et k3 est un nouveau paramètre, que l'on choisit typiquement dans l'intervalle [0; 0. 3] et dont la valeur adéquate est déterminée de façon expérimentale. Si l'on choisit k3=0, on retrouve l'équation de la première mise en oeuvre explicitée précédemment. Sur la figure 1, l'étape référencée 1 consiste à procéder à une première évolution d'un ensemble de contours actifs, chacun d'entre eux obéissant à l'une des équations données. Cet ensemble peut éventuellement être réduit à un unique contour actif. De façon indépendante les uns des autres, l'évolution des contours actifs cessent lorsqu'une première condition d'arrêt est atteinte. Cette condition d'arrêt peut prendre plusieurs formes. Elle peut par exemple être basée sur un calcul de la moyenne et du maximum de l'évolution du contour, sur l'ensemble des points du contour actif considéré. Autrement dit, on calcule pour chaque point son évolution entre deux itérations. On décide alors de l'arrêt ou non en fonction de deux tests: le premier test consiste à comparer la valeur moyenne des progressions de chaque point du contour actif à une première valeur seuil, et le second test consiste à comparer la valeur maximale des progressions à un second seuil. Lorsque ces deux tests sont remplis, c'est-à-dire lorsque la moyenne et le maximum des progressions deviennent inférieurs aux seuils, alors la progression est arrêtée, et l'on mémorise (étape référencée 2 sur la figure 1) les positions du contour actif. L'étape 3 consiste à relancer la progression du contour actif précédemment arrêté, à partir de sa position courante. L'évolution se fait de la même façon que pour l'étape référencée 1. Cette nouvelle progression est arrêtée lorsqu'une deuxième condition d'arrêt est remplie. Cette deuxième condition d'arrêt peut par exemple être la même que la première. L'étape 4 consiste à mémoriser la position du contour actif ainsi qu'il fut fait lors de l'étape 2. Pour chaque contour actif, les deux positions mémorisées permettent de détecter les objets présents et les éventuels objets imbriqués dans le modèle numérique d'élévation. La figure 2 illustre l'application du procédé selon l'invention sur un exemple pratique. La référence O représente un objet à détecter par un contour actif dont on a figuré l'isocontour I. La figure 2a représente l'état initial. L'isocontour I (ainsi que le contour actif dont il est la projection) possède un état initial quelconque. La figure 2b représente l'état à l'étape 2. L'isocontour I "colle" alors aux contours extérieurs de l'objet O. Cette position est mémorisée. La figure 2c représente l'état durant l'étape 3. L'isocontour a continué son évolution en dépassant sa première position d'arrêt. La figure 2d représente l'état à l'étape 4. L'isocontour I "colle" cette fois-ci au contour intérieur et cette nouvelle position est mémorisée. Les deux positions mémorisées (à l'étape 2 et à l'étape 4), le bâtiment O est détecté. Les isocontours mémorisés lors des étapes 2 et 4 (figures 2b et 2c) représentent l'objet O tel que détecté par le procédé selon l'invention. REVENDICATIONS 1) Procédé d'extraction automatique d'empreintes au sol d'objets, notamment de structures humaines, au sein d'un modèle numérique d'élévation, consistant à: * faire évoluer un ensemble de contours actifs obéissant à une loi d'évolution, À mémoriser les positions de chacun desdits contours actifs lorsque celui-ci rempli une première condition d'arrêt, À faire de nouveau évoluer ledit ensemble de contours actifs selon ladite loi d'évolution, stopper l'évolution desdits contours actifs lorsque ceux-ci remplissent une seconde condition d'arrêt, ledit procédé étant mis en oeuvre par un système de traitement de l'information. 2) Procédé selon la revendication 1, caractérisé en ce que ladite loi d'évolution est déterminée par l'équation: au k. Vu dans laquelle u représente la carte des distances associée à un desdits contours actifs, t représente les itérations, JV représente le gradient de l'image représentant ledit modèle numérique d'élévation, |Vu représente le gradient de ladite carte des distances, et k. et k2 sont deux paramètres. 3) Procédé selon la revendication précédente, caractérisé en ce que ladite loi d'évolution comporte en outre dans son second membre un terme de la k3 -div 7Vui(V forme: 1+k2' V( 1, dans laquelle le terme divv- ulreprésente la courbure dudit contour actif, et k3 un paramètre. 4) Procédé selon l'une des revendications précédentes, caractérisé en ce que lesdites conditions d'arrêt sont basées sur un calcul de la moyenne et du maximum de l'évolution dudit contour actif sur l'ensemble des points dudit contour actif.