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é :
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.
Représentation tridimensionelle d'un signal sur un graphe 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/2AD-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/2AD-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)
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.
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.
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.