Site de Vincent Gripon

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é :

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.

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 λ₀≤λ₁≤...≤λ_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.

Ma maison dans Half-life

Quelques impressions d'écran d'un projet de construction que j'ai modélisé avec le moteur d'Half-life source.

FPS avec OCaml

Quelques screenshots d'un mini first-person-shooter que je me suis amusé à programmer en OCaml. Le réseau est fonctionnel ainsi que tous les outils de base.

Clavier personnel Bépo

J'utilise une version modifiée du clavier Bépo que j'ai entraîné sur mes fichiers personnels. Vous pouvez trouver la version console ici.
Le XKbmap est là.
Enfin le fichier xmodmap est ici.

Carte de mes recherches