Auswahl der wissenschaftlichen Literatur zum Thema „Ondelettes sur graphe“

Dans cet article, nous proposons une méthode de caractérisation locale des textures des images de très haute résolution spatiale, dans lesquelles l'hypothèse de stationnarité est peu respectée.Une approche ponctuelle (i.e. non-dense) est d'abord introduite pour la représentation de l'image en utilisant un ensemble de pixels d'intétêt au lieu de la totalité des pixels de l'image. Un graphe pondéré est ensuite construit à partir de ces pixels représentatifs. Le signal de texture, porté sur ce graphe, est ensuite analysé à travers une transformée en ondelettes sur graphe. La classification en texture, implémentée ici de façon non-supervisée, est donc réalisée par la classification des coefficients d'ondelettes sur le graphe. Les expérimentations appliquées aux images panchromatiques Pléiades nous donnent des résultats très prometteurs avec une bonne précision de classification tout en gardant une compléxité intéressante.

Au cours de la dernière décennie, le traitement du signal sur graphe est devenu un domaine de recherche très actif. Plus précisément, le nombre d’applications utilisant des repères construits à partir de graphes, tels que les ondelettes sur graphe, a augmenté de manière significative. Nous considérons en particulier le débruitage de signaux sur graphes au moyen d’une décomposition dans un repère ajusté d’ondelettes. Cette approche est basée sur le seuillage des coefficients d’ondelettes à l’aide de l’estimateur sans biais du risque de Stein (SURE). Nous étendons cette méthodologie aux graphes de grande taille en utilisant l’approximation par polynômes de Chebyshev qui permet d’éviter la décomposition de la matrice laplacienne du graphe. La principale difficulté est le calcul de poids dans l’expression du SURE faisant apparaître un terme de covariance en raison de la nature surcomplète du repère d’ondelettes. Le calcul et le stockage de celui-ci est donc nécessaire et rédhibitoire à grande échelle. Pour estimer cette covariance, nous développons et analysons un estimateur de Monte-Carlo reposant sur la transformation rapide de signaux aléatoires. Cette nouvelle méthode de débruitage trouve une application naturelle en confidentialité différentielle dont l’objectif est de protéger les données sensibles utilisées par les algorithmes. Une évaluation expérimentale de ses performances est réalisée sur des graphes de taille variable à partir de données réelles et simulées
Over the last decade, signal processing on graphs has become a very active area of research. Specifically, the number of applications using frames built from graphs, such as wavelets on graphs, has increased significantly. We consider in particular signal denoising on graphs via a wavelet tight frame decomposition. This approach is based on the thresholding of the wavelet coefficients using Stein’s unbiased risk estimate (SURE). We extend this methodology to large graphs using Chebyshev polynomial approximation, which avoids the decomposition of the graph Laplacian matrix. The main limitation is the computation of weights in the SURE expression, which includes a covariance term due to the overcomplete nature of the wavelet frame. The computation and storage of the latter is therefore necessary and impractical for large graphs. To estimate such covariance, we develop and analyze a Monte Carlo estimator based on the fast transform of random signals. This new denoising methodology finds a natural application in differential privacy whose purpose is to protect sensitive data used by algorithms. An experimental evaluation of its performance is carried out on graphs of varying size, using real and simulated data

Dans ce manuscrit, nous avons étudié l’extension de l’analyse multi-résolution aux images couleurs par des transformées sur graphe. Dans ce cadre, nous avons déployé trois stratégies d’analyse différentes. En premier lieu, nous avons défini une transformée basée sur l’utilisation d’un graphe perceptuel dans l’analyse à travers la transformé en ondelettes spectrale sur graphe. L’application en débruitage d’image met en évidence l’utilisation du SVH dans l’analyse des images couleurs. La deuxième stratégie consiste à proposer une nouvelle méthode d’inpainting pour des images couleurs. Pour cela, nous avons proposé un schéma de régularisation à travers les coefficients d’ondelettes de la TOSG, l’estimation de la structure manquante se fait par la construction d’un graphe des patchs couleurs à partir des moyenne non locales. Les résultats obtenus sont très encourageants et mettent en évidence l’importance de la prise en compte du SVH. Dans la troisième stratégie, nous proposons une nouvelleapproche de décomposition d’un signal défini sur un graphe complet. Cette méthode est basée sur l’utilisation des propriétés de la matrice laplacienne associée au graphe complet. Dans le contexte des images couleurs, la prise en compte de la dimension couleur est indispensable pour pouvoir identifier les singularités liées à l’image. Cette dernière offre de nouvelles perspectives pour une étude approfondie de son comportement
In our work, we studied the extension of the multi-resolution analysis for color images by using transforms on graphs. In this context, we deployed three different strategies of analysis. Our first approach consists of computing the graph of an image using the psychovisual information and analyzing it by using the spectral graph wavelet transform. We thus have defined a wavelet transform based on a graph with perceptual information by using the CIELab color distance. Results in image restoration highlight the interest of the appropriate use of color information. In the second strategy, we propose a novel recovery algorithm for image inpainting represented in the graph domain. Motivated by the efficiency of the wavelet regularization schemes and the success of the nonlocal means methods we construct an algorithm based on the recovery of information in the graph wavelet domain. At each step the damaged structure are estimated by computing the non local graph then we apply the graph wavelet regularization model using the SGWT coefficient. The results are very encouraging and highlight the use of the perceptual informations. In the last strategy, we propose a new approach of decomposition for signals defined on a complete graphs. This method is based on the exploitation of of the laplacian matrix proprieties of the complete graph. In the context of image processing, the use of the color distance is essential to identify the specificities of the color image. This approach opens new perspectives for an in-depth study of its behavior

Cette thèse propose de nouveaux outils adaptés à l'analyse des réseaux : sociaux, de transport, de neurones, de protéines, de télécommunications... Ces réseaux, avec l'essor de certaines technologies électroniques, informatiques et mobiles, sont de plus en plus mesurables et mesurés ; la demande d'outils d'analyse assez génériques pour s'appliquer à ces réseaux de natures différentes, assez puissants pour gérer leur grande taille et assez pertinents pour en extraire l'information utile, augmente en conséquence. Pour répondre à cette demande, une grande communauté de chercheurs de différents horizons scientifiques concentre ses efforts sur l'analyse des graphes, des outils mathématiques modélisant la structure relationnelle des objets d'un réseau. Parmi les directions de recherche envisagées, le traitement du signal sur graphe apporte un éclairage prometteur sur la question : le signal n'est plus défini comme en traitement du signal classique sur une topologie régulière à n dimensions, mais sur une topologie particulière définie par le graphe. Appliquer ces idées nouvelles aux problématiques concrètes d'analyse d'un réseau, c'est ouvrir la voie à une analyse solidement fondée sur la théorie du signal. C'est précisément autour de cette frontière entre traitement du signal et science des réseaux que s'articule cette thèse, comme l'illustrent ses deux principales contributions. D'abord, une version multiéchelle de détection de communautés dans un réseau est introduite, basée sur la définition récente des ondelettes sur graphe. Puis, inspirée du concept classique de bootstrap, une méthode de rééchantillonnage de graphes est proposée à des fins d'estimation statistique
This thesis describes new tools specifically designed for the analysis of networks such as social, transportation, neuronal, protein, communication networks... These networks, along with the rapid expansion of electronic, IT and mobile technologies are increasingly monitored and measured. Adapted tools of analysis are therefore very much in demand, which need to be universal, powerful, and precise enough to be able to extract useful information from very different possibly large networks. To this end, a large community of researchers from various disciplines have concentrated their efforts on the analysis of graphs, well define mathematical tools modeling the interconnected structure of networks. Among all the considered directions of research, graph signal processing brings a new and promising vision : a signal is no longer defined on a regular n-dimensional topology, but on a particular topology defined by the graph. To apply these new ideas on the practical problems of network analysis paves the way to an analysis firmly rooted in signal processing theory. It is precisely this frontier between signal processing and network science that we explore throughout this thesis, as shown by two of its major contributions. Firstly, a multiscale version of community detection in networks is proposed, based on the recent definition of graph wavelets. Then, a network-adapted bootstrap method is introduced, that enables statistical estimation based on carefully designed graph resampling schemes

La recherche menée dans cette thèse a pour but de développer une analyse harmonique pour des fonctions définies sur les sommets d'un graphe orienté. À l'ère du déluge de données, de nombreuses données sont sous forme de graphes et données sur ce graphe. Afin d'analyser d'exploiter ces données de graphes, nous avons besoin de développer des méthodes mathématiques et numériquement efficientes. Ce développement a conduit à l'émergence d'un nouveau cadre théorique appelé le traitement de signal sur graphe dont le but est d'étendre les concepts fondamentaux du traitement de signal classique aux graphes. Inspirées par l'aspect multi échelle des graphes et données sur graphes, de nombreux constructions multi-échelles ont été proposé. Néanmoins, elles s'appliquent uniquement dans le cadre non orienté. L'extension d'une analyse harmonique sur graphe orienté bien que naturelle, s'avère complexe. Nous proposons donc une analyse harmonique en utilisant l'opérateur de marche aléatoire comme point de départ de notre cadre. Premièrement, nous proposons des bases de type Fourier formées des vecteurs propres de l'opérateur de marche aléatoire. De ces bases de Fourier, nous en déterminons une notion fréquentielle en analysant la variation de ses vecteurs propres. La détermination d'une analyse fréquentielle à partir de la base des vecteurs de l'opérateur de marche aléatoire nous amène aux constructions multi-échelles sur graphes orientés. Plus particulièrement, nous proposons une construction en trames d'ondelettes ainsi qu'une construction d'ondelettes décimées sur graphes orientés. Nous illustrons notre analyse harmonique par divers exemples afin d'en montrer l'efficience et la pertinence
The research conducted in this thesis aims to develop a harmonic analysis for functions defined on the vertices of an oriented graph. In the era of data deluge, much data is in the form of graphs and data on this graph. In order to analyze and exploit this graph data, we need to develop mathematical and numerically efficient methods. This development has led to the emergence of a new theoretical framework called signal processing on graphs, which aims to extend the fundamental concepts of conventional signal processing to graphs. Inspired by the multi-scale aspect of graphs and graph data, many multi-scale constructions have been proposed. However, they apply only to the non-directed framework. The extension of a harmonic analysis on an oriented graph, although natural, is complex. We, therefore, propose a harmonic analysis using the random walk operator as the starting point for our framework. First, we propose Fourier-type bases formed by the eigenvectors of the random walk operator. From these Fourier bases, we determine a frequency notion by analyzing the variation of its eigenvectors. The determination of a frequency analysis from the basis of the vectors of the random walk operator leads us to multi-scale constructions on oriented graphs. More specifically, we propose a wavelet frame construction as well as a decimated wavelet construction on directed graphs. We illustrate our harmonic analysis with various examples to show its efficiency and relevance

Cette thèse traite d'approches permettant la construction de décompositions multi-échelles de signaux définis sur des graphes pondérés généraux. Ce manuscrit traite de trois approches que nous avons développées. La première approche est basée sur un procédé variationnel itératif et hiérarchique et généralise la décomposition structure-texture, proposée initialement pour les images. Deux versions sont proposées : l'une basée sur un apriori quadratique et l'autre sur un apriori de type variation totale. L'étude de la convergence est effectuée et le choix des paramètres discuté dans chaque cas. Nous détaillons l'application des décompositions que nous obtenons au rehaussement de détails dans les images et les modèles 3D. La deuxième approche fournit une analyse multirésolution de l'espace des signaux sur un graphe donné. Cette construction repose sur l'organisation du graphe sous la forme d'une hiérarchie de partitions. Nous avons développé un algorithme permettant la construction adaptative de telles hiérarchies. Enfin, dans la troisième approche, nous adaptons le schéma de lifting à des signaux sur graphes. Cette adaptation pose divers problèmes pratiques. Nous nous sommes intéressés d'une part à l'étape de sous-échantillonnage, pour laquelle nous avons adopté une approche gloutonne, et d'autre part à l'itération de la transformée sur des sous-graphes induits
This thesis is concerned with approaches to the construction of multiscale decompositions of signals defined on general weighted graphs. This manuscript discusses three approaches that we have developed. The first approach is based on a variational and iterative process. It generalizes the structure-texture decomposition, originally proposed for images. Two versions are proposed: one is based on a quadratic prior while the other is based on a total variation prior. The study of the convergence is performed and the choice of parameters discussed in each case. We describe the application of the decompositions we get to the enhancement of details in images and 3D models. The second approach provides a multiresolution analysis of the space of signals on a given graph. This construction is based on the organization of the graph as a hierarchy of partitions. We have developed an adaptive algorithm for the construction of such hierarchies. Finally, in the third approach, we adapt the lifting scheme to signals on graphs. This adaptation raises a number of practical problems. We focused on the one hand on the subsampling step for which we adopted a greedy approach, and on the other hand on the iteration of the transform on induced subgraphs