Forum: Mikrocontroller und Digitale Elektronik Kreis in GPS-Koordinaten erkennen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Peter M. (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von F. (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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?!

von Der Andere (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Vieleicht erst mal prüfen ob sich der Weg berührt oder überkreuzt.
Dann kann man den Weg zwischen den beiden Punkten weiter analysieren.

von Ulrich (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Warum scheint dir die Hough - Transformation ungeeignet vor? Das wäre 
meiner Meinung nach das Mittel der Wahl.

von Sigi (Gast)


Bewertung
1 lesenswert
nicht lesenswert
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.

von asdfasd (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Auf irgendeinem Kreis befindet man sich immer. Was man machen kann: drei 
Punkte auswählen, als Dreieck betrachten, den Umkreis/~-radius 
berechnen, filtern.

von THOR (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Conny G. (conny_g)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Conny G. (conny_g)


Bewertung
1 lesenswert
nicht lesenswert
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?

von Rene K. (xdraconix)


Bewertung
0 lesenswert
nicht lesenswert
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

von Sigi (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.).

von Kpt. Nemo (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von c-hater (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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...

von Daniel F. (df311)


Bewertung
0 lesenswert
nicht lesenswert
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...

von Possetitjel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Jacko (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
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.

von Patrick J. (ho-bit-hun-ter)


Bewertung
0 lesenswert
nicht lesenswert
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

von Possetitjel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Jacko (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
@  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!

von Horst (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Wolfgang (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Horst (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Wolfgang (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Jacko (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
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!

von Neuling (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Forist (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von c-hater (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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...

von Georg (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Wolfgang (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.