Chapitre2
La reconnaissance des objets 3D
2.1 Introduction
La reconnaissance d'objets tridimensionnels est un
problème qui ne cesse pas de d'efier la communaut'e de vision par
ordinateur. La preuve de l'existence de la solution (le système de
vision humain), motive les chercheurs dans ce domaine. Ce problème peut
être d'efini par la reconnaissance des objets pr'emod'elis'es dans une
base de donn'ees a` partir des donn'ees acquises de la scène. La
reconnaissance signifie l'identification et la localisation des objets
pr'esents dans la scène. Un système de vision
»intelligent» doit être capable de reconnaàýtre
les objets existants dans son environnement (identification) et les situer
(localisation). La majorit'e des systèmes de reconnaissance d'objets
actuels tente de r'esoudre ce problème, en se basant sur un
modèle (les objets sont connus a` priori). La plupart de ces
systèmes travaillent sur des objets dits rigides (non d'eformables) ou
articul'es. Un Système de Reconnaissance d'Objets (SRO) complet comprend
diff'erents modules : calibration de capteurs, mod'elisation 3D, traitement
d'images de la scène et la reconnaissance proprement dite. Selon le type
de capteurs utilis'e, la reconnaissance d'objets 3D peut être trait'ee en
3D/3D (capteurs t'el'em'etriques, st'er'eoscopiques ou s'equences d'images) ou
en 2D/3D bas'ee sur une seule image de luminance. L'approche t'el'em'etrique
pose des problèmes de mise en oeuvre, de limite de port'ee et de
lenteur. L'approche a` plusieurs images (st'er'eo ou s'equences) possède
des difficult'es d'appariement entre les diff'erentes images d'entr'ee. Une
seule image d'entr'ee ne fournit pas d'informations 3D (profondeur), elle donne
lieu a` un grand nombre d'hypothèses sur la reconnaissance. Peu de
Systèmes de Reconnaissance d'Objets utilise la dernière
approche.
2.2 Classification des syst'em de reconnaissance des
objets polyedrique
De nombreuses approches au problème de la
reconnaissance d'objets 3D ont 'et'e d'evelopp'ees dans la litt'erature. Elles
peuvent être classifi'ees selon les m'ethodes et techniques mises en
oeuvre :
· Acquisition et repr'esentation informatique du
modèle 3D.
· Approche utilis'ee pour l'appariement.
2.2.1 Acquisition et Repr'esentation Informatique du
modèle 3D
Les m'ethodes les plus connues pour l'acquisition du
modèle 3D sont la CAO, les capteurs actifs (t'el'emètres laser)
et les capteurs passifs (cam'era unique, st'er'eo ou plus). Elles impliquent
des m'ethodes de repr'esentation de donn'ees adapt'ees.
1. Méthodes basées sur La CAO
L'approche Conception Assist'ee par Ordinateur (CAO) est la
plus dominante car elle d'ecrit un modèle 3D sans erreur de capture;
elle est applicable aux environnements industriels. En revanche, elle
possède des inconv'enients majeurs :
· L'implication d'un op'erateur humain lors de la
mod'elisation de la scène.
· La difficult'e d'application pour des objets naturels.
Plusieurs types de repr'esentation du modèle 3D adapt'es
a` la CAO existent
· volumique, la g'eom'etrie constructive des solides
consiste en la repr'esentation de l'objet a` mod'eliser en diff'erents
'el'ements simples qui s'appellent primitives et a` les lier par des
op'erateurs ensemblistes (union, intersection, etc.)
· Surfacique, la repr'esentation par les bords (BREP :
Boundary REPresentation) permet de construire un modèle
face/arête/sommet.[SHA99]
2. Méthodes basées sur des mesures capteurs
La m'ethode des capteurs t'el'em'etriques est plus facile a`
employer mais elle introduit des mesures impr'ecises et incertaines dans la
phase de reconnaissance. Il faudra toujours r'epondre a` certaines questions
lors de l'acquisition telles que : »combien de vues fautil pour couvrir
toutes les informations n'ecessaires ?» ou»comment faut-il segmenter
les images pour obtenir les descriptions surfaciques ou volumiques de l'objet
?». Ce sont des questions auxquelles il est difficile de r'epondre et qui
constituent des problèmes ouverts en recherche. Les m'ethodes
d'acquisition des modèles 3D en utilisant des capteurs photom'etriques
(une seule cam'era statique ou en mouvement, avec ou sans mod'elisation des
sources lumineuses, deux cam'eras ou plus), sont les plus difficiles a` mettre
en oeuvre. En
effet, elles posent les mêmes problèmes que les
m'ethodes appliqu'ees aux capteurs actifs en sus du problème de la
projection perspective et de la perspective inverse. Plusieurs techniques ont
'et'e utilis'ees pour calculer la position 3D (techniques st'er'eos, s'equences
d'images, etc.) Ces m'ethodes sont rarement employ'ees pour l'acquisition des
modèles 3D dans les SRO. Mais, elles sont prometteuses car moins
on'ereuses, plus g'en'erales et adapt'ees a` de nombreux environnements. La
repr'esentation des scènes r'ef'erenc'ee capteurs peut se d'ecomposer en
deux types selon ceux-ci (actifs ou passifs). Le problème d'ecisif de la
repr'esentation est la segmentation des donn'ees en primitives fiables pour la
reconnaissance. Or, le processus de segmentation est d'etermin'e par le type de
repr'esentation utilis'e. En g'en'erales repr'esentations 3D sont surfaciques
ou volumiques.
La capture passive des scènes est la plus proche du
système de vision humaine. L'utilisation des images de niveaux de gris
introduit elle aussi le problème de segmentation. Les deux principales
m'ethodes utilis'ees a` ce niveau sont l'approche contour et l'approche
r'egion. Il existe d'ailleurs des systèmes qui m'elangent les deux
approches.
2.2.2 Principales approches d'appariement
L'appariement ou la mise en correspondance entre la
scène et son modèle 3D est le point crucial d'un SRO. L'approche
de l'appariement utilis'ee dans un SRO marque souvent ses performances. Nous
pr'esentons ci-dessous un aperçu de la complexit'e algorithmique de ce
problème, puis les principales approches de r'esolution.[SHA99]
Complexitéde l'appariement
soit :
O : l'ensemble des caract'eristiques d'un objet (sommets et/ou
arêtes et/ou faces ...) D : l'ensemble des caract'eristiques des donn'ees
de son image
n : le nombre des caract'eristiques de l'objet
m : le nombre des caract'eristiques des donn'ees de son image
l min (n, m); m >= n car il y a souvent plusieurs objets
dans la scène, dont le modèle 3D n'est pas connu. Une solution
optimale peut être trouv'ee en cherchant tous les appariements possibles.
Du fait d'occlusions et de caract'eristiques du capteur utilis'e, il faut
comparer un sous-ensemble (de taille i) de D et de O [HORAUD 1993]. Le nombre
de possibilit'es d'appariement entre O et D est :
N=
|
X j
i=k
|
cn i .cm i .i! =
|
X j
i=k
|
n!
(n - 1)!.i! ×
|
m!
|
= m!.n!.
|
X j
i=k
|
1
|
|
|
|
k repr'esente le nombre d'appariement minimal pour trouver une
transformation objet/capteur. N s'accroàýt rapidement en fonction
du nombre d'objets dans la base.
Exemple Soit un objet contenant 18 sommets, l'extraction de ces
sommets dans une image 2D fournit 11 points. Le nombre de possibilit'es
d'appariement
c11
i .c18
i .i! = 4.34 × 1034
1 1
N= X
i=3
Pour trouver une solution optimale, il faut v'erifier toutes ces
possibilit'es.
solution
Deux techniques d'appariement pr'edominent :
· l'approche graphe.
· l'approche hachage g'eom'etrique (indexation
g'eom'etrique).
L'approche bas'ee sur les règles d''evidences peut
compl'eter les deux approches pr'ec'edentes
1. Travaux basés sur l'approche graphe
Dans l'approche graphe, les noeuds repr'esentent les
primitives de l'objet et les arêtes repr'esentent les relations entre
elles. Le problème se ramène donc a` un problème
d'isomorphisme, puisque la scène est en g'en'eral un sous graphe du
graphe de l'objet. Malheureusement ce problème NP-complet1
est très difficile a` r'esoudre et devient insoluble quand le nombre de
modèles dans la base est important. Les essais pou r'eduire la taille du
graphe utilis'e pour l'appariement ont conduit a` des diff'erentes
techniques.
Ayache et Faugeras [AYA 86] ont propos'e l'utilisation d'un
triplet de segments ayant un sommet commun. Cette technique permet de r'eduire
consid'erablement le nombre d'appariements possibles. Lowe [LOW 87] a propos'e
l'am'elioration du traitement d'images. Il a 'etabli des critères de
regroupement des indices 2D afin d'obtenir des primitives consistantes qui
facilitent l'appariement. Par ailleurs, un degr'e de probabilit'e est attribu'e
a` une hypothèse d'appariement afin de r'eduire l'espace des solutions
et enfin, une reconstruction 3D est effectu'ee pour v'erifier les
hypothèses d'appariement.
Pampagnin et Devy [PAMP91] ont introduit le Graphe de
Compatibilit'e qui regroupe dans ses noeuds toutes les hypothèses
d'appariement entre une chaàýne de segments 2D et une face d'un
aspect du modèle 3D dont les arcs repr'esentent les compatibilit'es
entre hypothèses d'appariement. L'utilisation du Graphe d'Aspects permet
de limiter la taille du graphe de compatibilit'e.
2. Travaux basés sur l'approche du hachage
géométrique
Lamdan et Wolfson [LAM 1988] ont introduit le Hachage
G'eom'etrique (HG). Il
consiste en la cr'eation hors ligne d'une table de
hachage (TabH) et une reconnais-
sance en ligne. La table de hachage
contient les diff'erents aspects des objets du
'Ensemble des problèmes pouvant être résolus
par des algorithmes Non déterministes en temps Polynomial. Complet :
veut dire qu'il n'existe pas un algorithme P efficace pour le résoudre
[SED 90].
modèle 3D, exprim'es dans des bases diff'erentes (une
base peut être repr'esent'ee par 2, 3 points ou arêtes) [WOLFSON
1992]. Cette expression est bas'ee sur des invariants ou des quasi invariants
g'eom'etriques [BIN 1993] et [GROS 1995]. Pour chaque entr'ee dans cette table,
il y a une liste des modèles susceptibles de satisfaire l'appariement.
La reconnaissance en ligne est obtenue par mise en correspondance de points 2D,
exprim'es a` leur tour dans diff'erentes bases, avec le contenu de la table de
hachage. Cette approche a l'avantage de r'eduire l'espace de recherche des
modèles possibles, sp'ecialement dans les grandes bases de donn'ees
(problème d'indexage). Son d'efaut est l'augmentation rapide de la
taille de la table de hachage en fonction du nombre de modèles.
2.1.l'algorithme d'indexation géométrique
L'algorithme d'indexation g'eom'etrique est sch'ematis'e a` la
figure 2.1 . Il se divise en deux phases, une phase de pr'etraitement
(hors-ligne) et une phase de reconnaissance (en-ligne). Cette subdivision
permet de r'eduire le temps de r'eponse a` l'usager, en effectuant une seule
fois le pr'etraitement sur la banque de modèles, avant d'appliquer la
reconnaissance sur plusieurs scènes diff'erentes. [BUS2001]
1.
FIG. 2.1 - Sch'ema de l'algorithme d'indexation
g'eom'etrique
Prétraitement La phase de prétraitement consiste
en trois étapes, qui sont répétées pour chacun des
modèles reçus en entrée. Tout d'abord, une base est
construite avec trois points du modèle. Ensuite, les coordonnées
de chaque autre point du modèle sont calculées dans cette base.
Finalement, ces coordonnées sont insérées dans une table
a` adressage dispersé(hash table), avec quelques autres informations
pertinentes (le modèle, la base et le point). Ces étapes sont
répétées pour toutes les bases possibles dans le
modèle. Il y a donc de la redondance dans le traitement, mais ceci est
fait pour permettre la reconnaissance même si un des points d'une base
n'est pas présent (ou est trop bruité) dans la scène.
C'est ce qui fait que l'indexation géométrique est robuste aux
occultations, c'est a` dire les cas o`u certains objets ne sont que
partiellement visibles dans la scène.
FIG. 2.2 - Exemple de cas o`u un modèle est
présent dans la scène. Les coordonnées d'un sous-ensemble
des points du modèle sont les mêmes que celles d'un sous ensemble
des points de la scène.
C'est le fait de calculer les coordonnées des points du
modèle dans une base formée elle aussi de points du
modèle, qui fait en sorte que l'indexation géométrique
permet de reconnaàýtre un modèle peu importe sa pose dans
une scène 3D. En effet, lorsqu'un modèle est présent dans
une scène, il y a une transformation qui amène un sous-ensemble
de points du modèle vers un sous-ensemble de points de la scène.
Comme les coordonnées de ces points du modèle coincideront avec
celles des points correspondants de la scène, l'algorithme
détectera ce modèle. La figure 2.2 en montre un exemple. Le
modèle est un poster et, dans la scène, ce poster est
accrochésur le mur, au dessus de la table. Les coordonnées qui
coincident sont encerclées. [BUS2001] En bref, le but du
prétraitement est d'extraire des informations utiles concernant les
modèles et de les emmagasiner de façon rapidement accessible. La
reconnaissance consiste a` extraire des informations similaires dans la
scène et a` chercher si elles sont présentes dans les
modèles. Essentiellement, les informations utilisées sont des
descriptions g'eom'etriques des modèles, invariantes a`
leur position et orientation dans l'espace. Ceci gràace a` la formation
de r'ef'erentiels de coordonn'ees (ou bases) a` partir de points de chaque
modèle, dans lesquels le reste du modèle est repr'esent'e.
L'indexation g'eom'etrique est une approche de reconnaissance d'objets robuste
aux occultations, c'est-à-dire les cas o`u certains modèles
pr'esents dans la scène ne sont que partiellement visibles. Elle permet
d'effectuer la reconnaissance simultan'ee de plusieurs objets dans une banque
de modèles efficacement, sans besoin de traiter chacun ind'ependamment.
Aussi, il est possible de choisir le type de transformation qui nous int'eresse
entre un modèle et son instance dans la scène, que ce soit par
exemple des transformations rigides, similaires ou affines.
Reconnaissance La phase de reconnaissance d'ebute de la
même façon que la phase de pr'etraitement. Une base est construite
avec trois points de la scène, puis les coordonn'ees de chaque autre
point de la scène sont calcul'ees dans cette base. Pour chacune de ces
coordonn'ees, un vote est effectu'e. Le vote se fait de la façon
suivante. Premièrement, on cherche dans la table a` adressage dispers'e
les bases de modèle qui, au pr'etraitement, ont donn'e des coordonn'ees
approximativement 'egales a` celles du point de la scène.
Deuxièmement, l'ensemble des points ayant servir a` construire la base
du modèle est compar'e a` l'ensemble des points ayant servi a`
construire la base dans la scène pour valider la correspondance des
bases. Si c'est le cas, un vote est ajout'e pour cette paire de bases. Dans
l'algorithme original, le vote est toujours unitaire, mais on peut aussi
utiliser un vote pond'er'e ayant un poids variable entre 0 et 1, selon la
distance entre les coordonn'ees. Une fois le vote compl'et'e, une nouvelle base
est choisie dans la scène et les 'etapes pr'ec'edentes de la phase de
reconnaissance sont r'ep'et'ees jusqu'àce que toutes les combinaisons de
trois points de la scène aient 'et'e parcourues (en r'ealit'e, il n'est
pas n'ecessaire de traiter chacune des bases. Si une certaine paire de bases a
obtenu un grand nombre de votes, un modèle est d'etect'e dans la
scène. Les points de ce modèle sont retir'es de la scène,
ainsi d'autres modèles pourront être reconnus en r'ep'etant la
phase de reconnaissance (nous verrons que ceci peut être fait d'une
façon plus efficace). Finalement, la position des modèles
reconnus dans la scène est d'etermin'ee par une estimation de pose.
[BUS2001]
Le processus d'indexation Le processus d'indexation analyse
une image et essaye de trouver quels objets y sont pr'esents dans la
scène. L'impl'ementation actuelle permet l'analyse des images contenants
un ou plusieurs objets a` la fois.
. Prend une image, elle peut contenir plus d'un objet
· Essaye de réduire au mieux le bruit contenu dans
l'image
· Divise le graphe-image en composantes connexes de
facon que chaque composante provienne au mieux possible d'un objet
identique. Pour chacun de ces graphes le même processus d'indexation.
:
(a) Extrait respectivement les figures fondamentaux et les
intersections.
(b) Calcul le code de hachage pour chaque graphe et chaque
intersection. Celui-ci est obtenu de la même facon que pour le
processus de la base de données.
(c) Fournit la liste de modèle respectif en indexant dans
la base de modèle.
Les modèles qui ont recus le plus de votes
sont sélectionnés comme les candidats les plus proches de l'objet
en question La même procédure est répétée
pour le reste des composants connexes (objets) dans l'image [SOS92]
FIG. 2.3 - schéma processus du d'indexation
| 
