×

Minimizing the weighted directed Hausdorff distance between colored point sets under translations and rigid motions. (English) Zbl 1206.68321

Summary: 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 a landmark can be measured with.
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 \(\mathbb R^3\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
92C50 Medical applications (general)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alt, H.; Guibas, L., Discrete geometric shapes: matching, interpolation, and approximation, (Handbook of Computational Geometry (2000), Elsevier B.V.), 121-153 · Zbl 0995.65023
[2] F. Hoffmann, K. Kriegel, S. Schönherr, C. Wenk, A simple and robust geometric algorithm for landmark registration in computer assisted neurosurgery, Tech. Rep. B 99-21, Freie Universität Berlin, Fachbereich Mathematik und Informatik, Germany, December 1999.; F. Hoffmann, K. Kriegel, S. Schönherr, C. Wenk, A simple and robust geometric algorithm for landmark registration in computer assisted neurosurgery, Tech. Rep. B 99-21, Freie Universität Berlin, Fachbereich Mathematik und Informatik, Germany, December 1999.
[3] Besl, P. J.; McKay, N. D., A method for registration of 3-D shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, 14, 2, 239-256 (1992)
[4] D. Dimitrov, C. Knauer, K. Kriegel, Registration of 3D-Patterns and Shapes with Characteristic Points, in: Proceedings of International Conference on Computer Vision Theory and Applications — VISAPP 2006, Setúbal, Portugal, 2006, pp. 393-400.; D. Dimitrov, C. Knauer, K. Kriegel, Registration of 3D-Patterns and Shapes with Characteristic Points, in: Proceedings of International Conference on Computer Vision Theory and Applications — VISAPP 2006, Setúbal, Portugal, 2006, pp. 393-400.
[5] D. Dimitrov, C. Knauer, K. Kriegel, F. Stehn, Approximation algorithms for a point-to-surface registration problem in medical navigation, in: Proc. Frontiers of Algorithmics Workshop, Lanzhou, China, 2007, pp. 26-37.; D. Dimitrov, C. Knauer, K. Kriegel, F. Stehn, Approximation algorithms for a point-to-surface registration problem in medical navigation, in: Proc. Frontiers of Algorithmics Workshop, Lanzhou, China, 2007, pp. 26-37. · Zbl 1214.68463
[6] Huttenlocher, D. P.; Kedem, K.; Sharir, M., The upper envelope of Voronoi surfaces and its applications, (SCG’91: Proceedings of the Seventh Annual Symposium on Computational Geometry (1991), ACM: ACM New York, NY, USA), 194-203
[7] Sharir, M.; Agarwal, P. K., Davenport-Schinzel Sequences and their Geometric Applications (1996), Cambridge University Press: Cambridge University Press New York, NY, USA · Zbl 0857.68109
[8] Aurenhammer, F.; Edelsbrunner, H., An optimal algorithm for constructing the weighted Voronoi diagram in the plane, Pattern Recognition, 17, 2, 251-257 (1984) · Zbl 0539.52008
[9] Hershberger, J., Finding the upper envelope of n line segments in \(O(n \log n)\) time, Information Processing Letters, 33, 4, 169-174 (1989) · Zbl 0689.68058
[10] Rucklidge, W., Lower bounds for the complexity of the graph of the Hausdorff distance as a function of transformation, Discrete & Computational Geometry, 16, 2, 135-153 (1996) · Zbl 0853.68111
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.