Appréciation de l’encadrant

Invariance la rotation . . . . . . . . . . . . . . . . . . . . . . . .

3.3.1.3

Inuence du changement d chelle . . . . . . . . . . . . . . . . .

3.3.1.4

Robustesse du descripteur par rapport au bruit

. . . . . . . . .

3.3.2 Application la mise en correspondance point point

. . . . . . . . . . .

3.3.3 Base de test et crit res d valuation . . . . . . . . . . . . . . . . . . . . . .

3.3.3.1

Environnement mat riel et logiciel

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

3.3.3.2

Base de test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.3.3.3

Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Bibliographie

Netographie

Rapport du projet de n d tudes-2015

Dorra Mimita

21

22

23

23

25

26

28

29

31

31

31

33

33

34

34

34

35

35

36

37

38

38

40

41

41

42

47

48

vi

Table des gures

1

Plan du travail .

.

.

.

.

.

.

.

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

1.1 Diff rence entre laspect 2D et laspect 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 limage 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 lespace 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 lext 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 n d tudes-2015

Dorra Mimita

vii

TABLE DES FIGURES

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

3.3 Processus dindexation .

.

.

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

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

Inuence 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 n d tudes-2015

Dorra Mimita

viii

Introduction

Motivations

bas e sur laspect 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 lensemble 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 na cess

dattirer lattention des chercheurs, des informaticiens ainsi que les industries dintelligence ar-

ticielle. De r centes applications comme les jeux vid os, le cin ma, larch 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 quils 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 efcacement ces donn es tridimensionnelles : de point de

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

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

l tape de chercher lobjet dans une base de donn es.

Rapport du projet de n d tudes-2015

Dorra Mimita

1

Introduction

Chercher un objet dans une grande base dobjets 3D, est un d qui se basera sur certains

crit res de similarit , lobjet requ te et lobjet obtenu suite la recherche doivent tre visuelle-

ment similaires.

Contexte du projet

Dans ce projet, nous cherchons faire lindexation dune base de donn es 3D. Pour cela

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

menter.

Nous nissons par indexer une base de donn es dobjet 3D, tester les performances du descrip-

teur propos , puis lint grer dans un moteur de reconnaissance de formes.

Ce travail est r alis en tant que projet de n d tudes lEcole Nationale des Sciences de lIn-

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

Planning pr -visuel du projet

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

gure 1 d crit la chronologie quon va suivre

FIGURE 1 Plan du travail

Rapport du projet de n d tudes-2015

Dorra Mimita

2

Introduction

Organisation du rapport

Nous planions le rapport comme suit

Une introduction g n rale

Le premier chapitre est nomm " l ments d tat de lart", il sera consacr une tude

approfondie des notions utiliser ainsi quune 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 dimpl mentation

Dans le dernier chapitre on applique le descripteur sur lindexation dun objet 3D, nous

valuons le descripteur impl ment en lint grant dans un syst me de reconnaissance de

formes.

Nous nissons par une conclusion g n rale ainsi que des perspectives.

Rapport du projet de n d tudes-2015

Dorra Mimita

3

Chapitre 1

l ments d tat de lart

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. Cest pour cela que nous intro-

duisons ce chapitre pour clarier 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 cest dans cette section que nous mettons

en place quelques d nitions et notions.

1.1.1 Pr sentations des donn es 3D

En observant un objet 3D, la question qui se pose cest 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

Limage 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 laxe de profon-

Rapport du projet de n d tudes-2015

Dorra Mimita

4

Chapitre 1 : l ments d tat de lart

deur celui qui donne leffet r aliste sur cran, cest celui qui donne laspect proche de ce quon

voit dans le monde r el comme le montre la gure 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 laspect 2D et laspect 3D

1.1.1.2 Types de donn es 3D

Selon les modalit s dacquisition : 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 : Lobjet 3D est repr sent par un ensemble de donn es ind pen-

dantes : ensemble de contours, nuage de points, ou encore ensemble dimages 2D. Comme

le montre la gure 1.2.

Le nuage de points, est en r alit des chantillons de lobjet 3D, non structur s obtenus

partir du "rangender" ,"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

ladjacence.

Lensemble 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 lima-

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

triangulation dans la phase d tablissement de lappariement entre les contours.

Quant lensemble des images, ce sont des images st r oscopiques, obtenus en tournant

un objet 3D sur un axe xe avec une vitesse constante. Lacquisition est faite avec un cam ra

Rapport du projet de n d tudes-2015

Dorra Mimita

5

Chapitre 1 : l ments d tat de lart

xe, ou bien en utilisant dautres instruments. Les images 2D contiennent des informations

dintensit alors que cet ensemble dimages contient des informations de profondeur.

(a) Nuage de Points

(b) Ensemble de contours

(c) Ensemble dimages 2D

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

Les Solides 3D : Cest 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 lobjet.

Parmi ces repr sentations, nous citons :

Wireframe model : appel Fil de Fer 3D, cest 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 signicatives de lobjet. 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 dambigu t vu quelle noffre pas des

d tails de remplissage comme le montre la gure 1.3.

Voxels : Cette technique, permet de subdiviser lespace 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, dopacit etc..

Cette technique est g n ralement utilis e pour limagerie m dicale en utilisant les IRM :

Imagerie R sonance Magn tique,un exemple est illustr par la gure 1.3.

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

base sur la repr sentation de lobjet comme ensemble de quelques objets tridimension-

nelles plus simples, larbre de construction est appel e CSG-arbre ( 1.3b de la gure 1.3)

Rapport du projet de n d tudes-2015

Dorra Mimita

6

Chapitre 1 : l ments d tat de lart

(a) Acquisiton de limage du

cerveau IRM,

repr sentation

(b) Larbre CSG dun mod le

(c) Lambiguit 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 : Cest une repr sentation qui d crit comme le nom lindique la surface ext -

rieure de lobjet. Ces surfaces sont repr sent s par :

Les surfaces param triques : une repr sentation dans lespace R3 d nie 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 lensemble des points

solution une quation implicite F (x, y, z) = 0 par exemple l quation dun ellipse :

( x

rx

)2 + ( y

ry

)2 + ( z

rz

)2 1 = 0

Les maillages : les Mesh en anglais de la gure 1.4, cest 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 lensemble des sommets (vertex), et

lautre qui contient, pour chaque facette les sommets qui la composent.

Cest avec cette repr sentation que nous travaillons car cest 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 n d tudes-2015

Dorra Mimita

7

Chapitre 1 : l ments d tat de lart

1.1.2 Calculs g od siques

" Courbe G od sique : Les g od siques sont les trajectoires dun 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

dapesanteur (avec pesanteur, ces lignes deviennent les lignes d coulement).

" Distance G od sique : Cest 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 dun objet g om trique est une mesure quantitative du caract re plus ou

moins courb de cet objet. Cest aussi linverse du rayon du cercle osculateur(cercle qui

peut tre confondue avec lobjet 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 gure 1.5.

partir de cette d nition on cosid re min et max On peut ainsi d nir 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 n d tudes-2015

Dorra Mimita

8

Chapitre 1 : l ments d tat de lart

1.1.3 Les Descripteurs

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

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

Cet identiant unique d crit lobjet soit globalement soit partiellement de telle fa on quil soit

signicatif, cest ce quon 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 dun mod le 3D, il traduit la g om trie

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

partie dun mod le, se focaliser sur les d tails locales et les param tres dune r gion de lobjet

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

pr -rep r .

Certains crit res sont souhaitables pour un descripteur savoir : linvariance maximale par

rapport au bruit, certaines perturbations, linvariance aux transformations, la compl tude

qui garantit quun objet soit identif dune 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 xer une m trique de mesure.

Le taux de similarit , doit tre quanti par une mesure math matique, une fonction appel e

distance entre les deux objets.

Certains lappellent mesure de "dissimilarit " pour quelle soit en coh rence avec le mot

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

dailleurs cest ce que re 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 nie 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 ri s savoir :

Rapport du projet de n d tudes-2015

Dorra Mimita

9

Chapitre 1 : l ments d tat de lart

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

La propri t de lidentit renseigne sur le fait quune forme est compl tement similaire

elle m me. Cest une propri t quon 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 nest pas assez n cessaire, car d j il nest pas souvent vident pour l tre

humain quun objet x ressemble un objet y veut dire que y est similaire x. Naturelle-

ment, et inconsciemment puisque la perception humaine afrme quun ellipse est plut t

ressemblant un cercle et que linverse nest pas souvent afrm , cest que cette attitude

nest pas fausse si elle est v ri 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 quelle vient du fait que cest une mesure de distance,

re 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 nest pas v ri e dans la mise en correspondance partielle, si une partie

de x est similaire une partie de y, alors d(x, y) H 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 lobjet 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 quelle garde le plus possible

dinformations sur la forme en ce descripteur.

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

Rapport du projet de n d tudes-2015

Dorra Mimita

10

Chapitre 1 : l ments d tat de lart

1.2.1 Descripteurs globaux

Un descripteur global, caract rise la forme de lobjet 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 lobjet.

1.2.1.1 Histogramme de cordes

Cest un descripteur propos par la CNRC(Canadian National Research Council) dOttawa

le premier centre qui a propos une m thode dindexation 3D. Il tait publi en 1997 par Paquet

et Rioux [17].

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

lobjet 3D au centre de gravit dune 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 lobjet.

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

Selon les auteurs, la taille optimale dun histogramme sera de 64(diviser lhistogramme 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

nest pas tr s utile pour discriminer les formes tr s complexes, cependant, on peut lutiliser

comme ltre pr liminaire en association avec dautres descripteurs pour faciliter le travail.

Aussi, ce descripteur simplie 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 linuence de lorientation des triangles sur lensemble 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 ni par un seul

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

Nous d signons par r la distance qui s pare le plan de lorigine du rep re,et [0, 2 [

et [ /2, /2[ les deux angles qui repr sentent le vecteur n (voir gure). Ce sont langle

Rapport du projet de n d tudes-2015

Dorra Mimita

11

Chapitre 1 : l ments d tat de lart

dorientation et longle 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 lhistogramme 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 luniversit de Princeton, USA,

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

repr senter la forme dun objet 3D comme distribution de probabilit chantillonn e partir

dune fonction de forme qui re te des propri t s g om triques de lobjet tudi .

La distribution de forme repr sente, sous la forme dun histogramme normalis , les proba-

bilit s doccurrence de lune des fonctions de formes propos s par les auteurs comme :

Langle entre trois points choisis au hasard de la surface de lobjet 3D

La distance euclidienne entre un point xe 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 gure 1.7, on peut remarquer deux classes dobjets 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.

Lalgorithme permet de calculer lhistogramme nomm distribution de forme, puis estimer

Rapport du projet de n d tudes-2015

Dorra Mimita

12

Chapitre 1 : l ments d tat de lart

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 lobjet.

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

gure prise de larticle [16] c(cid:13)

Cest une m thode donc, probabiliste , dont les principaux avantages sont la facilit dim-

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

angle, volume), linvariance 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 dobjets similaires dans des bases de donn es dobjets 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 dun 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.

Lindex de forme est une quantit math matique calcul e partir des courbures principales

et qui quantie le caract re plus ou moins courb dans le point tudi comme le montre la

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

p et k2

p les courbures principales associ es

Rapport du projet de n d tudes-2015

Dorra Mimita

13

Chapitre 1 : l ments d tat de lart

au point p, lindex 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 lhistogramme des index de formes de tous les

points du maillage. Cest un descripteur invariant au changement d chelle et aux transfor-

mations rigides. N anmoins cest 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 dun 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 dexploiter les informations obtenues

partir de lintersection de la surface avec des sph res concentriques.

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

partir de lintersection pour caract riser la surface 3D. Comme le montre la gure, pour un

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

Rapport du projet de n d tudes-2015

Dorra Mimita

14

Chapitre 1 : l ments d tat de lart

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 ramication et la surface est similaire

une branche.

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

cas o on a une cone aigu , et dans le cas ou on a une simple convexit qui nest pas trop ai-

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

les formes les auteurs proposent dautres 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 efcacit reconnue

dans le domaine de reconnaissance de formes pour les sc nes complexes. Lid e de ce descrip-

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

Lalgorithme 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 lorientation du maillage dans le point Oi.

Chaque sommet dans le voisinage de Oi est identi par deux coordonn es et o

est la distance du projet orthogonal dun sommet q(voir gure 1.9) sur la droite de vecteur

directeur n, et est d nie 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 n d tudes-2015

Dorra Mimita

15

Chapitre 1 : l ments d tat de lart

FIGURE 1.9 laboration de limage spin

Comme le montre la gure 1.9, limage est form e sur le plan du spin, ( droite) dont les di-

mensions sont choisies d s le d but. Chaque bin de lhistogramme est augment e par le nombre

de points qui lui appartiennent.

FIGURE 1.10 Quelques r sultats pour le descripteur Spin-images

La gure 1.10 montre quelques images spin labor s par les auteurs [10].

Rapport du projet de n d tudes-2015

Dorra Mimita

16

Chapitre 1 : l ments d tat de lart

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]. Cest un des-

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

Lid e du descripteur est d laborer un voisinage g od sique autour dun 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

laide des index de forme (d crit dans l quation 1.1 ).

Cest 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 lhistogramme).

1.2.2.4 Distribution de forme locale

<...