Site de Vincent Gripon

Blog sur mes recherches et mon enseignement

Traitement du signal sur graphes

Cette page est le résultat de travail de stage de Chiraz Nafouki, étudiante à Télécom Bretagne.

Le traitement de signal sur graphe est un domaine récent qui permet de généraliser le traitement classique de signal. Un graphe est composé d'un ensemble de points, appelés noeuds, dont certains sont liés par des arêtes. Si l'on étiquette les noeuds de 1 à n, un graphe est caractérisé par sa matrice d'adjacence. Cette matrice contient dans la case (i,j) le poids de l'arête, si elle existe, qui relie les noeuds i et j (0 sinon). Un graphe peut être orienté ou non. Un graphe non orienté a une matrice d'ajacence symmétrique.
Il existe aujourd'hui beaucoup d'applications du traitement de signal sur graphe. Par exemple l'analyse des réseaux sociaux, des données d'imagerie cérébrale, des réseaux de transport ou de courrant électrique... C'est la généricité des graphes qui leur permet de s'adapter à de nombreux domaines d'application.
Par exemple, on peut représenter un réseau social par un graphe dont les noeuds sont les personnes et les arêtes sont les liaisons d'amitié :

defaut
Exemple de graphe

Signal sur graphe

Un signal sur un graphe est un vecteur associant à chaque noeud d'un graphe une valeur réelle. Ce signal permet de représenter une intensité à chaque noeud du graphe.
Par exemple un signal peut être la température mesurée par des capteurs, vus comme les noeuds d'un graphe, et reliés par des arêtes correspondant à la distance entre les capteurs.

Représentation dans le domaine spatial

Il y a différentes façons de représenter un signal sur graphe dans le domaine spatial. On peut utiliser une représentation en 3D où le signal est représenté par des barres dont la hauteur correspond à la valeur du signal. Une deuxième façon consiste à utiliser des niveaux de couleurs (par exemple des niveaux de bleus) qui représentent la valeur du signal: on affecte à chaque noeud du graphe une couleur représentant la valeur du signal en ce point. On obtient ainsi une représentation bidimensionellle. Nous allons utiliser les niveaux de couleurs pour visualiser la diffusion du signal dans la suite.

defaut
Représentation tridimensionelle d'un signal sur un graphe
defaut
Représenation bidimensionelle d'un signal sur un graphe

Représentation dans le domaine spectral

A part la matrice d'adjacence, on peut associer à un graphe une autre matrice appelée le laplacien normalisé de graphe L = I - D-1/2 A D-1/2 , où I est la matrice identité, D la matrice des degrés et A la matrice d'adjacence du graphe. Cette matrice permet de mesurer la régularité d'un signal grâce à la norme quadratique qui lui est associée. En effet les valeurs propres de cette matrice correspondent à des "fréquences discrètes" et la décomposition d'un signal suivant la base des vecteurs propres du Laplacien normalisé permet ainsi de déterminer les différentes composantes fréquentielles du signal. Dans la suite, on désigne par λi la ième valeur propre du laplacien noramlisé avec λ0≤λ1≤...≤λn-1 , où n représente la taille du graphe.

Diffusion d'un signal sur un graphe

On peut définir un opérateur de diffusion d'un signal sur un graphe. Cet opérateur fait évoluer le signal en le faisant propager de manière uniforme à travers le graphe. Un exemple simple est la diffusion d'un message à travers un réseau social.
L'opérateur de diffusion est représenté par une matrice appelée matrice de diffusion W= D-1/2 A D-1/2 ,D étant la matrice diagonale des degrés et A la matrice d'adjacence associée au graphe.
A partir d'un graphe et d'un signal initial, on peut visualiser les différentes étapes de la diffusion du signal sur le graphe. Pour cela il suffit de multiplier à chaque fois le signal par la matrice de diffusion.

Exemples de diffusion d'un signal sur un graphe

Choisissez un graphe:

Entrez le signal initial (valeurs positives ou nulles)

Noeud 0 : Noeud 1 :

Noeud 2 : Noeud 3 :

Noeud 4 : Noeud 5 :

Noeud 6 : Noeud 7 :

Noeud 8 :

Visualisez la diffusion

A chaque fois que vous appuyez sur le bouton "Visualiser la diffusion", une diffision du signal est réalisée sur le graphe. La diffusion est représentée à la fois dans le domaine spatial et dans le domaine spectral.

defaut





Vous êtes le 485194ème visiteur

Site de Vincent Gripon