A identificação de formas apresenta inúmeras aplicações na área de visão computacional, pois representa uma poderosa ferramenta para analisar as características de um objeto. Dentre as aplicações, podemos citar como exemplos a interação entre humanos e robôs, com a identificação de ações e comandos, e a análise de comportamento para vigilância com a biometria não invasiva. Em nosso trabalho nós desenvolvemos um novo descritor de formas 2D baseado na utilização de redes complexas e teoria espectral de grafos. O contorno da forma de um objeto é representado por uma rede complexa, onde cada ponto pertencente a forma será representado por um vértice da rede. Utilizando uma dinâmica gerada artificialmente na rede complexa, podemos definir uma série de matrizes de adjacência que refletem a dinâmica estrutural da forma do objeto. Cada matriz tem seu espectro calculado, e os principais autovalores são utilizados na construção de um vetor de características. Esse vetor, após aplicar as operações de módulo e normalização, torna-se nossa assinatura espectral de forma. Os principais autovalores de um grafo estão relacionados com propriedades topológicas do mesmo, o que permite sua utilização na descrição da forma de um objeto. Para validar nosso método, nós realizamos testes quanto ao seu comportamento frente a transformações de rotação e escala e estudamos seu comportamento quanto à contaminação das formas por ruído Gaussiano e quanto ao efeito de oclusões parciais. Utilizamos diversas bases de dados comumente utilizadas na literatura de análise de formas para averiguar a eficiência de nosso método em tarefas de recuperação de informação. Concluímos o trabalho com a análise qualitativa do comportamento de nosso método frente a diferentes curvas e estudando uma aplicação na análise de sequências de caminhada. Os resultados obtidos em comparação aos outros métodos mostram que nossa assinatura espectral de forma apresenta bom resultados na precisão de recuperação de informação, boa tolerância a contaminação das formas por ruído e oclusões parciais, e capacidade de distinguir ações humanas e identificar os ciclos de uma sequência de caminhada. / The shape is a powerful feature to characterize an object and the shape analysis has several applications in computer vision area. We can cite the interaction between human and robots, surveillance, non-invasive biometry and human actions identifications among other applications. In our work we have developed a new 2d shape descriptor based on complex network and spectral graph theory. The contour shape of an object is represented by a complex network, where each point belonging shape is represented by a vertex of the network. A set of adjacencies matrices is generated using an artificial dynamics in the complex network. We calculate the spectrum of each adjacency matrix and the most important eigenvalues are used in a feature vector. This vector, after applying module and normalization operations, becomes our spectral shape signature. The principal eigenvalues of a graph are related to its topological properties. This allows us use eigenvalues to describe the shape of an object. We have used shape benchmarks to measure the information retrieve precision of our method. Besides that, we have analyzed the response of the spectral shape signature under noise, rotation and occlusions situations. A qualitative study of the method behavior has been done using curves and a walk sequence. The achieved comparative results to other methods found in the literature show that our spectral shape signature presents good results in information retrieval tasks, good tolerance under noise and partial occlusions situation. We present that our method is able to distinguish human actions and identify the cycles of a walk sequence.

La problèmatique dont nous nous occupons dans cette thèse est la classification automatique d'images bidimensionnelles, ainsi que la détection d'objets génériques dans des images. Les avancées de ce champ de recherche contribuent à l'élaboration de systèmes intelligents, tels que des robots autonomes et la création d'un web sémantique. Dans ce contexte, la conception de représentations d'images et de classificateurs appropriés constituent des problèmes ambitieux. Notre travail de recherche fournit des solutions à ces deux problèmes, que sont la représentation et la classification d'images. Afin de générer notre représentation d'image, nous extrayons des attributs visuels de l'image et construisons une structure de graphe basée sur les propriétés liées au relations de proximités entre les points d'intérêt associés. Nous montrons que certaines propriétés spectrales de ces graphes constituent de bons invariants aux classes de transformations géométriques rigides. Notre représentation d'image est basée sur ces propriétés. Les résultats expérimentaux démontrent que cette représentation constitue une amélioration par rapport à d'autres représentations similaires, mais qui n'intègrent pas les informations liées à l'organisation spatiale des points d'intérêt. Cependant, un inconvénient de cette méthode est qu'elle fait appel à une quantification (avec pertes) de l'espace des attributs visuels afin d'être combinée avec un classificateur Support Vecteur Machine (SVM) efficace. Nous résolvons ce problème en créant un nouveau classificateur, basé sur la distance au plus proche voisin, et qui permet la classification d'objets assimilés à des ensembles de points. La linéarité de ce classificateur nous permet également de faire de la détection d'objet, en plus de la classification d'images. Une autre propriété intéressante de ce classificateur est sa capacité à combiner différents types d'attributs visuels de manière optimale. Nous utilisons cette propriété pour formuler le problème de classification de graphes de manière différente. Les expériences, menées sur une grande variété de jeux de données, montrent les bénéfices quantitatifs de notre approche. / We are concerned in this thesis by the problem of automated 2D image classification and general object detection. Advances in this field of research contribute to the elaboration of intelligent systems such as, but not limited to, autonomous robots and the semantic web. In this context, designing adequate image representations and classifiers for these representations constitute challenging issues. Our work provides innovative solutions to both these problems: image representation and classification. In order to generate our image representation, we extract visual features from the image and build a graphical structure based on properties of spatial proximity between the feature points. We show that certain spectral properties of this graph constitute good invariants to rigid geometric transforms. Our representation is based on these invariant properties. Experiments show that this representation constitutes an improvement over other similar representations that do not integrate the spatial layout of visual features. However, a drawback of this method is that it requires a lossy quantisation of the visual feature space in order to be combined with a state-of-the-art support vector machine (SVM) classifier. We address this issue by designing a new classifier. This generic classifier relies on a nearest-neighbour distance to classify objects that can be assimilated to feature sets, i.e: point clouds. The linearity of this classifier allows us to perform object detection, in addition to image classification. Another interesting property is its ability to combine different types of visual features in an optimal manner. We take advantage of this property to produce a new formulation for the classification of visual feature graphs. Experiments are conducted on a wide variety of publicly available datasets to justify the benefits of our approach.

abstract: The Kuramoto model is an archetypal model for studying synchronization in groups of nonidentical oscillators where oscillators are imbued with their own frequency and coupled with other oscillators though a network of interactions. As the coupling strength increases, there is a bifurcation to complete synchronization where all oscillators move with the same frequency and show a collective rhythm. Kuramoto-like dynamics are considered a relevant model for instabilities of the AC-power grid which operates in synchrony under standard conditions but exhibits, in a state of failure, segmentation of the grid into desynchronized clusters. In this dissertation the minimum coupling strength required to ensure total frequency synchronization in a Kuramoto system, called the critical coupling, is investigated. For coupling strength below the critical coupling, clusters of oscillators form where oscillators within a cluster are on average oscillating with the same long-term frequency. A unified order parameter based approach is developed to create approximations of the critical coupling. Some of the new approximations provide strict lower bounds for the critical coupling. In addition, these approximations allow for predictions of the partially synchronized clusters that emerge in the bifurcation from the synchronized state. Merging the order parameter approach with graph theoretical concepts leads to a characterization of this bifurcation as a weighted graph partitioning problem on an arbitrary networks which then leads to an optimization problem that can efficiently estimate the partially synchronized clusters. Numerical experiments on random Kuramoto systems show the high accuracy of these methods. An interpretation of the methods in the context of power systems is provided. / Dissertation/Thesis / Doctoral Dissertation Applied Mathematics 2018

A identificação de formas apresenta inúmeras aplicações na área de visão computacional, pois representa uma poderosa ferramenta para analisar as características de um objeto. Dentre as aplicações, podemos citar como exemplos a interação entre humanos e robôs, com a identificação de ações e comandos, e a análise de comportamento para vigilância com a biometria não invasiva. Em nosso trabalho nós desenvolvemos um novo descritor de formas 2D baseado na utilização de redes complexas e teoria espectral de grafos. O contorno da forma de um objeto é representado por uma rede complexa, onde cada ponto pertencente a forma será representado por um vértice da rede. Utilizando uma dinâmica gerada artificialmente na rede complexa, podemos definir uma série de matrizes de adjacência que refletem a dinâmica estrutural da forma do objeto. Cada matriz tem seu espectro calculado, e os principais autovalores são utilizados na construção de um vetor de características. Esse vetor, após aplicar as operações de módulo e normalização, torna-se nossa assinatura espectral de forma. Os principais autovalores de um grafo estão relacionados com propriedades topológicas do mesmo, o que permite sua utilização na descrição da forma de um objeto. Para validar nosso método, nós realizamos testes quanto ao seu comportamento frente a transformações de rotação e escala e estudamos seu comportamento quanto à contaminação das formas por ruído Gaussiano e quanto ao efeito de oclusões parciais. Utilizamos diversas bases de dados comumente utilizadas na literatura de análise de formas para averiguar a eficiência de nosso método em tarefas de recuperação de informação. Concluímos o trabalho com a análise qualitativa do comportamento de nosso método frente a diferentes curvas e estudando uma aplicação na análise de sequências de caminhada. Os resultados obtidos em comparação aos outros métodos mostram que nossa assinatura espectral de forma apresenta bom resultados na precisão de recuperação de informação, boa tolerância a contaminação das formas por ruído e oclusões parciais, e capacidade de distinguir ações humanas e identificar os ciclos de uma sequência de caminhada. / The shape is a powerful feature to characterize an object and the shape analysis has several applications in computer vision area. We can cite the interaction between human and robots, surveillance, non-invasive biometry and human actions identifications among other applications. In our work we have developed a new 2d shape descriptor based on complex network and spectral graph theory. The contour shape of an object is represented by a complex network, where each point belonging shape is represented by a vertex of the network. A set of adjacencies matrices is generated using an artificial dynamics in the complex network. We calculate the spectrum of each adjacency matrix and the most important eigenvalues are used in a feature vector. This vector, after applying module and normalization operations, becomes our spectral shape signature. The principal eigenvalues of a graph are related to its topological properties. This allows us use eigenvalues to describe the shape of an object. We have used shape benchmarks to measure the information retrieve precision of our method. Besides that, we have analyzed the response of the spectral shape signature under noise, rotation and occlusions situations. A qualitative study of the method behavior has been done using curves and a walk sequence. The achieved comparative results to other methods found in the literature show that our spectral shape signature presents good results in information retrieval tasks, good tolerance under noise and partial occlusions situation. We present that our method is able to distinguish human actions and identify the cycles of a walk sequence.

Orientador: Marco Antonio Garcia de Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-17T11:47:27Z (GMT). No. of bitstreams: 1 Ferreira_AnselmoCasteloBranco_M.pdf: 7338510 bytes, checksum: 593cb683d0380e0c894f0147a4129c77 (MD5) Previous issue date: 2011 / Resumo: O particionamento de grafos tem sido amplamente utilizado como meio de segmentação de imagens. Uma das formas de particionar grafos é por meio de uma técnica conhecida como Corte Normalizado, que analisa os autovetores da matriz laplaciana de um grafo e utiliza alguns deles para o corte. Essa dissertação propõe o uso de Corte Normalizado em grafos originados das modelagens por Quadtree e Árvore dos Componentes a fim de realizar segmentação de imagens. Experimentos de segmentação de imagens por Corte Normalizado nestas modelagens são realizados e um benchmark específico compara e classifica os resultados obtidos por outras técnicas propostas na literatura específica. Os resultados obtidos são promissores e nos permitem concluir que o uso de outras modelagens de imagens por grafos no Corte Normalizado pode gerar melhores segmentações. Uma das modelagens pode inclusive trazer outro benefício que é gerar um grafo representativo da imagem com um número menor de nós do que representações mais tradicionais / Abstract: The graph partitioning has been widely used as a mean of image segmentation. One way to partition graphs is through a technique known as Normalized Cut, which analyzes the graph's Laplacian matrix eigenvectors and uses some of them for the cut. This work proposes the use of Normalized Cut in graphs generated by structures based on Quadtree and Component Tree to perform image segmentation. Experiments of image segmentation by Normalized Cut in these models are made and a specific benchmark compares and ranks the results obtained by other techniques proposed in the literature. The results are promising and allow us to conclude that the use of other image graph models in the Normalized Cut can generate better segmentations. One of the structures can also bring another benefit that is generating an image representative graph with fewer graph nodes than the traditional representations / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Orientadores: Carlile Campos Lavor, Leonardo Silva de Lima / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-26T08:31:47Z (GMT). No. of bitstreams: 1 Amaro_BrunoDias_D.pdf: 1369520 bytes, checksum: a36663d5fd23193d66bb22c83cb932aa (MD5) Previous issue date: 2014 / Resumo: A Teoria Espectral de Grafos é um ramo da Matemática Discreta que se preocupa com a relação entre as propriedades algébricas do espectro de certas matrizes associadas a grafos, como a matriz de adjacência, laplaciana ou laplaciana sem sinal e a topologia dos mesmos. Os autovalores e autovetores das matrizes associadas a um grafo são os invariantes que formam o autoespaço de grafos. Em Teoria Espectral de Grafos a conjectura proposta por Brouwer e Haemers, que associa a soma dos k maiores autovalores da matriz Laplaciana de um grafo G com seu número de arestas mais um fator combinatório (que depende do valor k adotado) é uma das questões interessantes e que está em aberto na literatura. Essa mostra diversos trabalhos que tentam provar tal conjectura. Em 2013, Ashraf et al. estenderam essa conjectura para a matriz laplaciana sem sinal e provaram que ela é válida para a soma dos 2 maiores autovalores e que também é válida para todo k, caso o grafo seja regular. Nosso trabalho aborda a versão dessa conjectura para a matriz laplaciana sem sinal. Conseguimos obter uma família de grafos que satisfaz a conjectura para a soma dos 3 maiores autovalores da matriz laplaciana sem sinal e a família de grafos split completo mais uma aresta satisfaz a conjectura para todos os autovalores. Ainda, baseado na desigualdade de Schur, conseguimos mostrar que a soma dos k menores autovalores das matrizes laplaciana e laplaciana sem sinal são limitadas superiormente pela soma dos k menores graus de G / Abstract: The Spectral Graph Theory is a branch of Discrete Mathematics that is concerned with relations between the algebraic properties of spectrum of some matrices associated to graphs, as the Adjacency, Laplacian and signless Laplacian matrices and their respective topologies. The eigenvalues and eigenvectors of matrices associated to graphs are the invariants which constitute the eigenspace of graphs. On Spectral Graph Theory the conjecture proposed by Brouwer and Haemers, associating the sum of k largest eigenvalues of Laplacian matrix of a graph G with its edges numbers plus a combinatorial factor (which depends on the choosed k) is an open interesting question in the Literature. There are several works that attempt to prove this conjecture. In 2013, Ashraf et al. stretch the conjecture out to signless Laplacian matrix and proved that it is true for the sum of the 2 largest eigenvalues of signless Laplacian matrix and it is also true for all k if G is a regular graph. Our work approaches on the version of the conjecture concerning to signless Laplacian matrix. We could obtain a family of graphs which satisfies the conjecture for the sum of the 3 largest eigenvalues of signless Laplacian matrix and we prove that the family of complete split graphs plus one edge satisfies the Conjecture for all eigenvalues. Moreover, based on Schur's inequality, we could show that the sum of the k smallest eigenvalues of Laplacian and signless Laplacian matrices are bounded by the sum of the k smallest degrees of G / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

In this thesis, we bring forward the study of the spectral properties of graphs and we extend this theory for chemical hypergraphs, a new class of hypergraphs that model chemical reaction networks.

<p>Evolutionary dynamics can be notoriously complex and difficult to analyze. In this dissertation I describe a population genetic regime where the dynamics are simple enough to allow a relatively complete and elegant treatment. Consider a haploid, asexual population, where each possible genotype has been assigned a fitness. When mutations enter a population sufficiently rarely, we can model the evolution of this population as a Markov chain where the population jumps from one genotype to another at the birth of each new mutant destined for fixation. Furthermore, if the mutation rates are assigned in such a manner that the Markov chain is reversible when all genotypes are assigned the same fitness, then it is still reversible when genotypes are assigned differing fitnesses. </p><p>The key insight is that this Markov chain can be analyzed using the spectral theory of finite-state, reversible Markov chains. I describe the spectral decomposition of the transition matrix and use it to build a general framework with which I address a variety of both classical and novel topics. These topics include a method for creating low-dimensional visualizations of fitness landscapes; a measure of how easy it is for the evolutionary process to `find' a specific genotype or phenotype; the index of dispersion of the molecular clock and its generalizations; a definition for the neighborhood of a genotype based on evolutionary dynamics; and the expected fitness and number of substitutions that have occurred given that a population has been evolving on the fitness landscape for a given period of time. I apply these various analyses to both a simple one-codon fitness landscape and to a large neutral network derived from computational RNA secondary structure predictions.</p> / Dissertation

Analysis of large networks in biology, science, technology and social systems have become very popular recently. These networks are mathematically represented as graphs. The task is then to extract relevant qualitative information about the empirical networks from the analysis of these graphs. It was found that a graph can be conveniently represented by the spectrum of a suitable difference operator, the normalized graph Laplacian, which underlies diffusions and random walks on graphs. When applied to large networks, this requires computation of the spectrum of large matrices. The normalized Laplacian matrices representing large networks are usually sparse and unstructured. The thesis consists in a systematic evaluation of the available eigenvalue solvers for nonsymmetric large normalized Laplacian matrices describing directed graphs of empirical networks. The methods include several Krylov subspace algorithms like implicitly restarted Arnoldi method, Krylov-Schur method and Jacobi-Davidson methods which are freely available as standard packages written in MATLAB or SLEPc, in the library written C++. The normalized graph Laplacian as employed here is normalized such that its spectrum is confined to the range [0, 2]. The eigenvalue distribution plays an important role in network analysis. The numerical task is then to determine the whole spectrum with appropriate eigenvalue solvers. A comparison of the existing eigenvalue solvers is done with Paley digraphs with known eigenvalues and for citation networks in sizes 400, 1100 and 4500 by computing the residuals.

Military analysis is becoming more reliant on constructive simulations for campaign modeling. Requirements for force-level capabilities, distributed command and control architectures, network centric operations, and increased levels of systems and operational integration are straining the analysis tools of choice. The models constructed are becoming more complex, both in terms of their composition and their behavior. They are complex in their composition because they are constituted from a large number of entities that interact nonlinearly through non-trivial networks and in their behavior because they display emergent characteristics. The modeling and simulation paradigm of choice for analyzing these systems of systems has been agent-based modeling and simulation. This construct is the most capable in terms of the characteristics of complex systems that it can capture, but it is the most demanding to construct, execute, verify and validate. This thesis is focused around two objectives. The first is to study the possibility of being able to compare two or more large-scale system architectures' capabilities without resorting to full-scale agent-based modeling and simulation. The second objective is to support the quantitative identification of the critical systems that compose the large-scale system architecture. The second objective will be crucial in the cases where a constructive simulation is the only option to capture the required behaviors of the complex system being studied. The enablers for this thesis are network modeling, graph theory, and in particular, spectral graph theory. The first hypothesis, stemmed from the first objective, states that if the capability of an architecture can be described as a series of functional cycles through the systems that compose them, then a simple network modeling construct can be employed to compare the different architectures' capabilities. The objective led to the second hypothesis, which states that a ranking based on the spectral characteristics of the network of functional interactions indicates the most critical systems. If modeling effort is focused on these systems, then the modeler can obtain the maximum fidelity model for the minimum effort.