3D Kurvenrekonstruktion aus Punktwolke

[Turing]

geg.: eine Menge von Punkten im dreidimensionalen Raum (Punktwolke)
ges.: eine Kurve, die möglichst durch viele Punkte geht (räumlicher Curve-fit)

Ich wäre für jede konkrete Idee sehr dankbar.

[Gast]

Wie definierst du denn Kurve? Ich kenn nur die Definition, dass eine Kurve eine Abbildung $\mathbb{R} \to \mathbb{R}^n$ also in deinem Fall eine Abbildung von $\mathbb{R} \to \mathbb{R}^3$ ist.

Für den Fall kannst du ja jede Komponente einzeln behandeln und die Punkte der Reihe nach linear verbinden.

[nevermore]

Im zweidimensionalen Raum macht man das ja mit Regressiongeraden/kurven.

Das geht doch bestimmt auch im 3d-Raum.
http://de.wikipedia.org/wiki/Regressionsgerade

[Turing]

@ProgChild:

Das Modell der Kurve ist ein Polynom dritten Grades in jeder Koordinatenrichtung. Zum zweiten Punkt stellt sich die Frage, in welcher Reihenfolge sollen die Punkte linear verbunden werden? Ich dachte eventuell daran immer denjenigen auszuwählen, der den minimalen euklidischen Abstand aufweist und noch nicht berücksichtigt ist. Einfaches lineares Verbinden geht leider nicht, da die Punkte nur Schätzungen sind und auch in der Nähe der Kurve liegen können. Ziel ist irgendwie eine Kurve zu erzeugen, die beispielsweise den mittleren quadratischen Abstand zu der Punktwolke minimiert. Ein einfaches Polynomfitting ist auch nicht unbedingt geeignet, da es zu Über- und Unterschwingern kommt. Vor allem gegen was soll ich das Fitting durchführen? Ich kenne ja in jeder Koordinatenrichtung lediglich den Koordinatenwert.

Mich würde interessieren, ob ich unter der Voraussetzung eine bestimmte Anzahl von Kurvenpunkten zu kennen daraus eindeutig eine Kurve konstruieren kann?

@nervermore:

Zweidimensional ist kein Problem, solange deine Kurve eine Funktion ist. In den meisten Fällen ist sie das allerdings nicht. Beispielsweise kommt ziemlicher murks raus, wenn du versucht eine Kreis (Kurve) durch ein Polynom zu fitten. Mach ich es für jede Koordinatenrichtung einzeln, stellt sich wieder die Frage gegen was soll ich überhaupt fitten? In 2D kann ich x gegen y fitten aber im Raum? x gegen y und y gegen z und z nochmal gegen x? Dann ist meine Kurve aber keine Kurve mehr, da ich (x,y,z) auf C(x,y,z) abbildet, also R^3 auf R^3

Zu guter letzt gibt es ja auch noch die Möglichkeit nichtlineare Ausgleichsrechnung zu betreiben. Aber fehlt mir ein Ansatz für die nichtlineare, zu minimierende Funktion.

[Daniel E.]

Turing schrieb:

Das Modell der Kurve ist ein Polynom dritten Grades in jeder Koordinatenrichtung.

Also eine (Ober-)Fläche, keine "Kurve" (unter Kurven verstehe ich Linien)?

Sagen wir mal, Du willst die Punktwolke an eine Funktion f(x,y):->z anpassen, die von ein paar Parametern abhängt. Dann ist das Minimierungsproblem doch ratzfatz hingeschrieben.

[Turing]

Es ist eine Kurve

Bsp.:

$C(t) = (t^3 + t^2 + 1, t^3 + t + 2, t^3 + t^2)^T$

Das Polynom dritten Grades hängt weder von x noch von y noch von z ab, sondern von einem Parameter t.

Der Ansatz für die nicht lineare Minimierung wäre:

$x\_i = a\_x t\_i^3 + b\_x t\_i^2 + c\_x t\_i + d\_x$
$y\_i = a\_y t\_i^3 + b\_y t\_i^2 + c\_y t\_i + d\_y$
$z\_i = a\_z t\_i^3 + b\_z t\_i^2 + c\_z t\_i + d\_z$

Der Umstand, dass ich die t_i zu einem vorgegebenen x_i,y_i und z_i nicht kenne, macht das ganze problematisch.

[optimierer]

ich würde das anders machen. dein polynom ist durch drei punkte eindeutig beschrieben. also würde mein ansatz so aussehen, dass ich diese drei punkte möglichst günstig wähle. z.b mit einem standardoptimierungsverfahren und neun unbekannten parametern.

vielleicht kann man da auch noch was vereinfachen ... z.b wenn man die entfernung der punkte auf 1 festlegt dürften nur noch acht parameter übrig bleiben ..

[Bitte ein Bit]

So wie ich das Ganze jetzt verstehe, hast du Turing ein generelles Verständnisproblem zum Thema Interpolation / Approximation von Kurvenpunkten.

Generell gilt, dass wenn man N+1 Punkte interpolieren möchte, man ein Polygon vom Grad N braucht. Alternativ kann man auch die N+1 Punkte durch mehrere Polygone interpolieren. Das Ganze nennt sich Spline-Interpolation. Ist der Grad des Polygons ungleich der Anzahl von Punkten plus eins ist, spricht man von Approximation.

Um nun generell ein solches Problem zu lösen, stellt man meistens ein LGS auf. Im Endeffekt hast du das schon mit deinen explizit hingeschriebenen Gleichungen getan. Du must das Ganze nur noch für jede Dimension in die Form Ax=b bringen, und bekommst danach 3 LGS. Auch hier zeigt sich der Unterschied zwischen dem Approximationsproblem und dem Interpolationsproblem. Ist das LGS über/unterbestimmt, ist das Ganze ein Approximationsproblem welches beispielsweise mittels der Pseudoinversen von A gelöst werden. Ist das LGS eindeutig lösbar, ist das Ganze ein Interpolationsproblem.

Die Wahl der ti's nennt sich übrigens Parametrisierung und kann äquidistant (ti = i), chordal (ich glaube ti = ||pi - pi+1|| / (Summe(||pi - pi+1||) oder zentripetal erfolgen. Die Parametrisierung ist entscheidend für das Aussehen der Kurve.

Detailliert kann man das Ganze auch in dem Buch "Grundlagen der Geometrischen Datenverarbeitung" nachlesen.

[Turing]

@Bitte ein Bit

Tut mir leid, ich benötige keine Einführung in Interpolation oder Ausgleichsprobleme. Ich denke, dass ich mit der Thematik vertraut bin. Vielmehr vermute ich, dass einige die geschilderte Problematik nicht verstehen und nur das runterbeten, was sie in Vorlesungen darüber gehört haben.

Wie du selbst bemerkt hast, ist die Parametrisierung von Bedeutung und genau hierin liegt das Problem. Ich kenne die Parametrisierung nicht, ich kenne nur die Koordinaten der Punktwolke. Weder die Reihenfolge, in der sie angeordnet werden müssen, um beispielsweise durch äquidistante t_i interpoliert zu werden, noch die tatsächlichen t_i's. Ich kann auch keine Punkte besonders günstig legen oder wählen, weil ich nur eine Punktwolke, eine ungeordnete Menge von Punkten, habe. Glücklicherweise konnte ich das Problem mittlerweile einigermaßen lösen.

[Jester]

Turing schrieb:

Wie du selbst bemerkt hast, ist die Parametrisierung von Bedeutung und genau hierin liegt das Problem. Ich kenne die Parametrisierung nicht, ich kenne nur die Koordinaten der Punktwolke. Weder die Reihenfolge, in der sie angeordnet werden müssen, um beispielsweise durch äquidistante t_i interpoliert zu werden, noch die tatsächlichen t_i's. Ich kann auch keine Punkte besonders günstig legen oder wählen, weil ich nur eine Punktwolke, eine ungeordnete Menge von Punkten, habe.

Wenn Du keinerlei Informationen hast, dann sollte eigentlich jede beliebige Kurve gleich gut sein. Da Du aber anscheinend doch eine gewisse Vorstellung davon hast, was gut ist und was nicht mußt Du eben versuchen diese Vorstellung zu formalisieren...

[Bitte ein Bit]

An Turing:

Wenn ich also das jetzt richtig verstehe, ist dein Problem nur dass du keine Ordnung (zeitlich oder anders) auf deinen Eingabepunkten hast. Dein Problem ist also kein Interpolations/Approximationsproblem sondern einfach ein Trajektorien-Problem. Du willst einen Weg mit N Zwischen-Stationen finden, so dass er "schön" aussieht.

Denn sobald eine Ordnung (Trajektorie) auf den Eingabepunkten festgelegt wurde, kann man ohne Probleme die Parametrisierung (chordal mit Nielson Metrik kann ich empfehlen) berechnen und danach die interpolierende Kurve (am besten eine B-Spline) und täterätä habe ich meine Kurve.

Dann gehe doch einfach hin, nimm dir Exel oder besser Gnuplot und schaue dir doch mal deine Daten in 3D an und lege die Ordnung per Hand fest. Falls du es mathematisch liebst, kann du doch auch irgenteine Norm verwenden, in dem du beispielsweise sagst, dass zwei Punkte (A benachbart sind, wenn es keinen weiteren Punkt C aus der Punktwolke gibt, welche näher an dem Punkt A liegt.

[Turing]

@Bitte ein Bit:

Gratuliere, Du hast die Problematik verstanden. Die Punkte von Hand zu sortieren ist allerdings nicht realisierbar.
Prinzipiell mache ich es aber ähnlich. Ich davon aus, dass ich den 'Anfang' und das 'Ende' der Punktwolke gegeben habe und suche dann immer denjenigen, nicht berücksichtigten Punkt, der den geringsten Abstand von dem Punkt hat, der zuletzt in die 'geordnete' Punktwolke aufgenommen wurde. Da die Punktwolke jedoch 'verrauscht' ist und die Punkte nicht äquidistant voneinander entfernt liegen, können auch hierbei ein paar häßliche Effekte auftreten. Anschließend lege ich ein Polynom mit äquidistanten t_i's durch die sortierten Punkte. Klappt ganz gut, aber nicht perfekt...