**** Pages temporaires - en restructuration ****
Quel
est
la fonctionalité d'un algorithme de stéréovision ?
C'est trouver pour un point de l'image de référence
(image choisie arbitrairement) le point de la seconde image qui
représente le même objet dans la scène spatiale
(exemple : la pointe d'un clocher).
Simple ? Pour l'oeil humain oui, pas pour un algorithme.
A
quoi
ça sert ?
Une fois les points entre deux images associés par un algorithme
de stéréovision, il est
aujourd'hui relativement facile de créer un modèle 3D de
la
scène observée.
Les jeux 3D actuels projettent un modèle 3D texturé pour
former une image 2D affichée à l'écran.
L'information initiale est en quelque sorte dégradée (3D
vers 2D).
Le but principal de la stéréovision est d'inverser ce
processus : recréer un modèle 3D à partir d'images
2D. Dans ce cas, l'information initiale est augmentée (2D vers
3D, le modèle 3D permettant de retrouver les images initiales
par projection et même de créer des images suivant
d'autres points de vue).
D'autres utilisations secondaires peuvent être la
détection et le pistage d'objets en mouvement, la
super-résolution...
Paire
d'image stéréo
Prises dans les Vosges avec un appareil photo numérique et
réduites
(400x300). Le photographe s'est déplacé entre les deux
photos de façon
à faire apparaitre le 3D de la scène. En effet, une
rotation seule ne
conduit qu'à un décalage des images qui est cependant
intéressant pour
créer une mosaique d'images (images collées pour en faire
une plus
grande).
Les
algorithmes actuels
Un algorithme classique est la corrélation par fenêtre :
pour chaque
point de l'image de référence, on "découpe" une
vignette (par exemple 9
pixels de haut et de large) centrée sur ce point, on la compare
à
différents endroits de la seconde image et l'on garde l'endroit
qui
correspond le mieux. La mesure de ressemblance entre deux vignettes
s'appelle la "corrélation". Il existe de nombreux types de
corrélation,
chacun ayant ses avantages et inconvénients. La
différence
de
position entre les
points associés s'appelle la "disparité".
Aucun algorithme actuel n'est satistfaisant car aucun ne cumule les
caractéristiques suivantes :
- Rapidité d'exécution
- Précision de localisation des discontinuités
de
relief (principal problème de la corrélation par
fenêtre)
- Gestion de larges disparités. Elles entraînent
d'importante déformations entre les images.
- Robustesse au gain/offset d'intensité entre les
images
- Robustesse aux motifs répétitifs
- (Pour les connaisseurs) Gestion du cas d'un mouvement de
translation perpendiculaire au plan de la caméra (épipole
dans l'image). La distorsion géometrique près de
l'épipole pose des problèmes pour les algorithmes
nécessitant une phase de rectification (même en polaire).
Les principaux types d'algorithmes sont :
- Les algorithmes travaillant sur les segments de l'image
(contours). Ils sont rapides, les discontinuités de relief ont
une localisation précise. Mais leur résultats ne sont pas
dense. Seuls les contours détectés peuvent contenir de
l'information.
- Les algorithmes travaillant sur les régions de
l'image
(partition de l'image en morceaux connexes de forme quelconque). Ils
ont été abandonnés au début des
années 90 car la primitive région est complexe à
obtenir et à gérer d'où la difficulté de
conception de ces algorithmes. Dommage car les régions d'une
image, une fois obtenues de façon fiable, sont très
riches en information (contour, texture, géométrie,
connexité).
- Les algorithmes par corrélation de vignette. Ils
sont
rapides mais possèdent
un gros défaut : le vignettage conduit à un
phénomène de "bavure" au niveau des discontinuités
de relief. Des variations tentent de le pallier (fenêtres
adaptatives), mais ne sont pas convaincantes.
- Les algorithmes d'optimisation globale (layered stereo,
graph
cut, ...). La précision de localisation des
discontinuités de relief est impressionnante. Hélas, leur
temps de calcul est prohibitif pour des images réelles ou de
forte disparité et leur robustesse aux bruit et au gain/offset
d'intensité semble intrinsèquement faible (bizarrement,
leur auteurs n'ont pas
étudié cet aspect).
Exemple
de résultat avec un algorithme par corrélation (images
non rectifiées)
La sortie de l'algorithme est deux images, dont la "couleur" est en
fait un nombre. Pour chaque point de l'image de
référence, les points de mêmes coordonnées
dans les 2 images de sortie donnent la différence de position
(horizontale et verticale) du point associé dans la seconde
image.
Exemple : si la pointe du clocher est le point (220, 90) dans l'image
de référence et si on lit -5 et +2 en (220, 90) dans les
images de sortie, le clocher sera à la position (220-5, 90+2)
dans la seconde image.
Images des
disparités
horizontales (de -50, noir, à +20, jaune)
|
Images des
disparités
verticales (de -16, noir, à +18, jaune)
|
Les seules entrées sont les deux images non rectifiées
ci-dessus. Comme d'habitude, tous les paramètres par
défaut sont gardés, l'algorithme y étant peu
sensible.
L'algorithme en quelques mots (dont quelques uns barbares) :
- Une première mise en correspondance avec recherche
2D est
effectuée sur l'image sous-échantillonnée.
- A partir de cette estimation grossière, une seconde
mise
en correspondance partielle avec recherche 2D est effectuée sur
les images à pleine résolution. Cette phase correspond
à la recherche et mise en correspondance de points
d'intérêt dans d'autres processus algorithmiques.
- Ces points en correspondance permettent une estimation
robuste de
la matrice fondamentale (Least Median Square suivi d'une phase de
M-estimator, le calcul de la fondamentale étant fait par SVD et
annulation de la valeur propre la plus faible). Cette matrice 3x3
représente les paramètres de prise de vue entre les deux
images (à une collinéation d'espace près
(homographie en 3D)).
- Une dernière mise en correspondance dense avec
recherche
1D le long des épipolaires est effectuée sur les images
à pleine résolution. Il n'y a pas de phase de
ré-échantillonnage, la géométrie
épipolaire étant prise en compte dans l'algorithme. Ceci
permet de gérer de façon transparente les images
contenant les épipoles.
Le temps d'exécution total est de 0.52 s sur un Athlon
1800+ sous Linux. Le programme, écrit en C++, a
été
compilé avec G++ 3.2.2 avec l'option -O2.
Remarques :
- Les images de sortie ont subi une égalisation
d'histogramme.
- Les notions de relief apparaissent. Sur l'image des
disparités horizontales, la falaise proche est bleue, et la
maison lointaine est jaune.
- Le blanc indique qu'aucun point associé n'a
été trouvé. C'est le cas dans la
végétation à cause de leur déformation (les
vignettes ne se ressemblent plus assez) ainsi que dans le ciel à
cause de son ambiguité (les vignettes sont toutes grises, avec
de nombreuses localisations équivalentes dans la seconde image).
- L'algorithme par corrélation utilisé n'est
pas
standard et les temps d'exécution peuvent être plus
rapides que la
moyenne.
- Le modèle 3D sous forme de facette est encore loin :
à ce stade, la "facettisation" est un problème à
part entière si l'on désire éviter la
facettisation
canonique (1 pixel = 2 triangles) éventuellement suivie d'une
simplification du maillage 3D (qui est aussi un problème
à part entière !).
D'autres exemples de résultat :
Ndlr: Ce brouillon sera
restructuré d'ici peu, avec plus de pages, d'exemples et
de détails sur :
- La
stéréovision
par ordinateur, en général
- D'autres traitements de
l'image
(segmentation en région, réduction du bruit,
rectification polaire, point d'intérêt, tracking de
points...)
- Une alternative aux
algorithmes
de stéréovision actuels (j'espère...)
- Les liens et les
références
|
 "Click to enlarge. Click to kill.")
 "Click to enlarge. Click to kill.")
 "Click to enlarge. Click to kill.")
 "Click to enlarge. Click to kill.")