Narrow 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.

The subgraph isomorphism problem is one of the most important problems for pattern recognition in graphs. Its applications are found in many different disciplines, including chemistry, medicine, and social network analysis. Because of the -completeness of the problem, the existing exact algorithms exhibit an exponential worst-case running time. In this paper, we propose several improvements to the well-known Ullmann's algorithm for the problem. The improvements lower the time consumption as well as the space requirements of the algorithm. We experimentally demonstrate the efficiency of our improvement by comparing it to another set of improvements called FocusSearch, as well as other state-of-the-art algorithms, namely VF2 and LAD.

A generalization of subgraph isomorphism for the fault-tolerant interpretation of disturbed line images has been achieved. Object recognition is effected by optimal matching of a reference graph to the graph of a distorted image. This optimization is based on the solution of linear and quadratic assignment problems. The efficiency of the procedures developed for this objective has been proved in practical applications. NP-complete problems such as subgraph recognition need exhaustive computation if exact (branch-and-bound) algorithms are used. In contrast to this, heuristics are very fast and sufficiently reliable for less complex relational structures of the kind investigated in the first part of this paper. Constrained continuous optimization techniques, such as relaxation labeling and neural network strategies, solve recognition problems within a reasonable time, even in rather complex relational structures where heuristics can fail. They are also well suited to parallelism. The second part of this paper is devoted exclusively to them.

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.

A new method for information extraction from document images is proposed in this paper as the basis for a document reader which can extract the required keywords and their logical relationship from various printed documents. The proposed method consists of robust keyword matching, global document matching, and postprocessing for matching errors. First, robust keyword matching between two-dimensional OCR results consisting of a set of possible character candidate lists and a set of keywords defined in the keyword dictionary is carried out. This keyword dictionary includes incorrect words with typical OCR errors and segments of words in order to deal with OCR errors. Next, document matching is invoked between keyword matching results in an input document and document models. Each document model consists of a set of word models with their logical relationship described in terms of a tree structure. This model matching extracts the required keywords and their logical relationship from the input document and determines the most suitable model for the input document. Finally, postprocessing using heuristic rules defined in the model is applied to document matching results to recover keyword matching errors and to modify keyword matching results. This comprehensive approach solves word segmentation problems accurately even if a document has unknown words, compound words, or incorrect words due to OCR errors. Experimental results obtained for 100 documents show that the method is robust and effective for various document structures.

Networks are powerful representation of topological features in biological systems like protein interaction and gene regulation. In order to understand the design principles of such complex networks, the concept of network motifs emerged. Network motifs are recurrent patterns with statistical significance that can be seen as basic building blocks of complex networks. Identification of network motifs leads to many important applications, such as understanding the modularity and the large-scale structure of biological networks, classification of networks into super-families, protein function annotation, etc. However, identification of network motifs is challenging as it involves graph isomorphism which is computationally hard. Though this problem has been studied extensively in the literature using different computational approaches, we are far from satisfactory results. Motivated by the challenges involved in this field, an efficient and scalable network Motif Discovery algorithm based on Expansion Tree (MODET) is proposed. Pattern growth approach is used in this proposed motif-centric algorithm. Each node of the expansion tree represents a non-isomorphic pattern. The embeddings corresponding to a child node of the expansion tree are obtained from the embeddings of the parent node through vertex addition and edge addition. Further, the proposed algorithm does not involve any graph isomorphism check and the time complexities of these processes are $O(n)$ and $O(1)$, respectively. The proposed algorithm has been tested on Protein–Protein Interaction (PPI) network obtained from the MINT database. The computational efficiency of the proposed algorithm outperforms most of the existing network motif discovery algorithms.

NP-complete and NP-hard problems, such as subgraph isomorphism, are well-known benchmarks to evaluate computation power of unconventional computing approaches. Optical computing, as one of the most important unconventional approaches, has determinant features such as massive parallelism that allows us to solve hard computational problems in an efficient time, while in the similar situations conventional computers require exponential time. In this paper, we solve subgraph isomorphism, as an NP-complete problem, using optical computing in a polynomial time after a polynomial preprocessing time. The proposed method has two main steps: first, possible solution space of the problem is generated using an optical manner and then all invalid solutions are eliminated from the space by several designed optical filters. The filters are made in the preprocessing phase in a polynomial time while the space of each filter is exponential. In this study, we have provided a solution to the YES/NO decision version of the problem.

Detection of ligand-binding sites in protein structures is a crucial task in structural bioinformatics, and has applications in important areas like drug discovery. Given the knowledge of the site in a particular protein structure that binds to a specific ligand, we can search for similar sites in the other protein structures that the same ligand is likely to bind. In this paper, we propose a new method named "BSAlign" (Binding Site Aligner) for rapid detection of potential binding site(s) in the target protein(s) that is/are similar to the query protein's ligand-binding site. We represent both the binding site and the protein structure as graphs, and employ a subgraph isomorphism algorithm to detect the similarities of the binding sites in a very time-efficient manner. Preliminary experimental results show that the proposed BSAlign binding site detection method is about 14 times faster than a well-known method called SiteEngine, while offering the same level of accuracy. Both BSAlign and SiteEngine achieve 60% search accuracy in finding adenine-binding sites from a data set of 126 proteins. The proposed method can be a useful contribution towards speed-critical applications such as drug discovery in which a large number of proteins are needed to be processed. The program is available for download at: http://www1.i2r.a-star.edu.sg/~azeyar/BSAlign/.

A powerful and universal data structure with applications in various 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.