In some applications of matching, the structural or hierarchical properties of the two graphs being aligned must be maintained. The hierarchical properties are induced by the direction of the edges in the two directed graphs. These structural relationships defined by the hierarchy in the graphs act as a constraint on the alignment. In this paper, we formalize the above problem as the weighted alignment between two directed acyclic graphs. We prove that this problem is NP-complete, show several upper bounds for approximating the solution, and finally introduce polynomial time algorithms for sub-classes of directed acyclic graphs.
Both of these problems have many practical applications, in particular, graph isomorphism has received a lot of attention in the area of computer vision. Images or objects can be represented as a graph. A weighted graph can be used to formulate a structural description of an object @cite_24 . There have been two main approaches to solving graph isomorphism: state--space construction with searching and nonlinear optimization. The first method consists of building the state--space, which can then be searched. This method has an exponential running time in the worst case scenario, but by employing heuristics, the search can be reduced to a low--order polynomial for many types of graphs @cite_20 @cite_9 . With the second approach (nonlinear optimization), the most successful approaches have been relaxation labeling @cite_27 , neural networks @cite_18 , linear programming @cite_8 , eigendecomposition @cite_0 , genetic algorithms @cite_4 , and Lagrangian relaxation @cite_21 .
@cite_18 @cite_4 @cite_8 @cite_9 @cite_21 @cite_24 @cite_0 @cite_27 @cite_20
1967974926 1594073672 2161444532 2006836707 2035143052 2108182844 2107792892 2013563330
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. Genetic algorithms (GA) can be exploited for optimal graph matching. Graphs represent powerful method of a pattern formal description. Globally optimal graph matching is a NP-complete problem. Pattern distortions and noise increase an optimal search difficulty which could be tackled using GA. This paper describes results of simple GA applied on a graph matching problem. As a conclusion, the suitable GA for an optimal graph "isomorphism" and "monomorphism" is proposed. Used coding resembles the travelling salesman problem (TSP). Consequently, performance of ordering operators has been tested. In contrast to the TSP, the fitness function depends on chromosome value positioning not ordering. It results in differences between optimal GA configuration for graph matching and for TSP. > A linear programming (LP) approach is proposed for the weighted graph matching problem. A linear program is obtained by formulating the graph matching problem in L sub 1 norm and then transforming the resulting quadratic optimization problem to a linear one. The linear program is solved using a simplex-based algorithm. Then, approximate 0-1 integer solutions are obtained by applying the Hungarian method on the real solutions of the linear program. The complexity of the proposed algorithm is polynomial time, and it is O(n sup 6 L) for matching graphs of size n. The developed algorithm is compared to two other algorithms. One is based on an eigendecomposition approach and the other on a symmetric polynomial transform. Experimental results showed that the LP approach is superior in matching graphs than both other methods. > A Lagrangian relaxation network for graph matching is presented. The problem is formulated as follows: given graphs G and g, find a permutation matrix M that brings the two sets of vertices into correspondence. Permutation matrix constraints are formulated in the framework of deterministic annealing. Our approach is in the same spirit as a Lagrangian decomposition approach in that the row and column constraints are satisfied separately with a Lagrange multiplier used to equate the two "solutions". Due to the unavoidable symmetries in graph isomorphism (resulting in multiple global minima), we add a symmetry-breaking self-amplification term in order to obtain a permutation matrix. With the application of a fixpoint preserving algebraic transformation to both the distance measure and self-amplification terms, we obtain a Lagrangian relaxation network. The network performs minimization with respect to the Lagrange parameters and maximization with respect to the permutation matrix variables. Simulation results are shown on 100 node random graphs and for a wide range of connectivities. In this paper we formally define the structural description of an object and the concepts of exact and inexact matching of two structural descriptions. We discuss the problems associated with a brute-force backtracking tree search for inexact matching and develop several different algorithms to make the tree search more efficient. We develop the formula for the expected number of nodes in the tree for backtracking alone and with a forward checking algorithm. Finally, we present experimental results showing that forward checking is the most efficient of the algorithms tested. An approximate solution to the weighted-graph-matching problem is discussed for both undirected and directed graphs. The weighted-graph-matching problem is that of finding the optimum matching between two weighted graphs, which are graphs with weights at each arc. The proposed method uses an analytic instead of a combinatorial or iterative approach to the optimum matching problem. Using the eigendecompositions of the adjacency matrices (in the case of the undirected-graph-matching problem) or Hermitian matrices derived from the adjacency matrices (in the case of the directed-graph-matching problem), a matching close to the optimum can be found efficiently when the graphs are sufficiently close to each other. Simulation results are given to evaluate the performance of the proposed method. > A large class of problems can be formulated in terms of the assignment of labels to objects. Frequently, processes are needed which reduce ambiguity and noise, and select the best label among several possible choices. Relaxation labeling processes are just such a class of algorithms. They are based on the parallel use of local constraints between labels. This paper develops a theory to characterize the goal of relaxation labeling. The theory is founded on a definition of con-sistency in labelings, extending the notion of constraint satisfaction. In certain restricted circumstances, an explicit functional exists that can be maximized to guide the search for consistent labelings. This functional is used to derive a new relaxation labeling operator. When the restrictions are not satisfied, the theory relies on variational cal-culus. It is shown that the problem of finding consistent labelings is equivalent to solving a variational inequality. A procedure nearly identical to the relaxation operator derived under restricted circum-stances serves in the more general setting. Further, a local convergence result is established for this operator. The standard relaxation labeling formulas are shown to approximate our new operator, which leads us to conjecture that successful applications of the standard methods are explainable by the theory developed here. Observations about con-vergence and generalizations to higher order compatibility relations are described. Attributed relational graphs (ARGs) have shown superior qualities when used for image representation and analysis in computer vision systems. A new, efficient approach for calculating a global distance measure between attributed relational graphs is proposed, and its applications in computer vision are discussed. The distance measure is calculated by a global optimization algorithm that is shown to be very efficient for this problem. The approach shows good results for practical size ARGs. The technique is also suitable for parallel processing implementation.