Narrow Results

A scheme for learning and recognizing 3D objects from their 2D views is presented. The scheme proceeds in two stages. In the first stage, we try to learn a prototype automatically from 2D training images of different objects which belong to the same object class and consequently have similar shapes of parts and similar adjacency relations between the parts. In the second stage, the generated prototype is used to recognize learned objects or the objects similar to the learned ones from images of complex real scenes. We tested the approach on recognizing some simple objects from images of indoor scenes and got satisfactory results.

We describe an object recognition system based on symbolic contour graphs. The image to be analyzed is transformed into a graph with object corners as vertices and connecting contours as edges. Image corners are determined using a robust multiscale corner detector. Edges are constructed by line-following between corners based on evidence from the multiscale Gabor wavelet transform. Model matching is done by finding subgraph isomorphisms in the image graph. The complexity of the algorithm is reduced by labeling vertices and edges, whereby the choice of labels also makes the recognition system invariant under translation, rotation and scaling. We provide experimental evidence and theoretical arguments that the matching complexity is below O(#V³), and show that the system is competitive with other graph-based matching systems.

Graphs and graph matching are powerful mechanisms for knowledge representation, pattern recognition and machine learning. Especially in computer vision their application is manifold. Graphs can characterize relations among image features like points or regions but they may also represent symbolic object knowledge. Hence, graph matching can accomplish recognition tasks on different levels of abstraction.

In this contribution, we demonstrate that graphs may also bridge the gap between different levels of knowledge representation. We present a system for visual assembly monitoring that integrates bottom-up and top-down strategies for recognition and automatically generates and learns graph models to recognize assembled objects. Data-driven processing is subdived into three stages: first, elementary objects are recognized from low-level image features. Then, clusters of elementary objects are analyzed syntactically; if an assembly structure is found, it is translated into a graph that uniquely models the assembly. Finally, symbolic models like this are stored in a database so that individual assemblies can be recognized by means of graph matching. At the same time, these graphs enable top-down knowledge propagation: they are transformed into graphs which represent relations between image features and thus describe the visual appearance of the recently found assembly. Therefore, due to model-driven knowledge propagation assemblies may subsequently be recognized from graph matching on a lower computational level and tedious bottom-up processing becomes superfluous.

Symbol recognition is a well-known challenge in the field of graphics recognition. Due to the representational power of graph structures, a number of graph-based approaches are used to answer whether a known symbol appears in a document and under which degree of confidence. In this paper, we review the particularities of graph structures representing technical drawings and we classify them in two categories, depending on whether the structure that they represent consists of prototype patterns or repetitive patterns. The recognition is then formulated in terms of graph matching or graph parsing, respectively. Since some symbols consist of two types of structures, the main contribution of this work is to propose a combined strategy. In addition, the combination of graph matching and graph parsing processes is based on a common graph structure that also involves a graph indexing mechanism. Graph nodes are classified in equivalence classes depending on their local configuration. Graph matching indexes in such equivalence classes using the information of model graph nodes as local descriptors, and then global consistency is checked using the graph edge attributes. On the other hand, representatives of equivalence classes are used as tokens of a graph grammar that guides a parsing process to recognize repetitive structures.

In this paper we describe a classification method that allows the use of graph-based representations of data instead of traditional vector-based representations. We compare the vector approach combined with the k-Nearest Neighbor (k-NN) algorithm to the graph-matching approach when classifying three different web document collections, using the leave-one-out approach for measuring classification accuracy. We also compare the performance of different graph distance measures as well as various document representations that utilize graphs. The results show the graph-based approach can outperform traditional vector-based methods in terms of accuracy, dimensionality and execution time.

Graphs provide us with a powerful and flexible representation formalism for pattern classification. Many classification algorithms have been proposed in the literature. However, the vast majority of these algorithms rely on vectorial data descriptions and cannot directly be applied to graphs. Recently, a growing interest in graph kernel methods can be observed. Graph kernels aim at bridging the gap between the high representational power and flexibility of graphs and the large amount of algorithms available for object representations in terms of feature vectors. In the present paper, we propose an approach transforming graphs into n-dimensional real vectors by means of prototype selection and graph edit distance computation. This approach allows one to build graph kernels in a straightforward way. It is not only applicable to graphs, but also to other kind of symbolic data in conjunction with any kind of dissimilarity measure. Thus it is characterized by a high degree of flexibility. With several experimental results, we prove the robustness and flexibility of our new method and show that our approach outperforms other graph classification methods on several graph data sets of diverse nature.

Graphs provide us with a flexible and powerful way to represent objects in various areas of computer science. One of the main drawbacks is, however, that many standard algorithms on graphs have a high computational complexity. 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 an assignment 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 diverse graph data sets we demonstrate substantial speedups of our proposed method over several standard procedures for graph isomorphism. Furthermore, although the computational framework for isomorphism is suboptimal, we show that the proposed algorithm rejects only very few pairs of graphs and otherwise returns correct results.

In this paper, we examine the main advances registered in the last ten years in Pattern Recognition methodologies based on graph matching and related techniques, analyzing more than 180 papers; the aim is to provide a systematic framework presenting the recent history and the current developments. This is made by introducing a categorization of graph-based techniques and reporting, for each class, the main contributions and the most outstanding research results.

The graph edit distance (GED) is a flexible distance measure which is widely used for inexact graph matching. Since its exact computation is ${𝒩}{𝒫}$-hard, heuristics are used in practice. A popular approach is to obtain upper bounds for GED via transformations to the linear sum assignment problem with error-correction (LSAPE). Typically, local structures and distances between them are employed for carrying out this transformation, but recently also machine learning techniques have been used. In this paper, we formally define a unifying framework LSAPE-GED for transformations from GED to LSAPE. We also introduce rings, a new kind of local structures designed for graphs where most information resides in the topology rather than in the node labels. Furthermore, we propose two new ring-based heuristics RING and RING-ML, which instantiate LSAPE-GED using the traditional and the machine learning-based approach for transforming GED to LSAPE, respectively. Extensive experiments show that using rings for upper bounding GED significantly improves the state of the art on datasets where most information resides in the graphs’ topologies. This closes the gap between fast but rather inaccurate LSAPE-based heuristics and more accurate but significantly slower GED algorithms based on local search.

In this paper, we discuss how rule based expert system shells can be used in pattern recognition for the implementation of algorithms which are procedurally oriented in their nature rather than rule based, and have traditionally been implemented in procedural programming languages. Particular examples include finite state automata, context free parsing, string matching, graph matching and discrete relaxation.

A recursive descent tree traversal algorithm is presented to find the point correspondences between two views. Given two sets of noisy 3-D feature points on multiple rigid objects at two time-sequential views, the points at the first view are constructed as a graph and then another graph is derived from those feature points at the second view so that a maximal matching point and minimum matching error is obtained. The correspondence of the vertices is then found. The algorithm can also he used when the number of points at two views are different. Therefore, after matching, the occluded points at either view or both views can be identified. The computation time of the proposed algorithm is large when the number of feature points is large. A data set splitting strategy for such cases, which can significantly reduce the computation time, is presented. Another algorithm presented is one in which motion parameters are estimated from a matched subgraph and are then used to guide the matching for the rest of the nodes. Computer simulations are performed to show the efficiency and accuracy of the algorithm.

Check forms are used by many people in daily life for money remittances. Surprisingly, the processing of these forms at banks and post offices is only partly automated. In this paper, we consider a particular kind of form, viz., the GIRO check forms used in Switzerland. We will describe a fully automatic system which is able to recognise the financial institution, the name and address of the receiver, and the account number on a GIRO check. The system comprises procedures for binarization, segmentation, model matching, and optical character recognition (OCR). Experiments on a sample set of 48 checks have shown promising results in terms of both computation time and recognition accuracy.

A surface feature hypergraph (SFAHG) representation is proposed for the recognition and localization of three-dimensional objects. The hypergraph representation is shown to be viewpoint independent thus resulting in substantial savings in terms of memory for the object model database. The resulting hypergraph matching algorithm integrates both, relational and the rigid pose constraint in a consistent unified manner. The matching algorithm is also shown to have a polynomial order of complexity even in multiple-object scenes with instances of objects partially occluding each other. An algorithm for incrementally constructing the hypergraph representation of an object model from range images of the object taken from different viewpoints is also presented. The hypergraph matching and the hypergraph construction algorithms are shown to be capable of correcting errors in the initial segmentation of the range image. The hypergraph construction algorithm and the matching algorithm are tested on range images of scenes containing multiple three-dimensional objects with partial occlusion.

A powerful and universal data structure with applications invarious subfields of science and engineering is graphs. In computer vision and image analysis, graphs are often used for the representation of structured objects. For example, if the problem is to recognize instances of known objects in an image, then often models, or prototypes, of the known objects are represented by means of graphs and stored in a database. The unknown objects in the input image are extracted by means of suitable preprocessing and segmentation algorithms, and represented by graphs that are analogous to the model graphs. Thus, the problem of object recognition is transformed into a graph matching problem.

In this paper, it is assumed that there is an input graph that is given on-line, and a number of model, or prototype, graphs that are known a priori. We present a new approach to subgraph isomorphism detection which is based on a compact representation of the model graphs that is computed off-line. Subgraphs that appear multiple times within the same or within different model graphs are represented only once, thus reducing the computational effort to detect them in an input graph. In the extreme case where all model graphs are highly similar, the run time of the new algorithm becomes independent of the number of model graphs. We also describe an extension of this method to error-correcting graph matching. Furthermore, an approach to subgraph isomorphism detection based on decision trees is proposed. A decision tree is generated from the models in an off-line phase. This decision tree can be used for subgraph isomorphism detection. The time needed for decision tree traversal is only polynomial in terms of the number of nodes of the input graph. Moreover, the time complexity of the decision tree traversal is completely independent on the number of model graphs, regardless of their similarity. However, the size of the decision tree is exponential in the number of nodes of the models. To cut down the space complexity of the decision tree, some pruning strategies are discussed.

Check amount recognition is one of the most promising commercial applications of handwriting recognition. This paper is devoted to the description of the check reading system developed to recognize amounts on American personal checks. Special attention is paid to a reliable procedure developed to reject doubtful answers. For this purpose the legal (worded) amount on a personal check is recognized along with the courtesy (digit) amount. For both courtesy and legal amount fields, a brief description of all recognition stages beginning with field extraction and ending with the recognition itself are presented. We also present the explanation of problems existing at each stage and their possible solutions. The numeral recognizer used to read the amounts written in figures is described. This recognizer is based on the procedure of matching input subgraphs to graphs of symbol prototypes. Main principles of the handwriting recognizer used to read amounts written in words are explained. The recognizer is based on the idea of describing the handwriting with the most stable handwriting elements. The concept of the optimal confidence level of the recognition answer is introduced. It is shown that the conditional probability of the answer correctness is an optimal confidence level function. The algorithms of the optimal confidence level estimation for some special cases are described. The sophisticated algorithm of cross validation between legal and courtesy amount recognition results based on the optimal confidence level approach is proposed. Experimental results on real checks are presented. The recognition rate at 1% error rate is 67%. The recognition rate without reject is 85%. Significant improvement is achieved due to legal amount processing in spite of a relatively low recognition rate for this field.

In this paper we present a fast algorithm for the computation of error-correcting graph isomorphisms. The new algorithm is an extension of a method for exact subgraph isomorphism detection from an input graph to a set of a priori known model graphs, which was previously developed by the authors. Similar to the original algorithm, the new method is based on the idea of creating a decision tree from the model graphs. This decision tree is compiled off-line in a preprocessing step. At run time, it is used to find all error-correcting graph isomorphisms from an input graph to any of the model graphs up to a certain degree of distortion. The main advantage of the new algorithm is that error-correcting graph isomorphism detection is guaranteed to require time that is only polynomial in terms of the size of the input graph. Furthermore, the time complexity is completely independent of the number of model graphs and the number of edges in each model graph. However, the size of the decision tree is exponential in the size of the model graphs and the degree of error. Nevertheless, practical experiments have indicated that the method can be applied to graphs containing up to 16 vertices.

In this paper, two different methodologies respectively based on an unsupervised self-organizing (SOM) neural network and on a graph matching are shown and discussed to validate the performance of a new 3D facial feature identification and localization algorithm. Experiments are performed on a dataset of 23 3D faces acquired by a 3D laser camera at eBIS lab with pose and expression variations. In particular results referred to five nose landmarks are encouraging and reveal the validity of this approach that although low computational complexity and the small number of landmarks guarantees an average face recognition performance greater than 80%.

ABSURDIST II, an extension to ABSURDIST, is an algorithm using attributed graph matching to find translations between conceptual systems. It uses information about the internal structure of systems by itself, or in combination with external information about concept similarities across systems. It supports systems with multiple types of weighted or unweighted, directed or undirected relations between concepts. The algorithm exploits graph sparsity to improve computational efficiency. We present the results of experiments with a number of conceptual systems, including artificially constructed random graphs with introduced distortions.

Recognizing topological analogy between the parts of semantic network seems to be very important step in the process of semantic categorization and interpretation of data that are embedded into the semantic network. Considering the semantic network as a set of graphs, recognition of topological analogy between the parts of semantic network can be treated as maximum common subgraph problem which falls in the group of exact graph matching problems. In this paper authors propose a new algorithm for maximum common subgraph detection aimed to a specific semantic network called Active Semantic Model (ASM). This semantic network can be represented as the set of labeled directed multigraphs with unique node labels. The structure of these graphs is specific because associations or edges are labeled with several attributes and some of them are related to nodes connected by edge. That kind of association-oriented structure enables associations or edges to play key role in the process of semantic categorization and interpretation of data. Furthermore, this kind of structure enables modeling semantic contexts in a form of semantically designated graphs (of associations). Proposed algorithm is capable of recognizing simultaneously maximum common subgraph of input graph and each of the graphs representing different contexts in ASM semantic network.

The Web has become a huge and indispensable source of information to be used and shared globally, where knowledge is commonly represented and stored in RDF, or alternatively, in conceptual graphs. Managing and searching for web information have gone beyond the relational database model, as the data are semi-structured and inexact answers are often the case. Usually, approximate searching results are due to mismatching between entity types and names in a query and an answer. Firstly, this research work focuses on partial subsumption of a query graph to an answer graph, which is an unsymmetric measure in contrast to similarity. Secondly, it proposes a population-based method for defining subsumption degrees between entity types, one to another, and a class-sensitive soft TF-IDF method for entity names. Lastly, on the one hand, for a user-friendly interface and easily readable query expressions, conceptual graphs are employed at the front-end. On the other hand, in order to take the advantage of the existing platform of SeRQL, an exact RDF query language, the query modification tactic is used to retrieve the knowledge graphs that are close to a query graph, before the subsumption degrees of the query graph to those answer graphs are calculated.