Segmentierung von bekannten Koordinaten

Hallo liebes Forum,

im Rahmen einer Studienarbeit soll ich folgende Aufgabenstellung lösen:

Mit Hilfe einer Kamera (71fps) lese ich Koordinaten eines Leuchtmittels ein. Dieses Leuchtmittel hat ein Mensch (oder zu Beginn ein Roboter, auf Grund der Genauigkeit) in der Hand und macht eine willkürliche Bewegung damit. Ich erhalte also zu jedem Abtastzeitpunkt ein Koordinatenpaar. Nachdem die Bewegung zu Ende ist, habe ich ein Array, das alle Koordinatenwerte beinhaltet.

Das Ziel ist, die Koordinaten durch Approximation in Segmente von Geraden und Kreisen zu definieren (ähnlich tracing).

Allerdings ist das Problem die völlige Wilkür der vorgemachten Bahnkurve (kein Mensch kann ohne weitere Hilfsmittel Kreise oder Geraden zeichnen)..

Ich erwarte keine Lösung des Problems von euch, allerdings sehe ich in diesem Forum eine Gruppe von Leuten, die sich zahlreich mit Algorithmik auseinandergesetzt hat. Vielleicht kommt einer auf eine Idee an die ich noch nicht gedacht habe.

Besten Dank im voraus!

Anzeige

Also,

2-dimensional würde ich die Kruven über Änderungen der Steigung approximieren (da Du aufeinander folgende Koordinatenpunkte kennst ist das ja kein Problem die Steigungen zu erhalten).
Dann musst du halt unterschiedliche Änderungen unterschiedlichen Funktionen (näherungsweise) zuordenen:

keine Steigungsänderung -> Gerade
trigonometrische Steigungsänderungen (z.b. Sinusverlauf) -> Kreislinie

Einfach ist es nicht, aber könnte klappen.
Noch schwieriger ist es die Berechungen in den Raum zu bringen...

Danke für die schnelle Hilfe!

Daran hatte ich auch schon gedacht. Allerdings gibt es dabei ein Problem- in der Theorie funktioniert das mit der erten und zweiten Ableitung hervorragend. Da ich die Positionen mit einer Kamera einlese, kommt es zu einer Art Treppenfunktion und leider nicht zu einem glatten Graphen. Darüber hinaus ist es äußerst schwierig einen in etwa trigonometrischen Verlauf von einem "etwas mehr" trigonometrischen Verlauf zu unterscheiden.

Was ich damit meine:

Stellen Sie sich vor, der Bahnverlauf ist z.B.(!) in etwa eine Zusammensetzung einer Auf- und Entladekurve eines Kondensators. Mit dem Auge lässt sich schnell erfassen, wo Ecken, Geraden und Kreisbögen für eine Approximation zu liegen haben.

Nun stellt sich die Frage- wie kann ich sozusagen ein "Wissen" implementieren, um die geeigneten Stellen und geometrischen Körper zu finden?

Jedoch trotzdem danke für die schnelle Idee!

Hallo Bommes,

nur mal meine ersten Gedanken zu der Aufgabe.

Doch zunächst gilt es eine Grenze zu definieren:
Geraden sind auch nur Kreise, mit unendlichem Radius. D.h. es kann ruhig erst einmal alles mit einer Kreisformel approximiert werden. Wenn der Radius ein Limit übersteigt, dann wird nicht ein Kreis angenommen, sondern eine Gerade. Das macht die Sache unkomplizierter.

Und nun die Kreis-abschnitte:
vielleicht könnte das iterativ geschehen. Ausgehend von den ersten 3 Punkten wird eine Kreisbahn approximiert. Schlägt das komplett fehl, dann werden Geraden angenommen. Wenn aber eine Kreisbahn gefunden werden kann, dann wird versucht einen weiteren Punkt hinzuzunehmen, also mit 4 Punkten eine Kreisbahn zu approximieren; usw. bis der weitere Punkt nicht mehr ins Schema passt. Bis dahin ist dann das Segment.
Im nächsten Segment beginnt das Spiel von vorne...
Es wird also auf Basis von definierten Aproximeriungs-Grenzwerten versucht, die Segmente mit maximal vielen Punkten zu bestimmen. So wenig Segmente wie möglich, so viele wie nötig sind, um die Bahn annähernd zu beschreiben.

Das Ergebnis sind dann Parametersätze für die Segmente.

btw.: Interessante Aufgabe.
Grüße und halte uns bitte auf dem Laufenden

Verstehe ich es richtig, dass die Bewegung einfach so schnell ist, dass ich nicht genügend Stützstellen in der Abtastung habe und dadurch eine "eckige Kurve" erhalte?

Wenn ja, dann muss wohl eine Interpolation her und ohne "das Rad neuzuerfinden" nimmt man entweder die "trigonometrische Interpolation" oder die Interpolation über höhergradige Polynome.

Denn so wie ich das sehe muss Dein Programm Informationen über fehlende Abtastpunkte erhalten und da werden wir den Herrn Fourier wohl kaum übertreffen können

Hey!

@Erik: ja so in etwa hatte ich mir das vorgestellt, die Lösung muss iterativ erfolgen. Leider kann ich nicht davon ausgehen, dass wirklich alle Positionen, die ich aufnehme wirklich genau dort sind, wo sie in echt "wären" (Abweichung durch Rauschen, statistische Fehler etc.). Aber prinzipiell ist das ein guter Ansatz (Gerade = Kreis). Jedoch werde ich auf Grund von mangelnden Kenntnissen bezüglich oben genannter, nicht vermeidbarer Abweichungen zunächst erst einmal die gute alte Fehlerquadratmethode anstrengen müssen, um ein paar Testreihen durchzuführen und so ein Gefühl für diese zu entwickeln. (Das Thema fand ich auch interessant, ich hatte es selbst vorgeschlagen- jedoch weiß ich nicht ob ich mir damit nicht etwas ins eigene Fleisch geschnitten habe..)

@gentos: Die Auflösung meiner Kamera ist zu gering, als dass ich einen kontinuierlichen Verlauf erhalten könnte. Ich hatte auch bereits in Erwägung gezogen, die Koordinaten vorher zu interpolieren, um eine nicht-diskrete Funktion zu erlangen. Jedoch bedeutet dies einen ziemlichen Aufwand, da ich die eben erwähnten "Ausreisser" unbedingt vorher entfernen muss, sonst bekomm ich ganz großen Ärger von der Fehlerfortpflanzungsbehörde . Dazu kommt noch, dass ich mir nicht sicher bin, ob mir ein kontinuierlicher Verlaufsgraf wirklich weiterhilft..

Ich danke Ihnen bereits jetzt für die Ideen! Bis jetzt waren wirklich nur sehr gute Vorschläge dabei, Danke sehr

In 2D hört sich das nach Spline-Interpolation an (fertige VIs in LabVIEW vorhanden). , ob es das auch in sinnvoller Form in 3D gibt.

Gruß, Jens

Siehst Du eventuell die Möglichkeit ein Paar Messreihen als LabVIEW Arrays hochzuladen?

Ja das kann ich gerne mal machen, wenn ich diese aufgenommen habe. Aber das kann noch ein bisschen dauern, vielleicht schaffe ich es erst im neuen Jahr. Ich hoffe das ist nicht weiter schlimm

Bis dann