Geometric matching problems are among the most intensely studied fields in Computational Geometry. A geometric matching problem can be formulated as follows: given are two geometric objects P and Q. These objects are taken from a class of geometric objects G and P is called the "pattern" and Q is called the "model". A geometric matching instance is defined for a distance measure dist and a transformation class T. The task is to find the transformations t of T that minimizes dist(t(P),Q). In this thesis, geometric hybrid registration problems are studied. Registration problems are closely related to geometric matching problems. The term geometric registration problem describes the task of mapping points from one space ("pattern space") to their corresponding points in a deformed copy of that space called "model space". This research is motivated by a real world application: navigated surgery. Here, the goal is to register an operation theatre space (pattern space) to the internal coordinate system (model space) of a medical navigation system. The purpose of a medical navigation system is to support surgeons by visualizing the used surgical instruments at their correct position in a 3D- model of a patient. The models are generated beforehand based on CT or MRT scans. Hybrid registration is a novel strategy to compute solutions for this alignment problem. Geometric hybrid registrations reduce the spatial synchronization problem to a series of (at least two) geometric matching problems that are solved interdependently. Usually, a computationally involved point-to-surface matching is combined with a comparably simpler but underdefined point-to-point matching. The point-to-surface matching is computed for a sufficiently large and suitably distributed set of points (called surface points) measured in the pattern space to a geometric surface in the model space. For the point-to-point matching, a small set of (one to three) characteristic points are measured in the pattern space and are defined in the model space. In the context of the intended application, these points are called anatomic landmarks - anatomically exposed spots within the field of interest.
Geometrische Musteranpassungsprobleme gehören zu den am intensivsten studierten Felder der Algorithmischen Geometrie. Ein geometrisches Musteranpassungsproblem kann wie folgt formuliert werden: Gegeben sind zwei geometrische Objekte P und Q. Diese Objekte gehören zu einer Klasse G von geometrischen Objekten, wobei P "Muster" und Q "Modell" genannt wird. Ein geometrisches Musteranpassungsproblem ist bestimmt durch ein Abstandsmaß dist sowie durch eine Transformationsklasse T. Gesucht sind diejenigen Abbildungen t aus T, welche die Zielfunktion dist(t(P), Q) minimieren. In dieser Arbeit werden hybride Registrierungsprobleme untersucht, welche in einem engen Zusammenhang zu geometrischen Musteranpassungsproblemen stehen. Bei einem Registrierungsproblem besteht die Aufgabe darin, eine Abbildung zu finden, die jeden Punkt eines "Musterraums" auf seinen entsprechenden Punkt in einem "Modellraum" abbildet. Die Forschung an dieser Problemstellung ist motiviert durch eine Anwendung aus in der Neurochirurgie -- durch bildgeführte Operationsverfahren. Hierbei wird während einer Operation mit Hilfe eines medizinischen Navigationssystems das verwendete Operationsbesteck in der korrekten relativen Lage und Position in einem 3D-Modell des Patienten visualisiert. Das Modell wird zuvor aus einer CT- oder MRT-Aufnahme generiert. Hierfür ist es notwendig, das Operationsfeld und das interne Koordinatensystem des Navigationssystems aneinander auszurichten; also eine Abbildung zu finden, welche jedem Punkt des Operationsfeldes seinen entsprechenden Punkt im Modellraum zuordnet. Der Schwerpunkt dieser Arbeit liegt auf Registrierungsstrategien, welche das beschriebene Ausrichtungsproblem mit Hilfe eines neuartigen "hybriden" Ansatzes lösen. Hierbei wird das Problem auf eine Menge von (zumindest zwei) geometrischen Musteranpassungsproblemen reduziert, welche in wechselseitiger Abhängigkeit gelöst werden. Die Grundidee ist, ein rechnerisch anspruchsvolles Punkt-zu-Oberflächen Anpassungsproblem mit einem vergleichsweise einfacherem aber unterdefiniertem Punkt-zu-Punkt- Anpassungsproblem zu kombinieren. Die Punkt-zu-Oberflächen-Anpassung wird für eine Menge von im Operationsfeld eingemessenen Punkten und einer im Modellraum definierten Oberfläche berechnet. Die Punkt-zu-Punkt Anpassung hingegen basiert auf einer kleinen Menge von (ein bis drei) so genannten "anatomischen Landmarken". Anatomische Landmarken sind anatomisch exponierte Stellen, welche auf dem Patienten leicht eingemessen und in dem Modell leicht definiert werden können.
