Reconnaissance d’objets 3D par points d’intérêt

Typologie des approches de reconnaissance 3D

La détermination de la similitude entre les objets 3D consiste à définir une signature et une mesure de similarité. Outre la reconnaissance 3D, la recherche par le contenu ou « l’indexation 3D » s’intéresse à cette notion. L’analyse de la littérature des approches de ces deux domaines montre qu’il existe une variété de descripteurs qui dérivent de différents aspects des objets 3D. Nous avons choisi comme première répartition d’adopter celle évoquée par Zaharia et Prêteux (Zaharia, et al., 2002). Si certaines méthodes caractérisent les modèles 3D par leurs propriétés géométriques, d’autres se fondent sur les projections 2D des modèles. Ces projections 2D encodent une information tridimensionnelle. De ce fait, une distinction des descripteurs en deux familles est possible: famille des approches 3D et famille des approches 2D/3D. Une deuxième répartition, proposée par Campbell et al. (Campbell, et al., 2001), répertorie les méthodes de reconnaissance selon la nature de la représentation de la forme 3D et Exemple Sげ;ヮヮヴWﾐデｷゲゲ;ｪW Prétraitement Apprentissage Description Prétraitement Exemple à Classification classifier Description extraite SHAIEK Ayet Page 42 considère : les approches locales et les approches globales (ou holistiques) (Roth, et al., 2008). Zhao et al. (Zhao, et al., 2003) rajoutent une troisième classe qui regroupe les méthodes caractérisant localement et globalement le modèle 3D. Dans cette partie, nous présentons dans un premier temps quelques approches 2D/3D en les subdivisant en locales et globales et dans un deuxième temps les approches 3D avec la même sousclassification de localité et globalité.

Approches 2D/3D

Parti du constat que deux modèles γD sont similaires s’ils ont le même aspect de la forme sous tous les angles de vues, le traitement direct de la forme 3D est remplacé par des projections 2D sous formes d’images de profondeur, des silhouettes ou encore de cartes de courbures (Diego, et al., 2010). En effet, les images de profondeur permettent de déduire les propriétés topologiques et structurales de l’objet et offrent ainsi une description riche de la forme 3D. 

Approches 2D/3D globales

Les approches globales couvrent l’information de tous les pixels de l’image. L’idée est de projeter les données initiales dans un sous-espace qui représente les données de manière optimale selon un critère précis : par exemple, dans le cas de l’ACP (analyse en composantes principales) la variance est minimisée, dans l’ACI (Analyse en Composantes Indépendantes), l’indépendance des composantes est visée, etc. L’un des avantages de ces méthodes est qu’à partir des descripteurs calculés une reconstruction du modèle original est possible. Cependant, ces approches sont sensibles aux occultations, aux variations d’illumination et de l’échelle, et aux déformations géométriques locales (expressions du visage par exemple), ce qui nécessite une étape de normalisation lors du prétraitement. Souvent, cette normalisation automatique ou manuelle (choix de points références) détériore la performance de la reconnaissance. • Chaouch et Verroust-Blondet (Chaouch, et al., 2007) proposent de représenter un modèle 3D par 20 images de profondeur. A chaque image est associé un descripteur de lignes de profondeurs. Ces lignes sont obtenues par une méthode de mise en séquences qui part de l’espace des points pour former une séquence d’éléments. Son principe est de coder une ligne de profondeur en N états d’une séquence d’observations. Chaque observation est représentée par un état parmi 5 défini en correspondance avec 5 types de région (fond intérieur, fond extérieur, profondeur croissante, profondeur décroissante, profondeur stable). Finalement, la distance de programmation dynamique (DPD) est utilisée pour le calcul de similarité entre les descripteurs des lignes de profondeurs. • Les travaux de Vranic et Saupe (Vranic, et al., 2000) présentent le premier descripteur basé sur les images de profondeur, le « Depth Buffer-based Descriptor » (DBD). Pour assurer un comportement invariant géométriquement, chaque objet 3D est normalisé avec une ACP par rapport à un cube d’axes parallèles à ceux du repère intrinsèque à l’objet 3D. En projetant le modèle sur les six faces de ce cube, des images de profondeur sont calculées et transformées dans l’espace de Fourier en utilisant la 2DFFT (Fast Fourier Transform). La signature de l’objet 3D est extraite en gardant les coefficients bassefréquence pour chaque image de Fourier traitée. • Les Eigenspaces utilisés par Murase et Naya (Murase, et al., 1995) et les Eigenfaces utilisés par (Tsalakanidou, et al., 2003) et par (Chang, et al., 2003) permettent un appariement holistique. Le  principe de cette technique est de projeter les images de profondeur sur un sous espace en appliquant une ACP (trouver les composantes principales). Les primitives correspondent au résultat du produit scalaire des images avec les premiers vecteurs propres obtenus (correspondant aux plus grandes valeurs propres). La signature est une somme pondérée de ces primitives. Une image test est projetée sur les vecteurs propres de la base. L’appariement utilise la classification avec une méthode de plus proche voisin (plus proche primitive selon un critère de distance). • Dans le cadre de vérification des visages, Diego, et al (Diego, et al., 2010) calculent des ondelettes de Gabor sur trois types de représentations de données : des images de profondeurs, des images 2D et des images de courbures moyennes. Pour générer la carte des courbures de la surface de l’objet γD, en chaque point, la moyenne des courbures minimales et maximales des polygones du maillage est calculée. Avec les informations des courbures, la surface du modèle 3D épouse alors la surface d’une forme élémentaire. Les filtres de Gabor peuvent être définis comme un plan d’ondes orientées dans une direction multipliée par une enveloppe gaussienne 2D. Les filtres de Gabor sont connus comme un moyen d’analyse espace-fréquence très robuste. Cette spécificité a fait des filtres de Gabor un puissant moyen d’analyse pour la classification. Ces filtres analysent l’information (profondeur, texture ou courbure) d’un objet suivant différentes résolutions et différents angles. Dans le domaine spatial, un filtre de Gabor 2D est une fonction à noyau gaussien modulé par une onde sinusoïdale plane complexe. La famille des filtres de Gabor est caractérisée par un certain nombre de résolutions, d’orientations et de fréquences, qui forment la signature de l’objet. • Courbes de niveau des profondeurs : Samir, et al. (Samir, et al., 2006) proposent d’apparier deux surfaces faciales par la comparaison des courbes faciales. L’approximation grossière de la surface faciale S, par un ensemble fini de courbes de niveau fermées, génère les courbes de niveau d’une fonction de profondeur où les indexes correspondent aux valeurs de cette fonction (Figure 2-2). Les courbes de niveau des profondeurs de deux surfaces de visages sont comparées par un outil de l’analyse Riemannienne des formes qui est la distance géodésique. Après extraction des courbes faciales à partir des images de profondeurs, une fonction d’angle est calculée pour chaque courbe et permet d’estimer les longueurs géodésiques. Une métrique sur les formes faciales est déduite en cumulant les distances entre les courbes faciales. Figure 2-2. Représentation des courbes faciales. En haut : six expressions faciales de la même personne. En bas: la même expression faciale de six personnes différentes (Samir, et al., 2006) 

Approches 2D/3D locales

L’une des approches les plus populaires pour représenter la surface est celle basée sur les descripteurs locaux ou une signature qui décrit la région locale. Les positions de la surface où sont estimés les SHAIEK Ayet Page 44 descripteurs locaux peuvent être simplement choisis d’une façon exhaustive ou aléatoire. Dans le cas d’une sélection exhaustive, la redondance dans des régions, ayant une légère variation de la forme, rend cette technique inefficace. La sélection aléatoire peut négliger certaines zones ayant une structure géométrique distincte ce qui réduit la performance de l’algorithme. Ainsi, extraire un ensemble représentatif de points primitives permet de remédier à ces problèmes. Plusieurs méthodes de reconnaissance d’objet, dont celles de Johnson et Hebert (Johnson, et al., 1999), et Frome, et al (Frome, et al., 2004)), ont suggéré d’utiliser un jeu de points choisis aléatoirement pour calculer les descripteurs de surface. D’autres ont tenté d’extraire efficacement des points. Dans le cas des approches locales qui détectent des régions saillantes, les invariants de l’objet peuvent être par exemple les coins, l’entropie, les niveaux de gris, les contours, la texture, la symétrie, etc. En reconnaissance de visages, des modèles peuvent être générés à partir des relations entre les formes géométriques ou la luminance des différentes parties de l’objet (le nez, les yeux, la bouche, le visage,…). A chaque région est attribué un descripteur de primitives. Ces primitives locales doivent répondre aux critères suivants: – assez discriminantes pour différencier un objet d’un autre, –reproductibles pour être détectables au même endroit de l’objet dans différentes scènes, –riches en information caractérisant la topologie, la forme ou la texture locale l’objet. –invariantes aux changements d’illumination, du bruit, d’échelle, de vues… –robustes au: bruit, occultations partielles et variations intra-classes. En général, une seule primitive ne permet pas de satisfaire tous ces critères, une combinaison de primitives est souvent utilisée. Les algorithmes d’appariement pour les primitives locales mettent en correspondance, soit directement les primitives, soit leurs distributions statistiques. Dans le cas particulier où la région saillante est réduite à un point, la notion de Point d’Intérêt (PI) est introduite. Dans ces approches, deux étapes sont nécessaires: d’abord, déterminer les régions de l’image qui doivent être comparées aux régions dans la seconde image (détection). Ensuite, générer des signatures invariantes pour comparer les régions sélectionnées (descripteurs). En 2D, les investigations pour caractériser des détecteurs et descripteurs locaux des PIs ne cessent de s’enrichir. Avec le succès de cette approche locale, plusieurs travaux cherchent à adapter à la tridimensionnalité les méthodes du 2D. Nous listons ci-dessous quelques une des approches 2D/3D locales. • Des primitives locales boostées sont introduites par Viola et Jones (Jones, et al., 2003) pour associer des régions rectangulaires des images de visages à différentes localisations, échelles et orientations. Une mesure de similarité consiste en une combinaison linéaire de primitives fi qui sont des filtres appliqués à une paire d’images : Le terme ti est un seuil sur les primitives et 剛i une fonction scalaire qui représente un filtre rectangulaire. Dans la Figure 2-3, les filtres rectangulaires sont calculés en additionnant les intensités de tous les pixels dans les régions sombres et en soustrayant la somme des intensités de tous les pixels dans les régions claires. Les entrées de l’étape d’apprentissage sont constituées d’une grande base de filtres rectangulaires et un jeu d’exemples positifs et négatifs. L’algorithme d’Adaboost est utilisé pour trouver les meilleurs filtres (剛i), les seuils (ti) et les poids (膳 et 紅) pour créer un classificateur qui sépare les exemples positifs (des mêmes paires de visage) des exemples négatifs (des paires de visages différentes). SHAIEK Ayet Page 45 Figure 2-3. Exemples de filtres rectangulaires (Jones, et al., 2003) •L’histogramme de primitives locales (local feature histogram) a été exploré dans le travail de Hetzel et al. (Hetzel, et al., 2001) pour reconnaitre des objets de forme libre sur des images de profondeurs. La signature a regroupé la profondeur des pixels, les normales de la surface er les courbures. La combinaison de ces primitives dans un histogramme multidimensionnel offre un cadre probabiliste permettant de gérer entre autres le problème de l’occultation. L’avantage de l’histogramme des distances est son invariance à la translation, aux rotations et à l’échelle si la distance est normalisée. Par contre, les distances normalisées sont sensibles aux intervalles de la profondeur perçue et au bruit du fond. Une paire d’angles des normales définies en coordonnées sphériques est considérée pour une représentation 2D des normales (Figure 2-4). L’indice de formes (défini dans le chapitre 1) est utilisé pour représenter les courbures de la surface. Les courbures peuvent être calculées directement par les dérivées premières et secondes, ou indirectement comme le taux de changement des orientations des normales dans une région locale. La robustesse aux angles de vues et la discrimination de l’information sont prouvés par ces primitives. La reconnaissance est établie par un appariement direct des histogrammes ou par une reconnaissance probabiliste. Figure 2-4. Représentation des normales en coordonnées sphériques (Hetzel, et al., 2001) •Une approche hybride : (Mian, et al., 2006) proposent un algorithme de reconnaissance hybride: locale et globale. La localité consiste à segmenter le visage en trois régions qui sont appariées avec un algorithme d’ICP (Iterative Closest Point) modifié. L’ICP est un algorithme utilisé pour l’alignement en minimisant une distance quadratique carrée entre les points les plus proches dans un processus itératif. Pour l’appariement holistique un algorithme basé sur l’ACP est utilisé. 

Approches 3D

Les données considérées pour les approches 3D se présentent sous formes de nuage de points ou sous forme de représentation polygonale (maillage). Ces approches tentent de caractériser la forme 3D avec une description indépendante de la topologie 3D. En effet, la topologie d’une forme peut varier sous l’effet : des déformations internes (expressions du visage) ou externes (bruit et occultations), ou de la façon de modéliser la forme comme la résolution du nuage de points (nombre de points), ou le nombre des facettes (tessellation du maillage). Ces techniques peuvent être classées selon leur portée en locale ou globale. 

Approches 3D globales

Nous pouvons subdiviser les méthodes holistiques 3D en deux catégories: approches surfaciques et approches volumiques. • Distribution de forme : Cette signature proposée par (Osada, et al., 2001) pour un modèle 3D polygonal se base sur une fonction de forme qui mesure les propriétés géométriques globales d’un objet. L’apport principal de cette méthode est, en premier lieu, le calcul de la signature avec la spécificité aléatoire de l’échantillonnage permettant de construire une distribution continue de probabilité. En deuxième lieu, une simple comparaison des distributions de probabilité est requise contrairement aux méthodes qui font appel à une reconstruction d’objets solides, une mise en correspondance de primitives ou un ajustement des modèles. Des primitives simples à mesurer sont considérées: la distance entre le centre de gravité et un point de la surface, la distance entre deux points, l’angle entre trois points, l’aire au carré du triangle formé par trois points et le volume au carré du tétraèdre formé par quatre points. Les points concernés par le calcul des primitives sont choisis arbitrairement sur les facettes, conférant à cette méthode une invariance aux modifications du nombre de facettes. De plus, l’échantillonnage pondéré et la normalisation permettent d’assurer une robustesse au bruit et une invariance par rapport aux changements d’échelle. Les modèles sont comparés en évaluant des mesures de similarité avec la norme LN, des fonctions de densité de probabilité (pdfs) et des fonctions de distribution cumulative (cdfs). • Les EGI (Image Gaussienne Etendue, Extended Gaussian Images) (Horn, 1984) caractérisent une fonction synthétisant l’information d’orientation en tout point de la surface de l’objet 3D (Figure 2-5). Un histogramme d’orientation, en tant qu’approximation discrète des EGI, est calculé sur la sphère unité de Gauss. En effet, l’information des normales de la surface peut être mappée sur la sphère unité de Gauss subdivisée en cellules. Le mapping utilisé consiste à associer l’inverse de la courbure gaussienne de chaque point de la surface de l’objet avec le point correspondant ayant la même normale dans la sphère gaussienne. Ce mapping est réversible si l’objet a partout une courbure gaussienne positive. Si u et v sont les coordonnées du point dans la surface originale, つ et た les paramètres du point dans la sphère de Gauss (peuvent correspondre par exemple à la longitude et latitude), . Dans les versions plus élaborées, cette fonction est pondérée par l’aire des facettes ou leur distance à l’origine d’un repère préalablement spécifié. L’EGI est invariant par translation et par rotation. La faiblesse majeure de cette approche est que plusieurs objets convexes peuvent avoir le même EGI. L’appariement entre deux objets revient à mettre en correspondance les deux histogrammes des EGI par le calcul de la distance Euclidienne. SHAIEK Ayet Page 47 Figure 2-5. A gauche-E┝WﾏヮﾉWゲ SげﾗHﾃWデゲ ;┗WI ﾉW ﾏZﾏW EGI-A droite- un objet avec la sphère de Gauss (Horn, 1984) •Une approche qui s’inspire de la théorie de la reconnaissance par composantes (Recognition By Components, RBC) proposée par (Biederman, 1987) consiste à identifier à l’aide d’un appariement de superquadriques des primitives de forme appelées géons. Ces géons décrivent qualitativement des volumes élémentaires (sphères, cylindres, cônes, etc.) d’un corps. A ce titre, ils permettent une identification sommaire mais rapide des objets. (Medioni, et al., 2000) proposent une modélisation par sous-parties volumiques des objets 3D à base de géons. Après une décomposition de l’objet 3D en géons, ces éléments sont hiérarchiquement organisés dans un arbre de description avec des relations d’adjacence. Cette structure hiérarchique permet en outre de calculer plus efficacement une mesure de similarité fondée sur un coût de transition issu d’une méthode d’appariement par graphes. Les images à attribut sphérique (Spherical Attribut Images : SAI) (Hebert, et al., 1995) permettent également de reconnaitre des objets de topologie proche de la sphère. • Le SF3D (descripteur par spectre de forme 3D) présentés par Zaharia et Préteux dans (Zaharia, et al., 2002). Le SFγD est un histogramme de l’indice de forme qui fournit une représentation intrinsèque des caractéristiques géométriques locales de la surface 3D. Cet indice est défini par la valeur de la coordonnée angulaire de la représentation polaire du vecteur de courbures principales. Invariant aux transformations euclidiennes et aux homothéties, ce descripteur n’est cependant pas robuste aux représentations topologiques. • La transformée de Fourier proposée par (Vranic, et al., 2001), permet de caractériser l’information spatiale des objets γD dans l’espace fréquentiel. L’extraction des primitives se fait après une étape de normalisation en utilisant une ACP continue et une voxelisation du modèle 3D. Les composantes du vecteur primitives sont les valeurs absolues des coefficients de la transformée de fourrier discrète 3D (3D DFT) appliquée aux voxels. Ces descripteurs sont invariants à la translation, la rotation, le changement d’échelle et la réflexion. • Le DH3DO, introduit par (Zaharia, et al., 2002) est un descripteur dérivé de la transformée de Hough 3D. Son principe consiste à accumuler des points sur des plans de R3 . En effet, un plan dans l’espace euclidien peut être transformé, dans l’espace de Hough, en un seul point défini par les coordonnées sphériques (r, し, l). Par conséquent, une collection de plans dans l’espace euclidien correspond à une collection de points dans l’espace de Hough. Le DH3DO a été proposé pour optimiser le DH3D suite aux faiblesses que présentaient le SFγD. Il permet, en effet, d’assurer une invariance aux transformations géométriques et une robustesse vis-à-vis des représentations topologiques multiples.