Appréciation de l’encadrant

35

35

36

37

38

38

40

41

41

42

47

48

vi

Table des figures

1

Plan du travail .

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1 Différence entre l’aspect 2D et l’aspect 3D . . . . . . . . . . . . . . . . . . . . . . .

1.2 Ensemble de données non-structurés pour la représentation 3D . . . . . . . . . .

1.3 Méthodes de représentation des modèles 3D par des solides . . . . . . . . . . . .

1.4 Les maillages triangulaires .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.5 Les courbures principales obtenues des plans tournant

. . . . . . . . . . . . . . .

1.6 Paramétrisation : un plan est décrit par un point

. . . . . . . . . . . . . . . . . . .

1.7 Distribution de forme de 6 voitures (noirs) et 5 chars (gris)

. . . . . . . . . . . . .

1.8

Index de formes pour quelques formes connues

. . . . . . . . . . . . . . . . . . .

1.9 Élaboration de l’image spin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.10 Quelques résultats pour le descripteur Spin-images . . . . . . . . . . . . . . . . .

1.11 Extraction du descripteur distribution de forme locale . . . . . . . . . . . . . . . .

1.12 Décomposition de l’espace en des bins . . . . . . . . . . . . . . . . . . . . . . . . .

2.1 Descripteur Contexte de formes 2D . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Methodes proposés pour créer la grille locale . . . . . . . . . . . . . . . . . . . . .

2.3 Chemin géodésique entre deux points . . . . . . . . . . . . . . . . . . . . . . . . .

2.4 Creation de la grille intrinsèque . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5 Propagation des lignes angulaires vers l’extérieure . . . . . . . . . . . . . . . . . .

2.6 Lancement des rayons exterieur-intérieur . . . . . . . . . . . . . . . . . . . . . . .

2.7 Choix du seuil epsilon .

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.8 Traçage des niveaux géodesiques . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.9 Elaboration de la Grille polaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

5

6

7

7

8

12

13

14

16

16

17

18

20

22

23

24

25

25

26

27

28

3.1 Reconnaissance de formes : Perception Humaine . . . . . . . . . . . . . . . . . . .

32

Rapport du projet de fin d’études-2015

Dorra Mimita

vii

TABLE DES FIGURES

3.2 Reconnaissance de formes : Processus . . . . . . . . . . . . . . . . . . . . . . . . .

3.3 Processus d’indexation .

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.4 Élaboration du descripteur .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.5

Invariance du descripteur par rapport à la rotation . . . . . . . . . . . . . . . . . .

3.6

Invariance du descripteur par rapport au changement d’échelle . . . . . . . . . .

3.7

Influence du bruit sur le calcul du descripteur

. . . . . . . . . . . . . . . . . . . .

3.8 Mise en correspondance des points dans un seul objet . . . . . . . . . . . . . . . .

3.9 Mise en correspondance des points (considérant un seuil) . . . . . . . . . . . . . .

3.10 Système de reconnaissance de forme : exemple de requete . . . . . . . . . . . . .

3.11 Echantillons de la base de test

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.12 Cumulativ matching curve : courbe de correspondances cumulés . . . . . . . . .

32

33

35

36

37

38

39

40

40

42

43

Rapport du projet de fin d’études-2015

Dorra Mimita

viii

Introduction

Motivations

basée sur l’aspect visuel de ces derniers. À partir des images détectées par le système

LA reconnaissance des images, des scènes et des visages pour l’être humain est toujours

visuel humain, le cerveau cherche à lier ces informations, de formes, de couleurs et

de textures à l’ensemble des scènes et des images stockés dans nos mémoires.

Simuler cette faculté de reconnaître des objets sur des machines est un axe qui n’a cessé

d’attirer l’attention des chercheurs, des informaticiens ainsi que les industries d’intelligence ar-

tificielle. De récentes applications comme les jeux vidéos, le cinéma, l’archéologie, la sécurité

ou la médecine... suscitent un intérêt croissant pour la représentation et le traitement des don-

nées tridimensionnelles.

Les techniques de vision par ordinateur visent à interpréter et traiter les images et les scènes

détectées par les capteurs.

Particulièrement, la reconnaissance des objets dans le champ de vue des capteurs, déjà pro-

fondément étudiée pour les images 2D, transite maintenant vers le domaine de 3D vu que les

robots et les capteurs évoluent et qu’ils ont maintenant la faculté de générer des rendus tridi-

mensionnels.

Pour répondre à ces "nouveaux" besoins, on a intérêt à développer de nouvelles fonction-

nalités qui permettent de manipuler efficacement ces données tridimensionnelles : de point de

vue format, qualité de représentation, compression, sécurité d’échange,.. tous sont des défis à

accomplir, mais aussi, pour aboutir à une reconnaissance de forme, nous devons passer par

l’étape de chercher l’objet dans une base de données.

Rapport du projet de fin d’études-2015

Dorra Mimita

1

Introduction

Chercher un objet dans une grande base d’objets 3D, est un défi qui se basera sur certains

critères de similarité, l’objet requête et l’objet obtenu suite à la recherche doivent être visuelle-

ment similaires.

Contexte du projet

Dans ce projet, nous cherchons à faire l’indexation d’une base de données 3D. Pour cela

nous cherchons les descripteurs déjà présents, puis nous proposons un algorithme à implé-

menter.

Nous finissons par indexer une base de données d’objet 3D, tester les performances du descrip-

teur proposé, puis l’intégrer dans un moteur de reconnaissance de formes.

Ce travail est réalisé en tant que projet de fin d’études à l’Ecole Nationale des Sciences de l’In-

formatique (ENSI) au sein du laboratoire CRISTAL-Pôle GRIFT.

Planning pré-visuel du projet

Avant de commencer un travail, il faut planifier et mettre les grandes lignes à suivre. La

figure 1 décrit la chronologie qu’on va suivre

FIGURE 1 – Plan du travail

Rapport du projet de fin d’études-2015

Dorra Mimita

2

Introduction

Organisation du rapport

Nous planifions le rapport comme suit

– Une introduction générale

– Le premier chapitre est nommé "Éléments d’état de l’art", il sera consacré à une étude

approfondie des notions à utiliser ainsi qu’une étude de quelques descripteurs présents.

– Dans le deuxième chapitre "Représentation locale intrinsèque" nous parlons du descrip-

teur proposé en détaillant les étapes d’implémentation

– Dans le dernier chapitre on applique le descripteur sur l’indexation d’un objet 3D, nous

évaluons le descripteur implémenté en l’intégrant dans un système de reconnaissance de

formes.

– Nous finissons par une conclusion générale ainsi que des perspectives.

Rapport du projet de fin d’études-2015

Dorra Mimita

3

Chapitre 1

Éléments d’état de l’art

Introduction

AVant de commencer tout travail, il faut mettre le projet dans son cadre technique en cher-

chant les notions à aborder et les travaux déjà présents. C’est pour cela que nous intro-

duisons ce chapitre pour clarifier des notions que nous allons utiliser, et présenter une étude

des principes de quelques descripteurs déjà présents dans le domaine de reconnaissance de

formes tridimensionnelles.

1.1 Concepts de base

Dans la suite de ce rapport, on va utliser des termes techniques familiers pour les spécia-

listes du domaine, parfois inconnus par autruis, donc c’est dans cette section que nous mettons

en place quelques définitions et notions.

1.1.1 Présentations des données 3D

En observant un objet 3D, la question qui se pose c’est comment ces objets sont représen-

tés sur un écran planaire. Le présent travail, porte sur les objets tridimensionnels, donc il est

indispensable de présenter les structures de données utilisés.

1.1.1.1 Notion de la tridimensionnalité

L’image 2D est représentée selon deux axes(X,Y) sur un plan, cependant, la forme 3D est

représentée suivant 3 axes(largeur, longueur et profondeur) (X,Y,Z) avec Z est l’axe de profon-

Rapport du projet de fin d’études-2015

Dorra Mimita

4

Chapitre 1 : Éléments d’état de l’art

deur celui qui donne l’effet réaliste sur écran, c’est celui qui donne l’aspect proche de ce qu’on

voit dans le monde réel comme le montre la figure 1.1.

La 3D est donc une méthode de modélisation des données tridimensionnels, appelés souvent

des objets 3D.

(a) Echographie tridimensionnelle

(b) Echographie bidimensionnelle

FIGURE 1.1 – Différence entre l’aspect 2D et l’aspect 3D

1.1.1.2 Types de données 3D

Selon les modalités d’acquisition : scanner 3D, vision assisté par ordinateur, capteurs,etc..,

les types de données 3D changent et les méthodes avec lesquelles on les représente changent

aussi.

Dans cette partie nous citons quelques méthodes pour représenter les objets 3D.

Ensemble de données : L’objet 3D est représenté par un ensemble de données indépen-

dantes : ensemble de contours, nuage de points, ou encore ensemble d’images 2D. Comme

le montre la figure 1.2.

Le nuage de points, est en réalité des échantillons de l’objet 3D, non structurés obtenus à

partir du "rangefinder" ,"Mise au point télémetrique", ou par la vision assistée par ordinateur.

Cette représentation est simple mais ne fournit aucune information sur les connectivités ou

l’adjacence.

L’ensemble de contours,est une représentation généralement utile pour les géologues, car

ils travaillent sur des coupes. Cette représentation était initialement développée pour l’ima-

gerie médicale. Le problème avec cette représentation est au niveau de la reconstruction et

triangulation dans la phase d’établissement de l’appariement entre les contours.

Quant à l’ensemble des images, ce sont des images stéréoscopiques, obtenus en tournant

un objet 3D sur un axe fixe avec une vitesse constante. L’acquisition est faite avec un caméra

Rapport du projet de fin d’études-2015

Dorra Mimita

5

Chapitre 1 : Éléments d’état de l’art

fixe, ou bien en utilisant d’autres instruments. Les images 2D contiennent des informations

d’intensité alors que cet ensemble d’images contient des informations de profondeur.

(a) Nuage de Points

(b) Ensemble de contours

(c) Ensemble d’images 2D

FIGURE 1.2 – Ensemble de données non-structurés pour la représentation 3D

Les Solides 3D : C’est une représentation concrète de données 3D sous forme de solides,

ces modèles offrent une description des détails extérieurs et intérieurs de l’objet.

Parmi ces représentations, nous citons :

– Wireframe model : appelé Fil de Fer 3D, c’est la méthode la plus ancienne de représen-

tation des objets 3D. Elle représente la forme de solide par le biais des segments et des

points significatives de l’objet. Dans une base de données, 2 tables forment le wireframe

model : le tableau contenant les coordonnées des points 3D et le tableau contenant les

arêtes. Néanmoins, cette méthode présente un peu d’ambiguïté vu qu’elle n’offre pas des

détails de remplissage comme le montre la figure 1.3.

– Voxels : Cette technique, permet de subdiviser l’espace en une grille de cellules appelés

des Voxels similairement aux Pixels pour les plans 2D. Chaque Voxel est stocké avec des

données de couleurs, d’opacité etc..

Cette technique est généralement utilisée pour l’imagerie médicale en utilisant les IRM :

Imagerie à Résonance Magnétique,un exemple est illustré par la figure 1.3.

– CSG (Constructive Solid Geometry), géométrie de construction solide, cette technique se

base sur la représentation de l’objet comme ensemble de quelques objets tridimension-

nelles plus simples, l’arbre de construction est appelée CSG-arbre ( 1.3b de la figure 1.3)

Rapport du projet de fin d’études-2015

Dorra Mimita

6

Chapitre 1 : Éléments d’état de l’art

(a) Acquisiton de l’image du

cerveau IRM,

représentation

(b) L’arbre CSG d’un modèle

(c) L’ambiguité de la représen-

par voxels

simple

tation WireFrame

FIGURE 1.3 – Méthodes de représentation des modèles 3D par des solides

Les Surfaces : C’est une représentation qui décrit comme le nom l’indique la surface exté-

rieure de l’objet. Ces surfaces sont représentés par :

– Les surfaces paramétriques : une représentation dans l’espace R3 définie par une équation

paramétrique r(u, v) = {x(u, v), y(u, v), z(u, v)}

– Les surfaces implicites : consiste à représenter la surface comme l’ensemble des points

solution à une équation implicite F (x, y, z) = 0 par exemple l’équation d’un ellipse :

( x rx

)2 + ( y ry

)2 + ( z rz

)2 − 1 = 0

– Les maillages : les Mesh en anglais de la figure 1.4, c’est un ensemble de polygones

connectés entre eux, généralement des triangles, appelés des facettes. Cette représenta-

tion est composée de deux tableaux, un qui décrit l’ensemble des sommets (vertex), et

l’autre qui contient, pour chaque facette les sommets qui la composent.

C’est avec cette représentation que nous travaillons car c’est la représentation la plus

simple à modeliser par les ordinateurs et la plus utilisée dans le monde.

FIGURE 1.4 – Les maillages triangulaires

Rapport du projet de fin d’études-2015

Dorra Mimita

7

Chapitre 1 : Éléments d’état de l’art

1.1.2 Calculs géodésiques

• Courbe Géodésique : Les géodésiques sont les trajectoires d’un point matériel se dépla-

çant sur la surface et soumis à la seule réaction du normale ; on peut donc les réaliser

physiquement en faisant rouler (côté concave) des petites billes sur la surface, en état

d’apesanteur (avec pesanteur, ces lignes deviennent les lignes d’écoulement).

• Distance Géodésique : C’est la mesure de longueur du chemin géodésique entre deux

points. Ce chemin géodésique est la plus courte courbe géodésique entre ces deux points.

• Les courbures :

La courbure d’un objet géométrique est une mesure quantitative du caractère plus ou

moins courbé de cet objet. C’est aussi l’inverse du rayon du cercle osculateur(cercle qui

peut être confondue avec l’objet au plus près voisinage du point étudié).

Pour calculer la courbure en un point M, on considère un plan tournant, perpendiculaire

en M au plan tangent à la surface.

Ce plan intersecte la surface considérée en une courbe. À chacune des courbes ainsi

construites est associée sa courbure en M.

Les valeurs minimum et maximum de la courbure portent le nom de courbures principales

comme illustré par la figure 1.5.

Àpartir de cette définition on cosidère γmin et γmax On peut ainsi définir la courbure

moyenne γmoy = (γmin + γmax) ÷ 2 et la courbure gaussienne (courbure de Gauss)

γg = γmin × γmax

FIGURE 1.5 – Les courbures principales obtenues des plans tournant

Rapport du projet de fin d’études-2015

Dorra Mimita

8

Chapitre 1 : Éléments d’état de l’art

1.1.3 Les Descripteurs

Pour chercher dans une grande base de données, chaque modèle 3D doit être associé avec

un identifiant unique, qui sera son index dans cette base.

Cet identifiant unique décrit l’objet soit globalement soit partiellement de telle façon qu’il soit

significatif, c’est ce qu’on appelle DESCRIPTEUR.

Un descripteur est aussi une quantité abstraite qui représente un ensemble de données relati-

vement plus complexe.

Un descripteur, peut caractériser la forme globale d’un modèle 3D, il traduit la géométrie

ou la topologie intégrale de l’objet, il est dit un descripteur global. Il peut aussi bien décrire une

partie d’un modèle, se focaliser sur les détails locales et les paramètres d’une région de l’objet

dans ce cas il est calculé pour un point spécifique ou une région en considérant un voisinage

pré-repéré.

Certains critères sont souhaitables pour un descripteur à savoir : l’invariance maximale par

rapport au bruit, à certaines perturbations, l’invariance aux transformations, la complétude

qui garantit qu’un objet soit identifé d’une façon unique.

1.1.4 Mesures de similarité

Pour faire la mise en correspondance et repérer le taux de similarité entre le modèle requête

et les descripteurs des objets dans la base des descripteurs, il faut fixer une métrique de mesure.

Le taux de similarité, doit être quantifié par une mesure mathématique, une fonction appelée

distance entre les deux objets.

Certains l’appellent mesure de "dissimilarité" pour qu’elle soit en cohérence avec le mot

"distance". En faitn c’est plus logique de voir le taux de non-ressemblance entre deux objets et

d’ailleurs c’est ce que reflète le terme distance : Plus la distance entre deux objets est minime,

plus les deux objets se ressemblent, et plus la mesure de dissimilarité est minime, plus la me-

sure de similarité augmente.

Une métrique distance peut être ainsi définie comme étant une fonction qui a pour entrée

une pair de descripteurs et a pour sortie le taux de ressemblance inversé. Soit d : Descripteurs × Descripteurs → R+

(cid:83){0}

Comme toute distance, certains critères doivent être vérifiés à savoir :

Rapport du projet de fin d’études-2015

Dorra Mimita

9

Chapitre 1 : Éléments d’état de l’art

(cid:88) Identité ∀x ∈ Descripteurs, d(x, x) = 0

La propriété de l’identité renseigne sur le fait qu’une forme est complètement similaire

à elle même. C’est une propriété qu’on cherche souvent à satisfaire lors du processus de

reconnaissance de formes.

(cid:88) Symétrie ∀x, y ∈ Descripteurs, d(x, y) = d(y, x)

Cette propriété n’est pas assez nécessaire, car déjà il n’est pas souvent évident pour l’être

humain qu’un objet x ressemble à un objet y veut dire que y est similaire à x. Naturelle-

ment, et inconsciemment puisque la perception humaine affirme qu’un ellipse est plutôt

ressemblant à un cercle et que l’inverse n’est pas souvent affirmé, c’est que cette attitude

n’est pas fausse si elle est vérifiée par VAO(vision assistée par ordinateur) [21].

(cid:88) Positivité ∀x (cid:54)= y ∈ Descripteurs, d(x, y) > 0.

Cette propriété de positivité, bien qu’elle vient du fait que c’est une mesure de distance,

reflète la propriété que deux objets différent ne peuvent jamais être complètement simi-

laires.

(cid:88) Inégalité triangulaire ∀x, y, z ∈ Descripteurs, d(x, z) <= d(x, y) + d(y, z)

Cette propriété n’est pas vérifiée dans la mise en correspondance partielle, si une partie

de x est similaire à une partie de y, alors d(x, y) ≈ 0

(cid:88) Invariance aux Transformations Pour un groupe de transformations G, ∀g ∈ G, ∀x, y ∈

Descripteurs, d(g(x), g(y)) = d(x, y)

Cette propriété assure que si l’objet subit une transformation, le calcul de descripteur et

de distance ne change pas.

1.2 Méthodes de description de forme 3D

Un descripteur est généralement vu comme la projection de la forme 3D sur un espace vec-

toriel de plus hautes dimensions. Le but essentiel des travaux de recherche dans l’élaboration

des descripteurs est de concevoir cette projection de telle façon qu’elle garde le plus possible

d’informations sur la forme en ce descripteur.

Dans la suite nous décrivons quelques approches globales et locales.

Rapport du projet de fin d’études-2015

Dorra Mimita

10

Chapitre 1 : Éléments d’état de l’art

1.2.1 Descripteurs globaux

Un descripteur global, caractérise la forme de l’objet 3D en sa totalité. Ce sont des descrip-

teurs basés sur les caractéristiques globales de la forme(les moments, les invariant, les transfor-

mées de Fourier..) et ils sont indépendants de la topologie de l’objet.

1.2.1.1 Histogramme de cordes

C’est un descripteur proposé par la CNRC(Canadian National Research Council) d’Ottawa

le premier centre qui a proposé une méthode d’indexation 3D. Il était publié en 1997 par Paquet

et Rioux [17].

Les auteurs définissent une corde comme étant le segment qui lie le centre de masse de

l’objet 3D au centre de gravité d’une facette. Pour chaque facette cette corde est calculée. Le

descripteur élaboré repose sur les statistiques des cordes et il est donné par trois histogrammes :

– Histogramme des longueurs des cordes

– Histogramme des angles entre les cordes et le premier axe principal de l’objet.

– Histogramme des angles entre les cordes et le deuxième axe principal

Selon les auteurs, la taille optimale d’un histogramme sera de 64(diviser l’histogramme en

64 intervalles, bins). Ce descripteurs est facile à implémenter,invariant à la translations et à la

rotation (puisque la référence est est représentée par les deux axes principaux). Cette techniques

n’est pas très utile pour discriminer les formes très complexes, cependant, on peut l’utiliser

comme filtre préliminaire en association avec d’autres descripteurs pour faciliter le travail.

Aussi, ce descripteur simplifie les triangles du maillage et les réduit en des points. Donc il ne

considère pas la différence de taille des facettes et tous les triangles du maillage sont pondérés

par le même poids. Aussi, en réduisant les triangles en des points, le descripteur ne considère

pas l’influence de l’orientation des triangles sur l’ensemble de la distribution de forme.

1.2.1.2 Descripteur de Hough 3D

Ce descripteur était introduit par Zaharia et Prêteux en 2002 [22], il se base sur le principe du Transformée de Hough. En effet chaque plan de R3 peut être entièrement défini par un seul

point dans le système de coordonnées sphériques (comme le montre la figure1.6).

Nous désignons par r la distance qui sépare le plan de l’origine du repère,et θ ∈ [0, 2Π[

et φ ∈ [−Π/2, Π/2[ les deux angles qui représentent le vecteur n (voir figure). Ce sont l’angle

Rapport du projet de fin d’études-2015

Dorra Mimita

11

Chapitre 1 : Éléments d’état de l’art

d’orientation et l’ongle d’élévation. n est le vecteur normal au plan dans le système de coor-

données sphériques.

FIGURE 1.6 – Paramétrisation : un plan est décrit par un point

Chaque axe dans le système des coordonnées sphériques est uniformément subdivisé. Un

histogramme 3D est alors formé, où chaque triangle du maillage est représenté par son centre

de gravité. La contribution de chaque facette dans l’histogramme est proportionnelle à son aire.

Ce descripteur a été performant sur la base de données MPEG-7.

1.2.1.3 Distribution de Forme 3D

Le groupe de recherche "Shape Retrieval and Analysis" de l’université de Princeton, USA,

a introduit le descripteur distribution de forme 3D en 2002. Osada et al., [16]. proposent de

représenter la forme d’un objet 3D comme distribution de probabilité échantillonnée à partir

d’une fonction de forme qui reflète des propriétés géométriques de l’objet étudié.

La distribution de forme représente, sous la forme d’un histogramme normalisé, les proba-

bilités d’occurrence de l’une des fonctions de formes proposés par les auteurs comme :

– L’angle entre trois points choisis au hasard de la surface de l’objet 3D

– La distance euclidienne entre un point fixe et un ensemble de points choisis au hasard du

maillage, ou la distance euclidienne entre deux points choisis au hasard de la surface.

– La racine carrée de la surface formée par trois ou plusieurs points choisis au hasard

– Ou encore la racine cubique du volume composé par quatre points de la surface.

Comme le montre la figure 1.7, on peut remarquer deux classes d’objets dans les distri-

butions. On remarque aussi que les 6 distributions qui représentent de différents voitures se

ressemblent et que les 5 distributions des chars de guerre sont très proches de points de vue

forme et distance.

L’algorithme permet de calculer l’histogramme nommé distribution de forme, puis estimer

Rapport du projet de fin d’études-2015

Dorra Mimita

12

Chapitre 1 : Éléments d’état de l’art

le taux de similarité entre deux objets en utilisant une des métriques de comparaison des dis-

tributions de probabilité (ex. distance de Minkowski). Selon les fonctions de formes choisies, le

descripteur est invariant aux transformations rigides, les petites distorsions, type de représen-

tation de l’objet.

FIGURE 1.7 – Distribution de forme de 6 voitures (noirs) et 5 chars (gris)

figure prise de l’article [16] c(cid:13)

C’est une méthode donc, probabiliste , dont les principaux avantages sont la facilité d’im-

plémentation, la rapidité de calculs(puisque les métriques utilisées sont simples : distance,

angle, volume), l’invariance aux transformations géométriques et la robustesse aux perturba-

tions du maillage (Puisque les points sont choisis arbitrairement donc le descripteur est inva-

riant au nombre de facettes), aussi la comparaison entre deux objets est devenu plus simple et

réduite à une comparaison de deux distributions de probabilité. Les signatures caractérisent la

forme globale des objets mais non les détails. La méthode semble donc être plus adaptée aux

recherches d’objets similaires dans des bases de données d’objets de formes très différentes.

1.2.1.4 Spectre de Forme 3D

Le spectre de formes 3D introduit par Zaharia et Preteux [23], caractérise indirectement les

propriétés de courbures d’un maillage 3D. Il était présenté avec la base MPEG-7. Le descripteur

spectre de forme est la distribution de tous les index de forme des points du maillage.

L’index de forme est une quantité mathématique calculée à partir des courbures principales

et qui quantifie le caractère plus ou moins courbé dans le point étudié comme le montre la

figure 1.8. Soit p un point du maillage, et soient k1

p et k2

p les courbures principales associées

Rapport du projet de fin d’études-2015

Dorra Mimita

13

Chapitre 1 : Éléments d’état de l’art

au point p, l’index de forme est donné par l’équation 1.1

Ip =

1 2

−

1 Π

arctan(

k1 k1

p + k2 p + k2

p

p

)

(1.1)

Le descripteur de forme élaboré est donc l’histogramme des index de formes de tous les

points du maillage. C’est un descripteur invariant au changement d’échelle et aux transfor-

mations rigides. Néanmoins c’est un descripteur très sensible à la connectivité et la qualité du

maillage.

Dans certains travaux de recherche, ce descripteur est considéré comme descripteur local car

il est très sensible aux détails et donc pertinent comme signature locale (voir section suivante,

Spectre de Forme Géodesiques [6]

FIGURE 1.8 – Index de formes pour quelques formes connues

1.2.2 Descripteurs locaux

Les descripteurs locaux tiennent en compte les caractéristiques locales de la forme 3D. Ils

se basent sur des propriétés de la surface au voisinage d’un point. Dans cette section nous

énumérons quelques approches existantes en expliquant leurs principes.

1.2.2.1 Boules de Savon (blowing bubble)

Ce descripteur a été presenté en [15], son principe est d’exploiter les informations obtenues

à partir de l’intersection de la surface avec des sphères concentriques.

En premier lieu, les auteurs exploitent le nombre des composantes connexes obtenues à

partir de l’intersection pour caractériser la surface 3D. Comme le montre la figure, pour un

point de référence p, plusieurs cas peuvent être considérés :

Rapport du projet de fin d’études-2015

Dorra Mimita

14

Chapitre 1 : Éléments d’état de l’art

– 1 seule composante : la surface autour de p est considéré comme planaire.

– 2 composantes : la surface autour de p est considéré similaire à un tube, cylindrique.

– 3 composantes ou plus, au voisinage de p, il y a une ramification et la surface est similaire

à une branche.

Ensuite, pour mieux caractériser la forme, le nombre de composantes ne suffit pas. Dans le

cas où on a une cone aiguë, et dans le cas ou on a une simple convexité qui n’est pas trop ai-

guë, une seule composante va être obtenue au niveau du sommet. Donc pour mieux distinguer

les formes les auteurs proposent d’autres primitives comme la longueur du cercle obtenu(plus

la forme est aiguë, plus le cercle a un diamètre minime), ou en utilisant les caractères topolo-

giques(convexe,concave).

Ce descripteur est invariant aux transformations euclidiennes, au changement d’échelle, résis-

tant au bruit. Il peut être aussi utilisé pour segmenter les formes.

1.2.2.2 Spin Image

Le descripteur Spin Image introduit par Johnson et al.(1999) [10] a une efficacité reconnue

dans le domaine de reconnaissance de formes pour les scènes complexes. L’idée de ce descrip-

teur est de générer des histogrammes 2D autour des points choisis.

L’algorithme est décrit comme suit : pour chaque point Oi choisi pour en calculer le des-

cripteur, on va élaborer le spin-image qui est un histogramme accumulé sur un support 2D. n

est le vecteur désignant l’orientation du maillage dans le point Oi.

Chaque sommet dans le voisinage de Oi est identifié par deux coordonnées α et β où α

est la distance du projeté orthogonal d’un sommet q(voir figure 1.9) sur la droite de vecteur

directeur n, et β est définie comme la distance du sommet q vers le plan contenant le point Oi

et dont n est un vecteur qui lui est orthogonal.

Rapport du projet de fin d’études-2015

Dorra Mimita

15

Chapitre 1 : Éléments d’état de l’art

FIGURE 1.9 – Élaboration de l’image spin

Comme le montre la figure 1.9, l’image est formée sur le plan du spin, (à droite) dont les di-

mensions sont choisies dès le début. Chaque bin de l’histogramme est augmentée par le nombre

de points qui lui appartiennent.

FIGURE 1.10 – Quelques résultats pour le descripteur Spin-images

La figure 1.10 montre quelques images ’spin’ élaborés par les auteurs [10].

Rapport du projet de fin d’études-2015

Dorra Mimita

16

Chapitre 1 : Éléments d’état de l’art

1.2.2.3 Spectre de Forme Géodesique

Le spectre de formes géodésiques, a été proposé en 2014 par Chaieb et al.[6]. C’est un des-

cripteur local qui utilise le spectre de forme proposé dans [23] dans un voisinage local.

L’idée du descripteur est d’élaborer un voisinage géodésique autour d’un point donné. Ce voi-

sinage est composé des lignes de niveau, géodésiques intersectés par des lignes radiales. Ce

partitionnement résulte en N ’patch’, en chacun des patchs, un spectre de forme est élaboré à

l’aide des index de forme (décrit dans l’équation 1.1 ).

C’est un descripteur, ou les auteurs ont pu joindre les descripteurs globaux et locaux, in-

variant aux transformations rigides. Le changement de paramètres peut changer les résultats

obtenus(nombre de bins de l’histogramme).

1.2.2.4 Distribution de forme locale

Ce descripteur proposé par X.Bai et al.[13] consiste à considérer le voisinage sphérique d’un

point. Pour un point P de la surface, son voisinage est défini par la sphère de centre P et de

rayon r. Le descripteur de distribution de forme local est un vecteur-histogramme de la distance

Euclidienne entre p et les autres points de la surface.

Plus le point est éloigné de P, plus son contribution dans l’histogramme est minime, d’o