THESE...deux images de pertinence : la première pour les données géométriques et la seconde pour les données des autres capteurs. Le processus de réduction des données fait

0

UNIVERSITE DE BOURGOGNE UFR SCIENCES ET TECHNIQUES

THESEprésentée par

Marc TOUBIN

pour obtenir le grade de

DOCTEUR DE L'UNIVERSITEdiscipline Instrumentation et Informatique de l’Image

CARACTERISATION ET SIMPLIFICATION DE MODELESNUMERIQUES DE SCENES REELLES PAR APPROCHE

MULTIRESOLUTION DANS UN CONTEXTEMULTI-CAPTEURS

Soutenue le 29 Novembre 2000 devant la commission d'examen

JURY

Mongi ABIDI Professeur

Christophe DUMONT Maître de conférences

Françoise PRETEUX Professeur Rapporteur

Remy PROST Professeur Rapporteur

Frédéric TRUCHETET Professeur

Eric VERRECCHIA Professeur

0

à Stéphanie

1

REMERCIEMENTS

Je remercie mon directeur de thèse Monsieur F.Truchetet, Professeur del’Université de Bourgogne, pour m’avoir accordé sa confiance et confié la chargede ce travail. Que Monsieur P. Gorria, Professeur de l’Université de Bourgogne,reçoive ici mes remerciements pour son accueil au sein de l’équipe du Le2i del’IUT du Creusot. Je tiens à exprimer ma sincère reconnaissance à MonsieurM. A. Abidi, Professeur de l’Université du Tennessee, pour m’avoir reçu ausein du laboratoire IRIS. Je le remercie pour ses conseils judicieux.

Je tiens à exprimer ma profonde gratitude à C. Dumont pour m’avoir dirigédurant ces trois années. Je le remercie pour la qualité de son encadrement et lapertinence de ces conseils. J’associe à ces remerciements sa famille, Brigitte etMaxime, qui ont su me soutenir pendant mon séjour dans le Tennessee.

Je suis extrêmement reconnaissant à Madame F.Pretteux, Professeur àl’Institut National des Télécommunications d’Evry, et à Monsieur R. Prost,Professeur à L’Institut National des Sciences Appliquées de Lyon, pour avoiraccepté de juger ces travaux en tant que rapporteurs.

Je tiens à exprimer ma sincère reconnaissance à Monsieur E.Verrecchia,Professeur à l’université de Neuchâtel, pour son dynamisme et ses précieusesrecommandations.

Je remercie le Département Energétique Américain (DOE) ainsi que le FondsSocial Européen (FSE) pour le financement de cette thèse.

Enfin, je tiens à remercier tous mes collègues des laboratoires Le2i et IRIS quim’ont apporté leur soutien et leur sympathie tout au long de mes travaux.

0

Cette thèse est consacrée à la simplification de modèles numériques de scènes naturelles dans

un contexte multi-capteurs en vue de leur utilisation dans des environnements contraints.

Cette méthode s’appuie sur une analyse multirésolution des données afin d’extraire les

informations pertinentes contenues à différentes échelles. Les images provenant des capteurs

sont traitées à l’aide de la transformée en ondelette quinconce, construite à l’aide de nouvelles

bases, autorisant une sélection plus fine des détails. Les résultats sont regroupés sous forme de

deux images de pertinence : la première pour les données géométriques et la seconde pour les

données des autres capteurs. Le processus de réduction des données fait intervenir ces images

de pertinence afin de supprimer les informations qui n’ont pas été retenues lors de la phase

d’analyse. L’utilisateur contrôle le processus de simplification en choisissant la nature des

données et la résolution des détails des données à conserver en fonction du contexte applicatif.

Cette méthode est appliquée à la caractérisation d’objets provenant du domaine des sciences

de la Terre et à la description de sites en milieux hostiles pour la robotique.

Mots-clefs : simplification, analyse multirésolution, transformée en ondelette, objets naturels,

objets multi-modaux, objets 3D.

We present in this dissertation a simplification process that inherently deals with virtual

reality data built from multi sensory data variety. A multi-resolution approach based on the

quincunx wavelet transform allows creation of two “detail relevance” images corresponding

to the geometrical and other multi modal data sets. This process extracts detail information at

various resolutions and produces a texture image that shows the relevance of each vertex

composing the model’s mesh. These resulting images are used in the reduction process. Edges

which do not link vertices tagged as relevant collapse to one vertex. The user has input in the

process to select what resolutions and sensors are relevant according to the application

requirements. This approach is useful for model compression and mining surface details. This

method has been applied in order to characterize and to modeled object from life and earth

sciences. In robotics, this process is useful for describing hazardous scenes.

Keywords: scene building, data mining, wavelet transform, multi-modal 3D models,

simplification.

1

INTRODUCTION 3

CHAPITRE 1: INTRODUCTION AUX MODÈLES NUMÉRIQUES DANS UN CONTEXTEMULTI-CAPTEURS 7

1.1 INTRODUCTION 71.2 STRUCTURE D’UN MODÈLE NUMÉRIQUE 3D 81.2.1 TERMINOLOGIE 81.2.2 MAILLAGE TRIANGULAIRE 91.2.3 INFORMATIONS GÉOMÉTRIQUES DÉRIVÉES 131.3 LES INFORMATIONS MULTI-MODALES 141.3.1 TEXTURE 141.3.2 PLAQUAGE D’UNE TEXTURE 161.4 CONCLUSION 18

CHAPITRE 2: CONSTRUCTION DE MODÈLES NUMÉRIQUES DANS UN CONTEXTEMULTI-CAPTEURS 19

2.1 INTRODUCTION 192.2 ACQUISITION DES IMAGES DE PROFONDEUR 202.2.1 DÉFINITION ET PROPRIÉTÉS 202.2.2 LES SYSTÈMES D’ACQUISITION 232.2.3 REPRÉSENTATION EN TROIS DIMENSIONS D’UNE IMAGE DE PROFONDEUR 322.3 STRATÉGIE GÉNÉRALE DE CONSTRUCTION DE MODÈLES NUMÉRIQUES À PARTIR DEPLUSIEURS PRISES DE VUES DANS UN CONTEXTE MULTI-CAPTEURS 342.3.1 MISE EN CORRESPONDANCE 342.3.2 FUSION 372.4 SCHÉMA DE VISUALISATION D’UN MODÈLE 3D 382.4.1 RENDU 392.4.2 MANIPULATION 432.4.3 NOUVEAU SCHÉMA DE CONSTRUCTION DE MODÈLES NUMÉRIQUES 3D DANS UN CONTEXTEMULTI-CAPTEUR 442.5 RÉDUCTION DES DONNÉES TRIDIMENSIONNELLES 452.5.1 ETAT DE L’ART SUR LES MÉTHODES DE SIMPLIFICATION DE MODÈLES 3D 452.5.2 RÉDUCTION DE MODÈLES 3D MULTI-MODAUX ET ESTIMATION DE LA PERFORMANCE 492.6 CONCLUSION 51

CHAPITRE 3: DESCRIPTION MULTI-ÉCHELLES 52

3.1 INTRODUCTION 523.2 ETAT DE L’ART DES MÉTHODES D’ANALYSE MULTIRÉSOLUTION DE SURFACES 3D 533.2.1 APPROCHE UTILISANT LA TRANSFORMÉE EN ONDELETTE 533.2.2 STRATÉGIE MISE EN ŒUVRE POUR ANALYSER LES MODÈLES 3D 633.3 EXTRACTION DE L’INFORMATION À DE MULTIPLES RÉSOLUTIONS 643.3.1 PROJECTION SUR DES SOUS-ESPACES ORTHOGONAUX 643.3.2 ALGORITHME CASCADE 663.3.3 ONDELETTES SÉPARABLES 683.3.4 APPLICATION 703.3.5 ANALYSE BIORTHOGONALE 72

2

3.4 ANALYSE MULTIRÉSOLUTION QUINCONCE 753.4.1 MATRICE DE DILATATION QUINCONCE 763.4.2 ALGORITHME QUINCONCE 773.4.3 CONSTRUCTION DES FILTRES QUINCONCES 783.5 SEGMENTATION 833.5.1 MISE EN ÉVIDENCE DES ZONES D’INTÉRÊT 833.5.2 MÉTHODE DES PASSAGES PAR ZÉRO 833.5.3 SEUILLAGE DE WEN 853.6 CONCLUSION 88

CHAPITRE 4: SIMPLIFICATION 89

4.1 INTRODUCTION 894.2 RÉDUCTION 904.2.1 MÉTHODOLOGIE 904.2.2 VECTEUR MULTI-COMPOSANTES 904.2.3 MISE EN OEUVRE 924.2.4 PROPRIÉTÉS 954.3 IMPACT DE LA DESCRIPTION MULTI-ÉCHELLES 964.3.1 SIMPLIFICATION CONTRÔLÉE PAR LA DESCRIPTION MULTI-ÉCHELLES 964.3.2 INTERACTION AVEC L’UTILISATEUR 1004.4 CONCLUSION 109

CHAPITRE 5: APPLICATION 111

5.1 INTRODUCTION 1115.2 APPLICATION AUX SCIENCES DE LA TERRE 1125.2.1 CARACTÉRISATION DES STRIES DE CROISSANCES SUR DES COQUILLAGES 1125.2.2 CONSTRUCTION D’UN MODÈLE NUMERIQUE A PARTIR D’UN FOSSILE : L’AMMONITE 1205.2.3 ANALYSE DE MODÈLES NUMÉRIQUES DE TERRAIN 1235.3 APPLICATION À LA ROBOTIQUE 1255.3.1 CARACTÉRISATION DE SITES EN MILIEUX HOSTILES 1255.3.2 VISUALISATION 1285.4 CONCLUSION 130

CONCLUSION 131

BIBLIOGRAPHIE 135

Introduction

3

Introduction

Le développement des techniques graphiques de réalité virtuelle offre des outils de plus en

plus performants permettant la visualisation des modèles numériques sur des écrans

d’ordinateurs. Ces modèles numériques sont des représentations synthétiques du monde réel

qui nous entoure ou même de celui imaginaire inventé par l’esprit de l’homme.

De nombreuses applications dans des secteurs civil et militaire aussi divers que la

recherche scientifique, l’automobile, l’aérospatiale, le divertissement, etc… trouvent un

intérêt à plonger une personne dans un monde virtuel. Le démantèlement de sites nucléaires

est un exemple où les modèles numériques permettent à l’homme de se promener

virtuellement dans des sites hautement hostiles tout en restant en sécurité derrière un écran

d’ordinateur. En imagerie satellitaire, la visualisation de modèles numériques de la surface de

la Terre à travers les Systèmes d’Informations Géographiques (SIG) conduit à une

observation précise de la planète permettant de tirer des conclusions de tout ordre sur : les

climats, l’exploitation agricole des sols, l’évolution de la couche d’ozone, les évolutions

géologiques, etc... L’étude de coquillages marins ou fossiles permet aux paléontologues

d’acquérir des informations sur les mouvements des plaques tectoniques au cours de l’histoire

terrestre. La caractérisation et la modélisation de leurs échantillons sont essentielles pour leurs

travaux de recherche.

Dans l’étude présentée dans ce document, nous nous intéresserons uniquement aux

modèles numériques construits à partir d’informations recueillies par des capteurs positionnés

en regard de la scène à modéliser. La construction de ses modèles numériques s’inscrit dans

un contexte multi-capteurs du fait de la diversité des capteurs que l’homme utilise pour

acquérir des informations de tout type : géométrique, luminance propre ou réfléchie dans le

domaine du visible (capteurs CCD noir et blanc ou couleur, …) ou non-visible (capteurs infra-

rouge et de radiation γ, …), composition chimique.

Introduction

4

L’amélioration nécessaire des techniques d’acquisition conduit brutalement à

l’accroissement, certes de la qualité des modèles numériques qui représentent alors fidèlement

et précisément la réalité, mais aussi de la quantité des informations. L’imagerie est le domaine

d’activité scientifique qui s’intéresse à la création des modèles numériques utilisés en réalité

virtuelle. Le contexte multi-capteurs, devenant de plus en plus d’actualité, par exemple dans

les secteurs nucléaires et satellitaires cités précédemment, force les scientifiques à étudier de

nouvelles méthodes de construction de modèles adaptés aux contraintes de transmission,

réception et de visualisation des données dans des environnements plus ou moins contraints.

A l’heure actuelle, comme nous pouvons le voir avec la définition de la norme MPEG 4 et du

futur standard MPEG 7 en particulier, un modèle numérique peut être un ensemble de

données organisées et hiérarchisées (comme le format BIFS) pouvant s’adapter aux

contraintes de son contexte applicatif. Par exemple, le niveau de détail le plus fin d’un modèle

numérique ne doit pas être utilisé par une personne (définie comme utilisateur) souhaitant un

aperçu rapide et grossier des données. Cette situation est encore plus vraie si l’utilisateur

dispose d’un ordinateur ayant de faibles capacités graphiques.

Les travaux de recherche présentés dans ce document couvrent seulement une partie des

problématiques cités précédemment dans le domaine de « l’imagerie multi-capteurs ». Cette

étude porte essentiellement sur la Simplification des données géométriques dans un contexte

Multi-capteurs pouvant s’insérer dans un schéma global de construction de modèles

numériques en vue de leur utilisation dans des environnements contraints.

Un algorithme de simplification est considéré comme un procédé intelligent qui analyse

les données multi-capteurs pour produire un modèle à un niveau de détail plus faible tout en

conservant un maximum de vraisemblance du modèle, qui doit ainsi ressembler le mieux

possible au modèle numérique du niveau de détail supérieur. Cette notion de vraisemblance

est très subjective car elle dépend de manière évidente du type d’utilisation des données et de

l’utilisateur lui-même. Par exemple, certaines applications réclament une conservation très

précise de la géométrie pour des régions du modèle à plus ou moins fortes courbures. D’autres

applications conduisent à la création de modèles numériques pour lesquels seule la qualité du

rendu visuel des informations autres que géométriques importe à l’utilisateur. Les mêmes

données peuvent alors être simplifiées de mille et une façons, et ce en fonction des contraintes

imposées par tel ou tel utilisateur placé dans tel ou tel contexte applicatif.

Introduction

5

Le but de cette recherche est de développer un algorithme de simplification permettant la

conservation d’informations multi-capteurs pertinentes sélectionnées par l’utilisateur. Les

objectifs de notre étude sont les suivants :

• simplification des données géométriques,

• prise en compte des informations multi-capteurs et

• conservation des données pertinentes.

La principale contribution apportée par notre étude est la mise au point d’une méthode

originale de simplification autorisant la conservation des informations locales provenant des

capteurs sélectionnés par l’utilisateur. Cette méthode s’inscrit dans le schéma de construction

de modèles numériques et de représentations à de multiples niveaux de détails. Elle s’articule

autour de deux outils :

• outil de caractérisation multirésolution,

• outil de simplification.

La caractérisation des données permet l’extraction des informations pertinentes sur les

images provenant des capteurs. La localisation des régions pertinentes est effectuée à l’aide

d’un algorithme d’analyse multirésolution. Cette analyse est développée à partir de la

transformée en ondelette à deux dimensions qui est construite selon un schéma non-séparable

en utilisant de nouvelles bases quinconces. Un nouveau jeu de filtres à deux dimensions, non-

séparables et bi-orthogonaux a été créé afin d’extraire les régions pertinentes contenues à

chaque résolution. Pour chaque niveau de résolution, une image de détails est produite à

l’échelle initiale en n’utilisant que les coefficients de l’échelle explorée. Cette image est

ensuite segmentée pour déterminer les zones d’informations pertinentes. Elle permet ensuite

d’établir l’image de pertinence qui servira à la conservation des détails lors de la

simplification. En effet, les données qui n’appartiennent pas aux régions pertinentes sont

réduites en première. La simplification tient compte des résultats obtenus lors de l’analyse

mutlirésolution. L’algorithme de simplification géométrique intègre et utilise les informations

sur la localisation des régions pertinentes issues des capteurs, contrairement aux autres

méthodes de simplification qui utilisent uniquement les informations sur la géométrie du

modèle. Ce travail de recherche décrit la méthode de simplification utilisée lors de la

construction de modèles numériques dans un contexte multi-capteurs.

Introduction

6

Le premier chapitre présente les modèles numériques dans un contexte multi-capteurs. Il

donne une explication sur l’organisation générale des données fournies par les capteurs afin

de représenter un modèle tridimensionnel. Les définitions relatives au vocabulaire employé en

imagerie 3D sont introduites.

Le second chapitre détaille les processus qui interviennent lors de la construction d’un

modèle numérique. Le problème lié à une quantité d’information trop importante provenant

des capteurs est mis en évidence. Un nouveau schéma de construction est alors proposé :

l’insertion d’une étape de simplification doit permettre la conservation des régions contenant

l’information dites pertinente.

Le troisième chapitre propose une méthode d’extraction des régions pertinentes à l’aide

d’une analyse multirésolution non-séparable utilisant la transformée en ondelette quinconce.

Le quatrième chapitre présente notre algorithme de simplification de modèles numériques

qui utilise les résultats de l’analyse multirésolution.

Le dernier chapitre expose l’application du processus de simplification pour la

numérisation des objets du domaine des sciences de la Terre, principalement des coquillages

et des modèles numériques de terrain, et dans le domaine de la robotique pour la

caractérisation de sites nucléaires en voie de démantèlement.

Notre étude a été réalisée dans le cadre d’un cofinancement de thèse entre le Fond Social

Européen (FSE-contrat numéro : FSE 972045) et le département de l’énergie (DOE-contrat

numéro : DOE-DE-FGO2-86NE37968) du gouvernement des Etats-Unis d’Amérique dans le

cadre d’un programme de recherche en robotique (University Research Program in Robotics).

Les travaux de recherche se sont déroulés en temps égaux au sein du laboratoire Le2i

(Laboratoire d’Electronique et d’Informatique de l’Image) de l’Université de Bourgogne (site

du Creusot) et du laboratoire IRIS (Imaging, Robotics and Intelligent Systems) de

l’Université du Tennessee, à Knoxville dans l’état du Tennessee - USA.

Chapitre 1 Introduction aux modèles numériques dans un contexte…

7

Equation Section 1

Chapitre 1 : Introduction aux modèles numériques dans un contexte multi-

capteurs

1.1 Introduction

La modélisation d’un objet naturel en trois dimensions consiste à représenter le plus

fidèlement cet objet dans un espace à trois dimensions. La géométrie d’un objet réel présente

souvent des formes variées très complexes qui ne peuvent être représentées ou approximées

par des fonctions mathématiques. La description géométrique nécessite donc un relevé

géométrique très précis de sa surface. L’acquisition de données tridimensionnelles permet

dans un premier temps la création d’un ensemble de données par échantillonnage de la surface

de l’objet. Ces données sont ensuite regroupées en sous-ensembles, généralement des facettes

à plusieurs côtés, pour former une structure à trois dimensions. La géométrie est une

composante importante au cours de l’élaboration d’un modèle. Des textures peuvent

néanmoins s’ajouter à la représentation 3D. Ces textures sont des images 2D fournies par des

capteurs en regard de l’objet qui nous donnent des informations sur l’objet. Ces informations

peuvent être des informations de couleur, de température, physiques ou chimiques mais aussi

des données synthétiques ou des informations haut niveau provenant de bases de données...

Ces textures sont positionnées sur la structure géométrique du modèle lors de sa construction.

Dans la première partie de ce chapitre, la méthode la plus utilisée pour représenter une

structure tridimensionnelle à partir d’un ensemble de données géométriques est décrite. La

notion de texture au sens de l’imagerie 3D est ensuite expliquée. La dernière partie est

consacrée à la définition du schéma général des divers traitements qui interviennent lors de

l’élaboration d’un modèle tridimensionnel.


8

Sommet

Arête

ArêteFrontière

FaceTriangulaire

FaceQuadrilatérale

Maillage

Figure 1. 1: Terminologie utilisée

1.2 Structure d’un modèle numérique 3D

La structure d’un modèle numérique 3D regroupe des données tridimensionnelles en plusieurs

ensembles sous une forme hiérarchique. Chaque ensemble dispose d’un nom bien défini qui

sera repris tout au long de ce manuscrit.

1.2.1 TERMINOLOGIE

L’entité fondamentale de la représentation 3D d’un objet réel est le sommet qui est un point

dans l’espace 3� [Mor89] [Wat93]. Deux sommets sont reliés entre eux pour former une

arête. Une arête peut se situer soit à l’intérieur du modèle, soit à sa frontière. Un polygone (ou

une face) sera formé de trois sommets ou plus, non alignés, situés dans le même plan et reliés

entre eux en séquence fermée. Cette face sera ainsi composée de trois ou plusieurs arêtes. La

multiplication de ces faces, connectées entre elles, compose un maillage. Le degré d’un

sommet sera défini comme le nombre des sommets voisins reliés au sommet par des arêtes.

La Figure 1. 1 résume la terminologie.

La face la plus simple est une face triangulaire. Elle est composée de trois sommets et de

trois arêtes. Les structures sont donc principalement composées de maillages triangulaires. Il

est à noter que tout autre plan peut se décomposer, de façon non-univoque, en polygones

triangulaires (voir Figure 1. 2).


9

Figure 1. 2: Décomposition d'un polygone à 5 arêtes en 3 facettes triangulaires

1.2.2 MAILLAGE TRIANGULAIRE

Un maillage triangulaire forme a priori un ensemble de points échantillonnés de façon

irrégulière dans l’espace. L’espace de travail n’est plus l’espace Euclidien, mais un espace

cellulaire abstrait Rd [God71].

Nous définissons une 0-cellule de Rd comme un point de Rd et une 1-cellule de Rd comme

une arête de Rd, i.e. une paire non-ordonnée de sommets distincts. Nous définissons

récursivement une d-cellule ( 2d ≥ ) de Rd comme une réunion de (d-1)-cellules. Ces cellules

sont des briques de base pour la construction d’un espace K si elles vérifient en plus les deux

conditions suivantes :

• le bord d’une cellule est constitué d’une réunion finie de cellules de K ,

• l’intersection de deux cellules de K est soit vide, soit une autre cellule de K de

dimension égale ou inférieure.

L’espace K est alors appelé complexe cellulaire.

Cette représentation cellulaire permet de définir un espace de travail pour les maillages

triangulaires. En effet, dans le cas où 2d = , l’espace 2-cellule regroupe les maillages

triangulaires. Sur la Figure 1. 3 les maillages (a) et (b) correspondent à un espace 2-cellule.

Toutes les arêtes des triangles appartiennent à une ou deux facettes triangulaires

contrairement au cas du maillage (c). D’autre part, tous les triangles rattachés à un sommet

forment un disque topologique : ils sont tous connectés entre eux par leurs arêtes. En d’autres

termes, ce disque ne doit pas contenir de trou : toutes ses faces sont connectées par

l’intermédiaire d’au moins une arête ce qui n’est pas le cas sur le maillage (d). Chaque

sommet sera ainsi relié soit à aucune, soit à deux arêtes de frontière. Une arête de frontière est

donc une arête reliée à une seule facette triangulaire.


10

(a) (b)

(c) (d)

Figure 1. 3: (a) et (b) surfaces 2-cellule, (c) et (d) surfaces qui ne sont pas des 2-cellule

La structure abstraite correspondant à un espace 2-cellule est appelée complexe simplicial

[Spa81]. Un complexe simplicial abstrait S est un ensemble }{v de sommets et un ensemble

}{ s de sous-ensembles finis et non vides de }{v appelés « simplexes » tel que :

• tout ensemble qui contient un seul sommet est un simplexe,

• tout ensemble non vide d’un simplexe est un simplexe.

La dimension d’un simplexe est définie comme le nombre de sommets moins un. La

dimension du complexe est celle du plus grand simplexe qu’il contient. La réalisation

graphique d’un simplexe peut être vu comme un polyèdre prenant appui sur des sommets.

D’après cette définition, une surface simpliciale est une surface plane et continue par

morceaux avec des facettes triangulaires. La structure d’un maillage triangulaire sera alors

définie à l’aide du couple ( , )V K ou V représente la position de N points :

{ }3 ,1iV v i N= ∈ ≤ ≤� . (1.1)

K est appelé le complexe simplicial qui contient l’information topologique. Les ensembles

constituant K sont les simplexes suivants :

• un ensemble de sommets indexés (simplexe de dimension 0)

}{1,2,...,v N= , (1.2)

• un ensemble d’arêtes indexées (simplexe de dimension 1)

}{ }{1, 2 , 1,3 , ...e = (1.3)

• et un ensemble de faces indexées (simplexe de dimension 2)

}{ }{1,2,3 , 1,3,4 , ...f = (1.4)


11

Sommet { }i

Arrête { , }i j

Face { , , }i j k

Figure 1. 4: Simplexes et leur voisinage simplicial

Un nouveau voisinage peut être défini pour chaque simplexe, appelé voisinage simplicial.

La Figure 1. 4 représente les simplexes pour un maillage triangulaire ainsi que leur voisinage

simplicial.

Deux exemples de maillage à faces triangulaires sont présentés sur la Figure 1. 5. Parmi

les maillages triangulaires rencontrés, nous pouvons distinguer trois types [Gus99] :

• régulier : chaque sommet est de degré six,

• irrégulier : les sommets peuvent avoir n’importe quel degré,

• semi-régulier : ce maillage est créé à partir d’une triangulation irrégulière puis

chaque triangle est découpé plusieurs fois en quatre (les sommets des triangles

irréguliers ont un degré arbitraire, les autres ont un degré de six).

Pour les sommets situés à la frontière, leur degré est de deux, trois ou quatre dans le cas

d’un maillage régulier. La Figure 1. 6 illustre ces trois types de maillage à faces triangulaires.


12

(a) (b)

Figure 1. 5: (a) maillage triangulaire d'après un modèle de tête (créé à l’Université de Stanford), (b) maillage

triangulaire d'un pièce métallique (disponible sur le site http://research.microsoft.com/research/graphics/hoppe)

(a) (b) (c)

Figure 1. 6: Maillage (a) régulier, (b) irrégulier et (c) semi-régulier

http://research.microsoft.com/research/graphics/hoppe


13

1.2.3 INFORMATIONS GEOMETRIQUES DERIVEES

La géométrie d’un maillage triangulaire et la distribution de ses facettes dans l’espace 3�

nous permettent de définir des paramètres qui nous renseignent sur sa structure. La normale

d’une face permet de retrouver son orientation dans l’espace. Elle se calcule à l’aide du

produit vectoriel des vecteurs qui la définissent. La normale d’un sommet iV est plus

généralement utilisée, notamment pour améliorer la qualité visuelle du maillage. Elle peut se

calculer en faisant la moyenne des normales de toutes les faces auxquelles le sommet est relié

(voir Figure 1. 7) :

1 ,

n

jj

i

FN

n==

��

��

(1.5)

où iN��

est la normale calculée pour le sommet iV , jF��

est la normale d’une face qui contient iV

et n est le nombre de faces qui contient iV .

3F��A B

C

Vi

n CB CA= ∧� ��

1

n

jj

i

FN

n==

��

��

(a) (b)

2F��

4F�� 1F

��

Figure 1. 7: (a) Normale d’une face et (b) normale d’un sommet

La courbure est une caractéristique importante dans le traitement des maillages triangulaires

car elle nous donne une information locale sur la forme. La courbure pour un sommet peut

être définie de plusieurs façons. Nous pouvons utiliser la dispersion locale des normales entre

un sommet et les faces auxquelles il est rattaché. Dans ce cas, la courbure iC pour un sommet

iV est calculée comme la variance des normales [Wat93] :

2

1 .

n

j ij

i

F NC

n=

−=

��

(1.6)


14

1.3 Les informations multi-modales

La structure du maillage ne dépend que des positions des sommets ( , , )i i i iv x y z= dans

l’espace 3� . Une propriété essentielle des maillages triangulaires est la possibilité d’ajouter

d’autres types d’information à la géométrie. Par exemple, en définissant une couleur pour

chaque sommet, nous apportons un autre type d’information. La couleur des facettes est

ensuite interpolée en fonction de la couleur des sommets composant la facette. Ce schéma de

représentation de la couleur limite la résolution qui dépendra de l’espacement entre les points.

Nous pouvons améliorer la représentation en utilisant des textures. Par exemple, dans un jeu

vidéo un personnage sera plus réaliste si on lui fait correspondre une texture qui correspond à

sa peau et ses habits. La résolution dépend alors dans ce cas, comme nous le présentons dans

la partie suivante, de la résolution de la texture appliquée à l’objet.

1.3.1 TEXTURE

La texture est une image. Elle peut représenter une propriété physique de l’objet qui peut nous

renseigner sur la nature de l’objet. La texture peut ainsi décrire le niveau de gris ou la couleur

« réelle » de l’objet. Elle peut aussi décrire des grandeurs physiques telles que la température

ou le niveau de certaines radiations. Chaque point de la texture, qui a pour coordonnées le

couple ( , )i i iTc s t= , est associé à un sommet iv appartenant au maillage auquel la texture est

appliquée [Fol90] [Hae93] :

( , , ) ( , ).i i i i i i iv x y z Tc s t= → = (1.7)

s

t

(0,0)

(1,1)

( , )i is t

( , , )i i i iv x y z=Texture

Figure 1. 8: Coordonnées de la texture d’un sommet


15

La Figure 1. 8 illustre la relation entre un sommet et ses composantes de texture. Cette

action est appelée « plaquer » la texture sur le modèle. L’emploi de cette technique permet

d’augmenter considérablement le réalisme de la représentation de l’objet. L’origine de

l’espace des textures est située au coin inférieur gauche de l’image avec pour coordonnées

(0,0) et (1,1) pour le coin supérieur droit. Les coordonnées sont comprises entre 0 et 1 quelle

que soit la taille de l’image de texture. Quand les coordonnées iTc indiquent des valeurs

supérieures à 1 ou inférieures à 0 , ce système autorise la répétition des textures (voir Figure

1. 9).

s

t

0 1 2 3

1

2

Figure 1. 9: Répétition de la texture lorsque les valeurs du couple (s, t) sont supérieures à 1


16

1.3.2 PLAQUAGE D’UNE TEXTURE

Le plaquage d’une texture sur un maillage s’effectue en déterminant les relations entre les

sommets et les coordonnées de texture. Ces relations dépendent de la position relative du

système de capture de la texture par rapport au référentiel du maillage. La texture peut ainsi

« épouser » la structure du maillage. La nouvelle couleur des sommets peut se déterminer de

plusieurs façons. La première possibilité consiste à donner à la couleur du sommet la couleur

du point de l’image de la texture correspondante. La seconde méthode permet de mettre en

évidence la géométrie et la texture. La couleur se calcule alors en moyennant les informations

de texture avec les informations de couleur des lumières diffuse et ambiante. Dans ces deux

situations, l’utilisation de coordonnées de texture définies pour chaque sommet améliore le

réalisme visuel du modèle. La Figure 1. 10, (a), (b) et (c), met en évidence l’avantage de ce

procédé que l’on retrouve dans de nombreuses applications comme lors de la conception de

jeux vidéo : un dé est construit à l’aide d’un maillage triangulaire de cube et de six images de

textures représentant les six faces du dé. La structure du maillage s’établit en définissant les

coordonnées des points du cube dans l’espace et en reliant ces points pour former des facettes

triangulaires. Il suffit ensuite d’ajouter les six fichiers images qui servent de texture et

d’indiquer les coordonnées de texture. Sans l’utilisation des textures, il aurait fallu créer un

modèle avec une structure beaucoup plus complexe. L’image (d) représente l’organigramme

du modèle tel qu’il est défini à l’aide d’Open Inventor.

La Figure 1. 11 présente un exemple de plaquage d’une texture sur un maillage

triangulaire construit à l’aide de données géométriques représentant la surface terrestre du

voisinage d’un village de la vallée de l’Ouche (Bourgogne, France). La texture plaquée est

une image synthétique numérisée d’une carte de l’Institut Géographique National

correspondant au modèle de terrain. L’image de texture vient se déformer pour couvrir toute

la surface du modèle géométrique.


17

(a)

(b) (c)

(d)

Index texture

Structure dumodèle et position

des sommetsUne face du dé :

image de texture etindex des 2 facettes

triangulaires

Nœud représentant2 faces du dé

Figure 1. 10: Amélioration du rendu visuel à l'aide de l'application de textures, (a) images des textures, (b) cube

(maillage triangulaire), (c) modèle de dé et (d) représentation sous forme de noeuds


18

+

(a) (b)

(c)

Figure 1. 11 : (a) Modèle à facettes triangulaires: la couleur est définie pour chaque sommet, (b) image de

texture, (c) modèle représenté avec sa texture: modulation entre la couleur et la texture

1.4 Conclusion

La modélisation d’un objet naturel en trois dimensions doit fournir une représentation de la

réalité. Nous avons rappelé dans ce chapitre la définition d’un modèle 3D. Ce modèle est

composé d’une structure appelée le maillage et d’une ou plusieurs textures. Le maillage est un

ensemble de facettes qui relient les points de l’espace délimitant la forme de l’objet. Les

textures sont des images 2D de capteurs placés en regard de la scène ou une image

synthétique qui nous renseigne sur l’objet. Nous ne traiterons par la suite que les modèles à

facettes triangulaires qui pourront comporter des textures.

Nous présentons dans le chapitre suivant, le détail des phases d’élaboration de la

construction de modèles 3D multi-modaux à partir d’objets naturels.

Chapitre 2 Construction de modèles numériques…

19

Equation Section 2

Chapitre 2 : Construction de modèles numériques dans un contexte multi-

capteurs

2.1 Introduction

Le modèle numérique se construit à partir de données géométriques de la structure de l’objet

sous observation puisqu’elles sont le support de l’information multi-capteurs. Les systèmes

d’acquisition tridimensionnels sans contact permettent la capture de ce type de données. De

nombreuses techniques non destructives existent. La qualité de ces appareils de mesure

permet maintenant de concevoir des modèles très précis et suscite un intérêt grandissant dans

tous les domaines où la description de surface, comme la Conception Assistée par Ordinateur

(CAO), est importante. Nous privilégions les méthodes d’acquisition qui fournissent des

images de profondeur. La création d’un modèle à l’aide d’images de profondeur se

décompose en plusieurs étapes. En premier lieu, il faut sélectionner les prises de vues car une

seule prise ne peut pas toujours capturer toute la surface d’un objet. Ensuite, la mise en

correspondance des images de profondeur détermine les transformations entre chaque prise de

vue. En effet, un espace de référence unique doit être défini dans lequel chaque image de

profondeur peut être référencée de manière spatiale. La dernière étape consiste à fusionner les

données de chaque prise de vue.

Des capteurs placés dans la scène en regard de l’objet fournissent les données sous forme

d’images pour créer les textures qui seront appliquées sur le maillage. Une étape de mise en

correspondance établit les relations entre les images de profondeur et les textures associées

pour les convertir dans un même référentiel.

Une fois le modèle construit et défini dans un espace de référence, il peut être visualisé

sous de multiples points de vue sur un écran à deux dimensions. Cette opération est effectuée

en définissant les paramètres d’une caméra virtuelle qui produit une vue du modèle 3D.

Lorsqu’une transformation géométrique est appliquée à l’objet, plusieurs vues du modèle sont

déterminées afin d’obtenir un affichage régulier de la transformation.


20

Comme la quantité d’information contenue dans le modèle dépend de la taille des images de

profondeur et des textures, il faudra, dans de nombreux cas, réduire la quantité des données

pour permettre un affichage régulier du modèle en mouvement.

Dans ce chapitre, nous présentons les propriétés des images de profondeur, puis une

description des systèmes d’acquisition des images de profondeur. La création d’un modèle à

partir des données géométriques de chaque prise de vue est ensuite expliquée. Le problème lié

à la quantité importante d’information est ensuite détaillé lors de l’étape de visualisation du

modèle. La dernière partie porte sur l’état de l’art des techniques de réduction des données de

profondeur.

2.2 Acquisition des images de profondeur

Les propriétés des images de profondeur sont décrites dans cette partie. Les appareils de

mesure que nous avons utilisés au cours de notre étude sont ensuite rapidement présentés.

2.2.1 DEFINITION ET PROPRIETES

Une image de profondeur contient des informations géométriques. La représentation des

points de la surface à l’aide d’une image de profondeur s’écrit sous la forme d’un graphe de

surface :

( , ).z g x y= (2.1)

Une image de profondeur est alors une fonction qui associe des points d’un sous-ensemble

X de l’espace 3� à des points images. Les points xp de X sont échantillonnés sur une

surface de référence RS tandis que les points images sp sont localisés sur les surfaces de

l’objet. La fonction définie par l’image de profondeur est, d’un point de vue géométrique, le

résultat de la projection des points de X sur l’objet. Le projecteur est un segment curviligne

d’équation connue [Sou95]. Un exemple d’image de profondeur est illustré Figure 2. 1.

Dans la pratique, la projection pour une image de profondeur est un segment de droite.

Trois surfaces de référence RS sont couramment utilisées : surface plane, cylindrique et

sphérique. Chacune de ces surfaces peut facilement être paramétrée à l’aide d’une distribution

de points sur une grille carrée. Notre étude se limitera aux images de profondeur paramétrées

à l’aide d’une surface de référence plane et dont le projeteur est un segment de droite. La

Figure 2. 2 illustre cette relation.


21

1sp

2sp

2xp

1xp

Surface de référence

Surface de l’objet

Figure 2. 1: Exemple d'image de profondeur dans le cas général

v

u x

y

Grille paramétrique

Objet

Figure 2. 2: Image de profondeur paramétrée à l'aide d'une surface plane: le projecteur est un segment de droite


22

Une image de profondeur doit être injective pour pouvoir étudier la relation de deux

éléments de surface de la scène à l’aide de leur relation dans l’espace de paramétrisation de

RS . En effet, une fonction :f X Y→ est injective si deux points de X correspondent à deux

points distincts de Y . Cette condition pour une image de profondeur dépend des projections

de la surface de référence sur l’objet. Les projections ne doivent pas s’intercepter sur la

surface de l’objet. Comme les images de profondeur sont échantillonnées à l’aide d’une grille

paramétrique plane, elles sont donc injectives. Toutes les projections sont parallèles entre

elles.

Les deux modes de représentation définis par l’image de profondeur dans le cas d’une

grille paramétrique plane comme surface de référence sont :

• les coordonnées dans l’espace 3� ,

• les niveaux de gris.

La première interprétation attribue à chaque point xip de la grille de définition de l’image

une valeur de profondeur iz . Cette valeur est définie comme la distance Euclidienne entre les

points xip de la surface de référence RS et les points sip de la surface de l’objet. Chaque

point de l’image de profondeur est considéré comme un point de l’espace 3� :

( , , )i i i ix y z=v . Les points iv sont définis dans le système de coordonnées dont l’origine est

fixée sur un point du coin de la grille et dont les axes x et y sont dans le plan contenant la

grille.

La seconde interprétation associe à la profondeur iz un niveau de gris ig . Pour la valeur

maximale de iz , le niveau noir lui est associé tandis que le blanc correspond à la valeur

minimale. Les autres valeurs de iz ont un niveau de gris échantillonné sur 256 niveaux de gris

entre le noir et le blanc. Le choix d’attribuer la valeur maximum au niveau noir est arbitraire,

l’inverse peut tout aussi bien s’appliquer et dans ce cas le noir correspond à la valeur

minimale de iz et le blanc la valeur maximale. Chaque point xip de RS est alors un pixel

( , )u v dont le niveau de gris est ig . L’image de profondeur devient une image en niveau de

gris. La Figure 2. 3 décrit les deux types de représentation d’une image de profondeur.


23

z

x

y

(a) (b)

u

v

A (1,1,5)

B (2,3,3)

C (3,1,0)

A

B

C

Figure 2. 3: (a) Interprétation géométrique de l'image de profondeur: création d'un nuage de points dans 3� ,

(b) interprétation de la même image de profondeur (a) en niveau de gris

2.2.2 LES SYSTEMES D’ACQUISITION

Les appareils de mesure de surface pour établir un modèle 3D font partie de la famille des

systèmes d'acquisition tridimensionnelles sans contact. Ces derniers se développent très

largement depuis quelques années. Deux types de méthodes sont utilisés pour obtenir des

informations tridimensionnelles :

• les méthodes directes,

• les méthodes indirectes.

Les méthodes directes consistent à mesurer la distance entre un point de référence du

capteur et les différents points de la scène. Un exemple de ces techniques se retrouve dans la

nature : la triangulation est utilisée par la plupart des mammifères et la technique du temps de

vol est utilisée par les chauves-souris.


24

Les méthodes indirectes sont peu utilisées. Plusieurs techniques permettent d’obtenir des

informations tridimensionnelles à partir de l'ombre créée par la forme des objets [Bat85].

L'orientation des surfaces peut aussi être déduite à partir du niveau de gris des pixels :

Woodham propose l'acquisition de plusieurs images avec des positions différentes d'éclairage

[Woo78]. Coulot décrit une méthode de reconstruction de profil à partir d'une seule image et

de la connaissance du diagramme de réflexion de la surface [Cou97]. La distance d'un point

peut également être déduite grâce à une séquence d'images pendant laquelle la mise au point

est modifiée [Nay94]. Enfin, des techniques utilisant l'interférométrie ou les effets de Moiré

sont parfois utilisées.

Dans cette partie, nous décrirons uniquement les systèmes utilisés au laboratoire le2i avec

le Scanner 3D et au laboratoire IRIS avec le Perceptron. Nous évoquerons aussi les principes

d’acquisition de Modèle Numérique de Terrain.

2.2.2.1 Perceptron

Le Perceptron, utilisé au laboratoire IRIS et représenté sur la Figure 2. 4, est un appareil de

mesure de profondeur qui utilise le principe de la modulation d’amplitude. La source émise

par le laser est continue. La lumière projetée par le laser est modulée en amplitude [Cha99].

La profondeur de l’objet est ainsi déterminée en mesurant la différence de phase entre le

rayon incident et le rayon retourné. Le balayage de la source permet la formation d’une

image. Un échantillonnage régulier sous forme de grille est généré en balayant la source à

l’aide de deux miroirs : un miroir azimutal polygonal et un miroir d’élévation plat. Les

miroirs se déplacent comme illustré sur la Figure 2. 5.

Figure 2. 4: Perceptron ( un système de capture d'images de profondeur)


25

Miroir rotatifà facettes

Elévation

AzimutRayon laser moduléSource laser

Miroir incliné

Figure 2. 5: Principe de formation d'une image à l'aide du Perceptron

Chaque pixel d’une image de profondeur [ ][ ]r i j capturée à l’aide d’un Perceptron est

converti en coordonnées cartésiennes de la façon suivante :

3

3

3

[ ][ ] sin( )[ ][ ] cos( )sin( )[ ][ ] cos( ) cos( )

x i j dx ry i j dy rz i j dz r

αα βα β

= += += +

(2.2)

La calibration du système est effectuée à l’aide d’une grille d’étalonnage. Elle permet de

définir les paramètres 3, et rα β . Les systèmes de calibration sont décrits dans [Cha99] et

[Dor94]. La particularité de cet appareil est de pouvoir capturer simultanément la profondeur

et la luminance des points balayés par la source laser. En effet, la mesure du coefficient de

réflexion permet d’établir une image en intensité. Ce coefficient est déterminé en calculant

l’amplitude relative du rayon retourné par l’objet. Les pixels de l’image d’intensité

correspondent ainsi aux points de l’image de profondeur : ils sont déterminés au même

moment. Un exemple d’acquisition d’images à l’aide du perceptron est présenté Figure 2. 6.

(a) (b)

Figure 2. 6: (a) Composante en intensité et (b) composante en profondeur


26

(a) (b)

Figure 2. 7: (a) Scanner tridimensionnel de type Replica Reversa et (b) exemple d’image de profondeur

2.2.2.2 Scanner tridimensionnel

Le scanner tridimensionnel de type Replica Reversa [Sca94], utilisé au laboratoire Le2i, est

un appareil de mesure de profondeur utilisant la technique de triangulation. Il est composé de

trois éléments principaux : le générateur de figure laser qui est un plan laser, le matériel

d’acquisition des images et un système mécanique permettant le balayage des faisceaux. Il

permet d’acquérir une image : la profondeur correspond à un niveau de gris. Une

photographie du système et un exemple d’acquisition de la surface d’un téléphone sont

représentés Figure 2. 7.

Le faisceau laser est dirigé vers un système optique divergent (lentille cylindrique) qui

étale le faisceau suivant un plan. L’intensité lumineuse est alors maximum au centre et décroît

de manière gaussienne sur les bords.

L’acquisition des images se fait à l’aide de deux caméras. La présence de deux caméras

permet de multiplier les points de vue et d’éviter les zones d’ombre. Ces caméras sont situées

de chaque côté de la source lumineuse.

Un moteur pas à pas déplace tout le système optique (laser et caméras) au-dessus de la

scène afin d’obtenir l’échantillonnage des points d’acquisition sur une grille.

Le calcul de la profondeur des points est réalisé en plusieurs étapes. Dans un premier

temps, le trait laser est repéré le plus précisément possible sur les plans image des caméras.

Une correction compense ensuite les erreurs de distorsion optique des caméras [Alu98].

Finalement, la position des points repérés par la caméra est calculée [Cla95].


27

La profondeur des points correspondant à la projection du plan laser sur l’objet est

déterminée à l’aide de la position du trait lumineux sur le plan image de la caméra. L’image

vue par une caméra est un tableau de dimension N M× . La distance B entre la caméra et la

source lumineuse est mesurée lors de la calibration ainsi que les angles 0A et cA (voir Figure

2. 8). La profondeur recherchée kD est simplement définie par :

tan( ).k kD B A= (2.3)

Soit λ la distance focale de la lentille, les relations nous permettent de définir kA :

0 0 0

0

0

1

tan( ) avec ,

incrément entre 2 colonnes,/ 2

tan( ) ,

( ),( 2 )tan .

c

k

kk

k c k

k c

d t t A Add k

Md dt t

A A t td M kA A

M

λ

λ

λ−

= = −

=

−− =

= − −−�= − ��

(2.4)

D B (Ak k= tan )B

DoDkDc

Faisceau de lumière

plan de référence

Ac

ddk

Axe optique

plan image (N,M) de la caméra(colonne où apparaît un des

points du trait lumineux)

λ

tk

centre de l’objectifAo

Ak

to

caméra

Figure 2. 8: Détermination de la profondeur kD


28

Le pas de déplacement est régulier suivant l’axe des x. Il correspond au pas du scanner

suivant l’axe des x. L’incrément suivant l’axe des y est défini par le choix de la largeur de

l’image (dk). Le déplacement du scanner suivant l’axe des y n’est effectué qu’après le

déplacement complet suivant l’axe des x. Il est seulement nécessaire dans le cas où la largeur

de l’objet est plus grande que l’étendue du trait laser. Le déplacement du scanner suivant l’axe

des z permet au faisceau laser d’être focalisé sur l’objet tout au long du balayage. Le calcul de

la profondeur est ainsi amélioré.

L’appareil tridimensionnel du laboratoire Le2i propose une résolution en x et en y qui

permet d’effectuer une mesure jusqu’à 50 mµ dans les deux directions. Nous proposons une

méthode simple pour vérifier si le système d’acquisition permet d’obtenir les résultats

annoncés par le constructeur. Cette méthode permet de valider les mesures pour les

applications qui ont besoin d’une précision proche de cette plage de résolution. L’étude porte

sur la fonction de transfert du système d’acquisition composé du laser et des deux caméras. La

réponse du système est caractérisée dans le domaine spatial par la PSF (Point Spread

Function) du système et dans le domaine fréquentiel par la MTF (Modulation Transfert

Function). La PSF est obtenue à l’aide de la mesure de la réponse indicielle du système

obtenue lorsqu’une transition de pente infinie lui est présentée (voir Figure 2. 9).

x

y

z

Figure 2. 9: Acquisition d’une image de profondeur d’un bord droit


29

Dans le cas du scanner Replica, une telle transition est obtenue à partir d’un bord droit placé

perpendiculairement à l’axe étudié. Les pixels de l’image de profondeur ont un niveau de gris

qui dépend de leur position par rapport au bord droit. Si le bord droit n’est pas tout à fait

perpendiculaire à l’axe, les pixels de la colonne proche du bord ne sont pas tous caractérisés

par la même profondeur. Une coupe verticale sur cette colonne, positionnée comme dans le

cas de la Figure 2. 10(b), permet d’obtenir une réponse indicielle suréchantillonnée par

rapport à une coupe verticale sur un bord droit disposé perpendiculairement à l’axe (voir

Figure 2. 10(a)). La PSF d’un pixel peut être obtenue en dérivant la réponse indicielle.

(a)

(b)

Figure 2. 10 : Position du bord droit; (a) et (b) le bord vertical est perpendiculaire à l’axe de mesure, (c) et (d)

le bord vertical est légèrement tournée.

Le pas de balayage en x et en y est fixé à 50 mµ . L’étude porte dans un premier temps sur la

résolution en x. L’angle de l’oblique par rapport à la perpendiculaire à l’axe des x est fixé à 4

degrés. La Figure 2. 11 montre un exemple d’image de profondeur obtenue.


30

Figure 2. 11 : Image de profondeur d’un bord droit en position oblique (le noir correspond à l’altitude la plus

élevée et le blanc à l’altitude la plus basse)

Le suréchantillonnage de la réponse indicielle est pris en compte lors de la mesure de la PSF.

Notre mesure consiste à déterminer le nombre de pixels de transition entre les niveaux bas et

haut sur les coupes verticales effectuées sur l’image de profondeur. Un exemple est représenté

sur la Figure 2. 12. L’image (a) correspond à une partie de la coupe au moment de la

transition entre les niveaux. La dérivation de ce signal (image (b)) nous permet de calculer la

PSF.

(a) (b)

Figure 2. 12 : Mesure expérimentale de PSF à partir d’une image de profondeur présentant une transition

oblique de 4 degrés ; (a) coupe verticale et (b) dérivation

La mesure de la largeur de la PSF est déterminée à partir du nombre de pixels de transition et

de l’angle choisi entre la normale à l’axe des x et l’inclinaison du bord droit, comme l’illustre

le schéma de la Figure 2. 13. Des valeurs de largeur de la PSF supérieures à un, indiquent que

l’appareil ne permet pas de différencier les points séparés de 50 mµ .


31

1 pixel

4 degrés

b = 14 pixels

Figure 2. 13 : Détermination du nombre de pixels de transition dans le cas théorique pour un angle donnée par

rapport à la normale à l’axe de mesure

Pour un angle de 4 degrés, le nombre moyen de pixels de transition est de 5. Cette valeur

doit être calculée pour une transition effectuée sur un pixel. La valeur de la largeur de la PSF

est donc de 0,35. Une étude similaire est conduite pour mesurer la réponse selon l’axe des y.

La valeur de la largeur de la PSF obtenue est dans ce cas de 0,38. Ces résultats prouvent que

des acquisitions effectuées tous les 50 mµ en x et en y seront correctes dès que la résolution

de l’appareil est de l’ordre de 25 mµ .

2.2.2.3 Modèle Numérique de Terrain

Les modèles numériques de terrain (MNT) sont des enregistrements numériques de

l’élévation de points du sol de la surface terrestre séparés par des intervalles réguliers. Le

regroupement de ces points forme une image de profondeur.

Les données d’un MNT sont capturées à partir des observations de l’élévation de la

surface de la Terre fournies par l’une de ces trois sources d’information : images de contour,

images aériennes et satellitaires et étude de l’altitude provenant du terrain [Let80] [Col75].

Toutes ces méthodes permettent de construire des modèles très précis et très denses. La

résolution la plus couramment utilisée lors de l’étude d’un MNT est d’un point tous les 75

mètres en x et en y . Un exemple d’image de profondeur représentant un MNT du massif du

Jura (France) est illustré sur la Figure 2. 14.


32

Figure 2. 14: Exemple de modèle numérique de terrain du massif du Jura (France)

2.2.3 REPRESENTATION EN TROIS DIMENSIONS D’UNE IMAGE DE PROFONDEUR

A partir d’une image de profondeur, un maillage triangulaire peut facilement être défini (voir

Figure 2. 15). En effet, les points sont paramétrés sur une grille rectangulaire. Ils ont tous le

même type de voisinage : quatre voisins de premier ordre et quatre voisins de second ordre.

La création du maillage s’effectue dans ce cas en deux étapes. La première phase consiste à

créer des polygones rectangulaires en reliant chaque sommet avec ses voisins du premier

ordre : deux selon l’axe x et deux suivant l’axe y . La seconde étape va permettre de

subdiviser chaque polygone en deux facettes triangulaires. Il y a alors deux possibilités pour

séparer le rectangle en deux. Soit 1 2 3 4, , et z z z z les profondeurs respectives des sommets

1 2 3 4, , et p p p p du polygone rectangulaire comme illustré sur la Figure 2. 15 :

• si 1 3 2 4( ) ( )abs z z abs z z− < − alors 1p est relié à 3p ,

• si 2 4 1 3( ) ( )abs z z abs z z− < − alors 2p est relié à 4p .

L’étude de la discontinuité entre un point et ses voisins au cours de l’élaboration du

maillage permet d’éliminer les facettes qui relient des points dont la différence de profondeur

est trop élevée pour la globalité du maillage. Le choix d’un seuil approprié autorise ainsi

l’élimination des points bruités. Ce seuillage met aussi en évidence les discontinuités de la

surface de l’objet. Cette phase peut s’effectuer plus tard lors de la construction. Des

algorithmes de segmentation peuvent permettre une séparation des éléments constituant le

modèle.

La Figure 2. 16 représente une image de profondeur et la représentation de son maillage

triangulaire.


33

1er ordre

2nd ordre

x

yz

Si abs(z1-z3)<abs(z2-z4)

Si abs(z2-z4)<abs(z1-z3)

(a) (b) (c)

p1 p2

p4 p3

p1 p2

p4 p3 p1 p2

p4 p3

Figure 2. 15: (a) Voisinage d'un point de la grille, (b) création de polygones rectangulaires et (c) création des

facettes triangulaires

(a) (b)

Figure 2. 16: (a)Image de profondeur ( 64 64× ) et (b) une vue du maillage triangulaire


34

2.3 Stratégie générale de construction de modèles numériques à partir de plusieurs

prises de vues dans un contexte multi-capteurs

La construction du modèle d’un objet en trois dimensions s’effectue à l’aide d’images de

profondeur qui recouvrent toute la surface de l’objet. Les points de vue sous lesquels l’objet

va être numérisé sont dans un premier temps sélectionnés. Ils peuvent être choisis de manière

automatique ou manuelle. La position de ces points de vue doit permettre la définition de la

surface de l’objet. Le choix dépend de l’approche privilégiée lors de la construction :

• minimiser le nombre de prises de vue [Won98],

• minimiser l’erreur lors de l’acquisition ; l’axe de prise de vue est choisi de manière

à ce que sa direction soit perpendiculaire à la surface.

L’information multi-modale correspondant à chaque image de profondeur est définie sous

forme de texture en fonction des capteurs en regard de la scène. Une première étape de mise

en correspondance doit permettre la superposition des textures sur chaque image de

profondeur. Une nouvelle mise en correspondance entre les images associées permet de

regrouper toute l’information dans un unique référentiel. Un dernier processus permet de

fusionner les zones des surfaces qui se recouvrent pour générer un seul modèle à facette

triangulaire.

2.3.1 MISE EN CORRESPONDANCE

La mise en correspondance lors de la construction d’un modèle 3D permet d’établir les

paramètres de prises de vue des multiples modalités et de projeter les données dans un unique

référentiel. Dans de nombreux cas, il n’y a pas de connaissance précise de la position des

capteurs les uns par rapport aux autres. Le mouvement entre les deux sources d’acquisition

comporte alors six degrés de liberté. La détermination de la position des capteurs se fait en

utilisant les couples d’images suivantes:

• les images des textures avec les image de profondeur,

• et les images de profondeur entre elles.

La mise en correspondance dans les deux cas s’effectue avec les mêmes techniques. Soit

T la transformation qui permet d’exprimer les coordonnées ( , , )x y z d’un point ixp de la

première prise de vue dans le référentiel de la seconde prise de vue : ' ( ', ', ')ix x y z=p . Les six

degrés de liberté définissant la transformation 3D entre les deux prises de vues sont trois

paramètres de translation ( , , )x y zt t t=d et trois angles de rotation ( , , )x y zr r r=R .


35

Si aucune distorsion n’est supposée, la transformation est alors définie par :

( ) .T = +p Rp d (2.5)

Deux approches permettent d’établir T.

2.3.1.1 Approche manuelle

Une première approche pour déterminer T repose sur la sélection de points de contrôle.

Les équations inverses de calibration des capteurs permettent de définir une fonction de

correspondance C entre le pixel d’une image et sa position dans l’espace. Si q est un point

dont les coordonnées sont exprimées dans le référentiel de la deuxième prise de vue alors

( )C q est le pixel de la deuxième image correspondant à un point de l’espace qui est le plus

proche de q. Pour établir T , des points de contrôle sont sélectionnés dans la première image.

Les points correspondants sont associés à ces points de contrôle dans la seconde image. La

transformation T est alors définie en minimisant la fonction de coût suivante :

( ) ( ( ), ( ( )))cf T d T C T=p

p p (2.6)

où d représente la distance Euclidienne en trois dimensions.

Cette technique est particulièrement utilisée dans le cas où l’objet est composé de formes

simples [Els98]. Elle permet notamment d’établir les alignements entre des données

tridimensionnelles et une image. L’objectif de recherches similaires est l’optimisation de la

fonction de coût [Bla95] [Fit93]. C’est notamment le cas de l’algorithme de recherche

itérative du point le plus proche (Iterative Closest Point) établi par Besl et al [Besl92]. Ils

cherchent à minimiser le calcul de la mesure des moindres carrés effectué sur la distance

métrique correspondant aux six paramètres de la transformation.

Cette méthode sera plutôt utilisée pour établir les relations entre une texture et une image

de profondeur car dans certains cas la modalité représentée par la texture n’a pas de lien direct

avec la profondeur. Par exemple, les informations de l’image synthétique du modèle de la

vallée de l’ouche, représenté dans le chapitre 1 sur la Figure 1.11, n’ont aucun rapport avec la

géométrie. Les zones des forêts, représentées en nuance de vert, peuvent aussi bien se situer

dans une combe, une pente ou sur un plateau.


36

2.3.1.2 Approche automatique

Dans la seconde approche, nous utilisons des outils statistiques pour mesurer le degré de

dépendance entre les images. Une fonction qui définit la similitude entre les deux images est

maximisée pour déterminer la correspondance entre les vues [Bou99]. La mesure plus récente

de similitude est fondée sur des techniques de corrélation. Cette méthode est particulièrement

efficace pour mettre en correspondance des images qui n’ont pas les mêmes modalités car

aucune hypothèse n’est effectuée sur la valeur des composantes des images. Le critère

d’information mutuelle déterminé pour la mise en correspondance est lié à la notion

d’entropie dans l’image. Il permet de quantifier le degré de dépendance en terme

d’information entre les différentes modalités [Mae97]. Le modèle de la Figure 2. 17 a été

obtenu à l’aide du calcul de la fonction de corrélation entre une image de couleur et une image

de profondeur. Il a été construit à partir d’une image de profondeur de taille 1024 1024× et

d’une image couleur 768 512× . Ce modèle est constitué d’un million de facettes triangulaires.

Le choix d’une approche manuelle ou automatique va aussi dépendre du type

d’application. Un système embarqué, comme un robot avec une caméra et un système

d’acquisition 3D, utiliserait les méthodes automatiques d’acquisition et de construction de

modèles 3D.

(a)

(b) (c)

Figure 2. 17: Mise en correspondance (a) d'une texture couleur avec (b) une image de profondeur et (c) la

représentation du modèle final


37

2.3.2 FUSION

Une fois que toutes les données sont exprimées dans un unique référentiel, celui du modèle,

les parties des surfaces qui se superposent doivent fusionner. Cette opération doit générer un

seul et unique modèle triangulaire. Les méthodes d’intégration de plusieurs images de

profondeurs peuvent être classées en deux catégories :

• structurées,

• non structurées.

Dans le cas des intégrations non structurées, les surfaces polygonales sont calculées

directement à partir d’un jeu de points tridimensionnels non organisés. La triangulation de

Delaunay a été l’une des première méthodes utilisant uniquement la position des points pour

construire un maillage [Boi84]. L’algorithme de Hoppe [Hop92] permet de calculer un

maillage à partir de points non organisés. Il détermine une fonction qui estime une distance

géométrique signée d’un jeu de points par rapport à une surface. A partir de cette fonction, il

définit le maillage en optimisant l’algorithme du « marching cubes » [Lor87].

Maillage A

Maillage B

SurfaceCommuneÉliminée

MaillageFinal

(a) (b) (c)

Figure 2. 18: (a) Le maillage A est fusionné avec le maillage B,(b) les parties communes sont éliminées et (c) la

partie éliminée est de nouveau triangulée

Les fusions structurées utilisent les informations sur les acquisitions des points comme par

exemple les propriétés de voisinage. Il faut dans un premier temps déterminer les zones des

surfaces communes aux images de profondeur pour les effacer et réajuster les maillages. La

seconde étape définit les nouvelles facettes triangulaires qui permettent de relier les maillages.


38

La Figure 2. 18 illustre le procédé de fusion de deux maillages A et B se superposant

partiellement. Soucy utilise le diagramme de Venn pour estimer les zones communes entre les

images de profondeur [Sou95]. La connexion des maillages locaux est effectuée à l’aide de la

triangulation de Delaunay. Sun et al [Sun00] utilise les mesures sur les orientations des faces

par rapport aux paramètres de prises de vues afin d’éliminer les parties communes. Turk

développe une méthode pour générer les facettes de liaison entre les parties des maillages non

communes à l’aide d’un algorithme de fermeture [Tur94]. Un exemple de fusion de maillage

est représenté sur la Figure 2. 19 utilisant la méthode de Sun et al [Sun00].

(a) (b)

(c) (d)

Figure 2. 19: Exemple de fusion réalisée à l’aide de deux prises de vue, (a) 2 images de profondeur 512 512× ,

(b) et (c) modèles 3D construit à partir des images de profondeur et (d) fusion des deux modèles (intégration

effectuée par le laboratoire IRIS de l'Université du Tennessee, USA)

2.4 Schéma de visualisation d’un modèle 3D

Les étapes d’élaboration d’une structure 3D conduisent à la création d’un modèle dans un

espace à trois dimensions. La phase de rendu va permettre la visualisation du modèle, car il

faut pouvoir afficher le maillage 3D sur un écran d’ordinateur qui, par définition, est de

dimension deux. Les trois composantes importantes qui interviennent pour afficher un modèle

sont : l’éclairage, la projection et la taille du modèle.


39

(a) (b) (c)

Figure 2. 20: Schéma de visualisation d'un modèle 3D, (a) écran de visualisation, (b) caméra virtuelle et

éclairage positionné par défaut et (c) modèle 3D

2.4.1 RENDU

Pour la visualisation d’un modèle, il faut définir un éclairage et une caméra permettant

d’obtenir une vue 2D du modèle (voir Figure 2. 20). Les couleurs du modèle sont définies

pour chaque sommet par la texture représentant la modalité que l’on souhaite afficher. Lors de

la création d’un maillage à partir d’une image de profondeur, une couleur par défaut est

donnée à tous les sommets. Dans le cas où une texture est définie pour le maillage, la couleur

des facettes dépend de la méthode d’application de texture utilisée [Wer94].

2.4.1.1 Eclairage

L’éclairage complète la description de notre objet. Il est possible de définir un modèle de

source lumineuse. Dans de nombreux cas, cette source de lumière est ponctuelle et illumine

dans toutes les directions afin de visualiser le modèle. Les propriétés lumineuses de la surface

de l’objet comme la réflexion, l’émission ou encore la diffusion sont aussi définies pour

accentuer le réalisme de l’objet. La Figure 2. 21 représente une image de profondeur sans

texture et le rendu de son maillage. La position de la source lumineuse et la couleur des points

sont choisis arbitrairement.


40

(a)

(b)

(c)

Figure 2. 21: (a) Image de profondeur (voir Figure 2. 16), (b) modèle rendu avec une source lumineuse disposée

sur la gauche de la scène et (c) la source lumineuse est placée à droite de la scène

2.4.1.2 Projection

Une fois que la scène est éclairée, il faut visualiser le modèle sur un écran 2D d’ordinateur.

Une image du modèle est alors capturée à l’aide d’une caméra virtuelle placée dans la scène.

Les deux modèles de caméra les plus couramment utilisés sont :

• caméra perspective,

• caméra orthographique.

Le premier modèle, appelé aussi modèle sténopé, fait l’hypothèse d’une projection à partir

d’un système de lentilles minces. La position dans l’image d’un pixel ( , )p x y représentant un

point ( , , )M X Y Z de l’espace est donnée par l’équation (voir Figure 2. 22):

1 .x Xy YZ

� �=� �

� �(2.7)

On peut également exprimer les coordonnées d’un point M appartenant au plan P d’équation

Z Ax By C= + + et dont la projection sur le plan image en ( , )p x y est :

.1

1

X xCY y

Ax ByZ

� �� =� �− −� ��

(2.8)


41

Malgré la simplicité de ces deux formules, la projection perspective est un phénomène non-

linéaire complexe qui soumet tout objet 3D à une série de distorsion. Notons l’effet de

distance : l’objet apparaît d’autant plus petit qu’il se trouve loin du plan de projection.

Le modèle orthographique est le modèle le plus simple utilisé en vision. Il obéit à la loi de

projection suivante (illustrée sur la Figure 2. 23) :

.x Xy Y

� �=� �

� �(2.9)

Il correspond au cas où tous les rayons optiques sont parallèles. C’est le cas d’un système de

prise de vue à ouverture très faible, tel qu’un téléobjectif. Ce modèle ne prend pas en compte

l’effet de distance [Vez95]. La projection de M dans le plan image s’écrit :

.X xY yZ Ax By C

� �� =� �� + +� �

(2.10)

La Figure 2. 24 représente deux vues d’une image de profondeur, l’une réalisée avec un

modèle de caméra orthographique, l’autre avec un modèle de caméra perspective.

Ces caméras permettent l’acquisition d’images 2D du modèle numérique. Les

mouvements de rotation et de translation de la caméra par rapport au modèle ou du modèle

par rapport à la caméra rendent le système de visualisation interactif et permettent une étude

de toute la surface de l’objet. Des modifications sur la position de la source d’éclairage, de la

scène peuvent aussi être envisagées afin de mettre en évidence des variations sur la surface du

modèle. Ces transformations requièrent un certain nombre d’opérations et sont coûteuses en

temps de traitement.


42

x

y

z

Figure 2. 22: Projection perspective suivant le modèle sténopé

x

y

Figure 2. 23: Projection orthographique

(a) (b)

Figure 2. 24: Différence entre (a) une vue d’un modèle de caméra en perspective et (b) la même prise de vue

d’un modèle de caméra orthographique


43

2.4.1.3 Taille d’un modèle

La taille d’un modèle dépend du nombre de sommets qui le composent. Cette dimension

s’exprime généralement par le nombre total de facettes représentant le modèle. La

construction d’un modèle 3D à l’aide d’images de profondeur fournit un maillage très précis.

L’image de profondeur de la Figure 2. 17 est de taille 1024 1024× et comporte 2 millions de

facettes triangulaires. L’image de texture associée est une image RGB de dimension

768 512× . La taille mémoire nécessaire pour stocker ce modèle (fichier Open Inventor) est

alors de 64 Mo.

2.4.2 MANIPULATION

Nous venons de décrire les trois principaux éléments qui interviennent lors de l’affichage d’un

modèle 3D : l’éclairage, la projection et la taille. Leur mise en œuvre nécessite de nombreux

calcul. L’impact de l’éclairage sur le maillage et la projection du modèle sur un plan 2D sont

à déterminer à chaque fois qu’une image du modèle est affichée.

Lors de la manipulation du modèle, l’utilisateur applique des transformations

géométriques afin de le visualiser sous de multiples points de vue. Pour chaque

transformation, il faut déterminer la position de tous les points du maillage, calculer quelles

sont les facettes cachées, redéfinir les effets d’ombre et afficher l’image. Malgré les progrès

des derniers matériels graphiques haut de gamme, certains fichiers contiennent trop de points

pour autoriser un affichage en temps réel.

Par exemple, pour effectuer une simple transformation géométrique du modèle de la Figure 2.

17(c) il faut 5 minutes environ de temps de calcul sur une machine Octane de Silicon

Graphics équipée d’un Processeur RISC cadencé à 195Mhz avec 512 MB de SDRAM. La

croissance des performances des ordinateurs n’est pas un facteur déterminant car la résolution

des modèles est elle aussi grandissante. En effet, la recherche de la précision est un besoin de

plus en plus important :

• en robotique dans la caractérisation d’un site nucléaire,

• en imagerie satellitaire où le besoin des informations peut être capitale dans des

applications militaires.

Nous allons donc chercher à réduire le nombre de points contenu dans le maillage.


44

2.4.3 NOUVEAU SCHEMA DE CONSTRUCTION DE MODELES NUMERIQUES 3D DANS UN

CONTEXTE MULTI-CAPTEUR

Dans le but de réduire le nombre de polygones de nos modèles 3D, nous proposons un

nouveau schéma de construction. Une étape de simplification vient s’insérer avant la mise en

correspondance des images de profondeur entre elles. Le diagramme de la Figure 2. 25

présente les étapes du nouveau schéma de création des objets 3D. La simplification s’opère

sur le maillage des images de profondeur.

Simplification

Fusion

Modèle

Prise de vue 1

Textures

Image deprofondeur

Prise de vue n

Textures

Image deprofondeur

Simplification

Figure 2. 25: Nouveau schéma de création d'un modèle 3D, une étape de simplification intervient maintenant

après chaque prise de vue

La taille des fichiers pour chaque prise de vue est dans la plupart des cas trop grande pour

permettre une fusion efficace des données. Ces traitements sont assez coûteux en temps de

calcul car le nombre de sommets du maillage est conséquent. La réduction des données avant

l’étape d’intégration va donc accélérer le processus d’intégration par la suite.

Dans le paragraphe suivant, l’état de l’art des méthodes de réduction de polygones est

décrit brièvement.


45

2.5 Réduction des données tridimensionnelles

2.5.1 ETAT DE L’ART SUR LES METHODES DE SIMPLIFICATION DE MODELES 3D

La plupart des méthodes de réduction de polygones sont apparues ces dernières années avec

l’amélioration des outils informatiques dédiés au 3D. Plusieurs caractéristiques sont à prendre

en considération lors de l’emploi d’une méthode de réduction notamment :

• les propriétés des données d’entrée et de sortie,

• la structure des données.

Le premier point définit les types de données d’entrée et de sortie. Ces données peuvent

apparaître sous forme de points, de fonctions, de surfaces paramétrées, etc…D’autres attributs

sont susceptibles de s’ajouter à cette liste, surtout dans le cas d’objets multi-modaux. La

structure des données affecte aussi la mise en œuvre de certains algorithmes. Certaines

données sont disposées sur une grille comme pour les données paramétrées, d’autres sont

disponibles sous forme hiérarchique.

Trois catégories de surface sont utilisées pour structurer les données :

• les surfaces paramétrées,

• les surfaces cellulaires,

• et les surfaces non-cellulaires.

Nous privilégions le cas des surfaces cellulaires. En effet, si dans un premier temps, les

images de profondeur semblent être des surfaces paramétrées définies sur une grille, les

modèles sont eux composés de facettes triangulaires qui peuvent contenir des trous et des

frontières. L’utilisation de données de plusieurs images de profondeur ne conduisent plus à

des données alignées sur une grille.

2.5.1.1 Méthode d’élimination

L’utilisation des méthodes d’élimination permettent de détruire les sommets, les arêtes, les

triangles, ou des parties de triangles. Ces méthodes donnent de bons résultats dans le cas de

données obtenues à l’aide d’images de profondeur. En effet, les données de profondeur

obtenues avec des scanners 3D fournissent des informations denses et parfois redondantes.

Par exemple, un mur qui peut être représenté uniquement par 4 points correspondra à des

milliers de points. L’élimination des données peut être mise en œuvre efficacement à cause de

leurs agencements [Tur94].


46

2.5.1.2 Méthode d’affinement

Les simplifications, mises en œuvre à l’aide de méthodes d’affinement, sont établies à partir

d’une représentation très simple du maillage (peu de sommets). Le but est ensuite d’ajouter

des points de détails. L’algorithme de Turk [Tur92] introduit un nombre aléatoire de sommets

sur une surface. La distribution de ces sommets dépend de la courbure de la surface. Les

sommets de départ sont entièrement éliminés et la surface finale est triangulée à nouveau.

Cette méthode a été développée pour les modèles représentés par des surfaces courbes.

D’autres méthodes subdivisent les triangles en quatre [Zor97].

2.5.1.3 Fusion de facettes coplanaires

Cette méthode permet la fusion des faces adjacentes qui possèdent des normales semblables

ou très proches. L’avantage de cet algorithme est sa rapidité de mise en œuvre et il permet de

garder les angles et arêtes pointus. Kalvin et al [Kal91] utilisent un algorithme qui permet

dans un premier temps d’approcher la surface du modèle à l’aide de polygones en utilisant

une méthode similaire au « marching cube ». Les faces adjacentes qui sont coplanaires sont

ensuite fusionnées.

(a) (b) (c)

Figure 2. 26:Méthode d'élimination des sommets, (a) choix du sommet, (b) élimination du sommet et des facettes

et (c) re-triangulation


47

2.5.1.4 Elimination de sommets

La méthode d’élimination de sommets est itérative. A chaque itération, un sommet est effacé

et les facettes qui possédaient ce sommet sont elles aussi éliminées. La zone est alors re-

triangulée. La Figure 2. 26 illustre ce procédé. Schröeder et al [Sch92] présentent un

algorithme de simplification qui utilise une méthode d’élimination des sommets. Cette

méthode préserve la topologie tout en conservant la géométrie. Un critère d’élimination est

déterminé afin de supprimer itérativement les sommets. Chaque trou formé par l’élimination

d’un sommet et des facettes adjacentes est alors re-triangulé. Plusieurs sommets peuvent être

éliminés à chaque itération. Les régions modifiées ne sont prises en compte que lors de

l’itération suivante. C’est un procédé qui entraîne dans certains cas de mauvaises réductions.

2.5.1.5 Contraction d’une arête

La contraction d’une arête permet de fusionner les deux sommets qui relient l’arête en un seul

point. Cette méthode produit de bons résultats. La Figure 2. 27 représente le mécanisme de

contraction d’une arête. Les deux faces qui contiennent l’arête sont éliminées et les triangles

adjacents sont adaptés à la nouvelle position du sommet. Hoppe [Hop96] développe l’idée

d’une représentation progressive d’un maillage. Cet algorithme est basé sur la contraction des

arêtes. L’arête à éliminer est sélectionnée par minimisation d’une fonction d’énergie. Cette

fonction dépend de la distance entre le point initial et la surface finale, du nombre de sommets

et de la taille d’un triangle. Garland et al [Gar97] éliminent itérativement les arêtes à l’aide

d’une mesure de l’erreur quadratique. L’erreur est stockée dans une matrice qui permet

l’évaluation de l’erreur globale générée par la réduction. Cette méthode ne permet pas de

préserver la topologie mais autorise la simplification des maillages qui ne sont pas cellulaires.

(a) (b)

Figure 2. 27: (a) Sélection de l'arête à contracter et (b) fusion de l'arête en un seul point


48

L’algorithme de Gourley [Gou98] reprend l’idée générale de Hoppe. L’auteur calcule une

distance pour chaque arête. Cette distance est déterminée à partir de la différence entre deux

vecteurs définis pour chaque point de l’arête. Les composantes de ces vecteurs regroupent des

données géométriques : les coordonnées ( , , )x y z , la normale, la courbure (voir chapitre 1).

La couleur peut aussi intervenir. A chaque itération, une arête est contractée et les vecteurs

des régions modifiées sont recalculés. Sa méthode est facile à mettre en œuvre. Elle est assez

rapide surtout pour des modèles qui sont de taille importante. Elle est d’autre part facilement

généralisable aux modèles 3D à composantes multiples.

2.5.1.6 Méthode du volume

La méthode volumique utilise les voxels. Un voxel est une cube unitaire de position ( , , )u v w

dans l’espace 3� . L’inconvénient de cette méthode est qu’elle ne préserve pas la topologie et

les parties du maillage contenant des détails fins. L’algorithme de He et al [He95] est

développé à l’aide d’une méthode simple pour réduire des modèles 3D. L’approche des

auteurs suit une démarche dite « traitement du signal » pour éliminer graduellement les détails

de hautes fréquences contenus dans le modèle. Le volume de l’objet est échantillonné et

chaque partie est filtrée par un filtre passe bas. Le « marching cubes » génère ensuite le

modèle final. Cet algorithme ne s’applique qu’à des surfaces fermées.

2.5.1.7 Simplification des enveloppes

Des enveloppes internes et externes sont définies par rapport au modèle. Un nouveau modèle

est alors construit à l’intérieur des deux enveloppes. Cohen et al [Coh96] présentent une

méthode sur la simplification d’enveloppes qui permet de générer des modèles hiérarchiques

présentant des niveaux de détails multiples. Une marge d’erreur est fixée par l’utilisateur pour

déterminer les limites des enveloppes interne et externe. Un inconvénient de cette méthode est

la lenteur de l’algorithme de mise en œuvre. Elle ne s’applique donc pas aux données fournies

par les images de profondeur.


49

2.5.2 REDUCTION DE MODELES 3D MULTI-MODAUX ET ESTIMATION DE LA PERFORMANCE

Le nombre important de méthodes de réduction présentées dans la section précédente

démontre qu’il n’y a pas de standard en ce qui concerne la simplification de maillages. Nous

recherchons un algorithme qui nous permette de réduire les modèles construits, à chaque prise

de vue, à partir des données provenant des multiples capteurs. La plupart des méthodes ne

gère pas ce type de modèle à l’exception des méthodes de Hoppe, Garland et Gourley.

Cignoni [Cig96] présente une méthode de comparaison de simplification de maillages qui

reste indépendante du choix de l’algorithme de réduction. Il a développé un logiciel Metro

Tool afin de comparer les performances des algorithmes de simplification. Celles-ci sont

déterminées par une évaluation de l’erreur globale. L’approximation générée par la réduction

est calculée en mesurant les distances des points du maillage initial aux surfaces du maillage

simplifié (voir Figure 2. 28).

Erreur, distance(sommet, Maillage Initial)

Arête maillage initial

Arête maillage simplifié

Figure 2. 28: Calcul approché de l'erreur globale lors de la simplification d'un maillage

Lorsque l’on regarde les résultats présentés par l’algorithme Metro [Cig98], l’algorithme

du maillage progressif de Hoppe présente dans de nombreux cas les meilleurs résultats si

l’erreur moyenne est utilisée. Mais ce résultat dépend beaucoup du type de modèle simplifié.

Son algorithme est assez lent et s’appuie avant tout sur la géométrie. Les méthodes de

Garland et de Gourley sont plus rapides avec un algorithme qui permet de prendre plus en

compte les informations multi-composantes pour Gourley.


50

Mais l’algorithme Metro s’appuie uniquement sur des critères géométriques pour

comparer les modèles simplifiés. Or si la géométrie se déforme au cours de la réduction la

texture évolue aussi. L’erreur géométrique globale n’est pas adaptée pour la simplification

d’objets naturels dans un contexte multi-capteurs car les détails dans les textures sont très

importants. Il n’y a pas d’outils pour l’instant qui compare des simplifications reposant à la

fois sur la géométrie et sur la texture.

La texture comporte des informations sur la nature du modèle comme des contours, des

détails qui ne sont pas liés à la géométrie. Dans certains cas, il faudra garder la géométrie

locale du maillage afin de préserver les informations de textures qui sont essentielles à la

représentation du modèle. Dans le cas d’un modèle multi-modal, il nous faut un algorithme de

conservation local de la géométrie fondé sur les informations dites pertinentes des textures.

La pertinence des informations est subjective et elle dépend du type d’application et de

l’expert. Il faut donc à la fois être capable d’extraire des informations multirésolution et de

laisser la possibilité à l’utilisateur ou au spécialiste de choisir les résolutions dites pertinentes

et / ou celles à éliminer. Notre outil de mesure de la pertinence est alors développé sur une

analyse multirésolution qui est capable d’extraire des informations sur la géométrie et sur les

textures. Pour l’analyse de la géométrie, l’image de profondeur peut être assimilée à une

image à deux dimensions ou un modèle à trois dimensions. L’analyse des textures ne peut

faire appel qu’à des techniques d’analyse à deux dimensions. Finalement, le choix se fait entre

deux outils d’analyse dans le cas où l’image de profondeur est considérée comme un modèle

3D et un seul outil dans l’autre cas.

La structure de l’algorithme de Gourley permet d’effectuer une simplification en fonction

de la texture. Son principal avantage est de pouvoir facilement ajouter une composante lors de

l’établissement des vecteurs multi-composantes. Il a d’ailleurs été développé dans ce but. La

distance peut ainsi dépendre d’une caractéristique autre que la simple position des sommets

dans l’espace. Néanmoins, notre méthode d’analyse de la pertinence peut être mise en œuvre

avec les méthodes de simplification de Hoppe et Garland.

Les techniques d’analyse des modalités les plus pertinentes s’appuieront sur des méthodes

d’analyse multirésolution à l’aide de la transformée en ondelette. En effet, les propriétés

spatiales et fréquentielles de la transformée en ondelette vont nous permettent d’établir un

algorithme d’extraction de l’information pour de nombreuses résolutions.


51

Notre schéma de simplification se présente de la manière suivante :

• description multirésolution des composantes géométriques,

• description multirésolution des textures,

• réduction des données non pertinentes sélectionnées par l’utilisateur.

2.6 Conclusion

Nous avons présenté dans ce chapitre les propriétés des images de profondeur ainsi que leurs

systèmes d’acquisition. Les images de profondeur nous servent de support géométrique lors

de la création de modèles multi-modaux. Ces modalités sont acquises à l’aide de capteurs et

l’emploi des textures permet une description plus réaliste d’un modèle. Nous avons montré

que lors de la phase de visualisation des modèles, il était nécessaire de réduire le nombre de

données pour permettre une manipulation en temps réel du modèle à cause de la taille, de

l’éclairage et des multiples projections. Un nouveau schéma de construction de modèle 3D a

été proposé. Nous insérons une phase de simplification après chaque prise de vue des images

de profondeur et des textures. Cette réduction prend en compte les modalités les plus

pertinentes. Pour améliorer la qualité de notre réduction, celle-ci s’appuie sur une étape de

description multirésolution utilisant soit des méthodes 2D soit des méthodes 2D et 3D, pour

mettre en valeur les régions d’intérêt de notre modèle. L’analyse multirésolution est

déterminée à l’aide de la transformée en ondelette. Le résultat de l’analyse est pris en

considération lors de la réduction.

Le chapitre suivant présente la méthode de description multi-échelles à l’aide de la

transformée en ondelette mise en œuvre pour extraire les informations à plusieurs résolutions

sur les composantes acquises à chaque prise de vue. Dans le chapitre quatre, nous verrons en

détail la méthode de réduction des données et comment la phase de description intervient

pendant la réduction des données multi-modales.

Chapitre 3 Description multi-échelles

52

Equation Section 3

Chapitre 3 : Description multi-échelles

3.1 Introduction

Notre objectif est d’effectuer une analyse multirésolution des images de profondeur et des

textures afin de dégager les régions pertinentes du modèle avant sa réduction. Les techniques

d’analyse sont développées sur des méthodes multi-échelles pour extraire les zones d’intérêt à

différentes résolutions. Le nombre de techniques à mettre en œuvre est fonction de

l’interprétation de l’image de profondeur : un maillage ou une image. Un modèle numérique

3D comportant des textures nécessite deux techniques pour effectuer sa caractérisation : une

approche 3D du maillage du modèle et une analyse 2D des textures. Dans le cas où

l’information géométrique est traitée comme une image, la même technique d’analyse peut

être utilisée pour étudier à la fois la géométrie et les textures.

Les analyses multirésolution développées à l’aide de la transformée en ondelette ont été

très utilisées ces dernières années en raison de ses propriétés spatiales et fréquentielles. Après

avoir effectué un état de l’art des méthodes d’analyse multi-échelles de modèle 3D, nous

privilégions une approche 2D du traitement de l’image de profondeur et des images des

textures. Les résultats de cette analyse multirésolution sont utilisés lors de l’étape de

réduction.

Une analyse 2D non-séparable est mise en œuvre et appliquée sur les images acquises

pour chaque prise de vue. Cette technique est employée afin d’extraire les zones d’intérêt de

nos images de profondeur, mais aussi des textures qui leur sont associées. Une application

importante de cet algorithme est l’obtention à l’échelle initiale d’une image de données

pertinentes d’un niveau de résolution plus faible.


53

L’état de l’art des méthodes d’analyse multirésolution de surface 3D est en premier lieu

présenté, puis nous expliquons pourquoi nous utilisons la transformée en ondelette sur les

images de profondeur et les textures pour accomplir notre description multi-échelle. Nous

présentons dans une seconde section notre algorithme cascade d’analyse des images de

profondeur et des textures. L’analyse multirésolution quinconce est ensuite décrite avec la

construction de nouveaux filtres 2D non-séparables. La dernière section décrit l’extraction des

zones d’intérêt sur les images construites à l’aide de notre algorithme.

3.2 Etat de l’art des méthodes d’analyse multirésolution de surfaces 3D

L’analyse multirésolution de surface 3D est apparue récemment avec l’amélioration des outils

graphiques et l’intérêt grandissant des méthodes multirésolution en traitement d’image.

L’objectif principal de ces algorithmes est la construction de maillages à des résolutions de

plus en plus grossières en calculant à chaque échelle des coefficients de détails pour pouvoir

reconstruire le maillage à sa résolution initiale. Nous présentons dans une première partie les

méthodes de description multi-échelle de modèle 3D utilisant la transformée en ondelette puis

nous présentons notre stratégie d’analyse.

3.2.1 APPROCHE UTILISANT LA TRANSFORMEE EN ONDELETTE

La transformée en ondelette a prouvé toute son efficacité dans de nombreuses applications où

une approche multirésolution avait son importance [Mey90] notamment en traitement du

signal et de l’image et dans les analyses numériques [Rio91] [Coh92a]. Les ondelettes

permettent en effet de décrire une fonction de manière hiérarchique [Dau92] : un espace

d’approximation qui représente la fonction sous sa forme globale et des espaces qui

regroupent les détails, des plus grossiers au plus fins. La transformée en ondelette fournit des

outils très performants pour décomposer, sur plusieurs niveaux de résolution, une fonction qui

représente un signal, une image ou une courbe. Les constructions classiques de la transformée

en ondelette se limitent aux fonctions définies sur des domaines simples comme les intervalles

ou les rectangles. Les surfaces 3D et les maillages ont généralement une distribution de points

dans l’espace qui n’est pas régulière. Les techniques d’analyse de modèles 3D mettant en

œuvre la transformée en ondelette doivent redéfinir des schémas de décomposition qui

respectent les propriétés des ondelettes. Nous rappelons dans un premier temps le schéma

général d’une analyse multirésolution avant de décrire les méthodes d’analyse multirésolution

utilisant la transformée en ondelette de maillages 3D.


54

3.2.1.1 Analyse multirésolution

Le schéma d’analyse multirésolution décrit par Mallat [Mal89a] fournit tous les outils

nécessaires à l’élaboration de filtres d’analyse et de synthèse dans le cadre d’une approche

multi-échelle. Les deux composantes primordiales pour effectuer une analyse multirésolution

sont :

• une chaîne infinie d’espaces emboîtés de fonctions de 2 ( )L � tels que le passage de

l’un à l’autre soit le résultat d’un changement d’échelle, 0 1 2 ...V V V⊂ ⊂ ⊂ ,

l’espace jV contient les fonctions de résolution j (les résolutions augmentent lorsque

j augmente),

• un produit scalaire ,f g défini pour chaque paire de fonctions , jf g V∈ , avec

j < ∞ .

Le produit scalaire permet de définir l’espace orthogonal complémentaire jW , appelé aussi

espace de détail :

{ }1 , 0j j jW f V f g g V+= ∈ = ∀ ∈ . (3.1)

Les espaces complémentaires orthogonaux sont écrits sous la forme : 1 ,j j jV V W+ = ⊕ car

chaque fonction 1 1j jf V+ +∈ peut s’écrire de manière unique comme une décomposition

orthogonale de fonction : 1 jj jdf f f+ = + avec j jf V∈ et .j jd W∈

La décomposition orthogonale joue un rôle important dans l’analyse multirésolution. Il est

facile de montrer que dans ce cas, jf est la meilleure approximation de 1jf + car c’est

l’unique fonction de jV qui minimise le produit 1 1, .j j j jf f f f+ +− − Une fonction

1 1j jf V+ +∈ se décompose en deux parties : une partie approximation qui est jf et une partie

détail qui est .jdf Les fonctions d’échelle servent alors de bases pour les espaces jV et les

ondelettes servent de bases pour les espaces complémentaires. Dans le cas général, ces

fonctions d’ondelettes sont définies comme des translatées et dilatées d’une fonction

particulière, l’ondelette mère. Ces ondelettes sont couramment appelées « ondelette de la

première génération ». La Figure 3. 1 représente le schéma d’analyse multirésolution.


55

0V

3V

0W

1V 1W

2V 2W

Figure 3. 1: Schéma d'analyse multirésolution

3.2.1.2 Analyse multirésolution de maillages 3D paramétrés par des plans triangulaires

Nous avons rappelé dans le premier paragraphe les propriétés de construction d’une analyse

multirésolution pour un ensemble de fonction de 2 ( )L � . Dans cette partie, nous présentons la

méthode de Lounsbery [Lou94] qui permet d’appliquer une analyse multirésolution aux

maillages de type semi-régulier. Ces maillages sont paramétrés par des surfaces triangulaires

qui se subdivisent sur plusieurs niveaux en quatre triangles. Un exemple illustrant ce type de

subdivision est représenté sur la Figure 3. 2. L’auteur définit les deux propriétés pour

construire son analyse multirésolution de maillages semi-régulier :

• il propose une méthode de subdivision récursive pour définir une séquence

d’espaces emboîtés

• et il définit ensuite un produit scalaire pour ces espaces

(a) (b) (c)

Figure 3. 2: Exemple de subdivision quaternaire de surfaces triangulaires: (a) premier niveau, (b) première

subdivision et (c) seconde subdivision


56

Un schéma de subdivision de surface permet d’affiner itérativement un maillage de contrôle0

cM vers une surface limite noté cM ∞ . A chaque étape, les positions des sommets du

maillage de 1jcM + sont calculés à partir des sommets de j

cM . Si nous notons jV le vecteur

colonne dont la ligne i correspond aux sommets i de jcM , alors il existe une matrice jP tel

que 1 .j j j+ =V P V La matrice jP caractérise la méthode de subdivision. Les valeurs de jP ne

dépendent que de la connexion des sommets de 0cM et non pas de la position géométrique de

ces sommets. Lounsbery montre que la subdivision de surfaces peut être paramétrée à l’aide

d’une fonction ( )S x où x est un point de 0cM . Il établit la correspondance S entre les points

de 0cM et de la surface limite cM ∞ . ( )S x est en fait une collection de fonctions emboîtées.

Pour 0,j s j≥ ≥ et jV le vecteur colonne de sommet de jcM , il existe des vecteurs lignes

0( ), :s j s jcM← ←Φ Φ →x tel que :

( ) ( ) .s s j jS ←= Φx x V (3.2)

L’auteur définit ensuite les fonctions d’échelle ( )jiϕ x à l’aide de la fonction ( )S x dont la

principale propriété est de pouvoir s’exprimer comme une combinaison linéaire de fonction

d’un niveau de résolution plus élevé :

( ) ( ),j ji i

iS v ϕ=x x (3.3)

avec 0j ≥ , 0cM∈x et iv représente le sommet i. Lounsbery utilise une notation matricielle

en posant ( ) (lim ( )).j s j

s

←

→∞Φ = Φx x L’équation (3.2) s’écrit alors :

( ) ( ) ,j jS = Φx x V (3.4)

où ( )jΦ x est une matrice dont les lignes représentent les fonctions d’échelle ( )jiϕ x .

Le produit scalaire de deux fonctions 0, ( )jcf g M∈ V , j < ∞ est définit selon la relation

suivante :

0 0

1, ( ) ( ) ,Aire( )

c cM M

f g f g dτ τ∈∆ ∈

=x'

x' x' x' (3.5)

où 0( )cM∆ représente les facettes triangulaires de 0cM et dx' est l’aire du triangle τ . Le

produit scalaire est, d’après l’équation (3.5), indépendant de la position géométrique des

sommets.


57

Les deux composantes nécessaires à une analyse multirésolution étant définies, Lounsbery

introduit les fonctions d’ondelette ψ sous forment matricielle 1 2( ) ( ( ), ( ),...)j j jψ ψΨ =x x x de

l’espace orthogonal complémentaire 0( )jcMW . Les lignes de la matrice ( )jΨ x représentent

les fonctions d’ondelette. jW représente la matrice des coefficients d’ondelette jiw .

Dans le cas d’une analyse multirésolution classique d’un signal ou d’une image, les filtres

d’analyse et de synthèse sont représentés par des séquences de nombres réels qui sont les

mêmes pour tout les points composant le signal ou l’image. Dans le cas de maillage semi-

régulier, les coefficients des filtres évoluent en fonction du maillage pour mesurer les

variations de la surface. Les filtres sont donc représentés par des matrices. Les filtres de

synthèse sont alors définis par la relation :

( ) ( )1( ) ( ) ( ) ,j j j j j+Φ Ψ = Φx x x P Q (3.6)

et les filtres d’analyses sont obtenus à partir de la relation inverse suivante :

( ) 1j

j jj

−�=�

�

AP Q

B(3.7)

Le schéma d’analyse multirésolution est alors déterminé à partir des matrices d’analyse et de

synthèse et nous avons les relations suivantes :1

1

,.

j j j

j j j

+

+

==

V A VW B W

(3.8)

La reconstruction au niveau supérieur est effectuée à l’aide des matrices jP et jQ :1 .j j j j j+ = +V P V Q W (3.9)

La Figure 3. 3 décrit le processus de décomposition multirésolution à l’aide de la transformée

en ondelette. A partir d’un maillage semi-régulier (a), les positions des sommets

d’approximation (b) sont obtenues à l’aide des matrices jA , les coefficients d’ondelette

obtenus avec les matrices jB . La résolution la plus grossière est pour cet exemple un octaèdre

(c). Le principal inconvénient de cette technique est la nécessité d’avoir un maillage semi-

régulier. En effet, les filtres sont définis à partir des subdivisions quaternaires du maillage. La

résolution la plus grossière 0cM représente le polygone à faces triangulaires le plus simple.

Les maillages des résolutions supérieures sont calculés par subdivisions quaternaires

successives du polygone de base suivies de déformations. La plupart des maillages ne

respectent pas cette propriété s’ils n’ont pas été construits à l’aide de schéma de subdivision

[Loo87].


58

Coefficients d ’ondelette Coefficients d ’ondelette

Figure 3. 3: Decomposition multirésolution (a) d'un maillage semi-régulier, (b) représentation d’une

approximation, (c) maillage le plus grossier(octaèdre)

Pour s’affranchir de ce problème de subdivision Eck, [Eck95] présente une méthode qui

convertit n’importe quel type de surface triangulaire en maillage semi-régulier. Sa

transformation se déroule en trois étapes. Le maillage initial est découpé à l’aide de la

triangulation de Delaunay en un polygone qui contient le minimum de faces triangulaires. Il

représente l’approximation de la plus basse résolution. Chaque face est alors utilisée pour

paramétrer localement le modèle de départ selon la règle de subdivision quaternaire. Un

nouvel échantillonnage des points du maillage est alors effectué pour que celui-ci vérifie la

propriété de subdivision. Cette transformation introduit de nombreuses erreurs dans les haut

niveaux de détail et augmente le nombre de faces pour la résolution de départ.

Valette et al [Val99] et Kim et al [Kim99] proposent d’assouplir la règle de subdivision

quaternaire : chaque face peut se subdiviser en 4, 3, 2 ou 1 (voir Figure 3. 4). Les auteurs

redéfinissent les matrices jA et jB en reformulant le produit scalaire dans le schéma

d’analyse multirésolution. Une conséquence importante de la règle de subdivision réside dans

le fait que seul les sommets de valence 4, 5 ou 6 sont simplifiés lors de la décomposition. Une

permutation d’arête entre deux faces voisines permet d’augmenter le nombre de sommets

jusqu’au nombre de valence requis mais cette transformation introduit des erreurs sur le

maillage initial.


59

Figure 3. 4: Subdivision en quatre, trois, deux ou un

3.2.1.3 Ondelettes sphériques

La transformée en ondelette sphérique s’applique aux fonctions définies sur une sphère

comme certains modèles topographiques de terrain ou des données planétaires. De

nombreuses applications pour modéliser la réflexion et l’illumination s’appuient sur des

fonctions définies sur une sphère. La première construction des ondelettes sphériques a été

réalisée par Dahlke et al [Dah94] à partir d’une spline exponentielle. Son approche utilise la

paramétrisation ( ),ϕ θ sur la sphère.

La méthode de Sweldens [Swe95] s’appuie sur la méthode du « lifting scheme » décrit

dans [Swe94] pour déterminer des bases d’ondelettes sphériques. Il s’appuie aussi sur les

travaux de Lounsbery [Lou94]. Chaque point est dans un premier temps repositionné sur une

sphère géodésique. Un voisinage à plusieurs niveaux est introduit (voir Figure 3. 5) qui

permet la construction de bases d’ondelettes.

(a) (b)

v1 v2

e1 e2

e3 e4f1

f2

Figure 3. 5: (a) sphère géodésique, (b) voisinage utilisé pour construire les bases d’ondelette


60

3.2.1.4 Analyse multirésolution de maillage 3D non régulier

La tâche principale lors d’une analyse multirésolution sur un modèle 3D irrégulier est de

trouver les maillages à des résolutions plus grossières. Comme nous le mentionnions en

introduction, la transformée en ondelette s’applique à des fonctions définies sur un support

régulier. La généralisation de l’analyse multirésolution à des données irrégulièrement

espacées ou des surfaces ne pouvant pas dans leur globalité être paramétrées par un plan

régulier, a pour objectif de retrouver et de préserver les nombreuses propriétés des ondelettes

de la première génération. Ces ondelettes généralisées à des supports irréguliers sont appelées

« ondelette de seconde génération » [Swe95]. Elles doivent en particulier générer des

algorithmes d’analyse et de synthèse rapides, de bonnes propriétés de localisation et de

séparation fréquentielle.

Daubechies et al [Dau99] et Guskov et al [Gus99] s’appuient sur la généralisation des

schémas de subdivision pour déterminer la construction des ondelettes de la seconde

génération. Les algorithmes de subdivision sont rapides et créent naturellement des structures

multirésolutions qui peuvent permettre le développement de fonctions d’échelle et

d’ondelette. Les auteurs proposent un schéma de subdivision non-uniforme construit à partir

d’un opérateur de relaxation non-uniforme et d’un procédé de sous et sur échantillonnage

déterminé à partir de l’algorithme du maillage progressif de Hoppe [Hop96].

L’opérateur de relaxation permet de lisser le maillage. Il est calculé en minimisant le

calcul d’une différence du second ordre. Cette différence du deuxième ordre, notée em , est la

différence entre deux normales de triangles voisins. Elle est associée à l’arête commune (voir

Figure 3. 6(a)). Le vecteur associé à cette différence entre deux normales est perpendiculaire à

l’arête commune car les deux normales sont perpendiculaires à cette arête. La troisième

composante de ce vecteur est nulle, donc il appartient au plan de paramétrage des deux

triangles (voir Figure 3. 6(b)). La différence de second ordre est orthogonale à l’arête

commune dans le plan de paramétrage. Une fonction d’énergie est calculée à partir de cette

différence. L’opérateur de relaxation est calculé pour un sommet et pour un voisinage donné.

Il correspond au minimum des fonctions d’énergie calculées pour chaque arête du voisinage.

Nous rappelons que l’algorithme du maillage progressif permet d’obtenir à partir d’un

maillage initial des représentations de plus en plus grossière. A chaque niveau de résolution

une arête fusionne et un sommet est éliminé (voir 2.5.1.5).


61

Plan deparamétrage

Normales auxtriangles

Plan qui contient les normalesaux 2 triangles et leurdifférence

Différence aux deuxnormales dans le plande paramétrage

Figure 3. 6: Calcul de la différence de second ordre associée à une arête

La subdivision permet à partir d’un maillage grossier de construire successivement des

maillages plus fin. L’objectif des auteurs est d’utiliser un schéma de subdivision non-

uniforme pour construire un maillage lissé qui à la même structure que le maillage initial. A

partir du maillage de la résolution la plus basse, calculé à l’aide de la méthode du maillage

progressif, les auteurs déterminent la position et les changements correspondant à l’insertion

d’un nouveau point. Cette position est calculée selon la valeur de l’opérateur de relaxation.

L’analyse multirésolution dérive du schéma pyramidal de Burt-Adelson [Bur83] (voir

Figure 3. 7). Les quatre étapes de l’analyse sont effectuées sur un sommet à la fois. Il y a dans

un premier temps un pré-filtrage, puis un sous échantillonnage, une subdivision à l’aide de

l’opérateur de relaxation et le calcul des coefficients de détail. L’étape de pré-filtrage n’est

pas nécessaire car la méthode du maillage progressif lors d’un sous échantillonnage à une

action de lissage ( ( ) ( 1)n n−→V V ). La subdivision non-uniforme permet d’établir à partir du

maillage ( 1)n−V le nouveau point qui conduit à un maillage lissé localement à la résolution n :( 1)n−V . Le calcul des détails s’effectue en faisant la différence entre les deux maillages ( )nV et( 1)n−V . Les détails ( )nW pour les niveaux de résolution n élevés proviennent des fusions

d’arêtes des résolutions fines et correspondent donc à des détails de hautes fréquences. De la

même façon, les détails ( )nW pour les niveaux de résolution n faibles correspondent à des

détails de basses fréquences. Cette analyse peut s’assimiler à une décomposition temps /

fréquence du maillage. Les auteurs n’ont pas encore trouvé de bases d’ondelette stable

numériquement qui mettent en œuvre cette analyse.


62

Pré lissage Subdivision

V(n)

V(n-1)

W(n)

Figure 3. 7: Le schéma pyramidal de Burt-Adelson

Bonneau [Bon98] présente une autre méthode pour appliquer les ondelettes à des

maillages irréguliers. Il définit deux opérateurs : un opérateur de lissage pour calculer le

maillage à un niveau de résolution plus bas et un opérateur d’erreur qui détermine la

différence entre le maillage d’approximation et celui de départ. Ces deux opérateurs sont

définis par des matrices A et B . Les matrices de synthèse P et Q regroupent les opérateurs

de reconstruction. La relation entre ces matrices est ( ) 1j

j jj

−�=�

�

AP Q

B.

Figure 3. 8: Calcul de A: intersection entre les triangles d'un niveau de résolution fin et son approximation

Pour déterminer les maillages aux résolutions moins élevés que celle du maillage initiale,

Bonneau utilise la représentation hiérarchique de la triangulation de Delaunay. Cette

représentation, comme dans le cas de l’algorithme du maillage progressif, fournie des

maillages de plus en plus simplifiés.

Le calcul de jA entre deux niveaux de résolution j et j+1, est effectué à partir du maillage

à la résolution j+1 et le maillage de la résolution j de la structure hiérarchique de Delaunay.

Les éléments de la matrice sont calculés à partir des intersections entre les triangles de la

résolution la plus fine et les triangles de la résolution grossière (voir Figure 3. 8) :


63

( )1

( , ) .( )

j jk lj

jk

aire Triangle Trianglek l

aire Triangle

+� ∩�=��

A (3.10)

La condition d’orthogonalité requise entre les espaces d’approximation et de détail permet

l’établissement de la matrice jB . jB est obtenue à partir de jA : les lignes de jA devant être

orthogonales aux lignes de jB . Notons v, w les lignes respectives de jA et jB . La condition

suivante doit être respectée :

11

1 0.( )

n

l ljl laire Triangle +=

=v w (3.11)

Bonneau généralise ainsi les fonctions de Haar pour l’analyse multirésolution de maillage

irrégulier.

3.2.2 STRATEGIE MISE EN ŒUVRE POUR ANALYSER LES MODELES 3D

3.2.2.1 Discussion

L’analyse multirésolution des maillages 3D à l’aide de la transformée en ondelette ne permet

pas de retrouver toutes les propriétés connues de cette transformée appliquée aux images 2D.

La principale différence provient de l’échantillonnage irrégulier des points du maillage dans

l’espace. Les méthodes mises en œuvre pour transformer un maillage irrégulier en maillage

semi-régulier et régulier introduisent des erreurs dans les échelles de haute résolution [Eck95].

D’autre part, les filtres développés sont très contraignants : ils sont calculés pour une

subdivision quaternaire. L’analyse ne porte alors que sur la géométrie. Les ondelettes

sphériques peuvent s’appliquer à toute fonction définie sur une sphère. La projection des

données de profondeur dans un système sphérique nécessite des phases d’interpolation qui

introduisent des erreurs dans les niveaux de détail de l’objet. Cette méthode n’est efficace que

lorsque les données sont fournies par des capteurs sphériques. Les méthodes qui définissent

un schéma d’analyse directement sur un maillage irrégulier s’appuient sur des représentations

hiérarchiques pour définir la règle de sous et sur échantillonnage. La détermination de ces

représentations comme le « maillage progressif » ou « la triangulation de Delaunay » est

longue et fastidieuse. La transformée de Guskov s’appuie sur des schémas de subdivision

d’interpolation qui introduisent des ondulations sur le maillage reconstruit [Gus99]. L’analyse

de Bonneau est plus simple à mettre en œuvre, mais les seules ondelettes généralisées sont

celles de Haar. Sa méthode ne permet pas d’utiliser des filtres plus performants.


64

3.2.2.2 Analyse 2D des images de profondeur et des textures

Les méthodes d’analyse multirésolution à l’aide de la transformée en ondelette 3D sont

comme nous venons de le voir peu nombreuses et ne connaissent pas pour l’instant l’essor des

méthodes d’analyse classiques 2D. Nous proposons donc une méthode d’analyse

multirésolution qui s’appuie sur l’analyse 2D des images de profondeur afin de retrouver

toutes les propriétés de la transformée en ondelettes définie sur un échantillonnage

rectangulaire. Le choix de cette méthode permet de ne considérer qu’une technique d’analyse

à la fois pour les images de profondeur et pour les textures. Notre algorithme construit des

images de détails à la résolution initiale qui sont ensuite utilisées lors de la réduction des

maillages. Les zones correspondant aux détails importants pour une résolution donnée ne sont

pas réduites.

3.2.2.3 Description d’un modèle 3D existant

Notre démarche s’applique également dans le cas où le modèle 3D est déjà construit. Nous

construisons un jeu de données de profondeur et de textures en effectuant des « scanning

virtuels » du modèle. Les points de prises de vue sont sélectionnés comme dans le cas réel

afin de recouvrir toute la surface du modèle. La projection virtuelle du modèle sur notre plan

de vue est un moyen de paramétrer le modèle par des grilles rectangulaires. A partir des

images de profondeur et des textures, nous reprenons le schéma d’analyse comme dans le cas

réel.

3.3 Extraction de l’information à de multiples résolutions

3.3.1 PROJECTION SUR DES SOUS-ESPACES ORTHOGONAUX

Le schéma d’analyse multirésolution orthogonal présenté par Mallat [Mal89b] s’applique à

toutes fonctions de 2 2( )L � , espace des fonctions à deux dimensions qui sont de carré

intégrable sur 2� . Soit un ensemble de sous espaces 2

jV L⊂ avec j∈ � , l’analyse

multirésolution dans le cas dyadique est alors définie par les équations suivantes:

{ }

1

2 2

-11

0 0

,

( ),

0 ,

( ) ( ) ,( ) ( - ) ,

j j

j j

j j

j j

j V V

V L

V

j si f V f x Vsi f V f V

+

∈

∈

−

∀ ∈ ⊂

=

=

∀ ∈ ∈ ⇔ ∈

∀ ∈ ∈ ⇔ ∈

x Jk x x k

�

�

�

� �

�

�

�

(3.12)


65

où J est une matrice 2 2× caractérisant le processus de dilatation qui permet de passer d’une

résolution à la suivante, 2∈x � , 2∈k � . La translation prendra la forme d’un vecteur entier

de 2� noté n, de telle sorte que ' = −x Jx n .

L’espace orthogonal complémentaire de jV dans 1jV + est jW avec 1j j jV V W+ = ⊕ et il

existe une base orthogonale pour ces sous espaces, appelée base d’ondelette orthogonale.

Notons jan les coefficients de la fonction d’approximation et jdn les coefficients

d’ondelette à la résolution j . Les projections sur les deux bases jV et jW sont définies par :

,

,

, ,

, .

jj

jj

a f

d f

ϕ

ψ

=

=

n n

n n

(3.13)

ϕ est la fonction d’échelle mère et ψ est la fonction d’ondelette mère. Ces fonctions

permettent d’établir les relations entres les fonctions de base des résolutions j :/ 2

,

/ 2,

( ) det ( ),

( ) det ( ).

j jj

j jj

ϕ ϕ

ψ ψ

− −

− −

= −

= −

n

n

x J J x n

x J J x n(3.14)

Les relations suivantes établissent le lien entre les coefficients pour deux niveaux de

résolution adjacents ( 1j + vers j ) :

1

1

( ) ,

( ) ,

j j

j j

a h a

d g a

+

+

= −

= −

n kk

n kk

k Jn

k Jn(3.15)

avec h représentant le filtre de la fonction d’échelle et g le filtre de la fonction d’ondelette.

La détermination de ces filtres est faite de la manière suivante :

1,

1,

( ) , ,

( ) , .

h

g

ϕ ϕ

ψ ϕ

=

=k

k

k

k(3.16)

Le calcul des coefficients des projections d’une fonction f à la résolution 1j + sur les sous

espaces jV et jW consiste à évaluer :

,

,

,

.

jj j

jj j

A f a

D f d

ϕ

ψ

=

=

n nn

n nn

(3.17)

L’approximation à l’échelle immédiate plus fine pourra être reconstruite en utilisant les

détails du signal fourni par sa projection sur la base de jW suivant la relation suivante :

1 .j j jA f A f D f+ = + (3.18)


66

3.3.2 ALGORITHME CASCADE

L’algorithme que nous proposons permet la construction de l’approximation de l’échelle

initiale notée initres . Cette approximation est caractérisée par les coefficients initresan de la

projection de la fonction à analyser sur les sous-espaces jV ou jW avec 0 initj res≤ < .

Puisque la résolution initiale est choisie arbitrairement, la précision de l’approximation peut

être définie librement. Les coefficients initresan représentent les résultats de la projection sur

initres de jA f ou de jD f notés respectivement ( )initres jA A f ou ( )

initres jA D f . Dans le premier

cas, les coefficients initresan sont définis par ,,init

init

resj resa A f ϕ=n n et dans le second cas

,,init

init

resj resa D f ϕ=n n .

Si 0 initj res≤ < , l’approximation à l’échelle initres de jA f est obtenue avec :

1 1( ) ( ) ( ).init init initres j res j res jA A f A A f D A f− −= + (3.19)

Si 1 1init initres resW V− −⊥ et 1initj resV V −⊂ , alors 1initres jW V− ⊥ entraînant 1( ) 0.initres jD A f− = L’équation

(3.19) s’écrit alors :

1( ) ( )init initres j res jA A f A A f−= (3.20)

La généralisation des équations précédentes (3.19) et (3.20) nous conduit à la relation suivante

(les opérateurs jA et jD sont idempotent) :

( ) .initres j jA A f A f= (3.21)

La décomposition de la fonction f pendant la phase d’analyse est une transformation bijective.

Les coefficients ( )initres jA A f sont alors calculés en reconstruisant les coefficients jan obtenus

après avoir effectué l’analyse de la fonction f et en annulant tous les coefficients de détail à

chaque échelle j . Ces coefficients représenteront une approximation à l’échelle initiale de la

projection de la fonction f sur le sous espace jV . La Figure 3. 9(b) illustre ce procédé. Une

fonction f est décomposée sur 3 niveaux (voir Figure 3. 9(a)). L’approximation de la

résolution la plus basse (échelle 3) est ensuite reconstruite à l’échelle initiale en annulant tous

les coefficients de détail. L’équation suivante est utilisée pour calculer l’approximation des

détails de la fonction f à l’échelle initiale :

1 1( ) ( ) ( ).init init initres j res j res jA D f A D f D D f− −= + (3.22)


67

Figure 3. 9: (a) Décomposition d'un signal f sur 3 niveaux d'échelle, (b) annulation des coefficients de détails

pour reconstruire une approximation non sous échantillonnée de f à l’échelle initiale et (c) reconstruction des

détails de l’échelle la plus basse à la résolution de départ en annulant les coefficients d’approximation du

niveau 0 et les coefficients de détail des niveaux supérieurs

Si i jW W⊥ et 11, ( ) ( ),init initinit res j res jj res A D f A D f−∀ ≠ − = la décomposition continue nous

permet d’écrire la relation (3.22) de la manière suivante :

( ) ( ) ( ).initres j j j j jA D f A D f D D f= + (3.23)

Les sous espaces jV et jW sont orthogonaux entre eux donc l’équation (3.23) s’écrit

finalement :

( ) .initres j jA D f D f= (3.24)

La reconstruction des détails d’un niveau de résolution j est accomplie en conservant les

coefficients de détail du niveau j , calculé lors de l’étape d’analyse du signal f, et en annulant

les coefficients d’approximation du niveau j et ceux de détail des niveaux supérieurs (plus

fins). Ces coefficients constituent une approximation à l’échelle initiale de la projection du

signal f sur le sous espace jW . La Figure 3. 9(c) représente le procédé pour la reconstruction

des détails du niveau de résolution le plus bas à l’échelle de départ.

Notre algorithme se divise donc en deux étapes. La première consiste à effectuer une

analyse multirésolution selon l’algorithme de Mallat afin de calculer les coefficients

d’approximation et de détail d’un niveau j : ja et .jd La seconde phase comprend la

reconstruction. Elle est effectuée en sélectionnant uniquement les coefficients de l’échelle

explorée. Le résultat est une fonction non sous échantillonnée de l’approximation ou de détail

de l’échelle j .


68

Ce schéma généralise l’algorithme cascade de Daubechies [Daub92 (Chapitre 6)] qui

permet la construction des fonctions d’échelle et d’ondelette.

En effet, si ,jf ϕ= 0 , nous avons ( )ja δ=n n et 0.jd =n La projection de ,jϕ 0 est alors donnée

par le calcul suivant :

,0 ,0 , ,

,0 ,

,0 ,0

,0 ,0

, ,

( ) ,

( ) .init init

j j j j j

j j j

j j j

res j j res j

A

A nAetA A A

ϕ ϕ ϕ ϕ

ϕ δ ϕϕ ϕ

ϕ ϕ

=

=

=

=

n nn

n

(3.25)

Cette équation justifie la reconstruction de la fonction d’échelle ,jϕ 0 à partir d’une impulsion

de Dirac et en ne tenant pas compte des détails.

La même opération peut être effectuée en considérant ,jf ψ= 0 . Dans ce cas 0ja =n et

( )jd δ=n n , la projection de ,jψ 0 est alors donnée par la formule suivante :

,0 ,0( )init initres j j res jA D Aψ ψ= (3.26)

Une approximation de la fonction d’ondelette peut ainsi être obtenue pour tous les niveaux de

résolution.

3.3.3 ONDELETTES SEPARABLES

3.3.3.1 Matrice de dilatation dyadique

L’analyse dyadique correspond à la matrice de dilatation J suivante :

2 02

0 2= =J I (3.27)

Cette matrice est la plus souvent utilisée dans le cadre d’analyse multirésolution d’images

[Tru99 (Chapitre 7)]. Elle correspond en effet à une simple extension des analyses à une

dimension à l’aide de produits tensoriels de deux sous espaces à une dimension.

On aura donc : 2=Jx x et 2j j=J x x et la famille de fonctions dilatées translatées est

notée :/ 2

, , ( , ) 4 (2 , 2 )j j jj m n x y x m y nϕ ϕ− − −= − − (3.28)


69

Figure 3. 10: Sous échantillonnage dans le cas dyadique

Le facteur de dilatation surfacique d’une échelle à l’autre est égal au déterminant de la matrice

de dilatation. Dans le cas d’une analyse dyadique celui-ci est égal à 4. Le passage d’une

résolution à la suivante est donnée par la relation ' 2 0' 0 2

x xy y

� � �=� � �

� � �. La Figure 3. 10 illustre

le sous échantillonnage dans le cas d’une analyse dyadique.

L’opération de dilatation agit de façon indépendante suivant les deux directions. L’analyse

multirésolution est effectuée en choisissant comme fonction d’échelle le produit de deux

fonctions d’échelle à une variable. Nous prendrons deux fois la même fonction d’échelle afin

de respecter l’isotropie du traitement. La fonction d’échelle peut s’écrire :

, , , ,( , ) ( ). ( )j m n j m j nx y x yϕ ϕ ϕ= (3.29)

3.3.3.2 Algorithme dyadique

Les opérations de filtrages seront menées en cascade suivant les lignes puis les colonnes (ou

inversement). Le signal 2D est traité comme un signal 1D et les outils d’implémentation

pourront avoir la même architecture. L’avantage de l’analyse dans le cas séparable vient du

fait que toutes les analyses 1D peuvent être transposées de la sorte à deux dimensions. Le

principe de l’algorithme est illustré par la Figure 3. 11. Les filtres h� et g� sont les filtres

symétriques dont la réponse impulsionnelle correspond aux séquences de h et g retournées.


70

(a) (b)

Figure 3. 11: (a) Schéma d'analyse d'une image et (b) algorithme de reconstruction

3.3.4 APPLICATION

La reconstruction à l’échelle initiale des images de détails ou d’approximation de résolution

plus faible permet de localiser et de visualiser la position des informations pertinentes. Pour

cela, les bases d’ondelette que nous utilisons doivent respecter les critères de localisation et de

régularité. Nous souhaitons avoir une analyse très sélective d’un point de vue fréquentiel afin

d’être le plus sélectif possible lorsqu’un niveau de résolution est déterminé. Enfin, l’analyse

doit être linéaire en phase car l’analyse est a priori isotropique.

Les propriétés des filtres sont donc les suivantes :

• symétrique,

• bonne localisation spatiale et fréquentielle,

• régularité des ondelettes.

Les bases splines répondent à ces critères. En effet, l’approximation par morceaux des

fonctions est plus fidèle : l’approximation est polynomiale avec raccordement sans

discontinuité. D’autre part, la relation de récurrence qui lie la fonction d’échelle et la réponse

fréquentielle du filtre numérique associé est similaire à une propriété voisine des fonctions

splines [Chu92]. En revanche, les bases splines ne forment pas une base orthonormée de2 ( )L . Le calcul des filtres est donc effectué à l’aide d’une méthode d’orthogonalisation de

ces bases [Dau92]. Les splines cubiques (ordre 3) apparaissent comme un bon compromis

entre la régularité souhaitée et la complexité du calcul des filtres. La Figure 3. 12 représente

les réponses fréquentielles et impulsionnelles des filtres h et g .


71

(a) (b)

(c) (d)

Figure 3. 12: Splines cubiques (a)réponse impulsionnelle du filtre d’échelle, (b) réponse impulsionnelle du filtre

d’ondelette, (c) reponse fréquentielle du filtre d’échelle et (d) réponse fréquentielle du filtre d’ondelette

L’image représentée sur la Figure 3. 13 (a) est décomposée à l’aide d’une analyse

multirésolution construite avec les bases orthogonales des splines cubiques. Si nous

souhaitons calculer le résultat de la reconstruction quand nous éliminons les coefficients

d’approximation de la résolution la plus grossière, nous reconstruisons l’approximation à

l’échelle initiale de jf A f− . Puisque l’opérateur de projection est linéaire :

1 2

1 2

( ) ( ),

( ) ... ,

( ) ... .

init init init

init

init

res j res res j

res j j j j

res j j

A f A f A f A A f

A f A f A f D f D f D f A fA f A f D f D f D f

− = −

− = + + + + −

− = + + +

(3.30)

Notre algorithme cascade nous permet de reconstruire une image des détails de toutes les

résolutions. Le résultat de l’application de cet exemple est représenté sur la Figure 3. 13 (b).


72

(a)

(b)

Figure 3. 13: (a) Image de profondeur représentant la surface d'un coquillage, (b) reconstruction d'une image

de détail des 3 niveaux de résolution inférieurs à l’échelle initiale

3.3.5 ANALYSE BIORTHOGONALE

Dans les applications liées à l’analyse d’images, il est souhaitable de préserver la symétrie

droite-gauche du traitement. Les filtres impliqués dans ce type d’analyse sont de réponse

impulsionnelle infinie. Leur mise en œuvre est alors relativement lourde. Les filtres doivent

être tronqués entraînant une transformée qui n’est pas parfaite [Coh92b]. Les bases

biorthogonales permettent une analyse et une reconstruction du signal parfaites avec les

propriétés de symétrie et de simplicité requises. Il sera plus facile de déterminer des filtres à

réponse finie à l’aide d’une analyse biorthogonale. Deux familles de fonctions duales sont

utilisées, l’une pour l’analyse et l’autre pour la synthèse. Ces fonctions sont orthogonales

entre elles, mais ne sont pas orthogonales en elles-mêmes. L’analyse duale est construite sur

des sous espaces jV emboîtés, définis à partir des fonctions d’échelle duales ,jϕ n .

Le produit scalaire des deux fonctions d’échelle est , ,, ( ')j jϕ ϕ δ= −n n' n n et

2, , 1,k

,j j jhϕ ϕ− += ∀ ∈n k Jn k n n' � avec h représentant le filtre d’échelle lors de synthèse.

L’espace complémentaire de la base duale jV est donné par l’espace d’ondelette duale jW qui

est défini par j jW V⊥ et j jW V⊥ avec V V Wj j j− = ⊕1 et 1j j jV V W− = ⊕ . Les propriétés

biorthogonales des fonctions d’ondelette sont données par :2

, ,, ( ) ( ') and , ' .j j j j j jψ ψ δ δ= − − ∀ ∈ ∀ ∈k k' k k' k,k' � � (3.31)

Les fonctions d’ondelette duales ,jψ n sont alors 2, , 1,kj j jgψ ϕ− += ∀ ∈n k Jn k n � , avec g

représentant le filtre d’ondelette de synthèse.


73

3.3.5.1 Moments nuls

Les propriétés d’approximation lors de la décomposition en ondelette sont déterminées par le

nombre N de moments nuls de la fonction d’ondelette ψ . Le nombre de moments nuls est le

plus grand nombre N pour lequel :

( ) 0, 0,..., 1.lx x dx l Nψ = = − (3.32)

Le nombre N détermine la précision avec laquelle une fonction f peut être approximée lors de

sa projection sur les espaces jV . Cette erreur est définie par 2 jN− et elle diminue lorsque les

échelles de résolution deviennent plus fines. Les ondelettes qui ont un nombre de moments

nuls élevé vont permettre de dissocier les coefficients de régions plus ou moins lisses.

3.3.5.2 Pseudocoiflets

Les pseudocoiflets forment une famille d’ondelettes biorthogonales définie par Reissell

[Rei93]. Cette famille répond aux critères de notre algorithme de représentation des détails

(voir section 3.3.4). Elle permet d’effectuer des analyses linéaires en phase et présente

l’avantage d’être à support compact. Ces ondelettes sont construites d’après la famille des

coiflets de Daubechies [Dau92 (Chapitre 8)] : familles d’ondelette orthonormales avec une

fonction d’échelle qui a des propriétés d’interpolation. On appelle fonction interpolante toute

fonction φ tel que pour n ∈ �

1 0( )

0 0if n

nif n

φ=

=≠

(3.33)

Une fonction interpolante permet un calcul facile des coefficients de la décomposition en

ondelette à partir de l’échantillonnage d’une fonction continue .

Cette famille est étendue au cas biorthogonal car il n’existe pas de base d’ondelette à

support compact qui possède des fonctions d’échelle interpolantes [Mal99 (Chapitre 7)].

La famille 2NP des pseudocoiflets présentée par Reissell respecte les propriétés suivantes :

• les fonctions d’échelle ϕ et ϕ sont symétriques,

• les 2N premiers moments de ψ et ψ sont nuls,

• ϕ satisfait la condition des moments nuls pour 2N (équation 3.28),

• ϕ ,ϕ ,ψ et ψ sont à support compact,

• ϕ est une fonction interpolante.


74

La famille 4P des pseudocoiflets présente un nombre de moments nuls de 4. Les filtres

d’ondelettes g et g sont obtenus en utilisant les filtres miroirs à partir des filtres d’échelle h

et h . L’ondelette d’analyse est donc calculée à partir de la fonction d’échelle de

reconstruction et l’ondelette de synthèse à partir de la fonction d’échelle d’analyse :

( ) ( 1) [ ]

( ) ( 1) [ ]

g h

g h

= − −

= − −

n

n

n 1 n

n 1 n(3.34)

Un exemple d’application est illustré par la Figure 3. 14. Une décomposition sur 3 niveaux

d’échelle est réalisée sur l’image de profondeur (a). Elle est suivi d’une reconstruction des

détails des 3 niveaux explorés (image (b)). La construction des fonctions d’ondelettes et

d’échelle est représentée sur la Figure 3. 15.

(a)

(b)

Figure 3. 14 : (a) Image de profondeur, (b) reconstruction d'une image des détails des 3 niveaux de résolution

inférieures à l’échelle initiale


75

(a) (b)

(c) (d)

Figure 3. 15 Représentation des fonctions d’échelle et d’ondelette à l’aide de l’agorithme cascade(3 itérations)

(a) fonction d’échelle, (b) fonction d’ondelette horizontale, (c) verticale et (d) diagonale

L’analyse biorthogonale nous permet de concevoir des filtres à réponses impulsionnelles

finies. Les filtres P4 font parties de cette catégorie. D’autre part, ils possèdent des propriétés

qui se rapprochent des filtres construits à partir de bases splines d’ordre 3.

3.4 Analyse multirésolution quinconce

Le facteur de dilatation dans le cas des ondelettes séparables est de 4 entre deux niveaux de

résolution successifs. Afin d’obtenir une analyse très fine, ce rapport entre deux échelles peut

paraître élevé. D’autres part, la nécessité de construire trois familles d’ondelettes dans le cas

d’une analyse dyadique est considéré comme un inconvénient si l’on cherche à simplifier

l’analyse multirésolution. L’analyse non-séparable permet de remédier à ces deux difficultés.


76

Figure 3. 16: Matrice de dilatation quinconce et ses “cosets”

3.4.1 MATRICE DE DILATATION QUINCONCE

La matrice de dilatation à deux dimensions est définie comme toutes les combinaisons

linéaires possibles de deux vecteurs de base ( )1 2,=J n n avec des coefficients entiers. J est

dite non-séparable si J n’est pas diagonale. Un « coset » représente tous les points générés

par la transformation de J appliquée au réseau d’entrée. Ce réseau représentera, dans notre

cas, l’image sur laquelle on effectue la décomposition. Il y a detN = J cosets et la réunion

de tous les cosets forme le réseau d’entrée.

Nous utilisons la matrice de dilatation non-séparable la plus simple que nous désignerons

par matrice de dilatation quinconce :

1 1.

1 1�

= � −�J (3.35)

Dans ce cas 2N = et il y a donc deux sous-espaces de décomposition. Les vecteurs qui

définissent cette matrice sont égaux à :

2

1 1.

1 1� �� −� �

1n n (3.36)

Le sous-échantillonnage est alors caractérisé par l’équation suivante �

= = ��

1 2

1 2

x + xy Jx

x - x. La

reconstruction est achevée en utilisant la matrice de sur-échantillonnage -1J et, dans notre cas,

12

=-1J J . La Figure 3. 16 montre les deux cosets de la matrice quinconce.


77

3.4.2 ALGORITHME QUINCONCE

La mise en œuvre d’une analyse multirésolution à base d’ondelette quinconce est faite suivant

l’algorithme de Feauveau [Fea90]. Chaque sous-niveau de décomposition a pour facteur de

résolution 2 dans chaque direction. Le nombre d’échantillons est alors divisé par deux entre

deux échelles consécutives. L’analyse quinconce permet donc d’effectuer une analyse plus

fine du signal d’entrée. La Figure 3. 17 représente l’algorithme d’analyse quinconce. Deux

filtres sont nécessaires lors de l’analyse : un filtre passe haut construit à partir des fonctions

d’ondelette quinconces et un filtre passe bas défini à partir des fonctions d’échelle. Un espace

de détail et un espace d’approximation sont obtenus à chaque décomposition.

niveau=j

Convolution avecfiltre passe-hautGarde

Convolution avecfiltre passe-basGarde

Visualisation dans laposition quinconce

niveau=j-1 niveau=j-2

Convolution avecfiltre passe-haut quinconceGarde

Convolution avecfiltre passe-bas quinconceGarde

Visualisation dans laposition quinconce

Figure 3. 17: Algorithme d'analyse quinconce


78

3.4.3 CONSTRUCTION DES FILTRES QUINCONCES

3.4.3.1 Transformée de filtre 1D

La construction des filtres dans le cas d’une analyse quinconce se fait à l’aide de filtres

déterminés lors des analyses à une dimension. Deux méthodes permettent de transformer un

filtre 1D en filtre à deux dimensions tout en gardant les propriétés de la transformée en

ondelette. L’emploi des composantes polyphasées du filtre 1D est une des première méthodes

introduite par Vetterli pour transformer le filtre [Vet92]. Les composantes polyphasées

représentent les cosets de la matrice de dilatation. Nous utiliserons la seconde méthode, celle

de McClellan, qui est plus facile à mettre en oeuvre [Mcc73].

Soit le filtre ( )H z à phase nulle, il existe un polynôme ( )Hp x avec des coefficients réels

tel que 1( ) (( ) / 2)H z Hp z z−= + . L’idée de la transformation de McClellan est de remplacer

l’expression 1( ) / 2z z−+ par un filtre de dimension deux et à phase nulle 1 2( , )F z z tel que :

1 2( ) ( ( , )).FH z Hp F z z= (3.37)

La transformée d’un filtre 1D en filtre 2D s’effectue donc en deux étapes. La première

phase consiste à extraire 1( ) / 2z z−+ de ( )H z pour construire 1(( ) / 2)Hp z z−+ . Ensuite, il

faut insérer 1 2( , )x F z z→ pour former 1 2( ( , )).Hp F z z Cette transformation est appliquée aux

filtres 1D de taille impaire et linéaires en phase, car ce sont les seuls filtres qui peuvent avoir

une phase nulle. D’autre part, les filtres biorthogonaux à support compact, sont les seuls filtres

linéaires en phase vérifiant le critère de « reconstruction parfaite » dans le cadre d’une analyse

multirésolution non-séparable [Vet92]. L’analyse multirésolution quinconce s’effectue alors à

l’aide de filtres biorthogonaux : le filtre d’échelle d’analyse ( )h z et le filtre d’échelle de

synthèse ( )h z . La transformation de McClellan est appliquée à ces deux filtres afin d’obtenir

les filtres 2D non-séparables 1 2( , )H z z et 1 2( , ).G z z Les filtres d’ondelette d’analyse

1 2( , )H z z et de synthèse 1 2( , )G z z sont alors obtenus à l’aide des relations suivantes :

1 2 1 2

1 2 1 2

( , ) ( , ),

( , ) ( , ).

H z z G z z

G z z H z z

= − −

= − − −(3.38)


79

Le filtre F à phase nulle, utilisé lors de la transformation, doit respecter les critères de

l’analyse quinconce. La substitution de 1( ) / 2z z−+ par 1 2( , )F z z est valide pour un

échantillonnage quinconce si les coefficients de F sont non nuls sur un des cosets et nuls sur

l’autre coset [Sha94]. Le filtre 2D résultant vérifie alors les propriétés d’ondelette de l’analyse

quinconce si le filtre 1D valide aussi ces propriétés. Nous utiliserons le filtre 1 2( , )F z z qui

respecte les propriétés de la transformation de McClellan :

14

1 11 2 4 4

14

0 0

( , ) 0 .

0 0

F z z

��

= ��

(3.39)

Nous appliquons cette transformation aux filtres biorthogonaux développés dans la section

3.3.5.2 : les pseudocoiflets de la famille 4P . Les résultats de cette transformation sont illustrés

par les figures suivantes : la Figure 3. 18 montre les fonctions d’échelle et d’ondelette des

filtres 2D construites à l’aide de l’algorithme cascade et la Figure 3. 19 représente les

réponses fréquentielles des filtres d’analyse et de synthèse.

(a) (b)

(c) (d)

Figure 3. 18: Représentation des fonctions d’échelle et d’ondelette (6 itérations) : (a) fonction d’échelle

d’analyse, (b) fonction d’échelle de reconstruction, (c) fonction d’ondelette d’analyse et (d) fonction d’ondelette

de synthèse


80

(a) (b)

(c) (d)

Figure 3. 19 : Représentation des réponses fréquentielles des filtres d’échelle (a)d’analyse, (b) et de synthèse et

des filtres d’ondelette (c) d’analyse et (d)de synthèse.

L’erreur quadratique moyenne est de 91,56 10−× après avoir effectué une analyse

quinconce sur deux échelles et reconstruit une image à la résolution initiale en gardant tous les

coefficients sur une machine de type PC équipée d’un processeur K6 200Mhz et de 128Mo

RAM. Le critère de reconstruction parfaite est bien vérifié.

3.4.3.2 Effet d’aliasing

Notre algorithme cascade nous permet de reconstruire les détails à plusieurs résolutions à

l’échelle initiale. Dans le cas d’une analyse quinconce, le facteur de résolution entre deux

échelles est plus petit. Il est de 2 . La sélection des résolutions des détails est donc plus fine.

Seuls les coefficients de détails correspondant aux niveaux explorés sont pris en compte

pendant le processus de reconstruction (voir 3.3.2). Les autres coefficients sont mis à zéro. Le

résultat est une image non sous-échantillonnée à la résolution initiale. Un exemple de ce

processus de multirésolution est représenté sur la Figure 3. 20. L’image de profondeur est

décomposée sur trois niveaux, et trois images de détails sont reconstruites en gardant à chaque

fois les coefficients de détail de l’échelle étudiée.


81

a)

b)

c)

d)

Figure 3. 20: Analyse multirésolution quinconce : (a) image de profondeur initiale, (b) image de profondeur

reconstruite en gardant les détails de 2 niveaux inférieurs, (c) de 3 niveaux inférieurs et (d) de 4 niveaux

inférieurs

Un artefact apparaît sur les images de détails représentées sur la Figure 3. 20. Elles ne

peuvent pas être utilisées afin d’extraire les zones d’intérêt. En effet, la forme spécifique des

fonctions d’échelle et d’ondelette reste visible après la reconstruction des détails. Ce problème

n’est pas uniquement lié aux pseudocoiflets. La même analyse a été réalisée avec les filtres B-

Splines cubiques de réponses impulsionnelles infinies. L’artefact apparaît aussi sur les images

reconstruites. Ce problème est lié au recouvrement des fonctions d’échelle et d’ondelette. En

effet, la séparation fréquentielle n’est pas parfaite entre les filtres passe-bas et les filtres passe-

haut. L’artefact provient aussi de la forme « diamant » des filtres 2D comme on peut le

visualiser sur la Figure 3. 19.

(a) (b)

(c) (d)

Figure 3. 21 : Représentation des réponses fréquentielles des filtres quasi bi orthogonaux synthétisés par la

transformation de McClellan, filtres d’échelle (a) d’analyse (b) et de synthèse et filtres d’ondelette (c) d’analyse

et (d) de synthèse.


82

Pour éviter ce problème, nous proposons d’atténuer les contraintes lors de la

transformation de McClellan et notamment dans le choix de 1 2( , )F z z . Nous allons essayer

d’accentuer la séparation fréquentielle des filtres passe-haut et passe-bas et leur donner une

forme plus circulaire.

3.4.3.3 Filtres quasi biorthogonaux pour l’analyse quinconce

Nous proposons l’utilisation du filtre 1 2( , )F z z suivant décrit par Jae [Jae90] :

1 1 18 4 81 1 1

1 2 4 2 41 1 18 4 8

( , ) .F z z −

��

= ��

(3.40)

Les filtres sont illustrés sur la Figure 3. 21. La nouvelle transformation permet de rendre les

filtres « plus circulaires » limitant ainsi les artefacts. Le critère de reconstruction parfaite n’est

plus valide, mais lorsqu’une analyse sur deux niveaux est effectuée, suivie d’une synthèse en

gardant tous les coefficients, l’erreur quadratique moyenne entre l’image initiale et l’image

reconstruite reste faible : elle est de 31.4 10−× . Ce résultat est obtenu sur une machine de type

PC avec un processeur K6 200Mhz et 128 Mo RAM.

Nous appliquons donc ces nouveaux filtres à l’image de profondeur représentée sur la

Figure 3. 22(a). Les images des détails des niveaux 2, 3 et 4 sont reconstruites et présentées

sur la Figure 3. 22 (b), la Figure 3. 22 (c) et la Figure 3. 22 (d). Si nous comparons ces images

aux résultats de la Figure 3. 20, les artefacts ont disparu.

a)

b)

c)

d)

Figure 3. 22 : Atténuation de l’effet d’aliasing : (a) image de profondeur initiale, (b) image de profondeur

reconstruite en gardant les détails de 2 niveaux inférieurs, (c) de 3 niveaux inférieurs et (d) de 4 niveaux

inférieurs


83

3.5 Segmentation

3.5.1 MISE EN EVIDENCE DES ZONES D’INTERET

Notre méthode d’analyse permet la reconstruction d’images de détails qui ont la même

résolution que l’image de départ. La segmentation des zones d’intérêt dans ces images

reconstruites nous permet de localiser facilement dans l’image de départ la position des

informations pertinentes à la résolution explorée. Les zones d’intérêt correspondent à de fortes

variations pour les détails des niveaux de résolution élevés et à des transitions plus grossières

lorsque le niveau des échelles explorées diminue. La segmentation des images reconstruites à

partir des images de profondeur met en évidence les régions où la discontinuité est assez

élevée, mais elle peut caractériser aussi les zones de plus faible variation de profondeur. A

partir des textures, les régions sélectionnées seront celles des coefficients reconstruits qui

contiennent le plus d’informations. Il existe des méthodes de seuillage à partir des coefficients

d’ondelette. Donoho [Don95] décrit une méthode de seuillage qui s’effectue sur les

coefficients d’ondelette obtenus à chaque niveau de décomposition afin de réduire la quantité

de bruit contenue dans les images. Antonini et al [Ant92] propose un algorithme pour faire de

la compression d’image. Dans la méthode présentée par ces auteurs, seuls les coefficients de

détails supérieurs à un seuil sont conservés. Contrairement aux approches classiques, nous

proposons deux méthodes de segmentation qui s’appliquent sur les images de détail

reconstruites et non sur les coefficients. La première est développée à partir des passages par

zéro, la seconde utilise un seuillage de Wen.

3.5.2 METHODE DES PASSAGES PAR ZERO

La recherche des zones d’intérêt s’effectue par la recherche des passages par zéro dans

l’image de détail reconstruite. Puisque les fonctions d’ondelette 4P sont de type dérivée du

second ordre, les passages par zéro représentent les fortes variations [Mal92]. Il ne faut pas

obligatoirement effectuer une recherche systématique des passages par zéro, car ils ne

correspondent pas tous à une variation. En effet, une forte variation engendre plusieurs

passages par zéro. La Figure 3. 23 (b) et la Figure 3. 23 (e) représentent la reconstruction des

détails après quatre niveaux de décomposition à l’aide de l’analyse multirésolution quinconce

appliquée à des images synthétiques (Figure 3. 23 (a) et Figure 3. 23 (c)) qui représentent des

échelons. La Figure 3. 23 (c) et la Figure 3. 23 (f) sont des coupes transversales. Ces figures

mettent en évidence un passage par zéro principal et des passages secondaires qui ne

correspondent pas à l’échelon.


84

(a) (b) (c)

(e)(d) (f)

Figure 3. 23: Analyse de la reconstruction des détails de l'échelle de résolution 4 par rapport à l'échelle initiale

sur un échelon vertical (a)et (b) et horizontal (d) et (e) ; (c) et (f) représente une coupe verticale et horizontale

sur (b) et (e) : les rebonds sont clairement mis en évidence

Un gradient est appliqué sur l’image de détail reconstruite pour calculer les passages par

zéro. Le passage par zéro principal, c’est-à-dire celui qui correspond à l’information, est

déterminé en utilisant la valeur du gradient. Le gradient est maximum au passage par zéro

principal. Un seuillage local est appliqué sur les valeurs des gradients pour relever les

positions des passages par zéro principaux. Une image binaire est créée où seuls les passages

par zéros sont reportés. Cette position est agrandie par un facteur proportionnel à la valeur du

gradient. La taille de la fenêtre locale, lors du seuillage, dépend de l’échelle de détail

explorée. La Figure 3. 24 illustre ce procédé. L’image (a) est celle d’un MNT sur lequel on

applique notre transformée. Les images (b) et (c) représentent le résultat de la segmentation à

l’aide de notre méthode de détection des passages par zéro principaux. Le niveau de gris est

proportionnel à la valeur du gradient au point considéré.

Cette méthode a l’avantage de sélectionner précisément la localisation des régions

pertinentes dans les images reconstruites. Néanmoins, elle n’est pas robuste au bruit.

L’application d’un gradient, sur l’image de détails, fait ressortir toutes les variations même

celles qui correspondent à du bruit ou à des variations isolées très faibles. Le seuillage local

ne permet pas l’élimination de ces régions.


85

(a)

(b) (c)

Figure 3. 24 : (a) Image de profondeur représentant un MNT de la région Canoncity de l’Arizona (USA), (b)

extraction des zones pertinentes des images de détail des résolutions 2 et 3 et (c) des images de détail des

niveaux 4 et 5.

3.5.3 SEUILLAGE DE WEN

La représentation des images de détail en niveau de gris met en évidence les zones d’intérêt :

elles sont caractérisées par un niveau de gris faible, proche du noir, ou élevé, proche du blanc.

La Figure 3. 25 illustre (images (b), (e) et (h)) cet aspect qui est dû à la normalisation des

coefficients reconstruits entre 0 et 255. Les images (c), (f) et (i) représentent les histogrammes

des images de détails.

Les histogrammes des images de détails présentent trois modes :

• les coefficients qui définissent les informations pertinentes : ceux aux valeurs

positives (pixels blancs, mode 1) et les autres aux valeurs négatives (pixels noirs,

mode 2),

• et les coefficients des régions non pertinentes (mode 3).

Une sélection à l’aide de seuils sur les histogrammes peut nous permettre d’isoler les régions

pertinentes des régions non pertinentes. La fusion de ces informations en une image binaire

nous permet finalement d’extraire les zones d’intérêt de nos images de détails.


86

(a)

(g)

(d)

(b)

(e)

(h)

(c)

(f)

(i)

Figure 3. 25: (a) Image en intensité, (b) image de détail niveau 3, (c) histogramme,(d) image de profondeur de

pièce, (e) image de détail niveau 4, (f) histogramme, (g) image de profondeur d’un coquillage, (h) image de

détail niveau 2 et (i) histogramme

L’algorithme de seuillage sélectionné est celui utilisant l’algorithme de Wen [Wen85].

L’idée principale est d’attribuer après seuillage un niveau de gris identique à tous les pixels

compris entre deux seuils. Avant le seuillage, les niveaux de gris se répartissent suivant les

valeurs [0, 255]ing ∈ et après le seuillage , les niveaux de gris prennent M valeurs

' [1, ]ing M∈ . M dépend du nombre de seuils choisis. L’algorithme conserve le plus grand

nombre possible de moments statistiques de l’histogramme lors de l’opération de seuillage. Il

permet de définir les valeurs des 1M − seuils jS . Le choix de M dépend de l’allure des

histogrammes.


87

Pour nos histogrammes de la Figure 3. 25, un nombre de seuils jS fixé à 2 permet de

segmenter les images de détail en trois régions avec chacune un niveau de gris. La Figure 3.

26 (images (b), (e) et (h)) présente un exemple de cet algorithme.

La dernière étape qui conduit à la création d’une image binaire établit la fusion entre les

zones représentant les coefficients pertinents, mais de valeurs opposées. Le résultat final est

représenté sur la Figure 3. 26 (images (c), (f) et (i)).

(a)

(g)

(d)

(b)

(h)

(e)

(c)

(i)

(f)

Figure 3. 26:(a) Image en intensité, (b)seuillage Wen avec 2 seuils, (c) binarisation,(d) image de profondeur de

pièce, (e) seuillage Wen avec 2 seuils, (f) binarisation, (g) image de profondeur d’un coquillage, (h) seuillage

Wen avec 2 seuils et (i) binarisation


88

3.6 Conclusion

Nous avons proposé dans ce chapitre une nouvelle méthode de description multi-échelles de

modèle 3D multi-modal, définie sur une grille. Notre méthode permet de localiser sur les

images de profondeur et les textures les zones pertinentes des détails contenus à de multiples

résolutions. Nous avons décrit un schéma de construction d’image de détail d’une résolution

donnée à la résolution initiale, développé à partir de la transformée en ondelette.

Nous avons utilisé une analyse non séparable afin de permettre une sélection plus fine des

échelles explorées. Pour effectuer cette analyse, nous avons développé de nouvelles bases

biorthogonales d’ondelette quinconces. La construction de filtres de réponses impulsionnelles

finies, d’analyse et de synthèse est effectuée à l’aide d’une modification de la transformée de

McClellan tout en gardant les propriétés de l’analyse en ondelette non séparable.

Enfin, nous avons présenté deux méthodes de segmentation des images de détail

reconstruites afin d’extraire les régions pertinentes des échelles explorées. Cette étape nous

permet de localiser directement sur les surfaces 3D les zones d’intérêt correspondant aux

données géométriques ou aux textures.

Ces étapes permettent d’établir « l’image de pertinence géométrique » et « l’image de

pertinence des textures » qui sont à la même résolution que l’image de profondeur et les

images de textures initiales. La location des régions d’intérêt se fait donc de manière très

précise.

Le chapitre suivant présente la méthode de simplification globale des modèles 3D, lors de

leur construction qui met en œuvre la description multi-échelles des surfaces 3D, que nous

venons de présenter.

Chapitre 4 Simplification

89

Equation Section 4

Chapitre 4 : Simplification

4.1 Introduction

Après avoir présenté les étapes de construction d’un modèle 3D à partir d’images de

profondeur et d’images de textures dans les chapitres 1 et 2, nous avons proposé une étape de

simplification qui intervient avant les phases de mise en correspondance et d’intégration.

Cette réduction des données doit faciliter et améliorer le processus de visualisation du modèle

final. Dans le chapitre précédent, nous avons présenté une méthode d’analyse multi-échelles

sur des images multi-composantes, qui permet de reconstruire à la résolution initiale une

image des détails d’une résolution donnée.

Notre schéma de réduction s’appuie sur l’algorithme de Gourley [Gou98]. La revue de

l’état de l’art des méthodes de réduction présentée dans le chapitre 2 montre que son

algorithme est rapide, facile à mettre en œuvre et il s’appuie sur les données de profondeur,

mais aussi de textures. Les images créées lors de la description multi-échelles fusionnent en

deux images appelées « image pertinence géométrique » et « image pertinence textures ». Ces

deux images interviennent lors du processus de réduction : les points et les facettes

triangulaires des régions pertinentes ne sont pas simplifiés.

Nous proposons un algorithme de simplification basé sur les composantes détail,

construites lors de l’analyse multi-échelles, qui permet de sélectionner la fréquence des détails

à réduire.

Dans un premier temps, les principales caractéristiques de l’algorithme de simplification

de Gourley sont rappelées. Dans le paragraphe suivant, nous présentons notre algorithme de

simplification qui met en œuvre les images de pertinence, déterminées lors de la description

multi-échelles. Nous proposons également de caractériser la performance de notre processus.


90

4.2 Réduction

4.2.1 METHODOLOGIE

L’algorithme, proposé par Gourley, utilise un processus de contraction des arêtes pour les

maillages à facettes triangulaires. La réduction n’est pas seulement construite sur la position

des sommets, mais aussi sur d’autres caractéristiques géométriques, telles que la normale ou

encore la courbure (voir Chapitre 1). Le maillage contient des informations qui peuvent être

utilisées lors de la simplification. Les modalités des textures en font partie et sont ainsi prises

en compte. Le processus de réduction projette toutes ces données dans un espace à plusieurs

dimensions appelé « espace des caractéristiques ». Dans cet espace, chaque sommet, et les

propriétés qui lui sont attachées, est représenté par un vecteur à n dimensions. Chaque

composante du vecteur représente un attribut du sommet. Ces attributs sont la position, la

couleur, le type (frontière, intérieur, etc.) et toutes les autres caractéristiques des textures. Un

poids est aussi attribué à chaque composante. A partir de la structure initiale du maillage et de

cet espace des caractéristiques, l’ordre dans lequel les arêtes fusionnent est déterminé à l’aide

de toutes ces informations. A chaque arête, une longueur lui est associée. Cette longueur est

déterminée en calculant une distance euclidienne entre les deux sommets, reliés par l’arête,

dans l’espace des caractéristiques. L’ordre de la contraction dépend alors de cette distance.

4.2.2 VECTEUR MULTI-COMPOSANTES

Plusieurs caractéristiques composent le vecteur utilisé pour déterminer la longueur des arêtes

dans la méthode de réduction. Ces composantes calculées pour chaque sommet sont :

• géométrie,

• couleur,

• normale,

• courbure et

• type.

La géométrie est représentée par la position du sommet ( , , )x y z . La couleur est un triplet

RGB qui est composé de la couleur diffuse ou de l’intensité du modèle au sommet. La

normale et la courbure au sommet sont définies comme dans le Chapitre 1. Enfin, le type est

une composante binaire : le point est à la frontière ou à l’intérieur du maillage. Cette dernière

caractéristique sert à préserver la frontière de l’objet. D’autres composantes peuvent être

ajoutées au vecteur, notamment les valeur des textures. Il suffit d’augmenter la dimension de

l’espace d’analyse du nombre de textures défini pour le modèle.


91

Un poids est associé à chaque composante des vecteurs. Un poids élevé pour une

caractéristique permettra de biaiser l’impact d’une autre composante plus faible lors du calcul

des distances.

La Figure 4. 1 montre un exemple simple de l’espace d’analyse utilisé pour déterminer

l’ordre de contraction des arêtes.

x

type

y

Espace d ’analyse à 3 dimensions

Structure initiale à 2 dimensions Structure initiale et longueur d’arête

1

1

1

1

1 1 1 1

1.4

1 1 1 1

1

1

1

1

1.4

1.41.4

1.4

1

1 1

1 1

1

1 1

1 11.71.7 1.7

1.7

1.7

1.7

1.7

1.7

1.71.71.7

1.4 1.4

1.4 1.4

1.41.4

1.4 1.4 1.4

1.4 1.4 1.4

11.4

1

Calcul des distances

(a) (b) (c)

Figure 4. 1 : Exemple de calcul des longueurs d’arêtes effectué dans l’espace d’analyse à l’aide des vecteurs

multi-composantes ; (a) structure initiale 2D, (b) projection dans l’espace d’analyse (nous ne prenons dans cet

exemple que 3 composantes : x, y , type) et (c) résultats des calculs des longueurs d’arête

Un maillage dans 2� avec 25 sommets est représenté sur la Figure 4. 1 (a). Dans cet exemple,

les vecteurs sont définis à chaque sommet pour trois composantes : la position x, la position y,

et le type. L’espace d’analyse est donc à trois dimensions. Les arêtes sont projetées dans cet

espace (voir Figure 4. 1 (b)). La longueur de chaque arête est ensuite calculée en utilisant une

norme dans l’espace d’analyse entre les deux sommets composant l’arête (voir Figure 4. 1

(c)). Cette distance est calculée selon la formule suivante :

( ) ,ij i jL w v v= −� � � (4.1)

où ijL représente la longueur de l’arête entre les deux vecteurs multi-composantes iv� et jv�

calculés à partir des sommets iV et jV , et w� le vecteur poids. Dans notre exemple, le poids

attribué à chaque composante est identique.

L’ensemble � regroupe les valeurs des distances ijL .


92

La longueur minimum k� est trouvée en prenant le minimum de � . L’arête associée avec

cette longueur minimum est fusionnée, c’est-à-dire que les deux sommets qui la composent se

regroupent en un seul sommet. L’arête est alors retirée de l’ensemble .k= −� � � Ce processus

est répété itérativement.

4.2.3 MISE EN OEUVRE

La première étape consiste à définir les composantes qui interviendront dans la réduction. Une

fois l’espace d’analyse défini, les sommets sont projetés dans cet espace afin de déterminer les

vecteurs caractéristiques. Un vecteur poids est fixé pour déterminer l’impact relatif des

composantes, les unes par rapport aux autres. La longueur des arêtes ijL est ensuite calculée.

Le mécanisme de contraction des arêtes commence. L’arête correspondant à la longueur

minimale est supprimée en un nouveau sommet. Pour préserver les frontières, plusieurs cas

sont considérés. Si l’arête est une arête frontière, les deux sommets qui la composent sont des

sommets frontières. Dans ce cas, l’arête se contracte sur le sommet qui présente l’angle le plus

petit entre l’arête et les arêtes frontières voisines. Le deuxième cas intervient lorsque l’arête à

contracter est composée d’un point frontière et d’un point interne. Afin de préserver la

frontière, l’arête se contracte sur le sommet externe. La dernière situation est celle où l’arête

est formée de deux sommets internes. Dans cette situation, l’arête fusionne en un nouveau

sommet qui est situé au milieu de l’arête. La Figure 4. 2 représente un exemple pour chacun

de ces cas.

A chaque contraction d’arête, il faut mettre à jour les évolutions qui interviennent

localement sur le maillage. En effet, lorsque qu’une arête est supprimée, une à deux faces

disparaissent. Dans le même temps, certaines arêtes voisines se superposent. Il faut éliminer

ces redondances et recalculer les longueurs des arêtes qui ont changé. La Figure 4. 3 montre

un exemple de la zone à mettre à jour lors d’une contraction d’arête (a) et le maillage après

contraction (b).

A la fin de chaque itération, un niveau de résolution est ajouté ainsi que la liste des faces

éliminées et des nouvelles faces créées. La réduction se poursuit jusqu’à l’obtention du

rapport de réduction souhaité. Ce rapport est déterminé en utilisant soit un nombre minimum

de triangle à atteindre ou un pourcentage de triangles éliminés par rapport au nombre de

facettes initiales.


93

V1

V2

A1

A2

A1<A2

V1

V1

V2V2

V1

V2

V3

(a)

(b)

(c)

Figure 4. 2 : Contraction des arêtes, (a) l’arête est composée de deux sommets frontières, (b) d’un sommet

frontière et d’un sommet interne et (c) deux sommets internes

(a) (b)

Figure 4. 3 : (a) Arêtes et faces qui subissent une modification, les faces noires sont éliminées et les faces grises

sont remises à jour, (b) résultat après contraction de l’arête et remise à jour


94

Deux exemples de réduction sont représentés sur la Figure 4. 4 et la Figure 4. 5. La

première réduction est appliquée à un modèle d’avion. Le second exemple est la

simplification d’un modèle construit à partir d’une image de profondeur acquise avec un

scanning laser du même type que le Perceptron. La taille de l’image de profondeur est de

512 384× , soit un nombre de facettes de 195K. Dans les deux cas, les paramètres choisis pour

le calcul des vecteurs sont la position, la normale et le type avec un poids équivalent.

Réduction: 90.2%

Réduction: 99.6%

40K facettes

(a)

(b)

(c)

Figure 4. 4 : (a) Modèle initial, (b) facteur de réduction de 90.2% et (c) facteur de réduction de 99.6% (les

images de gauche représentent une projection du modèle et celles de droite le maillage)


95

(a)

(b) (c)

Figure 4. 5 : (a) Image de profondeur (données fournies par le laboratoire ORNL, Oak Ridge, USA), (b) modèle

après un taux de réduction de 94,7% et (c) maillage correspondant

4.2.4 PROPRIETES

L’aspect multi-composantes du vecteur caractéristique calculé pour chaque sommet avant la

réduction permet de nombreuses combinaisons pour le choix des paramètres. Il peut contenir

aussi bien des informations géométriques que des informations de texture. L’importance

relative de chaque composante est fixée par la valeur du poids qui leur est attribuée. La

réduction du nombre de données peut, par exemple, dépendre de valeurs thermiques et non

géométriques.

L’algorithme de Gourley est mis en œuvre à l’aide d’outils de développement standard.

Gourley construit sa réduction à l’aide des librairies Open Inventor et OpenGL. Ces librairies

sont couramment utilisées en traitement 3D. Il est par conséquent facile d’apporter des

modifications à cet algorithme. De plus, la simplicité de cette méthode de réduction permet

d’obtenir des performances élevées en temps de calcul. Cette caractéristique est importante,

surtout lorsque la taille des fichiers à simplifier dépasse les 30K facettes.


96

4.3 Impact de la description multi-échelles

Notre simplification doit nous amener à réduire le nombre de points qui composent la surface

initiale tout en conservant les informations définies comme pertinentes par l’utilisateur. Nous

présentons dans cette partie notre algorithme de simplification qui intègre les résultats de

l’analyse multi-échelles.

4.3.1 SIMPLIFICATION CONTROLEE PAR LA DESCRIPTION MULTI-ECHELLES

Notre algorithme de simplification se décompose en deux étapes. La première phase traite

les données des images de profondeur et des textures. Une analyse multirésolution développée

à l’aide de la transformée en ondelette quinconce construit des images de détails pertinents à

plusieurs résolutions. L’utilisateur filtre ces données afin de sélectionner les images

pertinentes de profondeur et de textures qui interviennent dans la construction du vecteur

caractéristique. La seconde étape correspond à la réduction du maillage à partir des nouvelles

informations déterminées à partir des résultats de l’étape précédente. Notre réduction s’appuie

sur les données initiales du modèle et sur deux nouvelles images créées à l’aide de l’analyse

multirésolution, technique présentée dans le chapitre 3 :

• image de pertinence géométrique et

• image de pertinence des textures.

La Figure 4. 6 représente le schéma de notre algorithme de simplification construit sur deux

processus : la caractérisation et la simplification.

4.3.1.1 Création des nouvelles composantes

L’étape de description multi-échelle, effectuée sur les images qui servent à construire le

maillage, met en évidence les régions pertinentes. Afin de simplifier les zones qui ne font pas

parties de ces régions, nous proposons d’ajouter deux nouvelles composantes au vecteur

caractéristique utilisé pour la réduction. Ces nouvelles composantes appelées pertinence

géométrique et pertinence des textures sont déterminées à l’aide de l’analyse multirésolution.


97

Simplification

Modèle final

• Poids relatifsdes différentescomposantes• Facteur deréduction

Image de profondeur Images de textures

Modèle initialsous forme 3D

Réduction des points et desfacettes non pertinentes

DonnéesUtilisateur

Image pertinence textures

Image pertinencegéométrique

• Filtres depertinenceappliqués auxéchelles

Construction d’images de détailspour toutes les résolutions

Localisation des informationspertinentes

Filtrage et fusion desimages

Caractérisation

Figure 4. 6 : Schéma regroupant les étapes qui interviennent au cours de la simplification des modèles

construits à partir d’une image de profondeur et des textures


98

A chaque résolution, une image de détails est reconstruite, puis segmentée avec la méthode de

seuillage de Wen. Cette opération est effectuée directement sur l’image de profondeur et sur

les textures choisies par l’utilisateur. Dans le cas de textures en couleur, les trois composantes

rouge, vert et bleu sont séparées et elles forment trois nouvelles textures codées sur 256

niveaux.

A partir du jeu d’images binaires obtenu lors de la première phase d’analyse, la seconde

partie de notre traitement construit les deux images de pertinence géométrie et texture. Les

images binaires correspondant à l’image de profondeur interviennent pour l’élaboration de

l’image pertinence géométrique et les autres pour l’image pertinence texture. Le processus de

création des deux images de pertinence dans les deux cas reste le même : l’image pertinence

est le résultat d’un filtrage des images binaires. Le type de filtrage est déterminé en fonction

du type de détails que l’utilisateur désire conserver. La Figure 4. 7 présente un exemple de

fusion des images de détails à de multiples résolutions avec des poids définis pour chaque

résolution. Dans le premier exemple, le filtrage est de type passe haut : le choix porte sur la

conservation des détails de haute fréquence (image (f)). Dans le second exemple, nous

effectuons un filtrage de type passe bas pour privilégier les images binaires des niveaux de

résolution plus basse : le choix porte sur la conservation des détails de basse fréquence (image

(g)).

Les valeurs des deux nouvelles composantes du vecteur caractéristique sont attribuées à

partir de ces deux images de pertinence géométrique et de texture. Elles représentent les

valeurs des niveaux de gris des coordonnées de textures correspondant au sommet.


99

(b) (c) (e)(a)

(g)(f)

(d)

Figure 4. 7 : (a)image de profondeur (MNT région Dijon (France)), image segmentée des détails des résolutions

(b) niveau 1, (c) niveau 2, (d) niveau 3, (e) niveau 4, fusion des images détail à l’aide d’un filtrage des échelles;

l’image (f) a été construite avec les coefficients de filtres suivants respectivement de (b) à (e) 1, 1, 0.2 et 0.2,et

pour l’image (g) les coefficients du filtre des échelles suivants 0.2, 0.2, 1 et 1

4.3.1.2 Réduction

La création du vecteur caractéristique est obtenue à l’aide des deux images pertinences. A un

point de l’image correspondant à un sommet du maillage, le calcul de la composante

pertinence du vecteur s’effectue à partir des valeurs des pixels des images de pertinence. Les

autres composantes du vecteur sont la position et la normale, valeurs calculées directement

sur le maillage initial. Les composantes du vecteur définies en chaque sommet du maillage

deviennent les suivantes :

• géométrie,

• normale,

• « pertinence » déterminée à partir de l’image de profondeur et

• « pertinence » déterminée à partir des textures.


100

Il est à noter que les informations sur la courbure du modèle sont fournies par l’image de

pertinence géométrique ce qui n’est pas le cas dans la méthode utilisée par Gourley.

Le calcul de la longueur des arêtes est modifié pour limiter le nombre de contraction

d’arêtes à l’intérieur des zones de détails dits pertinents bien que la longueur, dans l’espace à

une dimension, indiquant la présence d’un détail est nulle. Nous rajoutons alors un poids

global wd non nul qui s’applique seulement dans le cas où au moins un des deux sommets

d’une arête est repéré comme détail pertinent :

( )( )

. si et / ou est un sommet pertinent ,

dans les autres cas.

ij d i j

ij i j

L w w v v i j

L w v v

= −

= −

� � �

� � �

(4.2)

Le paramètre wd permet de régler le taux de simplification à l’intérieur des zones de détail.

Dans certains exemples que nous présentons dans ce manuscrit la valeur de wd est très élevée

pour que la simplification dans ces zones pertinentes ne puisse s’effectuer qu’après avoir

réduit les sommets des régions non pertinentes.

Le vecteur caractéristique dispose donc de 4 composantes liées à la géométrie du modèle

et d’une composante liée aux textures. La simplification se déroule avec ce nouveau type de

vecteur selon le processus décrit dans la section 4.2. Les zones géométriques qui ne

supportent pas d’informations sont réduites en premier. La réduction est ainsi pilotée par les

nouvelles composantes pertinence issues de l’analyse multirésolution. Le schéma de la Figure

4. 6 résume toutes les étapes qui interviennent lors de la simplification.

4.3.2 INTERACTION AVEC L’UTILISATEUR

Les processus de caractérisation multirésolution et de simplification sont entièrement

automatisés. Les paramètres qui interviennent lors de l’exécution de l’algorithme d’analyse et

de réduction sont définis par l’utilisateur en fonction des propriétés du modèle qu’il désire

conserver.


101

L’utilisateur agit au cours de l’analyse pour déterminer le nombre d’échelles à explorer et

pour définir l’importance de ces échelles les unes par rapport aux autres lors de la création des

images de pertinence géométrique et texture. Il peut sélectionner les fréquences des détails

géométriques qu’il souhaite conserver, mais aussi les fréquences des détails des textures.

Dans la phase de réduction, l’utilisateur fixe la valeur de l’impact des composantes à l’aide de

poids, lors du calcul des distances. Il règle ainsi l’importance des images pertinentes dans la

simplification par rapport aux propriétés spatiales (position, normale,…). Les actions de

l’utilisateur lors du déroulement de la réduction sont résumées sur la Figure 4. 6.

Un premier exemple illustrant les étapes de notre algorithme est représenté sur la Figure 4.

8. Il s’agit de la réduction d’une surface d’un fossile : l’ammonite. L’image (a) représente

l’image de profondeur. La construction du modèle initial représente un total de 65K sommets.

Les images (b), (c) et (d) sont les images de détail à des résolutions plus basses et permettent

l’établissement de l’image de pertinence géométrique (f). Le choix du filtre de sélection dans

cet exemple est de type passe haut (e), afin de mettre en valeur les aspérités du fossile. Le

taux de réduction du nombre de sommet du modèle initial est de 95%. Le nombre de points

n’est alors plus que de 1,3K. Deux simplifications ont été effectuées : la première (figure (g))

utilise les composantes de Gourley, la seconde (figure (h)) utilise pour composantes la

géométrie, la normale et la pertinence géométrique. La comparaison visuelle de ces deux

modèles nous permet de constater que le deuxième modèle (figure (h)) conserve localement la

géométrie des aspérités.


102

(a) (b)

(c) (d)

(e) (f)

(g) (h)

Figure 4. 8 : (a) Image de profondeur d’une surface d’ammonite, (b), (c) et (d) images de détail des niveaux de

résolution respectivement 2 échelles plus basse que la résolution initiale, 3 échelles et 4 échelles, (e) filtre de

sélection des poids des images de détail segmentées, (f) image de pertinence géométrique résultante, maillage

réduit 1300 sommets (facteur de réduction : 98%) en utilisant les composantes (g) de Gourley et (h) géométrie,

normale et pertinence géométrique


103

(a (b

(c (d

Erreur0.0%

1.0%

0.01%

0.1%

Figure 4. 9 : (a) Modèle 3D réduit à 99% (660 sommets, 1300 facettes) avec la composante pertinence, (b)

report de l’erreur sur le modèle initial (vert : erreur la plus grande, bleu : erreur la plus faible), (c) modèle 3D

réduit à 99 % sans la composante pertinence, (d) report de l’erreur sur le modèle initial

Les prises de vues de la Figure 4. 9 représentent les modèles simplifiés à 99% et le report

de l’erreur, déterminée à partir de l’algorithme Metro, sur le modèle initial. La composante

pertinence permet de garder les points qui ont été sélectionnés pendant l’étape d’analyse. La

conservation de ces points pour des taux de réduction élevés entraîne l’élimination d’autres

points et de facettes. Dans le cas de l’ammonite, les points des parties lisses qui se situent près

des bords sont éliminés en premier impliquant des taux d’erreurs élevés près des bords. En

revanche, au niveau local, les erreurs sur les stries restent faibles, puisqu’un petit nombre de

facettes a évolué dans ces régions.

Un zoom est effectué sur une partie de l’ammonite afin de déterminer localement les

erreurs introduites par la simplification. Deux exemples de mesures sont présentés sur la

Figure 4. 10. L’image (a) représente l’erreur calculée après une réduction sans l’image de

pertinence de 50%. Cette erreur est visualisée sur le maillage initial. L’image (b) présente de

la même façon l’erreur déterminée dans le cas d’une simplification avec l’image de pertinence

géométrique. Notre méthode a permis de conserver la forme des stries : l’erreur est plus faible

dans le second cas au niveau des stries.


104

Erreur0.0%

1.0%

0.01%

0.1%

(a)

(b)

Figure 4. 10 : (a) Prise de vue effectué sur le zoom du maillage initiale de l’ammonite avec plaqué dessus

l’image en noir et blanc de l’erreur mesurée pour une réduction de 5O% dans le cas où l’image de pertinence

n’est pas utilisée, (b) prise de vue avec les mêmes paramètres que ceux de l’image (a) dans le cas où la

simplification fait intervenir l’image de pertinence

Nous pouvons conclure d’après cet exemple que la simplification sans la composante

pertinence, va réduire le niveau global de l’erreur au cours de la réduction. En revanche, elle

entraînera un taux d’erreurs locales plus important. Notre algorithme permet de conserver

localement la géométrie ou les informations pertinentes, sélectionnées par l’expert.


105

Le second exemple de la Figure 4. 11 révèle les différences de réduction occasionnées par

plusieurs types de filtrage lors de la formation de l’image de pertinence. La réduction porte

sur un modèle (b) contenant 16384 points et construit à partir d’une image de profondeur

128 128× (image (a)). L’image (c) représente les images segmentées de localisation des

détails pour 6 niveaux de résolution. Nous rappelons que le niveau 6 représente l’échelle la

plus fine et le niveau 0 l’échelle la plus grossière. Les images de pertinence géométrique (g),

(h) et (i) sont construites en prenant des valeurs de poids correspondant aux graphiques

respectifs (d), (e) et (f). Cette phase s’apparente à un filtrage dans le choix des localisations de

fréquences : (d) correspond à un filtrage passe bas, (e) à un filtrage passe bande et (f) à un

filtrage passe haut. Les modèles simplifiés d’un facteur de réduction de 75% à l’aide des

composantes géométriques ( , , )x y z et de la composante pertinence géométrique

correspondante sont représentés à l’aide d’une vue en perspective sur les images (i), (j) et (k).

Dans cet exemple, le filtre le mieux adapté pour un rapport de réduction de 75% est le filtre

passe haut car le modèle comporte de nombreuses arêtes et flanc droit (maillage (m)). Si

l’utilisateur désire atteindre des niveaux de réduction plus importants, il doit dans ce cas

utiliser un filtre passe haut. En effet, la réduction du modèle, pour un taux supérieur à 75%, à

l’aide d’une image pertinence définie à partir d’un filtre passe bande ou passe bas conduit

dans cet exemple à un modèle simplifié qui ne représente plus rien.

Le graphique de la Figure 4. 12 permet de confirmer l’impression visuelle sur le jugement

des résultats de la simplification. L’algorithme Metro va nous permettre de comparer les

erreurs lors des réductions en fonction du type de filtrage utilisé. La Figure 4. 12 représente

les résultats de cette mesure d’erreur. Lorsque ce modèle est constitué de 4650 facettes, soit

un taux de réduction de 86%, les meilleurs résultats sont obtenus avec le filtre passe haut.


106

(a) (b)

(c)

(d) (e) (f)

(g) (h) (i)

(j) (k) (l)

(m) (n) (o)

Figure 4. 11 : (a) Image de profondeur initiale (128×128), (b) modèle correspondant 16384 points (vue

perspective),(c) images de détail (de gauche à droite échelle 6 à 1), (g), (h) (i) images de pertinence créées en

prenant pour valeurs les poids respectifs de (d) passe haut, (e) passe bande et (f) passe bas, (j) (k) et (l) modèles

3D simplifiés 4180 points en utilisant les images de pertinence (d), (e) et (f), maillages simplifiés correspondants

(8000 facettes) (m) (n) et (o)


107

Nombre de triangle

Erreurmoyenne

Erreur locale moyenne

Figure 4. 12 : Comparaison des erreurs de réduction en fonction du type de filtrage appliqués aux images de

détail binaires

La Figure 4. 13 montre un exemple de comparaison d’un MNT réduit selon l’image

pertinence géométrique, dans un premier temps, et ensuite selon l’image pertinence de

texture. La texture (image (b)) représente des informations du satellite Landsat, bande 2, 3 et

4 qui sont des informations géologiques. Dans le premier cas, la texture est privilégiée au

détriment des informations de pertinence géométrique (image (c)). Le second exemple montre

un choix opposé où l’information de géométrie est privilégiée (image (d)).

Les coordonnées des textures des images de texture sont mises à jour lors de chaque

élimination d’arête. Garland montre dans [Gar98] que l’élimination d’une arête sans mettre à

jour les coordonnées de texture conduit à des erreurs. Notre algorithme utilise un schéma

d’interpolation classique pour mettre à jour les coordonnées des textures lors de l’élimination

des arêtes.


108

a)

c) d)

e) f)

b)

Figure 4. 13 : Simplification d’un modèle MNT, (a) image de profondeur (16K points), (b) image de texture

512 256× , (c) simplification du modèle d’après les informations de texture, (e) son maillage réduit (facteur de

réduction est de 75%), taille 124 Kb, (d) simplification du modèle d’après les informations géométriques, (f) son

maillage réduit (facteur de réduction 75%), taille 124 Kb

Nous avons appliqué l’algorithme Metro sur le MNT canoncity dans le but de tester les

performances de notre algorithme sur la simplification. La comparaison ne porte que sur la

réduction des données avec l’image de pertinence géométrique. Dans un premier temps le

MNT est réduit selon l’algorithme de Gourley avec un vecteur composante formé des

paramètres géométriques suivant : x, y, z, normale, courbure, type et avec un choix de poids

identique pour tous les paramètres. Ensuite le MNT est réduit avec un vecteur composante

possédant le paramètre pertinence géométrique en plus, déterminé à l’aide de l’image

pertinence géométrique. Nous avons procédé à trois type de réduction, la première à partir de

l’image pertinence construite à l’aide d’un filtre passe haut, la seconde avec un filtre passe

bande et enfin la dernière avec un filtre passe bas.


109

Canoncity erreur moyenne

Caractéristique:arête et géométriepasse hautpasse bandepasse bas

Nombre de sommet

Erreurmoyenne

Figure 4. 14 : Etude de l’erreur moyenne lors de la simplification du modèle canoncity

Les résultats apparaissent sur la Figure 4. 14. Dans cet exemple l’erreur moyenne sur la

simplification est plus faible dans le cas d’une utilisation de l’image pertinence géométrique

quel que soit le filtre appliqué lors de la sélection des images de détail.

4.4 Conclusion

Nous avons décrit dans ce chapitre un algorithme de simplification d’objets numériques dans

un contexte multi-capteurs. Nous avons montré que notre algorithme permettait la réduction

du modèle en fonction de la modalité et de la résolution des détails que le spécialiste désire

conserver. Notre méthode de simplification est basée sur deux processus :

• la caractérisation multirésolution

• et la réduction des données ne contenant pas d’informations pertinentes.


110

Le premier processus permet la reconstruction d’images à l’échelle initiale des détails

contenus dans les résolutions inférieures des images de profondeur et des textures à l’aide de

la transformée en ondelette quinconce. Les zones d’information sont ensuite extraites de ces

images afin de créer une image qui localise les régions pertinentes pour chaque niveau

d’échelle et chaque modalité. L’expert choisit finalement le filtrage qu’il désire appliquer aux

échelles pour établir l’image pertinence des détails géométriques et l’image pertinence des

textures. Le deuxième processus de réduction fait intervenir les informations de pertinence

lors de la construction des vecteurs caractéristiques définis pour chaque sommet du maillage

initiale. Une distance est déterminée pour chaque arête construite à l’aide des vecteurs

caractéristiques des sommets appartenant à l’arête. La réduction d’une donnée correspond à la

fusion de l’arête possédant la distance la plus faible. L’utilisateur agit aussi sur ce processus

en indiquant les poids des composantes du vecteur caractéristique.

Nous avons montré que cette méthode permettait de conserver les informations locales au

niveau du maillage afin de préserver le modèle dans le contexte de son application lors de la

simplification des données. L’approche multirésolution mise en place, à l’aide d’un filtre de

sélection des échelles des images de détail, autorise la conservation de résolutions spécifiques.

Enfin, cet algorithme permet de ne pas altérer le support géométrique correspondant à de

l’information contenue dans les textures sélectionnées par l’utilisateur.

Dans le prochain chapitre, nous présentons des applications de notre algorithme qui sont

issues de deux secteurs d’activité : la géologie d’une part et la robotique d’autre part.

Chapitre 5 Application

111

Equation Section 5

Chapitre 5 : Application

5.1 Introduction

Les modèles numériques de scènes ou d’objets naturels sont utilisés de façon croissantes dans

de nombreux domaines. Par exemple les activités comme la Conception Assistée par

Ordinateur (CAO), l’étude de Système d’Information Géographique (SIG), la conception de

jeux vidéo ou d’effets spéciaux ont besoin d’une représentation très fidèle de la réalité. Le

choix des techniques de modélisation va dépendre de l’application. Dans les chapitres

précédents, nous avons présenté une méthode d’analyse et de simplification multi-échelles de

modèles numériques multi-modaux, afin de pouvoir les manipuler avec aisance tout en

gardant leurs propriétés. Les caractéristiques principales sont extraites grâce à l’analyse

multirésolution développée dans le chapitre 2 afin d’effectuer une simplification du modèle

numérique tout en gardant la « pertinence » de ses informations de géométrie ou de texture.

Dans ce chapitre, nous présentons deux exemples d’utilisation de notre algorithme, ils

concernent les domaines des sciences de la Terre et de la Robotique. Ces deux applications

montrent l’étendue des performances de notre algorithme dans l’analyse et la simplification

de modèles numériques.

Dans la première partie de ce chapitre, nous détaillons les applications de notre algorithme

sur des objets provenant des sciences de la Terre. Nous appliquons notre méthode à l’analyse

et à la simplification de coquillages et de MNT. La seconde partie concerne l’étude réalisée

pour une application en robotique : la caractérisation de sites (usine, bâtiment) en milieux

hostiles pour l’homme, notamment les sites nucléaires.


112

5.2 Application aux sciences de la Terre

Les sciences de la Terre couvrent de nombreux champs d’étude et nous nous limitons aux

problèmes rencontrés en géologie et plus particulièrement aux analyses des informations

contenues sur la surface de coquilles de bivalves et de MNT. L’étude de la construction d’un

modèle d’ammonite est aussi présentée dans cette partie.

5.2.1 CARACTERISATION DES STRIES DE CROISSANCES SUR DES COQUILLAGES

Dans ce paragraphe, nous décrivons le traitement des informations écologiques contenues sur

la surface extérieure d’un mollusque d’eau douce, « Anodonta cygnae LINNE ». La coquille

(provenant de la région de Langres et d'âge holocène) est composée principalement de calcite

(CaCO3). L’analyse porte plus particulièrement sur la caractérisation géométrique des stries

de croissance de la coquille, formées au cours de la minéralisation lors d’échanges entre les

composants organiques de l'organisme et le milieu aqueux. Une strie ou incrément est définie

comme une période de temps séparant deux unités de croissance majeure. La mesure des

incréments peut donc servir à déterminer l’influence des variations environnementales sur

l’évolution de la coquille. Une image de la surface coquillière est capturée à partir du système

3D d’acquisition du laboratoire Le2i. L’information qui doit être extraite est de type multi-

échelles ; la surface contient des variations géométriques de basse et de haute fréquences dues

aux périodicités variables des stries de croissance. En effet, ces variations dépendent des

conditions climatiques et environnementales.

La première étape de notre algorithme permet dans un premier temps l’analyse des images

de profondeur afin de caractériser les stries de croissance des coquilles. Le modèle initial

construit à partir de l’image de profondeur est ensuite simplifié tout en conservant les

positions des stries des échelles souhaitées.

5.2.1.1 Acquisition des images

Le capteur de profondeur du système d’acquisition 3D [Sca94], monté sur les trois axes de

translation, se déplace au dessus de la coquille pour déterminer une image de profondeur. Les

écarts entre les incréments sont très petits, de l’ordre de 100 µm. Afin d’effectuer ces mesures,

les incréments de balayage en x et en y du système d’acquisition sont fixés à 50 µm.


113

(a)

(b)

(c)

Figure 5. 1 : (a) Photographie d’une vue de la surface du mollusque d'eau douce Anondonta cygneae L. (le

rectangle représente la zone balayée par le scanner 3D), (b) image de profondeur correspondant à la zone

rectangulaire (taille 512 128× ) et (c) modèle 3D de l’image de profondeur à l’aide de facettes triangulaires,

65K sommets, 130K faces, représentation sous Open Inventor


114

Une photographie de la coquille est représentée sur la Figure 5. 1(a). La région de la

coquille, qui a été balayée par le système d’acquisition tridimensionnel, est marquée à l’aide

d’un rectangle sur la même photographie. Elle correspond à une région de 0.64 2.6cm cm× .

L’image de profondeur correspondant à la zone numérisée est reproduite sur la Figure 5. 1(b).

L’information de profondeur est codée selon les niveaux de gris avec le noir représentant

l’altitude la plus basse. L’image de profondeur de la coquille peut aussi être considérée

comme un modèle 3D à l’aide d’une représentation utilisant des facettes triangulaires. La

Figure 5. 1(c) illustre le modèle 3D de l’image de profondeur de la Figure 5. 1 (b).

5.2.1.2 Résultats de l’analyse multirésolution

Une strie de croissance sur la surface d'une coquille est caractérisée par une accumulation de

CaCO3 qui peut être décrite par deux valeurs : sa largeur et son épaisseur relative. Dans cette

étude le spécialiste s’intéresse uniquement à la géométrie des stries. La quantité de dépôt sur

chaque couche du coquillage dépend de l’horloge interne du bivalve et de son

environnement : température, composition chimique des fluides [Ros75] [Wad76]. C’est

pourquoi deux types d’information sont contenus dans la structure de la coquille: les facteurs

internes (taux de croissance et périodicité) et les facteurs externes (variations des conditions

environnements). La recherche de ces deux types d’information sur des organismes de

coquillages fossiles ou vivants est fondamentale pour les géologues qui essaient de

caractériser les changements des conditions au cours de l’histoire terrestre.

Les mesures sur les stries de croissance s’effectuent la plupart du temps manuellement en

les comptabilisant à l’aide d’un microscope. Les données obtenues sont dépendantes de l’écart

entre deux incréments mais ne prennent pas en compte la quantité de carbonate de calcium

déposée, c’est à dire l’amplitude entre un sommet et la dépression séparant deux incréments.

La distinction entre les générations multiples d’incréments se fait en regroupant les stries de

même amplitude. Une méthode utilisant une approche spectrale des enregistrements de

croissance fondée sur la transformée de Fourier et développée par Dolman [Dol75] a permis

de mettre en évidence les périodicités multiples des générations d’incréments qui peuvent être

semi-annuelles, mensuelles ou bimensuelles. Cette méthode ne donne cependant aucune

information sur la position des stries. L’application de notre algorithme va permettre la

détermination de ces informations (position, fréquence et échelle) grâce à la transformée en

ondelette.


115

Afin d’extraire les incréments de la surface de la coquille, l’analyse multirésolution

présentée dans le chapitre 3 est effectuée sur l’image de profondeur de la Figure 5. 1 (b). Les

stries étant de tailles et de périodicités multiples, seule la reconstruction des images de détail

de chaque résolution à l’échelle initiale nous renseigne sur l’existence, la position et la

fréquence des incréments. Les images de détail sont construites en effectuant une

décomposition suivie d’une reconstruction, en annulant les coefficients d’approximation du

niveau exploré et les coefficients de détail des niveaux supérieurs. La Figure 5. 2 illustre ce

procédé.

(a) (b)

Figure 5. 2 : (a) Décomposition sur deux niveaux, (b) reconstruction avec mise à zéro des coefficients

d’approximation du niveau exploré et de détail du niveau supérieur (pixels noirs)

L’algorithme de reconstruction des détails est appliqué sur l’image de profondeur du

coquillage. Les résultats représentés sur la Figure 5. 3 correspondent aux échelles explorées

des niveaux 2 à 8. Ils ont été obtenus à l’aide d’une transformée quinconce utilisant les filtres

non-séparables, les pseudocoiflets, construits dans le chapitre 3.


116

(a) (b)

(c) (d)

(e) (f)

(g) (h)

Figure 5. 3 : (a) Image de profondeur initiale, images de détail reconstruites (b) sur de 2 niveaux, (c) sur 3

niveaux, (d) sur 4 niveaux, (e) sur 5 niveaux, (f) sur 6 niveaux, (g) sur 7 niveaux et (h) sur 8 niveaux

Ces résultats mettent en évidence les tailles et les positions des stries de croissance.

L’approche multirésolution permet de connaître les générations auxquelles appartiennent les

incréments. Ce classement est fonction de la taille et de l’amplitude des incréments calculés à

partir des images de détail reconstruites. En effet, l’annulation des coefficients

d’approximation pendant la phase de synthèse permet l’élimination de la courbure générale de

la coquille. A partir de l’image de détail, nous mesurons la distance entre les pics ou creux de

même amplitude, crête à crête pour en déduire les valeurs des incréments. La Figure 5. 4

montre l’image de profondeur et deux images de détail reconstruites sur lesquelles une coupe

horizontale a été effectuée. Les coupes montrent en effet que la courbure de la coquille (image

(a)) a disparu (image (b) et (c)) et qu’il ne reste que les pics ou creux générés par les

incréments.

Le calcul des largeurs entre les stries sur l’ensemble des images de détails a permis de

mettre en évidence quatre catégories d’incréments qui apparaissent en moyenne tous les 4,2

mm, 2.8 mm, 800 mµ et 350 mµ [Tou99b]. Les variations, en valeur absolue, des amplitudes

des stries de croissance n’ont pas encore été étudiées.


117

2

05 0

1 0 01 5 02 0 02 5 0

1 5 0 9P o sit io n ( p ix e l)

Gr a y sc a leNiveau de gris

(a)

(b)

(c)

Figure 5. 4 : Coupe horizontale sur (a) image de profondeur, (b) image de détail décomposée sur 2 échelles et

(c) image de détail décomposée sur 4 échelles


118

5.2.1.3 Visualisation

La seconde partie de l’application de notre algorithme sur les acquisitions tridimensionnelles

du coquillage concerne la simplification. L’objectif est d’obtenir un modèle simplifié sans

perdre les informations sur la catégorie d’incréments sélectionnée par le spécialiste. Cette

simplification doit lui permettre de manipuler dans un environnement 3D des modèles de

coquilles de grandes dimensions et lui permettre de faire des mesures d’incréments.

La Figure 5. 5 résume le processus de simplification dans le cas d’analyse de coquilles.

Dans cet exemple, l’utilisateur désire conserver les détails contenus à l’échelle correspondant

à quatre décompositions. Le filtrage des images de détail est très sélectif car une seule

résolution est choisie : le quatrième niveau de décomposition. L’image binaire de pertinence

géométrique est obtenue après un seuillage de Wen. Les images (d) et (e) permettent de

comparer l’impact de la réduction sur le modèle initial et de repérer les régions qui ont subi

des modifications.

Notre algorithme appliqué à l’étude des coquillages qui contiennent des informations à

plusieurs résolutions est un nouvel outil pour les géologues. Il leur permet de caractériser leur

échantillons et d’avoir une représentation visuelle de ces résultats. Il permet d’envisager aussi

une numérisation avec une extrême précision des coquillages de très grandes tailles puisque

les informations pertinentes seront préservées.


119

(a)

(b)

(c)

Maillage initial plustexture “pertinence

géométrique”130K Facettes

Maillage simplifié plustexture”pertinence

géométrique30K Faces

zoom

(d) (e)

Figure 5. 5 : (a) Image de profondeur initiale, (b) image des détails du niveau 4, (c) image pertinence

géométrique, (d) modèle du maillage avec l’image pertinence en texture (régions à conserver sont représentées

en foncé) et (e) modèle après simplification, les régions ne correspondant pas à de l’information pertinente sont

réduites


120

5.2.2 CONSTRUCTION D’UN MODELE NUMERIQUE A PARTIR D’UN FOSSILE : L’AMMONITE

Nous présentons dans cette partie un exemple simple de construction d’un modèle numérique

représentant un fossile d’ammonite.

5.2.2.1 Acquisition

La première étape consiste à acquérir les données géométriques de la topologie du fossile en

sélectionnant plusieurs prises de vue. L’objectif est de couvrir la totalité de la surface du

fossile. Nous travaillons à partir de deux images de profondeur. Elles vont servir à la

construction d’un modèle fermé. La Figure 5. 6 représente la position des deux points de vue

par rapport au fossile ainsi que les deux images de profondeur.

x

yz

Point de vue A

Image de profondeur A

Point de vue B

Image de profondeur B

Figure 5. 6 : Acquisition des données géométriques pour la construction d’un modèle d’ammonite


121

5.2.2.2 Analyse et simplification

La taille des images de profondeur est de 512 512× points. L’intégration des deux modèles

construits à partir de ces deux images de profondeur conduirait à un model contenant 88K

facettes. En effet, les deux modèles ont 22K points (6Mb) chacun. L’affichage d’un tel objet

n’est pas performant même à l’aide d’outils graphiques très puissants.

La simplification des modèles correspondant à chaque prise de vue permet en revanche

l’intégration des deux parties simplifiées et finalement un affichage plus performant du

modèle. L’algorithme de réduction présenté dans cette étude va permettre une réduction des

données sans perte les informations pertinentes sur la géométrie du modèle. Nous appliquons

l’algorithme de simplification sur les deux modèles calculés à partir des images de

profondeur.

Le premier processus de caractérisation nous permet d’analyser chaque image de

profondeur et d’extraire les informations de pertinence géométrique. La Figure 5. 7 (image (a)

et (b)) révèle les images de profondeur utilisées pour la construction du modèle d’ammonite.

Le filtre de sélection des échelles est choisie afin de ne privilégier que les détails provenant du

quatrième niveau de décomposition. Les images de détails sont représentées sur la Figure 5. 7

(image (c) et (d)). Les deux images de pertinence obtenues après le filtrage sont illustrées par

la Figure 5. 7 (image (e) et (f)). La simplification de chaque modèle, composant une des deux

parties du modèle final, est effectuée à partir de l’image de profondeur et du modèle 3D initial

non simplifié. Les résultats correspondant aux deux prises de vue sont donnés sur la Figure 5.

8. Le pourcentage de réduction est de 75%. La réduction des deux modèles de surface, qui

composent l’ammonite, conduit à deux modèles comportant 11K facettes et 5,5K sommets.

Comme nous pouvons le voir sur la Figure 5. 8, notre méthode a permis de conserver les

informations géométriques locales sur les deux faces de l’ammonite. Ces deux modèles

peuvent être utilisés pour construire le modèle qui contiendra 22K facettes.


122

(a)

(c) (d)

(e) (f)

(b)

Figure 5. 7 : Images de profondeur couvrant toute la surface du fossile (a) et (b), images de détail reconstruites

à partir du niveau 4 de la décomposition (c) et (d) et images de pertinence construites avec un filtre privilégiant

uniquement les détails provenant du niveau 4 d’exploration (e) et (f)


123

(a) (b)

Figure 5. 8 : Modèles simplifiés avec un taux de réduction de 75%, (a) maillage face 1 et (b) maillage face 2

5.2.3 ANALYSE DE MODELES NUMERIQUES DE TERRAIN

5.2.3.1 Analyse de l’information multi-composantes

L’étude des modèles numériques de terrain doit conduire à une représentation simplifiée du

modèle représentant les propriétés sélectionnées par l’utilisateur. En effet, l’imagerie

satellitaire produit, en plus des données géométriques du terrain, de nombreuses informations

sur les données géologiques de la zone étudiée.

Les images satellitaires produites par les satellites de type « Landsat » ou « Spot » sont

créées à partir des données spectrales du sol terrestre. Le satellite Landsat-5, par exemple,

fournit des données à l’aide de son capteur TM (Thematic Mapper) qui utilise sept détecteurs

sensibles à des bandes de longueurs d’onde allant du visible jusqu’à l’infrarouge thermique

qui indique la température de surface. L’analyse des mesures radiométriques acquises dans les

bandes spectrales permet à l’aide d’une palette de couleurs, déterminée pour une réponse

spécifique de longueur d’onde, de construire de nombreuses images.

Ces données s’ajoutent sous forme d’images de texture à l’information géométrique.

L’application de notre algorithme aux modèles numériques de terrain permet de caractériser

avec l’analyse multirésolution toutes les textures. La seconde étape conduit à la simplification

de la géométrie du modèle 3D en fonction des données de texture que le spécialiste souhaite

conserver.


124

Les données satellitaires de la région « Canoncity », Colorado, USA, permettent d’illustrer

l’application de notre algorithme sur un MNT. La Figure 5. 9 représente de bas en haut :

• le modèle sans sa texture,

• le modèle avec la texture construite à partir des bandes 4, 3 et 2 du satellite

Landsat codée sur les canaux R, G et B,

• le modèle avec la texture représentant l’intensité lumineuse,

• le modèle avec la texture construite à partir des bandes 7, 5 et 1 du satellite

Landsat codée sur les canaux R, G et B,

• le modèle avec la texture synthétique couleur.

L’image de profondeur et les images des textures sont tout d’abord analysées. L’utilisateur

sélectionne ensuite les filtres pour déterminer les images de pertinence dans le but d’obtenir

une vue simplifiée du modèle selon la nature de l’information qu’il souhaite conserver.

Les résultats sont regroupés sur la Figure 5. 10. Une réduction a été accomplie avec deux

textures différentes. Cette méthode permet de conserver le support géométrique correspondant

aux données des textures.

Figure 5. 9 : Modèle numérique de terrain avec de bas en haut : modèle sans sa texture, modèle avec la texture

représentant les bandes 4, 3 et 2 du satellite Landsat codées sur les canaux R, G, et B, modèle avec la texture

intensité lumineuse, modèle avec la texture représentant les bandes 7, 5 et 1 du satellite Landsat codées sur les

canaux R, G, et B, modèle avec la texture synthétique couleur


125

a)

c) d)

b)

Figure 5. 10 : Images de texture des données des bandes (a) 4, 3 et 2 et (b) 7, 5 et 1 du satellite Landsat,

simplification pour un taux de 75% (5K sommets, 9,5K facettes) en conservant les données (c) de couleur rouge

et (d) de couleur bleu-violet

5.3 Application à la robotique

5.3.1 CARACTERISATION DE SITES EN MILIEUX HOSTILES

5.3.1.1 Contexte

La création de modèles numériques provenant d’objets situés en milieux hostiles à l’homme

est généralement effectuée à l’aide de robots. Ces robots disposent d’une multitude de

capteurs pour extraire des informations variées sur le site à modéliser. Le département

d’énergie américain (DOE) a planifié la caractérisation d’anciens centres de recherche

nucléaire afin de recenser leurs contenus. Un robot supportant des capteurs géométrique,

thermique, couleur… sera envoyé sur le site afin de capturer des informations. Les données

acquises doivent permettre des représentations fidèles du milieux en fonction des propriétés

que l’utilisateur désire afficher pour prévoir précisément le scénario de démantèlement.


126

5.3.1.2 Caractérisation des sources multi-capteurs

Afin de nous situer dans un contexte industriel qui présente les mêmes fonctionnalités qu’un

site nucléaire, nous travaillons sur un échantillon de données acquises à partir d’une maquette

représentant une usine industrielle. Les données sont acquises à l’aide du Perceptron. Elles

proviennent du capteur géométrique et du signal d’intensité lumineuse retourné par le

Perceptron. La texture thermique est crée synthétiquement à partir de données thermiques

simulées. L’image de profondeur ainsi que les deux textures sont représentées sur la Figure 5.

11. Nous appliquons la première partie de notre algorithme pour extraire les images de

pertinence qui nous serviront lors de la simplification. Pour l’image de profondeur, comme

pour la texture, les filtres choisis lors de la sélection des échelles préservent les détails

correspondants aux décompositions sur 2, 3 et 4 niveaux. Pour la texture thermique le filtre

est de type passe bande en sélectionnant les échelles de décomposition 4, 5 et 6. Les résultats

pour ces exemples de détermination des images de pertinence sont illustrés sur la Figure 5. 12

pour l’image de profondeur, la Figure 5. 13 pour la texture intensité et la Figure 5. 14 pour la

texture thermique.

(a) (b) (c)

Figure 5. 11 : (a) Image de profondeur, (b) texture intensité et (c) texture thermique


127

a) b)

c) d)

Figure 5. 12 : (a) Image de profondeur 256 256× , (b) image de profondeur reconstruite à l’échelle initiale en

gardant les détails du 2ième niveau, (c) du 3ième niveaux et (d) du 4ième niveaux de décomposition

a) b)

c) d)

Figure 5. 13 : (a) Texture intensité 256 256× , (b) image reconstruite à l’échelle initiale en gardant les détails

du 2ième niveau, (c) du 3ième niveaux et (d) du 4ième niveaux de décomposition


128

a) b)

c) d)

Figure 5. 14 : (a) Texture thermique 256 256× , (b) image reconstruite à l’échelle initiale en gardant les

détails du 2ième niveau, (c) du 3ième niveaux et (d) du 4ième niveaux de décomposition

5.3.2 VISUALISATION

5.3.2.1 Objectifs

L’objectif de l’étude est la création d’un modèle numérique qui puisse permettre à l’utilisateur

ou au robot de situer les régions ou surfaces d’intérêt du modèle. Le contexte de l’application

dans le choix des informations à sélectionner est déterminant en vue de la création du modèle

final. En effet, la simplification des données doit conduire à la simplification des régions ne

contenant pas d’informations dites pertinentes.

5.3.2.2 Simplification

Nous présentons plusieurs exemples de simplification. Le premier privilégie la conservation

des informations géométriques et de l’intensité lumineuse. Les images de pertinence

géométrique et d’intensité sont prises en compte par l’algorithme de simplification. Deux

réductions sont effectuées avec des taux de 50% et 75%. Les résultats sont représentés sur la

Figure 5. 15. Dans les deux cas la structure géométrique avec sa texture ainsi que le maillage

filaire sont illustrés.


129

Dans le second exemple, nous présentons l’intérêt de notre méthode pour conserver les

régions d’intérêt issues d’un capteur intensité. La Figure 5. 16 illustre la simplification du

modèle effectuée cette fois-ci en utilisant les informations provenant de la texture thermique.

L’image de pertinence déterminée précédemment à l’aide d’un filtre passe bande permet la

conservation des variations thermiques de fréquence moyenne.

a) b)

c) d)

Figure 5. 15 : (a) Modèle de la maquette d’usine, taux de simplification 50% (32K points, 66K facettes, maillage

plus texture intensité), (b) maillage correspondant, (c) modèle de la maquette d’usine, taux de simplification

75% (16K points,33K facettes, maillage plus texture intensité) et (d) maillage correspondant


130

a) b) c)

Figure 5. 16 : (a) Modèle de la maquette d’usine simplifié à un taux de 60% (25K points, 53K facettes) avec

Open Inventor (maillage plus texture intensité), (b) maillage correspondant et (c) modèle sans texture

5.4 Conclusion

Nous avons présenté dans ce chapitre des exemples illustrant l’application de notre algorithme

à la caractérisation et la simplification de modèles numériques. Les deux processus qui

composent notre méthode conduisent à la sélection des informations pertinentes et à la

simplification des données non essentielles à l’interprétation du modèle.

Notre algorithme a permis l’étude et l’analyse de surface de coquillage. Cette première

étape d’analyse a permis d’extraire des informations sur la géométrie des incréments afin de

définir de nouveaux cycles de croissance. La simplification des données a ensuite autorisé la

construction d’une partie de la surface sans perdre la géométrie des incréments.

La construction d’un MNT, à partir d’une importante quantité d’information fournies par

le satellite Landsat, est rendue possible à l’aide de la phase d’analyse. Le modèle est établi en

fonction des données extraites lors de la phase d’analyse.

Nous avons présenté un exemple de construction de modèle numérique à partir d’un

fossile. La simplification de chaque modèle avant leur fusion a permis la construction d’un

modèle final dont l’affichage est performant.

Dans le cadre de caractérisation de site en milieux hostiles, le traitement de données

provenant des capteurs permet l’affichage et la manipulation de plusieurs types de modèle

selon le contexte de l’application. L’étape d’analyse sélectionne les informations pertinentes

qui sont à conserver afin de réduire ensuite le nombre important des informations recueillies

par les capteurs.

Conclusion

131

Conclusion

La représentation numérique du monde réel connaît un essor très important depuis ces

dernières années. Les avancées technologiques dans ce domaine permettent d’acquérir des

informations de plus en plus précises et variées. Toutefois, l’augmentation du nombre et de la

qualité des capteurs utilisés par l’homme produisent des données qui nécessitent de nouveaux

modes de représentation. Le modèle numérique apparaît comme un ensemble de données

structurées pouvant s’adapter aux contraintes diverses et variées imposées par le contexte

applicatif.

Nos travaux interviennent lors de la construction du modèle numérique à partir des

données fournies par les capteurs et ce, avant l’étape d’intégration des images provenant de

prises de vues différentes. Un méthode de simplification a été développée afin de permettre la

construction de modèles numériques dans un contexte multi-capteurs en vue de leur utilisation

dans des environnements contraints. Cet algorithme de réduction autorise la construction du

modèle à partir d’une quantité importante de données et s’inscrit dans une démarche de

représentation dépendante de la résolution des détails. Notre méthode de réduction est établie

à partir de deux processus : la caractérisation et la simplification des données. La

caractérisation s’appuie sur un algorithme d’analyse multirésolution construit à partir de la

transformée en ondelette quinconce. Cette première phase permet l’extraction des

informations pertinentes contenues dans les multiples niveaux de résolution. Elle produit deux

images de pertinence, une pour la géométrie et une pour les autres types de données. La

simplification utilise les images de pertinence afin de réduire les données qui ne contiennent

pas d’informations pertinentes. Au cours de ces deux phases, l’utilisateur choisit, selon le

contexte applicatif, la nature des données et la résolution des détails des données qu’il

souhaite conserver.

Conclusion

132

Dans le chapitre 1, nous avons présenté les outils de base pour comprendre la construction

de modèles numériques dans un contexte multi-capteurs. Ces définitions ont permis

d’introduire le vocabulaire employé en imagerie 3D. La structure d’un modèle 3D a été

présentée afin d’établir les propriétés des modèles numériques utilisés dans la suite de l’étude.

Nous avons montré qu’un modèle était un maillage géométrique composé de facettes

supportant les informations provenant des autres capteurs.

Dans le chapitre 2, nous avons rappelé les propriétés des images de profondeur puis nous

avons détaillé les étapes de construction des modèles numériques comprenant : l’acquisition

des données, la mise en correspondance, l’intégration et la visualisation. Nous avons montré

que la quantité des données était souvent trop importante pour construire et afficher de

manière performante les modèles. Un nouveau schéma de construction a donc été présenté

faisant intervenir une étape de simplification qui permet de réduire les données sans perdre les

informations pertinentes caractérisant le modèle.

Dans le chapitre 3, nous avons proposé un algorithme unique d’analyse multirésolution

2D des images de profondeur et des textures qui permet la localisation des informations

pertinentes géométriques mais aussi celles provenant des autres capteurs. Une nouvelle

analyse non-séparable a été développée à l’aide de bases quinconces pour augmenter la

précision dans la localisation et la fréquence des détails à caractériser. Cet algorithme nous

permet d’établir des images de pertinence produisant la localisation de détails dont la nature et

la résolution est fonction du type d’application à laquelle le modèle est destiné.

L’algorithme complet de simplification géométrique a été détaillé dans le chapitre 4. Nous

avons étendu un processus de simplification par contraction des arêtes pour tenir compte des

informations provenant des images de pertinence. Les arêtes des régions pertinentes ne sont

pas simplifiées. Nous avons ensuite présenté comment l’utilisateur peut contrôler le processus

général de simplification. Il sélectionne le type et la résolution des données à conserver afin

de produire un modèle qui garde toute sa pertinence par rapport au contexte applicatif.

Conclusion

133

Dans le dernier chapitre, nous avons présenté des exemples d’application de notre

algorithme dans deux domaines d’activité : les sciences de la Terre et la robotique. Le premier

exemple provenant de l’étude de coquillages étudiés en paléontologie, a permis de mettre en

évidence des stries de croissance et de proposer une simplification des données conservant les

informations géométriques de chaque résolution d’incrément. Le deuxième exemple porte sur

la construction d’un modèle où notre algorithme intervient afin de réduire le nombre de

données avant la mise en correspondance et l’intégration. Puis, l’étude de MNT a montré des

exemples de simplifications où les informations sélectionnées provenaient de capteurs non

géométriques. En robotique, nous avons décrit une méthode de caractérisation de sites

nucléaires à l’aide de l’algorithme de simplification. Ces exemples montrent tout l’intérêt

d’un algorithme permettant la caractérisation et la simplification de modèles numériques dans

un contexte multi-capteurs.

L’algorithme de simplification permet de traiter et de simplifier les modèles comportant

des données de nature très variées. La contribution de notre méthode réside dans la prise en

compte des informations multi-capteurs au cours de la simplification des données

géométriques. L’étape de caractérisation a l’avantage d’utiliser une seule technique qui traite

à la fois les données géométriques et les textures. De plus, en traitant des images à deux

dimensions, l’analyse multirésolution permet d’exploiter toutes les propriétés de la

transformée en ondelette 2D. Nous avons développé de nouvelles bases quinconces pour

effectuer une analyse non-séparable. La transformée quinconce comparée à l’analyse

dyadique permet d’améliorer la finesse de l’analyse spatiale et fréquentielle. La réduction des

données, une fois les images de pertinence établies, est simple et rapide. Elle permet de

conserver les détails au niveau local quelques soient la nature et la résolution de ces détails.

La méthode de sélection du type et de la résolution des détails à conserver est effectuée à

l’aide de filtres numériques pour simplifier le processus de sélection des informations

pertinentes.

D’autres perspectives sont envisageables afin de prolonger cette étude.

Comme nous l’avons montré dans ce document, la localisation et l’extraction des détails

sont effectuées de manière plus précise grâce à l’utilisation de la transformée en ondelette

quinconce. Cependant, de récents travaux ont permis d’établir des analyses multirésolutions à

partir d’ondelettes rationnelles [Nic00]. Ces ondelettes permettent une sélection très fine de la

Conclusion

134

fréquence des détails à reconstruire car la résolution entre deux échelles est fixée par un

nombre rationnel. L’application de ces ondelettes aux images de profondeur et aux textures

améliorerait la caractérisation des images de pertinence.

L’algorithme que nous avons présenté est un procédé de simplification qui permet la

fusion des régions non pertinentes. Nous pourrions utiliser ce processus pour segmenter le

modèle numérique en sous-objets. Notre étape d’analyse nous permet de dégager les régions

d’intérêt. Le maillage serait ensuite scindé en plusieurs sous-objets en fonction des résultats

de la segmentation. La représentation du modèle serait alors définie par les sous-objets qui le

composent. Cette méthode pourrait être très efficace du fait de la prise en compte de toutes les

modalités.

Il n’existe aucune méthode de comparaison qui permettent d’établir le calcul des erreurs

de réduction lorsque celle-ci est contrôlée par une texture. Cette méthode nous aiderait à

obtenir une estimation des performances de notre algorithme dans le cas où l’utilisateur

privilégie les données de texture par rapport aux données de géométrie.

Une étude sur la relation entre les facteurs de réduction et le filtre appliqué aux images de

localisation des détails permettrait d’établir une représentation en fonction du niveau de détail

souhaité par l’utilisateur. Par exemple, il est peut être intéressant d’appliquer un filtrage passe

haut quand le facteur de réduction est faible et un filtrage passe bas quand celui-ci est élevé.

L’utilisateur n’aura plus qu’à choisir les composantes qu’il souhaite conserver dans le but de

construire un modèle numérique qui permet la sélection et la visualisation progressive des

niveaux de détail pour s’adapter aux contraintes de transmission, de réception et d’affichage.

Ce travail a fait l’objet de 4 publications dans des revues internationales (Optical

Engineering [Tou99b], Computers and Geosciences [Tou99c] et deux soumissions à

Autonomous Robbot [Tou00b] et au Journal International de la CFAO et de l’Infographie

[Tou00c]), de 5 communications à des congrès internationaux [Tou98], [Tou99a], [Tou99d],

[Tou00a], [Nic00] et d’une présentation au Groupe de Recherche OT 3-3.

Bibliographie

135

Bibliographie

[ALU98] D. Aluze, "Système de détection et de caractérisation de défauts d'aspect sur des

surfaces parfaitement spéculaires et non planes", Thèse de l'Université de Bourgogne, Le

Creusot, 1998.

[ANT92] M. Antonini, M. Barlaud, P. Mathieu, I. Daubechies, "Image coding using wavelet

transform", IEEE TRANS. ON IMAGE PROCESSING, Vol. 2, N° 1, pp. 205-220, 1992.

[BAT85] B. Batchelor, D. Hill, D. Hodgson, "Automated Visual Inspection", IFS

(Publications) Ltd, Holland, 1985.

[BES88] J. Besancon, "Vision par ordinateur en deux et trois dimensions", Eyrolles, 1988.

[BESL92] P. Besl, N. McKay, "A method for registration of 3D shapes", IEEE PAMI, Vol. 14,

N° 2, pp. 239-256, 1992.

[BLA95] G. Blais, M. Levine, "Registering multiview range data to create 3D computer

objects", IEEE PAMI, Vol. 17, N° 8, pp. 820-824, 1995.

[BOI84] J. Boissenat, "Geometric Structures for three-dimensional shape representation",

ACM TRANS. ON GRAPHICS, Vol. 3, N° 4, pp. 266-286, Octobre 1984.

[BON98] G. Bonneau, "Multiresolution analysis on irregular surface meshes", IEEE TRANS.

ON VISUALIZATION AND COMPUTER GRAPHICS, Vol. 4, N° 4, pp. 365-378, 1998.

Bibliographie

136

[BOU99] F. Boughorbal, D. Page, C. Dumont, M. A. Abidi, "Registration and integration of

multi-sensor data for photo-realistic scene reconstruction", 28TH WORKSHOP: 3D VISUALIZATION

FOR DATA EXPLORATION AND DECISION MAKING, Vol. 3905, pp 74-84, 1999.

[BUR83] P. Burt, E. Adelson, "Laplacien pyramid as a compact image code", IEEE TRANS.

COMMUN., Vol. 31, N° 4, pp. 532-540, 1983.

[CHA99] B. Chase, "Calibration of scanning laser range cameras with application for

machine vision", Master of Sciences thesis, The University of Tenessee, Iris lab, Knoxville,

Décembre 1999.

[CHU92] C. Chui, "An introduction to wavelets", Academic Press, San Diego, 1992.

[CIG96] P. Cignoni, C. Rocchini, R. Scopigno, "Metro: measuring error on simplified

surface", Technical Report, I.E.I.-C.N.R., Pisa, Italy, Janvier 1996.

[CIG98] P. Cignoni, C. Montani, R. Scopigno, "A comparison of mesh simplification

algorithms", COMPUTER & GRAPHICS, Vol. 22, N° 1, pp. 37-54, 1998.

[CLA95] J. Clark, G. Zhang, A. M. Wallace, "Image acquisition using fixed and variable

Triangulation", IEEE FIFTH INTER. CONF. ON IMAGE PROCESSING, pp. 539-543, Edinburg, Juillet

1995.

[COH92A] A. Cohen, "Ondelettes et traitement numérique du signal", Masson, Paris, 1992.

[COH92B] A. Cohen, I. Daubechies, J. Feauveau, "Biorthogonal bases of compactly

supported wavelets", COMM. PURE AND APPL. MATHEMATICS, Vol. 45, pp. 485-560, 1992.

[COH96] J. Cohen, A. Varshney, D. Manocha, G. Turk, H. Weber, P. Agarwal, F. Brooks,

W. Wright, "Simplification envelopes", SIGGRAPH'96 PROC, pp. 119-128, Août 1996.

[COL75] S. Collins, "Terrain parameters directly from digital terrain model", THE CANADIAN

SURVEYOR, Vol. 29, pp. 507-518, 1975.

Bibliographie

137

[COU97] C. Coulot, "Etude de l'éclairage de surfaces métalliques pour la vision artificielle:

application au contrôle dimensionnel", Thèse de l'Université de Bourgogne, Le Creusot, 1997.

[DAH94] S. Dahlke, W. Dahmen, E. Schmitt, I. Weinreich, "Multiresolution analysis and

wavelets on S2 and S3", Institut für Geometrie und angewandete Mathematik, RWTH

Aachen, 1994.

[DAU92] I. Daubechies, "Ten Lectures on Wavelets", SIAM, Philadelphia, 1992.

[DAU99] I. Daubechies, I. Guskov, W. Sweldens, P. Schroder, "Wavelets on irregular point

sets", CONSTR. APPROX., Vol. 15, pp. 381-426, 1999.

[DOL75] J. Dolman, "A technique for the extraction of environmental and geophysical

information from growth records in invertebrates and stromalites", GROWTH RHYTHMS AND THE

HISTORY OF EARTH 'S ROTATION, G. Rosenberg and S. Runcorn (Eds.), pp. 191-221, 1975.

[DON95] D. Donoho, "De-noising by soft-thresholding", IEEE TRANS. ON INFORMATION

THEORY, Vol. 41, N° 3, pp. 613-627, 1995.

[DOR94] O. H. Dorum, A. Hoover, J. P. Jones, "Calibration and control for range imaging in

mobile robot navigation", VISION INTERFACE 1994, pp. 25-32, Alberta, Canada, Mai 1994.

[ECK95] M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsberry, W. Stuelze,

"Multiresolution analysis of arbitrary meshes", SIGGRAPH'95 PROC, pp. 173-182, Août 1995.

[ELS98] M. D. Elstrom, P. W. Smith, and M. A. Abidi, "Stereo based registration of Ladar

and color imagery", SPIE INTELLIGENT ROBOTS AND COMPUTER VISION XVII: ALGORITHMS,

TECHNIQUES, AND ACTIVE VISION, Vol. 3522, pp. 343-354, Boston, 1998.

[FEA90] J. C. Feauveau, "Analyse multiresolution avec un facteur de resolution racine de

2", JOURNAL DE TRAITEMENT DU SIGNAL, Vol. 7, N° 2, pp. 117-128, 1990.

Bibliographie

138

[FIT93] A. Fitzgibbon, R. Fisher, E. Trucco, "Model acquisition from multiple range

views: a survey", Dept. Of Artificial Intelligence, University of Edinburgh, United Kingdom,

1993.

[FOL90] J. D. Foley, A. A Van Dam, S. Feiner, J. F. Hughes, "Computer Graphics:

Principles and Practice", Addison-Wesley Publishing Company, 1990.

[GAR97] M. Garland, P. Heckbert, "Surface simplification using quadric error metrics",

SIGGRAPH'97 PROC, pp. 209-216, 1997.

[GAR98] M. Garland, P. S. Heckbert, "Simplifying surfaces with color and texture using

quadric error metrics", IEEE VISUALIZATION PROC., pp. 263-269, Octobre 1998.

[GOD71] C. Godbillon, "Elément de topologie algébrique", Hermann, Paris, 1971.

[GOU98] C. Gourley, "Pattern vector based reduction of large multimodal data sets for fixed

rate interactivity during visualization of multiresolution models", Ph.D. thesis, The University

of Tenessee, Iris lab, Knoxville, 1998.

[GOU99] C. S. Gourley, C. Dumont, M. A. Abidi, "Pattern Vector Based Reduction of 3D

Meshes Created from Multimodal Data Sets", SPIE, AEROSENSE (AEROSPACE/DEFENSE SENSING,

SIMULATION AND CONTROLS), Vol. 3693, pp. 112-123, Orlando, Avril 1999.

[GUS99] I. Guskov, W. Sweldens, P. Schroder, "Multi-resolution processing for 3D

meshes", SIGGRAPH'99 PROC, pp. 325-334, 1999.

[HAE93] P. Haeberli, M. Segal, "Texture mapping as a fundamental drawing primitive",

SGI White Paper, Silicon Graphics, http://www.sgi.com, 1993.

[HE95] T. He, L. Hong, A. Kaufman, A. Varshney, S. Wang, "Voxel-based object

simplification", IEEE VISUALIZATION’95 PROC, pp. 296-303, 1995.

Bibliographie

139

[HEC97] P. S. Heckbert, M. Garland, "Survey of polygonal surface simplification

algorithms", SIGGRAPH'97 PROC, Course Notes CD-ROM, Course 25: Multiresolution Surface

Modeling, ACM SIGGRAPH, Août 1997.

[HOP92] H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, W. Stuetzle, "Surface

reconstruction from unorganized point", COMPUTER GRAPHICS, Vol. 26, N° 2, pp. 71-78, 1992.

[HOP96] H. Hoppe, "Progressive meshes", SIGGRAPH'96 PROC, pp. 99-108, Août 1996.

[JAE90] L. S. Jae, "Two dimensional signal and image processing", Englewood Cliff,

Prentice Hall, pp. 218-237, 1990.

[JAR83] R. A. Jarvis, "A perspective on range finding techniques for computer vision",

IEEE PAMI, Vol. 2, pp. 122-139, 1983.

[KAL91] A. Kalvin, C. Cutting, B. Haddad, M. Noz, "Constructing topologically connected

surfaces for the comprehensive analysis of 3D medical structures", SPIE MEDICAL IMAGING V:

IMAGE PROCESSING, Vol. 1445, pp. 247-258, Fevrier 1991.

[KIM99] Y. Kim, S. Valette, H. Jung, R. Prost, "Local wavelets decomposition for 3D

surfaces", ICIP 99, Vol. 4, pp. 357-360, 1999.

[LET80] P. Letts, G. Rochon, "Generation and use of digital elevation data for large area",

6TH CANADIAN SYMPOSIUM OF REMOTE SENSING, pp. 597-602, Halifax, 1980.

[LOR87] W. Lorensen, H. Cline, "Marching cubes: a high resolution 3D surface

construction algorithm", COMPUTER GRAPHICS, Vol. 21, pp. 163-169, 1987.

[LOO87] C. Loop, "Smooth subdivision surfaces based on triangles", Technical Report,

University of Utah, Department of Mathematics, 1987.

[LOU94] M. Lounsbery, "Multiresolution analysis for surface of arbitrary topological type",

Ph.D. thesis, University of Washington, USA, 1994.

Bibliographie

140

[MAE97] F. Maes, A. Collignon, D. Vandermeulen,G. Marchal, P. Suetens, "Multi-modality

image registration by maximization of mutual information", IEEE TRANS. ON MEDICAL IMAGING,

Vol. 16, N° 2, pp. 187-198, 1997.

[MAL89A] S. Mallat, "A theory for multiresolution signal decomposition of images and

wavelet models", IEEE PAMI, Vol. 11, N° 7, pp. 674-693, Juillet 1989.

[MAL89B] S. Mallat, "Multiresolution approximations and wavelet orthonormal bases of

L2(R)", IEEE TRANS. ON AM. MATHEMATIC SOCIETY, Vol. 315, N° 1, pp. 69-87, Septembre 1989.

[MAL92] S. Mallat, S. Zhong, "Characterization of signal from multiscale edges", IEEE

PAMI, Vol. 14, N° 7, pp. 710-732, Juillet 1992.

[MAL99] S. Mallat, "A wavelet tour of signal processing", Academic Press, San Diego,

1999.

[MCC73] J. McClellan, "The design of two dimensional filters by transformations", PROC.

7TH ANNUAL PRINCETON CONF. ON INFORMATION SCIENCES AND SYSTEMS, pp. 247-251, Princeton,

Mars 1973.

[MEY90] Y. Meyer, "Ondelettes et Opérateurs d'Ondelettes", Hermann, Paris, 1990.

[MOR89] M. Mortenson, "Computer Graphics: an introduction to the mathematics and

geometry", Industrial Press, 1989.

[NAY94] S. Nayar, Y. Nakagawa, "Shape from focus", IEEE PAMI, Vol. 16, N° 8, pp. 824-

831, 1994.

[NIC00] F. Nicolier, M. Toubin, A. Baussard, F. Truchetet, "Clam shell analysis using

rational wavelet analysis", VISION INTERFACE 2000, pp. 373-377, Montreal, Mai 2000.

[REI93] L. Reissell, "Wavelet mutliresolution representation of curves and surfaces",

Technical Report, University of British Columbia, Departement of Computer Science,

Canada, 1993.

Bibliographie

141

[RIO91] O. Rioul, M. Vetterli, "Wavelet and signal processing", IEEE SIGNAL PROC. MAG.,

pp. 1544-1576, 1991.

[ROS75] G. Rosenberg, "A comment on terminology: the increment and the series",

GROWTH RHYTHMS AND THE HISTORY OF EARTH 'S ROTATION, G. Rosenberg and S. Runcorn (Eds.),

pp.1-8, 1975.

[SCA94] 3D Scanners Ltd., South Bank Technopark, London, 1994.

[SCH92] W. Schröeder, J. Zarge, W. Lorensen, "Decimation of triangle meshes",

SIGGRAPH'92 PROC, Vol. 26, N° 2, pp. 65-70, Juillet 1992.

[SHA94] I. Shah, "Theory, design and structures for multidimensional filter banks and

application in coding of interlaced video", Ph.D. thesis, University of Colombia, USA, 1994.

[SOU95] M. Soucy, D. Laurendeau, "A general surface approach to the integration of a set

of range views", IEEE PAMI, Vol. 17, N° 4, pp. 344-358, Avril 1995.

[SPA81] E. H. Spanier, "Algebraic Topology", Springer-Verlag, NewYork, 1981.

[SUN00] Y. Sun, C. Dumont, M. A. Abidi, "Mesh-based integration of range and color

images", SPIE, AEROSENSE (AEROSPACE/DEFENSE SENSING, SIMULATION AND CONTROLS), Vol. 4051,

pp. 110-117, Orlando, Avril 2000.

[SWE94] W. Sweldens, "The lifting scheme: a custom design construction of biorthogonal

wavelets", Technical Report,University of South Carolina, Departement of Mathematics,

1994.

[SWE95] W. Sweldens, P. Schroder, "Spherical wavelets: efficiently representing function

on the sphere", SIGGRAPH'95 PROC, pp. 161-172, Août 1995.

Bibliographie

142

[TOU98] M. Toubin, C. Dumont, E. P. Verrechia, O. Laligant, A .Diou, F. Truchetet, M. A.

Abidi,, "A multi-scale analysis for the characterization of 3D objects", INTELLIGENT ROBOTS

AND COMPUTER VISION XVII: ALGORITHMS, TECHNIQUES, AND ACTIVE VISION, Vol. 3522, pp. 414-

423, Boston, Novembre 1998.

[TOU99A] M. Toubin, F. Truchetet, E. P. Verrecchia, C. Dumont, M. A. Abidi, "A 3D Multi-

resolution Description of Range Images through 2D Quincunx Wavelet Analysis", SPIE,

AEROSENSE (AEROSPACE/DEFENSE SENSING, SIMULATION AND CONTROLS), Vol. 3723, pp. 350-360,

Orlando, April 1999.

[TOU99B] M. Toubin, O. Laligant, A. Diou, F. Truchetet, E. P. Verrecchia, C. Dumont, M. A.

Abidi, "Multi-scale analysis of range image: its use for growth increment characterization",

OPTICAL ENGINEERING, Vol. 38, N° 12, pp. 2016-2021, Décembre 1999.

[TOU99C] M. Toubin, C. Dumont, E. P. Verrechia, O. Laligant, A. Diou, F. Truchetet, M. A.

Abidi,, "A Multi-scale Analysis of shell growth increments using wavelet transform",

COMPUTERS AND GEOSCIENCES, Vol. 25, pp. 877-885, 1999.

[TOU99D] M. Toubin, C. Dumont, F. Truchetet, M. A. Abidi, "Multi-resolution analysis of

3D multi-modal objects using a 2D quincunx wavelet analysis", INTELLIGENT ROBOTS AND

COMPUTER VISION XVIII: ALGORITHMS, TECHNIQUES, AND ACTIVE VISION, Septembre 1999.

[TOU00A] M. Toubin, D. Page, C. Dumont, F. Truchetet, M. Abidi, "Multiresolution Wavelet

Analysis for Simplification and Visualization of Multi-Textured Meshes", SPIE PHOTONICS

WEST ELECTRONIC IMAGING 2000, San Jose, California, Janvier 2000.

[TOU00B] M. Toubin, D. Page, C. Dumont, F. Truchetet, M. Abidi, "Simplification of multi-

sensory data sets in a scene building", AUTONOMOUS ROBOTS, Soumis Mars 2000.

[TOU00C] M. Toubin, C. Dumont, F. Truchetet, M. Abidi, "Construction de modèles

numériques de scènes naturelles par approche multirésolution", JOURNAL INTERNATIONAL DE LA

CFAO ET DE L’INFOGRAPHIE, Hermes, Soumis Octobre 2000.

[TRU98] F. Truchetet, "Ondelettes pour le signal numérique", Hermes, Paris, 1998.

Bibliographie

143

[TUR92] G. Turk, "Re-tiling polygonal surfaces", SIGGRAPH'92 PROC, Vol. 26, N° 2, pp. 55-

64, Juillet 1992.

[TUR94] G. Turk, M. Levoy, "Zippered polygon meshes from range images", SIGGRAPH'94

PROC, Vol. 2, pp. 311-318, Orlando, 1994.

[VAL99] S. Valette, Y. Kim, H. Jung, I. Magnin, R. Prost, "A multiresolution wavelet

scheme for irregularly subdivided 3D triangular mesh", ICIP 99, Vol.1, pp 171-174, 1999.

[VET92] M. Vetterli, J. Kovacevic, "Nonseparable multidimensional perfect reconstruction

filter banks and wavelet bases for Rn", IEEE TRANS. ON INFORMATION THEORY, Vol. 38, N° 2, pp.

533-555, Mars 1992.

[VEZ95] J. M. Vezien, "Techniques de reconstruction globale par analyses de paires

d'images stereoscopiques", Thèse de l'Université Paris VII, Paris, 1995.

[WAD76] K. Wada, T. Fujinuki, "Biomineralization in bivalve molluscs with emphasis on

the chemical composition of the extrapallial fluid", THE MECHANISMS OF MINERALIZATION IN

INVERTEBRATES AND PLANTS, pp. 175-190, Columbia, University of South Carolina Press 1976.

[WAT93] A. Watt, "3D Computer Graphics, 2nd Edition", Addison-Wesley Publishing

Company, 1993.

[WEN85] W. Tsai, "Moment-preserving thresholding: a new approach", COMPUTER VISION,

GRAPHICS, AND IMAGE PROCESSING, Vol. 29, pp. 377-393, 1985.

[WER94] J. Wernecke, "The Inventor Mentor, Programming Object Oriented 3D Graphics

with Open Inventor", Addison-Wesley Publishing Company, Massachusetts, 1994.

[WON98] L. Wong, C. Dumont, M. A. Abidi, "An algorithm for finding the next best view in

object reconstruction", SPIE INTELLIGENT ROBOTS AND COMPUTER VISION XVII: ALGORITHMS,

TECHNIQUES, AND ACTIVE VISION, Vol. 3523, pp. 191-200, Boston, Novembre 1998.

Bibliographie

144

[WOO78] R. Woodham, "Photometric stereo: a reflectance map technique for determining

surface orientation from image intensity", SPIE IMAGE UNDERSTANDING SYSTEMS AND INDUSTRIAL

APPLICATIONS, Vol. 155, pp. 136-143, 1978.

[ZOR97] D. Zorin, P. Schröder, W. Sweldens, "Interactive multiresolution mesh editing",

SIGGRAPH'97 PROC, pp. 259-268, 1997.

Documents

THESE...deux images de pertinence : la première pour les données géométriques et la seconde pour les données des autres capteurs. Le processus de réduction des données fait