Diese Seite ist extra salopp geschrieben, um euch einen schnellen praktischen Einstieg in das Thema zu ermöglichen - wer mathematische Unkorrektheiten findet, darf sie gern in die Kommentare posten.
Ziel Wir haben mehrere 3D Modelle aus verschiedenen Quellen, zum Beispiel ein CAD Modell (Q1) und einen 3D Scan(Q2). Nun wollen wir die Datensätze zueinander so positionieren, dass sie “aufeinander liegen” aka wir berechnen die Transformation von Q2 zu Q1 (Gemeint: Q1 ist die Basis oder im Scene Graph der Parent) und invertieren diese dann, um Q2 gleich orientiert, transformiert und (wenn nötig) skaliert anzuzeigen.
Stolpersteine
Skalierungen verkomplizieren das Ganze ordentlich und sollten, wenn möglich behoben werden, bevor mit der Transformiererei begonnen wird - sie erscheinen häufig, wenn bei einem Modell die transformation in mm und beim anderen in m angegeben ist - bei Gebäudemodellen kann zusätzlich ein Maßstab (z.B. 50.000:1) mit angewandt sein. Achtung 2: Computer Vision und Computer Grafik Leute haben sich nie so ganz einigen können, ob sie rechtshändig oder linkshändig arbeiten wollen: Deshalb ist das zweite, was ihr beachten solltet, ob alle verwendeten Softwarepakete und Libraries die selbe Händigkeit verwenden (z.B. bei OpenCV und Unity ist das nicht der Fall!). Um probleme mit der Händigkeit zu lösen siehe https://towardsdatascience.com/change-of-basis-3909ef4bed43
Aber erst einmal zurück zum Thema, gehen wir von zwei Modellen mit der gleichen Händigkeit und der gleichen Skalierung, aus brauchen wir ein globales und ein lokales Registrierungsverfahren. Warum das? Naja, die lokalen Verfahren sind gut darin, kleine Abweichungen zu korrigieren und das Modell quasi “zurecht zu ruckeln”, sie neigen jedoch dazu, in lokale Minima hineinzulaufen und brauchen deshalb vorher eine grobe Vorregistrierung.
Für diese globale Vorregistrierung gibt es zwei Möglichkeiten: Manuell und Automatisch. Automatisch ist ein offenes Forschungsfeld mit zig Papern (cf. Masterarbeit von Regina Hof) - der “klassische Ansatz” ist das Random Sample Consensus Verfahren, das im Prinzip folgendes tut: nachdem beide Modelle in Punktwolken umgewandelt wurden, werden für die Punkte Features berechnet, sodass sie sich zwischen den Modellen zuordnen lassen. Dann wird für eine feste Untermenge an Punkten die Transformation bestimmt (mit Absolute Orientation verfahren, dazu komme ich gleich) und anschließend geschaut, wie viel % der Punkte mit der Transformation einverstanden sind (deshalb Consensus). Sind das eine gewisse Anzahl von Punkten, z.B. 90%, werden die Anderen als Outlier klassifiziert und dürfen in den nächsten Iterationen nicht mehr mitspielen.
Alternativ können wir dem Algorithmus auch auf die Sprünge helfen und per Point Picking ein paar Punkte vorgeben, die wir in beiden Modellen wiederfinden können (z.B. Zimmer Ecken) das ist zwar durch den Faktor Mensch ungenauer und bedarf user-input, aber im Gegensatz zu RANSAC kann es nicht aufgrund ungünstiger Threshholds schiefgehen (ist also robuster). Hier ist der Ansatz, wir suchen uns mindestens 3 Punkte, die in beiden Datensätzen gut zu sehen sind und berechnen anschließend per Absolut Orientation eine erste Transformation.
Je nach Use Case kann das schon genau genug sein und wir können direkt diese Transformation verwenden, ansonsten können wir die Pose nun mit einem lokalen Registrieralgorithmus verbessern. Der klassische Ansatz hier heißt ICP (Iterative Closest Point). Hierbei wird iterativ die Energiefunktion der Distanzen der Punktwolken zu einander minimiert. Keine Lust auf Optimierungsmathematik weil… ist ja ein Praktikum und ihr wollt eigentlich eine Anwendung bauen? Kein Ding es gibt eine Reihe fertiger Implementierungen.
Zunächst hätten wir da CloudCompare: Eine unglaublich hilfreiche Freeware Software mit GUI, in der ihr sowohl ein Point Picking als auch einen ICP bereits implementiert und fertig zur Nutzung findet. Ein Video für das Verfahren findet ihr hier:
(und wie ihr die homogene Matrix in Unity reinbekommt, findet ihr selber raus
).
Alternativ, wenn ihr gern eine Script Lösung bauen wollt, kann ich euch Open3D empfehlen, eine Python-Library, in der sowohl ICP (http://www.open3d.org/docs/latest/tutorial/Basic/icp_registration.html) als auch RANSAC http://www.open3d.org/docs/latest/tutorial/Advanced/global_registration.html implementiert sind.
Warum nicht einfach die Modelle von Hand zurechttransformieren, bis es passt? Geht natürlich auch - aber das dauert definitiv länger als das Point Picking und ist auch noch ungenauer, was auf Gebäudeebene gerade bei Winkelfehler einen großen Einfluss hat. (Überlegt einfach mal, um wie weit ein Punkt am Ende einer 30m strecke schon bei 1° Drehung der Strecke um den Ursprung verschoben ist…)