31

N° d'ordre 1053



Thèse




A présenter devant


L'Université de Rennes 1


Institut de Formation Supérieure en Informatique

et Communication





Pour obtenir


Le titre de Docteur de l'Université de Rennes 1


Mention INFORMATIQUE



par


Bernard COUAPEL




Titre de la thèse



Stéréovision par ordinateur

géométrie et expérimentation






Date de la soutenance: 11 Mars 1994



Composition du jury:


Président: Jean Pierre BANATRE

Rapporteurs: Roger MOHR

Olivier MONGA

Examinateurs: Jean CAMILLERAPP

François CHAUMETTE

Jean Pierre MASSON













Je tiens à remercier:


Jean Camillerapp professeur à L'INSA de Rennes de m'avoir permis d'entreprendre cette thèse et pour ses conseils pendant le déroulement de ce travail, ainsi que le Professeur Delmas du laboratoire des sciences du sol à l'INRA de Rennes pour le sujet qu'il m'a proposé,


Jean Pierre Banâtre directeur de l'IRISA d'avoir accepté de présider ce jury, et pour l'aide qu'il m'a apportée pendant mes études dans la réalisation de mes projets,


Les rapporteurs Roger Mohr, Professeur à l'IMAG de Grenoble et Olivier Monga de l'INRIA Roquencourt, d'avoir accepté la lourde tâche d'être rapporteurs et pour la qualité avec laquelle ils ont analysé mon travail,


Jean Pierre Masson et François Chaumette pour leur sympathie et leur soutien, ainsi que pour leur participation à ce jury.






Je remercie Luce Morin pour son aide et ses conseils lors des difficiles moments de cette fin de thèse ainsi que tous ceux et celles qui pendant ces quatre années m'ont entouré de leur sympathie, notamment mes étudiants et stagiaires, ainsi que mes collègues de travail qui ont dû supporter mes moments de découragement ou d'euphorie...


Cette période m'a permis de rencontrer de nombreuses personnes qui m'ont spontanément rendu service ou écouté, afin de me sortir d'une impasse ou simplement me permettre de verbaliser un problème. Je les remercie pour leur générosité et leur désintéressement. D'autres m'ont appris que la recherche n'est pas désincarnée et parfois loin des idéaux qu'on lui attache.


Je tiens ici à remercier tout particulièrement Monsieur Eugène Duclos, professeur de mathématiques, qui m'a offert sa grande compétence et son expérience en géométrie et sans qui une grande partie de mon travail serait restée à l'état de vagues élucubrations.






Enfin je dédie ce travail à mon père pour son dévouement permanent. Il m'a largement aidé à contrôler les dérapages dûs à un virage professionnel parfois difficile à négocier.








1. Introduction





L'analyse d'images est un thème de recherche important en informatique, elle a de nombreuses applications dans les domaines de la robotique (adaptation d'un robot à son environnement), de la production industrielle (contrôle de qualité, comptage d'objets), de la médecine (étude du corps humain, diagnostic, assistance chirurgicale) de la biologie, de l'agronomie, des agro-industries et en général dans toutes les tâches qui nécessitent un contrôle visuel.


L'évolution rapide du traitement des images est largement favorisée par les progrès des calculateurs en termes de vitesse de calcul et de capacité mémoire puisque les images sont formées d'une quantité très importante de points (pixels) qui sont autant d'informations à traiter.

Dans cette branche des applications de l'informatique, la représentation et la localisation d'objets dans l'espace ouvrent d'énormes perspectives.


Définition : La stéréoscopie est un procédé permettant d'obtenir l'impression de relief (Petit Robert).


Définition : La stéréophotogrammétrie consiste à mesurer la taille des objets et la position des objet dans l'espace à partir d'un ensemble d'images stéréoscopique.


L'étude d'objets en trois dimensions ou stéréovision peut se faire à l'aide de capteurs actifs ou passifs.



1 - La vision active du relief est obtenue en envoyant un signal vers l'objet à étudier, et en recueillant le résultat obtenu après réflexion sur sa surface (information topologique) ou après avoir traversé l'objet (information densitométrique).

a - L'information densitométrique est utilisée pour les tomographies à partir des images de scanner dont le principe est un couple émetteur de rayons X et un récepteur situé de l'autre côté de l'objet, qui tourne autour de l'objet à observer. La densité de chaque point de l'objet (voxel) est calculée dans un espace 3D discret à partir de l'ensemble des densités totales de l'objet à chaque pas d'acquisition.

b - L'information topographique est obtenue activement en envoyant un faisceau impulsionnel vers un point de l'objet est en mesurant le temps d'aller et retour du signal qui est réfléchi par la surface de l'objet. Le signal émis peut être une onde électromagnétique (RADAR), une onde sonore (SONAR, échographie) ou un faisceau laser. L'ensemble des informations distance et orientation du faisceau donne un nuage de points représentatif de l'enveloppe de l'objet et de sa position dans l'espace.

2 - La vision passive du relief est basée sur l'analyse de plusieurs images d'un même objet prises de différents points de vue, soit le long de l'axe optique de la caméra (stéréo vision axiale), soit en déplaçant le système de prise de vue latéralement (stéréovision latérale). La stéréovision passive est fondée en général sur un ensemble de deux (vision binoculaire) ou trois (vision trinoculaire) images stéréoscopiques. Elle est statique lorsque le positionnement relatif des objets est inchangé sur les deux points de vue, et dynamique lorsqu'il y a déplacement. La vision dynamique des objets permet d'étudier en outre leur déplacement spatio-temporel.



La stéréoscopie statique passive constitue le thème de notre étude. Le calcul de points dans l'espace à partir de leurs projections sur les plans images nécessite des hypothèses sur le modèle de caméra qui donne le mode de création des images.


Les méthodes traditionnelles s'appuient sur la connaissance d'informations sur les caméras ainsi que les coordonnées de points dans l'espace pour mettre les projections d'un même point en correspondance et calculer la position de ce point dans l'espace. Certaines applications de la stéréovision basées sur l'analyse d'images optiques sont déjà relativement fiables. Par exemple, les modèles numériques de terrain calculés à partir de photographies aériennes ou spatiales sont réalisés couramment. Cependant d'autres applications comme l'évaluation du relief d'images de microscopie électronique à balayage sont encore à l'étude compte tenu de la difficulté d'évaluation des paramètres du microscope et des propriétés de ces images.


Plus récemment, de nouvelles études ont été réalisées sur les propriétés projectives des images stéréoscopiques, évitant la nécessité de connaître les paramètres des appareils de prise de vue. Cette voie ne propose encore que des résultats partiels qui ne constituent pas une chaîne complète de traitement.


L'objet de notre travail se situe dans cette nouvelle approche du problème de la stéréovision. Notre contribution consiste à découpler l'analyse des relations géométriques du système de prise de vues en deux parties:

- une analyse bidimensionnelle des relations géométriques qui lient deux plans images nous fournit des informations permettant la mise en correspondance des projections d'un même point de l'espace. Cette phase s'appuie sur un ensemble de couples homologues (au moins 8) de projections de points respectivement sur deux plans images.

- une analyse tridimensionnelle du système de prise de vues en s'appuyant sur les informations de l'étape bidimensionnelle et la connaissance de points dans l'espace ainsi que leurs projections sur les plans images. Le nombre de points connu est de 4 pour la projection parallèle et 5 pour la projection centrale.

Cette partie fait l'objet du chapitre 3 de notre rapport. Elle comprend la présentation théorique de notre méthode et les résultats sur des ensembles de points générés artificiellement.


D'autre part nous proposons une chaîne de traitement à partir d'images brutes qui comprend deux étapes :


A) Mise en correspondance des images divisée en trois phases:

1. Extraction de contours d'objets constituant les indices visuels de base. Cette phase est traitée dans le chapitre 4.

2. Mise en correspondance des contours d'objets entre deux images par programmation dynamique basée sur un critère de forme et par la contrainte géométrique bidimensionnelle étudiée dans le chapitre 3. Puis correction d'une image par rapport à l'autre pour faciliter la mise en correspondance. Cette phase constitue une autre originalité de notre méthode. Elle est abordée dans le chapitre 5.

3. Mise en correspondance de l'ensemble des deux images (fusion) par programmation dynamique basée sur la luminance des points homologues supposée identique. Elle est décrite à la fin du chapitre 5.

B) Calcul de points dans l'espace à partir de leurs projections sur les deux plans images. Cette partie constitue les chapitres 3 et 6 de notre rapport. Elle comprend une méthode basée sur un modèle projectif perspectif d'une part s'appuyant sur cinq points connus dans l'espace et d'autre part un modèle projectif parallèle sur quatre points de l'espace.


Nous finissons cet ouvrage par une discussion sur les points forts et points faibles de la méthode ainsi que sur les perspectives de ce travail.


Mais tout d'abord, présentons les modèles géométriques utilisés dans les méthodes de stéréovision ainsi que les différentes méthodes existantes.




2. Techniques de stéréovision



Ce chapitre est consacré à la présentation des modèles géométriques utilisés, de la problématique de base et des différentes approches étudiées dans la littérature. Il se termine par une description de notre travail et des motivations qui ont guidé nos choix.

2.1 Modèles géométriques de caméra

2.1.1 Modèle sténopé ou trou d'épingle


Le modèle simplifié généralement utilisé pour représenter une caméra est le modèle sténopé ou trou d'épingle [BENA83] [AYAC89] [HURA60] [CARR71]. Nous utiliserons des termes dérivés de l'optique pour décrire ce modèle géométrique qui constituent des abus de langage courants dans le domaine de la vision par ordinateur.


Ce modèle est formé d'un centre optique C et d'un plan image P. Tous les rayons lumineux issus de l'objet observé dans l'espace passent par le centre optique et se propagent en ligne droite.

On appelle axe optique la perpendiculaire menée du centre optique sur le plan image, point central l'intersection de l'axe optique avec le plan image et distance focale la distance du centre optique au plan image .

La projection d'un point de l'espace sur le plan image est centrale ou perspective. Sa trace Im sur l'image est l'intersection de la droite (M,C) passant par le point de l'espace et le centre optique de l'appareil de prise de vues, avec le plan image P.


La figure suivante présente le modèle géométrique sténopé, et le référentiel qui lui est associé.



Fig. 2.1: Le modèle sténopé



Si l'on suppose un maillage rectangulaire des points du plan image, nous pouvons prendre comme origine d'un repère orthonormé le centre optique C du système de prise de vue, les axes X et Y parallèles au plan image et l'axe des Z perpendiculaire au plan image. Les paramètres de l'appareil de prise de vue sont:

- La distance focale F qui est la distance entre le centre optique et le plan image

- Le point central Pc qui est la projection orthogonale du centre optique sur le plan image.

- La taille des pixels en X et en Y.


Ces paramètres sont appelés intrinsèques ou internes car ils dépendent uniquement de l'appareil de prise de vue.


L'image d'un point du plan image a donc comme coordonnées (x, y, -F) dans le repère du système de prise de vue.

2.1.2 Modèle projectif parallèle

La projection parallèle correspond au cas où le centre optique est situé à l'infini, c'est à dire qu'il n'y a pas d'axe optique. La projection d'un point est orthogonale lors que la trace d'un point de l'espace sur le plan image est la base de la perpendiculaire menée de ce point sur le plan image.

Ce modèle permet une simplification de la méthode de calcul des points dans l'espace, comme nous le présentons ultérieurement. Il présente une bonne approximation du modèle sténopé si la taille de l'objet observé est faible par rapport à la distance d'observation. Il peut donc être utilisé pour les appareils de prise de vue à longue focale, ou le calcul d'objets compacts et suffisamment éloigné.


Richard O.DUDA et al [DUDA70] étudient largement les transformations perspectives et les invariants projectifs. Cette référence présente les bases de la correspondance projective de deux images stéréoscopiques et présente les intérêts des projections orthogonales par les simplifications qu'elles entraînent. Dans le cas de projection orthogonale, les droites épipolaires sont parallèles et les propriétés de cette transformation sont la linéarité et le fait que la longueur de la projection orthogonale d'un segment de droite sur un plan parallèle est identique à la longueur de ce segment de droite. Ces propriétés permettent d'envisager le calcul des points dans l'espace sans calcul des paramètres du système de prise de vue puisque ceux-ci sont fixés par le modèle de projection.

La référence [MICR85] étudie la projection du microscope à balayage pour les forts grandissements (supérieurs à 500). Dans ce cas, nous pouvons considérer le type de projection comme orthogonale du fait de la distance focale importante. Ceci ouvre des perspectives très intéressantes dans le traitement de ce type d'images, car nous obtenons un simplification du problème de stéréovision.

2.1.3 Modèle de déformation

Les modèles présentés précédemment considèrent un plan image de métrique Euclidienne défini par son référentiel pour les appareils de prise de vue, ce qui n'est pas le cas dans la réalité. L'influence des déformations du plan image peut dans certains cas jouer un rôle capital dans les erreurs de calcul des points dans l'espace. Les images optiques et de microscope à balayage présentent des distorsions semblables en forme de tonneau ou en coussin. Elles ont été étudiées par Giorgio Toscani [TOSC87] dans sa thèse pour les images optiques. L'auteur décrit une erreur radiale par rapport au point central, qu'il approxime de façon polynomiale. La référence [ALIR85] étudie les déformations d'images de microscope à balayage qui sont de forme similaire aux images optiques, l'auteur les approxime par des quadriques.

2.2 Stéréoscopie

La stéréoscopie ou vision en relief, est obtenue en calculant les points dans l'espace à partir de deux images observées à partir de points de vue différents.


Pour deux appareils de prise de vue de type sténopé, la projection du point M sur un plan image est l'intersection du plan avec la droite passant par le centre optique et le point M. Les points M, Mg, Cg, Md, Cd sont donc coplanaires. La position d'un point M de l'espace est obtenue calculant l'intersection des droites (Mg, Cg) et (Md, Cd) qui passent par l'image du point et son centre optique associé dans chaque appareil de prise de vue.

Ce calcul n'est possible que si l'on connaît la position respective des appareils de prise de vue dans l'espace ainsi que les projections du point M sur les deux plans images.




Fig. 2.2: Problématique de base



La position d'un appareil de prise de vue par rapport à l'autre revient à calculer le changement de repère entre leurs deux référentiels soit:

- 3 paramètres qui déterminent la rotation entre les axes des deux repères

- 3 paramètres qui déterminent la translation entre les origines des deux repères.

Ces six paramètres constituent les paramètres extrinsèques ou paramètres extérieurs du système de prise de vue.


Dans la stéréovision statique passive, les deux problèmes à résoudre sont l'identification des points homologues entre les deux images ou mise en correspondance (en anglais matching) et la calibration du système de prise de vue, c'est à dire sa modélisation dans l'espace. Les deux étapes fondamentales de mise en correspondance des images et de calibration mènent au calcul d'un point par triangulation (intersection de deux droites dans l'espace).


2.2.1 Mise en correspondance

La mise en correspondance de deux images stéréoscopiques consiste à établir une relation point à point entre celles-ci. Elle nécessite une représentation condensée des images pour réduire les calculs et permettre d'appliquer des critères de similarité entre les objets synthétiques issus de la segmentation des images.


Les deux types d'objets principalement utilisés sont les contours d'objets et les régions homogènes.

- Les contours représentent des zones de discontinuité lumineuse représentés sous forme de suite de points connexes, de segments de droites ou de courbes [AYAC88]. Les critères de ressemblance sont basés sur la forme, ou sur la longueur et l'orientation de segments qui les composent.

- Les régions homogènes sont caractérisées par leurs propriétés d'homogénéité généralement basées sur la luminance. Les méthodes de segmentation en régions sont classées en deux catégories: les méthodes de division (top down) qui réalisent une partition de l'espace des luminances et les méthodes de croissance de régions (bottom up) qui utilisent l'information de luminance et les relations spatiales entre les points de l'image [VINE91] [HWAN80]. Les critères de ressemblance sont basés sur la luminance et les caractéristiques inertielles des régions.


En plus des critères de ressemblance utilisables pour mettre en correspondance les objets de deux images, la structure du système de prise de vue stéréoscopique définit une contrainte épipolaire qui réduit pour un point la recherche de son correspondant à une droite sur l'image homologue. Cette contrainte est issue du fait que les deux droites passant par les images d'un point de l'espace sur les deux plans images définissent un plan dans l'espace. L'intersection de ce plan avec les deux plans images définit un couple de droites épipolaires homologues.

L'obtention des droites épipolaires est issue soit de l'étape de calibration qui donne la position relative ou absolue des deux plans images dans l'espace, soit de la connaissance de points homologues sur les deux images qui définissent le modèle géométrique de celles-ci [MOHR92] [MOHR93] [MORI93].


Pour initialiser le processus de mise en correspondance de deux images stéréoscopiques, dans le cas de systèmes de prise de vue non calibrés, il faut donc extraire un certain nombre d'indice visuels et les apparier afin d'obtenir des couples de points appelés amers qui sont les images homologues d'un même point de l'espace.


Les indices visuel doivent avoir les propriétés suivantes pour être utilisables dans la mise en correspondance entre deux images [AYAC89].


compacts: les informations doivent être aussi concises que possible pour limiter la complexité d'algorithmes ultérieurs.


intrinsèques: ils doivent correspondre à la projection dans l'image d'objets physiques et être invariants par changement de point de vue.


précis et robustes: la qualité de la localisation des objets dans l'espace ou de la mise en correspondance entre images dépend de leur précision et de leur robustesse au bruit.


discriminants: ils ont des propriétés permettant de les discriminer pour permettre la mise en correspondance de deux descriptions.


denses: un nombre minimal d'indices visuels est nécessaire pour assurer la mise correspondance, d'autre part ces indices doivent être répartis régulièrement sur l'image pour une meilleure stabilité des calculs.



L'extraction de points amers peut se faire :


- manuellement en repérant des points homologues sur deux images stéréoscopiques [BENA83],

- en mettant en relation les centres de gravité des régions homologues [VINE91] ce qui suppose une certaine tolérance puisque le centre de gravité d'une région n'est pas forcément celui de la région correspondante.

- en mettant en relation les centres des segments de droites homologues pour les contours appariés [AYAC89]. La stabilité de ces points est fonction de la précision de l'extraction des contours.


Lorsque la géométrie épipolaire est définie, la fusion de deux images stéréoscopiques utilise en général les propriétés suivantes [SHIR87] [AYAC89]:


compatibilité : les luminances des points homologues sont supposées similaires


unicité : chaque point ne peut avoir qu'un seul point homologue (sauf pour les objets transparents).


ordre : la relation d'ordre des points de l'image homologues respecte celle des points de l'image de départ. Cette contrainte est violée si il existe dans un même plan épipolaire, des points de la scène visible par les deux caméras que l'on peut joindre par une droite qui passe entre les deux centres optiques.


continuité : la surface des objets est suffisamment régulière pour que les disparités entre points voisins varient de manière régulière, presque continue.



Les méthodes de fusion d'images stéréoscopiques sont basées sur:


- l'élargissement de la correspondance par recouvrement de deux régions homologues et l'utilisation de la cohérence des relations d'adjacence [VINE91] [HWAN80],

- la mise en correspondance des droites épipolaires homologues par programmation dynamique en calculant le chemin de coût minimum dans un graphe de luminance [BENA83] [SHIR87],

- le déplacement d'une fenêtre de corrélation le long de droites épipolaires homologues [FORE88] [SHIR87]. Cette méthode consiste à rechercher pour une zone de l'image de référence un maximum de corrélation sur une fenêtre mobile dans l'image homologue. Le maximum de ressemblance correspond à une corrélation maximale entre les pixels des deux images.

Toutes ces méthodes sont très sensibles aux variations de radiométrie (ou variation de l'intensité lumineuse entre les deux images pour un même point), et demandent des temps de calcul très importants.

Certaines approches de mise en correspondance utilisent trois images homologues.

Nicholas Ayache [AYAC89] présente une méthode de vision trinoculaire permettant de mettre en place des algorithmes de prédiction-vérification. En utilisant une approximation polygonale des contours, l'algorithme est basé sur le fait que lorsqu'un appariement de segments est réalisé entre deux images, sa position dans la troisième image peut être prédite. La validation de l'appariement est réalisée par la vérification de cette prédiction. D'autre part la contrainte épipolaire est utilisée pour renforcer le critère de correspondance entre segments.

La génération de prédictions et leur vérification est largement utilisée par Lux [LUX_84] comme technique d'intelligence artificielle en vue de la limitation du combinatoire dans la reconnaissance d'objets partiellement visibles, et dans l'interaction entre interprétation et segmentation. Cette technique est appliquée à la reconnaissance d'objets de différents types qui sont modélisés dans une base de données.

2.2.2 Calibration

Au début de ce chapitre, nous avons vu que les deux problèmes de base en stéréovision consistent à mettre les points des deux images en correspondance et de positionner les plans images dans l'espace. Le calcul du point peut alors être réalisé par triangulation, c'est à dire l'intersection des deux droites passant respectivement par l'image du point dans un plan image et le centre optique associé à ce plan image.


La calibration consiste à définir la géométrie dans l'espace qui permettra de définir les deux droites associées à un couple de points homologues. Cette calibration peut être obtenue de façons différentes.


Certaines méthodes de stéréovision présentent des modèles géométriques simplifiés qui facilitent la calibration du système de prise de vue.


La première application courante de stéréovision est la photographie aérienne. Le Général Hurault [HURA60] et Jean Carré [CARR71] présentent le principe de prise de vue normale d'un couple d'images stéréoscopiques qui consiste à prendre deux photos à la même altitude avec les plans images horizontaux.

L'altitude H de l'avion est constante et connue ainsi que son déplacement entre les deux prises de vue. D'autre part, la distance f du centre optique au plan image, ainsi que les coordonnées (x0,y0) du point central correspondant à sa projection sur l'image sont connues. La translation B entre les deux prise de vues est appelée base du couple. Les plans images étant coplanaires, les droites épipolaires sont parallèles, chaque point homologue sur la deuxième image est translaté par rapport au point sur l'image de référence dans la direction du déplacement de l'avion.

La méthode pour calculer les points dans l'espace se déroule en deux temps.

- Le recalage consiste à superposer les points centraux des deux images et orienter les images de telle façon que les droite passant par les points homologues soient parallèles, en prenant comme axe des X la direction du déplacement de l'avion.

- La distance dl entre deux points homologues appelée parallaxe linéaire longitudinale nous donne l'altitude Z du point par la formule:


dl = - b . Z / ( H - Z )


où b représente la quantité B.f/H qui correspond à la longueur de la base à l'échelle du plan image.


La référence [CARM91] propose une étude de la stéréovision axiale. Les couples d'images sont obtenus par déplacement de la caméra le long de son axe optique ou par effet de zoom sans déplacement de la caméra. Ce type de stéréoscopie est simplifié par rapport à la stéréoscopie latérale. Deux algorithmes de détermination du point central sont proposés, ainsi qu'une présentation des expériences réalisées. L'auteur conclut que cette stéréoscopie est moins précise que la stéréoscopie latérale, surtout auprès du point central, puisque les écarts entre points homologues ne sont pas assez significatifs pour permettre une évaluation correcte.


On peut distinguer deux familles de méthodes de calibration de systèmes stéréoscopiques, la reconstruction avec étalonnage suppose l'évaluation des paramètres intrinsèques et extrinsèques du système de prise de vue et le positionnement relatif qui fait appel au propriétés géométriques des images stéréoscopiques pour positionner les points par rapport à un ensemble de points de référence connus dans l'espace et sur les plans images.


La reconstruction avec étalonnage [AYAC89] [CHAU89] fait appel à des grilles de calibration parfaitement connues qui présentent des points identifiables dans l'espace et sur les plans images, permettant ainsi l'évaluation des paramètres intrinsèques et extrinsèques du système de prise de vue. On choisit généralement un repère orthonormé sur le centre optique de l'un des appareils de prise de vue avec l'axe Z perpendiculaire à son plan image.

Le problème de cette approche est que ce type de calibration nécessite une rigidité parfaite du système de prise de vue. Les chocs mécaniques, les variations de température ou de mise au point font varier les paramètres du système de prise de vue, de sorte que les résultats obtenus avec ce mode de calibration sont souvent inexploitables. D'autre part, certains types de système stéréoscopiques interdisent une telle approche par l'impossibilité d'utiliser une mire (ex: microscopie électronique).

Certaines méthodes s'appuient sur les données du constructeur pour les paramètres intrinsèques et calculent les paramètres extrinsèques, soit par une méthode itérative [BENA83] en connaissant six couples de points homologues pour des angles faibles entre les plans images, soit avec la connaissance de huit couples de points par la résolution d'un système d'équations linéaires [HWAN80] [LONG81]. Les résultats sont peu précis du fait des incertitudes sur les valeurs des paramètres intrinsèques fournis par les constructeurs.


Les méthodes de positionnement relatif sont relativement récentes et s'appuient sur un ensemble de points connus dans l'espace. Roger Mohr et Luce Morin [MOHR92] [MORI93] [MOHR93] proposent une solution avec un ensemble de six points dans l'espace et étudient la stabilité des résultats en fonction des imprécisions sur la position des points dans les plans images. L'instabilité des points calculés par la méthode de positionnement relatif est moindre que pour les reconstructions avec étalonnage. Dans la même approche, Claude Millon [MILL91] propose une méthode de calcul avec six points et Olivier Faugeras [FAUG92] avec cinq points dans le cas d'une projection centrale et quatre points pour une représentation affine de l'environnement.

2.2.3 Chaîne de traitement

Notre travail ayant au départ pour but l'étude et la réalisation d'une chaîne de traitement adaptée à des images stéréoscopiques de microscopie électronique, nous avons choisi une approche qui ne nécessite par d'étalonnage. Nous avons conservé cette approche dans la généralisation de notre méthode, étant donné que en général, les images stéréoscopiques ne sont pas accompagnées des paramètres du système de prise de vue.

Notre objectif a donc été de réaliser la mise en correspondance des images en nous basant uniquement sur les informations contenues dans les images et à repousser l'étape de calibration à la fin de la chaîne de traitement pour éviter la propagation d'erreurs d'approximation des points de référence dans l'espace.

Pour découpler les étapes de mise en correspondance et de calibration, nous avons divisé la partie géométrique en deux étapes. La première, bidimensionnelle permet d'aboutir à la fusion des deux images, c'est à dire la mise en correspondance point à point, et la seconde dans un espace projectif à trois dimensions qui permet de calculer les points relativement à une base projective formée par cinq points de référence supposés connus. Le passage aux valeurs tridimensionnelles des points dans l'espace cartésien 3D se fait par une simple matrice de changement de repère obtenue avec les coordonnées tridimensionnelles de cinq points de référence.


Pour la mise en correspondance des deux images, nous avons choisi de nous appuyer sur les contours des objets qui nous offrent des points plus précis grâce auxquels nous pouvons calculer la géométrie épipolaire liée aux images.

Dans un premier temps, nous extrayons un ensemble d'au moins huit couples de points homologues sur les deux images. Nous utilisons pour cela un algorithme de programmation dynamique qui met en correspondance les couples potentiels de contours codés suivant l'alphabet de Freeman, et la validation des appariements obtenus par les contraintes de la géométrie épipolaire.

Les couples de points extraits nous permettent ensuite de recalculer une des images par rapport à l'autre en superposant les droites épipolaires des deux images. Cette étape nous permet de fusionner les deux images en mettant les points des droites épipolaires en correspondance par programmation dynamique suivant le critère de luminance.


La figure suivante présente le schéma synoptique de notre chaîne de traitement. Elle est divisée en cinq parties principales.

1) Les deux blocs d'extraction de contours prennent en entrée les images d'origine et donnent en sortie deux ensembles de contours codés suivant l'alphabet de Freeman.

2) Le bloc géométrie épipolaire a pour fonction de calculer le modèle géométrique épipolaire à partir d'un ensemble de couples de points, il définit une homographie qui revient à projeter l'image homologue sur un plan de l'espace par le centre optique homologue, puis à reprojeter ce plan de l'espace sur l'image de référence par le centre optique associé à celle-ci. Il donne en sortie des coefficients correspondant à l'homographie calculée, ainsi que des valeurs d'erreur qui caractérisent la validité de la relation calculée.

3) Le bloc forme, distance et position contours prend en entrée les contours des deux images. Il coopère avec le bloc de géométrie épipolaire et donne en sortie un ensemble de couples de points homologues.

4) Le bloc correction et fusion d'images prend en entrée des couples de points homologues et la relation homographique correspondante. Il donne en sortie l'ensemble des points appariées entre les deux images homologues.

5) Le bloc espace projectif, géométrie 3D prend en entrée l'ensemble des points appariés et les paramètres de la calibration (position des points de référence dans l'espace), il donne en sortie les valeurs tridimensionnelles de tous les points appariés.









Figure 2.3: Schéma synoptique de la chaîne de traitement






 3. Géométrie

Ce chapitre est dédié à une étude de la géométrie d'un système de stéréovision et des solutions que nous proposons.


Notre méthode nous permet de travailler en trois étapes:


1) en deux dimensions afin de calculer les épipoles dans les plans images. Ces points nous aideront à traiter le problème dans l'espace et à mettre les deux images en correspondance.

2) dans un espace projectif afin de calculer les coordonnées projectives des points appariés sans connaissance préalable de la position des points de référence dans l'espace.

3) en trois dimensions par simple passage de l'espace projectif à l'espace cartésien, grâce à la matrice de changement de repère calculée à partir des coordonnées cartésiennes des points de référence.


Nous présentons les notions nécessaires à la compréhension de notre méthode, puis le problème et la solution proposée dans le cas de projection centrale et parallèle. Enfin, nous abordons l'expérimentation de notre méthode sur des ensembles de points générés artificiellement pour valider notre solution.


Les applications de ce travail se trouveront dans le chapitre 5 de mise en correspondance pour la partie bidimensionnelle et dans le chapitre 6 de calcul 3D pour les aspects tridimensionnels.



3.1 Coordonnées homogènes

Rapportons l'espace de dimension n à un repère cartésien. A tout élément non nul de Rn+1 noté (X,Y,Z,T) pour n=3, nous pouvons associer :

- si T<>0 le point M de coordonnées cartésiennes (x=X/T, y=Y/T, z=Z/T)

- si T=0 le "point à l'infini" (convention de langage) M dans la direction que définit dans l'espace ordinaire le vecteur non nul (X,Y,Z).

Dans les deux situations, deux points M et M' coincident si et seulement si (X,Y,Z,T) et (X',Y',Z',T') sont proportionnels.

Inversement, à tout point donné (au sens ordinaire ou "à l'infini"), correspond une infinité de systèmes (X,Y,Z,T) possibles (et non nuls) proportionnels. L'un d'entre eux est généralement retenu sous le nom de coordonnées homogènes du point M.


Ainsi (0,0,0,1) représente l'origine des axes, (1,0,0,0), (0,1,0,0) et (0,0,1,0) leurs points à l'infini (directions), et le système (1,1,1,1) représente le point unitaire qui sert à déterminer la graduation des axes. L'ensemble de ces n+2 points est un repère projectif que nous notons Ro.


Si nous considérons les points Mi (Xi,Yi,Zi,Ti) avec 0<i<n+2,


pour n=3: quatre points Mi sont dans un même plan si et seulement si :


X1 X2 X3 X4
Y1 Y2 Y3 Y4
Z1 Z2 Z3 Z4 = 0
T1 T2 T3 T4




pour n=2: trois points Mi sont alignés si et seulement si :


X1 X2 X3

Y1 Y2 Y3 = 0

T1 T2 T3


pour n=1: deux points Mi sont confondus si et seulement si :


X1 X2

T1 T2 = 0



La souplesse des coordonnées homogènes se manifeste donc surtout dans les problèmes projectifs où n'interviennent que des points, droites, plans à identifier, droites concourantes, plans ayant une droite commune, notions qui se ramènent à une dépendance linéaire dans un espace vectoriel, entre éléments non nuls.





3.2 Coordonnées projectives

On appellera plus généralement repère projectif R tout système de n+2 points Mi tels que (n+1) quelconques d'entre eux soient indépendants (c'est à dire non coplanaire si n=3, non alignés si n=2, non confondus si n=1). Le (n+2)ème point joue le rôle de point unitaire, ce qui signifie en prenant n=2 qu'il existe des coefficients non nuls p1, p2, p3,p4 tels que:


p4.X4 p1.X1 p2.X2 p3.X3 X1 X2 X3 p1 p4.X4

p4.Y4= p1.Y1+p2.Y2+p3.Y3 <=> Y1 Y2 Y3 p2 = p4.Y4

p4.T4 p1.T1 p2.T2 p3.T3 T1 T2 T3 p3 p4.T4


Ces coefficients sont définis à un facteur de proportionnalité près, on est donc resté fidèle au principe des coordonnées homogènes. Cependant, pour des raisons de commodité, on choisit généralement p1=p2=p3=p4=1.

En pratique, ces quatre points étant "à distance finie", on simplifie en prenant M4 au centre de gravité du triangle M1,M2,M3, ce qui revient à choisir T1=T2=T3=p1=p2=p3=1,T4=3 et p4=1.


Changement de coordonnées: Le passage de Ro (du paragraphe précédent) à R permet de représenter un point M par un nouveau système de coordonnées. si on les note (X',Y',T'), la formule de passage est:


-1
X X1 X2 X3 X' X' X1 X2 X3 X
Y = Y1 Y2 Y3 Y' <=> Y' = Y1 Y2 Y3 Y
T T1 T2 T3 T' T' T1 T2 T3 T


comme en algèbre linéaire. Mais il faut remarquer que les coordonnées (X,Y,T) et (X',Y',T') sont des coordonnées homogènes.


Un tel système (X',Y',T') est un système de coordonnées projectives dans le repère R.


L'emploi de ces coordonnées reste techniquement le même. Ainsi l'équation d'une droite est toujours de la forme uX + vY + wT = 0. Celle qui joint les points de coordonnées (a,b,c) et (a',b',c') dans R est:


X a a'

Y b b' = 0

Z c c'


Les sommets M1(1,0,0), M2(0,1,0), M3(0,0,1) et le point unitaire M4(1,1,1) du repère R sont respectivement associés à M1(X1,Y1,T1), M2(X2,Y2,T2), M3(X3,Y3,T3) et M4(X4,Y4,T4). Tout se passe comme dans Ro du point de vue calcul, même si (0,0,1) est cité ici en troisième position à cause des habitudes matricielles.


3.3 Les homographies

3.3.1 Dimension 1

Considérons deux droites D et D' munies chacune d'un repère projectif R et R' respectivement.

Une homographie H: D -> D' est une application bijective définie par une matrice inversible:


H =a b

c d

de sorte que M(X,T) ait pour image M'(X',T') telle que (X',T')=H(X,T).




Propriétés:


1) La transformation ne change pas en remplaçant H par une matrice proportionnelle.

2) Si un changement de repère projectif est effectué de matrice P pour R, P' pour R', on substitue simplement à (X,T) et (X',T'): P(X,T) et P'-1(X',T'). Donc H est remplacée par: H'= P'-1.H.P qui est toujours une matrice inversible. La notion d'homographie H a donc un caractère intrinsèque.

3) Si on compose H avec une homographie H': D' -> D" (avec repère R"), H o H' est encore une homographie (de matrice H'H dans les repères R,R").

4) H-1: D' -> D est une homographie.

5) Dans le cas où D'=D on pourra donc parler du groupe des homographies de la droite D.



Notion de birapport:


Ce paragraphe a un rôle purement descriptif puisque dans notre méthode, nous n'utilisons pas les birapports.


Prenons R=Ro et R'=Ro' pour retrouver les coordonnées cartésiennes usuelles sur D et D', x=X/T et x'=X'/T' donnent x'=(ax+b)/(cx+d). C'est la fonction homographique classique (ad-bc<>0) complétée par :

- "l'infini" a pour image le point (a,c), généralement à distance finie sur D'.

- le point (-d,c) de D généralement à distance finie sur D a son image "à l'infini" sur D'.


Appelons M1', M2', M3' et M4' les images de quatre points M1, M2, M3, M4. On a:


(x' - x1') / (c' - x2) = k. (x - x1)/(x - x2) où k = (c.x2 + d)/(c.x1 + d)


donc:


x3' - x1' x4' - x1' x3 - x1 x4 - x1

--------- : --------- = ------- : -------

x3' - x2' x4' - x2' x3 - x2 x4 - x2




Ce nombre est dit birapport des quatre points énumérés dans cet ordre et noté (M1,M2,M3,M4). L'homographie a conservé le birapport. Inversement, une transformation ponctuelle de D dans D' conservant le birapport sera de la forme :


x' - x1' x4' - x1' x - x1 x4 - x1
-------- : --------- = ------ : -------
x' - x2' x4' - x2' x - x2 x4 - x2


et donc une homographie.


La notion de birapport est donc fondamentale en géométrie projective. Elle sert même à caractériser les homographies en dimension 1. C'est l'invariant projectif fondamental.



Figure 3.1 Birapport de quatre points sur deux droites


Remarque:

si R est défini par (M1,M2,M3) et R' par (M1',M2',M3'), alors l'homographie est définie par une matrice:


a 0

0 a


qui se ramène à l'identité, c'est à dire que des points homologues par H auront les mêmes coordonnées projectives respectivement dans R et dans R'. Une telle simplification est parfois très utile.

3.3.2 Dimension 2

On considère deux plans P et P' munis chacun d'un repère projectif R et R' respectivement.

Une homographie H: P -> P' est une application bijective définie par une matrice inversible 3x3: H telle que l'image de M(X,Y,T) soit M':(X',Y',T') = H (X,Y,T).


Propriétés:


Les cinq propriétés citées en dimension 1 sont toujours valables.

L'image d'une droite D appartenant à P est une droite D'.

La restriction de H à D et D' est une homographie: D -> D', ce qui entraîne que l'homographie H conserve aussi les birapports de quatre points alignés. Ceci trouve son application dans le birapport de quatre droites coplanaires concourantes D1,D2,D3,D4. Si deux droites D et D' les coupent respectivement en M1,M2,M3,M4 et M1',M2',M3',M4' alors (M1,M2,M3,M4) = (M1',M2',M3',M4'). Ce nombre est appelé birapport de ces quatre droites et noté (D1,D2,D3,D4).


3.3.3 Dimension 3

Les propriétés des dimensions 1 et 2 sont toujours valables.

L'espace permet de voir dans une homographie de plan à plan H: P -> P' qui envoie Mi sur Mi' (i=1,2,3,4) (formant respectivement des repères projectifs de P et P') la restriction d'une homographie de l'espace en lui même.

Le cas particulier où les droites (Mi,Mi') se coupent en un point S constitue une perspective ou une projection de P sur P' à partir de S. Les perspectives conservent donc aussi les birapports. Si L est l'intersection des plans P et P', deux droites D et D' de P et P' se coupent en L, et pour quatre couples, on met en évidence la conservation du birapport des quatre droites concourantes coplanaires par homographie.


3.4 Problème de la stéréoscopie

Définition:

Etant donné un objet de l'espace, on appelle image d'un point P sur un plan donné Q à partir d'un centre (optique) C le point d'intersection M de Q avec la droite (C,P).


Problème:

On suppose connues deux images planes d'un assez grand nombre de points de l'objet Pi sur deux plans Q et Q' à partir de deux centres C et C': images Mi et Mi' supposées identifiées.



Fig. 3.2: Schéma de base de la géométrie épipolaire


On ne peut reconstituer l'objet à partir de ces seules images, mais si l'on dispose à l'avance de cinq points identifiés P1,P2,P3,P4,P5 (tels que quatre d'entre eux ne soient jamais coplanaires) de cet objet, montrons que la reconstitution est possible.

Pour résoudre ce problème nous présentons un cas particulier et une méthode pour nous ramener du cas général à ce cas particulier.


3.4.1 Cas particulier

Considérons le cas particulier où les deux plans images Q et Q' coincident avec un plan q défini par P1, P2 et P3 connus. Appelons m et m' les deux images d'un point P inconnu sur q à partir de C et C', et e point épipolaire l'intersection de la droite (C,C') avec q.




Figure 3.3: Cas particulier de stéréovision



m et m' sont alignés nécessairement avec e qui est donc identifiable si l'on dispose d'au moins deux couples de points.

Si nous connaissons P4, m4 et m4', nous disposons par là même du plan (e,C,C',P4). Il suffit donc de connaître aussi P5, m5 et m5' pour déterminer:

- La droite (C,C') comme intersection des deux plans (e,C,C',P4) et (e,C,C',P5).

- Le point e comme intersection des deux droite coplanaires (m4,m4') et (m5,m5').

- Le point C dans l'espace comme intersection des droites (P4,C,m4) et (P5,C,m5).

- Le point C' dans l'espace comme intersection des droites (P4,C,m4') et (P5,C,m5').


Par suite tout autre couple d'images mi et mi' définira le point Pi dans l'espace comme l'intersection des droites (C,mi) et (C',mi').


3.4.2 Cas général

Dans la pratique, nous n'avons pas la possibilité de savoir comment étaient disposés au départ les plans Q et Q' dans l'espace.

Appelons E et E' les points épipolaires qui correspondent à l'intersection de la droite (C,C') respectivement avec les plans Q et Q'.

Conservons le plan q présenté dans le cas particulier et défini par les points P1,P2 et P3. L'alignement de E,E' et e nous invite à envisager une méthode projective pour résoudre le problème. La figure suivante présente la situation des trois plans Q, Q' et q dans l'espace.




Figure 3.4 : relation entre les plans Q, Q' et q dans l'espace


Remarque: Tous les points présenté sur cette figure sont coplanaires.


Notations:

Dans la suite de notre présentation nous utiliserons les notations suivantes:

les images d'un point sur un plan image seront notées en majuscules, et les images du même point sur le plan q seront en minuscules. Un point P aura donc pour projection M sur Q par C, M' sur Q' par C', m sur q par C et m' sur q par C'.


Principe de la méthode de calcul:

Considérons un plan q de l'espace supposé connu, nous projetons le plan Q sur q par le centre optique C, et le plan Q' sur q par le centre optique C'. Les projections de Q sur q et Q' sur q sont des homographies de plan à plan:

H1: Q -> q et H2: Q' -> q.


Si nous reprojetons l'image du plan Q' sur q vers le plan Q par le centre C, nous appliquons l'inverse de H1 sur H2(Q').

Le paragraphe précédent nous a présenté les propriétés des homographies. L'inverse d'une homographie étant une homographie et la composition de deux homographies étant aussi une homographie, il en résulte que cette double projection Q' -> q -> Q est aussi une homographie H.

Celle ci pour être calculée nécessite la connaissance de quatre points coplanaires homologues sur les deux images. Cependant, la géométrie épipolaire nous donne l'alignement des points homologues dans q avec e qui est l'intersection de la droite (C,C') avec le plan q. Nous choisissons trois couples de points homologues (P1,P2,P3) (P1',P2',P3') plus un point unitaire pris arbitrairement, comme base projective sur les deux images. Après passage en coordonnées projectives des deux ensembles de points homologues (Pi, Pi'), nous calculons une homographie H entre Q et Q' qui superpose les points de la base projective P1=H(P1'), P2=H(P2'), P3=H(P3'), et aligne tous les couples Pi, H(Pi') avec un point E qui correspond à l'épipôle sur le plan Q.

Cette méthode nécessite la connaissance d'un ensemble de 8 points appariés entre les deux images.


Ensuite, il est possible de recalculer les points Mi' de l'image homologue dans l'image de référence par la relation Mi"=H(Mi'). Si nous connaissons l'homographie H entre Q et Q', et cinq points (P1,P2,P3,P4,P5) dans l'espace ainsi que leurs traces (M1,M2,M3,M4,M5) sur Q et (M1',M2',M3',M4',M5') sur Q', nous calculons H(M1',M2',M3',M4',M5') = (M1",M2",M3",M4",M5") dans Q.

Pour nous ramener au cas particulier présenté en début de sous chapitre, il reste à calculer l'homographie H1 entre Q et q ainsi que la position de C et C' soit 6 coordonnées et les deux coefficients de H1.

Ils peuvent être calculés grâce à la connaissance de P4,P4' et P5,P5' par les alignements:

(C,P4,m4), (C',P4,m4'), (C,P5,m5), et (C',P5,m5')

avec m4=H1(M4), m4'=H1(M4"), m5=H1(M5) et m5'=H1(M5"),

ce qui fournit un système linéaire de huit équations et huit inconnues.

Il est possible de calculer C et C' dans l'espace projectif, en prenant P1,P2,P3,P4,P5 comme base projective dans l'espace avec P5 comme point unitaire. Les coordonnées sont alors fixées arbitrairement et permettent de calculer C et C' dans cette base. Le passage à l'espace cartésien se fait par un simple changement de base.


Démonstration:

Introduisons M" en projetant m' sur Q à partir de C, et montrons que l'application H: Q' -> Q , M' -> M" est une homographie et qu'il est possible de la préciser.

C'est en effet une composée d'homographies:

- de Q vers q: M' -> m' induite par la perspective de centre C'

- de q vers Q':m' -> M" induite par la perspective de centre C


H transforme les points M1',M2',M3',E' dans Q' en M1",M2",M3",E dans Q par l'intermédiaire de P1,P2,P3,e dans q. D'autre part, toutes les droites (M,M") de Q concourent en E.



Figure 3.5 : relation entre les points dans le plan (C,C',P)


a) Relations entre les plans images

Rapportons Q au repère projectif R formé par M1,M2,M3 et comme point unitaire le centre de gravité de M1,M2,M3. Aux coordonnées cartésiennes (xi,yi) d'un point Mi de Q, on associera le système de coordonnées projectives (Xi,Yi,Zi) défini par:



-1
Xi x1 x2 x3 xi
Yi = y1 y2 y3 yi
Zi 1 1 1 1


Formule de passage en coordonnées projectives



on sait que l'on peut multiplier Xi,Yi,Zi par un nombre différent de zéro arbitraire, ce nouveau système détermine le même M, il n'y a bien que deux paramètres effectifs par point.


Rapportons Q' à un repère R' à partir de M1', M2', M3' de façon analogue. L'homographie transformant un point M' de R' en M" dans R sera définie par une matrice diagonale car à (1,0,0) dans R, correspond (1,0,0) dans R' (idem pour (0,1,0) et (0,0,1)). Les formules:




Xi" a 0 0 Xi'
Yi" = 0 b 0 Yi'
Zi" 0 0 c Zi'


Matrice diagonale de l'homographie a,b,c



avec a.b.c<>0 déterminent un système de coordonnées projectives de M".

A noter que les nombres a, b et c sont définis à un facteur de proportionnalité près et qu'ils sont encore inconnus, de même que la position de E.



Soit (Ex,Ey,Ez) un système de coordonnées projectives de E dans R. Utilisons le fait que les droites Di(Mi,Mi") se rencontrent en E, c'est à dire:



Ex Xi a.Xi'
Ey Yi b.Yi' = 0
Ez Zi c.Zi'


Equ.1: Système d'équations de l'alignement (E,Mi,H.Mi')


ce qui n'a d'intérêt que pour les indices i>3 puisque les points d'indice 1,2,3 ont les mêmes coordonnées projectives. Prenons trois tels indices i,j,k distincts. La compatibilité en Ex, Ey et Ez des trois équations entraîne:



c.Yi.Zi'-b.Yi'.Zi a.Zi.Xi'-c.Zi'.Xi b.Xi.Yi'-a.Xi'Yi
c.Yj.Zj'-b.Yj'.Zj a.Zj.Xj'-c.Zj'.Xj b.Xj.Yj'-a.Xj'Yj = 0
c.Yk.Zk'-b.Yk'.Zk a.Zk.Xk'-c.Zk'.Xk b.Xk.Yk'-a.Xk'Yk


Equ.2: Système d'équations des coefficients de l'homographie


que l'on peut ramener compte tenu de son homogénéité à la forme:




A.b/c + A'.c/b + B.c/a + B'.a/c + C.a/b + C'.b/a + D = 0


deux telles équations de ce type (avec deux triplets i,j,k différents) suffisent à priori, puisqu'il n'y a que deux inconnues véritables (par exemple a/c et b/c), mais puisqu'on dispose d'un nombre suffisant de couples de points Mi,Mi', il est préférable de les traiter comme équations linéaires de la forme A.x1 + A'.x2 + B.x3 + B'.x4 + C.x5 + C'.x6 + D = 0 à six inconnues x1, x2, ..., x6.

Pour cela nous avons besoins d'au moins 5 points qui pris trois à trois nous fournissent 10 équations nous permettant de résoudre le système au moindres carrés. Au total, cette méthode nécessite 3 points de base + 5 points secondaires pour résoudre le système, soit 8 points homologues connus sur les deux images.

Après coup, on vérifiera qu'il est possible de contrôler la validité des points choisis puisque x1.x2 = x3.x4 = x5.x6 = 1.


L'homographie H étant ainsi déterminée, le point E sera à son tour déterminé par le système linéaire d'équation d'alignement (E,Mi,H.Mi'), puis de même E' = H-1(E).

b) Relations dans l'espace

Revenons maintenant à l'espace, prenons le repère projectif R* formé par P1, P2, P3, P4 et pour point unitaire le centre de gravité de ces quatre points, pour conserver la même technique de passage cartésienne - projective. Il est possible de choisir P5 comme point unitaire mais sans aucun intérêt technique, sinon de pouvoir calculer la position des points dans l'espace projectif, le point P5 intervenant alors dans le passage en coordonnées cartésiennes.

En restriction au plan q, celui-ci se trouve muni du repère r* (P1,P2,P3 et comme point unitaire le centre de gravité de ces trois points).


On a envisagé plus haut l'homographie q -> Q, m -> M, m' -> M" induite par la perspective de centre C.

Si les coordonnées projectives de m dans r* sont notées (x*, y*, z*), celles de M associé seront de la forme:



X u 0 0 x*
Y = 0 v 0 y*
Z 0 0 w z*


Matrice diagonale de l'homographie u,v,w



où la matrice diagonale définit l'homographie (u.v.w<>0).

Elle est diagonale puisque P1 -> M1, P2 -> M2 et P3 -> M3.

On aura donc m: (X/u, Y/v, Z/w) et m':(X"/u, Y"/v, Z"/w) avec X"=a.X', Y"=b.Y' et Z"=c.Z'.


Montrons que l'on peut préciser aussi cette homographie grâce à la connaissance de P4 et de P5.

On se sert du fait que (1) (P4,m4) et (P5,m5) se coupent en C dans le plan (P4, P5, m4, m5), et de même (2) (P4,m4') et (P5,m5') se coupent en C' dans le plan (P4, P5, m4', m5').

Les coordonnées projectives de P5 dans le repère spatial étant supposées connues et notées (X5*,Y5*,Z5*,1), comme l'équation d'un plan passant par P4:(0,0,0,1) est de la forme A.x* + B.y* + C.z* = 0, on a:


(1) X4/u X5/u X5* X4 X5 u.X5*

Y4/v Y5/v Y5*= 0 <=> Y4 Y5 v.Y5*= 0

Z4/w Z5/w Z5* Z4 Z5 w.Z5*

soit:



(1)
X4 X5 u.X5* (2) X4" X5" u.X5*
Y4 Y5 v.Y5* = 0 et Y4" Y5" v.Y5* = 0
Z4 Z5 w.Z5* Z4" Z5" w.Z5*


Equ.3: Système d'équations de l'homographie u,v,w



Ces deux équations (A.u + B.v + C.w = 0 et A'.u + B'.v + C'.w = 0) définissent u,v et w à un facteur de proportionnalité près. L'homographie est donc déterminée: u=BC'-CB', v=CA'-AC', w=AB'-BA' ou des nombres proportionnels.

Notons que e l'est aussi, comme intersection des droites (m4,m4') et (m5,m5'), ou comme transformée par l'homographie de E qui est connu.


Détermination de C:

Les coordonnées projectives dans R* de m4 sont (X4/u,Y4/v,Z4/w,0), donc celles de C aligné avec P4: (0,0,0,1) et m4 sont de la forme (s.X4/u, s.Y4/v, s.Z4/w, 1), s étant inconnu.

C étant aligné avec P5 et m5, on une dépendance linéaire de (s.X4/u, s.Y4/v, s.Z4/w, 1), (X5*,Y5*,Z5*,1) et (X5/u,Y5/v,Z5/w,0).


On a donc par exemple à l'aide des deux premières coordonnées:




s = X5*.u.Y5 - Y5*.v.X5
-------------------
X4.Y5 - X5.Y4


Dépendance linéaire entre C et les projections de M4 et M5


On détermine C' de la même façon.


Nous sommes maintenant ramenés au cas particulier vu au début, le problème est résolu.

3.4.3 Cas de la projection parallèle

Dans ce cas particulier de la projection parallèle, les points C et C' sont rejetés à l'infini dans deux directions D et D' a priori inconnues.

Les calculs pourront donc ici légitimement privilégier les points à distance finie.

Cette fois la reconstruction est possible avec la connaissance de quatre points seulement que nous appelons P1, P2, P3 , P4 et qui forment un vrai tétraèdre. Aucune des homographies envisagées dans le cas général ne nécessite de calculs. L'application m -> M de q dans Q induite par projection parallèle est une affinité, conserve les barycentres (comme tous les rapports au sens de Thalès).


m a donc dans P1,P2,P3 mêmes coordonnées barycentriques que M dans M1,M2,M3.

m' a de même dans P1,P2,P3 les coordonnées barycentriques de M' dans M1',M2',M3'.

Si on connaît M4, M4' et P4, on en déduit m4 et m4', les droites (m4,P4) et (m4',P4) ont les directions D et D' que l'on recherche.


A tout autre couple Mi,Mi' on associera de même mi,mi' par lesquels il suffira de mener les parallèles à D et D' pour obtenir le point objet Pi.

A noter que tous les segments m,m' sont parallèles, l'épipôle e de la théorie est en effet à l'infini dans P1,P2,P3 et l'alignement C,C',e se fait à l'infini.




Rappel:


Les coordonnées barycentriques pour un point M par rapport à M1, M2 et M3 sont les trois nombres X, Y, Z tels que :



--> --> --> ->
X.MM1 + Y.MM2 + Z.MM3 = 0 et X + Y + Z =1.


Définition de coordonnées barycentriques



A noter que (X,Y,Z) interviennent de manière homogène (coefficients barycentriques), la technique "projective" est encore visible ici.


Elles s'obtiennent donc comme nous l'avons déjà vu par :



x x1 x2 x3 X
y = y1 y2 y3 Y
1 1 1 1 Z


Passage en coordonnées barycentriques


3.4.4 Moindres carrés


Si l'on dispose d'un nombre suffisant de points appariés, on peut améliorer l'évaluation de l'homographie entre les plans images et la position des points E et E' par la méthode des moindre carrés lors de la résolution des système linéaires.




Tout modèle linéaire peut être représenté sous la forme






y = X . beta + epsilon
(n,1) (n,p) (p,1) (n,1)





où y est le vecteur des observations

X est une matrice connue fixée

beta est le vecteur des paramètres à estimer

epsilon est le vecteur "erreur" distribué en alpha(0,s2 )


n est le nombre d'observations

p est le nombre de paramètres à évaluer (n>p)





Théorème de Gauss-Markov:

Le meilleur (de variance minimum) estimateur non biaisé de beta est l'estimateur des "moindre carrés".




beta
* = (X'.X)-1 X'y




avec l'espérance


E(beta*) = beta


et la variance


var(beta*) = s2 (X'X)-1


3.5 Expérimentation

3.5.1 Relation entre plans images

Nous avons testé la méthode sur le modèle théorique présenté ci-dessous. Les points ont été choisis arbitrairement sur une figure avec pour seule propriété le fait que les points "homologues" sont sur des lignes passant par les deux centres des faisceaux et dont les intersections deux à deux se trouvent sur une même droite.


Les deux faisceaux de droites de la figure présentent une relation homographique et nous cherchons à calculer les centres épipolaires gauche et droit. Les coordonnées des points gauches et droits sont définies par rapport à deux repères distincts pour les deux zones de l'image.



Fig.3.6: Ensemble de points d'origine sur les plans P et P'


Après avoir calculé l'homographie entre les deux faisceaux de droites avec comme base projective les couples de points (1,2,3,4) et en suivant la méthode présentée précédemment, nous avons recalculé tous les points de la partie droite dans le repère gauche en trois temps:


1) Passage de coordonnées cartésiennes (xd,xd) dans le repère cartésien R2 en coordonnées projectives (Xd,Yd,Zd) dans le repère projectif R2'.

2) Transformation des coordonnées par l'homographie (a,b,c), et obtention des coordonnées (aX,bY,cZ).

3) Passage en coordonnées cartésiennes (Xg,Yg) dans le repère gauche à partir des coordonnées (aX,bY,cZ).




Les tableaux suivants présentent les étapes intermédiaires de notre calcul.



  1. Passage en coordonnées homogènes Pi(X1,Y1,Z1) et Pi':(X2,Y2,Z2) à partir de la base (A1,A2,A3,E) dans chaque repère.

X1

Y1

Z1

X2

Y2

Z2

1.5000

0.0000

0.0000

-0.5000

-0.0000

0.0000

0.0000

-0.3000

0.0000

-0.0000

0.4000

0.0000

0.0000

0.0000

0.2727

0.0000

-0.0000

2.0000

1.0000

1.0000

1.0000

1.0000

1.0000

1.0000

1.5000

1.8000

1.6363

1.8333

1.6000

1.3333

0.0000

0.9000

1.0909

1.8750

1.9500

-0.2500

1.5000

2.7000

2.4545

2.5000

2.4000

0.0000

0.0000

1.5000

1.6363

1.6667

2.0000

-1.3333




  1. A partir de l'ensemble des coordonnées homogènes, nous calculons l'homographie H:(a,b,c) qui transforme les points Pi' de telle façon que les droites (Pi,H.Pi') se coupent en un même point qui est l'épipôle. Nous observons que les contrôles sur les coefficients (a,b,c) et l'erreur des moindre carrés donnent des valeurs nulles, ce qui signifie la résolution exacte du système d'équations.

Homographie: a=-7,3333, b=-2.75, c=1, errmc=0.0000, errcoef=0.0000



  1. Résultat dans le repère cartésien des points obtenus. Les coordonnées (X1,Y1) sont inchangées alors que les coordonnées (X2,Y2) correspondent aux coordonnées des points Pi' transformées par l'homographie et ramenées dans le repère cartésien R1. Nous observons que les trois premier points pris comme référentiel projectif sont bien confondus. Le dernier point du tableau correspond à l'épipôle dans le repère R1.



X1

Y1

X2

Y2

4.0000

4.0000

3.999999

4.000000

2.0000

6.0000

2.000001

5.999999

3.0000

8.0000

3.000000

7.999998

7.0000

12.0000

1.230771

8.153844

10.0000

16.0000

0.769233

8.615382

6.0000

14.0000

-0.470585

8.117645

13.0000

22.0000

-0.499997

8.499997

8.0000

18.0000

-1.999995

7.230767

-4.9999

4.0000

-4.999990

4.000000






Fig 3.7: Résultat sur P après transformation de points de P'



Le résultat présenté sur cette figure est la visualisation graphique des coordonnées des points dans le premier repère et les droites formées par les couples de points homologues. Le centre du faisceau est l'épipôle dans le premier repère. Ce résultat correspond bien au modèle théorique, et les erreurs entre les coefficients de l'homographie, ainsi que les erreurs d'approximation aux moindre carrés sont nulles.


Après cette vérification concluante, il est intéressant d'observer l'influence du choix des points de base des coordonnées projectives (A1, A2, A3) sur la position des points recalculés et la position du centre du faisceau de droites calculé.

Nous avons choisi six combinaisons de points:

. Quatre manuellement en prenant successivement les points (1,2,3), (2,3,4), (3,4,5) et (4,5,6) de la liste des points homologues.

.une combinaison en prenant

A1: M(x,y), M'(x,y) tel que Mx minimum

A2 Mx maximum

A3 My minimum

.une combinaison en prenant les points A1, A2, A3 formant le triangle de surface maximale.

Après application de notre méthode sur ces différentes configurations, nous observons que ces points influencent fortement les résultats en ce qui concerne la position des points recalculés, mais que les centres des faisceaux restent identiques. Ceci montre l'invariance de l'épipôle lorsque l'on change les points de base et confirme la validité de notre méthode de calcul.




Points 1 2 3




Points 3 4 5




Points MIN/MAX X Y




Points 2 3 4




Points 4 5 6




Points surface max


Fig 3.8: Résultat du calcul du centre épipolaire avec différents points


3.5.2 Calcul 3D en projection centrale

Pour tester cette méthode, nous avons généré artificiellement des points dans l'espace et les avons projeté de façon perspective sur deux plans de l'espace par rapport à deux centre optiques. Les valeurs test sont les suivantes:


Centre optiques: Cg(0,0,100) Cd(200,300,200)


Image gauche

Image droite

Coordonnés 3D

-346.34

-230.89

2220.67

1343.15

1000.00

200.00

345.00

74.36

71.44

78.47

66.75

100.00

2.00

3.00

2.19

-0.73

10.35

-1.38

1.00

2.00

3.00

26.70

-20.92

-19.76

1.54

4.00

33.00

2.00

7.37

-5.89

4.50

-2.11

1.00

9.00

4.00

25.78

22.83

33.05

19.96

33.00

2.00

4.00

6.43

3.86

42.12

-28.12

4.00

1.00

45.00

104.48

32.72

50.03

24.67

65.00

34.00

33.00

34.96

15.89

28.65

14.95

32.00

12.00

11.00

3.72

-0.74

11.50

-2.07

2.00

3.00

5.00


Tableau 3.1: Coordonnées de départ dans les plans et dans l'espace


Les résultats obtenus sont les suivants:


Homographie entre l'image homologue et l'image de référence: a= -7.45 b= 0.99

Homographie entre l'image de référence et le plan P: u=-139.35 v= -1.08

Centres optiques: Cg(-0.00,-0.00,100.00), Cd(199.99,299.99,199.99)


Calcul des points dans l'espace


Coordonnées réelles

Coordonnées calculées

ErreurMC

Dist.

1000.00

200.00

345.00

1000.00

200.00

345.00

0.000000

0.0

100.00

2.00

3.00

100.00

2.00

3.00

0.000000

0.0

1.00

2.00

3.00

1.00

2.00

3.00

0.000000

0.0

4.00

33.00

2.00

4.00

33.00

2.00

0.000000

0.0

1.00

9.00

4.00

1.00

9.00

4.00

0.000000

0.0

33.00

2.00

4.00

33.00

2.00

4.00

0.000025

0.0

4.00

1.00

45.00

4.00

1.00

45.00

0.000000

0.0

65.00

34.00

33.00

65.00

34.00

33.00

0.000004

0.0

32.00

12.00

11.00

32.00

12.00

11.00

0.000002

0.0

2.00

3.00

5.00

2.00

3.00

5.00

0.000000

0.0


Tableau 3.2 Résultats des calculs, erreur et distance entre points réels et calculés


Nous observons que les centre optiques ont bien été calculés ainsi que les points dans l'espace. La valeur ErrMC est l'erreur aux moindres carrés issue de l'intersection des deux droites (Ig,Cg) et (Id,Cd) dans l'espace 3D. La valeur Dist est la distance entre points réels et points calculés.

Les résultats montrent un calcul exact de la position des points dans l'espace ainsi que les centre optiques du système de prise de vue, ce qui confirme la démarche théorique décrite précédemment.


3.6 Conclusion

Dans ce chapitre, nous avons présenté une étude de la géométrie de la stéréovision.

Cette étude débouche sur une méthode géométrique qui permet de déterminer la relation entre les plans images d'une part, et d'autre part de calculer les points dans l'espace. Ces résultats correspondent à d'autres recherches menées indépendamment suivant une approche algébrique [FAUG92].

Elle ressemble à la rectification des images stéréoscopiques réalisée en photogrammétrie [HURA60] [CARR71] puisque la transformation réalisée par l'homographie ainsi calculée correspond à celle réalisée par les chambres claires. Ces appareils sont des systèmes optiques permettant de voir à la fois deux objets, l'un étant transformé par réflexion dans un miroir en une image virtuelle, l'autre étant vu directement à travers le miroir précédent à face réfléchissante semi-dépolie. Dans notre méthode, nous utilisons comme centre de projection les centres optiques, et calculons la géométrie épipolaire, alors que la chambre claire utilise le centre du miroir et l'oeil de l'observateur en réalisant un redressement approximatif. On peut envisager un intérêt potentiel de notre algorithme dans le domaine de la photogrammétrie.



1) La relation entre les plans images peut être définie par une méthode linéaire grâce à la connaissance de huit couples de points homologues sur les deux images. Une surdétermination du système d'équations permet une résolution aux moindres carrés qui donne une meilleure stabilité des résultats ainsi qu'un indice de validité de ce résultat. Cette technique est particulièrement utile à la mise en correspondance des images stéréoscopiques, qui concerne le chapitre 5 de ce rapport.

2) Le calcul des points est possible dans un espace projectif sans connaissance des points dans l'espace cartésien, et le calcul des coordonnées cartésiennes en 3D nécessite la connaissance cinq points dans l'espace pour la projection centrale de quatre pour la projection parallèle. L'utilisation de notre technique est réalisée dans le chapitre 6.

Notre méthode donne des solutions exactes pour les points générés artificiellement. Son application à des images réelles suppose qu'elle soit résistante au bruit qui résulte des imprécisions d'appariement, de la déformation des plans images et dans une moindre mesure de la discrétisation des plans images. Nous aborderons l'influence du bruit sur l'exactitude des reconstructions dans le chapitre 6.


Ces aspects ouvrent des perspectives de travail à partir des modèles présentés pour éventuellement aboutir à des algorithmes de correction des plans images suivant les modèles de déformation [TOSC87] [ALIR85], soit en modifiant les équations, soit par des méthodes itératives destinées à minimiser les erreurs d'autocontrôle des coefficients de l'homographie en 2D, et les résidus pour les approximations aux moindre carrés.





4. Extraction des contours

La mise en correspondance d'images suppose le traitement d'une quantité énorme d'informations que l'on est tenté de réduire pour ne garder qu'une partie nécessaire à l'élaboration d'une méthode de fusion de deux images stéréo.


Cette simplification des images est basée sur des indices visuels [AYAC89] qui contiennent de manière concise des informations importantes pour le traitement des images.


Notre chaîne de traitement nécessite la détermination de points homologues suffisamment précis pour que l'on puisse s'appuyer sur ceux-ci afin de calculer la correspondance entre les deux images du couple stéréo. Cette relation entre les deux images est utilisée pour diminuer le calcul nécessaire à la fusion des images, en se basant sur un modèle géométrique épipolaire qui donne les contraintes géométriques entre les images issues des conditions de prise du vue. Ces contraintes facilitent les algorithmes de traitement d'image, limitent les calculs et permettent d'évaluer la fiabilité des résultats obtenus.


Différentes approches existent pour extraire des points homologues entre deux images, les principales sont de mettre en correspondance des régions d'images homologues (ou zones de l'image homogènes au sens d'un certain critère), ou de comparer les contours des objets (ou zones de transition entre régions homogènes) contenus dans les images.

C'est cette dernière approche que nous avons choisie car elle nous permet d'avoir des points homologues assez précis sur lesquels nous nous appuierons pour initialiser le processus de mise en correspondance des images. Le nombre de couples de points homologues nécessaires à l'étape suivante de notre chaîne de traitement étant limité, ceci ne nous oblige pas à chercher à extraire la totalité des contours, mais plutôt un ensemble d'éléments suffisamment caractéristiques pour apparier le nombre nécessaire de points.


La technique d'appariement s'appuie sur un critère de forme qui doit être suffisamment localisé pour obtenir une correspondance entre des pixels des deux images. Il est donc utile de coder les contours d'une manière qui permette d'obtenir cette précision d'appariement et de s'affranchir d'une part des problèmes de rotation d'une image par rapport à l'autre et dans une certaine mesure d'éventuelles variations de la taille des objets entre les deux images d'autre part.


Après une description des caractéristiques des contours, nous citerons les familles d'extracteurs de contours et nous décrirons le codage de Freeman [FREEMA] que nous avons choisi pour représenter les contours.

4.1 Différents types de contours

Les contours d'une image correspondent aux discontinuités de l'intensité lumineuse.


Dans les images optiques, cette intensité est fonction de trois paramètres:

- I:l'intensité lumineuse incidente

- n:le vecteur normal à l'élément de surface

- R:la réflectance de l'élément de surface.


Les contours correspondent à la discontinuité d'un ou de plusieurs de ces paramètres.


- Occultation: C'est la discontinuité de la normale, de la réflectance ou de l'éclairage incident due à l'occultation partielle d'un objet par un autre.

- Arêtes: Ceci correspond aux discontinuités de la normale sur une surface continue, c'est à dire aux changements brusques d'orientation de la surface de l'objet.

- Marques: Ce sont les discontinuités de la réflectance de la surface, comme des tâches ou des changements de constituant d'une surface continue.

- Ombres: ce sont les discontinuité de l'intensité de l'éclairage incident, qui correspondent à l'occultation de la lumière incidente par un objet.

Les arêtes et les marques sont intrinsèques, c'est à dire invariantes ou presque par changement de point de vue, ce qui est une propriété importante en stéréovision. Les ombres sont intrinsèques si l'orientation de la source lumineuse par rapport à la scène ne change pas entre les prises de vue.

Les occultations dépendent du point de vue et peuvent poser des problèmes. Ils donnent lieu à des contours apparents, c'est à dire que l'on calcule des contours à partir d'ensembles de points qui ne sont pas les mêmes d'une image à l'autre (ex: image stéréo d'une sphère dans l'espace).

4.2 Caractéristiques des contours

Les caractéristiques d'un contour sont:


- La continuité des points contours d'un objet. Un contour est représenté par une chaîne connexe de points sur l'image. Il est possible de caractériser la forme des contours et d'utiliser des méthodes de reconnaissance de forme pour les comparer entre eux. L'utilisation du voisinage ou contexte d'un point contour donne des informations de forme et d'orientation.

- Epaisseur d'un pixel: les contours représentent les frontières des objets. Il est important d'évaluer avec précision la position du contour de l'objet et de la représenter par un seul point qui correspond à la zone de variation maximale de la luminance.

- La direction du contour est orthogonale à celle du gradient. Le contour correspond à la frontière de l'objet et la variation de luminance est perpendiculaire au contour sur l'image.

- Robustesse au bruit: il faut éliminer les points qui du fait des imperfections du système de prise de vue présentent les caractéristiques d'un contour, afin d'obtenir un contour aussi proche que celui obtenu sans influence du bruit.

4.3 Méthodes d'extraction de contours

De nombreux auteurs se sont penchés sur le problème de l'extraction de contours.


Un point contour étant caractérisé par un fort gradient ou variation de l'intensité lumineuse, le premier opérateur de détection de contour qui fut développé par Robert est une application directe de la formule d'une dérivée. Il est formé de deux masques H1 et H2 donnant le gradient respectivement dans les directions PI/4 et 3PI/4 :



0 1 1 0
H1 =
H2 =
-1 0 0 -1


L'application de ces deux masques pour un point M(x,y) de l'image donne g1 et g2.


L'amplitude est donnée par


g (x,y) = sqrt( g12 + g22 )


que l'on peut approximer par:


g (x,y) = | g1 | + | g2 |


La direction du gradient est fonction de l'arc-tangente entre g1 et g2


dg = arctg ( g2 / g1 ) -PI/4


Cet opérateur est très localisé, et donc très sensible au bruit, qui nuit gravement à la qualité de l'approximation des contours.


Dans la plupart des techniques proposées, plusieurs opérateurs locaux de dérivation du premier ordre et du second ordre sont utilisés suivis respectivement par une recherche des maxima locaux et de passages par zéro [BALL82]. Ces opérateurs effectuent le filtrage et la dérivation de l'image localement, d'où leur nom de filtre à réponse impulsionnelle finie (FIR). Les plus connus sont les filtres de Prewitt et de Sobel.


Depuis quelques années, une nouvelle approche est proposée, basée sur des filtres à réponse impulsionnelle infinie (IIR). L'approche de Canny [CANN86] est basée sur un opérateur optimal en fonction d'un critère basé sur la détection et la localisation. Les travaux de Deriche [DERI87] [DER'87] et Shen et Castan [SHEN91] ont repris cette démarche et proposé des opérateur plus simples et présentant de meilleurs indices de performance.


Pour obtenir à partir d'images souvent bruitées, des contours correspondant aux caractéristiques énoncées dans le paragraphe précédent, les algorithmes comprennent plusieurs étapes qui peuvent être confondues lors de l'implémentation des algorithmes:


- Filtrage passe-bas afin d'atténuer l'influence du bruit dans les images.

- Détection de contours: extraction d'un ensemble de points présentant les caractéristiques d'un contour.

- Localisation des contours: à partir de l'ensemble précédent, détermination de la position du contour et élimination des faux contours.

- Chaînage des points contours.

4.4 Chaînage et codage

L'étape de chaînage consiste à relier les points contours connexes obtenus à l'étape précédente, soit à partir des maxima locaux dans la méthode de Deriche, soit les passages par zéro du Laplacien pour Shen et Castan.

Dans la méthode de Shen et Castan, ces contours sont formés et chaînés au fur et à mesure du choix des meilleurs chemins dans le graphe.


Le chaînage est suivi d'un codage du contour soit point par point, soit par des polygones, voire des arcs ou courbes paramétrées.


Le codage que nous avons choisi est celui de Freeman [FREEMA] qui va nous donner par son alphabet un critère de similarité nous permettant de mettre en correspondance les contours de deux images stéréoscopiques. Son principe est de décrire les arcs formant un contour par une suite de vecteurs de taille élémentaire et de direction choisie dans un ensemble fini. La direction d'un arc est codée par une valeur comprise entre 0 et 7 dans le sens trigonométrique comme le montre la figure suivante.




Fig.4.1: Principe du codage de Freeman


L'écart entre deux valeurs du codage de Freeman représente 45° ce qui est assez imprécis, et la longueur des segments correspondant aux directions (0,2,4,6) est de un pixel alors que la longueur des segments de direction (1,3,5,7) est de 1.414 pixels ce qui entraîne une variation du nombre d'éléments codant une longueur donnée suivant l'orientation du segment de contour. Cependant, dans le cas d'une mise en correspondance, ces désavantages peuvent être atténués si l'on choisit des points de correspondance dans les zones de changement de direction. Cette méthode est de toute façon moins critique que la mise en correspondance de courbes ou de segments de droites pour lesquels l'approximation exacte nécessite une extraction et une segmentation optimales des contours sur les deux images homologues.


Le problème de la rotation d'une image par rapport à l'autre peut être résolu en utilisant un codage relatif des arcs du contour comme le montre la figure suivante qui présente le codage absolu et relatif d'un même contour.




Fig.4.2: Codage de Freeman en absolu et en relatif


Dans cet exemple chaque direction est codée par rapport à la direction précédente. Cette méthode est trop localisée et affaiblit le codage en tant que critère de similarité entre deux contours. En effet, la direction entre deux arcs successifs variera en général d'une unité de direction à cause du lissage des contours par les algorithmes utilisées. Nous avons donc choisi le codage d'un arc i par rapport à l'arc i-k en choisissant k entre 5 et 20 pour bénéficier à la fois de l'ensemble des valeurs de codage possibles et du codage relatif d'un arc. Pour un arc i, i=1..nombre d'arcs, la fonction de codage relatif R à partir des valeurs absolues A est:


SI (i<k+1) ALORS R[i]=A[i];
SINON {R[i]=A[i]-A[i-k];
SI R[i]<0) ALORS R[i]=8-R[i];}


Ainsi la chaine codée en absolu: (0,7,0,1,0,6,5,4,6,3,2) est codée (0,7,1,1,7,6,7,7,2,5,7) pour k=1 et (0,7,1,1,7,6,6,4,5,3,4) pour k=5.


Les résultats présentés dans le chapitre suivant montrent que notre choix constitue un bon compromis qui permet une bonne caractérisation des couples de points homologues, confirmée par la qualité de la mise en correspondance des images.

4.5 Expérimentation

Nous avons testé les méthodes de Deriche et de Shen et Castan sur trois types d'images: images de caméra, images optiques de photographie aérienne et images de microscopie électronique.

Le résultat des traitements effectués est présenté ci-dessous, les contours sont ensuite codés sur l'alphabet de Freeman en relatif en choisissant un sens de codage orienté par rapport au gradient.




Image originale




Méthode Deriche

Méthode Shen et Castan




Fig. 4.3: Exemple de contours d'images de caméra (pyramide)




Image originale




Méthode Deriche

Méthode Shen et Castan




Fig.4.4: Exemple d'images de photographie aérienne (Belle Ile)




Image originale




Méthode Deriche

Méthode Shen et Castan




Fig.4.5: Exemple d'images de microscope à balayage (calcite)









4.6 Conclusion


Nous avons extrait les contours des images test selon les méthodes de Deriche d'une part, et de Shen et Castan d'autre part. Les résultats obtenus sont similaires avec une exécution plus rapide pour la méthode de Shen et Castan. Un affinage des seuils permettrait d'améliorer la qualité des contours obtenus, cependant les résultats sont suffisant pour les étapes suivantes de la chaîne de traitement.

Dans le travail présenté, l'extraction de contour est surtout un moyen d'obtenir des points homologues entre deux images stéréoscopiques afin de préparer les étapes de calibration du système de prise de vues et de mise en correspondance des deux images. Il n'est donc pas nécessaire d'obtenir le maximum de contours sur une image mais plutôt d'extraire les contours les plus fiables possibles. Un nombre trop élevé de contours serait un désavantage par l'explosion combinatoire de la recherche de correspondance entre contours homologues.


D'autre part, les modèles utilisés pour rehausser les contours ne sont pas forcément optimaux pour des images de microscopie électronique, puisque les contours qui présentent un pic lumineux importants, n'ont pas exactement les mêmes propriétés que ceux d'images optiques, et les propriétés statistiques du bruit ne sont pas les mêmes que pour les images optiques (bruit blanc).


Nous avons donc testé ces deux détecteurs de contours sans les affiner puisque le plus important était d'obtenir une chaîne de traitement complète. Il sera intéressant de tester l'enchaînement de différents filtrages (Sobel, Deriche ou Shen & Castan) avec les méthodes de sélection de points ( max local, Laplacien ou programmation dynamique) afin de déterminer pour chaque type d'image la solution la mieux adaptée.




5. Mise en correspondance











La mise en correspondance de deux images stéréoscopique se divise en deux étapes principales:

1) l'extraction de points homologues appelés amers qui servent à initialiser le processus de mise en correspondance

2) l'élargissement de la correspondance à l'ensemble des deux images appelée fusion des images dans la suite de ce chapitre.


La détermination des points amers se fait en trois phases:


1) Mise en correspondance des contours suivant des critères de forme. Cette phase détermine un sous ensemble de contours homologues potentiels et définit une correspondance point à point entre ceux-ci.

2) Application de contraintes géométriques sur les couples de contours en s'appuyant sur les correspondances de points définies lors de la phase 1. Cette phase permet d'éliminer les appariements aberrants et de limiter le combinatoire de l'étape suivante.

3) Choix du meilleur sous ensemble de couples de contours et extraction sur ces contours des points amers les plus fiables. Cette phase élargit la contrainte géométrique à plusieurs contours et prend en compte leurs positions relatives sur les deux images.


La fusion des deux images se fait en deux phases:


1) Recalcul d'une image par rapport à l'autre afin de superposer les droites épipolaires homologues. Cette phase utilise la géométrie épipolaire décrite dans le chapitre 3 et corrige l'image homologue par rapport à l'image de référence afin de faciliter le traitement de la phase suivante.

2) Mise en correspondance des droites épipolaires homologues pour obtenir la correspondance point à point entre les deux images homologues. Cette phase fait appel aux techniques de programmation dynamique entre droites épipolaire, en utilisant comme critère de similarité la luminance des points homologues qui est supposée identique.

Dans la suite de ce chapitre, nous présentons les cinq phases successives qui mènent à la mise en correspondance des images.

5.1 Appariement de contours

Les contours extraits de l'étape présentée dans le chapitre précédent ont été codés sur l'alphabet de Freeman. Cette représentation permet d'élaborer un critère de ressemblance entre contours, basé sur les directions successives des arcs formant le contour.


Cette phase a pour but de "proposer" des appariements suivant un critère de forme basé sur la direction des arcs successifs qui forment un contour. La direction d'un arc est calculée relativement à celle d'un arc précédent pour s'affranchir du problème de rotation d'une image par rapport à l'autre. Nous avons présenté cette technique en lors de la définition de l'alphabet de Freeman.

La figure suivante présente un exemple d'appariement rejeté du fait d'une trop grande disparité de forme et un exemple d'appariement potentiel du fait de la ressemblance des deux contours.






Figure 5.1: Appariement suivant le critère de forme



Pour simplifier le problème de mise en correspondance des contours, nous considérons plusieurs hypothèse :


1) Les contours sont ouverts, ce qui permet de définir leur début et leur fin et de conserver une relation d'ordre entre les points homologues des deux contours.

2) Chaque contour extrait est orienté. Le gradient représentant une variation d'intensité lumineuse, la luminance est plus forte d'un côté du contour que de l'autre. Le début et la fin des contours doivent se correspondre pour que les contours soient codés dans le même sens.

3) La taille de l'objet observé est similaire sur les deux images homologues.

Nous proposons de prendre comme critère de ressemblance la différence de direction entre les arcs homologues des contours. La minimisation de la somme des différence nous donne la correspondance entre les points des contours homologues. Elle peut être évaluée par des algorithmes de recherche de chemin de coût minimum dans un graphe valué dont les noeuds sont les correspondances entre points des deux contours, et les arcs les différences de direction des arcs entre points successifs des deux contours. Ainsi, une suite d'orientations relatives semblable pour les deux contours détermine une zone de valeurs nulles dans la matrice.


Il est donc possible de mettre en correspondance les phrases représentant les contours par des méthodes de comparaison dynamiques de chaînes. Ces méthodes sont basées sur le principe de distance d'édition entre chaînes qui permet d'obtenir une fonction de ressemblance entre contours. Les techniques de programmation dynamique sont présentées dans l'ouvrage de Miclet [MICL84], notamment l'algorithme de Wagner et Fisher que nous décrirons dans la première section de ce chapitre.

5.1.1 Distance d'édition entre contours


a) Principe de la distance d'édition


On définit trois opérations élémentaires possibles dont les combinaisons permettent de transformer une chaîne en une autre:


La substitution: a -> b coût: k(a,b)


L'insertion : 0 -> a coût: k(0,a)


La destruction : a -> 0 coût: k(a,0)


La phrase x=ab est transformée en y=bac par les opérations élémentaires:

(0 -> c), (b -> 0), (c -> b), (0 -> c).


Un méthode de transformation peut être la suite de phrases:

ab, cab, ca, ba, bac.


Le coût total de cette transformation est:

k(0,c) + k(b,0) + k(c,b) + k(0,c).


La distance d'édition d(x,y) (ou distance de Levenstein) entre les deux phrases est le coût de la suite de transformations élémentaires la moins coûteuse pour transformer x en y.

b) Adaptation au codage des contours

Si l'on considère les contours codés sous forme de chaînes de Freeman, nous pouvons calculer une distance d'édition entre les contours. Les coûts sont définis comme suit:


1) La substitution aura comme coût l'écart de direction entre arcs. Soit pour les direction u et v appartenant à {0,..,7}:

k[u,v] = abs(u - v);
Si abs(u - v)>4 ALORS {k[u,v] = 8 - abs(u - v);}


Formule du coût pour le calcul de la distance d'édition


2) L'insertion et la destruction auront pour valeur la différence de direction entre l'élément courant et l'élément inséré ou détruit, suivant la même formule que la substitution.

Les chaînes étant orientées, l'algorithme revient à chercher de la même façon un chemin de coût minimum dans un graphe d'état représenté par une matrice dont l'élément courant d(i,j) représente la distance optimale entre

x(i) = a1 ... ai et y(j) = b1 ... bj.

c) Algorithme de Wagner et Fisher

L'algorithme de Wagner et Fisher calcule la distance d(x,y) dans une matrice [m,n]. Il se présente comme suit:


1) D(0,0) = 0

2) Pour i := 1 à n

Faire D(i,0) := D(i-1,0) + k(ai,0)

3) Pour j := 1 à m

Faire D(0,j) := D(0,j-1) + k(0,bj)

4) Pour i := 1 à n

Pour j := 1 à m

Faire m1 := D(i-1,j-1) + k(ai,bj)

m2 := D(i-1,j) + k(ai,0)

m3 := D(i,j-1) + k(0,bj)

D(i,j) = MIN (m1, m2, m3)

5) Distance d'édition d(x,y) = D(n,m)


Les phases 1,2,3 correspondent à l'initialisation de la première ligne et première colonne de la matrice.

La phase 4 correspond au remplissage de la matrice suivant les coûts définis.

La phase 5 correspond au calcul du coût aux valeurs x et y.

La complexité de cet algorithme est en O(n m).

d) Programmation

La mise en oeuvre de l'algorithme présenté dans le paragraphe précédent est légèrement plus complexe pour obtenir des informations supplémentaires nécessaires au choix des meilleurs contours homologues à un contour donné.

La structure de donnée est une matrice dont chaque élément comprend quatre informations:

- Le coût local calculé comme décrit dans le premier paragraphe de ce chapitre.

- Le poids courant du chemin de mise en correspondance.

- Le nombre de sommets courants, c'est à dire la longueur courante du chemin de correspondance.

- Le nombre courant de diagonales dans le chemin, c'est à dire les zones de correspondance point à point entre les contours.

L'algorithme se déroule en cinq temps:


1) Initialisation de la matrice des poids locaux

2) Initialisation de la première ligne et la dernière colonne:
poids_courant:=0; nb_sommets:=1; nb_diago:=0;
(étapes 1, 2 et 3 de l'algorithme décrit)

3) Calcul des matrices poids_courant, nb_sommets et nb_diago.
En comparant les poids locaux des cases voisines en haut, en haut à droite, et à droite de la case courante, on choisit le poids courant le plus faible (en privilégiant la diagonale en cas d'égalité).
Lorsque le voisin PRED est choisi, les valeur courantes deviennent:
. Nb_sommet := PRED.nb_sommets + 1,
. Poids_courant := PRED.poids_courant + poids_local,
. SI la diagonale a été choisie ALORS Nb_diago:=PRED.nb_diago+1

4) Recherche du départ du meilleur chemin dans la matrice, c'est à dire la case de poids minimum, et de nombre de diagonales maximum. Cette recherche s'effectue sur la première colonne et la dernière ligne de la matrice.

5) Remontée du chemin jusqu'à la dernière colonne ou la première ligne de la matrice. Codage de la correspondance entre les contours. La figure suivante présente le chemin de correspondance entre les contours gauche et droit. La suite des directions du contour gauche forme les ordonnées, et les directions du contour droit les abscisses. Le chemin permet de définir la correspondance entre les deux contours en mettant en relation l'abscisse (point gauche) et l'ordonnée (point droit) du point du chemin de correspondance. Ce chemin est lui aussi codé dans l'alphabet de Freeman (0, 1, 2). Une valeur 0 signifie qu'un point gauche a deux points correspondants à droite et une valeur 2 met un point droit en relation avec deux points à gauche. Les diagonales du chemin de correspondance codées avec la valeur 1 correspondent à une correspondance unique entre les points gauches et droits. Les suite de valeurs 1 dans la codage du chemin sont des zones de bonne correspondance entre les contours.



Fig.5.2: Chemin de correspondance entre les contours


Cette technique nous donne un bon critère de ressemblance de formes entre deux contours par le coût du chemin formé de la somme des différences d'orientations des arcs homologues des deux contours, et le rapport entre le nombre de diagonales du chemin et sa longueur totale.

e) Optimisation de la méthode

Dans le principe présenté au paragraphe précédent, la recherche du meilleur chemin se fait entre tous les points des contours. Cette méthode est très gourmande en place mémoire et temps de calcul. Si on ne compare que des contours de taille proche, il est alors possible d'optimiser la méthode en ne calculant les chemins que dans une bande de la matrice si l'on considère que l'écart entre les indices des points homologues des deux contours ne peut dépasser la différence de longueur entre les deux contours. Il faut alors gérer en plus d'une matrice contenant l'ensemble des zones de recherche, un vecteur de décalage de chaque ligne par rapport à la précédente.


La figure suivante présente la zone de recherche du meilleur chemin dans la matrice.


Fig.5.3: Limitation de la zone de calcul dans la matrice de correspondance


Côté du carré de départ:

h = (% de différence maxi) * (min de longueur des deux contours)


Largeur de la bande:

B = ( h * ( X + Y - 2h ) ) / ( Y - h )


Décalage entre deux lignes consécutives:

d = ( X - B ) / ( Y - 2h )


Borne supérieure des décalages à partir de laquelle le décalage est maximum:

S = ( Y - h )


Les figures suivantes présentent les meilleurs chemins de correspondance entre contours. La première calcule la correspondance d'un point sur toute la longueur du contour homologue, et la deuxième limite la recherche dans une fenêtre limitée à un certain pourcentage de longueur. Les niveaux de gris correspondent à la disparité d'orientation des contours. Plus un point de la matrice de correspondance est sombre, plus l'orientation locale des contours est semblable, et donc meilleure est la correspondance locale. Le chemin de correspondance entre les arcs des contours est présenté en blanc et se déplace du haut à gauche vers le bas à droite de la figure. Nous observons que le chemin calculé est le même dans les deux cas, avec un gain en temps de calcul d'un facteur 3 pour la deuxième méthode puisqu'il n'est réalisé que sur une partie de la matrice.




Fig.5.3: Chemin de correspondance entre contours (méthode globale)




Fig.5.4: Chemin de correspondance entre contours (fenêtre de recherche)


5.1.2 Algorithme de mise en correspondance

L'algorithme présenté dans le paragraphe précédent donne la distance d'édition entre deux contours quelconques. Il fournit le coût, la longueur du chemin de correspondance et le nombre de diagonales dans ce chemin. Le chemin est codé dans l'alphabet de Freeman, et comprend des valeurs 0, 1 ou 2.


La recherche des contours homologues est effectuée entre des contours de longueur comparable pour éviter des calculs importants dûs à une explosion combinatoire, mais aussi pour optimiser la recherche du meilleur chemin de correspondance, comme présenté dans le paragraphe précédent.

Les tests ont porté sur des contours ne différant pas de plus de 5 à 20 pour-cent de longueur entre eux.


Si l'on recherche les contours homologues entre deux ensembles E1 et E2 comprenant respectivement N1 et N2 contours, le principe de l'algorithme est le suivant:


- Calcul de la distance d'édition entre les contours de longueurs comparables (cf paragraphe précédent).

- Mise en mémoire dans une matrice N1 * N2 (contours gauches * droits). La matrice obtenue est une matrice creuse qui mémorise les résultats des calculs précédent, ci-dessous, un exemple est présenté avec les valeurs des distances d'édition calculés. Les case vides correspondent aux appariements non calculés du fait d'une trop grande disparité de longueur entre contours.

- Recherche des coûts ligne minima qui soient en même temps minima colonne. Ceci revient à chercher les contours de l'ensemble E1 et E2 qui soient respectivement les meilleurs appariement l'un pour l'autre dans chacun des ensembles.



1 2 3 4 5 6 7 8 9

┌───────────────────────────────────┐

1 . . . . 12 23 10 . .

│ │

2 . 34 . 23 6 12 3 . .

│ │

3 4 . . 10 . . . . .

│ │

5 5 . 10 . . . . . 23

│ │

6 89 . 67 . . . . 45 .

│ │

7 . 45 . . . . . . .

└───────────────────────────────────┘


Matrice des distances d'édition

taille N1 * N2


Dans l'exemple présenté ci-dessus, les contours retenus seront:


Numéro ligne 2 3 6

Numéro colonne 7 1 8

Coût 3 4 45



Il est possible d'optimiser la méthode présentée dans le paragraphe précédent et d'éviter l'utilisation d'une matrice pour mémoriser les résultats. L'algorithme présenté ci-dessous a le même effet mais utilise moins de place mémoire et est plus rapide.



Fig.5.6: Structure des données pour la mise en correspondance des contours



Algorithme optimisé:


1) Tri des contours gauches et droits par ordre croissant de longueur et mémorisation sous forme de chaînes de Freeman dans deux tableaux de données. Un troisième tableau, indicé comme l'ensemble des contours gauches, mémorise le chemin de correspondance entre le contour gauche et son meilleur homologue à droite, ainsi que le poids du chemin et le nombre de diagonales du chemin.

2) Calcul de la distance d'édition des contours de longueur proche. On calcule une correspondance de chaque contour gauche avec tous les contours droits répondant au critère:lg_droit-(lg_gauche * C%) < lg_gauche < lg_droit+(lg_gauche * C%).
Avec : lg_gauche, lg_droit:longueur des contours gauche et droit, et C% : pourcentage de tolérance de longueur entre les contours.

3) Mémorisation des couples de contours qui ont réciproquement pour meilleur correspondant l'autre contour. Le critère de ressemblance se fait sur le poids du chemin de correspondance et le nombre de diagonales du chemin. Pour les deux contours, si la correspondance est meilleure que celle calculée précédemment avec un autre, on déchaîne les deux contours précédemment liés. Si la correspondance est meilleure pour les deux contours gauche et droit, ou qu'ils n'étaient liés à aucun autre contour, on chaîne les contours gauche et droit par le troisième tableau présenté dans la figure précédente.

4) A la fin du traitement, seul les contours respectivement les plus proche au sens de la distance de Levenstein sont chaînés entre eux. On obtient ainsi une première sélection des appariements entre contours.

5.2 Contrainte géométrique de forme

Dans la section précédente nous avons présenté une méthode de mise en correspondance de contours basée sur un critère de forme. Cette technique représente la première phase de l'appariement des contours. Les résultats à ce stade du traitement montrent une majorité de bons appariement, mais aussi quelques erreurs de mise en correspondance. La deuxième phase de l'appariement des contours des deux images consiste à faire intervenir la contrainte géométrique liée au modèle des images stéréoscopiques. Le modèle géométrique des images stéréoscopiques a été présenté dans le chapitre 3 de ce rapport.

Ce traitement s'applique aux couples de contours appariés dans la première phase de la mise en correspondance. Pour chaque couple de contours nous disposons d'un ensemble de points appariés qui sont définis par le chemin coût minimum évalué dans l'algorithme de Wagner et Fisher.

Nous choisissons un sous ensemble de 8 couples de points et nous appliquons la méthode décrite dans le chapitre 3 sur l'ensemble des points du contour homologue. L'épipôle obtenu est peu significatif car très instable, cependant d'une part l'autocontrôle sur les variables liées nous donne une idée de la validité de la relation, d'autre part la somme des distances entre chaque point et son homologue transformé par l'homographie calculée, que l'on peut assimiler à la surface de disparité des deux contours donne un critère intéressant de similarité.


Propriétés:

Si les contours sont plans dans l'espace et les appariement point à point correctement effectués dans la phase précédente, alors après projection sur un même plan de l'espace par rapport à leur centre optique respectif, ils coincident exactement.

S'ils ne sont pas plans, alors la disparité de leur projection est liée à un écart par rapport à un plan de l'espace.


Ces propriétés découlent de la géométrie décrite dans le chapitre 3. Nous réalisons le calcul en trois étapes:


1) sur les deux contours appariés, trois couples de points homologues sont utilisés comme base projective (le point unitaire est le barycentre de ces trois points). Les trois points sur chaque contour ne doivent pas être alignés. Ils sont choisis dans des zones de variation d'orientation sur les contours pour la précision de position, et doivent former les triangles de surface maximale pour la stabilité des calculs (maximisation du rapport distance_entre_points / erreur_de_discrétisation).

2) les coordonnées des points des deux contours sont transformées en coordonnées projectives par rapport à leur référentiel respectif.

3) l'homographie qui permet d'aligner les points homologues avec les points du premier contour est calculée suivant la méthode décrite dans le chapitre 3. Nous obtenons deux informations qui constituent le critère de similarité : l'erreur sur l'autocontrôle des coefficients de l'homographie et la somme des distances entre couples de points recalculés.

Le critère de validité des appariements entre deux contours est formé par:


a) l'erreur sur les coefficients: cette valeur est obtenue en calculant les incohérences entre les valeurs calculées en résolvant le système linéaire à six variables liées dont on tire les coefficients a et b de l'homographie. Cette valeur erreur_coef est donc utilisée pour éliminer les appariements "suspects". Les appariement donnant des erreurs supérieures à un seuil fixé sont considérés comme faux.

b) la somme des distances entre chaque point du contour de référence et son point homologue recalculé. Cette distance est mémorisée pour chaque appariement, puis triée par ordre croissant pour préparer l'étape suivante.


Dans cette étape, nous avons calculé les erreurs liées à la géométrie des images sur les appariements de contours issus de la première étape du filtrage, nous ne gardons que les appariements dont les erreurs sur les coefficients sont inférieurs à un seuil.

Pour les couples de contours satisfaisant à l'autocontrôle sur les coefficients, nous trions leur surface de disparité par ordre croissant. On peut être ainsi assuré que les distances minimales correspondent à des contours relativement plans dans l'espace pour lesquels l'appariement point à point a été correctement réalisé lors de la phase 1.


La figure suivante présente un exemple d'appariement rejeté et d'un appariement considéré comme exact.



Figure 5.7 Appariement par contrainte géométrique locale


5.3 Cohérence géométrique de position


L'étape précédente nous fournit un ensemble de contours appariés après application du critère géométrique localement. Dans cette phase, nous nous intéressons au sous ensemble de contours qui respectent au mieux la contrainte épipolaire et qui minimise la distance entre tous les points pour l'ensemble de couples de contours. La figure suivante présente un ensemble d'appariement de couples de contours homologues considérés comme faux et un ensemble considéré comme vrai.



Figure 5.8 Appariement par contrainte géométrique globale



Cette méthode fonctionne comme celle du paragraphe précédent. La différence réside dans le choix des points de la base projective sur trois contours différents. Le calcul de la distance entre points homologues après application de l'homographie sur l'image homologue nous donne un critère de similarité basé sur la position des contours dans les deux images.

Nous recherchons le meilleur ensemble de contours appariés au sens de ce critère en calculant de façon combinatoire les surfaces de disparité entre des sous ensembles de couples potentiels dans l'ensemble issu de la phase précédente. Le sous ensemble est limité à cinq couples de contours, ce qui est suffisant pour garantir une dispersion des points dans les images. La base projective s'appuie sur les trois points du sous ensemble formant le triangle de surface maximale sur l'image de référence.

Pour éviter une explosion combinatoire, nous limitons le nombre de couples considérés. Dans nos expérimentations, nous ne considérons que les huit appariements de distances minimales et nous recalculons l'homographie engendrée par leurs appariements cinq par cinq. Le meilleur résultat constitue l'ensemble résiduel de points qui seront utilisés dans les phases suivantes. Cette méthode est un bon compromis, car elle évite un excès de combinatoire et fournit un ensemble résiduel de points suffisant pour obtenir une bonne approximation d'une relation entre les deux images qui permettra le recalcul présenté dans le chapitre suivant.


A la fin de cette phase de la mise en correspondance, nous disposons d'un ensemble de points amers sur les deux images et de l'homographie calculée suivant la méthode du chapitre 3, ainsi qu'une base projective qui utilise les points amers les plus dispersés sur l'image de référence.

5.4 Algorithme d'extraction d'amers

Ce paragraphe résume les différentes étapes de l'algorithme. Dans notre description des critères de sélection nous emploierons le terme de distance, bien que les critères définis pour les contraintes épipolaires n'aient pas ses propriétés, car par exemple d(a,b)<>d(b,a). Cet abus de langage permet d'exprimer les contraintes sous une forme parlante souvent utilisée par les auteurs. L'orientation de la distance entre les contours des images met en relief le fait que notre méthode se base sur une image qui servira de référence. La deuxième image du couple stéréo sera calculée par rapport à celle-ci.



Les trois critères de sélection sont dans leur ordre d'apparition:


- Distance de Levenstein d1(Ca,Cb) entre les contours des images A et B de longueur semblable. Cette distance est un indice de ressemblance des formes de contours deux à deux.

- Distance épipolaire locale d2(Ca,Cb) entre les contours potentiellement homologues pris deux à deux. Cette distance est intéressante car si on suppose que chaque contours est relativement plan, le recalcul du contour Cb de l'image B se superposera avec son homologue Ca sur l'image A.

- Distance épipolaire globale d3(Cai,Cbj) entre cinq couples de contours homologues. Le meilleur sous-ensemble de cinq couple est conservé parmi ceux issus de l'étape précédente. Cette étape nous donne une homographie entre les deux images basée sur un plan moyen passant par les contours sélectionnés.


Au niveau calculatoire, il est intéressant d'évaluer le combinatoire et les techniques choisis pour le limiter. Les images de microscopie testées ont environ 40 contours.


- La distance d1 est calculée sur 40x40=1600 couples potentiels. On limite le combinatoire sur un critère de similarité de longueur entre contours testés. A la fin de cette étape on obtient 15 couples de contours potentiellement homologues.

- La distance d2 s'applique sur ce sous ensemble. L'élimination des couples se fait sur le critère des erreurs de coefficients lors du calcul de l'homographie entre contours. Après cette étape on dispose de 10 couples fortement potentiels, triés suivant leur distance d2.

- La distance d3 est calculée sur les huit couples de distance minimale de l'ensemble précédent. Les cinq couples les plus homogènes forment le résultat final.

5.5 Résultats

Nous avons testé cette méthode sur les types d'images utilisées pour l'extraction de contours.


Les résultats sont en général satisfaisants comme le montrent les images présentées ci-dessous. Des problèmes surgissent sur des images comportant peu de contours ou sur des contours mités, peut être du fait de la non optimisation des critères d'extraction de contours.

Pour les contours fermés, notre méthode ne convient pas car nous ne pouvons définir le début des contours à mettre en correspondance dans l'étape 1. Cependant, le choix du début des contours fermés au maximum de courbure permet de résoudre partiellement ce problème dans le cas de contours fermés.

La méthode ne s'applique pas bien aux contours rectilignes car le critère de similarité est surtout performant dans les changements de direction.

Pour les images à contours répétitifs, comme par exemple les images de cristaux en microscopie électronique, la contrainte épipolaire globale est un puissant critère qui permet d'extraire des ensembles homogènes d'appariements.


L'application de notre méthode n'a pas donné de résultat pour les images dont les contours sont peu nombreux, rectilignes ou fermés. Par contre, sur les images de photographie aérienne ou de microscopie électronique, l'extraction a donné de très bons résultats, même dans le cas d'images à contours répétitifs.


Un approfondissement de notre technique permettra sans doute d'améliorer encore la fiabilité de l'appariement entre contours.




Contours et amers de l'image de référence



Contours et amers de l'image homologue


Fig.5.8: Images de calcite de M.E.B.




Contours et amers de l'image de référence



Contours et amers de l'image homologue


Fig.5.9: Images de photographie aérienne (Belle Ile)

5.6 Recalcul d'images

5.6.1 Principe

Le principe du recalcul d'images consiste à choisir une image de référence et à corriger l'image homologue par rapport à celle-ci suivant la méthode présentée dans le chapitre 3. Elle consiste en une première projection sur un plan P de l'espace par le centre optique homologue, puis une deuxième projection vers l'image de référence par le centre optique de celle ci. Le plan de l'espace correspond à celui qui passe par les trois points définis sur chaque image comme base projective, le point unitaire étant choisi arbitrairement.

Cette technique ressemble aux procédés optiques de redressement utilisés en photogrammétrie au moyen de chambres claires.

L'image de référence n'est pas modifiée. On calcule l'antécédent de chaque point de l'image de référence par l'homographie inverse. Cette méthode permet d'obtenir l'image homologue recalculée sur l'image de référence. Il est important de rappeler que ce recalcul ne nécessite aucune calibration des systèmes de prise de vue. Il est uniquement basé sur les homologies de points extraites lors de l'étape de mise en correspondance de contours.

Les propriétés de la superposition de l'image de référence et de l'image homologue recalculée sont:

- la superposition des couples de points homologues appartenant au plan P de l'espace, ainsi qu'une relation entre la distance du point au plan P dans l'espace et l'écart entre ses deux images. Cette relation est linéaire dans le cas de la projection parallèle, où les centres optiques sont rejetés à l'infini.

- l'alignement de tous les couples de points homologues avec un point appelé épipôle.


5.6.2 Intérêt de cette représentation

Les intérêts de cette méthode sont triples:


- Contrôle visuel de la validité de la relation entre les images. En effet, l'observation visuelle de la superposition d'images recalculées permet d'évaluer la qualité de la superposition et même de déduire une idée de relief, soit de façon subjective, soit en tirant parti de l'information qualitative liée à la position d'un point par rapport à un plan de référence. En effet, il est possible de contrôler que des point perçus comme homologues sont alignés avec l'épipôle de l'image de référence et d'évaluer le relief par la distance entre deux images d'un même point après recalcul de l'image homologue.

- Mise à l'échelle de l'image homologue par rapport à l'image de référence. L'image recalculée est superposée à l'image de référence, l'écart entre les images homologues est lié à la position du point dans l'espace. Cet écart est relativement limité et homogène sur toute l'image, ce qui améliore la qualité de la mise en correspondance point à point ou fusion des deux images présentée dans le chapitre suivant.

- Préparation à la fusion des images stéréo sans passer par la calibration du système de prise de vue. La contrainte épipolaire fait que les points de l'image de référence et leurs homologues recalculés par homographie sont alignés avec l'épipôle de l'image de référence. C'est une contrainte fondamentale qui permet de diminuer de façon significative le calcul nécessaire à la fusion d'images. En effet, l'homologue d'un point de l'image de référence est sur la droite passant par lui même et l'épipôle. Donc la recherche se fait de façon monodimensionnelle et beaucoup plus facilement que dans l'espace bidimensionnel.

Il est important de noter que le recalcul de l'image, c'est à dire l'homographie calculée est fonction des points de référence utilisés comme base des coordonnées projectives.


5.6.3 Expérimentation


a) Modalités de l'expérimentation



Dans ce chapitre, nous observons les résultats sur quatre types d'images réelles.


- Objet plan: affiche verset

- Objet à faible relief: clavier d'ordinateur

- Objet fortement grossi au microscope électronique: calcite

- Objet tri-dimensionnel : pyramide


Pour chaque expérience, nous présentons :


1) les images d'origine gauche et droite


2) l'image droite corrigée par homographie et sa superposition avec l'image gauche d'origine


3) l'influence du choix des points de base des coordonnées projectives (A1, A2, A3) sur la position du centre du faisceau de droites calculé.

Nous avons choisi six combinaisons de points comme dans le paragraphe 3.5, soit:

. Quatre manuellement en prenant successivement les points (1,2,3), (2,3,4), (3,4,5) et (4,5,6) de la liste des points homologues.

.une combinaison en prenant

A1: M(x,y), M'(x,y) tel que Mx minimum

A2 Mx maximum

A3 My minimum

.une combinaison en prenant les points A1, A2, A3 formant le triangle de surface maximale.

4) l'influence du bruit, c'est à dire l'erreur sur l'acquisition des points homologues.

.Sur les points secondaires autres que les points A1, A2 et A3.

. Sur les points de base A1, A2 et A3 des coordonnées homogènes.

Nous avons introduit dans les coordonnées des points sur les images un bruit blanc dont le maximum varie 1 à 20 pixels et calculé pour chaque fenêtre de variation les coefficients a et b de l'homographie (c étant fixé à 1) 100 fois. Les graphiques montrent pour chaque fenêtre d'erreur la moyenne, l'écart type et l'écart maximum à la moyenne des coefficients a et b de l'homographie.



b) Image optique d'objet plan (Verset)




Image gauche d'origine (référence)




Image droite d'origine






Image droite corrigée par rapport à l'image de référence




Superposition de l'image gauche et de la droite corrigée




Points 1 2 3




Points 3 4 5




Points MIN/MAX X Y


Points 2 3 4




Points 4 5 6




Points surface max


Influence du choix des points de base












Influence des erreurs


c) Image optique d'objet tridimensionnel (clavier)




Image gauche d'origine (référence)




Image droite d'origine






Image droite corrigée par rapport à l'image de référence




Superposition de l'image gauche et de la droite corrigée




Points 1 2 3




Points 3 4 5




Points MIN/MAX X Y


Points 2 3 4




Points 4 5 6




Points surface max


Influence du choix des points de base













Influence des erreurs


d) Image de microscopie électronique (calcite)




Image gauche d'origine (référence)




Image droite d'origine






Image droite corrigée par rapport à l'image de référence




Superposition de l'image gauche et de la droite corrigée





Points 1 2 3




Points 3 4 5




Points MIN/MAX X Y


Points 2 3 4




Points 4 5 6




Points surface max


Influence du choix des points de base













Influence des erreurs


e) Image optique 3D (pyramide)





Image gauche d'origine (référence)




Image droite d'origine






Image droite corrigée par rapport à l'image de référence




Superposition de l'image gauche et de la droite corrigée












Image gauche de référence

Image droite corrigée

Superposition des 2 images









Image gauche de référence

Image droite corrigée

Superposition des 2 images


Exemple de quatre recalculs d'images optiques (pyramide)





Points 1 2 3




Points 3 4 5




Points MIN/MAX X Y



Points 2 3 4




Points 4 5 6




Points surface max


Influence du choix des points de base














Influence des erreurs


5.6.4 Interprétation des résultats


La visualisation des images nous amènent à plusieurs remarques.


- Les épipôles obtenus sur les images réelles sont très instables, contrairement à ceux calculés sur les ensembles de points générés artificiellement en projection centrale. Cette instabilité est dues aux imprécisions de positionnement des points homologues, aux déformations du plan image et à la discrétisation de l'image numérique. Les épipôles calculés sur des images de faible relief sont sans signification, du fait que les droites sont définies par des couples de points très proches. A la limite, pour l'image d'un objet plan, les points étant confondus, le calcul d'un épipôle revêt un caractère complètement aléatoire.


- Les recalculs d'images sont assez stables ainsi que les paramètres de l'homographie entre les plans images pour des points de référence donnés. Ils sont même assez résistant au bruit, ce qui est un indice de fiabilité de la méthode.


Cette méthode présente donc une application dans la mise en correspondance point à point (fusion) d'images stéréoscopiques puisqu'elle constitue un premier traitement qui rapproche les caractéristiques des images pour favoriser une correspondance plus fine que nous étudions ci-dessous.

5.7 Fusion d'images

La fusion d'images stéréoscopiques consiste à mettre deux images homologues en relation point à point, c'est à dire, si l'on prend une image comme référence, de rechercher pour chaque point de cette image, son correspondant sur l'image homologue. Il faut tenir compte du fait que tous les points de l'image de référence n'ont pas forcément, un correspondant, soit parce que le point correspondant est en dehors de l'image homologue (problème de recouvrement de zone observée), soit parce que ce point est caché par un objet plus proche lors de l'observation d'un point de vue différent (problème d'occlusion).


Le problème de mise en correspondance entre deux images est au départ bidimensionnel, ce qui pour une image de taille 512 x 512 représente pour chaque point 512 x 512 possibilités d'appariement. Il est donc impératif de réduire le combinatoire si l'on veut obtenir des algorithmes exploitables. Dans le chapitre 3, nous avons étudié le modèle géométrique des images stéréoscopique, et calculé la relation qui existe entre deux images homologues. La géométrie épipolaire nous offre un puissant outil qui nous permet de réduire considérablement la zone de recherche de l'homologue d'un point de l'image de référence. En effet, la connaissance des droites homologues entre les deux images permet en théorie de ramener le problème bidimensionnel de la mise en correspondance à un problème monodimensionnel. Si l'on considère 512 lignes épipolaire de longueur constante 512, le nombre de possibilités d'appariement pour un point devient alors 512. Si l'on prend en compte la relation d'ordre qui existe en général entre les points des droites homologues, la recherche d'un point homologue se limite à une fenêtre de recherche sur l'autre ligne épipolaire. Pour un fenêtre de 10, le nombre d'appariements possible pour chaque point devient 10 ce qui est plus facilement calculable.


Les algorithmes de fusion d'images stéréoscopique [BENA83] [SHI87] [FORE88] utilisent généralement les propriétés de la géométrie épipolaire ainsi que la relation d'ordre sur deux droites épipolaires homologues comme principes de base. Le critère de corrélation est basé sur la luminance des points et de leur voisinage, ce qui revient à déplacer une fenêtre de corrélation le long des droites épipolaires.


Nous avons choisi d'utiliser l'algorithmique de programmation dynamique pour résoudre ce problème, puisque la recherche de points homologues sur deux droites épipolaire peut se traiter par la recherche d'un chemin de coût minimum dan un graphe valué. Les noeuds du graphe sont les couples de points de référence et homologues potentiels, et les arcs valués le critère de similarité. L'algorithme de mise en correspondance est celui de Wagner et Fischer présenté au début de ce chapitre. La contrainte est de prendre les lignes épipolaires homologues dans le même sens, c'est à dire que les points des droites homologues ont la même relation d'ordre avec leur épipôle respectif. Le critère de similarité est basé sur la minimisation des différences de luminance entre points homologues.


La figure suivante présente un exemple de chemin de correspondance entre lignes épipolaires. La recherche se fait dans une fenêtre pour limiter le temps de calcul. Les niveaux de gris de la figure représentent la valeur absolue des disparités de luminance entre points de deux lignes épipolaire homologues. Plus la zone est sombre, plus les luminances sont semblables, et donc plus les points se correspondent s'ils gardent la même luminance entre les deux prises de vue. Le chemin de mise en correspondance est dessiné en blanc dans la matrice.



Fig.5.10: Chemin de correspondance entre deux droites épipolaires homologues



Algorithme:

L'algorithme de fusion de deux images stéréoscopique s'applique à une image de référence et son homologue corrigée selon la technique décrite dans le paragraphe précédent. Les droites épipolaires homologues sont superposées et l'épipôle dans l'images de référence est connu.


Il comprend cinq phases principales:


1) Mise en correspondance des droites épipolaires homologues. Cette phase consiste à extraire les deux droites homologues en faisant tourner un rayon autour de l'épipôle suivant un pas variable afin de balayer l'ensemble des deux images superposées. Les droites sont représentées comme une suite de points caractérisés par leur luminance.

2) Mise en correspondance par programmation dynamique des suites de valeurs issues de la première phase. Cette mise en correspondance se fait en cherchant un chemin de coût minimal du haut à gauche vers le bas à droite dans la matrice présentée dans la figure précédente. Ensuite, on cherche un deuxième chemin du bas à droite vers en haut à gauche dans la même matrice. Le résultat de cette phase est un ensemble de points appartenant à la fois au premier et au deuxième chemin. Cette technique permet de limiter les faux appariements.

3) Pour éviter un mitage trop important de la correspondance et en nous appuyant sur les hypothèses d'ordre des points homologues et de continuité des surfaces observées présentées au chapitre 2, nous réalisons une interpolation entre deux couples appariés. Cette interpolation est limitée à une fenêtre de trois points, c'est à dire que nous appliquons cette technique lorsque deux appariements dans la suite des points formant la droite sont séparés de moins de quatre points. Si nous appelons l'appariement '*', le non appariement '.' et l'interpolation '-', la suite '***...*....*..***...' est transformée en '***---*....*--***...'

4) Les étapes 1), 2) et 3) sont répétées sur l'ensemble de l'image. A la fin de ce traitement, nous avons une correspondance entre l'image de référence et l'image homologue corrigée. nous appliquons une deuxième interpolation sur l'ensemble de l'image dans une fenêtre de trois points, ce qui permet d'élargir la relation entre les deux images. A la fin de cette étape, nous avons une mise en correspondance de 90 à 95% des points selon les images. Cette correspondance est faite entre les points de l'image de référence et l'image homologue.

5) Pour obtenir une correspondance entre les deux images d'origines, il suffit pour chaque point de revenir à l'antécédent du point recalculé de l'image homologue, ce qui revient à appliquer à ses coordonnées, l'homographie inverse calculée au chapitre 3. Cependant, cette phase n'est pas nécessaire pour le calcul du point dans l'espace puisque celui ci s'appuie sur les coordonnées transformées par homographie et exprimées dans le référentiel de l'image de référence.


Les images suivantes montrent des images d'origine gauche et droite de photographie aérienne, puis l'image droite recalculée par rapport à la gauche, et enfin le résultat de la fusion entre l'image gauche de référence et l'image droite recalculée. Cette dernière image de correspondance est formée par les points homologues appariés de l'image droite ramenés aux coordonnées de leur équivalent sur l'image de référence. Les parties de l'image homologue non représentées sur l'image de correspondance correspondent à de zones non appariées.


Pour évaluer la qualité de la fusion des deux images nous superposons l'image de référence en rouge et l'image de correspondance en vert et bleu. Si l'on considère que les points homologues ont la même luminance, les zones de bonne correspondance s'affichent en noir et blanc par l'addition avec la même intensité des couleurs de base.


Nous observons une bonne mise en correspondance en général, sauf dans des zones où la luminance présente des variations importantes entre les deux images du fait de reflets du soleil sur la mer. Ceci est dû au critère de similarité choisi entre les points homologues, puisque l'on considère les points selon leurs caractéristiques de luminance. Des tests réalisés sur le gradient de l'image n'ont pas présenté de meilleurs résultats. Il est envisageable de définir un critère mixte qui prenne en compte les caractéristiques de luminance et gradient de l'image afin d'atténuer les inconvénients d'un critère unique.


Une interpolation plus large peut être réalisée pour remplir des zones non appariées, mais cela risque de nuire à la précision de la mise en correspondance.


L'élargissement de la recherche à une fenêtre de corrélation le long des droites épipolaires améliorera les performances de cette mise en correspondance puisqu'elle palliera l'instabilité des centres épipolaires qui induit des décalages entre droites épipolaires conjuguées.



Fig.5.11: Image gauche d'origine (référence)




Fig.5.12: Image droite d'origine



Fig.5.13: Image droite recalculée par rapport à l'image gauche




Fig.5.14: Résultat de la fusion entre l'image gauche et l'image droite recalculée

5.8 Conclusion

Dans ce chapitre, nous avons présenté une chaîne de mise en correspondance de couples d'images stéréoscopiques. Cette méthode est divisée en trois étapes principales:


1) Extractions d'amers à partir de mise en correspondance de contours.

2) Calcul de la géométrie épipolaire à partir des amers, et recalcul de l'image homologue pour superposer les droites épipolaires homologues.

3) Fusion des deux images en élargissant correspondance entre les deux images à partir de l'image de référence et de l'image homologue recalculée lors de l'étape 3.

L'application de notre méthode à des images stéréoscopiques réelles donne de bons résultats. Cependant certains types d'images posent des problèmes pour l'extraction des amers, ou bien pour la fusion du couple stéréoscopique.


Nous avons essayé de caractériser les problèmes à résoudre pour chaque étape de la mise en correspondance afin d'orienter notre travail dans l'avenir.

Les améliorations envisagées sont les suivantes:


1) pour l'étape d'extraction d'amers, les difficultés liées aux contours rectilignes peuvent être surmontées par la coopération d'une méthode basée sur le codage par segments [AYAC89], mais en tous cas il faut que les images aient suffisamment de contours pour qu'un appariement soit possible. Si cette étape est irréalisable, il est toujours possible de déterminer les correspondances entre points manuellement, ce qui permet de passer à l'étape suivante de la mise en correspondance. L'impossibilité d'extraction d'amers n'interdit donc pas la fusion d'un couple d'images stéréoscopiques.

2) le calcul des épipôles qui permet le recalcul de l'image homologue par rapport à l'image de référence pose parfois un problème de stabilité, surtout pour les scènes à relief peu marqué. Cette instabilité des épipôles est due aux imprécisions de l'appariement des amers, aux déformations des plans images, et dans une certaine mesure à la discrétisation des images. Il y a donc un travail important à réaliser sur l'étude des déformations des plans images et des algorithmes de corrections d'images. Cet aspect est capital pour une amélioration de la précision du calcul des points dans l'espace, puisque la géométrie calculée à cette étape est fondamentale pour la qualité des résultats.

3) pour la fusion des deux images, les variations radiométriques que nous avons observées sur les couples stéréo nous invitent à élaborer un critère de similarité plus complexe que la luminance, peut être qu'une combinaison de la luminance et du gradient permettrait de lever certaines ambiguïtés. D'autre part, la prise en compte du voisinage soit par la recherche d'une surface de coût minimum dans un espace à quatre dimensions par programmation dynamique, soit par une fenêtre de corrélation, améliorerait sans doute la qualité des résultats, au prix cependant d'un temps de calcul plus important. Nous pouvons sans doute envisager un algorithme de mise en correspondance basé sur des conditions de réaction entre les points des deux images (luminance, gradient, ordre, alignement avec l'épipôle), qui s'inspirerait des méthodes de croissance des régions et de minimisation de fonction d'énergie représentant la somme des disparités des points appariés. En tous cas, les grandes surfaces de zones homogènes restent difficilement fusionables de façon précise.




6. Calcul 3D


Ce chapitre utilise les techniques de calcul des points dans l'espace qui ont été décrites dans le chapitre 3 de ce rapport.


Nous étudions dans la suite de ce chapitre les deux type de calculs, suivant que nous sommes en présence d'une projection centrale ou parallèle.


Pour cela, nous avons choisi cinq exemples d'ensembles de points que nous définissons comme suit:


1) orthogonal est un premier ensemble de points de l'espace généré artificiellement en projection orthogonale

2) central_près est le même ensemble de points que orthogonal, mais généré en projection centrale. Les centres optiques C et C'ont été choisis proches des points de l'espace afin d'apprécier leur influence dans la méthode de calcul choisie.

3) central_loin est généré en projection centrale. Les centres optiques C et C'ont été choisis éloignés des points de l'espace afin d'apprécier leur influence dans la méthode de calcul choisie.

4) pyramide est un ensemble de points issu des images réelles de la pyramide que nous avons étudiées au cours de ce travail. Ce sont donc des points acquis à partir d'une caméra video, appariés manuellement sur les deux images et évalués dans l'espace par mesure sur le modèle. Nous appliquons les deux algorithmes de calcul sur ces points et nous étudions la précision et la stabilité des résultats lorsqu'on injecte une erreur dans les coordonnées des points sur les plans images.


Méthode expérimentale


Pour chaque ensemble de points, nous présentons tout d'abord les coordonnées de leurs images sur chaque plan (X1,Y1) et (X2,Y2) par rapport à leur référentiel respectif, ainsi que les coordonnées (X3D,Y3D,Z3D) des points réels dans le référentiel de l'espace.


Nous présentons ensuite les résultats du calcul de ces points dans l'espace. Ce calcul est réalisé en deux étapes:


1) D'abord la relation entre les plans images est calculée et les points homologues sont recalculés par l'homographie déduite de cette étape. Cette relation utilise d'une part les 3 premiers couples de points comme points de base qui servent au changement de coordonnées, et d'autre part le reste des points dits secondaires pour l'alignement avec l'épipôle.

2) Ensuite le calcul est réalisé avec les deux méthodes. La première suppose une projection parallèle, basée sur la connaissance dans l'espace des quatre premiers points de l'ensemble. La seconde suppose une projection centrale et utilise les coordonnées 3D des cinq premiers points de l'ensemble. Les points de base seront donc quatre ou cinq suivant la méthode utilisée. Les points sont calculés dans l'espace par l'intersection des deux droites définies pour chaque point selon les techniques décrite dans le chapitre 3.

Les résultats obtenus par les deux méthodes de calcul sont présentés dans des tableaux qui comprennent pour chaque point ses coordonnées réelles, ses coordonnées calculées, l'erreur aux moindres carrés du système de résolution de l'intersection des deux droites dans l'espace, et la distance euclidienne entre le point réel et le point calculé. Il faut noter que par définition les points de base seront calculés avec exactitude dans les reconstructions 3D, c'est à dire les quatre premiers points pour la projection parallèle, et les cinq premiers pour la projection centrale.


Le but de cette expérience est d'évaluer les performances des deux techniques, ainsi que la qualité des reconstructions de points avec la technique en quatre points pour les images perspectives.


Pour évaluer l'erreur relative de la reconstruction par rapport à la taille de l'objet, nous avons calculé la somme des distances entre chaque couple de points et la somme des variations par rapport au total des distances. Pour cela, nous utilisons deux variables:

- Somme des distance réelles: c'est la somme des distances réelles entre tous les points de l'ensemble pris deux à deux. Cette somme est notée S.

- Ecart entre distances: si nous appelons Di la distance réelle entre deux points de l'objet et Di' la distance entre les points calculés, l'écart calculé est la valeur ei = |Di - Di|. L'écart E représente la somme des ei pour chaque couple de points.

Nous pouvons calculer cette variation en pourcentage, elle nous donne une idée de l'erreur de reconstruction relative à la taille de l'objet.


La fin de ce chapitre présente une étude de l'erreur de reconstruction si l'on traite un image perspective comme une projection parallèle, et une étude de l'influence du bruit sur les reconstructions.



6.1 Exemple orthogonal


X1

Y1

X2

Y2

X3D

Y3D

Z3D

48.293

2.540

73.345

-31.286

15.00

26.00

-14.00

42.079

11.622

13.902

4.159

72.00

35.00

-62.00

26.564

-50.646

81.295

24.562

31.00

-24.00

-62.00

9.983

-62.959

115.134

8.699

14.00

-47.00

-37.00

18.466

-14.388

109.567

-46.359

6.00

-9.00

12.00

-4.443

-25.242

108.441

-37.079

25.00

-31.00

5.00

-4.121

-9.164

114.475

-62.307

17.00

-21.00

30.00

-7.529

-78.121

78.405

53.721

62.00

-64.00

-87.00

28.128

-61.358

131.429

-2.328

-14.00

-36.00

-24.00

31.929

-26.861

115.235

-31.986

-7.00

-9.00

-1.00

34.663

4.385

83.840

-45.390

15.00

17.00

3.00

31.919

10.241

67.423

-40.088

31.00

21.00

-6.00

37.739

8.224

138.203

-93.822

-37.00

15.00

62.00

43.311

96.521

8.325

-98.669

64.00

92.00

32.00

312.534

88.719

5.121

-22.700

-125.00

264.00

-62.00

-35.098

-63.082

-7.027

97.751

157.00

-62.00

-148.00


Coordonnées des points sur les plans image et dans l'espace


Dans cet exemple, les points de l'espace sont projetés de façon orthogonale sur les deux plans images.

Notation : les valeurs élevées sont présentées en notation scientifique, par exemple 10000 est présenté E4.

La première étape de calcul de la relation entre les plans images donne:

Homographie entre plans images: a=1 b=1 c=1 errmc=0 errcoef=0

Epipôles calculés: I=(52 E7, 97 E6) I'=(68 E6, 13 E6) errmc = 0


Les valeurs calculées pour les épipôles sur les deux plans images sont conformes à la théorie c'est à dire qu'ils sont rejetés à l'infini (limité à une valeur importante du fait des erreurs d'arrondi sur la représentation de nombres réels).



Dans la deuxième étape du calcul résumée par les deux tableaux suivants, nous observons l'exactitude de la reconstruction.

- La projection parallèle étant conforme au mode de génération des points, ceci confirme la validité de la méthode de calcul.

Distance totale entre points 3D et points calculés : 0.000416

Somme des distances entre points: S=15252.43, somme des différences E=0.00, soit 0.00 % de S.


- La projection centrale donne:

Homographie du plan de l'espace vers le plan image de référence: u=0.228 v=0.228 w=0.228

Centre optiques calculés: C=(-38 E6, -50 E5, 43 E6) C'=(-19 E6, 20 E6, -22 E5)

Les centres optiques sont théoriquement à l'infini, mais la représentation des réels induit une erreur sur leur position, ce qui entraîne des erreurs aux moindres carrés lors de la reconstruction des points qui est malgré tout exacte.

Distance totale entre points 3D et points calculés : 0.003588

Somme des distances entre points S=15252.43, somme des différences E=0.05, soit 0.00 % de S.







Xréel

Yréel

Zréel

Xcalc.

Ycalc.

Zcalc.

errmc

dist.

15.00

26.00

-14.00

15.00

26.00

-14.00

0.00

0.00

72.00

35.00

-62.00

72.00

35.00

-62.00

0.00

0.00

31.00

-24.00

-62.00

31.00

-24.00

-62.00

0.00

0.00

14.00

-47.00

-37.00

14.00

-47.00

-37.00

0.00

0.00

6.00

-9.00

12.00

6.00

-9.00

12.00

0.00

0.00

25.00

-31.00

5.00

25.00

-31.00

5.00

0.00

0.00

17.00

-21.00

30.00

17.00

-21.00

30.00

0.00

0.00

62.00

-64.00

-87.00

62.00

-64.00

-87.00

0.00

0.00

-14.00

-36.00

-24.00

-14.00

-36.00

-24.00

0.00

0.00

-7.00

-9.00

-1.00

-7.00

-9.00

-1.00

0.00

0.00

15.00

17.00

3.00

15.00

17.00

3.00

0.00

0.00

31.00

21.00

-6.00

31.00

21.00

-6.00

0.00

0.00

-37.00

15.00

62.00

-37.00

15.00

62.00

0.00

0.00

64.00

92.00

32.00

64.00

92.00

32.00

0.00

0.00

-125.00

264.00

-62.00

-125.00

264.00

-62.00

0.00

0.00

157.00

-62.00

-148.00

157.00

-62.00

-148.00

0.00

0.00


Résultat du calcul avec la méthode à 4 points (projection parallèle)







Xréel

Yréel

Zréel

Xcalc.

Ycalc.

Zcalc.

errmc

dist.

15.00

26.00

-14.00

15.00

26.00

-14.00

0.00

0.00

72.00

35.00

-62.00

72.00

35.00

-62.00

0.00

0.00

31.00

-24.00

-62.00

31.00

-24.00

-62.00

0.00

0.00

14.00

-47.00

-37.00

14.00

-47.00

-37.00

0.00

0.00

6.00

-9.00

12.00

6.00

-9.00

12.00

0.00

0.00

25.00

-31.00

5.00

25.00

-31.00

5.00

5606.39

0.00

17.00

-21.00

30.00

17.00

-21.00

30.00

1801.59

0.00

62.00

-64.00

-87.00

62.00

-64.00

-87.00

135.81

0.00

-14.00

-36.00

-24.00

-14.00

-36.00

-24.00

10.83

0.00

-7.00

-9.00

-1.00

-7.00

-9.00

-1.00

6930.65

0.00

15.00

17.00

3.00

15.00

17.00

3.00

518.43

0.00

31.00

21.00

-6.00

31.00

21.00

-6.00

9460.46

0.00

-37.00

15.00

62.00

-37.00

15.00

62.00

78.64

0.00

64.00

92.00

32.00

64.00

92.00

32.00

17898

0.00

-125.0

264.0

-62.00

-125.00

264.00

-62.00

4549690

0.00

157.00

-62.00

-148.00

157.00

-62.00

-148.00

18917

0.00


Résultat du calcul avec la méthode à 5 points (projection centrale)




6.2 Exemple central_près



X1

Y1

X2

Y2

X3D

Y3D

Z3D

57.616

12.500

62.013

-82.305

15.00

26.00

-14.00

58.333

14.336

39.349

8.294

72.00

35.00

-62.00

56.488

8.538

82.581

19.796

31.00

-24.00

-62.00

52.534

3.605

96.998

12.632

14.00

-47.00

-37.00

43.307

3.112

104.053

-33.152

6.00

-9.00

12.00

45.023

5.519

94.288

-6.949

25.00

-31.00

5.00

21.668

0.438

99.619

-24.695

17.00

-21.00

30.00

55.078

8.396

82.381

25.233

62.00

-64.00

-87.00

51.388

-5.124

118.292

2.584

-14.00

-36.00

-24.00

49.147

-1.028

118.895

-37.505

-7.00

-9.00

-1.00

53.744

12.176

83.870

-63.318

15.00

17.00

3.00

55.204

13.863

68.244

-37.292

31.00

21.00

-6.00

63.870

15.794

-71.681

327.498

-37.00

15.00

62.00

56.975

27.407

-731.820

-1219.26

64.00

92.00

32.00

215.067

60.141

91.794

19.423

-125.00

264.00

-62.00

56.135

11.758

69.011

28.853

157.00

-62.00

-148.00


Coordonnées des points sur les plans image et dans l'espace



Dans cet exemple, les points de l'espace sont projetés de façon centrale sur les deux plans images. Les centre optiques : C=(-19, 38, 24) C'=(-8, 17, -57) sont très proches des points de l'espace, ce qui correspond à une prise de vue très rapprochée d'une scène.


La première étape de calcul de la relation entre les plans images donne:

Homographie entre plans images: a=2.394 b=1.815 c=1

Epipôles calculés: I=(61.5, 8.04) I'=(57.22, 10.26)



Dans la deuxième étape du calcul résumée par les deux tableaux suivants, nous observons une forte disparité des résultats de reconstruction suivant la méthode employée.

- La projection parallèle donne des résultats aberrants ce qui prouve que la distance trop proche des centres optique par rapport à la profondeur de la scène observée interdit une approximation par projection parallèle. Les études dans ce domaine annoncent un rapport minimum de 10 entre la distance et la profondeur de la scène pour une approximation par projection parallèle.

Distance totale entre points 3D et points calculés : 5125.45

Somme distances réelles S=15252.43 somme des différences E=55076.43 soit 361.1 % de S.


- La projection centrale donne:

Les centres optiques sont calculés avec exactitude ce qui valide la méthode de calcul employée.

Homographie du plan de l'espace vers le plan image de référence: u=1.34 v=3.84 w=2.84

Centre optiques calculés: C=(-19, 38, 24) C'=(-8, 17, -57)

Les points sont calculés de façon exacte et les erreurs aux moindres carrés lors de leur reconstruction sont négligeables.

Distance totale entre points 3D et points calculés : 0.034121

Somme des distances entre points S=15252.43,

Somme des différences E=0.44, soit 0.00 % de S.






Xréel

Yréel

Zréel

Xcalc.

Ycalc.

Zcalc.

errmc

dist.

15.00

26.00

-14.00

15.00

26.00

-14.00

0.00

0.00

72.00

35.00

-62.00

72.00

35.00

-62.00

0.00

0.00

31.00

-24.00

-62.00

31.00

-24.00

-62.00

0.00

0.00

14.00

-47.00

-37.00

14.00

-47.00

-37.00

0.00

0.00

6.00

-9.00

12.00

-5.91

66.75

145.52

11971

153.97

25.00

-31.00

5.00

13.69

78.65

125.51

12487

163.32

17.00

-21.00

30.00

11.37

298.39

487.43

11E4

557.93

62.00

-64.00

-87.00

33.85

-8.72

-41

254

77.18

-14.00

-36.00

-24.00

-13.57

-162.89

-102

5888

149.04

-7.00

-9.00

-1.00

-26.77

-68.30

6.17

0.10

62.92

15.00

17.00

3.00

1.30

72.88

66.59

5227

85.76

31.00

21.00

-6.00

26.78

75.81

35.71

3740

69.01

-37.00

15.00

62.00

302.03

-54.75

-382.03

19844

563.00

64.00

92.00

32.00

415.84

192.92

-221.54

82E4

445.26

-125.0

264.00

-62.00

-39.75

-1234

-2205

15E5

2616

157.00

-62.00

-148.00

49.40

27.14

-32.34

999

181.39


Résultat du calcul avec la méthode à 4 points (projection parallèle)






Xréel

Yréel

Zréel

Xcalc.

Ycalc.

Zcalc.

errmc

dist.

15.00

26.00

-14.00

15.00

26.00

-14.00

0.00

0.00

72.00

35.00

-62.00

72.00

35.00

-62.00

0.00

0.00

31.00

-24.00

-62.00

31.00

-24.00

-62.00

0.00

0.00

14.00

-47.00

-37.00

14.00

-47.00

-37.00

0.00

0.00

6.00

-9.00

12.00

6.00

-9.00

12.00

0.00

0.00

25.00

-31.00

5.00

25.00

-31.00

5.00

0.00

0.00

17.00

-21.00

30.00

17.00

-21.00

30.00

0.00

0.00

62.00

-64.00

-87.00

62.00

-64.00

-87.00

0.00

0.00

-14.00

-36.00

-24.00

-14.00

-36.00

-24.00

0.00

0.00

-7.00

-9.00

-1.00

-7.00

-9.00

-1.00

0.00

0.00

15.00

17.00

3.00

15.00

17.00

3.00

0.00

0.00

31.00

21.00

-6.00

31.00

21.00

-6.00

0.00

0.00

-37.00

15.00

62.00

-37.00

15.00

62.00

0.00

0.00

64.00

92.00

32.00

64.00

92.00

32.00

0.00

0.00

-125.00

264.00

-62.00

-124.99

263.98

-62.00

0.00

0.02

157.00

-62.00

-148.00

157.00

-62.00

-148.00

0.00

0.01


Résultat du calcul avec la méthode à 5 points (projection centrale)



6.3 Exemple central_loin



X1

Y1

X2

Y2

X3D

Y3D

Z3D

975.031

-23.720

56.497

-615.222

0.00

0.00

0.00

977.309

-28.239

60.213

-616.965

5.00

8.80

0.00

978.667

-26.104

58.234

-617.840

7.50

4.40

0.00

976.239

-25.926

58.234

-614.751

2.50

4.40

5.00

976.279

-24.310

56.868

-615.584

2.50

1.10

1.90

977.314

-26.714

58.859

-616.333

4.80

5.80

2.10

974.812

-28.114

60.325

-615.222

0.00

8.80

0.00

977.528

-23.845

56.373

-616.965

5.00

0.00

0.00

977.327

-25.413

57.729

-616.325

4.70

3.20

2.00

975.926

-27.349

59.537

-615.444

2.10

7.20

1.90


Coordonnées des points sur les plans image et dans l'espace


Les points sont projetés de façon centrale sur les plans images. Les centres optiques sont éloignés des points de l'espace.


Dans cet exemple, les points de l'espace sont projetés de façon centrale sur les deux plans images. Les centre optiques : C=(-50, 50, 2000) C'=(770, 100, 1000) sont éloignés des points de l'espace, ce qui correspond à une prise de vue à distance d'une scène.


La première étape de calcul de la relation entre les plans images donne:

Homographie entre plans images: a=0.996 b=0.999 c=1 errmc=0 errcoef=0

Epipôles calculés: I=(1764,16, -138.16) I'=(8638.37, -1127.41) errmc=0



Dans la deuxième étape du calcul résumée par les deux tableaux suivants, nous observons une identité des résultats de reconstruction avec les deux méthodes.

- La projection parallèle donne de très bons résultats ce qui montre qu'à partir d'un certain rapport entre la distance des centres optique et la profondeur de la scène observée permet une approximation par projection parallèle. Ce rapport étant de 100 dans ce cas une approximation par projection parallèle est tout à fait valide.

Distance totale entre points 3D et points calculés : 0.061847

Somme des distances réelle S=265.41

Somme des différences E=0.15 soit 0.06 % de S



- La projection centrale donne:

Les centres optiques sont calculés avec exactitude ce qui valide la méthode de calcul employée.

Homographie du plan de l'espace vers le plan image de référence: u=0.094713 v=0.094715 w=0.094714

Centre optiques calculés: C=(-50, 50, 2001) C'=(770.4, 100.1, 1000.5)

Les points sont calculés de façon exacte et les erreurs aux moindres carrés lors de leur reconstruction sont négligeables.

Distance totale entre points 3D et points calculés : 0.000150

Somme des distances réelle S=265.41

Somme des différences E=0.00 soit 0.00 % de S










Xréel

Yréel

Zréel

Xcalc.

Ycalc.

Zcalc.

errmc

dist.

0.00

0.00

0.00

0.00

0.00

0.00

0.00

0.00

5.00

8.80

0.00

5.00

8.80

-0.00

0.00

0.00

7.50

4.40

0.00

7.50

4.40

-0.00

0.00

0.00

2.50

4.40

5.00

2.50

4.40

5.00

0.00

0.00

2.50

1.10

1.90

2.50

1.10

1.90

0.00

0.01

4.80

5.80

2.10

4.80

5.80

2.10

0.00

0.00

0.00

8.80

0.00

0.00

8.78

-0.01

0.00

0.02

5.00

0.00

0.00

5.00

-0.00

0.01

0.00

0.01

4.70

3.20

2.00

4.70

3.20

2.01

0.00

0.01

2.10

7.20

1.90

2.10

7.20

1.89

0.00

0.01


Résultat du calcul avec la méthode à 4 points (projection parallèle)











Xréel

Yréel

Zréel

Xcalc.

Ycalc.

Zcalc.

errmc

dist.

-0.00

-0.00

-0.00

0.00

0.00

0.00

0.00

0.00

5.00

8.80

0.00

5.00

8.80

-0.00

0.00

0.00

7.50

4.40

0.00

7.50

4.40

-0.00

0.00

0.00

2.50

4.40

5.00

2.50

4.40

5.00

0.00

0.00

2.50

1.10

1.90

2.50

1.10

1.90

0.00

0.00

4.80

5.80

2.10

4.80

5.80

2.10

0.00

0.00

0.00

8.80

-0.00

-0.00

8.80

-0.00

0.00

0.00

5.00

0.00

0.00

5.00

0.00

-0.00

0.00

0.00

4.70

3.20

2.00

4.70

3.20

2.00

0.00

0.00

2.10

7.20

1.90

2.10

7.20

1.90

0.00

0.00


Résultat du calcul avec la méthode à 5 points (projection centrale)





6.4 Relation projection parallèle / centrale

Pour visualiser l'influence de l'approximation d'une projection centrale en projection parallèle, nous avons fait varier la distance des plans de projection à l'objet observé et calculé la variation des résultats obtenus.


Nous avons modélisé les appareils de prise de vue selon un modèle perspectif, c'est à dire un plan de projection Pi et un centre de projection associé Ci.

Les deux appareils de prise de vue sont caractérisés par:

P1: (0,10,-d) (0,0,-d) (10,0,-d) et C1: (5,5,-d-f)

P2: (10-d,0,-d) (10-d,10,-d) (40-d,0,10-d) et C2: (25-d-f,5,5-d-f)


Nous avons fixé f=50 ce qui correspond à la focale et nous avons fait varier d, ce qui revient à déplacer les appareils de prise de vue dans l'espace.

Pour chaque variation de d, nous avons projeté l'ensemble de points 3D de l'exemple précédent central_loin, qui est aussi celui de l'exemple optique pyramide. Nous avons reconstruit les points 3D avec la méthode en 4 points qui suppose la projection parallèle. Cette méthode nous a donné l'erreur relative de la reconstruction, et nous l'avons reportée sur la figure suivante qui représente d sur l'axe des X en échelle logarithmique, et le pourcentage d'erreur de reconstruction sur l'axe des Y.



La profondeur de l'objet étant de l'ordre de 10, on observe qu'à une distance supérieure à 200, les erreurs deviennent faibles. Elles sont négligeables au dessus de 1000. Ces valeurs correspondent respectivement à un rapport distance / taille de 20 et 100.

Ces résultats résument les exemples précédents et montrent que la projection peut être approximée par une projection parallèle dès que l'on se trouve à une certaine distance de l'objet observé. Ces résultats mériteront d'être approfondis afin d'analyser plus finement les influences de la distance, la taille de l'objet et la focale de l'appareil de prise de vue.

6.5 Exemple pyramide (optique)



X1

Y1

X2

Y2

X3D

Y3D

Z3D

15

150

89

41

0

0

0

454

106

395

186

5

8.8

0

343

188

169

202

7.5

4.4

0

164

34

255

26

2.5

4.4

5

93

128

121

61

2.5

1.1

1.9

306

100

272

126

4.8

5.8

2.1

336

50

457

97

0

8.8

0

112

213

16

124

5

0

0

206

133

157

111

4.7

3.2

2

312

58

370

96

2.1

7.2

1.9


Coordonnées des points sur les plans image et dans l'espace





Les points de cet ensemble sont issus des images de la pyramide que nous avons présentées au cours de ce rapport. La projection est donc centrale, mais elle a aussi subi les distorsions dues à l'optique de l'appareil de prise de vue. D'autre part, la position exacte des points sur l'image peut être entachée d'erreur, ainsi que l'évaluation de la position des points correspondants dans l'espace.

L'objet observé est assez compact et éloigné de l'appareil de prise de vue.



La première étape de calcul de la relation entre les plans images donne:

Homographie entre plans images: a=0.997 b=0.986 c=1 errmc=0 errcoef=0.03

Epipôles calculés: I=(1860, -1177) I'=(1573, -922) errmc=0.0001

Les erreurs aux moindres carrés ainsi que l'autocontrôle sur les coefficients de l'homographie montrent que la résolution est correcte, ce qui permet d'envisager une bonne reconstruction 3D.


Dans la deuxième étape du calcul résumée par les deux tableaux suivants, nous observons une quasi identité des résultats de reconstruction avec les deux méthodes.

- La projection parallèle donne:

Distance totale entre points 3D et points calculés : 2.766678

Somme des distances réelle S=265.41

Somme des différences E=9.25 soit 3.48 % de S

- La projection centrale donne:

Homographie du plan de l'espace vers le plan image de référence: u=0.0174 v=0.0183 w=0.017

Centre optiques calculés: C=(50,5, -5.9, 37.9) C'=(79.9, 26.3, 80.7)

Distance totale entre points 3D et points calculés : 2.659343

Somme des distances réelle S=265.41

Somme des différences E=9.67 soit 3.64 % de S


On remarque que les centres optiques calculés sont aberrants, ce qui montre leur grande instabilité qui s'explique par leur mode de calcul. Le gain par rapport à la méthode à quatre point est minime. Ceci pose le problème des déformations des plans images et de la robustesse de la méthode de calcul.









Xréel

Yréel

Zréel

Xcalc.

Ycalc.

Zcalc.

errmc

dist.

0.00

0.00

0.00

0.00

-0.00

0.00

0.00

0.00

5.00

8.80

0.00

5.00

8.80

0.00

0.00

0.00

7.50

4.40

0.00

7.50

4.40

0.00

0.00

0.00

2.10

7.20

1.90

2.10

7.20

1.90

0.00

0.00

2.50

4.40

5.00

1.80

4.32

5.10

0.03

0.71

2.50

1.10

1.90

2.08

1.38

1.80

0.02

0.51

4.80

5.80

2.10

4.52

5.72

2.16

0.00

0.30

0.00

8.80

0.00

0.00

8.54

-0.06

0.00

0.27

5.00

0.00

0.00

4.44

-0.14

-0.46

0.03

0.74

4.70

3.20

2.00

4.54

3.04

2.09

0.02

0.24


Résultat du calcul avec la méthode à 4 points (projection parallèle)









Xréel

Yréel

Zréel

Xcalc.

Ycalc.

Zcalc.

errmc

dist.

-0.00

-0.00

-0.00

0.00

-0.00

0.00

0.00

0.00

5.00

8.80

0.00

5.00

8.80

0.00

0.00

0.00

7.50

4.40

0.00

7.50

4.40

0.00

0.00

0.00

2.10

7.20

1.90

2.10

7.20

1.90

0.00

0.00

2.50

4.40

5.00

2.50

4.40

5.00

0.00

0.00

2.50

1.10

1.90

2.52

1.53

1.82

18.21

0.44

4.80

5.80

2.10

4.90

5.70

2.17

17.08

0.16

0.00

8.80

-0.00

-0.94

8.72

-0.29

1.07

0.99

5.00

0.00

0.00

4.42

0.12

-0.48

3.61

0.76

4.70

3.20

2.00

5.00

3.17

2.07

41.42

0.31


Résultat du calcul avec la méthode à 5 points (projection centrale)





6.6 Etude de la stabilité

Nous présentons ici une première évaluation de la résistance des calculs au bruit. Pour cela, nous avons utilisé l'erreur de reconstruction relative décrite au début de ce chapitre.



Notation:

les points images du plan de référence sont notés mi

les points images du plan homologue sont notés mi'

les points images bruités du plan homologue sont notés mi"

les points supposés connus dans l'espace sont notés Pi

les points reconstruits dans l'espace sont notés Qi



Définition du bruit:

Nous générons un bruit blanc gaussien qui prend une valeur aléatoire dans l'intervalle [-M,M]. Ce bruit B(M) est ensuite appliqué aux coordonnées X et Y des points mi' sur le plan image homologue. Les points mi du plan image de référence sont inchangés. La valeur de M varie de 0 à 8.



Classes de points:

Pour l'application de ce bruit, nous considérons trois classes de points:


- C1 représente l'ensemble des points.

- C2 représente les points de base qui sont utilisés dans le calcul de la calibration c'est à dire 4 pour la projection parallèle, et 5 pour la projection perspective.

- C3 représente les points secondaire qui ne sont pas de base, c'est à dire C3 = C1 - C2.

Chaque point de la classe Cn, mi'(Xi',Yi') est transformé en mi"(Xi",Yi") avec Xi"=Xi'+B(M) et Yi"=Yi'+B(M), que nous notons mi"=mi' + B(M).



Méthode expérimentale:

Nous avons fait deux expérimentations sur l'exemple précédent: pyramide, qui est constitué de points mesurés dans les plans images et dans l'espace. Ces points sont déjà bruités, comme le montre l'écart entre les points réels et calculés. Cependant, ce jeu d'essai nous permet d'apprécier l'évolution de l'erreur après bruitage, sur des objets réels.

La première expérimentation a utilisé la méthode à quatre points (projection supposée parallèle) et la seconde la méthode centrale (projection perspective)

Chaque expérimentation, est divisée en trois sous expérimentations où l'on bruite une des classes de points C1, C2 ou C3.

La valeur du bruit est comprise dans une fenêtre dont la borne maximale varie de 0 à 10 pixels.

Le calcul consiste alors à mesurer pour chaque fenêtre de bruit la variation moyenne de la reconstruction sur 100 itérations.




Algorithme de l'expérimentation:

Choix de la classe Cn des points à bruiter

S= somme (dist(Pi,Pj), i<>j)

Pour M = 0 jqa 10 faire

Pour k = 1 jqa 100 faire

Pour tout mi' de classe Cn, mi"= mi' + B(M)