Search

In this paper, we propose a highly robust point-matching method (Graph Transformation Matching - GTM) relying on finding the consensus graph emerging from putative matches. Such method is a two-phased one in the sense that after finding the consensus graph it tries to complete it as much as possible. We successfully apply GTM to image registration in the context of finding mosaics from retinal images. Feature points are obtained after properly segmenting such images. In addition, we also introduce a novel topological descriptor for quantifying disease by characterizing the arterial/venular trees. Such descriptor relies on diffusion kernels on graphs. Our experiments have showed only statistical significance for the case of arterial trees, which is consistent with previous findings. [ABSTRACT FROM AUTHOR]

New technologies for shape acquisition and rendering of digital shapes have simplified the process of creating virtual scenes; nonetheless, shape annotation, recognition and manipulation of both the complete virtual scenes and even of subparts of them are still open problems. Once the main components of a virtual scene are represented by structural descriptions, this paper deals with the problem of comparing two (or more) sets of 3D objects, where each model is represented by an attributed graph. We will define a new distance to estimate the possible similarities among the sets of graphs and we will validate our work using a shape graph [1]. [ABSTRACT FROM AUTHOR]

In this paper we propose a quadratic programming approach to computing the edit distance of graphs. Whereas the standard edit distance is defined with respect to a minimum-cost edit path between graphs, we introduce the notion of fuzzy edit paths between graphs and provide a quadratic programming formulation for the minimization of fuzzy edit costs. Experiments on real-world graph data demonstrate that our proposed method is able to outperform the standard edit distance method in terms of recognition accuracy on two out of three data sets. [ABSTRACT FROM AUTHOR]

We propose in this article an image classification technique based on kernel methods and graphs. Our work explores the possibility of applying marginalized kernels to image processing. In machine learning, performant algorithms have been developed for data organized as real valued arrays; these algorithms are used for various purposes like classification or regression. However, they are inappropriate for direct use on complex data sets. Our work consists of two distinct parts. In the first one we model the images by graphs to be able to represent their structural properties and inherent attributes. In the second one, we use kernel functions to project the graphs in a mathematical space that allows the use of performant classification algorithms. Experiments are performed on medical images acquired with various modalities and concerning different parts of the body. [ABSTRACT FROM AUTHOR]

In this paper we consider how coined quantum walks can be applied to graph matching problems. The matching problem is abstracted using an auxiliary graph that connects pairs of vertices from the graphs to be matched by way of auxiliary vertices. A coined quantum walk is simulated on this auxiliary graph and the quantum interference on the auxiliary vertices indicates possible matches. When dealing with graphs for which there is no exact match, the interference amplitudes together with edge consistencies are used to define a consistency measure. We have tested the algorithm on graphs derived from the NCI molecule database and found it to significantly reduce the space of possible matchings thereby allowing the graphs to be matched directly. An analysis of the quantum walk in the presence of structural errors between graphs is used as the basis of the consistency measure. We test the performance of this measure on graphs derived from images in the COIL-100 database. [ABSTRACT FROM AUTHOR]

In many applications of computer vision and pattern recognition which use graph-based knowledge representation, it is of great interest to be able to extract the K largest cliques in a graph, but most methods are geared either towards extracting the single clique of maximum size, or enumerating all cliques, without following any particular order. In this paper we present a novel approach for partial clique enumeration, that is, the extraction of the K largest cliques of a graph. Our approach is based on a continuous formulation of the clique problem developed by Motzkin and Straus, and is able to avoid extracting the same clique multiple times. This is done by casting the problem into a game-theoretic framework and iteratively rendering unstable the solutions that have already been extracted. [ABSTRACT FROM AUTHOR]

In this paper we propose a new lower bound to a subgraph isomorphism problem. This bound can provide a proof that no subgraph isomorphism between two graphs can be found. The computation is based on the SDP relaxation of a - to the best of our knowledge - new combinatorial optimisation formulation for subgraph isomorphism. We consider problem instances where only the structures of the two graph instances are given and therefore we deal with simple graphs in the first place. The idea is based on the fact that a subgraph isomorphism for such problem instances always leads to 0 as lowest possible optimal objective value for our combinatorial optimisation problem formulation. Therefore, a lower bound that is larger than 0 represents a proof that a subgraph isomorphism don't exist in the problem instance. But note that conversely, a negative lower bound does not imply that a subgraph isomorphism must be present and only indicates that a subgraph isomorphism is still possible. [ABSTRACT FROM AUTHOR]

In this paper, we propose to represent shapes by graphs. Based on graphic primitives extracted from the binary images, attributed relational graphs were generated. Thus, the nodes of the graph represent shape primitives like vectors and quadrilaterals while arcs describing the mutual primitives relations. To be invariant to transformations such as rotation and scaling, relative geometric features extracted from primitives are associated to nodes and edges as attributes. Concerning graph matching, due to the fact of NP-completeness of graph-subgraph isomorphism, a considerable attention is given to different strategies of inexact graph matching. We also present a new scoring function to compute a similarity score between two graphs, using the numerical values associated to the nodes and edges of the graphs. The adaptation of a greedy graph matching algorithm with the new scoring function demonstrates significant performance improvements over traditional exhaustive searches of graph matching. [ABSTRACT FROM AUTHOR]

Many medical applications require a registration of different images of the same organ. In many cases, such a registration is accomplished by manually placing landmarks in the images. In this paper we propose a method which is able to find reasonable landmarks automatically. To achieve this, nodes of the vessel systems, which have been extracted from the images by a segmentation algorithm, will be assigned by the so-called association graph method and the coordinates of these matched nodes can be used as landmarks for a non-rigid registration algorithm. [ABSTRACT FROM AUTHOR]

We propose a new approach to stereo matching for obstacle detection in the autonomous navigation framework. An accurate but slow reconstruction of the 3D scene is not needed; rather, it is more important to have a fast localization of the obstacles to avoid them. All the methods in the literature, based on a punctual stereo matching, are ineffective in realistic contexts because they are either computationally too expensive, or unable to deal with the presence of uniform patterns, or of perturbations between the left and right images. Our idea is to face the stereo matching problem as a matching between homologous regions. The stereo images are represented as graphs and a graph matching is computed to find homologous regions. Our method is strongly robust in a realistic environment, requires little parameter tuning, and is adequately fast, as experimentally demonstrated in a comparison with the best algorithms in the literature. [ABSTRACT FROM AUTHOR]

In the field of structural pattern recognition graphs constitute a very common and powerful way of representing patterns. In contrast to string representations, graphs allow us to describe relational information in the patterns under consideration. One of the main drawbacks of graph representations is that the computation of standard graph similarity measures is exponential in the number of involved nodes. Hence, such computations are feasible for rather small graphs only. One of the most flexible error-tolerant graph similarity measures is based on graph edit distance. In this paper we propose an approach for the efficient compuation of edit distance based on bipartite graph matching by means of Munkres' algorithm, sometimes referred to as the Hungarian algorithm. Our proposed algorithm runs in polynomial time, but provides only suboptimal edit distance results. The reason for its suboptimality is that implied edge operations are not considered during the process of finding the optimal node assignment. In experiments on semi-artificial and real data we demonstrate the speedup of our proposed method over a traditional tree search based algorithm for graph edit distance computation. Also we show that classification accuracy remains nearly unaffected. [ABSTRACT FROM AUTHOR]

A common problem encountered in structural pattern recognition is the difficulty of constructing classification models or rules from a set of examples, due to the complexity of the structures needed to represent the patterns. In this paper we present an extension of a method for structural learning applied to predictive toxicology evaluation. [ABSTRACT FROM AUTHOR]

In a video surveillance system, moving object detection is the most challenging problem especially if the system is applied to complex environments with variable lighting, dynamic and articulate scenes, etc. Furthermore, a video surveillance system is a real-time application, so discouraging the use of good, but computationally expensive, solutions. This paper presents a set of improvements of a basic background subtraction algorithm that are suitable for video surveillance applications. Besides we present a new performance evaluation scheme never used in the context of moving object detection algorithms. [ABSTRACT FROM AUTHOR]

In a video surveillance system, moving object detection is the most challenging problem especially if the system is applied in complex environments with variable lighting, dynamic and articulate scenes, etc.. Furthermore, a video surveillance system is a real-time application, so discouraging the use of good, but computationally expensive, solutions. This paper presents a set of improvements of a basic background subtraction algorithm that are suitable for video surveillance applications. Besides we present a new evaluation scheme never used in the context of moving object detection algorithms. [ABSTRACT FROM AUTHOR]

In this article we try to make different kinds of information cooperate in a characters recognition system addressing old Greek and Egyptians documents. We first use a statistical approach based on classical shape descriptors (Zernike, Fourier). Then we use a structural classification method with an attributed graph description of characters and a random graph modeling of classes. The hypothesis, that structural methods bring topological information that statistical methods do not, is validated on Greek characters. A cooperation with a chain of classifiers based on reject management is then proposed. Due to computation cost, the goal of such a chain is to use the structural approach only if the statistical one fails. [ABSTRACT FROM AUTHOR]

In this paper we propose the use of a simple kernel function based on the graph edit distance. The kernel function allows us to apply a wide range of statistical algorithms to the problem of attributed graph matching. The function we describe is simple to compute and leads to several convenient interpretations of geometric properties of graphs in their implicit vector space representation. Although the function is not generally positive definite, we show in experiments on real-world data that the kernel approach may result in a significant improvement of the graph matching and classification performance using support vector machines and kernel principal component analysis. [ABSTRACT FROM AUTHOR]

In this paper we develop a new graph representation based on the path-weighted adjacency matrix for characterising global graph structure. The representation is derived from the heat-kernel of the graph. We investigate whether the path-weighted adjacency matrix can be used for the problem of graph partitioning. Here we demonstrate that the method out-performs the use of the adjacency matrix. The main advantage of the new method is that it both preserves partition consistency and shows improved stability to structural error. [ABSTRACT FROM AUTHOR]

This paper describes how heat-kernel asymptotics can be used to compute approximate Euclidean distances between nodes in a graph. The distances are used to embed the graph-nodes in a low-dimensional space by performing Multidimensional Scaling(MDS). We perform an analysis of the distances, and demonstrate that they are related to the sectional curvature of the connecting geodesic on the manifold. Experiments with moment invariants computed from the embedded points show that they can be used for graph clustering. [ABSTRACT FROM AUTHOR]

In this paper, an experimental comparison among three structural approaches to fingerprint classification is reported. Main pros and cons of such approaches are investigated by experiments and discussed. Moreover, the effectiveness of their measurement-level fusion is analysed. Finally, a comparison among the investigated structural approaches and the well-known statistical approach based on "FingerCodes" is reported. [ABSTRACT FROM AUTHOR]

In this paper we propose a novel approach to obtain unambiguous and robust node attributes for matching non-attributed graphs. Such approach consists of exploiting the information coming from diffusion kernels to embed the subgraph induced by the neighborhood of each vertex in an Euclidean manifold and then use entropic graphs for measuring the α-entropy of the resulting distribution. Our experiments with random-generated graphs with 50 nodes show that at low edge densities, where the effect of structural noise is higher, this approach outperforms the description of the subgraph only in terms of diffusion kernels. Furthermore, our structural recognition experiments show that the approach has a practical application. All experiments were performed by weighting the well-known quadratic cost function used in the Softassign algorithm. [ABSTRACT FROM AUTHOR]

In this paper we address the problem of comparing and classifying protein surfaces through a kernelized version of the Softassign graph-matching algorithm. Preliminary experiments with random-generated graphs have suggested that weighting the quadratic cost function of Softassign with information coming from the computation of diffusion kernels on graphs attenuate the performance decay with increasing noise levels. Our experimental results show that this approach yields a useful similarity measure to cluster proteins with similar structure, to automatically find prototypical graphs representing families of proteins and also to classify proteins in terms of their distance to these prototypes. We also show that the role of kernel-based information is to smooth the obtained matching fields, which in turn results in noise-free prototype estimation. [ABSTRACT FROM AUTHOR]

This paper introduces a tree-based algorithm for the motion tracking of dominant parts in a temporal image sequence. A tree allows us to express hierarchical relations of segments in an image. We first develop a fast tree matching algorithm which is suitable for matching of images. Second, employing the linear-scale-space analysis, we develop an algorithm to extract hierarchical relations of temporal images as a tree. Combining tree matching and tree extraction provides a method to extract moving dominant parts in a sequence of temporal images. [ABSTRACT FROM AUTHOR]

Novel algorithms for the analysis of graph sequences are proposed in this paper. In particular, we study the problem of recovering missing information and predicting the occurrence of nodes and edges in time series of graphs. Our work is motivated by applications in computer network analysis. However, the proposed recovery and prediction schemes are generic and can be applied in other domains as well. [ABSTRACT FROM AUTHOR]

An important topic in pattern recognition is retrieval of candidate patterns from a database according to a given sample input pattern. Using graphs, the database retrieval problem is turned into a graph matching problem. In this paper we propose a method based on decision trees to filter a database of graphs according to a given input graph. The present paper extends previous work concerned with graph and subgraph isomorphism to the case of error-tolerant graph matching. [ABSTRACT FROM AUTHOR]

A model of the target object is required for the recognition of cartographic objects in satellite images. We developed a learning system that constructs the structural models for cartographic objects automatically. Using a database of examples extracted from satellite images, this system constructs the abstract model of the object in each class. The images containing the objects are decomposed into primitive figures and are transformed to Attributed Relational Graphs (ARGs) that are very appropriate for the representation of structured data. We generated the object models applying graph-matching algorithms on these graphs. The quality of a model is evaluated by a specific edit-distance of the examples to the model. We tested our system on images of bridges and roundabouts. We could obtain object models compatible with manually generated models. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm for the computation of the maximum common subgraph (MCS) between two directed, acyclic graphs with attributes. The core of the contribution resides in the modularity of the proposed algorithm which allows different heuristic techniques to be plugged in, depending on the application domain. Implemented heuristics for robust graph matching with respect to graph structural noise are discussed. As example of its effectiveness, the algortihm is applied to the problem of 3D shape similarity evaluation through structural shape descriptors. [ABSTRACT FROM AUTHOR]

This paper discusses inexact matching of graphs that are spatially-attributed and asymmetric. In a spatially-attributed graph, vertex attributes indicate the coordinates of an image feature represented by the vertex. Asymmetry arises when two graphs represent the same data at different resolutions: this causes an edge in the coarse graph to match an entire path in the fine graph. The two graphs may use different coordinate systems, so a coordinate transform must be estimated during the graph matching. We present an edge first graph matching algorithm to solve this problem, and illustrate its application to the registration of satellite images to road maps. In our current implementation, graphs that represent road networks are manually extracted from satellite images and digitized road maps. Most of the existing algorithms are not designed to handle the asymmetry present when matching a coarse graph to a fine graph. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the notion of consistency in inexact graph matching to be able to correctly determine the optimal solution of the matching problem. Consistency allows us to study the cost function which controls the graph matching process, regardless of the optimization technique that is used. The analysis is performed in the context of change detection in geospatial information. A condition based on the expected graph error is presented which allows to determine the bounds of error tolerance and in this way characterizes acceptable over inacceptable data inconsistencies. [ABSTRACT FROM AUTHOR]

This work discusses the issue of approximation in point set matching problems. In general, one may have two classes of approximations when tackling a matching problem: a representational approximation, which involves a simplified and suboptimal modeling for the original problem, and algorithmic approximation, which consists in using suboptimal algorithms to infer the assignment. Matching techniques in general have relied on the second approach: to keep a complete model of the original problem and use suboptimal techniques to solve it. In this paper, we show how a technique based on using exact inference in simple graphical models, which is an instance of the first class, can significantly outperform instances of techniques from the second class. We give theoretical insights of why this happens, and experimentally compare our approach with the well-known Shapiro and Brady and Christmas et al. methods, which are exemplars of the second class. We perform experiments with synthetic and real-world data sets, which reveal a significant accuracy improvement of the proposed technique both under point position jitter and size increasing of the point sets. The main conclusion is that techniques based on optimal algorithms with appropriate suboptimal representations may lead to better results than their counterparts which consist in using optimal representations, but approximate algorithms. [ABSTRACT FROM AUTHOR]

A method allowing to integrate syntactic and semantic approaches in an automatic segmentation process is described. This integration is possible thanks to the formalism of graphs. The proposed method checks the relevancy of merging criteria used in an adaptive pyramid by matching the obtained segmentation with a semantic graph describing the objects that we look for. This matching is performed by checking the arc-consistency with bilevel constraints of the chosen semantic graph. The validity of this approach is experimented on synthetic and real images. [ABSTRACT FROM AUTHOR]

A concept relating story-board description of video sequences with spatio-temporal hierarchies build by local contraction processes of spatio-temporal relations is presented. Object trajectories are curves in which their ends and junctions are identified. Junction points happen when two (or more) trajectories touch or cross each other, which we interpret as the "interaction" of two objects. Trajectory connections are interpreted as the high level descriptions. [ABSTRACT FROM AUTHOR]

In a video surveillance system the object tracking is one of the most challenging problem. In fact objects in the world exhibit complex interactions. When captured in a video sequence, some interactions manifest themselves as occlusions. A visual tracking system must be able to track objects which are partially or even fully occluded. In this paper we present a novel method of tracking objects through occlusions using a multi-resolution representation of the moving regions. The matching between objects in two consecutive frames to recognize the trajectories is preformed in a graph theoretic approach. The experimental results on the standard database PEST2001 show that the approach looks promising. [ABSTRACT FROM AUTHOR]

Shock graphs have emerged as a powerful generic 2-D shape representation. However, most approaches typically assume that the silhouette has been correctly segmented. In this paper, we present a framework for shock graph-based object recognition in less contrived scenes. The approach consists of two steps, beginning with the construction of a region adjacency graph pyramid. For a given region, we traverse this scale-space, using a model shock graph hypothesis to guide a region grouping process that strengthens the hypothesis. The result represents the best subset of regions, spanning different scales, that matches a given object model. In the second step, the correspondence between the region and model shock graphs is used to initialize an active skeleton that includes a shock graph-based energy term. This allows the skeleton to adapt to the image data while still adhering to a qualitative shape model. Together, the two components provide a coarse-to-fine, model-based segmentation/recognition framework. [ABSTRACT FROM AUTHOR]

In this paper, we propose an original tree matching algorithm for intra-patient hepatic vascular system registration. The vascular systems are segmented from CT-Scan images acquired at different time, and then modeled as trees. The goal of this algorithm is to find common bifurcations (nodes) and vessels (edges) in both trees. Starting from the tree root, edges and nodes are iteratively matched. The algorithm works on a set of matching hypotheses which is updated to keep best matches. It is robust against topological modification, as the segmentation process can fail to detect some branches. Finally, this algorithm is validated on the Visible Human with synthetic deformations thanks to the simulator prototype developed at the INRIA which provides realistic deformations for liver and its vascular network. [ABSTRACT FROM AUTHOR]

Graph matching is often used for image recognition. Different kinds of graph matchings have been proposed such as (sub)graph isomorphism or error-tolerant graph matching, giving rise to different graph similarity measures. A first goal of this paper is to show that these different measures can be viewed as special cases of a generic similarity measure introduced in [8]. This generic similarity measure is based on a non-bijective graph matching (like [4] and [2]) so that it is well suited to image recognition. In particular, over/under-segmentation problems can be handled by linking one vertex to a set of vertices. In a second part, we address the problem of computing this measure and we describe two algorithms: a greedy algorithm, that quickly computes sub-optimal solutions, and a reactive Tabu search algorithm, that may improve these solutions. Some experimental results are given. [ABSTRACT FROM AUTHOR]

We present a direct algorithm that computes a largest common connected induced subgraph of two given graphs. It is based on an efficient generation of the common connected induced subgraphs of the input graphs. Experimental results are provided. [ABSTRACT FROM AUTHOR]

In this paper we explore how a spectral technique suggested by quantum walks can be used to distinguish non-isomorphic cospectral graphs. Reviewing ideas from the field of quantum computing we recall the definition of the unitary matrices inducing quantum walks. We show how the spectra of these matrices are related to the spectra of the transition matrices of classical walks. Despite this relationship the behaviour of quantum walks is vastly different from classical walks. We show how this leads us to define a new matrix whose spectrum can be used to distinguish between graphs that are otherwise indistinguishable by standard spectral methods. [ABSTRACT FROM AUTHOR]

Graph pyramids are often used for representing irregular pyramids. Combinatorial pyramids have been recently defined for this purpose. We define here pyramids of n-dimensional generalized maps. This is the main contribution of this work: a generic definition in any dimension which extend and generalize the previous works. Moreover, such pyramids explicitly represent more topological information than graph pyramids. A pyramid can be implemented in several ways, and three representations are discussed in this paper. Keywords: Hierarchical data structure, irregular pyramids, generalized map, n-G-map pyramids, multi-resolution. [ABSTRACT FROM AUTHOR]

Irregular pyramids are made of a stack of successively reduced graphs embedded in the plane. Such pyramids are often used within the segmentation and the connected component analysis frameworks to detect meaningful objects together with their spatial and topological relationships. The graphs reduced in the pyramid may be region adjacency graphs, dual graphs or combinatorial maps. Using any of these graphs each vertex of a reduced graph encodes a region of the image. Using simple graphs one edge between two vertices encodes the existence of a common boundary between two regions. Using dual graphs and combinatorial maps, each connected boundary segment between two regions is associated to one edge. Moreover, special edges called loops may be used to differentiate a special type of adjacency where one region surrounds the other. We show in this article that the loop information does not allow to distinguish inside and outside of the loop by local computations. We provide a method based on the combinatorial pyramid framework which uses the orientation explicitly encoded by combinatorial maps to determine inside and outside with local calculus. [ABSTRACT FROM AUTHOR]

We propose the GeoMap abstract data type as a unified representation for image segmentation purposes. It manages both topology (based on XPMaps) and pixel-based information, and its interface is carefully designed to support a variety of automatic and interactive segmentation methods. We have successfully used the abstract concept of a GeoMap as a foundation for the implementation of well-known segmentation methods. [ABSTRACT FROM AUTHOR]

Representing the regions of a segmented image is an important aspect of image segmentation. Several different models have been proposed to represent the regions of a segmented image but most of them are dedicated to a specific method. Among the non hierarchical models, the model of planar maps with discrete embedding is certainly the most versatile one. Maps have the great advantage to provide a continuity of representation from the abstract mathematical model to the concrete implementation. They encode and provide most of topological and geometrical features required by segmentation algorithms and can be efficiently updated. In this paper we give an overview of the use of planar maps with discrete embedding in the context of image segmentation and we show how to design, implement and use a general environment for 2D image segmentation, from the mathematical model up to a real application. The model, data structure, algorithms and API described in this paper are currently implemented in a software which will be available under LGPL in the course of year 2005. Keywords: Image representation, image segmentation, combinatorial maps, discrete boundaries, feature extraction. [ABSTRACT FROM AUTHOR]

This paper proposes a new possible way to represent a symbolic graph pyramid built by successive applications of some rules. This representation is targeted for learning the rules, since it contains information about which rules were applied, but also because it can be used to easily define the space of all possible pyramids as a reduction tree. We also consider restraining the possible rules to some basic ones in order to make the reduction trees easy to build, and a way to use them for learning will be presented. [ABSTRACT FROM AUTHOR]

This paper shows how strings can be used in a natural images classification task. We propose to build an attributed string from a set of regions of interest detected thanks to an interest point detector. These salient zones are characterized by local signatures describing singularities and they are linked by using graph seriation algorithms and perceptual methods. Once each image is represented by a string of signatures, we propose to use string-based edit distances and an ordered histograms-based distance in order to perform the classification task. Experiments have shown that whereas seriation algorithms give approximately the same results, the ordered histogram based distance is more efficient for the considered application. [ABSTRACT FROM AUTHOR]