2009 | OriginalPaper | Buchkapitel
Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions
verfasst von : Christian Knauer, Klaus Kriegel, Fabian Stehn
Erschienen in: Frontiers in Algorithmics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
$\mathcal{P}$
of weighted point sets (anatomic landmarks measured from a patient), a second sequence
$\mathcal{Q}$
of corresponding point sets (defined in a 3D model of the patient) and a transformation class
$\mathcal{T}$
, compute the transformations
$t\in\mathcal{T}$
that minimize the
weighted
directed Hausdorff distance of
$t(\mathcal{P})$
to
$\mathcal{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 ℝ
3
.