Traitement du signal sur graphesCette 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.
Signal sur grapheUn 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. Représentation dans le domaine spatialIl 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 spectralA 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 grapheOn 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 grapheChoisissez 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 diffusionA 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-lifeQuelques impressions d'écran d'un projet de construction que j'ai modélisé avec le moteur d'Half-life source.
| ||||
FPS avec OCamlQuelques 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époJ'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 recherchesAfficher ma carte de recherche sur une carte plus grande |
Français
English
Vous êtes le 769283ème visiteur