This presentation analyses the problem of approximate point set pattern matching, presenting a solution that is applicable to spacecraft navigation. The spacecraft orientation is determined by recognizing a pattern of stars in an image (pattern), from a fixed star catalogue (background).<P>
The approach follows the alignment strategy, where the largest pattern segment is aligned with all background segments of similar length. Each alignment defines a rigid motion that, when applied to the pattern, identifies a region which is cut out of the background. The similarity between pattern and cut-out is measured by means of the directed Hausdorff distance. In order to perform the operations of background cut-out and segment search efficiently, the background is pre-processed, resulting in two data structures.<P>
This work also presents a novel algorithm for determining the Hausdorff distance, which solves all of the nearest neighbour queries at the same time as the Voronoi diagram is computed. Experimental results show that it outperforms the conventional solution, provided that the number of points in the pattern does not exceed a small multiple of the number of points in the background cut-out.<P>
The proposed solution has been implemented and tested with input sizes similar to those of the application domain.
