Noisy pattern matching problems arise in many areas, e.g., computational vision, robotics, guidance and control, stereophotogrammetry, astronomy, genetics, and high-energy physics. Least-squares pattern matching over the Euclidean space E/sup n/ for unordered sets of cardinalities p and q is commonly formulated as a combinatorial optimization problem having complexity p(p-1)/spl middot//spl middot//spl middot/(p-q+1), q/spl les/p. Since p and q may be 10/sup 3/ or larger in typical applications, less than satisfactory suboptimal methods are usually employed. A hybrid approach is described for solving the pattern matching problem under rigid motion constraints, which often apply. The method reduces the complexity to l/sub 21//spl middot/n/sup 4/+l/sub 12//spl middot/p/sup 3/, where l/sub 12/ and l/sub 21/ are the number of iterations required by steepest-ascent and singular value decomposition (SVD)-based procedures, respectively.>

A tool is presented for solving some types of pattern matching problems using the method of steepest-descent/ascent. These matching problems can be recast as function maximization problems with the functions to be maximized being constrained over the orthogonal group. The optimization of these functions is then performed using the steepest-ascent algorithm. This is made possible by representing the orthogonal group as a Lie group and then investigating the gradient vector field associated with the function to be maximized or minimized. Since the orthogonal group includes the group of permutations as a subgroup, the proposed procedure works not only for the continuous optimization problem, but also for the combinatorial problem. The conditions for the convergence of the steepest-ascent algorithms are also shown and simulations are performed.>