Detecção de objetos é um problema clássico em visão computacional, presente em aplicações como vigilância automatizada, análise de imagens médicas e recuperação de informação. Dentre as abordagens existentes na literatura para resolver esse problema, destacam-se métodos baseados em reconhecimento de pontos-chave que podem ser interpretados como diferentes implementações de um mesmo arcabouço. O objetivo desta pesquisa de doutorado é desenvolver e avaliar uma versão generalizada desse arcabouço, na qual reconhecimento de pontos-chave é substituído por reconhecimento de grafos-chave. O potencial da pesquisa reside na riqueza de informação que um grafo pode apresentar antes e depois de ser reconhecido. A dificuldade da pesquisa reside nos problemas que podem ser causados por essa riqueza, como maldição da dimensionalidade e complexidade computacional. Três contribuições serão incluídas na tese: a descrição detalhada de um arcabouço para detecção de objetos baseado em grafos-chave, implementações fiéis que demonstram sua viabilidade e resultados experimentais que demonstram seu desempenho. / Object detection is a classic problem in computer vision, present in applications such as automated surveillance, medical image analysis and information retrieval. Among the existing approaches in the literature to solve this problem, we can highlight methods based on keypoint recognition that can be interpreted as different implementations of a same framework. The objective of this PhD thesis is to develop and evaluate a generalized version of this framework, on which keypoint recognition is replaced by keygraph recognition. The potential of the research resides in the information richness that a graph can present before and after being recognized. The difficulty of the research resides in the problems that can be caused by this richness, such as curse of dimensionality and computational complexity. Three contributions are included in the thesis: the detailed description of a keygraph-based framework for object detection, faithful implementations that demonstrate its feasibility and experimental results that demonstrate its performance.

Fractional factorial designs are a popular choice in designing experiments for studying the effects of multiple factors simultaneously. The first step in planning an experiment is the selection of an appropriate fractional factorial design. An appro- priate design is one that has the statistical properties of interest of the experimenter and has a small number of runs. This requires that a catalog of candidate designs be available (or be possible to generate) for searching for the "good" design. In the attempt to generate the catalog of candidate designs, the problem of design isomor- phism must be addressed. Two designs are isomorphic to each other if one can be obtained from the other by some relabeling of factor labels, level labels of each factor and reordering of runs. Clearly, two isomorphic designs are statistically equivalent. Design catalogs should therefore contain only designs unique up to isomorphism. There are two computational challenges in generating such catalogs. Firstly, testing two designs for isomorphism is computationally hard due to the large number of possible relabelings, and, secondly, the number of designs increases very rapidly with the number of factors and run-size, making it impractical to compare all designs for isomorphism. In this dissertation we present a new approach for tackling both these challenging problems. We propose graph models for representing designs and use this relationship to develop efficient algorithms. We provide a new efficient iso- morphism check by modeling the fractional factorial design isomorphism problem as graph isomorphism problem. For generating the design catalogs efficiently we extend a result in graph isomorphism literature to improve the existing sequential design catalog generation algorithm. The potential of the proposed methods is reflected in the results. For 2-level regular fractional factorial designs, we could generate complete design catalogs of run sizes up to 4096 runs, while the largest designs generated in literature are 512 run designs. Moreover, compared to the next best algorithms, the computation times for our algorithm are 98% lesser in most cases. Further, the generic nature of the algorithms makes them widely applicable to a large class of designs. We give details of graph models and prove the results for two classes of designs, namely, 2-level regular fractional factorial designs and 2-level regular fractional factorial split-plot designs, and provide discussions for extensions, with graph models, for more general classes of designs.

Detecção de objetos é um problema clássico em visão computacional, presente em aplicações como vigilância automatizada, análise de imagens médicas e recuperação de informação. Dentre as abordagens existentes na literatura para resolver esse problema, destacam-se métodos baseados em reconhecimento de pontos-chave que podem ser interpretados como diferentes implementações de um mesmo arcabouço. O objetivo desta pesquisa de doutorado é desenvolver e avaliar uma versão generalizada desse arcabouço, na qual reconhecimento de pontos-chave é substituído por reconhecimento de grafos-chave. O potencial da pesquisa reside na riqueza de informação que um grafo pode apresentar antes e depois de ser reconhecido. A dificuldade da pesquisa reside nos problemas que podem ser causados por essa riqueza, como maldição da dimensionalidade e complexidade computacional. Três contribuições serão incluídas na tese: a descrição detalhada de um arcabouço para detecção de objetos baseado em grafos-chave, implementações fiéis que demonstram sua viabilidade e resultados experimentais que demonstram seu desempenho. / Object detection is a classic problem in computer vision, present in applications such as automated surveillance, medical image analysis and information retrieval. Among the existing approaches in the literature to solve this problem, we can highlight methods based on keypoint recognition that can be interpreted as different implementations of a same framework. The objective of this PhD thesis is to develop and evaluate a generalized version of this framework, on which keypoint recognition is replaced by keygraph recognition. The potential of the research resides in the information richness that a graph can present before and after being recognized. The difficulty of the research resides in the problems that can be caused by this richness, such as curse of dimensionality and computational complexity. Three contributions are included in the thesis: the detailed description of a keygraph-based framework for object detection, faithful implementations that demonstrate its feasibility and experimental results that demonstrate its performance.

Beim Graphisomorphieproblem geht es um die Frage, ob zwei Graphen bis auf Knotenumbenennungen die gleiche Struktur haben. Es ist eines der wenigen verbleibenden natürlichen Probleme, für die weder ein Polynomialzeitalgorithmus noch NP-Härte bekannt ist. Aus dieser Situation ist ein Forschungszweig erwachsen, der effiziente Isomorphiealgorithmen für eingeschränkte Graphklassen entwickelt. Der Hauptbeitrag dieser Arbeit besteht in Logspace-Algorithmen, die das Isomorphieproblem für k-Bäume, Intervallgraphen, sowie Helly- und Proper-Kreisbogengraphen lösen. Dies verbessert zuvor bekannte parallele Algorithmen und führt zu einer vollständigen Klassifikation der Komplexität dieser Probleme, da für sie auch Logspace-Härte nachgewiesen wird. Tatsächlich leisten die vorgestellten Algorithmen mehr: Im Fall der k-Bäume berechnet der Algorithmus kanonische Knotenbenennungen mit O(k log n) Platz. Eine alternative Implementation des Algorithmus kommt mit O((k+1)!n) Zeit aus – hierbei ist n die Anzahl der Knoten – und ist damit der schnellste bekannte FPT-Algorithmus für Isomorphie von k-Bäumen. Die Algorithmen für Intervall- und Kreisbogengraphen berechnen kanonische Repräsentationen – das heißt, sie weisen jedem Knoten ein Intervall (beziehungsweise einen Kreisbogen) zu, sodass diese sich genau dann schneiden, wenn die zugehörigen Knoten benachbart sind, und isomorphe Eingabegraphen das gleiche Intervallmodell (beziehungsweise Kreisbogenmodell) erhalten. Außerdem werden auch Logspace-Algorithmen angegeben, die Intervallrepräsentationen mit zusätzlichen Eigenschaften berechnen – oder erkennen, dass dies nicht möglich ist: Für die resultierenden Intervallmodelle kann gefordert werden, dass sie proper sind (also kein Intervall ein anderes enthält), dass sie unit sind (also alle Intervalle die gleiche Länge haben) oder dass die Längen der paarweisen Schnitte (und optional der einzelnen Intervalle) vorgegebenen Werten entsprechen. / The graph isomorphism problem deals with the question if two graphs have the same structure up to renaming their vertices. It is one of the few remaining natural problems for which neither a polynomial-time algorithm nor NP-hardness is known. This situation has led to a branch of research that develops efficient algorithms for special cases of the graph isomorphism problem, where the input graphs are required to be from restricted graph classes. The main contribution of this thesis comprises of logspace algorithms that solve the isomorphism problem for k-trees, interval graphs, Helly circular-arc graphs and proper circular-arc graphs. This improves previously known parallel algorithms and leads to a complete classification of the complexity of these problems, as they are also shown to be hard for logspace. In fact, these algorithms achieve more: In the case of k-trees, the algorithm computes canonical labelings in space O(k log n). An alternative implementation runs in time O((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism. The algorithms for interval and circular-arc graphs actually compute canonical representations, i.e., each vertex is assigned an interval (or arc) such that these intersect each other if and only if the corresponding vertices are adjacent, and isomorphic input graphs receive the same interval (or arc) model. This thesis also presents logspace algorithms that compute interval representations with additional properties, or detect that this is not possible: The resulting interval models can be required to be proper (no interval contains another), unit (all intervals have the same length), or to satisfy prescribed lengths for pairwise intersections (and possibly prescribed lengths of intervals).

Made available in DSpace on 2015-03-04T18:50:59Z (GMT). No. of bitstreams: 1 thesis.pdf: 520664 bytes, checksum: a8423486c7ffd3a3ceff9cb2b60761ce (MD5) Previous issue date: 2008-03-14 / Fundação Carlos Chagas Filho de Amparo a Pesquisa do Estado do Rio de Janeiro / The graph isomorphism problem has applications in several areas of science. This problem has not an efficient solution to its general case. In this work, we present the basic concepts of group theory, graph theory and quantum mechanics. We introduce the hidden subgroup problem and a known polynomial reduction of the graph isomorphism problem in its general case to the hidden subgroup problem on the symmetric group. We use a method that reduces the graph isomorphism problem to the group intersection problem. This method combines results from quantum computing and solvable group theory providing a efficient solution through a quantum algorithm to the graph isomorphism problem for the particular class of graphs. / O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos.

Orientador: Prof. Dr. Daniel Morgato Martin / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciências da Computação, 2014. / Neste trabalho estudamos o Problema do Isomorfismo de Grafos e a sua complexidade para resolvê-lo. Nossa principal contribuição é a proposta de um algoritmo para o caso geral do Problema, baseado no particionamento do conjunto de vértices e em emparelhamentos perfeitos de grafos bipartidos. Estudamos também o algoritmo de Brendan McKay, que é o mais rápido algoritmo para o Problema do Isomorfismo de Grafos conhecido. Ao final, implementamos o algoritmo proposto nesta dissertação e o algoritmo de McKay. Após a comparação dos dois algoritmos, verificamos que os resultados obtidos pelo algoritmo proposto não foram satisfatórios, porém apresentamos possíveis melhorias de como deixá-lo mais eficiente. / In this work we study the Graph Isomorphism Problem and their complexity to solve it. Our main contribution is to propose an algorithm for the general case of the Problem, based on partitioning the set vertex and perfect matchings of bipartite graphs. We also studied the Brendan McKay¿s algorithm, who is the fastest algorithm for the Graph Isomorphism Problem known. At the end, we implemented the algorithm proposed in this dissertation and McKay¿s algorithm. After comparison of the two algorithms, we found that the results obtained by the proposed algorithm were not satisfactory, but improvements are possible as to make it more efficient.

O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos. / The graph isomorphism problem has applications in several areas of science. This problem has not an efficient solution to its general case. In this work, we present the basic concepts of group theory, graph theory and quantum mechanics. We introduce the hidden subgroup problem and a known polynomial reduction of the graph isomorphism problem in its general case to the hidden subgroup problem on the symmetric group. We use a method that reduces the graph isomorphism problem to the group intersection problem. This method combines results from quantum computing and solvable group theory providing a efficient solution through a quantum algorithm to the graph isomorphism problem for the particular class of graphs.

Made available in DSpace on 2016-12-23T14:33:41Z (GMT). No. of bitstreams: 1 Dissertacao de Philippe Leal Freire dos Santos.pdf: 1222437 bytes, checksum: 0b5ab3d6e8b9f4b4640e53168b2d042d (MD5) Previous issue date: 2010-08-23 / In this work we investigated the use of concepts from Spectral Graph Theory (SGT) to support the construction of algorithms that solve the Graph Isomorphism Problem (GIP). Three theoretical results which consider information from the spectrum of the graphs and from the eigenvector centralities were presented. Furthermore, an algorithm for detection of graph isomorphism based on two of these results was proposed. Finally, we present the computational results comparing this algorithm with others from literature. / Neste trabalho investigamos a utilização de conceitos da Teoria Espectral de Grafos (TEG) a fim de auxiliar a construção de algoritmos que solucionem o Problema de Isomorfismo de Grafos (PIG). Três resultados teóricos que consideram informações do espectro e das centralidades de autovetor dos vértices dos grafos foram apresentados. Além disso, foi proposto um algoritmo para detecção de isomorfismo de grafos baseado em dois destes resultados. Por fim, apresentamos os resultados computacionais da comparação deste algoritmo com outros da literatura

Le problème d’´équivalence de code joue un rôle important dans la théorie de code et la cryptographie basée sur le code. Cela est dû à son importance dans la classification des codes ainsi que dans la construction et la cryptanalyse des cryptosystèmes à base de codes. Il est également lié à un problème ouvert d’isomorphisme de graphes, un problème bien connu dans le domaine de la théorie de la complexité. Nous prouvons pour les codes ayant un hull trivial qu’il existe une réduction polynomiale de l’équivalence par permutation de codes à l’isomorphisme de graphes. Cela montre que cette sous-classe d’équivalence de permutation n’est pas plus dure que l’isomorphisme de graphes. Nous introduisons une nouvelle méthode pour résoudre le problème d’équivalence de code. Nous développons des approches algébriques pour résoudre le problème dans ses deux versions : en permutation et en diagonale. Nous construisons un système algébrique en établissant des relations entre les matrices génératrices et les matrices de parité des codes équivalents. Nous nous retrouvons avecun système plusieurs variables d’équations linéaires et quadratiques qui peut être résolu en utilisant des outils algébriques tels que les bases de Groebner et les techniques associées. Il est possible en théorie de résoudre l’équivalence de code avec des techniques utilisant des bases de Groebner. Cependant, le calcul en pratique devient complexe à mesure que la longueur du code augmente. Nous avons introduit plusieurs améliorations telles que la linéarisation par bloc et l’action de Frobenius. En utilisant ces techniques, nous identifions de nombreux cas où le problème d’équivalence de permutation peut être résolu efficacement. Notre méthode d’équivalence diagonale résout efficacement le problème dans les corps de petites tailles, à savoir F3 et F4. L’augmentation de la taille du corps entraîne une augmentation du nombre de variables dans notre système algébrique, ce qui le rend difficile à résoudre. Nous nous intéressons enfin au problème d’isomorphisme de graphes en considérant un système algébrique quadratique pour l’isomorphisme de graphes. Pour des instances tirées aléatoirement, le système possède des propriétés intéressantes en termes de rang de la partie linéaire et du nombre de variables. Nousrésolvons efficacement le problème d’isomorphisme de graphes pour des graphes aléatoires avec un grand nombre de sommets, et également pour certains graphes réguliers tels que ceux de Petersen, Cubical et Wagner.123 / Code equivalence problem plays an important role in coding theory and code based cryptography.That is due to its significance in classification of codes and also construction and cryptanalysis of code based cryptosystems. It is also related to the long standing problem of graph isomorphism, a well-known problem in the world of complexity theory. We introduce new method for solving code equivalence problem. We develop algebraic approaches to solve the problem in its permutation and diagonal versions. We build algebraic system by establishing relations between generator matrices and parity check matrices of the equivalent codes. We end up with system of multivariables of linear and quadratic equations which can be solved using algebraic tools such as Groebner basis and related techniques. By using Groebner basis techniques we can solve the code equivalence but the computation becomes complex as the length of the code increases. We introduced several improvements such as block linearization and Frobenius action. Using these techniques we identify many cases where permutation equivalence problem can be solved efficiently. Our method for diagonal equivalence solves the problem efficiently in small fields, namely F3 and F4. The increase in the field size results in an increase in the number of variables in our algebraic system which makes it difficult to solve. We introduce a new reduction from permutation code equivalence when the hull is trivial to graph isomorphism. This shows that this subclass of permutation equivalence is not harder than graph isomorphism.Using this reduction we obtain an algebraic system for graph isomorphism with interesting properties in terms of the rank of the linear part and the number of variables. We solve the graph isomorphism problem efficiently for random graphs with large number of vertices and also for some regular graphs such as Petersen, Cubical and Wagner Graphs.

No description available.