Dissertationen zum Thema „Graph wavelets“

In typical statistical parametric mapping (SPM) of fMRI data, the functional data are pre-smoothed using a Gaussian kernel to reduce noise at the cost of losing spatial specificity. Wavelet approaches have been incorporated in such analysis by enabling an efficient representation of the underlying brain activity through spatial transformation of the original, un-smoothed data; a successful framework is the wavelet-based statistical parametric mapping (WSPM) which enables integrated wavelet processing and spatial statistical testing. However, in using the conventional wavelets, the functional data are considered to lie on a regular Euclidean space, which is far from reality, since the underlying signal lies within the complex, non rectangular domain of the cerebral cortex. Thus, using wavelets that function on more complex domains such as a graph holds promise. The aim of the current project has been to integrate a recently developed spectral graph wavelet transform as an advanced transformation for fMRI brain data into the WSPM framework. We introduce the design of suitable weighted and un-weighted graphs which are defined based on the convoluted structure of the cerebral cortex. An optimal design of spatially localized spectral graph wavelet frames suitable for the designed large scale graphs is introduced. We have evaluated the proposed graph approach for fMRI analysis on both simulated as well as real data. The results show a superior performance in detecting fine structured, spatially localized activation maps compared to the use of conventional wavelets, as well as normal SPM. The approach is implemented in an SPM compatible manner, and is included as an extension to the WSPM toolbox for SPM.

The classical wavelet transform has been widely used in image and signal processing, where a signal is decomposed into a combination of basis signals. By analyzing the individual contribution of the basis signals, one can infer properties of the original signal. This dissertation presents an overview of the extension of the classical signal processing theory to graph domains. Specifically, we review the graph Fourier transform and graph wavelet transforms both of which based on the spectral graph theory, and explore their properties through illustrative examples. The main features of the spectral graph wavelet transforms are presented using synthetic and real-world data. Furthermore, we introduce in this dissertation a novel method for visual analysis of dynamic networks, which relies on the graph wavelet theory. Dynamic networks naturally appear in a multitude of applications from different domains. Analyzing and exploring dynamic networks in order to understand and detect patterns and phenomena is challenging, fostering the development of new methodologies, particularly in the field of visual analytics. Our method enables the automatic analysis of a signal defined on the nodes of a network, making viable the detection of network properties. Specifically, we use a fast approximation of the graph wavelet transform to derive a set of wavelet coefficients, which are then used to identify activity patterns on large networks, including their temporal recurrence. The wavelet coefficients naturally encode spatial and temporal variations of the signal, leading to an efficient and meaningful representation. This method allows for the exploration of the structural evolution of the network and their patterns over time. The effectiveness of our approach is demonstrated using different scenarios and comparisons involving real dynamic networks.
A transformada wavelet clássica tem sido amplamente usada no processamento de imagens e sinais, onde um sinal é decomposto em uma combinação de sinais de base. Analisando a contribuição individual dos sinais de base, pode-se inferir propriedades do sinal original. Esta tese apresenta uma visão geral da extensão da teoria clássica de processamento de sinais para grafos. Especificamente, revisamos a transformada de Fourier em grafo e as transformadas wavelet em grafo ambas fundamentadas na teoria espectral de grafos, e exploramos suas propriedades através de exemplos ilustrativos. As principais características das transformadas wavelet espectrais em grafo são apresentadas usando dados sintéticos e reais. Além disso, introduzimos nesta tese um método inovador para análise visual de redes dinâmicas, que utiliza a teoria de wavelets em grafo. Redes dinâmicas aparecem naturalmente em uma infinidade de aplicações de diferentes domínios. Analisar e explorar redes dinâmicas a fim de entender e detectar padrões e fenômenos é desafiador, fomentando o desenvolvimento de novas metodologias, particularmente no campo de análise visual. Nosso método permite a análise automática de um sinal definido nos vértices de uma rede, tornando possível a detecção de propriedades da rede. Especificamente, usamos uma aproximação da transformada wavelet em grafo para obter um conjunto de coeficientes wavelet, que são então usados para identificar padrões de atividade em redes de grande porte, incluindo a sua recorrência temporal. Os coeficientes wavelet naturalmente codificam variações espaciais e temporais do sinal, criando uma representação eficiente e com significado expressivo. Esse método permite explorar a evolução estrutural da rede e seus padrões ao longo do tempo. A eficácia da nossa abordagem é demonstrada usando diferentes cenários e comparações envolvendo redes dinâmicas reais.

Signal processing is used in a wide variety of applications, ranging from digital image processing to biomedicine. Recently, some tools from signal processing have been extended to the context of graphs, allowing its use on irregular domains. Among others, the Fourier Transform and the Wavelet Transform have been adapted to such context. Graph signal processing (GSP) is a new field with many potential applications on data exploration. In this dissertation we show how tools from graph signal processing can be used for visual analysis. Specifically, we proposed a data filtering method, based on spectral graph filtering, that led to high quality visualizations which were attested qualitatively and quantitatively. On the other hand, we relied on the graph wavelet transform to enable the visual analysis of massive time-varying data revealing interesting phenomena and events. The proposed applications of GSP to visually analyze data are a first step towards incorporating the use of this theory into information visualization methods. Many possibilities from GSP can be explored by improving the understanding of static and time-varying phenomena that are yet to be uncovered.
O processamento de sinais é usado em uma ampla variedade de aplicações, desde o processamento digital de imagens até a biomedicina. Recentemente, algumas ferramentas do processamento de sinais foram estendidas ao contexto de grafos, permitindo seu uso em domínios irregulares. Entre outros, a Transformada de Fourier e a Transformada Wavelet foram adaptadas nesse contexto. O Processamento de Sinais em Grafos (PSG) é um novo campo com muitos aplicativos potenciais na exploração de dados. Nesta dissertação mostramos como ferramentas de processamento de sinal gráfico podem ser usadas para análise visual. Especificamente, o método de filtragem de dados porposto, baseado na filtragem de grafos espectrais, levou a visualizações de alta qualidade que foram atestadas qualitativa e quantitativamente. Por outro lado, usamos a transformada de wavelet em grafos para permitir a análise visual de dados massivos variantes no tempo, revelando fenômenos e eventos interessantes. As aplicações propostas do PSG para analisar visualmente os dados são um primeiro passo para incorporar o uso desta teoria nos métodos de visualização da informação. Muitas possibilidades do PSG podem ser exploradas melhorando a compreensão de fenômenos estáticos e variantes no tempo que ainda não foram descobertos.

This thesis addresses statistical estimation and testing of signals over a graph when measurements are noisy and high-dimensional. Graph structured patterns appear in applications as diverse as sensor networks, virology in human networks, congestion in internet routers, and advertising in social networks. We will develop asymptotic guarantees of the performance of statistical estimators and tests, by stating conditions for consistency by properties of the graph (e.g. graph spectra). The goal of this thesis is to demonstrate theoretically that by exploiting the graph structure one can achieve statistical consistency in extremely noisy conditions. We begin with the study of a projection estimator called Laplacian eigenmaps, and find that eigenvalue concentration plays a central role in the ability to estimate graph structured patterns. We continue with the study of the edge lasso, a least squares procedure with total variation penalty, and determine combinatorial conditions under which changepoints (edges across which the underlying signal changes) on the graph are recovered. We will shift focus to testing for anomalous activations in the graph, using the scan statistic relaxations, the spectral scan statistic and the graph ellipsoid scan statistic. We will also show how one can form a decomposition of the graph from a spanning tree which will lead to a test for activity in the graph. This will lead to the construction of a spanning tree wavelet basis, which can be used to localize activations on the graph.

O presente texto descreve a tese de doutorado intitulada Análise de Formas usando Wavelets em Grafos. O tema está relacionado à área de Visão Computacional, particularmente aos tópicos de Caracterização, Descrição e Classificação de Formas. Dentre os métodos da extensa literatura em Análise de Formas 2D, percebe-se uma presença menor daqueles baseados em grafos com topologia arbitrária e irregular. As contribuições desta tese procuram preencher esta lacuna. É proposta uma metodologia baseada no seguinte pipeline : (i) Amostragem da forma, (ii) Estruturação das amostras em grafos, (iii) Função-base definida nos vértices, (iv) Análise multiescala de grafos por meio da Transformada Wavelet Espectral em grafos, (v) Extração de Características da Transformada Wavelet e (vi) Discriminação. Para cada uma das etapas (i), (ii), (iii), (v) e (vi), são inúmeras as abordagens possíveis. Um dos desafios é encontrar uma combinação de abordagens, dentre as muitas alternativas, que resulte em um pipeline eficaz para nossos propósitos. Em particular, para a etapa (iii), dado um grafo que representa uma forma, o desafio é identificar uma característica associada às amostras que possa ser definida sobre os vértices do grafo. Esta característica deve capturar a influência subjacente da estrutura combinatória de toda a rede sobre cada vértice, em diversas escalas. A Transformada Wavelet Espectral sobre os Grafos revelará esta influência subjacente em cada vértice. São apresentados resultados obtidos de experimentos usando formas 2D de benchmarks conhecidos na literatura, bem como de experimentos de aplicações em astronomia para análise de formas de galáxias do Sloan Digital Sky Survey não-rotuladas e rotuladas pelo projeto Galaxy Zoo 2 , demonstrando o sucesso da técnica proposta, comparada a abordagens clássicas como Transformada de Fourier e Transformada Wavelet Contínua 2D.
This document describes the PhD thesis entitled Shape Analysis by using Wavelets on Graphs. The addressed theme is related to Computer Vision, particularly to the Characterization, Description and Classication topics. Amongst the methods presented in an extensive literature on Shape Analysis 2D, it is perceived a smaller presence of graph-based methods with arbitrary and irregular topologies. The contributions of this thesis aim at fullling this gap. A methodology based on the following pipeline is proposed: (i) Shape sampling, (ii) Samples structuring in graphs, (iii) Function dened on vertices, (iv) Multiscale analysis of graphs through the Spectral Wavelet Transform, (v) Features extraction from the Wavelet Transforms and (vi) Classication. For the stages (i), (ii), (iii), (v) and (vi), there are numerous possible approaches. One great challenge is to nd a proper combination of approaches from the several available alternatives, which may be able to yield an eective pipeline for our purposes. In particular, for the stage (iii), given a graph representing a shape, the challenge is to identify a feature, which may be dened over the graph vertices. This feature should capture the underlying inuence from the combinatorial structure of the entire network over each vertex, in multiple scales. The Spectral Graph Wavelet Transform will reveal such an underpining inuence over each vertex. Yielded results from experiments on 2D benchmarks shapes widely known in literature, as well as results from astronomy applications to the analysis of unlabeled galaxies shapes from the Sloan Digital Sky Survey and labeled galaxies shapes by the Galaxy Zoo 2 Project are presented, demonstrating the achievements of the proposed technique, in comparison to classic approaches such as the 2D Fourier Transform and the 2D Continuous Wavelet Transform.

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

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

This thesis focuses on spectral-based graph neural networks (GNNs). In Chapter 2, we use multiresolution Haar-like wavelets to design a framework of GNNs which equips with graph convolution and pooling strategies. The resulting model is called MathNet whose wavelet transform matrix is constructed with a coarse-grained chain. So our proposed MathNet not only enjoys the multiresolution analysis from the Haar-like wavelets but also leverages the clustering information of the graph data. Furthermore, we develop a novel multiscale representation system for graph data, called decimated framelets, which form a localized tight frame on the graph in Chapter 3. Based on this, we establish decimated G-framelet transforms for the decomposition and reconstruction of the graph data at multi resolutions via a constructive data-driven filter bank. The graph framelets are built on a chain-based orthonormal basis that supports fast graph Fourier transforms. From this, we give a fast algorithm for the decimated G-framelet transforms, or FGT, that has linear computational complexity O (N) for a graph of size N. Finally, in Chapter 4, we present a new approach for assembling graph neural networks based on the undecimated framelet transforms which provide a multiscale representation for graph-structured data. With the framelet system, we can decompose the graph feature into low-pass and high-pass frequencies as extracted features for network training, which then defines an undecimated-framelet-based graph convolution UFGConv. The framelet decomposition naturally induces a graph pooling strategy UFGPool by aggregating the graph feature into low-pass and high-pass spectra, which considers both the feature values and geometry of the graph data and conserves the total information. Moreover, we propose shrinkage as a new activation for UFGConv, which thresholds the high-frequency information at different scales.

Graph Signal Processing (GSP), as the field concerned with the extension of classical signal processing concepts to the graph domain, is still at the beginning on the path toward providing a generalized theory of signal processing. As such, this thesis aspires to conceive the theory of sparse representations on graphs by traversing the cornerstones of wavelet and sampling theory on graphs. Beginning with the novel topic of graph spline wavelet theory, we introduce families of spline and e-spline wavelets, and associated filterbanks on circulant graphs, which lever- age an inherent vanishing moment property of circulant graph Laplacian matrices (and their parameterized generalizations), for the reproduction and annihilation of (exponen- tial) polynomial signals. Further, these families are shown to provide a stepping stone to generalized graph wavelet designs with adaptive (annihilation) properties. Circulant graphs, which serve as building blocks, facilitate intuitively equivalent signal processing concepts and operations, such that insights can be leveraged for and extended to more complex scenarios, including arbitrary undirected graphs, time-varying graphs, as well as associated signals with space- and time-variant properties, all the while retaining the focus on inducing sparse representations. Further, we shift from sparsity-inducing to sparsity-leveraging theory and present a novel sampling and graph coarsening framework for (wavelet-)sparse graph signals, inspired by Finite Rate of Innovation (FRI) theory and directly building upon (graph) spline wavelet theory. At its core, the introduced Graph-FRI-framework states that any K-sparse signal residing on the vertices of a circulant graph can be sampled and perfectly reconstructed from its dimensionality-reduced graph spectral representation of minimum size 2K, while the structure of an associated coarsened graph is simultaneously inferred. Extensions to arbitrary graphs can be enforced via suitable approximation schemes. Eventually, gained insights are unified in a graph-based image approximation framework which further leverages graph partitioning and re-labelling techniques for a maximally sparse graph wavelet representation.

Biometric identification systems have several distinct advantages over other authentication technologies, such as passwords, in reliably recognising individuals. Iris based recognition is one such biometric recognition system. Unlike other biometrics such as fingerprints or face images, the distinct aspect of the iris comes from its randomly distributed features. The patterns of these randomly distributed features on the iris have been proved to be fixed in a person's lifetime, and are stable over time for healthy eyes except for the distortions caused by the constriction and dilation of the pupil. The distortion of the iris pattern caused by pupillary activity, which is mainly due changes in ambient lighting conditions, can be significant. One important question that arises from this is: How closely do two different iris images of the same person, taken at different times using different cameras, in different environments, and under different lighting conditions, agree with each other? It is also problematic for iris recognition systems to correctly identify a person when his/her pupil size is very different from the person's iris images, used at the time of constructing the system's data-base. To date, researchers in the field of iris recognition have made attempts to address this problem, with varying degrees of success. However, there is still a need to conduct in-depth investigations into this matter in order to arrive at more reliable solutions. It is therefore necessary to study the behaviour of iris surface deformation caused by the change of lighting conditions. In this thesis, a study of the physiological behaviour of pupil size variation under different normal indoor lighting conditions (100 lux ~ 1,200 lux) and brightness levels is presented. The thesis also presents the results of applying Elastic Graph Matching (EGM) tracking techniques to study the mechanisms of iris surface deformation. A study of the pupil size variation under different normal indoor lighting conditions was conducted. The study showed that the behaviour of the pupil size can be significantly different from one person to another under the same lighting conditions. There was no evidence from this study to show that the exact pupil sizes of an individual can be determined at a given illumination level. However, the range of pupil sizes can be estimated for a range of specific lighting conditions. The range of average pupil sizes under normal indoor lighting found was between 3 mm and 4 mm. One of the advantages of using EGM for iris surface deformation tracking is that it incorporates the benefit of the use of Gabor wavelets to encode the iris features for tracking. The tracking results showed that the radial stretch of the iris surface is nonlinear. However, the amount of extension of iris surface at any point on the iris during the stretch is approximately linear. The analyses of the tracking results also showed that the behaviour of iris surface deformation is different from one person to another. This implies that a generalised iris surface deformation model cannot be established for personal identification. However, a deformation model can be established for every individual based on their analysis result, which can be useful for personal verification using the iris. Therefore, analysis of the tracking results of each individual was used to model iris surface deformations for that individual. The model was able to estimate the movement of a point on the iris surface at a particular pupil size. This makes it possible to estimate and construct the 2D deformed iris image of a desired pupil size from a given iris image of another different pupil size. The estimated deformed iris images were compared with their actual images for similarity, using an intensitybased (zero mean normalised cross-correlation). The result shows that 86% of the comparisons have over 65% similarity between the estimated and actual iris image. Preliminary tests of the estimated deformed iris images using an open-source iris recognition algorithm have showed an improved personal verification performance. The studies presented in this thesis were conducted using a very small sample of iris images and therefore should not be generalised, before further investigations are conducted.

Biometric identification systems have several distinct advantages over other authentication technologies, such as passwords, in reliably recognising individuals. Iris based recognition is one such biometric recognition system. Unlike other biometrics such as fingerprints or face images, the distinct aspect of the iris comes from its randomly distributed features. The patterns of these randomly distributed features on the iris have been proved to be fixed in a person's lifetime, and are stable over time for healthy eyes except for the distortions caused by the constriction and dilation of the pupil. The distortion of the iris pattern caused by pupillary activity, which is mainly due changes in ambient lighting conditions, can be significant. One important question that arises from this is: How closely do two different iris images of the same person, taken at different times using different cameras, in different environments, and under different lighting conditions, agree with each other? It is also problematic for iris recognition systems to correctly identify a person when his/her pupil size is very different from the person's iris images, used at the time of constructing the system's data-base. To date, researchers in the field of iris recognition have made attempts to address this problem, with varying degrees of success. However, there is still a need to conduct in-depth investigations into this matter in order to arrive at more reliable solutions. It is therefore necessary to study the behaviour of iris surface deformation caused by the change of lighting conditions. In this thesis, a study of the physiological behaviour of pupil size variation under different normal indoor lighting conditions (100 lux ~ 1,200 lux) and brightness levels is presented. The thesis also presents the results of applying Elastic Graph Matching (EGM) tracking techniques to study the mechanisms of iris surface deformation. A study of the pupil size variation under different normal indoor lighting conditions was conducted. The study showed that the behaviour of the pupil size can be significantly different from one person to another under the same lighting conditions. There was no evidence from this study to show that the exact pupil sizes of an individual can be determined at a given illumination level. However, the range of pupil sizes can be estimated for a range of specific lighting conditions. The range of average pupil sizes under normal indoor lighting found was between 3 mm and 4 mm. One of the advantages of using EGM for iris surface deformation tracking is that it incorporates the benefit of the use of Gabor wavelets to encode the iris features for tracking. The tracking results showed that the radial stretch of the iris surface is nonlinear. However, the amount of extension of iris surface at any point on the iris during the stretch is approximately linear. The analyses of the tracking results also showed that the behaviour of iris surface deformation is different from one person to another. This implies that a generalised iris surface deformation model cannot be established for personal identification. However, a deformation model can be established for every individual based on their analysis result, which can be useful for personal verification using the iris. Therefore, analysis of the tracking results of each individual was used to model iris surface deformations for that individual. The model was able to estimate the movement of a point on the iris surface at a particular pupil size. This makes it possible to estimate and construct the 2D deformed iris image of a desired pupil size from a given iris image of another different pupil size. The estimated deformed iris images were compared with their actual images for similarity, using an intensitybased (zero mean normalised cross-correlation). The result shows that 86% of the comparisons have over 65% similarity between the estimated and actual iris image. Preliminary tests of the estimated deformed iris images using an open-source iris recognition algorithm have showed an improved personal verification performance. The studies presented in this thesis were conducted using a very small sample of iris images and therefore should not be generalised, before further investigations are conducted.

Die Arbeit befasst sich mit der Entwicklung und Anwendung verschiedener Konzepte und Algorithmen zum skalierbaren Live-Streaming von Video sowie deren Umsetzung in der Media Internet Streaming Toolbox. Die Toolbox stellt eine erweiterbare, plattformunabhängige Infrastruktur zur Erstellung aller Teile eines Live-Streamingsystems von der Videogewinnung über die Medienverarbeitung und Codierung bis zum Versand bereit. Im Vordergrund steht die flexible Beschreibung der Medienverarbeitung und Stromerstellung sowie die Erzeugung von klientenindividuellen Stromformaten mit unterschiedlicher Dienstegüte für eine möglichst große Zahl von Klienten und deren Verteilung über das Internet. Es wird ein integriertes graphenbasiertes Konzept entworfen, in dem das Component Encoding Stream Construction, die Verwendung von Compresslets und eine automatisierte Flussgraphenkonstruktion miteinander verknüpft werden. Die für die Stromkonstruktion relevanten Teile des Flussgraphen werden für Gruppen mit identischem Zustand entkoppelt vom Rest ausgeführt. Dies führt zu einer maximalen Rechenlast, die unabhängig von der Zahl der Klienten ist, was sowohl theoretisch gezeigt als auch durch konkrete Messungen bestätigt wird. Als Beispiele für die Verwendung der Toolbox werden unter Anderem zwei waveletbasierte Stromformate entwickelt, integriert und bezüglich Codiereffizienz und Skalierbarkeit miteinander verglichen

Die Arbeit befasst sich mit der Entwicklung und Anwendung verschiedener Konzepte und Algorithmen zum skalierbaren Live-Streaming von Video sowie deren Umsetzung in der Media Internet Streaming Toolbox. Die Toolbox stellt eine erweiterbare, plattformunabhängige Infrastruktur zur Erstellung aller Teile eines Live-Streamingsystems von der Videogewinnung über die Medienverarbeitung und Codierung bis zum Versand bereit. Im Vordergrund steht die flexible Beschreibung der Medienverarbeitung und Stromerstellung sowie die Erzeugung von klientenindividuellen Stromformaten mit unterschiedlicher Dienstegüte für eine möglichst große Zahl von Klienten und deren Verteilung über das Internet. Es wird ein integriertes graphenbasiertes Konzept entworfen, in dem das Component Encoding Stream Construction, die Verwendung von Compresslets und eine automatisierte Flussgraphenkonstruktion miteinander verknüpft werden. Die für die Stromkonstruktion relevanten Teile des Flussgraphen werden für Gruppen mit identischem Zustand entkoppelt vom Rest ausgeführt. Dies führt zu einer maximalen Rechenlast, die unabhängig von der Zahl der Klienten ist, was sowohl theoretisch gezeigt als auch durch konkrete Messungen bestätigt wird. Als Beispiele für die Verwendung der Toolbox werden unter Anderem zwei waveletbasierte Stromformate entwickelt, integriert und bezüglich Codiereffizienz und Skalierbarkeit miteinander verglichen

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

This work applies sparse representations and nonlinear image processing to two inverse imaging problems. The first problem involves image restoration, where the aim is to reconstruct an unknown high-quality image from a low-quality observed image. Sparse representations of images have drawn a considerable amount of interest in recent years. The assumption that natural signals, such as images, admit a sparse decomposition over a redundant dictionary leads to efficient algorithms for handling such sources of data. The standard sparse representation, however, does not consider the intrinsic geometric structure present in the data, thereby leading to sub-optimal results. Using the concept that a signal is block sparse in a given basis —i.e., the non-zero elements occur in clusters of varying sizes — we present a novel and efficient algorithm for learning a sparse representation of natural images, called graph regularized block sparse dictionary (GRBSD) learning. We apply the proposed method towards two image restoration applications: 1) single-Image super-resolution, where we propose a local regression model that uses learned dictionaries from the GRBSD algorithm for super-resolving a low-resolution image without any external training images, and 2) image inpainting, where we use GRBSD algorithm to learn a multiscale dictionary to generate visually plausible pixels to fill missing regions in an image. Experimental results validate the performance of the GRBSD learning algorithm for single-image super-resolution and image inpainting applications. The second problem addressed in this work involves image enhancement for detection and segmentation of objects in images. We exploit the concept that even though data from various imaging modalities have high dimensionality, the data is sufficiently well described using low-dimensional geometrical structures. To facilitate the extraction of objects having such structure, we have developed general structure enhancement methods that can be used to detect and segment various curvilinear structures in images across different applications. We use the proposed method to detect and segment objects of different size and shape in three applications: 1) segmentation of lamina cribrosa microstructure in the eye from second-harmonic generation microscopy images, 2) detection and segmentation of primary cilia in confocal microscopy images, and 3) detection and segmentation of vehicles in wide-area aerial imagery. Quantitative and qualitative results show that the proposed methods provide improved detection and segmentation accuracy and computational efficiency compared to other recent algorithms.

En décembre 2015, les détecteurs LIGO ont pour la première fois détecté une onde gravitationnelle émise lors de la coalescence d'une paire de trous noirs il y a de cela 1.3 milliards d'années. Une telle première dans la toute nouvelle astronomie gravitationnelle a été suivie par plusieurs autres observations. La dernière en date est la fusion de deux étoiles à neutron dont la contrepartie électromagnétique a pu être observée par plusieurs observatoires à travers le monde. A cette occasion, les ondes gravitationnelles se sont inscrites dans l'astronomie multi-messager. Ces observations ont été rendues possibles par des techniques avancées d'analyse de données. Grâce à elles, la faible empreinte laissée par une onde gravitationnelle dans les données de détecteurs peut être isolée. Le travail de cette thèse est dédié au développement d'une technique de détection d'ondes gravitationnelles ne reposant que sur une connaissance minimale du signal à isoler. Le développement de cette méthode consiste plus précisément à introduire une information sur la phase du signal d'onde gravitationnelle selon un contexte astrophysique déterminé. La première partie de cette thèse est consacrée à la présentation de la méthode. Dans une seconde partie cette méthode est appliquée à la recherche de signaux d'ondes gravitationnelles en provenance de systèmes binaires de trous noirs de masse stellaire dans du bruit Gaussien. Puis l'étude est répétée dans du bruit de détecteurs collecté pendant la première période de prise de données. Enfin la troisième partie est dédiée à la recherche de binaires de trous noirs dont l'orbite montre un écart à la géométrie circulaire, ce qui complexifie la morphologie du signal. De telles orbites sont qualifiées d'excentriques. Cette troisième analyse permet d'établir de premiers résultats quant à la méthode proposée lorsque le signal d'intérêt est peu connu
In december 2015 the LIGO detectors have first detected a gravitational wave emitted by a pair of coalescing black holes 1.3 billion years ago. Many more observations have been realised since then and heralded gravitational waves as a new messenger in astronomy. The latest detection is the merge of two neutron stars whose electromagnetic counterpart has been followed up by many observatories around the globe. These direct observations have been made possible by the developpement of advanced data analysis techniques. With them the weak gravitational wave inprint in detectors may be recovered. The realised work during this thesis aims at developping an existing gravitational wave detection method which relies on minimal assumptions of the targeted signal. It more precisely consists in introducing an information on the signal phase depending on the astrophysical context. The first part is dedicated to a presentation of the method. The second one presents the results obtained when applying the method to the search of stellar mass binary black holes in simulated Gaussian noise data. The study is repeated in real instrumental data collected during the first run of LIGO. Finally, the third part presents the method applied in the search for eccentric binary black holes. Their orbit exhibits a deviation from the quasi-circular orbit case considered so far and thus complicates the signal morphology. This third analysis establishes first results with the proposed method in the case of a poorly modeled signal

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

碩士
國立中央大學
數學研究所
95
In recent years along with the advance in technology, using the functions and quality of imaging devices is getting more and more common, how processes the image is quite important. But in examination work, if with human eye judgment graph slight defect, regular session, because artificial subjectively or creates the mistake wearily, therefore in the examination graph slight defect, needs the computer precess image compared and defect inspection. In this thesis , we concentrate in provide a graph compares to the method, use wavelet transform, may have ability to underline in view of the slight defect part. This thesis basis different energy sub-area makes gradually the level –like compared to rightly, may use the primitive image most important part first compared to right, is left over some pictures are enhancing the threshold to do severely compared to the way, like this gradually the level -like compared to the method, the far ratio two picture one by one pixel value makes compares to effectiveness.

碩士
國立交通大學
電機與控制工程學系
86
In this thesis, we use the technology of graph and text segmentationin wavelet coefficients to separate graph and text in color document. Zero-Tree encodes the part of graph-image, and the part of text-image is coded by the method of multi-plain text coding. Color-number, the ratio of projection variance, and fractal dimension which are different in graph and text part of the block give us the information manipulate the segmentation. Because of the characteristic of these three parameters which reveal strong fuzzy property, we develop a fuzzy rule to achieve the purpose of segmentation. The result of program simulation shows that image compression with graph- text segmentation has good performance on high compression ratio in color document. We also discuss the problem of the best bit- rate allocation in color image, the relation between PSNR and the layer number in wavelet transform, and how high-frequency coefficients effect the image quality.

碩士
國立中正大學
資訊工程研究所
89
Traditional region-based image retrieval systems often use only the dominant features within each region and ignore the useful relationship of neighboring regions. In this paper, we propose a new color region-based image retrieval system using the region relationship. An image is first processed with the wavelet transform to divide the image into several subbands and to extract the important texture information. A new color watershed transformation on not only the luminance wavelet coefficients but also the chromatic wavelet coefficients is performed to accurately segment the image into several important regions. Then, the region adjacency graph (RAG) is used to be the representation of the regions and their spatial relationships in the segmented image. In the RAG, a node denotes one region and an edge represents the spatial relationship of two neighboring regions. Hence, the features of regions such as the wavelet coefficients in an image can be recorded in their corresponding nodes within a RAG; while the features of adjacent regions are recorded in the edges. Now, the image retrieval problem is reduced to a subgraph isomorphism algorithm, which is performed to verify the similarity between two graphs. A simple and heuristic algorithm of subgraph isomorphism is applied to compare the query image’s RAG with those RAGs in the image database. In experiments, several query results from the test database that contains various kinds of images are used to evaluate the performance of proposed system.

This dissertation studies the causes and mechanism of power system cascading outages and proposes the improved interactive scheme between system-wide and local levels of monitoring and control to quickly detect, classify and mitigate the cascading outages in power system. A novel method for evaluating the vulnerability of individual components as well as the whole power system, which is named as weighted vulnerability analysis, is developed. Betweenness centrality is used to measure the importance of each bus and transmission line in the modeled power system network, which is in turn used to determine the weights for the weighted vulnerability index. It features fast reaction time and achieves higher accuracy when dealing with the cascading outage detection, classification and mitigation over the traditional methods. The overload problem due to power flow redistribution after one line tripped is a critical factor contributing to the cascading outages. A parallel corridor searching method is proposed to quickly identify the most vulnerable components after tripping a transmission line. The power system topology model can be simplified into state graph after searching the domains for each generator, the commons for each bus, and links between the commons. The parallel corridor will be determined by searching the links and commons in system topology graph for the given state of power system operation. During stressed operating state, either stable or unstable power swing may have impacts on distance relay judgment and lead to relay misoperation, which will result in the power system lines being tripped and as a consequence power system operating state becoming even more stressful. At the local level, an enhanced fault detection tool during power system swing is developed to reduce the chance of relay misoperation. Comprehensive simulation studies have been implemented by using the IEEE 39-bus and 118-bus test systems. The results are promising because: The results from weighted vulnerability analysis could provide better system situational awareness and accurate information about the disturbance; The results form parallel corridor search method could identify the most vulnerable lines after power re-distribution, which will give operator time to take remedial actions; The results from new travelling wave and wavelet transform based fault detection could reduce the impact of relay misoperation.