Thèse de doctorat Ondelettes et problèmes mal posés : la ...

Thèse de doctorat Ondelettes et problèmes mal posés : la ...

Français
251 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Thèse de doctorat
Ondelettes et problèmes mal posés : la mesure
du flot optique et l’interpolation irrégulière
Christophe BERNARD
Version finale ii T
E
E
R R M S
Je tiens tout d’abord a exprimer ma profonde reconnaissance pour mon directeur de
these Stephane Mallat, qui a consacre a l’encadrement de ma these un temps et une
disponibilite d’esprit considerables, auxquels j’ai ete d’autant plus sensible que son emploi
du temps est tres charge. J’ai ainsi largement pu pro ter de sa grande acu te scienti que et
de son enthousiasme indefectible et communicatif pour le travail de ses etudiants. Je lui suis
donc redevable d’avoir pu faire une these dans des conditions exceptionnelles.
Je remercie egalement Jean-Jacques Slotine, qui m’a accompagne tout au long de ce
travail de these, au cours de longues et fructueuses discussions a Paris ou a Boston, ou il
m’a re cu de nombreuses fois.
Je tiens a remercier Albert Benveniste, Patrick Bouthemy et Ronald DeVore d’avoir
accepte la t^ache ingrate de lire ma these et d’ecrire un rapport. Albert Cohen a tres t^ot
manifeste un grand inter^et pour l’ensemble de ma these, et a pris la peine de la lire en detail
et de me faire part de ses commentaires. Je lui en suis tres reconnaissant. Jean Serra a
egalement montre son inter^et pour les divers volets de mon travail et m’a donne l’occasion
de le presenter au centre de morphologie mathematique, dont il est le fondateur.
Je remercie en n Patrick Bouthemy, Ronald DeVore et Ingrid Daubechies de ...

Sujets

Informations

Publié par
Nombre de lectures 352
Langue Français
Poids de l'ouvrage 2 Mo
Signaler un problème
Thèse de doctorat Ondelettes et problèmes mal posés : la mesure du flot optique et l’interpolation irrégulière Christophe BERNARD Version finale ii T E E R R M S Je tiens tout d’abord a exprimer ma profonde reconnaissance pour mon directeur de these Stephane Mallat, qui a consacre a l’encadrement de ma these un temps et une disponibilite d’esprit considerables, auxquels j’ai ete d’autant plus sensible que son emploi du temps est tres charge. J’ai ainsi largement pu pro ter de sa grande acu te scienti que et de son enthousiasme indefectible et communicatif pour le travail de ses etudiants. Je lui suis donc redevable d’avoir pu faire une these dans des conditions exceptionnelles. Je remercie egalement Jean-Jacques Slotine, qui m’a accompagne tout au long de ce travail de these, au cours de longues et fructueuses discussions a Paris ou a Boston, ou il m’a re cu de nombreuses fois. Je tiens a remercier Albert Benveniste, Patrick Bouthemy et Ronald DeVore d’avoir accepte la t^ache ingrate de lire ma these et d’ecrire un rapport. Albert Cohen a tres t^ot manifeste un grand inter^et pour l’ensemble de ma these, et a pris la peine de la lire en detail et de me faire part de ses commentaires. Je lui en suis tres reconnaissant. Jean Serra a egalement montre son inter^et pour les divers volets de mon travail et m’a donne l’occasion de le presenter au centre de morphologie mathematique, dont il est le fondateur. Je remercie en n Patrick Bouthemy, Ronald DeVore et Ingrid Daubechies de m’avoir donne l’occasion de presenter mon travail a di erents seminaires qu’ils organisent. J’ai eu la chance de faire ma these au CMAP, un centre de recherches accueillant et vivant, ou regne une ambiance conviviale et dynamique. Parmi les artisans de ce bel equilibre, je dois d’abord citer Geo Boleat, d’un abord bourru, mais qui a un c ur d’or, ainsi que Jeanne Bailleul, toujours gaie, active et ardente defenseuse de la veuve et de l’orphelin. Je dois egalement parler de Liliane Doare, pilier du CMAP et de Nathalie Limonta, une nouvelle recrue. Je remercie Jean-Claude Nedelec, directeur au long cours du centre, qui gere ses troupes avec la bienveillance d’un pere de famille. Pierre-Arnaud Raviart qui a regne sur le CMAP avec une voix de stentor, Vincent Giovangigli. Je salue Carl Graham, grand specialiste de la bible, qui eleve heureusement le niveau de la discussion que Fran cois Jouve amene periodiquement au-dessous de la ceinture, Eric Bonnetier, qui se pique d’aimer le bon vin et les bons mots, Marc Schoenauer, Pedro Ferreira, Josselin Garnier, Aldjia Mazari, qui m’a spontanement propose de faire une repetition de soutenance qui m’a ete extr^emement utile. Je salue egalement Habib Ammari, Kamel Hamdache, Tou c Abboud, Frederic Nataf, Robert \Bob" Brizzi et Genevieve Allain. Je remercie Jean-Fran cois Colonna qui m’a consacre du temps et de la patience pour realiser un lm de presentation, malgre un emploi du temps charge. Je salue les autres membres de l’equipe ondelettes, Emmanuel Bacry, Maureen Clerc, Jer^ ome Kalifa qui vient de convoler en justes noces, Remi Gribonval, Erwan Le Pen- nec, Jer^ ome Fraleu, Yann Samuelides, ainsi que tous les autres membres du CMAP qui ont ajoute leur pierre a l’harmonie de l’equipe, a savoir Shiraz Latiri qui nous a souvent conduits, Rita et moi, dans sa shirazmobile, So ane Oussedik, Daniel Delahaye, An- nalisa Ambroso, Paul Seignourel, Florence Bailly, Natacha Vialle, Rama Cont et ses plaisanteries homeopathiques, Erik Burman et Jonas Ribbe, Denis Barbier et Snorre Christiansen sans oublier mes collegues de bureau Alain Racine, Sana Ben Hamida et Jean-Philippe Ayanides. E C E N I M iv Je dedie cette these a Rita, et a mes parents. vi TABLE DES MATIÈRES vii Table des matières 1 Introduction 1 1.1 La mesure du mouvement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 La mesure du mouvement est un probleme mal pose . . . . . . . . . . 3 1.1.2 Aliasage en temps et localisation de la mesure . . . . . . . . . . . . . . 4 1.1.3 Plan de la premiere partie . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Interpolation multidimensionnelle irreguliere . . . . . . . . . . . . . . . . . . . 8 1.2.1 Choix d’une representation. Approximation lineaire et non-lineaire . . 10 1.2.2 Methode proposee pour construire un interpolant . . . . . . . . . . . . 12 1.2.3 Contr^ ole a posteriori de la stabilite et regularisation locale . . . . . . . 15 2 Les ondelettes 17 2.1 Frequence locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.2 Representations temps{frequence et temps{echelle . . . . . . . . . . . . . . . 18 2.3 Transformee en ondelettes continue . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 La transformee en discrete . . . . . . . . . . . . . . . . . . . . . . . 21 2.5 Analyses multi-resolutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5.1 Cadre theorique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5.2 Les bases d’ondelettes . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.5.3 Transformee en ondelettes . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.5.4 Filtres duaux, duales . . . . . . . . . . . . . . . . . . . . . . 25 2.5.5 L’algorithme de la transformee en ondelettes rapide . . . . . . . . . . 26 2.5.6 Les ondelettes orthogonales . . . . . . . . . . . . . . . . . . . . . . . . 28 2.6 Decroissance des coe cients, regularite et approximation . . . . . . . . . . . . 29 2.7 Creation d’ondelettes regulieres et choix de ltres . . . . . . . . . . . . . . . . 30 2.7.1 Conditions su santes dans le cas orthogonal . . . . . . . . . . . . . . 32 2.7.2 Condition su sante de regularite . . . . . . . . . . . . . . . . . . . . . 32 I Mesure du flot optique 37 3 Le flot optique 39 3.1 Estimation di erentielle projetee du ot optique . . . . . . . . . . . . . . . . 40 3.2 Aliasing temporel et echelle des fonctions de mesure . . . . . . . . . . . . . . 45 viii TABLE DES MATIÈRES 4 Présentation de la méthode 51 4.1 Les ondelettes sont un outil d’analyse multi-echelles naturel . . . . . . . . . . 51 4.1.1 Bases et frames d’ondelettes . . . . . . . . . . . . . . . . . . . . . . . 52 4.1.2 Convergence de l’estimation . . . . . . . . . . . . . . . . . . . . . . . . 53 4.1.3 Resolution de systemes sur-determines . . . . . . . . . . . . . . . . . . 56 4.1.4 Ra nement progressif des mesures . . . . . . . . . . . . . . . . . . . . 57 4.2 Ondelettes analytiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2.1 Stabilite de l’estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.2.2 Decentrement de la gamme de deplacements mesurables avec des on- delettes analytiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.3 Ondelettes en bancs de ltres . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.3.1 Ondelettes analytiques en bancs de ltres . . . . . . . . . . . . . . . . 68 4.3.2 Conception des ltres . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5 Preuves de convergence 75 5.1 Frame analytique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.2 Consistance de l’estimation du ot optique . . . . . . . . . . . . . . . . . . . 79 5.2.1 Erreur d’approximation d’un ot non uniforme par un ot uniforme . 79 5.2.2 d’aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6 Expérimentations numériques. Perspectives. 93 6.1 Experimentions numeriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.1.1 Cout^ de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6.1.2 Sequences reelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6.1.3 S synthetiques . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6.1.4 Changement d’illumination . . . . . . . . . . . . . . . . . . . . . . . . 98 6.2 Compression video . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.3 Introduction de l’eclairement comme variable explicative supplementaire . . . 101 6.4 Modeles non constants du ot optique . . . . . . . . . . . . . . . . . . . . . . 103 6.4.1 Modele de projection stereographique d’elements plans . . . . . . . . . 103 6.4.2 Cas d’un modele de camera a projection orthogonale . . . . . . . . . . 105 6.4.3 Estimation d’un ot non localement constant avec des ondelettes . . . 105 A Bases et frames d’ondelettes dérivées 109 A.1 Ondelettes et ltres derives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 A.2 Frames d’ondelettes derivees . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 II Apprentissage et interpolation 119 7 L’apprentissage 121 7.1 Les problemes d’apprentissage . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 7.1.1 Quelle solution choisir? . . . . . . . . . . . . . . . . . . . . . . . . . . 121 7.1.2 Quel probleme choisir? . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 7.1.3 Mesure d’erreur et fonction objectif . . . . . . . . . . . . . . . . . . . 123 7.1.4 Les di erentes approches . . . . . . . . . . . . . . . . . . . . . . . . . 123 TABLE DES MATIÈRES ix 7.2 Les reseaux de neurones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 7.2.1 Le perceptron multi-couches . . . . . . . . . . . . . . . . . . . . . . . . 124 7.2.2 Capacite d’expression . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 7.2.3 La regle d’apprentissage supervise . . . . . . . . . . . . . . . . . . . . 125 7.2.4 Les trois etapes de la conception d’un reseau de neurones . . . . . . . 126 7.2.5 Le perceptron de Rosenblatt . . . . . . . . . . . . . . . . . . . . . . 127 7.3 Des ondelettes comme fonctions de transfert neuronales ... . . . . . . . . . . . 128 7.4 Le contr^ ole adaptatif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 7.4.1 Contr^ ole adaptatif en dimension nie . . . . . . . . . . . . . . . . . . . 129 7.4.2 Apprentissage de fonctions . . . . . . . . . . . . . . . . . . . . . . . . 132 7.5 La regularisation et les radiales . . . . . . . . . . . . . . . . . . . . . 133 7.5.1 Le probleme regularise . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 7.5.2 Resolution du probleme regularise . . . . . . . . . . . . . . . . . . . . 134 7.5.3 Noyaux auto{reproduisants de regression . . . . . . . . . . . . . . . . 135 7.5.4 Fonctions de nies positives . . . . . . . . . . . . . . . . . . . . . . . . 136 7.5.5 Modele bayesien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 7.5.6 Limite de l’approche regularisee . . . . . . . . . . . . . . . . . . . . . . 139 7.6 Extension a des semi{normes . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.6.1 Theoreme du representant . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.6.2 Ordre d’approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 7.6.3 Calcul rapide avec des noyaux radiaux . . . . . . . . . . . . . . . . . . 143 7.7 Les machines a vecteurs support de Vapnik . . . . . . . . . . . . . . . . . . . 147 7.7.1 Dimension de Vapnik-Chervonenkis . . . . . . . . . . . . . . . . . . 148 7.7.2 Majoration de l’erreur d’estimation . . . . . . . . . . . . . . . . . . . . 149 7.7.3 Mise en uvre du principe de minimisation de l’erreur structurelle : les machines a vecteurs support . . . . . . . . . . . . . . . . . . . . . . 151 8 Approches multi résolutions 157 8.1 Le choix d’une representation . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 8.1.1 Approximation lineaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 8.1.2 Approximation non{lineaire et espaces de Besov . . . . . . . . . . . . 159 8.1.3 Structure et approximation en arbres . . . . . . . . . . . . . . . . . . . 163 8.1.4 Limites de l’appro en ondelettes . . . . . . . . . . . . . . . . . 166 8.1.5 Arbres d’ondelettes d’interpolation . . . . . . . . . . . . . . . . . . . . 169 8.1.6 Apprentissage pour les reseaux d’ondelettes . . . . . . . . . . . . . . . 171 8.2 Ondelettes d’interpolation et grilles d’approximation . . . . . . . . . . . . . . 172 8.3 Schema d’allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 8.3.1 Quasi unicite et existence d’un optimum . . . . . . . . . . . . . . . . . 175 8.3.2 Schema d’allocation iteratif . . . . . . . . . . . . . . . . . . . . . . . . 176 8.3.3 Comportement asymptotique . . . . . . . . . . . . . . . . . . . . . . . 178 8.4 Allocation dans une base de Schauder . . . . . . . . . . . . . . . . . . . . . 179 8.4.1 Conditionnement des matrices a diagonale dominante . . . . . . . . . 180 8.4.2 La base de Schauder . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 8.4.3 La relocalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 8.5 Generalisation en dimension superieure . . . . . . . . . . . . . . . . . . . . . . 189 8.5.1 Conditions de stabilite . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 8.5.2 Stabilite de l’interpolation en cas de bon placement relatif . . . . . . . 192 8.5.3 Vitesse de convergence de l’approximation . . . . . . . . . . . . . . . . 195 8.5.4 Theoremes d’approximation non uniforme . . . . . . . . . . . . . . . . 198 8.6 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 8.6.1 Decroissance de l’erreur avec le nombre de points de mesure . . . . . . 206 8.7 Commentaires et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 8.7.1 Comparaison avec les autres methodes . . . . . . . . . . . . . . . . . . 209 8.7.2 Le cas des mesures bruitees . . . . . . . . . . . . . . . . . . . . . . . . 210 8.7.3 Densite de points de mesure non uniforme . . . . . . . . . . . . . . . . 211 9 Interpolation incrémentale. Perspectives. 215 9.1 Implementation incrementale de l’algorithme d’interpolation . . . . . . . . . . 215 9.1.1 Structure d’arbre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 9.1.2 Calculs de mise a jour des matrices . . . . . . . . . . . . . . . . . . . . 217 9.2 Contr^ ole a posteriori de la stabilite . . . . . . . . . . . . . . . . . . . . . . . . 219 9.2.1 Vue d’ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 9.2.2 Remplacement de mesures . . . . . . . . . . . . . . . . . . . . . . . . . 220 9.2.3 Contr^ ole de croissance . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 9.3 Regularisation partielle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 9.3.1 Experiences numeriques et perspectives . . . . . . . . . . . . . . . . . 223 B Ondelettes d’interpolation 227 B.1 Fonctions d’echelle d’interpolation . . . . . . . . . . . . . . . . . . . . . . . . 227 B.2 Ondelettes d’interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 B.3 de Deslauriers{Dubuc . . . . . . . . . . . . . . . . . . . . . . . 229 B.4 Ondelettes sur l’intervalle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 B.4.1 Periodisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 B.4.2 Ondelettes de bords et bases de fonctions sur l’intervalle . . . . . . . . 231 B.4.3 d’interpolation sur l’intervalle . . . . . . . . . . . . . . . . 232 B.5 Theoremes d’approximation uniforme . . . . . . . . . . . . . . . . . . . . . . 235 B.6 Ondelettes de Deslauriers{Dubuc triadiques . . . . . . . . . . . . . . . . . 236