Graph-Based Representations in Pattern Recognition

This paper presents an approach to matching parts of deformable shapes. Multiscale salient parts of the two shapes are first identified. Then, these parts are matched if their immediate properties are similar, the same holds recursively for their subparts, and the same holds for their neighbor parts. The shapes are represented by hierarchical attributed graphs whose node attributes encode the photometric and geometric properties of corresponding parts, and edge attributes capture the strength of neighbor and part-of interactions between the parts. Their matching is formulated as finding the subgraph isomorphism that minimizes a quadratic cost. The dimensionality of the matching space is dramatically reduced by convexifying the cost. Experimental evaluation on the benchmark MPEG-7 and Brown datasets demonstrates that the proposed approach is robust.

A large family of shape comparison methods is based on a medial axis transform combined with an encoding of the skeleton by a graph. Despite many qualities this encoding of shapes suffers from the non continuity of the medial axis transform. In this paper, we propose to integrate robustness against structural noise inside a graph kernel. This robustness is based on a selection of the paths according to their relevance and on path editions. This kernel is positive semi-definite and several experiments prove the efficiency of our approach compared to alternative kernels.

Disconnected skeleton

[1] is a very coarse yet a very stable skeleton-based representation scheme for generic shape recognition in which recognition is performed mainly based on the structure of disconnection points of extracted branches, without explicitly using information about boundary details [2,3]. However, sometimes sensitivity to boundary details may be required in order to achieve the goal of recognition. In this study, we first present a simple way to enrich disconnected skeletons with radius functions. Next, we attempt to resolve the conflicting goals of stability and sensitivity by proposing a coarse-to-fine shape matching algorithm. As the first step, two shapes are matched based on the structure of their disconnected skeletons, and following to that, the computed matching cost is re-evaluated by taking into account the similarity of boundary details in the light of class-specific boundary deformations which are learned from a given set of examples.

The Laplacian approach, when applied to mesh smoothing leads in many cases to convergence problems. It also leads to shrinking of the mesh. In this work, the authors reformulate the mesh smoothing problem as an optimisation one. This approach gives the means of controlling the steps to assure monotonic convergence. Furthermore, a new optimisation function is proposed that reduces the shrinking effect of the method. Examples are given to illustrate the properties of the proposed approches.

In this work, we present an approach that utilizes a graph-based representation of symbolic musical data in the context of automatic topographic mapping. A novel approach is introduced that represents melodic progressions as graph structures providing a dissimilarity measure which complies with the invariances in the human perception of melodies. That way, music collections can be processed by non-Euclidean variants of Neural Gas or Self-Organizing Maps for clustering, classification, or topographic mapping for visualization. We demonstrate the performance of the technique on several datasets of classical music.

In this paper, we propose a new graphical framework for extracting the relevant dietary, social and environmental risk factors that are associated with an increased risk of Nasopharyngeal Carcinoma (NPC) based on a case-control epidemiologic study. This framework builds on the use of Bayesian network for representing statistical dependencies between the random variables. BN is directed acyclic graphs that models the joint multivariate probability distribution underlying the data. These graphical models are highly attractive for their ability to describe complex probabilistic interactions between variables. The graph provides a statistical profile of the recruited population and meanwhile help identify a subset of features that are most relevant for probabilistic classification of the NPC. We report experiment results with the NPC case-study data using a novel constraint-based BN structure learning algorithm. We show how the DAG provides an improved comprehension of NPC etiology. Our findings are compared with the risk factors that were suggested in the recent literature in cancerology.

Modeling and understanding complex non-manifold shapes is a key issue in shape analysis and retrieval. The topological structure of a non-manifold shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we consider a decomposition of a non-manifold shape into components which are almost manifolds, and we present a novel graph representation which highlights the non-manifold singularities shared by the components as well as their connectivity relations. We describe an algorithm for computing the decomposition and its associated graph representation. We present a new tool for visualizing the shape decomposition and its graph as an effective support to modeling, analyzing and understanding non-manifold shapes.

A universal data model, named DG, is introduced to handle vectorized data uniformly during the whole recognition process. The model supports low level graph algorithms as well as higher level processing. To improve algorithmic efficiency, spatial indexing can be applied. Implementation aspects are discussed as well. An earlier version of the DG model has been applied for interpretation of Hungarian cadastral maps. Although this paper gives examples of map interpretation, our concept can be extended to other fields of graphics recognition.

Tracking multiple features of a rigid or an articulated object, without considering the underlying structure, becomes ambiguous if the target model (for example color histograms) is similar to other nearby regions or to the background. Instead of tracking multiple features independently, we propose an approach that integrates the underlying structure into the tracking process using an attributed graph. The independent tracking processes are driven to a solution that satisfies the visual as well as the structural constraints. An approach for rigid objects is presented and extended to handle articulated objects consisting of rigid parts. Experimental results on real and synthetic videos show promising results in scenes with considerable amount of occlusion.

In this paper, we present a novel graph-based approach for the registration of city maps. The goal is to find the best registration between a given image, which shows a small part of a city map, and stored map data. Such registration is important in fields like mobile computing for augmentation purposes. Until now, RFID tags, markers, or regular dot grids on specially prepared maps are typically required. In this paper we propose a graph-based method to avoid the need of special maps. It creates a graph representation of a given input image and robustly finds an optimal registration using a geometric hashing technique. Our approach is translation, scale and rotation invariant, map type independent and robust against noise and missing data.

In this paper, we address the problem of searching for a pattern in a plane graph,

i.e.

, a planar drawing of a planar graph. To do that, we propose to model plane graphs with 2-dimensional combinatorial maps, which provide nice data structures for modelling the topology of a subdivision of a plane into nodes, edges and faces. We define submap isomorphism, we give a polynomial algorithm for this problem, and we show how this problem may be used to search for a pattern in a plane graph. First experimental results show the validity of this approach to efficiently search for patterns in images.

The median graph has been shown to be a good choice to infer a representative of a set of graphs. It has been successfully applied to graph-based classification and clustering. Nevertheless, its computation is extremely complex. Several approaches have been presented up to now based on different strategies. In this paper we present a new approximate recursive algorithm for median graph computation based on graph embedding into vector spaces. Preliminary experiments on three databases show that this new approach is able to obtain better medians than the previous existing approaches.

In the field of structural pattern recognition, graphs provide us with a common and powerful way to represent objects. Yet, one of the main drawbacks of graph representation is that the computation of standard graph similarity measures is exponential in the number of involved nodes. Hence, such computations are feasible for small graphs only. The present paper considers the problem of graph isomorphism, i.e. checking two graphs for identity. A novel approach for the efficient computation of graph isomorphism is presented. The proposed algorithm is based on bipartite graph matching by means of Munkres’ algorithm. The algorithmic framework is suboptimal in the sense of possibly rejecting pairs of graphs without making a decision. As an advantage, however, it offers polynomial runtime. In experiments on two TC-15 graph sets we demonstrate substantial speedups of our proposed method over several standard procedures for graph isomorphism, such as Ullmann’s method, the VF2 algorithm, and Nauty. Furthermore, although the computational framework for isomorphism is suboptimal, we show that the proposed algorithm rejects only very few pairs of graphs.

Motion capture, a currently active research area, needs estimation of the pose of the subject. For this purpose, we match the tree representation of the skeleton of the 3D shape to a pre-specified tree model. Unfortunately, the tree representation can contain vertices that split limbs in multiple parts, which do not allow a good match by usual methods. To solve this problem, we propose a new alignment, taking in account the homeomorphism between trees, rather than the isomorphism, as in prior works. Then, we develop several computationally efficient algorithms for reaching real-time motion capture.

In this paper we propose an inexact spectral matching algorithm that embeds large graphs on a low-dimensional isometric space spanned by a set of eigenvectors of the graph Laplacian. Given two sets of eigenvectors that correspond to the smallest non-null eigenvalues of the Laplacian matrices of two graphs, we project each graph onto its eigenenvectors. We estimate the histograms of these one-dimensional graph projections (eigenvector histograms) and we show that these histograms are well suited for selecting a subset of significant eigenvectors, for ordering them, for solving the sign-ambiguity of eigenvector computation, and for aligning two embeddings. This results in an inexact graph matching solution that can be improved using a rigid point registration algorithm. We apply the proposed methodology to match surfaces represented by meshes.

We present an algorithm for graph matching in a pattern recognition context. This algorithm deals with weighted graphs, based on new structural and topological node signatures. Using these signatures, we compute an optimum solution for node-to-node assignment with the Hungarian method and propose a distance formula to compute the distance between weighted graphs. The experiments demonstrate that the newly presented algorithm is well suited to pattern recognition applications. Compared with four well-known methods, our algorithm gives good results for clustering and retrieving images. A sensitivity analysis reveals that the proposed method is also insensitive to weak structural changes.

This article presents a structural and probabilistic framework for representing a class of attributed graphs with only one structure. The aim of this article is to define a new model, called Structurally-Defined Random Graphs. This structure keeps together statistical and structural information to increase the capacity of the model to discern between attributed graphs within or outside the class. Moreover, we define the match probability of an attributed graph respect to our model that can be used as a dissimilarity measure. Our model has the advantage that does not incorporate application dependent parameters such as edition costs. The experimental validation on a TC-15 database shows that our model obtains higher recognition results, when there is moderate variability of the class elements, than several structural matching algorithms. Indeed in our model fewer comparisons are needed.

Arc-consistency checking has been adapted to be able to interpret over-segmented image. This adaptation lead to the arc-consistency algorithm with bilevel constraints. In this paper we propose an optimization of this algorithm. This new way to solve arc-consistency checking with bilevel constraints gives the possibility to parallelize the algorithm. Some experiments shows the efficiency of this approach.

Given a query image of an object of interest, our objective is to retrieve all instances of that object with high precision from a database of scalable size. As distinct from the bag-of-feature based methods, we do not regard descriptor quantizations as ”visual words”. Instead a group of selected SIFT features of an object together with their spatial arrangement are represented by an attributed graph. Each graph is then regarded as a ”visual word”. We measure the similarity between graphs using the similarity of SIFT features and the compatibility of their arrangement. Using the similarity measure we efficiently identify the set of K nearest neighbor graphs (KNNG) using a SOM based clustering tree. We then extend the concept of “query expansion” widely used in text retrieval to develop a graph clustering method based on pairwise similarity propagation (SPGC), in that the trained KNNG information is utilized for speeding up. Using SOM based clustering tree and SPGC, we develop a framework for scalable object indexing and retrieval. We illustrate these ideas on a database of over 50K images spanning more than 500 objects. We show that the precision is substantially boosted, achieving total recall in many cases.

Graph-based approaches for pattern recognition techniques are commonly designed for unsupervised and semi-supervised ones. Recently, a novel collection of supervised pattern recognition techniques based on an optimum-path forest (OPF) computation in a feature space induced by graphs were presented: the OPF-based classifiers. They have some advantages with respect to the widely used supervised classifiers: they do not make assumption of shape/separability of the classes and run training phase faster. Actually, there exists two versions of OPF-based classifiers: OPF

cpl

(the first one) and OPF

knn

. Here, we introduce a learning algorithm for the last one and we show that a classifier can learns with its own errors without increasing its training set.

Isomap emerged as a powerful tool for analyzing input patterns on manifolds of the underlying space. It builds a neighborhood graph derived from the observable distance information and recomputes pairwise distances as the shortest path on the neighborhood graph. In the present paper, Isomap is applied to graph based pattern representations. For measuring pairwise graph dissimilarities, graph edit distance is used. The present paper focuses on classification and employs a support vector machine in conjunction with kernel values derived from original and Isomap graph edit distances. In an experimental evaluation on five different data sets from the IAM graph database repository, we show that in four out of five cases the graph kernel based on Isomap edit distance performs superior compared to the kernel relying on the original graph edit distances.

The collection of behavior protocols is a common practice in human factors research, but the analysis of these large data sets has always been a tedious and time-consuming process. We are interested in automatically finding

canonical behaviors

: a small subset of behavioral protocols that is most representative of the full data set, providing a view of the data with as few protocols as possible. Behavior protocols often have a natural graph-based representation, yet there has been little work applying graph theory to their study. In this paper we extend our recent algorithm by taking into account the graph topology induced by the paths taken through the space of possible behaviors. We applied this technique to find canonical web-browsing behaviors for computer users. By comparing identified canonical sets to a ground truth determined by expert human coders, we found that this graph-based metric outperforms our previous metric based on edit distance.

In this paper, we propose a new approach for keypoint-based object detection. Traditional keypoint-based methods consist of classifying individual points and using pose estimation to discard misclassifications. Since a single point carries no relational features, such methods inherently restrict the usage of structural information. Therefore, the classifier considers mostly appearance-based feature vectors, thus requiring computationally expensive feature extraction or complex probabilistic modelling to achieve satisfactory robustness. In contrast, our approach consists of classifying graphs of keypoints, which incorporates structural information during the classification phase and allows the extraction of simpler feature vectors that are naturally robust. In the present work, 3-vertices graphs have been considered, though the methodology is general and larger order graphs may be adopted. Successful experimental results obtained for real-time object detection in video sequences are reported.

This paper describes a new approach for regularising triangulated graphs. We commence by embedding the graph onto a manifold using the heat-kernel embedding. Under the embedding, each first-order cycle of the graph becomes a triangle. Our aim is to use curvature information associated with the edges of the graph to effect regularisation. Using the difference in Euclidean and geodesic distances between nodes under the embedding, we compute sectional curvatures associated with the edges of the graph. Using the Gauss Bonnet Theorem we compute the Gaussian curvature associated with each node from the sectional curvatures and through the angular excess of the geodesic triangles. Using the curvature information we perform regularisation with the advantage of not requiring the solution of a partial differential equation. We experiment with the resulting regularization process, and explore its effect on both graph matching and graph clustering.

Matrix representations for graphs play an important role in combinatorics. In this paper, we investigate four matrix representations for graphs and carry out an characteristic polynomial analysis upon them. The first two graph matrices are the adjacency matrix and Laplacian matrix. These two matrices can be obtained straightforwardly from graphs. The second two matrix representations, which are newly introduced [9][3], are closely related with the Ihara zeta function and the discrete time quantum walk. They have a similar form and are established from a transformed graph, i.e. the oriented line graph of the original graph. We make use of the characteristic polynomial coefficients of the four matrices to characterize graphs and construct pattern spaces with a fixed dimensionality. Experimental results indicate that the two matrices in the transformed domain perform better than the two matrices in the original graph domain whereas the matrix associated with the Ihara zeta function is more efficient and effective than the matrix associated with the discrete time quantum walk and the remaining methods.

In this paper, we introduce a novel descriptor of graph complexity which can be computed in real time and has the same qualitative behavior of polytopal (Birkhoff) complexity, which has been successfully tested in the context of Bioinformatics. We also show how the phase-change point may be characterized in terms of the Laplacian spectrum, by analyzing the derivatives of the complexity function. In addition, the new complexity notion (

flow complexity

) is applied to cluster a database of Reeb graphs coming from analyzing 3D objects.

Structural pattern recognition describes and classifies data based on the relationships of features and parts. Topological invariants, like the Euler number, characterize the structure of objects of any dimension. Cohomology can provide more refined algebraic invariants to a topological space than does homology. It assigns ‘quantities’ to the chains used in homology to characterize holes of any dimension. Graph pyramids can be used to describe subdivisions of the same object at multiple levels of detail. This paper presents cohomology in the context of structural pattern recognition and introduces an algorithm to efficiently compute representative cocycles (the basic elements of cohomology) in 2D using a graph pyramid. Extension to nD and application in the context of pattern recognition are discussed.

This article shows how the interactive segmentation tool termed “Active Paintbrush” and a fully automatic region merging can both be based on the theoretical framework of contraction kernels within irregular pyramids instead of their own, specialized data structures. We introduce “continous pyramids” in which we purposely drop the common requirement of a fixed reduction factor between successive levels, and we show how contraction kernels can be annotated for a fast navigation of such pyramids. Finally, we use these concepts for improving the integration of the automatic region merging and the interactive tool.

The extraction of a 3D topological map from an Oriented Boundary Graph can be needed to refine a 3D Split and Merge segmentation using topological information such as the Euler characteristic of regions. A presegmentation could thus be efficiently obtained using a light structuring model, before proceeding to the extraction of more information on some regions of interest. In this paper, we present the topological map extraction algorithm which allows to reconstruct locally a set of regions from the Oriented Boundary Graph. A comparison of the two models is also presented.

We present an irregular image pyramid which is derived from multi-scale analysis of segmented watershed regions. Our framework is based on the development of regions in the Gaussian scale-space, which is represented by a region hierarchy graph. Using this structure, we are able to determine geometrically precise borders of our segmented regions using a region focusing. In order to handle the complexity, we select only stable regions and regions resulting from a merging event, which enables us to keep the hierarchical structure of the regions. Using this framework, we are able to detect objects of various scales in an image. Finally, the hierarchical structure is used for describing these detected regions as aggregations of their parts. We investigate the usefulness of the regions for interpreting images showing building facades with parts like windows, balconies or entrances.

Combinatorial maps define a general framework which allows to encode any subdivision of an

n

-D orientable quasi-manifold with or without boundaries. Combinatorial pyramids are defined as stacks of successively reduced combinatorial maps. Such pyramids provide a rich framework which allows to encode fine properties of the objects (either shapes or partitions). Combinatorial pyramids have first been defined in 2D. This first work has later been extended to pyramids of

n

-D generalized combinatorial maps. Such pyramids allow to encode stacks of non orientable partitions but at the price of a twice bigger pyramid. These pyramids are also not designed to capture efficiently the properties connected with orientation. The present work presents our first results on the design of a pyramid of

n

-D combinatorial maps.

In [4], given a binary 26-adjacency voxel-based digital volume

V

, the homological information (that related to

n

-dimensional holes: connected components, ”tunnels” and cavities) is extracted from a linear map (called homology gradient vector field) acting on a polyhedral cell complex

P

(

V

) homologically equivalent to

V

. We develop here an alternative way for constructing

P

(

V

) based on homological algebra arguments as well as a new more efficient algorithm for computing a homology gradient vector field based on the contractibility of the maximal cells of

P

(

V

).

This paper proposes to transform data scanned randomly in a well-defined space (e.g, Euclidean) along a hierarchical irregular pyramidal structure in an attempt reduce search time consumed querying these random data. Such a structure is built as a series of graphs with different resolutions. Levels are constructed and surviving cells are chosen following irregular irregular pyramidal rules and according to a proximity criterion among the space points under consideration. Experimental results show that using such a structure to query data can save considerable search time.

In this paper, we present a novel graph construction method and demonstrate its usage in a broad range of applications starting from a relatively simple single-surface segmentation and ranging to very complex multi-surface multi-object graph based image segmentation. Inspired by the properties of electric field direction lines, the proposed method for graph construction is inherently applicable to n-D problems. In general, the electric field direction lines are used for graph “column” construction. As such, our method is robust with respect to the initial surface shape and the graph structure is easy to compute. When applied to cross-surface mapping, our approach can generate one-to-one and every-to-every vertex correspondent pairs between the regions of mutual interaction, which is a substantially better solution compared with other surface mapping techniques currently used for multi-object graph-based image segmentation.

Image segmentation has long been an important problem in the computer vision community. In our recent work we have addressed the problem of texture segmentation, where we combined top-down and bottom-up views of the image into a unified procedure. In this paper we extend our work by proposing a modified procedure which makes use of graphs of image regions. In the top-down procedure a quadtree of image region descriptors is obtained in which a novel affine contractive transformation based on neighboring regions is used to update descriptors and determine stable segments. In the bottom-up procedure we form a planar graph on the resulting stable segments, where edges are present between vertices representing neighboring image regions. We then use a vertex merging technique to obtain the final segmentation. We verify the effectiveness of this procedure by demonstrating results which compare well to other recent techniques.

A generic model-based segmentation algorithm is presented. Based on a set of training data, consisting of images with corresponding object segmentations, a local appearance and local shape model is build. The object is described by a set of landmarks. For each landmark a local appearance model is build. This model describes the local intensity values in the image around each landmark. The local shape model is constructed by considering the landmarks to be vertices in an undirected graph. The edges represent the relations between neighboring landmarks. By implying the

markovianity

property on the graph, every landmark is only directly dependent upon its neighboring landmarks, leading to a local shape model. The objective function to be minimized is obtained from a maximum

a-posteriori

approach. To minimize this objective function, the problem is discretized by considering a finite set of possible candidates for each landmark. In this way the segmentation problem is turned into a labeling problem. Mean field annealing is used to optimize this labeling problem. The algorithm is validated for the segmentation of teeth from cone beam computed tomography images and for automated cephalometric analysis.

The efficiency of a pyramid segmentation approach mainly depends on the graph selected to encode the information within each pyramid level, on the reduction or decimation scheme used to build one graph from the graph below, and on the criteria employed to define if two adjacent regions are similar or not. This paper evaluates three pairwise comparison functions for perceptual grouping into a generic framework for image perceptual segmentation. This framework integrates the low–level definition of segmentation with a domain–independent perceptual grouping. The performance of the framework using the different comparison functions has been quantitatively evaluated with respect to ground-truth segmentation data using the Berkeley Segmentation Dataset and Benchmark providing satisfactory scores.