Graph-Based Representations in Pattern Recognition

An appropriate image representation induces some good image treatment algorithms. Hypergraph theory is a theory of finite combinatorial sets, modeling a lot of problems of operational research and combinatorial optimization. Hypergraphs are now used in many domains such as chemistry, engineering and image processing. We present an overview of a hypergraph-based picture representation giving much application in picture manipulation, analysis and restoration: the Image Adaptive Neighborhood Hypergraph (IANH). With the IANH it is possible to build powerful noise detection an elimination algorithm, but also to make some edges detection or some image segmentation. IANH has various applications and this paper presents a survey of them.

We present a broad algorithmic framework for transforming an image comprised of pixels into a vectorized image segmented into polygons that can be subsequently used in image processing and understanding. A digital image is processed to extract edge pixel chains and a constrained Delaunay triangulation of the edge contour set is performed to yield triangles that cover the pixelated image without crossing edge contours. Each triangle is attributed a color by a Monte Carlo sampling of pixels within it. A combination of rules, each of which models an elementary perceptual grouping criterion, determines which adjacent triangles should be merged. A grouping graph is formed with vertices representing triangles and edges between vertices that correspond to adjacent triangles to be merged according to the combination of grouping rules. A connected component analysis on the grouping graph then yields collections of triangles that form polygons segmenting and vectorizing the image.

Graphs and graph transformation are versatile tools for representing and interpreting the contents of document images. Three main components are involved: a graph representing the contents of a document image at some level of interpretation, a set of graph transformation rules (graph productions), and a mechanism for controlling the application of the graph productions. We review existing document analysis systems that use graph transformation, and discuss challenges and research opportunities in this area.

This paper deals with the problem of graphical knowledge management (formalization, modelling, representation and operationalization) in graphics recognition systems. We present here a “generic” formalism for graphical knowledge, allowing various modellings for a given graphical shape. We use a modelling library based on this formalism for the management of our graphical knowledge. The use of this library allows to request graphical knowledge databases, according to the processings’ requirements on graphical primitives. Like this, this approach allows interoperability between processings, especially for their combination. We present a “short” system use-case of our approach to illustrate the interoperability between processings.

Vascular networks develop by way of angiogenesis, a growth process that involves the biological mechanisms of vessel sprouting (budding) and splitting (intussusception). Graph theory is a branch of discrete mathematics that is excellently suited to model vascular networks and to analyze their properties (invariants). A random graph process model can simulate the development of a vascular network that has been modeled using graph theory. The renal glomerulus is one example of such a vascular network. Here the correlation between the invariants of this vascular network modeled as a graph and the mechanisms of the growth of the network are studied. It is proposed that the relative frequencies of sprouting and splitting during the growth of a given renal glomerulus can be estimated by the invariants (root distance, radius, and diameter) of the graph representing the renal glomerulus network. Experimental evidence is given to support this conjecture.

This paper shows how to construct a linear deformable model for graph structure by performing principal components analysis (PCA) on the vectorised adjacency matrix. We commence by using correspondence information to place the nodes of each of a set of graphs in a standard reference order. Using the correspondences order, we convert the adjacency matrices to long-vectors and compute the long-vector covariance matrix. By projecting the vectorised adjacency matrices onto the leading eigenvectors of the covariance matrix, we embed the graphs in a pattern-space. We illustrate the utility of the resulting method for shape-analysis.

Graph seriation is concerned with placing the nodes of a graph in a serial order so that edge consecutive constraints are generally preserved. It is an important task in network analysis problem in routine and bioinformatics. In this paper we show how the problem of graph seriation can be solved using semi-definite programming (SDP). This is a convex optimisation procedure that has recently found widespread use in computer vision. The main contribution of the paper is to detail the matrix representation needed to cast the graph-seriation problem in a matrix setting so that it can be solved using SDP. We illustrate the utility of the method for graph-matching and graph-clustering, where it is shown to offer advantages to the graph-spectral approach to seriation.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 algorithm is applied to the problem of 3D shape similarity evaluation through structural shape descriptors.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.