2D-Transformation bestimmen
-
hallo,
ich weiss nicht ob mein problem einfach zu lösen ist, deshalb frage ich hier mal
gegeben :
A eine Menge von Punkten im 2D-Raum
B eine Menge von Punkten im 2D-Raumgesucht :
diejenige lineare Transformation
(am besten nur translationen und rotationen)
welche A "am besten" in B überführt.Gibt es dafür einen Ansatz?
Wäre über jede Hilfe dankbar.Das ist kein Hausaufgabe, sondern ein reales Problem, und ich weiss eben nicht
wo ich anfangen soll. Weil eine exakte Lösung wird es ja im allgemeinen
nicht geben.
-
Schau mal nach der least squares method bzw. Methode der kleinsten Quadrate.
-
die methode der kleinsten Quadrate kannst du aber nur sinnvoll anwenden, wenn du weißt, welcher Originalpunkt welchem Bildounkt entsprcith und andersrum, und wenn es keine neuen bildpunkte gibt oder welche verloren gingen.
Ein weiteres Anwendungsfeld bieten sogenannte Point-Matching-Algorithmen. Danach musste mal suchen. Wobei solche dann schon eher auf den Brute-force-Ansatz abzielen (d.h. alles probieren und was am besten passt ist dann das beste)
-
Ja, wenn die Zuordnung nicht bekannt ist, dann ist es eher ein shape-matching-Problem. Vielleicht lässt sichda was benutzen. Ein Ansatz mit theoretischem Unterbau, der mehr als Brute-Force ist, ist etwa der hier: http://delaunay.tem.uoc.gr/~mkaravel/ewcg06/papers/26.pdf die Autoren haben auch noch mehr in die richtung gemacht.
-
Schau Dir mal diesen Thread 'Rotation und Verschiebung von Koordinaten ermitteln' an. Insbesondere den letzten Beitrag im Thread, der von mir ist.
Leider hat der Latex-Prozessor damals nicht funktioniert, aber wenn Du auf 'zitieren' gehst, ist der Latex-Source-Code sichtbar.Gruß
Werner
-
vielleicht kannst du das beheben, indem du den beitrag editierst?
-
Jester schrieb:
vielleicht kannst du das beheben, indem du den beitrag editierst?
.. funktioniert nicht
-
Alle Lsq Lösungen haben den gleichen Schwerpunkt, bleibt also nur die Rotation zu finden. Da sollte man versuchen mit der konvexen Hülle zu arbeiten, das sind dann weniger Punkte. Danach eine Patternsuche auf die Längen der Schwerpunktvektoren der Hüllenpunkte.
Da die konvexe Hülle Sortieren braucht wird der gesamt Algorithmus O(n log n), Der Schwerpunkt ist nur O(n) und das Hüllenpunkte überprüfen O(n-Hüllenpunkte)~O(n)
Edit: das Testen der Hüllenpunkte geht, glaub ich, nicht in O(n)