No description available.

Among the vital problems in a variety of emerging applications is the graph matching problem, which is to determine whether two graphs are similar, and if so, find all the valid matches in one graph for the other, based on specified metrics. Traditional graph matching approaches are mostly based on graph homomorphism and isomorphism, falling short of capturing both structural and semantic similarity in real life applications. Moreover, it is preferable while difficult to find all matches with high accuracy over complex graphs. Worse still, the graph structures in real life applications constantly bear modifications. In response to these challenges, this thesis presents a series of approaches for ef?ciently solving graph matching problems, over both static and dynamic real life graphs. Firstly, the thesis extends graph homomorphism and subgraph isomorphism, respectively, by mapping edges from one graph to paths in another, and by measuring the semantic similarity of nodes. The graph similarity is then measured by the metrics based on these extensions. Several optimization problems for graph matching based on the new metrics are studied, with approximation algorithms having provable guarantees on match quality developed. Secondly, although being extended in the above work, graph matching is defined in terms of functions, which cannot capture more meaningful matches and is usually hard to compute. In response to this, the thesis proposes a class of graph patterns, in which an edge denotes the connectivity in a data graph within a predefined number of hops. In addition, the thesis defines graph pattern matching based on a notion of bounded simulation relation, an extension of graph simulation. With this revision, graph pattern matching is in cubic-time by providing such an algorithm, rather than intractable. Thirdly, real life graphs often bear multiple edge types. In response to this, the thesis further extends and generalizes the proposed revisions of graph simulation to a more powerful case: a novel set of reachability queries and graph pattern queries, constrained by a subclass of regular path expressions. Several fundamental problems of the queries are studied: containment, equivalence and minimization. The enriched reachability query does not increase the complexity of the above problems, shown by the corresponding algorithms. Moreover, graph pattern queries can be evaluated in cubic time, where two such algorithms are proposed. Finally, real life graphs are frequently updated with small changes. The thesis investigates incremental algorithms for graph pattern matching defined in terms of graph simulation, bounded simulation and subgraph isomorphism. Besides studying the results on the complexity bounds, the thesis provides the experimental study verifying that these incremental algorithms significantly outperform their batch counterparts in response to small changes, using real-life data and synthetic data.

Sequential mammograms contain important information, such as changes of the breast or developments of the masses, for diagnosis of disease. Comparison of sequential mammograms plays an important part for radiologists in identifying malignant masses. However, currently computer-aided detection (CAD) programs can not use such information eciently. The diculties lie in the registration of sequential mammograms. Most of current methods register sequential mammograms based on control points and image transformations. For these methods to work, extraction and correspondence of the control points is essential. This thesis presents a new approach in registering mammograms. The proposed method registers mammograms by associating mass-like objects in sequential mammograms directly. The mass-like objects appear in the images of normal breasts as well as images of breast with cancer. When the mass-like objects in sequential mammograms are accurately associated, measurements of changes in mass-like objects over time become possible. This is an important way to distinguish mass-like objects associated with cancer from cysts or other benign objects. The proposed method is based on graph matching. It uses the internal structure of the breast represented by the spatial relation between the mass-like objects to establish a correspondence between the sequential mammograms. In this method, the mammogram is firstly segmented into separate components using an adaptive pyramid (AP) segmentation algorithm. A series of filters, based on the features of components, is then applied to the components to remove the undesired ones. The remaining components, the mass-like objects, are represented by a complete graph. The spatial relations between the remaining mass-like objects are expressed by fuzzy spatial relation representation and are associated to the edges of the graph as weights. Association of the mass-like objects of two sequential mammograms is realized by finding a common subgraph of the corresponding two graphs using the backtrack algorithm. The segmentation methods developed in the course of this work were tested on a separate problem in computer-aided detection of breast cancer, namely the automatic extraction of the pectoral muscle. The graph matching method was tested independently of the segmentation method on artificially distorted mammograms and the full process, including the segmentation and the graph matching, was evaluated on 95 temporal mammogram pairs. The present implementation indicates only a small improvement in cancer detection rates but also presents opportunities for a substantial development of the basic method in the future.

L'objectiu d'aquesta tesis es crear o adaptar models de programació per a fer els processadors multi-core accessibles per a la majoria de programadors. Aquest objectiu inclou la possibilitat de reusar els algoritmes existents, la capacitat de depuració, I la capacitat d'introduir els canvis de forma incremental. Contrastem les solucions proposades en diversos tipus de multi-core, incloent sistemes homogenis i heterogenis, i sistemes de memòria compartida i memòria distribuïda. A més a més contribuïm exposant algorismes i programes reals i ensenyant com aquests es poden ser usat per aplicacions en temps quasi real. / The aim of this thesis is to create or adapt a programming model in order to make multi-core processors accessible by almost every programmer. This objective includes existing codes and algorithms reuse, debuggability, and the capacity to introduce changes incrementally. We face multi-cores with many architectures including homogeneity versus heterogeneity and shared-memory versus distributed-memory. We also contribute by exposing real algorithms and programs and showing how some of them can be used for quasi realtime applications.

En aplicaciones de reconocimiento de patrones, los grafos con atributos son en gran medida apropiados. Normalmente, los vértices de los grafos representan partes locales de los objetos i las aristas relaciones entre estas partes locales. No obstante, estas ventajas vienen juntas con un severo inconveniente, la distancia entre dos grafos no puede ser calculada en un tiempo polinómico. Considerando estas características especiales el uso de los prototipos de grafos es necesariamente omnipresente. Las aplicaciones de los prototipos de grafos son extensas, siendo las más habituales clustering, clasificación, reconocimiento de objetos, caracterización de objetos i bases de datos de grafos entre otras. A pesar de la diversidad de aplicaciones de los prototipos de grafos, el objetivo del mismo es equivalente en todas ellas, la representación de un conjunto de grafos. Para construir un prototipo de un grafo todos los elementos del conjunto de enteramiento tienen que ser etiquetados comúnmente. Este etiquetado común consiste en identificar que nodos de que grafos representan el mismo tipo de información en el conjunto de entrenamiento. Una vez este etiquetaje común esta hecho, los atributos locales pueden ser combinados i el prototipo construido. Hasta ahora los algoritmos del estado del arte para calcular este etiquetaje común mancan de efectividad o bases teóricas. En esta tesis, describimos formalmente el problema del etiquetaje global i mostramos una taxonomía de los tipos de algoritmos existentes. Además, proponemos seis nuevos algoritmos para calcular soluciones aproximadas al problema del etiquetaje común. La eficiencia de los algoritmos propuestos es evaluada en diversas bases de datos reales i sintéticas. En la mayoría de experimentos realizados los algoritmos propuestos dan mejores resultados que los existentes en el estado del arte. / In pattern recognition, the use of graphs is, to a great extend, appropriate and advantageous. Usually, vertices of the graph represent local parts of an object while edges represent relations between these local parts. However, its advantages come together with a sever drawback, the distance between two graph cannot be optimally computed in polynomial time. Taking into account this special characteristic the use of graph prototypes becomes ubiquitous. The applicability of graphs prototypes is extensive, being the most common applications clustering, classification, object characterization and graph databases to name some. However, the objective of a graph prototype is equivalent to all applications, the representation of a set of graph. To synthesize a prototype all elements of the set must be mutually labeled. This mutual labeling consists in identifying which nodes of which graphs represent the same information in the training set. Once this mutual labeling is done the set can be characterized and combined to create a graph prototype. We call this initial labeling a common labeling. Up to now, all state of the art algorithms to compute a common labeling lack on either performance or theoretical basis. In this thesis, we formally describe the common labeling problem and we give a clear taxonomy of the types of algorithms. Six new algorithms that rely on different techniques are described to compute a suboptimal solution to the common labeling problem. The performance of the proposed algorithms is evaluated using an artificial and several real datasets. In addition, the algorithms have been evaluated on several real applications. These applications include graph databases and group-wise image registration. In most of the tests and applications evaluated the presented algorithms have showed a great improvement in comparison to state of the art applications.

This thesis proposes an expressive yet efficient declarative framework for graph matching in constraint programming (CP), and focuses on efficient algorithms to solve the subgraph isomorphism problem. The framework is based on graph and map variables, and specific graph morphism constraints. This allows to model and solve various graph matching problems, avoiding the tedious development of dedicated and specific algorithms. A specialized filtering algorithm is proposed for the subgraph isomorphism problem, which uses the semantic of the problem as well as the global structure of the two input graphs. It is shown that it is the state-of-the-art filtering algorithm, compared to dedicated algorithms and other CP approaches. Various search techniques from CP are also extended to the subgraph isomorphism problem. An automatic detection and exploitation of symmetries for the subgraph isomorphism problem is proposed, together with a decomposition approach of the search. The significance of this thesis lies in the fact that, even though the framework is expressive, CP can be considered as the state-of-the-art for subgraph isomorphism, outperforming the dedicated known algorithms on current benchmarks.

Donat un conjunt d'objectes, el concepte genèric de mediana està definit com l'objecte amb la suma de distàncies a tot el conjunt, més petita. Sovint, aquest concepte és usat per a obtenir el representant del conjunt. En el reconeixement estructural de patrons, els grafs han estat usats normalment per a representar objectes complexos. En el domini dels grafs, el concepte de mediana és conegut com median graph. Potencialment, té les mateixes aplicacions que el concepte de mediana per poder ser usat com a representant d'un conjunt de grafs. Tot i la seva simple definició i les potencials aplicacions, s'ha demostrat que el seu càlcul és una tasca extremadament complexa. Tots els algorismes existents només han estat capaços de treballar amb conjunts petits de grafs, i per tant, la seva aplicació ha estat limitada en molts casos a usar dades sintètiques sense significat real. Així, tot i el seu potencial, ha restat com un concepte eminentment teòric. L'objectiu principal d'aquesta tesi doctoral és el d'investigar a fons la teoria i l'algorísmica relacionada amb el concepte de medinan graph, amb l'objectiu final d'extendre la seva aplicabilitat i lliurar tot el seu potencial al món de les aplicacions reals. Per això, presentem nous resultats teòrics i també nous algorismes per al seu càlcul. Des d'un punt de vista teòric aquesta tesi fa dues aportacions fonamentals. Per una banda, s'introdueix el nou concepte d'spectral median graph. Per altra banda es mostra que certes de les propietats teòriques del median graph poden ser millorades sota determinades condicions. Més enllà de les aportacioncs teòriques, proposem cinc noves alternatives per al seu càlcul. La primera d'elles és una conseqüència directa del concepte d'spectral median graph. Després, basats en les millores de les propietats teòriques, presentem dues alternatives més per a la seva obtenció. Finalment, s'introdueix una nova tècnica per al càlcul del median basat en el mapeig de grafs en espais de vectors, i es proposen dos nous algorismes més. L'avaluació experimental dels mètodes proposats utilitzant una base de dades semi-artificial (símbols gràfics) i dues amb dades reals (mollècules i pàgines web), mostra que aquests mètodes són molt més eficients que els existents. A més, per primera vegada, hem demostrat que el median graph pot ser un bon representant d'un conjunt d'objectes utilitzant grans quantitats de dades. Hem dut a terme experiments de classificació i clustering que validen aquesta hipòtesi i permeten preveure una pròspera aplicació del median graph a un bon nombre d'algorismes d'aprenentatge. / Given a set of objects, the generic concept of median is defined as the object with the smallest sum of distances to all the objects in the set. It has been often used as a good alternative to obtain a representative of the set. In structural pattern recognition, graphs are normally used to represent structured objects. In the graph domain, the concept analogous to the median is known as the median graph. By extension, it has the same potential applications as the generic median in order to be used as the representative of a set of graphs. Despite its simple definition and potential applications, its computation has been shown as an extremely complex task. All the existing algorithms can only deal with small sets of graphs, and its application has been constrained in most cases to the use of synthetic data with no real meaning. Thus, it has mainly remained in the box of the theoretical concepts. The main objective of this work is to further investigate both the theory and the algorithmic underlying the concept of the median graph with the final objective to extend its applicability and bring all its potential to the world of real applications. To this end, new theory and new algorithms for its computation are reported. From a theoretical point of view, this thesis makes two main contributions. On one hand, the new concept of spectral median graph. On the other hand, we show that some of the existing theoretical properties of the median graph can be improved under some specific conditions. In addition to these theoretical contributions, we propose five new ways to compute the median graph. One of them is a direct consequence of the spectral median graph concept. In addition, we provide two new algorithms based on the new theoretical properties. Finally, we present a novel technique for the median graph computation based on graph embedding into vector spaces. With this technique two more new algorithms are presented. The experimental evaluation of the proposed methods on one semi-artificial and two real-world datasets, representing graphical symbols, molecules and webpages, shows that these methods are much more ecient than the existing ones. In addition, we have been able to proof for the first time that the median graph can be a good representative of a class in large datasets. We have performed some classification and clustering experiments that validate this hypothesis and permit to foresee a successful application of the median graph to a variety of machine learning algorithms.

Encontrar las correspondencias entre dos imágenes es un problema crucial en el campo de la visión por ordenador i el reconocimiento de patrones. Es relevante para un amplio rango de propósitos des de aplicaciones de reconocimiento de objetos en las áreas de biometría, análisis de documentos i análisis de formas hasta aplicaciones relacionadas con la geometría desde múltiples puntos de vista tales cómo la recuperación de la pose, estructura desde el movimiento y localización y mapeo. La mayoría de las técnicas existentes enfocan este problema o bien usando características locales en la imagen o bien usando métodos de registro de conjuntos de puntos (o bien una mezcla de ambos). En las primeras, un conjunto disperso de características es primeramente extraído de las imágenes y luego caracterizado en la forma de vectores descriptores usando evidencias locales de la imagen. Las características son asociadas según la similitud entre sus descriptores. En las segundas, los conjuntos de características son considerados cómo conjuntos de puntos los cuales son asociados usando técnicas de optimización no lineal. Estos son procedimientos iterativos que estiman los parámetros de correspondencia y de alineamiento en pasos alternados. Los grafos son representaciones que contemplan relaciones binarias entre las características. Tener en cuenta relaciones binarias al problema de la correspondencia a menudo lleva al llamado problema del emparejamiento de grafos. Existe cierta cantidad de métodos en la literatura destinados a encontrar soluciones aproximadas a diferentes instancias del problema de emparejamiento de grafos, que en la mayoría de casos es del tipo "NP-hard". El cuerpo de trabajo principal de esta tesis está dedicado a formular ambos problemas de asociación de características de imagen y registro de conjunto de puntos como instancias del problema de emparejamiento de grafos. En todos los casos proponemos algoritmos aproximados para solucionar estos problemas y nos comparamos con un número de métodos existentes pertenecientes a diferentes áreas como eliminadores de "outliers", métodos de registro de conjuntos de puntos y otros métodos de emparejamiento de grafos. Los experimentos muestran que en la mayoría de casos los métodos propuestos superan al resto. En ocasiones los métodos propuestos o bien comparten el mejor rendimiento con algún método competidor o bien obtienen resultados ligeramente peores. En estos casos, los métodos propuestos normalmente presentan tiempos computacionales inferiores. / Trobar les correspondències entre dues imatges és un problema crucial en el camp de la visió per ordinador i el reconeixement de patrons. És rellevant per un ampli ventall de propòsits des d’aplicacions de reconeixement d’objectes en les àrees de biometria, anàlisi de documents i anàlisi de formes fins aplicacions relacionades amb geometria des de múltiples punts de vista tals com recuperació de pose, estructura des del moviment i localització i mapeig. La majoria de les tècniques existents enfoquen aquest problema o bé usant característiques locals a la imatge o bé usant mètodes de registre de conjunts de punts (o bé una mescla d’ambdós). En les primeres, un conjunt dispers de característiques és primerament extret de les imatges i després caracteritzat en la forma de vectors descriptors usant evidències locals de la imatge. Les característiques son associades segons la similitud entre els seus descriptors. En les segones, els conjunts de característiques son considerats com conjunts de punts els quals son associats usant tècniques d’optimització no lineal. Aquests son procediments iteratius que estimen els paràmetres de correspondència i d’alineament en passos alternats. Els grafs son representacions que contemplen relacions binaries entre les característiques. Tenir en compte relacions binàries al problema de la correspondència sovint porta a l’anomenat problema de l’emparellament de grafs. Existeix certa quantitat de mètodes a la literatura destinats a trobar solucions aproximades a diferents instàncies del problema d’emparellament de grafs, el qual en la majoria de casos és del tipus “NP-hard”. Una part del nostre treball està dedicat a investigar els beneficis de les mesures de ``bins'' creuats per a la comparació de característiques locals de les imatges. La resta està dedicat a formular ambdós problemes d’associació de característiques d’imatge i registre de conjunt de punts com a instàncies del problema d’emparellament de grafs. En tots els casos proposem algoritmes aproximats per solucionar aquests problemes i ens comparem amb un nombre de mètodes existents pertanyents a diferents àrees com eliminadors d’“outliers”, mètodes de registre de conjunts de punts i altres mètodes d’emparellament de grafs. Els experiments mostren que en la majoria de casos els mètodes proposats superen a la resta. En ocasions els mètodes proposats o bé comparteixen el millor rendiment amb algun mètode competidor o bé obtenen resultats lleugerament pitjors. En aquests casos, els mètodes proposats normalment presenten temps computacionals inferiors.

Shuffled linear regression concerns itself with linear models with an unknown correspondence between the input and the output. This correspondence is usually represented by a permutation matrix II*. The model we are interested in has one more complication which is that the design matrix is itself latent and is observed with noise. This is considered as a type of errors-in-variables (EIV) model. Our interest lies in the recovery of the permutation matrix. We propose an estimator for II* based on the total least squares (TLS) technique, a common method of estimation used in EIV model. The estimation problem can be viewed as approximating one matrix by another of lower rank and the quantity it seeks to minimize is the sum of the smallest singular values squared. Due to identifiability issue, we evaluate the proposed estimator by the normalized Procrustes quadratic loss which allows for an orthogonal rotation of the estimated design matrix. Our main result provides an upper bound on this quantity which states that it is required that the signal-to-noise ratio to go to infinity in order for the loss to go to zero. On the computational front, since the problem of permutation recovery is NP-hard to solve, we propose a simple and efficient algorithm named alternating LAP/TLS algorithm (ALTA) to approximate the estimator, and we use it to empirically examine the main result. The main idea of the algorithm is to alternate between estimating the unknown coefficient matrix using the TLS method and estimating the latent permutation matrix by solving a linear assignment problem (LAP) which runs in polynomial time. Lastly, we propose a hypothesis testing procedure based on graph matching which we apply in the field of digital humanities, on character social networks constructed from novel series.

No description available.