FR 2767404 A1 19990219 FR 9710284 A 19970812 PROCEDE DE PRODUCTION DE DONNEES CARTOGRAPHIQUES PAR STEREOVISION La présente invention concerne les procédés de produc- tion de données cartographiques en trois dimensions à partir de n images à deux dimensions d'une scène, fournies par n capteurs ayant des points de vue différents de la scène. On sait depuis très longtemps définir la postion dans l'espace de structures présentes dans une scène et visibles dans deux images prises sous différents angles de vue, par des techniques stéréoscopiques. Ce procédé a été généralisé au cas de n images, n étant un entier supérieur à 2, ces n images constituant un système stéréoscopique à plusieurs lignes de base. On connaît notamment des procédés comportant les étapes suivantes: - on calibre les n capteurs (en utilisant la connais- sance 3D de leur position relative par rapport à la scène observée et/ou des procédés de reconnaissance de formes, de façon à disposer des paramètres de n modèles Fi.(x,y,z) définissant chacun la relation entre un point de la scène, de coordonnées x,y,z, et les coordonnées (p,q)i de sa projection dans chacune des n images, pour i allant de 1 à n; - on met en correspondance les n images, de facon à localiser dans les images les coordonnées de la projecion d'un même point dans l'espace à trois dimensions; - on effectue une reconstruction 3D, consistant à obtenir les coordonnées x,y et z du point 3D correspondant à chaque appariement entre images, à partir de la connais- sance des modèles Fi et des points images appariés. Un procédé de ce genre est décrit dans l'article de Sing Bing Kang et al. "A Multibaseline Stereo System with Active Illumination and Real-Time Image Acquisition", Proceedings IEEE Int. Conf. on Computer Vision, pages 88-93, juin 1995. Le procédé proposé dans cet article met en oeuvre quatre caméras dont les axes optiques convergent approximativement en un même point. L'image fournie par une des caméras est choisie comme référence. Etant donné que les axes des caméras ne sont pas parallèles, les lignes épipolaires associées ne sont pas parallèles aux lignes des images. Pour simplifier la restitution de l'altitude à partir des images stéréoscopiques, c'est-à-dire la reconstruction 3D, les images sont soumises à une rectification qui transforme chaque paire d'images d'origine en une autre paire telle que les lignes épipolaires qui en résultent soient parallèles, égales et confondues avec les lignes des images. Le mode de mise en correspondance utilise une variable A, définie comme la distance au centre optique, suivant l'axe de visée passant par le centre optique de la caméra de référence et le point considéré, pour calculer la zone de recherche d'homologues potentiels dans les images à apparier à l'image de référence. L'utilisation de cette variable) conduit inévitablement à un modèle de passage non linéaire entre les images, ce qui complique les calculs. La stratégie enseignée par l'article, consistant à affecter une importance égale à chaque couple, est source d'erreur chaque fois que des points sont masqués dans une ou plusieurs des images. Une étude détaillée d'algorithmes de fusion de plusieurs représentations pour restituer des données cartographiques 3D à partir de plusieurs images 2D d'une scène est donnée dans la thèse de l'Université de Paris Sud, Centre d'Orsay, Mai 1988 "Construction et Fusion de Représentations Visuel- les 3D: Applications à la Robotique Mobile" de N. Ayache. 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 facilite la mise en correspondance multi-couples de n images (n étant un entier supérieur à 2) et est suffisamment souple pour s'adapter sans difficulté à de nombreux domaines, tels que: - la détection d'obstacles et le guidage autonome d'un robot mobile, dans une scène fixe, - la modélisation 3D de sites réels, la cartographie, - la reconnaissance aérienne, permettant d'obtenir un profil de terrain, - la modélisation de trajectoires optimales, lors de la préparation d'une mission aérienne. Pour cela, le procédé utilise notamment la constatation que, quelle que soit la nature des capteurs (sténopé, barrette de sites photodétecteurs, capteur à balayage) et leur position relative au moment de l'acquisition des images (à condition qu'elles soient stéréoscopiques et qu'il y ait un recouvrement entre plusieurs images) on peut toujours exprimer les n-l courbes de ressemblance, correspondant chacune à un couple d'images dont une image de référence unique, en fonction de la disparité, définie dans un couple quelconque. Pour cela, on effectue un changement de référen- tiel des courbes de ressemblance, qui peut toujours être réalisé par un modèle affine de passage de la disparité d'un couple à celle d'un autre couple. La disparité pourra en général être assimilée à l'ab- cisse curviligne d'un point par rapport à un autre le long de l'épipolaire; elle peut être mesurée en pixels dans le cas fréquent d'une image représentée par des points élémen- taires affectés chacun d'au moins une valeur radiométrique (luminance et/ou chrominance). L'invention propose notamment un procédé de production de données cartographiques en trois dimensions à partir de U images à deux dimensions de la scène, fournies par n capteurs avec des points de vue différents, n étant un entier supérieur à 2, suivant lequel: (a) on calibre chaque capteur d'ordre i pour estimer les paramètres des n modèles Fi(x,y,z) définissant la relation entre les coordonnees x,y,z d'un point de la scène et les coordonnées (pq)i de sa projec- tion dans l'image i parmi les n images; (b) on met en correspondance chacun des n-1 couples d'images comportant toutes une même image de référence choisie parmi les r images, en recherchant l'homologue de chaque pixel ou zone de l'image de référence le long de l'épipolaire correspondante de l'autre image du couple; (c) dans chacun des n-1 couples de deux images compre- nant chacune une image de référence et pour chaque pixel ou zone de l'image de référence, on établit une courbe de ressemblance (courbe de variation d'un indice de similarité) en fonction de la disparité, le long de l'épipolaire de l'autre image; (d) on ramène toutes les courbes dans un référentiel commun, par un modèle par exemple affine, pour appa- rier le plus grand nombre possible d'images; (e) on effectue la sommation des courbes, en écartant éventuellement chaque pic situé à une disparité singulière par rapport à celui de toutes les autres courbes et on retient le pic le plus élevé de la courbe résultante; et (f) on calcule les coordonnées x,y,z à partir de la disparité du pic retenu et des paramètres des n modèles Fi(x,y,z). Il est également possible de calculer plusieurs images de disparité en prenant différentes images comme référence. La fusion peut s'effectuer après calcul des coordonnées en trois dimensions; elle peut aussi s'effectuer au niveau des images de disparité, ce qui est une solution avantageuse lorsque les capteurs sont calibrés dans un espace projectif. La fusion des résultats de mise en correspondance multi- couples peut être réalisée à l'aide d'un vote majoritaire, en affectant un coefficient de pondération plus élevé aux pics correspondant aux points de vue les plus distants de l'image de référence. Le procédé qui vient d'être décrit permet d'écarter dans la plupart des cas les difficultés rencontrées pour trouver à coup sûr l'homologue d'un point de l'image dans une ou plusieurs autres images. L'utilisation d'un nombre n supé- rieur à 2 permet d'écarter les conséquences d'une occulta- tion dans une ou plusieurs images. La cohérence géométrique des appariements multiples réduit les erreurs et lève les ambiguïtés. La présence d'images ayant des points de vue proches permet de traiter des images ressemblantes ayant peu d'occultation entre elles; l'utilisation d'images ayant des points de vue distants permet d'obtenir une information 3D précise. 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 de l'invention, donnés à titre d'exemple non limitatif. La description se réfère aux dessins qui l'accompagnent, dans lesquels: - la figure 1 est un schéma représentant une disposition possible des capteurs et montrant le rôle de la rectifica- tion; - la figure 2 montre le principe des appariements d'un point par recherche sur des portions d'épipolaire; - la figure 3 montre des exemples de courbes de varia- tion d'un indice de ressemblance en fonction de la dispari- té; - la figure 4 représente un exemple de schéma d'exploi- tation des images dans le cadre de l'appariement multi- images; - la figure 5 montre un procédé de fusion des traite- ments multi-images; - la figure 6 montre un mode de mise en référence de courbes de ressemblance par rapport à un plan; et - les figures 7A et 7B, qui montrent des courbes de ressemblance en fonction de la disparité, montrent l'intérêt d'une sélection des courbes. On décrira tout d'abord l'architecture générale du procédé, qui est conservée quelle que soit l'application, s avant d'envisager des cas particuliers. Pour simplifier, les parties déjà bien connues du procédé suivant l'invention ne seront que brièvement rappelées et on pourra se reporter aux documents déjà mentionnés ainsi que: - en ce qui concerne le cas simple de capteurs de type sténopé, tous identiques, fournissant des images acquises dans des positions coplanaires, à la même altitude, à l'article de R.Y. Tsai "Multiframe Image Point Matching and 3-D Surface Reconstruction" IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-5, n 2, pages 159- 164, mars 1983; - en ce qui concerne la cartographie à partir de cartes d'images aériennes numériques calibrées, à l'article de L. Gabet et al. "Construction Automatique de Modèle Numéri- que de Terrain à Haute Résolution en Zone Urbaine", Bul. SFPT n 135, pages 9-25, 1994. Le procédé suivant l'invention comporte trois phases es- sentielles: - le calibrage des capteurs (étape (a) ci-dessus), - la mise en correspondance ou appariement des images, impliquant la fusion d'au moins n résultats de mise en correspondance multi-couples, ces résultats étant les cartes de disparité directement obtenues ou des modèles numériques d'élévation (MNE) calculés à partir de ces dernières, - la reconstruction 3D (étape (f)). Ces trois phases seront successivement décrites. Calibrage Le calibrage des capteurs a pour but de fournir une estimation des paramètres des modèles F1(x,y,z) et Fi(x,y,z) qui définissent la relation entre les coordonnées x,y,z d'un point 3D de la scène et les coordonnées 2D (p,q) de sa projection dans le plan image respectivement ni et ni. Le procédé exige une telle calibrage préalable des cap- teurs. Dans le cas simple de deux capteurs seulement, illustré en figure 1, le calibrage a pour but d'estimer les paramètres des modèles Fl (x,y, z) F2(xy, z) qui définissent la relation entre un point Sk de la scène, défini en trois dimensions par ses coordonnées x,y et z et les coordonnées (pq)i de sa projection dans le plan image si (avec i = 1 ou 2). Le calibrage est effectué différemment selon la nature des capteurs, par des procédés connus, comme par exemple celui décrit dans l'article de Ayache mentionné plus haut. On peut utiliser des correspondances entre des points homologues des images, définies manuellement ou obtenues par des techniques de reconnaissance de forme portant sur des voisinages. A l'issue de cette étape, on dispose de l'ensemble des modèles Fi(x,y,z) avec iE{l, .,n} et des directions de recherche des points correspondants, qui sont celles des épipolaires. Toutefois, lorsque le calibrage est réalisé sans connaissance initiale 3D de la scène, la reconstruction 3D ne peut être définie par les méthodes classiques qu'à une transformation projective près de l'espace projectif 3D. On verra plus loin que le procédé multi-couples suivant l'invention est indépendant de la géométrie et permet..DTD: d'appréhender les variations d'altitude dans la scène. Mise en correspondance multi-couples L'appariement des images s'effectue en recherchant l'homologue de chaque point P d'une image de référence, généralement défini avec son voisinage sous forme d'une vignette, le long des épipolaires E2,E-,... des autres images (figure 2). Pour cela, on établif des courbes de similarité en fonction de la disparité d1,d13,... (lignes A et B). L'indice de similarité S peut être notamment un coefficient d'inter-corrélation ou un indice de ressemblance sur des contours ou des régions. Toutes les courbes sont ensuite ramenées dans un référentiel commun, par exemple d13, qui fera apparaître un appariement probable avec une précision sub- pixélique correspondant à la coïncidence des pics (ligne C de la figure 3). Un changement de référentiel est nécessaire si on veut exprimer toutes les courbes dans un même référentiel en vue de leur fusion; il utilise un modèle affine élaboré en fonction de la géométrie d'acquisition des images. Ce modèle est de la forme, pour un exemple impliquant trois images en tout: d13 = a(q,p)d12 + b(n,ia) o d désigne la disparité, 9 et g désignent les paramètres qui définissent la géométrie des couples (1,2) et (1,3) pour une position p sur l'épipolaire de la primitive (point, contour ou région) à apparier dans l'image 1. Lorsque le calibrage est réalisé sans connaissance 3D de la scène, les coefficients a(9,u) et b(q,u) du modèle affine sont calculés en utilisant une rectification des images, destinée à transformer chaque paire d'images planes 2D en une autre paire telle que les lignes épipolaires soient parallèles et confondues avec les lignes ou les colonnes des images, comme indiqué sur la figure 1 o les épipolaires conjuguées rectifiées sont indiquées dans les plans réti- niens virtuels l,2 et r2,1 pour les points Ilk et I2k dans les plans image ni et n2. La rectification facilite la mise en correspondance en permettant d'établir immédiatement les courbes de la figure 3. A titre d'exemple, on peut indiquer que le modèle de passage (p,q) = Fi(x,yz) pour un modèle sténopé est, en coordonnées projectives, une fonction linéaire de la forme: = Px rsx avec u = et x = sy sz P est une matrice 3x4 définie à un lecteur multiplicatif près; w et s sont des facteurs multiplicatifs. Pour déterminer la matrice, 11 paramètres sont nécessaires. Ils peuvent être déterminés à condition de disposer d'au moins 6 points homologues. Si on considère uniquement deux images, on peut définir un modèle de passage d'un point 3D de la scène aux coordonnées de sa projection dans chacune des images rectifiées 1 et 2 ; les matrices de projection perspectives M et N pour l'image 1 et l'image 2 définissant les modèles de passage sont: u = M x = N x Pour calculer les coefficients des matrices M et N. à un facteur d'échelle près, il faut respecter diverses contrain- tes: - épipolaires parallèles dans les deux images (épipoles à l'infini); - pour un point 3D quelconque Sk n'appartenant pas au plan focal des caméras définis après rectification, ordon- 1,2 2,1 nées des pixels, représentés par les points Ik1'2 et Ik2'1, identiques (figure 1); - coordonnées des centres optiques C1 et C2 invariants pour la rectification. Les équations auxquelles conduisent ces contraintes sont données dans le document Ayache mentionné plus haut. Une solution à ces équations peut être trouvée de manière à limiter les distorsions des images rectifiées. A titre d'exemple, on donne les expressions suivantes pour les matrices M et N: a(t Acl a(t c2)T 0 M = e(cl^C2)T O N = (c^ c2)T 0 T T T T ((Ci-C2)A t) c(C2A^ t) ((cI -c2)A t) cl(c2A t) O: c1 et c2 sont les vecteurs des coordonnées 3D des centres optiques C1 et C2 des caméras à sténopé; " et P sont des facteurs d'échelle, conditionnant la déformation des images rectifiées dans la direction des épipolaires pour l'un et dans la direction orthogonale pour l'autre (si les épipolaires après rectification sont choisies horizontales). f est un vecteur imposant l'orientation du plan de rectifi- cation (permettant de limiter les distorsions des images rectifiées). La géométrie projective permet de calculer également les matrices M et N par l'intermédiaire des matrices fondamen- tales. On trouvera dans la thèse de l'Ecole Polytechnique "Vision stéréoscopique et propriétés différentielles des surfaces de F. Devernay la description d'une telle appro- che. Les matrices de passage des images réelles (ou acquises) aux images rectifiées peuvent se déduire des matrices M et N, par exemple de la manière indiquée dans le document Ayache. Il faut ensuite définir un modèle inter-disparité par ses coefficients a(,ui) et b( ,u1) tels que: d13(p) = a(T,,p).d12 + b(jp) Ce modèle fait passer de la disparité d12(p) du point p dans le couple des images rectifiées 1 et 2 à la disparité d13(p) dans le couple formé des images 1 et 3. 1 désigne le couple d'images (1,2) et p désigne le couple d'images (1,3). Les équations paramétriques des lignes de visée dans la caméra 1, définies à partir des coordonnées du pixel p dans l'image rectifiée dans la géométrie du couple n et dans la géométrie du couple p sont: C Icz +)t et x = c + Xgt o x désigne les coordonnées 3D d'un point cI (coordonnées du centre optique de la caméra 1) et tq et tu sont les vecteurs directeurs définis de façon simple en fonction des termes de la matrice M: nt = en(mll-pm3) ^(m2-q m3) t = A(ml-plmz) ^ (my-qn) o e désigne un coefficient de normalisation du vecteur t. On en déduit que l1 = Tp'- 1 avec p.T'1 = (t T.t)/t i Les expressions de a et b s'en déduisent directement a(rn,) =g k, On considèrera de nouveau le cas 'articulier et simple o les capteurs sont de type sténopé. L'appariement multi- couples peut s'effectuer par la démarche schématisée en figure 4, dans le cas de quatre images réelles, numérotées 1, 2, 3 et 4. Après rectification, un point P de l'image 1 pris comme référence sera recherché sur les épipolaires correspondantes des images 2, 3 et 4. En utilisant la notation montrée en figure 4, les appariements multi- couples sont réalisés entre les images gi et di, avec 1O iE{1,2,3} Les coefficients a et b du modèle affine du passage de la disparité d'un couple. à la disparité d'un autre couple peuvent s'exprimer simplement en fonction de la position du pixel P à apparier, de la géométrie du couple d'origine et de celle du couple de destination. Comme on l'a indiqué plus haut, on fusionne ensuite l'ensemble des appariements obtenus en prenant n différentes images comme référence (n=4 dans le cas de la figure 4). Cette opération peut s'effectuer après calcul des modèles numériques de terrain (MNT) ou d'élévation (MNE), comme indiqué en figure 5. Mais elle peut être effectuée par fusion des cartes de disparité, pour obtenir une carte de disparité finale, avant de déterminer le MNE final. De préférence, la fusion est réalisée sur le principe des votes majoritaires ou sélection d'une valeur médiane. Une pondération est utilisée au moment de la réalisation des votes. Elle est calculée en affectant un poids maximum aux points de vue les plus distants de l'i age de référence. Lorsque la géométrie des capteurs est connue (modèle sténopé, scanner, barrette) on donnera quelques indications sur un mode de mise en correspondance ou appariement dans le cas de deux images 1 et 2, l'image I étant l'image de référence. Les notations sont celles de la figure 6. La mise en référence prend en compte un plan à une altitude constante z=z0. Les fonctions Fi sont connues, et, dans le cas de modèles sténopés, reviennent aux matrices de projec- tion perpective Mi. On peut en consequence toujours exprimer les coordonnées (p,q) en 2D dans le plan E pour z=z0 à partir de deux pixels (pl,ql) et (p2,q2) mis en correspon- dance dans les images 1 et 2. Si (x1,y1) est le point du plan ú qui est l'image du pixel (p1,ql) à apparier de l'image 1, et (x2,y2) est l'image du pixel (p2,q2) de l'image 2, alors on définit la disparité associée à cet appariement potentiel comme la distance euclidienne dans ie plan E entre les points (xl,y1) et (x2,y2): d2(xl, yl) = Y (Xl -x2)2 + (Yi -y2)2 A partir de cette définition de la disparité, le calcul montre que l'on peut exprimer la disparité dans un couple d'images (1,2) sous la forme: 2 0 dl2(XI, yl) = I(an am)2 +(C -cm)2 (Zo - Z) o an, am, cn et cm sont des coefficients que l'on peut déduire des systèmes linéaires reliant, à z0 constant, p et q et le vecteur m défini plus haut dans chaque image. Dans le cas des images 1 et 3, on aurait, de façon similaire, une relation: d13(x, Yî) = j(ap-a)2 +(cp-cm)2 (Zo-Z) o ap et cp jouent le même rôle que an et cn. Le modèle linéaire de passage inter-disparité entre le couple n des images (1,2) et le couple D des images 1,3), lorsque le plan est spécifié, s'écrit très simplement sous la forme: d, 3(xi, y,) = a(l, l). d2(xl, y,) avec: a(, p)= J(ap-ar)2+ (C p-Cm)2 !(an - a m) +(C.-c) On peut ainsi établir, par un calcul qui pourra être fait en parallèle, toutes les courbes de similarité en vue de faire apparaître les pics qui se correspondent. Lors de l'appariement, il convient d'écarter les pics dus à une occultation de points dans une des images du couple. La figure 7B montre, à titre d'exemple, les courbes de ressemblance en fonction de la disparité pour quatre couples. Le pixel de l'image de référence est masqué sur l'autre image dans le couple 4, qui fait apparaître des pics pour des disparités o les autres courbes ne présentent pas de maximum. Dans ce cas, il conviendra d'écarter la courbe 4 pour trouver la disparité correcte pour le pixel masqué. Ce résultat peut notamment être obtenu par un vote majori- taire. REVENDICATI'NS 1. Procédé de production de données cartographiques en trois dimensions à partir de n images a ceux dimensions de la scène, fournies par n capteurs avec des points de vue différents, n étant un entier supérieur à 2, suivant lequel: (a) on calibre chaque capteur d'ordre i pour estimer les paramètres des n modèles Fi(x,y,z) définissant la relation entre les coordonnées x,y,z d'un point de la scène et les coordonnées (p,q)i de sa projec- tion dans l'image i parmi les n images; (b) on met en correspondance chacun des n-1 couples d'images comportant toutes une même image de réfé- rence choisie parmi les n images, en recherchant l'homologue de chaque pixel ou zone de l'image de référence le long de l'épipolaire correspondante de l'autre image du couple; (c) dans chacun des n-1 couples de deux images compre- nant chacune une image de référence et pour chaque pixel ou zone de l'image de référence, on établit une courbe de resserrmblance (courbe de variation d'un indice de similarité) en fonction de la disparité, le long de l'épipolaire de l'autre image; (d) on ramène toutes les courbes dans un référentiel commun, par un modèle par exemple affine, pour appa- rier le plus grand nombre possible d'images; (e) on effectue la sommnation des courbes, en écartant éventuellement chaque pic situé à une disparité singulière par rapport à celui de toutes les autres courbes et on retient le pic le plus élevé de la courbe résultante; et (f) on calcule les coordonnées x,y,z à partir de la disparité du pic retenu et des paramètres des n modèles Fi(x,y,z). 2. Procédé selon la revendication 1, caractérisé en ce que l'on effectue plusieurs appariements en prenant diffé- rentes images corrLe référence. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce qu'on fusionne les résultats de mise en correspondance multi-couples à l'aide d'un vote majoritaire, en affectant un coefficient de pondération plus élevé aux pics correspon- dant aux points de vue les plus distants de l'image de référence.