FR 2779854 A1 19991217 FR 9807557 A 19980616 PROCEDE DE PRODUCTION DE DONNEES CARTOGRAPHIQUES La présente invention concerne les procédés de production de données cartographiques caractérisant les pixels d'une image numérique et elle trouve des applications dans de très nombreux domaines. Parmi ces domaines d'application, on peut notamment citer la production de données cartographiques caractérisant la position en trois dimensions de points d'une scène à partir de plusieurs images fournies par des capteurs voyant la scène sous des angles différents. Les données cartographiques sont alors constituées par les coordonnées tridimensionnelles du point dans la scène. On connaît déjà de nombreux procédés de production de données cartographiques destinées aux applications précéden- tes. Dans le cas particulier de la stéréographie, il existe déjà de très nombreux procédés permettant de retrouver le relief d'une scène à partir d'au moins deux images planes de la scène, prises sous des angles de vue différents. Ces procédés recherchent une mise en correspondance d'éléments différents dans les images. On trouvera notamment une description d'algorithmes appropriés dans l'article de Nicolas Ayache "Artificial vision for mobile robots: stereo- vision and multisensory perception", InterEdition 1991, auquel on pourra se reporter. Cet article montre en particulier qu'on peut limiter la recherche du pixel d'une image qui correspond à un pixel d'une autre image à un segment d'une droite épipolaire bien déterminée. On utilise à l'heure actuelle l'une ou l'autre de deux approches pour mettre en correspondance ou apparier les éléments des deux images. Une première méthode consiste à rechercher une correspondance pixel à pixel entre les images (stéréovision dense). Une autre méthode recherche la corres- pondance entre des éléments plus synthétiques dans l'image, tels que des segments extraits (stéréovision extraite). Dans le premier cas, on utilise la corrélation entre des vignet- tes. En stéréovision dense on compare, par des processus classiques de reconnaissance de forme, une vignette centrée sur le pixel à apparier d'une première image à une série de vignettes centrées sur les positions possibles du correspon- dant de ce pixel dans l'autre image ou chacune des autres images. A chaque position testée, correspondant à une disparité (différence entre abscisse sur les droites épipo- laires respectives), on associe un indice de ressemblance, tel qu'un coefficient d'intercorrélation. Chaque pixel a plu- sieurs disparités candidates (une par maximum local de l'intercorrélation). Le choix de la disparité retenue pour chaque pixel se fait généralement en considérant les choix de disparité des pixels voisins de la même ligne. La cohéren- ce est donc monodimensionnelle. C'est le choix de la dispari- té parmi celles possibles qui est simplifié en n'effectuant la comparaison qu'avec des vignettes toutes centrées sur une même épipolaire. En contrepartie de sa simplicité, cette méthode a un inconvénient: elle n'utilise pas la cohérence spatiale entre points adjacents d'une même image, dans des domaines étendus. Souvent, les résultats obtenus présentent des stries correspondant à la direction des épipolaires. De meilleurs résultats sont obtenus en comparant les disparités choisies faites sur des lignes voisines. Mais il en résulte des temps de calcul prohibitifs. On a également déjà proposé (document Ayache déjà mentionné) une approche en stéréovision discrète, mettant en correspondance des segments extraits des images, utilisant une propagation bidimensionnelle de résultats, avec vérifica- tion d'hypothèses. Cette approche est schématisée sur la figure 1. Pour une image, on fait des hypothèses d'appariement des segments. Elles consistent à choisir des segments de longueur et d'orientation à peu près similaires et compatibles dans la géométrie épipolaire. On obtient ainsi, pour une image, une liste H d'hypothèses d'appariement entre deux segments. Pour chacune de ces hypothèses Hi, correspondant à un appariement déterminé, on tente de propager l'appariement issu de l'hypothèse au segment voisin. On détermine, pour chaque hypothèse, une "force" qui est le nombre de segments pour lequel on arrive à un appariement correct. On établit ainsi une liste Ai d'appariements réputés corrects. Puis, pour chaque paire de segments, on élimine, dans la liste H d'hypothèses, toutes les hypothèses semblables aux appariements Ai obtenus. Les conflits d'appariement entre hypothèses peuvent être résolus en retenant celle des hypo- thèses pour laquelle la "force" est la plus élevée. Une fois éliminées dans H, les hypothèses semblables à Ai, il subsiste une liste A d'appariements pour lesquels la continuité est vérifiée dans la liste avec rejet des appa- riements incohérents. On arrive ainsi à une liste A finale. Cette solution donne des résultats satisfaisants, mais uniquement pour une stéréovision non-dense. La présente invention vise à fournir un procédé de production de données cartographiques répondant mieux que ceux antérieurement connus aux exigences de la pratique, notamment en ce qu'il fournit des résultats fiables avec un volume de calcul acceptable. Elle propose notamment d'écarter les inconvénients du traitement global (utilisés en stéréovi- sion discrète) en utilisant la cohérence bidimensionnelle qui existe dans des zones continues des images (c'est-à-dire en conservant les caractéristiques favorables) Pour cela il est fait usage de la cohérence bidimension- nelle de l'image sur de grands domaines, afin de propager des informations considérées comme sûres. Les voisins d'un point sûr ont une forte probabilité d'avoir un résultat (par exemple une disparité) proche de celui-ci. Pour mettre en oeuvre cette approche on partira de "germes". Un germe sera un point dont le résultat est considéré comme certain. Ce résultat sera considéré comme une prédiction du résultat des voisins. Pour que le germe croisse, on vérifie et corrige la prédiction; puis on intègre le voisin au germe. En plus de la prédiction et de la vérification, déjà prévues dans l'article de Ayache, on utilise donc une propagation bidimen- sionnelle grâce au voisinage bidimensionnel entre pixels. De façon générale, l'invention propose notamment un procédé de production de données cartographiques caractéri- sant des pixels d'au moins une image numérique, suivant lequel (a) on sélectionne un pixel germe, auquel est affectée une donnée cartographique connue ou déterminée de façon sûre; (b) on affecte, à chaque pixel d'un voisinage prédéterminé à deux dimensions centré sur le pixel germe, une donnée cartographique prédite constituée par la valeur cartographi- que du pixel germe; (c) on applique, à chaque pixel du voisinage, un critère de validité de la donnée prédite et on retient ce pixel en tant que pixel germe additionnel, avec la valeur cartographique prédite, éventuellement ajustée, si le critère est rempli; et (d) on poursuit la croissance de façon bidimensionnelle, en effectuant de plus un contrôle de cohésion entre les valeurs prédites dans le cas d'un pixel appartenant aux voisinages de plusieurs pixels germes. Les étapes de prévision et de vérification (étapes b et c) peuvent utiliser des critères comparables à ceux décrits dans l'article de N. Ayache "Vision stéréoscopique et perception multi-sensorielle" déjà cité, mais ces critères sont appliqués, dans le cas de l'invention, à une cartogra- phie du genre qu'on peut qualifier de dense, en ce sens qu'elle affecte une valeur cartographique à chaque pixel plutôt que de traiter des segments, comme dans le cas de l'article de Ayache. Dans le cas particulier de la stéréovision, la donnée cartographique est la disparité, dont on peut ensuite déduire par des algorithmes connus, pour chaque pixel de coordonnées (x,y), l'altitude (z). Dans ce cas, l'étape (c) pourra impliquer, pendant la propagation du germe et alors que le pixel à traiter appar- tient au voisinage de plusieurs pixels germes pré-existants, le calcul d'un coefficient d'intercorrélation en fonction de la disparité, mais cela uniquement dans un domaine étroit autour de la disparité prédite. Lorsque les disparités prédites à partir de plusieurs pixels germes diffèrent entre elles d'une quantité supérieure à un seuil de discontinuité prédéterminé, plusieurs recherches seront nécessaires et fréquemment les disparités prédites seront les mêmes pour les différents pixels, au seuil de discontinuité près. L'intérêt de l'invention dans ce cas apparaît immédiate- ment si une comparaison est faite avec l'application d'un algorithme classique de stéréovision dense. Un tel algorithme recherche globalement les appariements entre tous les pixels d'une ligne d'une première image et des pixels correspondants d'une seconde image. Cela implique un calcul de corrélation qui est effectué pour chacun des pixels successifs d'une ligne d'une première image, sur un intervalle de recherche qui est forcément beaucoup plus étendu que dans le cas de l'invention. A l'issue de cette première étape, chacun des N coefficients d'intercorrélation correspondant à chacun des N points d'une ligne, fournit un ensemble d'appariements potentiels du pixel correspondant. Une opération ultérieure effectue une sélection par ligne des appariements, en utilisant la cohérence spatiale unidimensionnelle de l'image. A titre d'indication, on peut relever que l'algorithmie classique exige autant de corrélations que de disparités entières possibles, alors que la mise en oeuvre de l'inven- tion n'exige dans la plupart des cas que trois corrélations par pixel, correspondant à la vérification de la présence d'un maximum local pour la majorité des points. En d'autres termes, l'invention propose, dans le cas d'un procédé de stéréovision dense o la donnée cartographique est la disparité de chaque pixel d'un couple d'images stéréogra phiques, suivant lequel, une fois constitué un germe formé de plusieurs pixels, (b) on affecte, à chaque pixel à traiter appartenant au voisinage de plusieurs pixels du germe, plusieurs disparités prédites constituées par les disparités de chaque pixel germe voisin, (c) on applique au pixel à traiter, un même critère de validité de chaque disparité prédite à partir d'un pixel germe voisin, sous forme d'un calcul d'intercorrélation autour de la disparité donnée par la prédiction et dans un intervalle de discontinuité prédéterminé. Cet intervalle correspond à une continuité entre la prédiction et le résultat recherché. On retient celle des disparités prédites qui donne le pic de corrélation le plus élevé, dans la mesure o le coefficient d'intercorrélation du pic dépasse un seuil prédéterminé; et (d) on intègre le pixel traité au germe si la proposition d'intercorrélation est supérieure au seuil, puis on poursuit la croissance de façon bidimensionnelle. Au cours de cette croissance, on traite les pixels voisins auxquels n'est pas encore attribuée une disparité, ainsi que les pixels pour lesquels les critères de validité n'ont pas été remplis, par exemple parce que les prédictions à partir de plusieurs pixels voisins diffèrent des valeurs supérieurs au seuil de discontinuité. La croissance peut ainsi se poursuivre jusqu'à remplir toute région qui est relativement homogène et pour laquelle un appariement est possible. Elle conduira en revanche à écarter les pixels pour lesquels l'appariement est impossi- ble, par exemple parce qu'un point représenté par un pixel dans une des images est masqué dans l'autre image ou parce qu'il y a une discontinuité brutale de disparités, par exemple dans des images de scènes comportant des ruptures de relief brutales. Dans le second cas, les domaines qui n'auront pas été traités par propagation d'un germe situé dans un premier domaine peuvent être traités à leur tour, en partant d'un nouveau germe. Les caractéristiques ci-dessus ainsi que d'autres apparaîtront mieux à la lecture de la description qui suit de modes particuliers de réalisation, donnés à titre d'exem- ples non limitatifs. La description se réfère aux dessins qui l'accompagnent, dans lesquels: - la figure 1, déjà mentionnée, est un organigramme d'un algorithme d'appariement de segments connu (par exemple celui de l'article de N. Ayache); - la figure 2 est un diagramme de principe d'un algo- rithme indiquant les traitements successifs qui interviennent dans le procédé suivant l'invention; - les figures 3A, 3B et 3C indiquent des voisinages utilisables pour mettre en oeuvre l'invention; - la figure 4 montre un critère possible de sélection d'un pixel germe; - la figure 5 montre la croissance de la zone traitée dans un domaine homogène, en présence d'une zone incohérente avec le domaine o s'effectue la croissance. Comme on l'a déjà indiqué plus haut, le principe de base de l'invention consiste dans la propagation, jusqu'à couvrir tout un domaine homogène, d'informations considérées comme sûres en partant du postulat que les voisins d'un pixel dont on a déterminé la donnée cartographique sûre ont une forte probabilité d'avoir une donnée cartographique égale à la donnée du pixel sûr ou proche de cette donnée. Pour cela on peut considérer que la démarche suivant l'invention implique la mise en oeuvre de quatre critères successifs: - critère 1: critère de définition d'un pixel sûr, qui constituera un germe initial; - critère 2: critère de détermination des valeurs carto- graphiques prédites pour un pixel non encore traité et voisin d'un pixel ou de pixels germe; - critère 3: critère de validation d'une valeur carto- graphique égale à une valeur prédite, éventuellement avec une correction; - critère 4: choix d'un voisinage pour la propagation du germe. La démarche suivie est schématisée en figure 2. La première opération consiste à recherche un pixel sûr, parmi ceux qui ne sont pas encore traités. On définit, autour de ce pixel, un voisinage constitué de pixels de croissance. On peut utiliser divers voisinages. Dans le cas d'un réseau carré de pixels, il peut comporter huit ou quatre pixels, comme indiqué sur les figures 3A et 3B. Dans le cas d'une répartition en quinconce, le voisinage sera généralement constitué de six pixels occupant les sommets d'un hexagone (figure 3G). A partir de là, on exécute sur chaque pixel de croissance (voisin d'au moins un pixel germe), une boucle de traitement. La première étape de la boucle consiste à collecter et à exploiter les prédictions, puis à calculer une valeur cartographique à partir de cette exploitation. La valeur cartographique attribuée et éventuellement corrigée est ensuite soumise à un critère de validation. Si le critère n'est pas rempli, la valeur est considérée comme non valide et il y a retour à l'entrée de la boucle. Si le critère est rempli, la valeur validée est mémorisée pour le pixel traité. Les pixels de l'image appartenant à son voisinage et non encore affectés d'une valeur sont considérés comme des pixels de croissance, auxquels on applique la boucle de traitement. Stéréovision dense: On décrira maintenant un mode possible de mise en oeuvre du procédé pour affecter une disparité, constituant la donnée cartographique, aux points d'une scène représentée par des images de la scène vue sous des angles différents. L'opération de départ consiste à sélectionner un point auquel correspondra le pixel germe dans une des images. Dans certains cas, le point de la scène a des caractéristiques connues, et peut être identifié visuellement dans les deux images. Dans ce cas la disparité peut être sélectionnée de façon arbitraire. Dans la plupart des cas cependant, il faudra affecter une disparité obtenue de façon sûre par le calcul. Pour cela, on établit une courbe de variation du coeffi- cient dintercorrélation en fonction de la disparité sur un large intervalle de recherche le long d'une épipolaire. On connaît déjà des méthodes de détermination de l'intervalle de recherche nécessaire et de calcul d'un coefficient de corrélation. Un tel procédé est par exemple décrit dans l'article de Ayache mentionné ci-dessus, sous la rubrique 3.5. Toutefois, pour obtenir une certitude élevée sur la disparité attribuée au premier pixel germe, il est préférable d'adopter un critère plus sûr que la simple recherche d'un pic de la fonction dintercorrélation. En particulier, on peut ne retenir un pixel comme germe, avec une disparité D, que si: - le maximum de coefficient dintercorrélation Cl pour D est supérieur à un seuil prédéterminé S (figure 4), et - l'amplitude relative par rapport au second pic (C1- C2)/C1 est également supérieure à un seuil. La collecte des prédictions, pour un pixel non encore traité, est effectuée à partir de tous les voisins de ce pixel qui ont une disparité déjà attribuée, appartenant donc au germe. Par exemple, on disposera, pour le pixel P de la figure 3A, de deux disparités prédites si les disparités sont déjà attribuées, dans son voisinage, aux pixels 4 et 5. Le calcul des coefficients d'intercorrélation pour le pixel P ne se fera alors qu'autour de chaque disparité prédite, dans un intervalle de recherche qui peut être beaucoup plus limité que dans le cas des procédés tradition- nels. L'intervalle de recherche peut par exemple être limité à: [disparité prédite - seuil de discontinuité - 1; disparité prédite + seuil de discontinuité + 1]. Le seuil de discontinuité est choisi à priori. Il joue deux fonctions. D'une part, un pixel ne sera traité que si les disparités attribuées à partir des disparités des pixels voisins ne diffèrent pas de plus du seuil de discontinuité. D'autre part, il définit l'intervalle de recherche, les décalages de un pixel permettant de détecter un maximum même au bord de l'intervalle de recherche. La disparité retenue pour le pixel traité est celle qui donne le pic de corrélation le plus élevé, parmi les pics de corrélation obtenus pour les intervalles de recherche associés aux diverses prédictions. Le résultat est validé (critère 3) uniquement si le coefficient dintercorrélation pour la disparité retenue est supérieur à un seuil. Dans l'affirmative, le pixel traité est intégré au germe et sera donc utilisé pour poursuivre la propagation. Enfin, le traitement sera repris sur les pixels du nouveau voisinage. Les valeurs numériques du seuil de corrélation pour la recherche d'un pixel germe, du seuil sur l'amplitude relative du second pic, du seuil de discontinuité et du seuil de corrélation pour la propagation seront choisis en fonction de la nature de la scène. A titre d'exemple, une scène comportant un seul bâtiment de grande taille a été traité par un processus classique de stéréovision dense, avec un intervalle de recherche sur la disparité de - 10 à + 10 pixels et par le procédé suivant l'invention. Dans cet exemple, le processus classique exige un calcul systématique de vingt et une corrélations par pixel; le procédé suivant l'invention permet de ne calculer que trois coefficients dintercorrélation, en vue de la vérification d'un maximum local, pour la grande majorité des points. Du fait que le procédé utilise la cohérence bidimen- sionnelle, on élimine les stries. [11 Le procédé qui vient d'être décrit fait l'hypothèse d'une continuité de la disparité dans des domaines importants et permet de prédire les résultats au bord du germe en cours de croissance. Pour affiner la position du pic de corrélation, il est possible de propager non seulement l'information de disparité, mais aussi la valeur de ses dérivées premières en x et en y, voire même la valeur des dérivées secondes. Le recalage de la valeur prédite par recherche du maximum le plus proche de la courbe de corrélation en fonction de la disparité est alors complété par le recalage des dérivées en x et en y. Cette approche présente notamment un intérêt dans le cas de zones à fort relief. Les dérivées de la disparité peuvent être calculées par un processus similaire à celui décrit dans la thèse de doctorat de l'école polytechnique de F. Devernay "Vision stéréoscopique et propriétés différentielles des surfaces", février 1997. Une première approche consiste à effectuer une régression bilinéaire sur l'ensemble des disparités déjà calculées situées dans un voisinage de taille constante d'un point de la carte de disparité. On affecte alors aux dérivées de la disparité des valeurs égales aux coefficients de la régres- sion. Une seconde approche consiste à calculer les dérivées premières de la disparité directement à partir d'une paire d'images stéréoscopiques. Les dérivées sont alors assimilées aux paramètres d'un élément d'une des images déformées pour obtenir le maximum du coefficient de corrélation entre les deux régions des images. Cette dernière approche est décrite dans la thèse de F. Devernay en pages 60 à 62. REVENDICATIONS 1. Procédé de production de données cartographiques caractérisant des pixels d'au moins une image numérique, suivant lequel (a) on sélectionne un pixel germe, auquel est affectée une donnée cartographique connue ou déterminée de façon sûre; (b) on affecte, à chaque pixel d'un voisinage prédéterminé en deux dimensions centré sur le pixel germe, une donnée cartographique prédite constituée par la valeur cartographi- que du pixel germe; (c) on applique, à chaque pixel du voisinage, un critère de validité de la donnée prédite et on retient ce pixel en tant que pixel germe additionnel, avec la valeur cartographique prédite, éventuellement ajustée, si le critère est rempli; et (d) on poursuit la croissance de façon bidimensionnelle, en effectuant de plus un contrôle de cohésion entre les valeurs prédites dans le cas d'un pixel appartenant aux voisinages de plusieurs pixels germes. 2. Procédé de stéréovision selon la revendication 1, caractérisé en ce que l'étape (c) comprend, une fois le germe constitué de plusieurs pixels, le calcul d'un coefficient dintercorrélation en fonction de la disparité, uniquement dans un domaine étroit autour de la disparité prédite à partir de chaque pixel voisin du germe. 3. Procédé selon la revendication 2, caractérisé en ce qu'on effectue plusieurs recherches à partir des disparités prédites à partir de plusieurs pixels germes du voisinage différant entre elles d'une quantité inférieure à un seuil de discontinuité prédéterminé. 4. Procédé selon la revendication 3, caractérisé en ce que la recherche en cours de l'étape (c) est effectuée le long d'une épipolaire dans un intervalle égal à: [disparité prédite - seuil de discontinuité - 1; disparité prédite + seuil de discontinuité + 1]. 5. Procédé selon la revendication 2, 3 ou 4, caractérisé en ce qu'on retient un pixel comme pixel germe avec une disparité D lorsque: - le maximum de coefficient d'intercorrélation Cl pour D est supérieur à un seuil prédéterminé S (figure 4), et - l'amplitude relative par rapport au second pic (C1- C2)/C1 est également supérieure à un seuil prédéterminé. 6. Procédé suivant l'une quelconque des revendications 2 à 5, caractérisé en ce qu'au cours de l'étape (d) on propage, en plus de l'information de disparité, mais aussi la valeur de ses dérivées en x et en y. 7. Procédé de production de données cartographiques en stéréovision dense, les données étant constituées par la disparité, de chaque pixel entre les deux images d'un couple dimages stéréographiques, suivant lequel, (a) une fois constitué un germe formé de plusieurs pixels, (b) on affecte, à chaque pixel à traiter appartenant au voisinage de plusieurs pixels d'un germe de disparités connues, plusieurs disparités prédites constituées par les disparités de chaque pixel germe voisin, (c) on applique, au pixel à traiter, un même critère de validité de chaque disparité prédite à partir d'un pixel germe voisin, sous forme d'un calcul dintercorrélation autour de la disparité donnée par la prédiction et dans un intervalle de discontinuité prédéterminé et on retient celle des disparités prédites qui donne le pic de corrélation le plus élevé, dans la mesure o le coefficient d'intercorréla- tion du pic dépasse un seuil prédéterminé; et (d) on intègre le pixel traité au germe si la proposition d'intercorrélation est supérieure au seuil, puis on poursuit la croissance de façon bidimensionnelle.