Hallo Zusammen, ich habe GPS-Koordinaten (die zunächst mal in einen FIFO via UART kommen). Nun ist die Frage: Wie erkenne ich, ob ich mich auf einem Kreis bewege dessen Mittelpunkt und Radius (noch nicht) bekannt ist. Zielsystem ANSI C & STM32L4. (Kein bekannter Radius des Kreises - irgendwas zwischen 50m und 300m) Meine erste Idee war das GPS Signal soweit zu filtern, dass man irgendwie vernünftig eine Ableitung bilden kann und diese dann aufintergieren bis man die 2Pi voll hat. Hough Circle und RANSAC kommen mir für diese Applikation nicht unbedingt geeignet vor. Hat jemand Stichworte oder Ideen für mich? Dankeschön
Das heißt, du darfst nicht dichter als 50m an den Mittelpunkt heran, aber auch nicht weiter weg als 300m oder wie ist dies zu verstehen? Worum geht es denn genau? Das man sich kreisförmig bewegt? Darf man dann seinen Radius dabei ändern?!
Vieleicht erst mal prüfen ob sich der Weg berührt oder überkreuzt. Dann kann man den Weg zwischen den beiden Punkten weiter analysieren.
Warum scheint dir die Hough - Transformation ungeeignet vor? Das wäre meiner Meinung nach das Mittel der Wahl.
Es fehlen noch ein paar Angaben, ich nehme jetzt mal an, dass es die Punkte eines bewegten Objekts in zeitlich korrekter Reihenfolge sind. Dann kannst du die Kurve rekonstruieren und auf Bogenlänge umparametrisieren. Damit ist die erste Ableitung eine Menge von Tangenten (Länge 1!!) und die zweite Ableitung eine Menge von Vektoren, die im Krümmungsfall in Richtung Krümmungsmitte zeigen und deren Länge reziprok zum Krümmungsradius sind. Damit hast du dann fast alles zusammen, evtl. die Daten noch ein wenig "entrauschen". Sollte sich eine Kreisbewegung einstellen, dann zeigen die zweiten Ableitungen alle auf etwa einen Punkt und haben alle etwa die selbe Länge. Damit lassen sich auch Teilkreise erkennen.
Auf irgendeinem Kreis befindet man sich immer. Was man machen kann: drei Punkte auswählen, als Dreieck betrachten, den Umkreis/~-radius berechnen, filtern.
Also so ganz grundlegend: Ein Kreis lässt sich durch 3 Punkte beschreiben. In deinem Fall hast du 3 Punkte, die du vom GPS bekommst, Punkte A B und C. Von A und B annehmen dass Sie auf einer Kreisbahn liegen, Radius berechnen Gleiches für B und C. Wenn jetzt der Radius gleich lang ist und in die gleiche Richtung zeigt, liegen diese Punkte auf dem gleichen Kreis. Problem: GPS ist nicht absolut genau und tastet nicht beliebig häufig ab. Du wirst also in der Kreis-Erkennung eine Toleranz haben müssten. Die Radius-Vektoren müssen ungefähr in die gleiche Richtung zeigen und ungefähr gleich lang sein. Besser wäre die Verwendung eines Accelerometers, das spuckt auf einer Kreisbahn konstante Beschleunigung aus.
Sigi schrieb: > Sollte sich eine Kreisbewegung einstellen, dann > zeigen die zweiten Ableitungen alle auf etwa einen > Punkt und haben alle etwa die selbe Länge. Damit > lassen sich auch Teilkreise erkennen. Als Kriterium, ob man das Ergebnis als Kreis akzeptiert könnte man dann nehmen, dass die Schnittpunkte dieser Vektoren alle in einer begrenzen Zone liegen. Zu weite Streuung -> kein Kreis.
THOR schrieb: > Besser wäre die Verwendung eines Accelerometers, das spuckt auf einer > Kreisbahn konstante Beschleunigung aus. Welche Beschleunigung hat man denn dann zu Fuss auf einer Kreisbahn von 300m?
Conny G. schrieb: > THOR schrieb: >> Besser wäre die Verwendung eines Accelerometers, das spuckt auf einer >> Kreisbahn konstante Beschleunigung aus. > > Welche Beschleunigung hat man denn dann zu Fuss auf einer Kreisbahn von > 300m? Gnihihi.. also der Einwand ist gut! :-D
Conny G. schrieb: > Als Kriterium, ob man das Ergebnis als Kreis akzeptiert könnte man dann > nehmen, dass die Schnittpunkte dieser Vektoren alle in einer begrenzen > Zone liegen. Und sehr wichtig dabei ist: Man muss keine "komplexen" Schnittberechnungen vornehmen. Der Schnittpunkt ergibt sich, indem man an den Punkten die Ableitungsvektoren abträgt, jeweils skaliert mit 1/Vektorlänge. Also insgesammt sehr einfache Berechnungen, inkl. der Filteroperationen (laufender Durchschnitt etc.).
Peter M. schrieb: > Nun ist die Frage: Wie erkenne ich, ob ich mich auf einem Kreis > bewege dessen Mittelpunkt und Radius (noch nicht) bekannt ist. Indem du einen Kreis in deine Daten reinfittest und guckst, was als Mittelpunkt und was als Radius rauskommt. Wenn die Werte stabil bleiben, hält der Haken. Für einen Kreis muss bekanntlich gelten, wobei bei Verrechnung der GPS-Koordinaten die Abweitung zu berücksichtigen ist.
1 | r² = (x-x0)² + (y-y0)² |
Mit deinem Radiusbereich kannst du den Wertebereich für die Radiussuche einschränken und die Suche abbrechen, wenn der quadratische Fehler zu groß bleibt.
Peter M. schrieb: > ich habe GPS-Koordinaten (die zunächst mal in einen FIFO via UART > kommen). Wie die Daten verfügbar werden, ist für das Problem völlig irrelevant... > Nun ist die Frage: Wie erkenne ich, ob ich mich auf einem Kreis > bewege dessen Mittelpunkt und Radius (noch nicht) bekannt ist. > > Zielsystem ANSI C & STM32L4. Welche Programmiersprache verwendet wird und welcher Prozessor an den Daten rumrechnet ist für das Problem völlig irrelevant... > (Kein bekannter Radius des Kreises - irgendwas zwischen 50m und 300m) Aha, jetzt wird es das erste Mal wirklich interessant im Bezug auf das Problem. Genau diese Eingrenzung macht es nämlich überhaupt erst (zumindest potentiell) lösbar! Was jeder mit grundlegender mathematischer Bildung (auf Hochschulniveau) natürlich sofort selbst erkannt hätte... Immerhin scheint es einige Contributors in diesem Thread zu geben, die über die entsprechende Bildung verfügen, denn einige der Beiträge zielen in diese Richtung, wagen es aber irgendwie nicht, das Problem auf den Punkt zu bringen... > Meine erste Idee war das GPS Signal soweit zu filtern, dass man > irgendwie vernünftig eine Ableitung bilden kann und diese dann > aufintergieren bis man die 2Pi voll hat. Naja, die Idee geht zumindest schon ungefähr in die richtige Richtung. Das lässt zmindest hoffen, dass du tatsächlich schon selber darüber nachgedacht hast. Allerdings wohl nicht sehr intensiv... > Hat jemand Stichworte oder Ideen für mich? - FIFO für die Koordinaten - wiederholte lineare Regression zum Finden der Kreiseigenschaften bei jedem FIFO-Update. - Wegfiltern der Kreise, deren Eigenschaften (Radius) nicht auf die Vorgabe passen - Wegfiltern der Kreise, deren Radius groß im Verhaltnis zur größten Diagonale der betrachteten Koordinaten (also dem FIFO-Inhalt) ist - für den Rest (können zu jeder Zeit mehrere sein): Kreiseigenschaften und zeitlich erste Koordinate für diesen Kreis speichern und alle eingehenden Folgewerte im Fifo dagegen abgleichen. Verläßt der Kreis durch den Folgewert die Vorgabe bezüglich des Radius: auch diesen Kreis verwerfen. - für alle nicht verworfenen Kreise für jeden neuen FIFO-Wert den Abstand zum ersten Wert prüfen, der zu diesem Kreis beitrug. Nah genug? -> Kreis komplett. Das ist nur das grobe Konzept, das kann (und sollte) man sicher noch in vielerlei Hinsicht verfeinern/verbessern. Ich habe es absichtlich nicht vollständig aufgedröselt, denn ich will, dass du selber auch denken musst...
Um festzustellen, ob man sich innerhalb des Kreises muss man (den evtl auch variablen) Mittelpunkt und Radius kennen sowie den Standort kennen. Der Radius von 300m ist jetzt (in Bezug auf die Größe der Erde) nicht wirklich groß, daher würde ich den Kreis als flach annehmen. Bei einem durchschnittlichen Erdradius von ca. 6.371.001 m (https://de.wikipedia.org/wiki/Erdradius) ergibt sich eine Strecke von ca. 30,8m pro Bogensekunde in Nord-Süd Richtung, Ost-West ist stark von der geographischen Breite abhängig, kann man aber trigonometrisch recht einfach bestimmen/abschätzen. Damit dann einfach über die Differenz der Koordinaten den Abstand der Punkte berechnen. Da nur quadrieren und keine Wurzel in der Rechnung vorkommt kommt man (theoretisch) auch ohne Bibliotheken aus...
Peter M. schrieb: > ich habe GPS-Koordinaten (die zunächst mal in einen > FIFO via UART kommen). Nun ist die Frage: Wie erkenne > ich, ob ich mich auf einem Kreis bewege dessen > Mittelpunkt und Radius (noch nicht) bekannt ist. Hmm. Für meinen Geschmack sind das zwei Teilaufgaben: Approximieren aller bisher eingelaufenen Punkte durch einen Kreis; feststellen, wo Du Dich auf diesem Kreis gerade befindest (Winkel Startpunkt-Mittelpunkt-aktueller Punkt). > Meine erste Idee war das GPS Signal soweit zu filtern, > dass man irgendwie vernünftig eine Ableitung bilden > kann und diese dann aufintergieren bis man die 2Pi > voll hat. Numerisch ableiten ist Scheisse. Integrieren ist gut. > Hat jemand Stichworte oder Ideen für mich? "Lissajous-Figur". Die Paare (a*sin(p),a*cos(p)) liegen alle auf einem Kreis. Du musst nicht zwingend vektoriell geometrisch mit den Punkten herumrechnen; man kann auch x(p) und y(p) (oder auch y(x)) mit allen üblichen mathematischen Methoden approximieren. Wenn Du mit Sicherheit einen ganzen Umlauf zusammen- bekommst, müsste sogar eine FFT gehen. Der Gleichanteil liefert den Mittelpunkt, die Amplitude den Radius, und die Phasenlage definiert den Startpunkt.
Ob der Prozessor samt Ressourcen wirklich so irrelevant ist? Es kommen NMEA-Strings in die FIFO und müssen erstmal vorgehalten werden, da noch nicht bekannt ist, ab wieviel Samples die Kreisbewegung erkennbar wird. - Da fehlen Angaben vom TO zur Samplerate und Abschätzung der (min/max) Zeit für einen Orbit (und ob der Rest des NMEA-Strings auch noch benötigt wird). STM32L4: 16 KB RAM können schnell knapp werden, wenn man nicht per "intelligenter" Zwischenfilterung nach Orts- und Richtungs- änderung die FIFO-Daten (auf das Nötige reduziert) in eine Zwischen-FIFO für den Bahn-Verlauf überführt. Jeder NMEA-String hat vielleicht 64 Byte, da ist mit 1024 Samples das ganze RAM belegt. Kein Platz mehr für Zwischenspeicher des Erkennungs- algorithmus, oder gar für die Ausgabe... Beispiel mit 64 Samples: 30° Erdbewegung um die Sonne 64 x 1 Sample / Sekunde: 0,00073° 2,6 Mega-Samples für 30° 64 x 1 Sample / Stunde: 2,62839° 732 Samples für 30° 64 x 1 Sample / Tag: 63,0814° 30 Samples für 30° Ab einem Bogenabschnitt von >= 30° lässt sich vielleicht schon halbwegs sicher die Bahn als Kreisbewegung um einen Zentralpunkt errechnen. Also müssen die Daten auf die notwendigen Samples/Umlauzeit reduziert werden. Auf die reduzierten Daten der Zwischen-FIFO kann man dann Algorithmen zur Kreiserkennung ansetzen, ohne mit dem Limit von 16 KB RAM zu kollidieren.
Hi Da ein Kreis mit 3 (drei) Punkten definiert werden kann, sollten sich vier aufeinander folgende Punkte eindeutig zu einem Kreis dazugehörend erkennen lassen, oder eben nicht. Ginge auch in 3D. Welche Punkte man während dessen besser verwirft dürfte hier eher die entscheidende Frage sein, daß Einem nicht eine Fehlmessung die ganze Erkennung versaut. Wie viel Kreis muß abgegangen worden sein, um als Kreis zu gelten? Wofür war diese Erkennung jetzt gut? MfG
Patrick J. schrieb: > Da ein Kreis mit 3 (drei) Punkten definiert werden kann, > sollten sich vier aufeinander folgende Punkte eindeutig > zu einem Kreis dazugehörend erkennen lassen, oder eben > nicht. Das Problem ist stark überbestimmt. Auffassung als Interpolationsaufgabe ist unzweckmäßig. > Welche Punkte man während dessen besser verwirft dürfte > hier eher die entscheidende Frage sein, daß Einem nicht > eine Fehlmessung die ganze Erkennung versaut. Dazu wurde vom "Fürsten der Mathematiker" die Approximation im quadratischen Mittel erfunden.
@ Patrick J. (ho-bit-hun-ter) Um auf handhabbare Datenmengen für den STM32L4 zu kommen. Mein Lehrer hat früher bei solchen Rückfragen "Guten Morgen" gesagt. - Und "du hast wohl gepennt" gemeint. Nimm mal 3 Datenpunkte (mit Positions-Toleranz von 1% von r), die nur einen Kreisbogenabschnitt < 1° beschreiben. Dämmert es??? - Wenn nicht, mach besser nix Technisches!
Leider liest man hier wieder von viel zu vielen Bastelansätzen, ohne dass wirklich wissenschaftlich und logisch anzugehen. Würde man das tuen, hätte hier schon längst der Begriff der Fourier Descriptoren fallen sollen. Wer dieses simple Konzept verstanden hat, weiß auch wie er daraus zur Lösung des hier gestellten Problems kommt.
Jacko schrieb: > Jeder NMEA-String hat vielleicht 64 Byte, ... Für solche Abschätzungen nach oben würde ich die NMEA Spezifikation zu Grunde legen und die definiert eine maximale Länge von 82 Byte einschließlich Startzeichen ("$") und abschließendem <CR><LF>. Um den Speicherbedarf ggf. klein zu halten, könnte man "on-the-fly" beispielsweise den RMC-Sentence auseinander nehmen und sich Zeit, Breiten-/Längen-Minuten und evtl. Datum rauspicken.
Ein anderer Konzeptansatz wäre die Analyse der Eigenvectoren und Eigenwerte der Kovarianzmatrix, sprich PCA. Aber vermutlich ist auch das für den Großteil des Forums zu hoch, ganz zu schweigen von der Implementierung von stabiler, linearer Algebra auf einem uC.
Patrick J. schrieb: > Da ein Kreis mit 3 (drei) Punkten definiert werden kann, sollten sich > vier aufeinander folgende Punkte eindeutig zu einem Kreis dazugehörend > erkennen lassen, oder eben nicht. Das rechne mal vor und zwar mit Rauschen auf den Daten und geringem Winkelabstand der Punkte (bezogen auf den Kreismittelpunkt). Ob man mit vier aufeinanderfolgenden Punkten überhaupt schon etwas über den Kreis sagen kann, hängt sehr davon ab, wie weit auseinander die Punkte auf dem Kreisbogen liegen und wie stark verrauscht die Koordinatenpaare sind. Auch müssen die Datenpunkte zeitlich weit genug auseinander liegen, damit die Fehler statistisch unabhängig werden.
Supi! Jetzt kommt noch so ein Horst, der mal endlich die Fourier Descriptoren und die Kovarianzmatrix zur Sprache bringt. - Also PCA: womit wohl nicht die Posterior cortical atrophy gemeint ist, aber vielleicht (?) die Principal Component Analysis. (Die würde allerdings einer angepassten Datenreduktion auch nicht im Wege stehn.) Ohne solche Beiträge wäre ich schon längst im Traumland. Herrlich abgehoben, ohne z.B. die begrenzten Ressourcen auch nur eines Blickes zu würdigen... - Und dass der TO noch NULL Rückmeldung gemacht hat, fällt auch keinem auf. Wirklich amüsant hier, aber trotzdem: Gute Nacht!
um aus "nur 3 punkten" den kreis bestimmmen zu können sollte man sich doch erstmal anschauen welchen kleinen winkel drei samples hintereinander haben, oder nicht? Angenommen das GPS-Modul sendet mit 1 Hz. Dann kannst du dir erstmal den abstand der punkte ausrechnen. wenn das im kreis fliegt, geht das doch leicht über den umfang: länge des bogensegements (punktedistanz) / radius = alpha Damit könnte man erstmal abschätzen, wie viele samples man bräuchte, bis man die 30° von Jacko hat.
Ich frage mich, warum hier jemand so eine Frage in den Raum wirft und dann von der Bildfläche verschwindet. Zu klären wäre beispielsweise, ob es um eine Bewegung entlang des Kreises geht oder ob geprüft werden soll, ob sich das Objekt (weiterhin) irgendwo auf einem einmal identifizierten Kreis aufhält.
Possetitjel schrieb: > Dazu wurde vom "Fürsten der Mathematiker" die Approximation > im quadratischen Mittel erfunden. Jepp: exakt die von mir vorgeschlagene lineare Regression. Tipp für den TO: Auch die Bildverarbeiter von heute nutzen die oft und gern... Und irgendwelche NMEA-Koordinaten sind auch nix anderes als Bildverarbeitung, man muss sie nur auf eine plane Fläche mappen. Zumindest, bei dem Kreisdurchmesser, den der TO angegeben hat, ist das absolut problemlos möglich, da spielt die Krümmung der Erdoberfläche noch überhaupt keine Rolle. Vermutlich spielt nichtmal das Gelände eine nennenswerte Rolle, denn im Hochgebirge würde wohl selbst ein Vollidiot merken, wenn er im Kreis klettert, ganz ohne Softwarehilfe. D.h.: man kann die Z-Komponente komplett ignorieren...
Neuling schrieb: > Damit könnte man erstmal abschätzen, wie viele samples man bräuchte, bis > man die 30° von Jacko hat. Schön und gut, aber was sagt das denn aus? Dass ich einen Kreisbogen von 30 Grad gelaufen bin, heisst doch noch lange lange nicht, dass ich im Kreis laufe. Darüber kann man vielleicht mal bei 180 Grad nachdenken. Aber ohne den TO, der sich aus dem Staub gemacht hat, ist eh die ganze Diskussion witzlos, es sei denn er läuft da auch im Kreis und kommt irgendwann wieder hier vorbei... Georg
Georg schrieb: > Schön und gut, aber was sagt das denn aus? Dass ich einen Kreisbogen von > 30 Grad gelaufen bin, heisst doch noch lange lange nicht, dass ich im > Kreis laufe. Darüber kann man vielleicht mal bei 180 Grad nachdenken. Wenn du einen Kreisbogen von 1° gelaufen bist, kannst du wegen des Rauschens der Koordinaten nicht mal feststellen, wie groß der Kreis ist und wo sein Mittelpunkt liegt. Bei 30° stehen die Chancen deutlich besser. Und die Frage war nicht philosophischer Art, i.e. ab wieviel Grad Laufstecke man im Kreis läuft, sondern es ging um die Schätzung von Mittelpunkt und Radius des Kreises.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.