Verfahren zur automatischen Registrierung von Daten aus 3D-Laserscannern basieren oft auf der Erkennung bestimmter Objekte im Scan, wie etwa Targets. Typischerweise wird dabei der Objekttyp identifizifert, nicht aber das Individuum. Dieser Schritt erfolgt mit Hilfe der Korrespondenzfindung, in der die geometrische Konstellation erkannt und zur individuellen Identifizierung verwendet wird.

In dieser Arbeit wird ein Verfahren vorgestellt, das eine solche automatische Korrespondenzfindung realisiert. Sowohl der Algorithmus selbst, als auch Teile seiner Analyse basieren auf einer Kombination aus bestehenden Graph Matching Algorithmen und Konzepten aus dem Information Retrieval.

Weiterhin berücksichtigt er variable Translations- und Rotationsfehler in den Scandaten und ist effizient, bei einer angenommenen Anzahl r von Targets des einen Scans beträgt der Zeitaufwand nur O(r²log(r)), der Platzaufwand O(r²). Die hohe Geschwindigkeit und die Robustheit gegenüber Messfehlern und fehlenden oder zusätzlichen Targets wird anhand zahlreicher automatisierter und zufallsbasierter Tests bestätigt. Nach einer theoretischen Untersuchung wird eine mögliche Implementierung vorgestellt. Zusätzlich enthält diese Arbeit ein Kapitel zur automatischen Suche nach markanten Punkten im Raum, was als Vorstufe zur Korrespondenzfindung sehr nützlich ist, um z.B. Targets automatisch zu finden.

Methods for the automatic registration of 3D laser scanner data are often based on the recognition of specific objects in space, like targets. Typically, the type of the object is thereby identified, but not the individual. This step is done by the search for correspondences, where geometric constellations are recognized and used for the individual identification.

In this thesis, a method is introduced, which realizes such an automatic search for correspondences. Both the algorithm itself and parts of its analysis are based on a combination of existing graph matching algorithms and concepts of information retrieval.

Furthermore, it considers variable errors in translation and rotation of scan data and is efficient, with an assumed number r of targets of one scan, the time effort is only O(r²log(r)), the space effort O(r²). The high speed and the robustness due to errors in measurement and missing or spare targets is being confirmed by numerous automatic and random based tests. After a theoretic investigation, a possible implementation is presented. Additionally, this thesis contains a chapter about the automatic search of interesting points in space, which is useful as a pre-stage for the search for correspondences, e.g. to find targets automatically.