Décompositions multi-échelles hiérarchiques de signaux sur graphes

Télécharger le fichier pdf d’un mémoire de fin d’études

Graphes et signaux

Introduction

Nous introduisons dans ce chapitre le vocabulaire et les notions dont nous ferons usage dans toute la suite de ce manuscrit.

Ce chapitre est organisé de la manière suivante. Dans la section 2.2, nous introduisons la notion de graphe pondéré ainsi que le langage de la théorie des graphes dont nous nous servons. L’étude des propriétés d’un graphe G peut se faire en examinant les valeurs et vecteurs propres de certaines matrices associées. Il s’agit là de la théorie spectrale des graphes [Chu97, Moh91, Moh97, Spi07]. Les matrices laplaciennes y jouent un rôle important. Nous définissons ces matrices et énonçons certaines propriétés utiles pour la suite du document. Les développements ultérieurs feront usage principalement de la version combinatoire du laplacien. Une autre matrice importante est la matrice de transition associée à une chaîne de Markov dont les états sont les sommets du graphe. La section 2.3 est dédiée aux approches de construction de graphes pondérés à partir d’un ensemble de données. Les graphes que l’on y obtient sont des graphes de similarité, c’est-à-dire que le poids aﬀecté à une arête reliant deux sommets relève de la similarité que l’on accorde à ces sommets. Outre les constructions classiques (graphes des plus proches voisins et ǫ graphes), nous rappelons également certaines constructions récentes principalement issues de la communauté d’apprentissage. Dans la section 2.4, nous définissons le concept de signal sur graphe. Il s’agit de fonctions définies sur l’ensemble des sommets d’un graphe pondéré général. L’étude de ces signaux repose sur une famille d’opérateurs discrets que nous donnons ici. Ces opérateurs permettent de définir des mesures relatives de régularité. Nous nous servirons de ces mesures pour proposer des décompositions mono-échelles de signaux sur graphes dans le chapitre 3 et multi-échelles dans le chapitre 4. Enfin, la section 2.5 traite de la modélisation des images numériques comme des signaux sur des graphes. Les spécificités de la construction des graphes à partir d’images y sont présentées. Au-delà de la construction des graphes, cette section illustre un aspect important de la modélisation : l’utilisation des attributs de l’image pour définir le graphe permet de mieux tenir compte des structures. Une conclusion de ce chapitre est présentée dans la section 2.6.

Graphes pondérés et matrices associées

Nous introduisons dans cette section, d’une part, les concepts de théorie des graphes sur lesquelles nous nous appuierons dans la suite de ce manuscrit, et d’autre part, les matrices associées à des graphes pondérés. Il s’agit des matrices d’adjacence, des matrices laplaciennes, et de la matrice de transition associée à une marche aléatoire sur un graphe.

Premières définitions

Soit V un ensemble fini non vide. On appelle graphe sur V tout couple G = (V, E) où E ⊂ V × V . Les éléments de V sont appelés des sommets et ceux de E des arêtes. Notons que la définition que nous donnons ici exclut la notion d’arêtes multiples. Dans la suite, V (G) désignera l’ensemble des sommets d’un graphe G et E(G) l’ensemble de ses arêtes.

On appelle ordre de G le cardinal de V (G). Si e = (u, v) ∈ E, on dira que

– e est incidente à u et à v ;

– u et v sont les extrémités de e ;

– u et v sont voisins (ou adjacents), et on notera u ∼ v.

– e est une boucle si u = v.

Un sommet u ∈ V (G) est dit isolé s’il n’a aucun voisin. G est dit non orienté si (u, v) ∈ E(G) si et seulement si (v, u) ∈ E(G).

Les graphes que nous considérons dans toute la suite de ce manuscrit sont supposés d’ordre fini, sans aucun sommet isolé, sans boucles et non orientés, sauf mention contraire.

Si u ∈ V (G), on notera d(u) le nombre de ses voisins. On dira que d(u) est le degré simple de u. Le graphe G est dit k-régulier si d(u) = k pour tout u ∈ V (G).

Deux sommets u, v ∈ V (G) sont dits connectés s’il existe un chemin les reliant, c’est-à-dire s’il existe u0, , u n ∈ V (G) tels que

(i) u0 = u ;

(ii) un = v ;

(iii) (∀i ∈ {0, , n − 1}) ui ∼ ui+1 .

Une partie W ⊂ V (G) est dite connectée si toute paire de sommets dans W est connectée par un chemin inclus dans W . Une composante connexe est une partie connectée maximale. G est connexe s’il contient une unique composante connexe. Un exemple de graphe connexe est le graphe complet, pour lequel (u, v) ∈ E(G) pour tous u, v ∈ V (G).

Soit H un graphe. On dit que H est un sous-graphe de G si :

(i) V(H) ⊂ V(G);

(ii) E(H) ⊂ E(G).

On dit d’un sous-graphe H de G qu’il est couvrant si V (H ) = V (G).

Un graphe G muni d’une fonction symétrique w : E(G) → R s’appelle un graphe pondéré. Dans toute la suite de ce document, la fonction de pondération

w est supposée à valeurs dans R+∗. Pour (u, v) ∈ E, la quantité w(u, v) est interprétée comme une mesure de similarité entre u et v.

Soit u ∈ V (G). On appelle degré pondéré de u la quantité

dw (u) = w(u, v)

v∼u

Si H = (V (H ), E(H ), wH ) désigne un graphe pondéré, on dit que H est un sous-graphe pondéré de G si

(i) (V (H ), E(H )) est un sous-graphe de (V, E) ;

(ii) w|E(H ) = wH .

Coloration

Soit G un graphe et k ≥ 2 un entier. Une k-coloration de G est une fonction c : V → {1, , k } telle que (∀e = (u, v) ∈ E(G)) c(u) = c(v)

On dit que G est dit k-coloriable s’il admet une k-coloration. Le plus petit k tel que G soit k-coloriable s’appelle le nombre chromatique de G et est noté χ(G). Un graphe 2-coloriable est dit biparti.

Tout graphe admet un sous-graphe couvrant biparti. Le problème du sous-graphe couvrant biparti maximal consiste à en sélectionner un ayant le plus grand nombre d’arêtes. Si G est pondéré, on cherche alors un sous-graphe biparti couvrant maximisant le critère suivant :

w(u, v), (2.1)

u∼v

u∈A,v∈B

où A et B désignent les deux parties du sous-graphe. Ce problème est équivalent à celui de la recherche d’une coupe maximale que nous décrivons maintenant.

Coupe maximale

On est souvent amené à partitionner l’ensemble des sommets V (G) d’un graphe pondéré G en deux parties disjointes A et B. De telles partitions s’appellent des coupes. On associe à une coupe (A, B) la fonction d’utilité suivante :

w(u, v) (2.2)

u∼v

u∈A,v∈B

Le problème de la coupe maximale consiste alors à déterminer une coupe maximisant l’utilité 2.2. Ce problème, équivalent au problème du sous-graphe couvrant biparti maximal, est NP-complet. Le lecteur intéressé par les algorithmes d’approximation de ce problème pourra consulter la section 4 [Moh97].

Le problème de la coupe maximale sera rencontré dans le chapitre 5 de ce manuscrit dans le contexte des transformées multi-échelles de signaux sur graphes. Nous y verrons en particulier que l’adaptation de la transformée de lifting [Swe96] à des signaux sur graphes nécessite un critère de partitionnement des sommets.

Coupes en optimisation combinatoire

En optimisation combinatoire, la notion de coupe est diﬀérente de celle que nous venons de rappeler : elle s’applique à des graphes orientés ayant des noeuds remarquables. Plus précisément, soit G un graphe pondéré orienté. On suppose que V (G) contient deux sommets particuliers : un sommet noté s et appelé source ; un sommet noté t et appelé puits. Une s/t coupe est définie comme étant une partition de V (G) en deux ensembles S et T tels que s ∈ S et t ∈ T (c.f. figure 1 2.1). On associe à une telle coupe le coût suivant :

C(S,T ) = w(u, v) (2.3)

(u,v) S ×T

Le problème de la s/t coupe minimale est celui de la recherche d’une coupe minimisant le coût (2.3). Ce problème peut être résolu en temps polynomial. L’article [BK04] présente, dans le contexte de la vision par ordinateur, une comparaison des performances de plusieurs algorithmes et en propose un nouveau, disponible à l’adresse http://pub.ist.ac.at/~vnk/software. html. Greig et al. [GPS89] ont été les premiers à faire le lien entre la mi-nimisation d’une énergie discrète et la recherche d’une coupe minimale.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1 Introduction 9
2 Graphes et signaux
2.1 Introduction
2.2 Graphes pondérés et matrices associées
2.2.1 Premières définitions
2.2.2 Coloration
2.2.3 Coupe maximale
2.2.4 Coupes en optimisation combinatoire
2.2.5 Matrices associées à un graphe pondéré
2.3 Construction d’un graphe pondéré à partir d’un ensemble de données
2.3.1 Construction de la topologie
2.3.2 Fonctions de similarité
2.3.3 Construction simultanée de la topologie et des poids
2.4 Signaux sur graphes
2.4.1 Espaces H(V ) et H(E)
2.4.2 Opérateurs de différence
2.4.3 Mesures de régularité
2.5 Les images comme des fonctions sur des graphes
2.5.1 Principe
2.5.2 Vecteurs de caractéristiques
2.5.3 Débruitage d’images par filtres de voisinage
2.5.4 Lien avec les graphes
2.6 Conclusion
3 Approches variationnelles pour le débruitage de signaux sur graphes
3.1 Introduction
3.2 Éléments d’analyse et d’optimisation convexes
3.2.1 Espace Γ0(H)
3.2.2 Fonction conjuguée
3.2.3 Opérateur proximal
3.2.4 Algorithmes proximaux
3.3 Le cadre bayésien pour le débruitage d’images
3.3.1 Débruitage par minimisation d’énergie
3.3.2 Le cadre bayésien
3.3.3 A priori classiques en traitement de l’image
3.4 Approches variationnelles pour le débruitage de signaux sur graphes
3.4.1 A priori quadratique
3.4.2 A priori basé sur la variation totale
3.5 Expériences
3.5.1 Images
3.5.2 Maillages
3.6 Conclusion
4 Décompositions multi-échelles hiérarchiques de signaux sur graphes
4.1 Introduction
4.2 Décompositions u + v
4.3 Décompositions multi-échelles
4.3.1 Définition et motivations
4.3.2 Décompositions basées sur le principe de la pyramide laplacienne
4.3.3 L’approche hiérarchique de Tadmor, Nezzar et Vese pour la décomposition d’images
4.4 Décomposition multi-échelle quadratique
4.4.1 Principe
4.4.2 Convergence et choix des paramètres
4.5 Décomposition basée sur la TV sur graphes
4.5.1 Principe
4.5.2 Convergence
4.5.3 Choix de la suite d’échelle λi
4.6 Exemples de décompositions obtenues avec Jw 1,2
4.6.1 Images
4.6.2 Maillages et nuages de points 3D
4.7 Applications en rehaussement de détails pour les images et les maillages
4.7.1 Comparaison avec l’état de l’art
4.7.2 Rehaussement de contours
4.7.3 Tone mapping
4.7.4 Retouche virtuelle de portraits
4.7.5 Rehaussement de détails sur des maillages
4.8 Conclusion
5 Transformées multi-échelles de signaux sur graphes
5.1 Introduction
5.2 Transformées multi-échelles pour les signaux et les images
5.2.1 Difficultés d’adaptation pour les signaux sur graphes
5.3 Transformées multi-échelles définies dans le domaine spectral
5.3.1 Ondelettes de diffusion
5.3.2 Ondelettes spectrales
5.4 Transformée de Haar sur une hiérarchie
5.4.1 Transformée de Haar sur une hiérarchie
5.4.2 Construction adaptative d’une hiérarchie à partir d’un graphe pondéré
5.4.3 Expériences
5.5 Transformées multi-échelles par lifting sur graphes
5.5.1 Schéma du lifting pour les signaux 1D
5.5.2 Lifting sur graphes
5.5.3 Transformée multi-échelle par suite de liftings élémentaires
5.5.4 Expériences
5.6 Conclusion
6 Conclusion et perspectives
Liste des figures