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

The author studies an application of the rapid transform for classification of entire two-dimensional shapes. The algorithm is based on the transform invariance property under cyclic shifts. A boundary will be represented by a sequence of segments defining the feature vector components of the shape. It is assumed that a sequence of segments corresponding to a rotated pattern, can be deduced from an original sequence of the same pattern by a number of cyclic shifts. Then, the transform of the vector of segments is independent of translation and rotation of the pattern in two dimensions. The classification algorithm will be tested on data derived from a library of two-dimensional aircraft patterns. The results show the algorithm efficiency in terms of computation time and classification.>