Combinatorial optimization applied to variable scale 2D model matching

Abstract

A local search optimization procedure, subset-convergent local search, is developed for identifying known 2D models in broken and skewed line data. Due to fragmentation in the data, the mapping between model and data line segments may be one-to-many. The proposed algorithm starts with a model-data mapping selected at random and refines it until it is locally optimal. Results are presented in which the algorithm frequency converges upon the globally optimal match. This best match can be found with greater confidence by independently running the algorithm several times. The match error being minimized has two basic components, a spatial fit error and an omission error. Spatial fit is a function of the integrated squared perpendicular distance between model lines and data line segments. This measure is minimized, subject to rotation, translation, and scaling, for every set of correspondences tested. The closed-form equation solving for this optimal transform is second order. Although the matching system itself is 2D, results are presented in which the matcher, in conjunction with a 3D robot navigation system, correctly updates estimates of robot position.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>