Indexation et recherche dynamique d’objets 3D par des

d’indexation et de recherche d’images par le contenu à partir de ces connaissances A MICA, nous construisons un système d’indexation et de recherche d’images par le contenu symbolique en héritant les techniques déjà existantes et en rajoutant nos idées Nous orientons notre recherche vers la recherche

Indexation de documents

Introduction aux techniques d'indexation et de recherche 6-----1 Techniques d'indexation Indexation plein-texte : des mots clés sont extraits automatiquement du contenu Méta-données documentaires : des propriétés documentaires sont renseignées manuellement

Indexation et recherche d’images par arbres des coupes

destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés Indexation et recherche d’images par arbres des coupes Petra Bosilj To cite this version: Petra Bosilj

Indexation visuelle et recherche d’images sur le Web : Enjeux

recherche d’information visant à plus d’efficacité et de simplicité dans le classement, l’indexation et l’accès aux données Ces projets aboutissent à la création de logiciels de

Annotation, indexation et recherche d’images

Indexation et recherche dynamique d’objets 3D par des

phase d’indexation et une phase de recherche Dans la phase d’indexation, pour tout mod`ele tridimensionnel de labase,oncalculelesvuescaract´eristiquesetleursindexes associes Lors de la phase de recherche, l’image requ´ eteˆ subit un traitement similaire aux vues de la base, `a l’issue

Indexation automatique et la Recherche D’information dans les

Comment extraire la sémantique d’une image

d’indexation et de recherche d’information Deux niveaux d’interprétation d’une image sont définis : symbolique, ou bas niveau, et sémantique, ou haut niveau L’objectif de la

[PDF] cours indexation image

[PDF] indexation d'images par le contenu

[PDF] recherche d'image par contenu visuel

[PDF] comment indexer une image

[PDF] indexation images

[PDF] indexation et recherche d'images

[PDF] descripteurs d'images

[PDF] la bastille paris

[PDF] la bastille 1789

[PDF] qu'est ce que la bastille

[PDF] multiplication a trou cm2

[PDF] bastille place

[PDF] la bastille aujourd'hui

[PDF] soustraction a trou cm2

[PDF] bastille arrondissement

Indexation et recherche dynamique d"objets 3D par des requ

ˆetes 2D

J. Ricard D. Coeurjolly A. Baskurt

LIRIS (Laboratoire d"InfoRmatique en Image et Syst `emes d"information)

UMR 5205 CNRS/Universit

´e Claude Bernard Lyon 1

43, Boulevard du 11 novembre 1918, 69622 Villeurbanne Cedex - France

{jricard, dcoeurjo, abaskurt}@liris.cnrs.fr R

´esum´e

Cet article pr

´esente un nouveau syst`eme d"indexation dy-

namique d"objet 3D par vues permettant de rechercher un objet `a partir d"une requˆete image. Les m´ethodes de re- cherches d"objets 3D par vues se heurtent aux probl `emes du choix des vues qui ne permettent pas d"avoir des m ´ethodes adaptatives`a l"objet et`a la requˆete. Pour per- mettre cette double adaptabilit

´e, il faut mettre en place un

processus dynamique.

Dans cet article, nous proposons un nouveau syst

`eme de comparaisons dynamiques d"objets 3D bas

´e sur une

repr ´esentation spectrale de l"objet. Cette repr´esentation permet d"extraire rapidement les vues et de mettre en place une recherche dynamique dans l"espace des vues pour rendrepluspr en ´etant adaptatif,`a la fois`a l"objet et`a la requˆete.

Mots clefs

Indexation 2D/3D, indexation 3D par vues.

1 Introduction

Le nombre toujours croissant d"objets 3D disponible rend obligatoire la mise en place de m

´ethodes permettant de

les classer. Plusieurs grandes voies se distinguent dans la litt ´erature [1, 2, 3]. On peut noter : les approches structu- relles, les approches statistiques, les approches par trans- form ´ees, et les approches par vues ou"Visual indexing».

Ces derni

`eres caract´erisent un objet 3D par un ensemble de vues 2D et classent les objets 3D en comparant leurs en- sembles de vues. Pour chaque objet 3D, un certain nombre de vues est cr ´e´e et index´e par un descripteur de forme

2D. Ces approches permettent de mettre en place des re-

cherches, soit `a partir d"une vue 2D, on parle alors d"in- dexation 2D /3D, soit `a partir d"un objet 3D, indexation

3D/3D. La figure 1 montre un objet 3D d

´ecrit par un en-

semble de vues 2D et les possibilit

´es de comparer soit di-

rectement avec une image requ

ˆete soit avec un autre objet

3D en comparant leurs ensembles de vues.

Lesm de vues, varient en fonction du nombre et de la position des vues et de la m

´ethode de description pour les d´ecrire. CesFigure 1 -Exemple de mise en correspondance 2D/3D et

3D/3D entre un ensemble de vues et une image requ

ˆete et

un autre ensemble de vues. m a d´ecrire en fonction du nombre de vues choisies, mais ne sont pas adaptatives `a la complexit´e de la requˆete. Pour per- mettre une double adaptation `a l"objet et`a la requˆete, il faut mettre en place un processus dynamique qui en fonction de la requ ˆete va parcourir l"espace des vues de l"objet et re- cherche la vue la plus similaire. Un tel processus requi `ere la mise en place : d"un syst `eme de repr´esentation, conte- nant les vues de l"objet et permettant de les extraire rapi- dement, une m

´etrique entre les vues pour les comparer, et

pour rechercher la vue la plus similaire. Cette comparaison dynamique entre l"objet 3D et la vue requ

ˆete permettra de

fournir des r ´esultats plus pr´ecis, car l"espace des vues de l"objet sera convenablement repr

´esent´e. D"autre part, cette

repr ´esentation fournira des informations suppl´ementaires en indiquant la position pr

´ecise de la vue extraite sur la

sph `ere des vues.

Cette article sera organis

´e comme suit : dans un premier

temps, un ´etat de l"art reviendra sur les m´ethodes d"in- dexation d"objets 3D par vues et leurs limites, puis nous expliquerons la m

´ethode que nous proposons, enfin, les

exp ´eriences que nous avons mises en place en indexation d"objets 3D par requ

ˆetes 2D seront expliqu´ees.

´Etat de l"art en indexation 2D/3D

Les m ´ethodes utilisant des vues des mod`eles 3D sont mo- tiv ´ees par les r´esultats psychophysiques [4] qui montrent quedans lesyst `emevisuel humain,un objeten troisdimen- sions est repr ´esent´e par un ensemble de vues 2D plutˆot que par un mod `ele tridimensionnel. De plus, de telles m´ethodes peuvent ˆetre utilis´ees soit pour classer des objets 3D entre eux soit pour retrouver un objet au d

´epart d"une de ces vues

2D. Les applications vis

´ees par ce type de m´ethodes sont la

recherchedemod `eles3D`apartird"unephotoouducroquis d"une pi `ece. L"objectif est de rechercher le ou les mod`eles tridimensionnels les plus proches `a partir d"une image 2D.

Le processus peut se d

´ecomposer en deux phases : une

phase d"indexation et une phase de recherche. Dans la phase d"indexation, pour tout mod `ele tridimensionnel de la base, on calcule les vues caract

´eristiques et leurs indexes

associ ´es. Lors de la phase de recherche, l"image requˆete subit un traitement similaire aux vues de la base, `a l"issue duquel un descripteur (invariant `a certaines d´eformations) est calcul ´e et compar´e avec les descripteurs de la base. L"id ´ee g´en´erale de ce type de m´ethodes est de discr´etiser l"espace des vues en un ensemble deNpoints de vues r ´epartis autour du mod`ele et de prendreNimages du profil de la pi `ece 3D. Chaque image est index´ee par une m´ethode d"analyse de formes 2D : CSS[5, 6], ART[7], Zernike[8] etc. Lors de la recherche, la m

´ethode indexe la vue 2D

requ ˆete, la compare avec lesNvues de l"objet et retourne la vue la plus proche pour dire si la vue vient de ce mod `ele

3D. Les deux points longuement discut

´es dans la litt´erature

sont le choix de la m

´ethode d"indexation des vues 2D et

le choix du nombres de vues `a prendre en compte et les- quels. Le choix du descripteurs de formes des vues 2D ne va pas modifier le principe g

´en´eral mais va modifier les

performances et l"efficacit

´e, en fonction des propri´et´es de

la m

´ethode choisie.

2.1 Choix du nombre de vues

Un point qui va modifier l"efficacit

´e et la rapidit´e de ces

m ´ethodes est le nombre et la position de vues`a prendre en compte. Ce nombre est directement li

´e aux perfor-

mances du syst `eme. Il faut le diminuer au maximum pour avoir une m ´ethode rapide, tout en conservant la capacit´e descriptive des vues. Deux approches ont

´et´e exploit´ees

pour diminuer le nombre de vues, soit en ne prenant au d ´epart un nombre restreint de vues [9, 10, 11], calcul´ees g ´en´eralement par rapport au axes principaux du mod`ele

3D, soit en prenant un grand nombre de vues et en les

regroupant pour ne garder que les plus caract

´eristiques

[12, 13]. La figure 2 montre plusieurs r

´epartitions de vues

sur la sph `ere des vues : 4 vues plac´ees sur les axes princi- paux, 7 vues plac

´ees sur les axes principaux et sur les dia-

gonales [11] et une m

´ethode de s´election de vues variables

bas ´ees sur 94 vues. Les m´ethodes de s´election de vues va- riablesdiscr m ´ethode de Sphere Picking et regroupent les points de vues en fonction de la similarit ´e entre les vues cr´e´ees, pour negarder qu"un faible nombre de vues caract ´eristiques.Figure 2 -Exemple de r´epartition de vues sur la sph`ere des vues d"une objet : 4 vues, 7 vues ou 94 vues par une m

´ethode de Sphere Picking.

Un autre param

`etre modifiant les vues extraites est le co- efficient perspectif. Pour reconna

ˆıtre des formes naturelles,

il faut ´echantillonner l"espace des vues en fonction de la position de la cam

´era et de la perspective pour prendre

en compte ces d ´eformations. G´en´eralement, les m´ethodes d"indexation 2D/3D fixe l"indice de perspective `a une va- leur moyenne, ce qui permet de n

´egliger ce param`etre, ou

utilisent un coefficient de perspective infini, ce qui revient a faire une projection orthographique et permet de r´eduire l"espace des vues en ne consid

´erant que la demi-sph`ere des

vues.

2.2 Probl

´ematiques

Les m ´ethodes d"indexation d"objets 3D par vues sont adap- tatifs `a l"objet`a d´ecrire mais ne le sont pas`a la requˆete.

Quelque soit la requ

ˆete, la comparaison entre l"ensemble

des vues de l"objet et la vue requ

ˆete, se fait de fac¸on

pr ´ed´efinit et ne d´epend pas de l"image requˆete. La re- cherche va comparer la vue requ

ˆete`a toutes les vues conte-

nues dans le descripteur, quelque soit la vue requ

ˆete. Si

cette vue est tr `es proche de la premi`ere vue descripteur, la recherche va quand m

ˆeme la comparer`a toutes les vues.

Danslecascontraire,silavuerequ

ˆeteestloindesvuesdes-

cripteurs, ou n"est pas d

´ecrit par l"une d"elle, les r´esultats

ne seront pas exactes malgr

´e une recherche exhaustive sur

les vues descripteurs. Le seul moyen pour avoir une pro- cessus permettant `a la fois de s"adapter`a la complexit´e de l"espace des vues de l"objet `a d´ecrire et`a celui de l"image requ ˆete, est de mettre en place un processus dynamique pour extraire la meilleure vue dans l"espace des vues en fonction de l"image requ

ˆete. Pour mettre en place un pro-

cessus dynamique de comparaison de vues, il faut : -un syst`eme de repr´esentation et de calcul des vues, qui permet d"extraire rapidement des vues de l"objet 3D. -une mesure de similarit´epermettant de comparer les vues extraites `a la vue requˆete. -un processus d"optimisationqui en fonction de la dis- tance entre les vues extraites recherche la vue optimale.

Un tel processus sera doublement adaptatif

`a la requˆete et`a l"objet 3D et permettra de retrouver la vue de l"espace des vues de l"objet la plus proche de l"image requ

ˆete. La figure

3 montre ce processus compos

´e de ces trois points. L"ap-

proche que nous proposons repr

´esentera l"int´egralit´e des

vues de l"objet par une transform

´ee de Fourier 3D (voir

section 3). La pr

´ecision d"un tel syst`eme sera nettement

sup ´erieure`a une m´ethode de s´election de vues, se qui per- mettra de fournir la position de la vue requ

ˆete sur la sph`ere

de vues pour faire de la mise en correspondance entre l"ob- jet 3D et l"image requ ˆete.Figure 3 -Principe d"un processus de recherche dyna- mique compos

´e d"un syst`eme de repr´esentation permet-

tant l"extraction rapide de vues, d"une mesure de similarit ´e entre vues et d"un processus d"optimisation.

3 Recherche dynamique d"objets 3D

Comme nous venons de le voir, le processus dynamique de recherche d"objets 3D va

ˆetre bas´e sur trois´el´ements

qui vont ˆetre explicit´es dans cette partie : un syst`eme de repr ´esentation, un mesure de similarit´e et un processus d"optimisation.

3.1 Syst

`eme de repr´esentation et cr´eation des vues Les m ´ethodes d"indexation d"objets 3D par vues se basent sur une repr ´esentation triangulaire de l"objet et obtiennent les vues par un processus de rendu de type de Z-buffer.

Pour garantir une cr

´eation de vues rapides, nous avons opt´e

pour la mise en place un processus de rendu spectral bas ´e sur le Fourier discret d"un objet 3D et sur le th

´eor`eme de

Radon, identique aux m

´ethodes de Fourier Volume Ren-

dering [14]. Le th

´eor`eme de Radon stipule, en deux di-

mensions, que la valeur de la transform

´ee bidimensionnelle

d"un signal le long d"un axe de pente1/mpassant par le centre d"un spectre 2D est

´egale`a la transform´ee de Fourier

de la projection orthographique de l"objet parall `element`a un axe de pente-m. La fonctiong, projection orthogra- phique de la fonctionf, et sa transform´ee de FourierG peuvent s"

´ecrire :

g(t) =m? f[x,m(t-x)]dx(1)

G(w) =m?

f[x,m(t-x)]e-jwtdxdt(2)

En faisant un changement de variabley=m(t-x), on

peut

´ecrire :

G(w) =m?

f[x,y]e-jw(x+ym )dxdt(3)

En posantu=wetv=w/m, on reconnaˆıt dans

G(w)la valeur de la transform´ee de Fourier bidimension-

nelleF(u,v)def(x,y)le long d"une droite passant parFigure 4 -Principe du th´eor`eme de Radon en deux di-

mensions. La coupe le long d"un axe passant par le centre d"une transform

´ee de Fourier d"une forme discret

repr ´esente la transform´ee de Fourier de la projection de la forme. l"origine et de pente1/m. La figure 4 montre un exemple sur une forme 2D. Le th ´eor`eme de Radon est transposable en dimension trois, o `u la coupe 2D passant par le centre du spectre 3D d"un ob- jet discret repr ´esente la transform´ee de la projection ortho- graphique volumique de l"objet. Dans une premi `ere´etape de pr ´e-traitement, l"objet 3D est discr´etis´e sur un grille deN3voxels. La transformation de Fourier 3D (FFT 3D) de l"objet est gard

´ee comme espace de repr´esentation des

vues. En effet, une telle repr

´esentation contient l"ensemble

de vues de l"objet 3D. Pour cr

´eer une vue, il suffit d"ex-

traire une coupe passant par le centre de la FFT 3D. Ceci permet d"extraire une vue plus rapidement que par une pro- jection des triangles, car la complexit

´e passe deO(n2T)`a

O(n2logn), mais il faut pour cela manipuler la FFT 3D de l"objet de tailleN3. La figure 5 montre le principe de rendu par l"extraction de coupes d"une FFT 3D.Objet 3D discretObjet 3D

Transformée

Fourier3D

Images 2DImages profondeurs 2D

Prétraitement

Extraction

de vues )log(2nnO )(3NO )log(2 3NNO )(2TnOFigure 5 -Principe compar´e de rendu par l"extraction de coupe spectrale et par un processus bas

´e sur le Z-buffer.

Cette repr

´esentation permet de cr´eer les vues de l"objet de fac¸on rapide et pr ´ecise, mais´etant bas´ee sur la transform´ee de Fourier, elle poss `ede les mˆemes propri´et´es que cette derni `ere. En particulier, on peut n"extraire que les basses fr ´equences du Fourier 3D, ce qui fournira une vue base r ´esolution de l"objet. Ceci permettra de r´eduire fortement la complexit ´e du processus d"extraction de vues. La figure

6 montre un exemple de coupes extraites

`a quatre plages de fr

´equences et les vues reconstruites correspondantes.Figure6-Exempledecoupesextraitesdelarepr´esentation

de Fourier 3D et les images reconstruites `a 4 r´esolutions diff

´erentes : 128, 64, 32 et 16.

3.2 Comparaison des vues

La comparaison entre la vue requ

ˆete et les vues extraites

se fait par le calcul du descripteur de forme : Angular Ra- dial Transform (ART) [7, 2]. Cette transformation est en particulier invariante en rotation, ce qui permet de ne pas prendre en compte l"orientation de la prise de vue et de ne s"int ´eresser qu"`a sa position. Ce descripteur fournit une distance entre les deux images et permet de savoir si la vue extraite et proche de la vue requ

ˆete. L"axe de prise de vues

est d ´efini sur la demi-sph`ere des vues par un angle d"Euler (θ,φ). Notons que les vues cr´e´ees sont des projections or- thographiques de l"objet 3D, ce qui revient `a ne pas d´efinir de coefficient de perspective lors de la prise de vue, et `a limiter la recherche `a une demi-sph`ere des vues, l"autre etant identique. On peut calculer cette distance pour tous les points de l"espace des vues en discr

´etisant ce dernier.

Pour chaque point, on cr

´ee une vue extraite et on la com-

pare avec la vue requ

ˆete. Ceci fournit une carte des dis-

tances repr ´esentant les distances entre les vues de l"objet et la vue requ

ˆete. La figure 7 montre une carte de distance

entre une vue requ

ˆete et un objet 3D, ou pour chaque point

de l"espace des vues,(θ,φ)?[0,2π]?[0,π/2], une dis- tance est calcul ´ee entre la vue extraite et la vue requˆete.

3.3 Processus d"optimisation

Le calcul de la carte des distances requi

`ere la cr´eation pro- paraison rapide, un processus d"optimisation a

´et´e mis en

place pour trouver le minimum de la carte des distances en un nombre restreint d"extractions. Un processus d"optimi- sation d

´epend de deux param`etres :

-un espace de rechercheiciθetφ, -une fonction d"´evaluation, qui vaˆetre la mesure de si- milarit

[PDF] Indexation et recherche dynamique d’objets 3D par des