Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions

摘要

Matching geometric objects with respect to their Hausdorff distance is a well investigated problem in computational geometry with various application areas. The variant investigated in this paper is motivated by the problem of determining a matching (in this context also called registration) for neurosurgical operations. The task is: given a sequence P of weighted point sets (anatomic landmarks measured from a patient), a second sequence Q of corresponding point sets (defined in a 3D model of the patient) and a transformation class T, compute the transformations t ∈ T that minimize the weighted directed Hausdorff distance of t(P) to Q. The weighted Hausdorff distance, as introduced in this paper, takes the weights of the point sets into account. For this application, a weight reflects the precision with which a landmark can be measured. We present an exact solution for translations in the plane, a simple 2-approximation as well as a FPTAS for translations in arbitrary dimension and a constant factor approximation for rigid motions in the plane or in R~3.