FR 2894355 A1 20070608 FR 0512359 A 20051206 Procédé de mise en correspondance d'images stéréoscopiques La présente invention se rapporte au domaine de l'analyse et du traitement des images stéréoscopiques. Plus précisément, l'invention a pour objet un procédé de mise en correspondance de points analogues d'une première image et d'une seconde image, les première et seconde images formant deux images stéréoscopiques. Ce type de procédé de mise en correspondance de points analogues est connu en soi et consiste par exemple, à partir de deux images issues de deux caméras distinctes à déterminer les positions dans chaque image de caméra, des points correspondant à la projection d'un même point physique dans l'espace à trois dimensions. Il peut également être utilisé pour déterminer le déplacement d'une caméra ayant acquis deux images successives. Dans ce cas, si l'on arrive à déterminer qu'un point de la première image correspond au même point physique en trois dimensions qu'un autre point de la seconde image, on pourra déterminer le déplacement de la caméra à partir de la position des deux points dans le champ. De façon générale, deux points de deux images stéréoscopiques correspondant au même point physique en trois dimensions seront appelés points analogues. La publication IEEE Transactions on pattern analysis and machine intelligence (BROWN, BURSCKA, HAGER, VOL.30 25, N 8, Août 2003) propose une revue des différentes méthodes connues de mise en correspondance de deux images stéréoscopiques. Ces méthodes comprennent par exemple la mise en correspondance de blocs d'images (ou block matching en langue anglaise), l'optimisation de gradients (ou gradient-based optimization en langue anglaise), ou la mise en correspondance d'éléments (ou feature matching en langue anglaise). Cependant, la fiabilité de ces méthodes de mise en correspondance est parfois insuffisante et les occurrences de mises en correspondance erronées faussent les reconstructions tridimensionnelles subséquentes. Un des objets de la présente invention est donc de trouver une alternative aux méthodes de mise en correspondance entre images stéréoscopiques connues. Il existe par ailleurs des méthodes de mise en correspondance basées sur les distances entre les points mis en correspondance pour localiser un mobile par rapport à un objet cible. L'inconvénient de ces méthodes basées sur la distance est que les points positionnés dans la scène réelle à des profondeurs différentes ne bougent pas à la même vitesse apparente dans les images de ladite scène. De fait les distances entre les points homologues correspondant à un même point 3D dans les images de la scène réelle sont différentes selon la profondeur de ce point. On ne peut donc juger de la fiabilité des appariements sur des points homologues correspondant à des points 3D de profondeurs différentes en se basant uniquement sur la distance les séparant. Un autre objet de la présente invention est donc de fournir une méthode qui prenne en compte la profondeur des objets d'une scène de référence. Par ailleurs, plusieurs méthodes de mise en correspondance nécessitent des temps de calcul trop longs pour être exploitables rapidement, par exemple dans le cadre d'un robot muni de deux caméras, et cherchant à s'orienter dans l'espace. Un autre objet de la présente invention est donc de fournir une méthode de mise en correspondance qui soit rapide. A cet effet, la présente invention se rapporte à un 15 procédé de mise en correspondance de points analogues d'une première image et d'une seconde image, les premières et secondes images formant deux images stéréoscopiques, et elle est caractérisée en ce qu'elle comporte des étapes consistant à : qu'il comprend des étapes consistant à : 20 -Sélectionner dans ladite première image, une première liste de points d'analyse ([Al, A2, ... An]) ; - Sélectionner dans ladite seconde image, une seconde liste de points d'analyse ([Bl, B2, ... Bpi); - Calculer les angles relatifs (Op, ; Ostuv) entre les 25 droites joignant les points d'un premier ensemble de paires de points d'analyse et les droites joignant les points d'un second ensemble de paires de points d'analyse, lesdites paires appartenant à au moins une partie (C,C') de l'ensemble (C) des paires de points d'analyse ([(Ai,Bk)], j=1,n, k=1,p), le premier 30 élément desdites paires de points dudit ensemble (C) appartenant à ladite première liste et le second élément desdites paires de points dudit ensemble (C) appartenant à ladite seconde liste ; 10 - Sélectionner en tant que paires de points analogues, parmi ladite au moins une partie (C, C') dudit ensemble (C), les paires ([(Ai,Bk)]) correspondant aux angles (Om) ayant une répartition majoritaire. De préférence, ladite au moins une partie (C, C') de l'ensemble (C) des paires de points d'analyse est choisie en fonction de contraintes de déplacement relatives aux paires de points d'analyse dudit ensemble (C). Ces contraintes sont par exemple choisies de sorte à assurer l'unicité desdites paires de points. Elle peuvent dépendre d'au moins un paramètre choisi parmi la distance, la luminosité, l'ordre et la stabilité pyramidale. Grâce à ce procédé et au critère d'orientation purement statistique utilisé, on met en correspondance deux images, par exemple dans le cadre d'une reconstruction spatiale 3D. L'invention a également pour objet un programme d'ordinateur comprenant un ensemble d'instructions pour l'exécution du procédé tel que précédemment décrit, ainsi qu'un médium d'enregistrement pour enregistrer de telles instructions. L'invention est particulièrement adaptée lorsque les dispositifs d'acquisition de la première image et de la seconde image ont des axes optiques sensiblement parallèles. D'autres aspects, buts et avantages de l'invention apparaîtront à la lecture de la description détaillée de l'invention.30 L'invention sera également mieux comprise à l'aide des dessins sur lesquels : La figure 1 est une vue générale d'un environnement d'application du procédé selon la présente invention ; La figure 2 illustre un exemple de mise en oeuvre du procédé selon l'invention ; La figure 3 illustre un exemple d'histogramme pour la mise en correspondance selon la présente invention. - La figure 4 illustre un exemple de définition des paires de points définissant des droites pour l'obtention d'un histogramme des orientations selon la présente invention. La figure 5 représente l'histogramme des orientations associé à la figure 4. - La figure 6 illustre un exemple d'application des contraintes dans le cadre du procédé selon la présente invention. Sur les différentes figures, les mêmes références désignent des éléments identiques ou similaires. L'extraction d'informations de positionnement et/ou d'orientation d'un objet est par exemple applicable dans le cadre de la localisation d'un véhicule mobile ou d'un bras de robot équipé de caméras par rapport à son environnement. La figure 1 représente un tel environnement dans lequel peut être mise en oeuvre l'invention. Sur cette figure, un robot mobile 1 est équipé de 30 caméras 2A, 2B et doit se localiser dans son environnement contenant ici un objet cylindrique 3. Le système de caméras 2A, 25 2B du robot est relié par liaison filaire ou sans fil à un ordinateur 5 effectuant l'acquisition et le traitement des images. Le système de caméras 2 permet l'acquisition d'un couple d'images de l'environnement situé devant lui. Ces images 4D, 4G de l'environnement comprennent notamment une image de l'objet 3. Dans le cadre de l'analyse d'images stéréoscopiques, les deux images 4D et 4G possèdent au moins une partie commune, ici l'objet 3. Selon l'invention, on commence par sélectionner un certain nombre de points d'intérêt sur l'une des irnages 4D ou 4G, par exemple ici 4D. Des techniques connues de sélection de points d'intérêt sont les détecteurs de Moravec, les détecteurs de Harris et Stephens, et le filtre SUSAN. Ces méthodes de sélection de points utilisent souvent une analyse de l'image 4D permettant de distinguer leurs singularités, comme les limites des éléments qu'elles représentent, d'après les variations brusques de luminosité d'un point d'une image à un autre. NI faut remarquer que la sélection des points ne dépend pas de l'opérateur mais du programme seul et qu'elle reste inconnue de l'opérateur ; toutefois, l'opérateur peut limiter la sélection des points de l'image 4D aux régions comprenant l'image d'un objet particulier 3 et ses alentours, en spécifiant par exemple un cadre hors lequel les points sélectionnés sont écartés. On va ensuite soit sélectionner un certain nombre de points d'intérêt sur l'autre image, ici 4G, à l'aide de la même technique que pour l'image 4D ; soit déduire des points détectés dans l'image 4D des points potentiellement homologues dans l'image 4G par des techniques dites de tracking ou pyramidales qui recherchent les points de 4G possédant des caractéristiques d'invariance similaires à ceux de 4D successivement stables et robustes dans plusieurs sous parties de 4G. Les points sélectionnés finalement dans l'image 4D sont notés par la lettre A suivie d'un indice numérique et ceux sélectionnés dans l'image 4G sont notés par la lettre B suivie d'un indice numérique. Les points d'analyse sélectionnés sont donc les points (Al, A2, ..., An) dans l'image 4D, et les points (B1, B2, ..., Bp) dans l'image 4G. Aux fins de l'explication, on représente dans un même repère, en superposition les images 4D et 4G de l'objet 3. Après cette étape de sélection des points, selon 15 l'invention, on recense les orientations des droites (Ai Bk). Comme illustré figure 2, ces orientations peuvent correspondre à l'angle entre une droite de référence D, par exemple horizontale, et la droite passant par les points d'analyse 20 (Aj Bk). Cet angle sera alors noté Ojk. Elles peuvent également correspondre à l'angle entre les droites passant par une première paire de points (As,Bt) et une seconde paire de point (Au,Bä), cette seconde paire de points 25 (AU,Bä) étant distincte de première paire de points (As,Bt). Dans ce cas, l'angle sera noté estuv. Il est entendu que les orientations relatives entre les droites passant par différentes paires de points peuvent aussi 30 bien être mesurées par rapport à une droite de référence et à la variable 6jk, que par rapport aux angles esta,. On observera à ce titre que le premier cas n'est qu'un cas particulier du deuxième dans lequel l'une des droites est toujours la même et est supposée passer par deux points (Ao,Bo) quelconques des images 4D et 4G respectivement. L'orientation relative entre des paires de points des deux images peut également être calculé par rapport à la droite passant par les projections calculées ou supposées des centres optiques des caméras dans les images. Dans toute la suite de la description, on n'utilisera que les variables Oak, définies par rapport à une droite de référence. De façon générale, l'angle d'une paire de points 15 correspond ainsi à l'angle entre la droite définie par ladite paire de point, et une droite de référence. Selon un premier mode de mise en oeuvre de l'invention, tous les points A et tous les points B sont ainsi 20 appariés par une orientation. Pour des points d'analyse (AI, A2, ..., An) dans l'image 4D et (BI, B2, ., Bp) dans l'image 4G, n.p couples sont donc formés dans un ensemble de couple C...DTD: Les orientations ejk entre tous les points A et tous les 25 points B dans les limites d'exhaustivité calculées sont ensuite recensées et celles dont les valeurs sont presque semblables ou presque semblables à l'orientation de la droite passant par les centres optiques des deux images 4D et 4G sont regroupées. On cherche alors la valeur em d'orientation non nulle la plus fréquente 30 fmax pour les 00, dans une tolérance X. Ceci est par exemple réalisable par analyse statistique d'un histogramme tel qu'illustré figure 3. Comme illustré sur cette figure, on sélectionne par tous 10 les angles dans l'intervalle em ù X/2, em + X/2. Cette orientation la plus fréquente em représente alors celle du déplacement de l'image de l'objet 5 entre les deux images 4D et 4G. Ainsi, si un angle ejk correspondant à la répartition angulaire majoritaire et est donc compris entre em ù X/2, em + X/2, on sélectionne la paire (Ai,Bk) comme une paire de points analogues dans les deux images stéréoscopiques. 10 De la même façon, si un angle absolu Ostuv correspondant à l'angle entre les droites passant par les paires (As,Bt) et (Au,Bä) correspondant à la répartition angulaire majoritaire et est donc compris entre em ù X/2, em + X/2, on sélectionne les paires (As,Bt) et (Au,Bä) comme paires de points 15 analogues dans les deux images stéréoscopiques. Selon l'invention, le critère d'orientation non nulle la plus fréquente (ou du maximum d'orientations sensiblement identiques), est donc utilisé comme critère purement statistique 20 de détermination du déplacement de l'image de l'objet. Ce procédé est particulièrement applicable dans le cas d'un système monoculaire où le déplacement de la caméra entre les images 4D et 4G est une translation horizontale et/ou 25 verticale, et, dans le cas d'un système de plusieurs caméras dans lequel les axes optiques de ces caméras sont parallèles et les caméras sont rigidement fixées. Dans ces conditions, l'amplitude des déplacements (ou les distances) des images des objets de l'environnement varient en fonction de l'éloignement desdits 30 objets par rapports au système de caméras, mais l'orientation et la direction du déplacement restent les mêmes.5 Selon une variante de l'invention, une fois n.p couples formés dans l'ensemble C, on élimine les paires de points selon des contraintes prédéfinies permettant de garantir l'unicité d'appariement de chaque point homologue. On ne retient par exemple que les orientations compatibles avec une contrainte de déplacement associée à un couple (Ar,Bs) reflétant par rs exemple le déplacement entre l'acquisition successive de deux paires d'images. Cette contrainte peut être estimée à l'aide d'un capteur annexe de type centrale inertielle. On peut également sélectionner les couples de points des figures 4G et 4D selon une contrainte de ressemblance des points des deux images qui dépend des luminosités relatives des points Ai et Bk dans leurs voisinages respectifs. Dans ce cas, on ne cherche à apparier à un point A que les points B présentant des luminosités propres et des luminosités de voisinage similaires dans toutes les directions. Suite à l'élimination d'un certain nombre de paires de points, le procédé d'analyse statistique sur les orientations est alors mis en oeuvre comme décrit précédemment. Dans le cas de contraintes sur les déplacements rs, l'utilisation de coordonnées polaires pour estimer les orientations des droites passant par les couples de points et les déplacements permet ainsi de faire successivement une sélection d'après les angles jk des déplacements jk sur les images, puis une autre sélection d'après les valeurs de jk. Ce type d'élimination des paires de points correspond à un filtrage préliminaire avant l'étape d'analyse statistique. Ce filtrage possède l'avantage d'accélérer le temps de traitement statistique en fonction des orientations sur les couples restants et de garantir l'unicité d'appariement de chaque pont homologue. Cette étape de filtrage peut être soit réalisée suite au calcul de l'ensemble C correspondant à toutes les paires possibles associées aux listes A et B, ou bien lors de la formation de ces paires, en testant, pour chaque paire candidate, si les contraintes sont respectées, et en ne retenant que les paires respectant les contraintes. Dans ce dernier cas, l'ensemble C' des paires obtenues correspond à un sous-ensemble de l'ensemble C et tient compte directement des contraintes sur les paires de points des images 4D et 4G. Illustré figures 4 et 5, on fournit un exemple d'obtention d'un histogramme des orientations selon la présente invention à partir de deux images stéréographiques. Sur cette figure, l'objet 3 correspond à un segment de droite. Les points d'analyse sont d'une part les points BI, B2, B3, les points B1 et B3 délimitant le segment de droite, et le point B2 étant au milieu du segment, et les points Al, A2, A3, les points Al et A3 délimitant le segment de droite, et le point A2 étant au milieu du segment. Il semble évident que les paires de points analogues sont les paires (A1, B1), (A2, B2), (A3,B3). Le procédé selon l'invention confirme cette conclusion. En effet, on construit les 9 droites passant d'une part par l'ensemble des points (B1,B2,B3) et d'autre part par l'ensemble des points (Al,A2,A3). Sur la figure 4, toutes les droites de même orientation relatives portent alors le même nom. On dénombre ensuite les droites de même orientation et donc de même nom sur l'histogramme la figure 5. Il y a 3 droites Do, 2 droites DI, 2 droites D_1, 1 droite D2, et une droite 112. Selon l'invention, les paires de points correspondant aux droites Do sont donc des points analogues. Selon l'invention, on sélectionne donc les paires (A1, B1), (A2, B2) et (A3, B3) comme paires de points analogues, ce qui confirme l'analyse intuitive réalisée précédemment. La FIG. 6 illustre un exemple d'application de contraintes de déplacement dans le cadre de la présente invention. Sur cette figure, les droites (B1, Al), (B'1, Al), (B1, A'1) et (B'1, Al), définissent un angle identiques, par exemple par rapport à une droite horizontale de référence. Selon l'invention, on compare alors les distances B1A1, B'1A1, B1A'1, et B'1A'1. La répartition maximale de distance correspond aux couples (BI, Al) et (B'1, Al), et ce sont donc ces couples qui seront retenus en tant que paires de points analogues. 20 Le procédé selon la présente invention est applicable dans le cadre de la localisation d'un véhicule mobile ou d'un bras de robot équipé de caméras par rapport à son environnement. Pour cela, on utilise par exemple deux caméras montées sur le véhicule 25 mobile qui prennent des images de leur environnement et éventuellement d'un objet à atteindre au cours du déplacement du véhicule. On peut aussi utiliser une seule caméra qui prend successivement des images décalées latéralement. Un ordinateur est utilisé pour localiser les caméras par rapport à leur 30 environnement à partir des images stéréoscopiques prises par les caméras. Ces informations de localisation peuvent être recalculées et enrichies à mesure que les caméras se déplacent et que de 15 nouvelles acquisitions sont considérées. L'obtention des paramètres de localisation à partir d'images stéréoscopiques passe par les étapes suivantes : - une première étape de calibration des caméras et/ou des images, pouvant être connue en soi ; - une étape de mise en correspondance selon la présente invention ; une étape de reconstruction spatiale 3D pouvant être connue en soi, connaissant les paramètres de triangulation des images stéréo et le grossissement des caméras.15 REVENDICATIONS , 1. Procédé de mise en correspondance de points analogues d'une première image et d'une seconde image, les 5 premières et secondes images formant deux images stéréoscopiques caractérisé en ce qu'il comprend des étapes consistant à : - Sélectionner dans ladite première image, une première liste de points d'analyse ([Al, A2, ... An]) ; - Sélectionner dans ladite seconde image, une seconde liste de points d'analyse ([B1, B2, . Br]); -Calculer les angles relatifs (0jk ; Ostuv) entre les droites joignant les points d'un premier ensemble de paires de points d'analyse et les droites joignant les points d'un second 15 ensemble de paires de points d'analyse, lesdites paires appartenant à au moins une partie (C,C') de l'ensemble (C) des paires de points d'analyse ([(Ai,Bk)], j=1,n, k=1,p), le premier élément desdites paires de points dudit ensemble (C) appartenant à ladite première liste et le second élément desdites paires de 20 points dudit ensemble (C) appartenant à ladite seconde liste ; Sélectionner en tant que paires de points analogues, parmi ladite au moins une partie (C, C') dudit ensemble (C), les paires ([(Ai,Bk)]) correspondant aux angles (0m) ayant une répartition majoritaire. 25.. CLMF: 2. Procédé de mise en correspondance d'une première image et d'une seconde image selon la revendication 1, dans lequel ladite au moins une partie (C, C') de l'ensemble (C) des paires de points d'analyse est choisie en fonction de 30 contraintes de déplacement relatives aux paires de points d'analyse dudit ensemble (C). 10 10 15 20 3. Procédé de mise en correspondance d'une première image et d'une seconde image selon la revendication 2 dans lequel lesdites contraintes sont choisies de sorte à assurer l'unicité desdites paires de points. 4. Procédé de mise en correspondance d'une première image et d'une seconde image selon la revendication 2 dans lequel lesdites contraintes dépendent d'au moins un paramètre choisi parmi la distance, la luminosité, l'ordre et la stabilité pyramidale. 5. Procédé de mise en correspondance d'une première image et d'une seconde image selon la revendication 1, dans lequel lesdits angles relatifs sont calculés par rapport à une droite de référence. 6. Programme d'ordinateur comprenant un ensemble d'instruction pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 5. 7. Médium d'enregistrement de données numériques lisible par ordinateur, sur lequel sont enregistrées des instructions pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 5. 25