Bewegungsmessung und Positionserkennung mit "Sharp-Rada

[sep]

Zunächst eine kurze Einführung:
Ich habe einen SHARP - Sensor der mir Entferungen ab 15 cm bis etwa 80 cm auf 1 cm genau und bis 180 cm auf ca. 3 cm genau mißt. Möglicherweise lässt sich die Genauigkeit steigern. Ist das Hindernis weiter als 180 cm entfernt, erkennt der Sensor dies als "zu weit".

Der Sensor ist auf einen Schrittmotor montiert der 200 Schritte à 1,8° ausführen kann. Noch habe ich keine Nullpositionserkennung eingebaut, aber die kommt noch. (Magnet + Reed-Schalter)

Nun kann ich also den Sensor irgendwohin stellen und einen Rundumscan machen.
Dann trage ich ihn eine kleine Strecke weiter und drehe ihn ein wenig und mache noch einen Scan.
Das soll, wie leicht zu erraten ist, die Bewegung eines Roboters simulieren.

Nun will ich aus den beiden Scans die Bewegungsrichtung und die Drehung um die Hochachse errechnen. Dabei dachte ich an eine Art Korrelationsrechnung der beiden Datensätze.

Ich habe dazu folgende Arbeit gefunden: http://www.medialab.ch/archiv/pdf_st...navigation.pdf
Nun ist meine Frage an euch: Hat sich bereits einer von euch darüber Gedanken gemacht, wie soetwas zu realisieren ist?

In ferner Zukunft kommt zu diesem Problem noch dazu, dass nicht nur die momentane Bewegung ermittelt werden soll sondern auch die Absolutposition in einer Karte, die durch wiederholtes Messen gelernt werden soll. Aber zunächst wäre ich schon zufrieden, wenn ich überhaupt meine Bewegung ermitteln könnte.

Hallo

Hab mir da auch schon ein paar Gedanken darueber gemacht (wer wohl nicht

Hier ist ne alternative Loesung:
http://rossum.sourceforge.net/papers/Localization/

Fuer die Rotation waere ein "Angle Histogramm" ev. etwas, damit lassen sich v.a. Waende, etc finden. Vergleicht man dann zwei Scans, die in etwa der gleichen Umgebung gemacht wurden, so kann man die Rotation berechnen. Gibt noch ne weitergehende Methode, die damit dann auch die x, und y Translationen findet. Finde das Paper jetzt gerade nicht mehr...ev. mal googeln.

Je nach Umgebung kann man auch irgendwelche Objekte ("landmarks") suchen, hier waeren das wohl Ecken, und in einem zweiten Scan versuchen, dieselbe Ecke wieder zu finden => Positionsdifferenz

Kennst Du Where am I? von J. Borenstein? Da hats x solche Algorithmen drin
http://www-personal.umich.edu/~johan...d/pos96rep.pdf

Welchen Sharp verwendest Du, den 20-150cm Typ?
(Hab meinen gestern gekillt (=verpolt); mal schauen, wie schnell micromaus liefert...)

mfg
Fritzli

[sep]

Hier ist ne alternative Loesung:
http://rossum.sourceforge.net/papers/Localization/

Was ist daran alternativ?
Das ist doch genau das was ich machen (möchte).

Ich habe mir gestern mal meine Mathe-sachen aus dem letzten Semester angeschaut und ein bisschen mit VB simuliert.

Wenn man ein Feld a mit Zahlen hat (Entfernungs-Werte eines Rundumscans)
Und ein weiteres Feld b, dass ebenfalls soclhe Werte beinhaltet, jedoch um einen konstanten drehwinkel versetzt (Sensor wurde zwischen den Scans gedreht)

Ausserdem sind die Zahlen stark "verrauscht"

Und nun berechnet man die summen:

For j = 1 to anz
For i = 1 to anz
          nj=i+j
          if (nj > anz) nj -= nj
          s(j)+=a(i)*b(nj)
Next i
Next j

Zum Schluß sucht man das Maximum der Werte in s(j), und damit hat man auch den Drehwinkel (nämlich j)

cool was?
Leider sind recht viele Multiply-Accumulate-Operationen nötig

Fuer die Rotation waere ein "Angle Histogramm" ev. etwas, damit lassen sich v.a. Waende, etc finden. Vergleicht man dann zwei Scans, die in etwa der gleichen Umgebung gemacht wurden, so kann man die Rotation berechnen. Gibt noch ne weitergehende Methode, die damit dann auch die x, und y Translationen findet. Finde das Paper jetzt gerade nicht mehr...ev. mal googeln.

genauso wie ich oben beschrieben hab... Juhu...
Man muss nur die x-y-Verschiebung auf das b-Feld anwenden... dazu braucht man jeweils noch eine For-Schleife, und s wird 3-dimensional

Je nach Umgebung kann man auch irgendwelche Objekte ("landmarks") suchen, hier waeren das wohl Ecken, und in einem zweiten Scan versuchen, dieselbe Ecke wieder zu finden => Positionsdifferenz

zu ungenau, da Landmarken nur schlecht erkannt werden können, die Korrelation berücksichtigt darüberhinaus _alle_ sichtbaren Punkte und kann daher auch recht viel Rauschen wegstecken

Kennst Du Where am I? von J. Borenstein? Da hats x solche Algorithmen drin
http://www-personal.umich.edu/~johan...d/pos96rep.pdf

habs noch nicht durchgelesen, das war mir einfach zu lange

Welchen Sharp verwendest Du, den 20-150cm Typ?
(Hab meinen gestern gekillt (=verpolt); mal schauen, wie schnell micromaus liefert...)

Genau den...

[Fritzli]

Hallo

Was ist daran alternativ?
Das ist doch genau das was ich machen (möchte).

Ich muss zugeben, dass ich den von Dir angegebenen Artikel nur sehr schnell überflogen habe...

genauso wie ich oben beschrieben hab... Juhu...

Äehm, nein.
Schau Dir das Winkel-Histogramm mal genauer an, dass ist KEINE Korrelation mit irgendwas.

Man muss nur die x-y-Verschiebung auf das b-Feld anwenden... dazu braucht man jeweils noch eine For-Schleife, und s wird 3-dimensional

Wie soll das gehen? Wenn Du Sowohl Rotation als auch Translation hast, wird das meiner Meinung nach nicht mehr funktionieren. Falls Du eines davon kennst, dann gehts.

zu ungenau, da Landmarken nur schlecht erkannt werden können

Yep, das ist das Problem bei natürlichen Landmarken, man muss sie erst finden (ähnliches Problem bei Stereo-Vision)

mfg
Fritzli

[sep]

Wie soll das gehen? Wenn Du Sowohl Rotation als auch Translation hast, wird das meiner Meinung nach nicht mehr funktionieren. Falls Du eines davon kennst, dann gehts.

Ich postuliere hier mal, ohne es geprüft zu haben. Die X/Y-Verschiebung ist halt recht einfach zu ermitteln, man braucht nur Matrix-Zeilen und-Spalten zu verschieben, zu deutsch, einfach dien index um einen offset verschieben. (Die Matrix ist eigentlich eine Art Bitmap, die den Rundumscan darstellt)
Das blöde bei der Drehung ist, dass man dazu die Matrix rotieren muss... Und zwar in kleinen schritten. Wenn du also eine 400x400 Grafik in 1,8-Grad schritten drehen willst, dauet das ewig.

Vor allem hat mein ATmega8 ja kaum soviel RAM, als dass da sowas reinpassen würde...

Schau Dir das Winkel-Histogramm mal genauer an, dass ist KEINE Korrelation mit irgendwas.

Womit du recht hast - Asche auf mein Haupt... Aber der Vorgang ist der Korrelation sehr ähnlich, allerdings möglicherweise Rechenzeitsparsamer

[sep]

Auch ein schöner Text, leider voller Rectschreibfehler
http://bordeaux.informatik.uni-breme...on-referat.pdf

[Fritzli]

Hallo

Ich postuliere hier mal, ohne es geprüft zu haben. Die X/Y-Verschiebung ist halt recht einfach zu ermitteln, man braucht nur Matrix-Zeilen und-Spalten zu verschieben, zu deutsch, einfach dien index um einen offset verschieben. (Die Matrix ist eigentlich eine Art Bitmap, die den Rundumscan darstellt)
Das blöde bei der Drehung ist, dass man dazu die Matrix rotieren muss... Und zwar in kleinen schritten. Wenn du also eine 400x400 Grafik in 1,8-Grad schritten drehen willst, dauet das ewig.

Ok, jetzt hab ich gemerkt, was Du meinst. Eine solche Korrelation von zwei Scans müsste theoretisch funktionieren, das Problem ist nur, dass Du für jeden Rotationswinkel sämtliche Translationsmöglichkeiten durchprobieren musst, um dann von allen Möglichkeiten, den besten match zu nehmen, aber da werden die benötigten Durchläufe ballistisch => es geht ewig. Durch Odometrie-Schätzung liesse sich das allerdings etwas beschleunigen.

Wenn ich dann sowas mal implementiere, werde ich den Ansatz des Rossum-Projekts (mein link) nehmen: Eine Matrix-Karte und dann jeweils die Vektoren eintragen. Die Zelle auf der am meisten Vektoren enden ist dann die ungefähre aktuelle Position.

http://bordeaux.informatik.uni-breme...on-referat.pdf

Seite 14 haben wir ja genau, was ich ganz oben gemeint habe. Taugt aber nur für relative Positionsmessungen zwischen einzelnen Scans.

Vor allem hat mein ATmega8 ja kaum soviel RAM, als dass da sowas reinpassen würde...

Das wär dann ein Job für diese Mini-ATX, gumstix oder eben dann per Funk auf einen ausgewachsenen PC, aber das wär dann eben nicht mehr autonom...

Gruess
Fritzli

[sep]

Wääh ich komm nicht vorran. Ich wollte mir Testdaten erzeugen um die Algorithmen testen zu können.
Die Rotation aller Punkte um einen konstanten Winkel ist ja sehr einfach, da die Messwerte einfach "ringsum" in einem Array stehen - man muss dieses Array nur rotieren.
Jedoch in diesen Kreis-Koordinaten eine ordentliche X- oder Y-Verschiebung hinzubekommen ist fast unmöglich. Im Prinzip wärs ja einfach, aber in der Realität scheitert es bei mir an Rundunksproblematiken...

[Fritzli]

Hallo

Wie rechnest Du denn genau? Double sollte eigentlich für sowas mehr als genug Genauigkeit haben.

Gruess
Fritzli

[sep]

Nein das Problem war, dass ich zunächst ja einfach 200 Messwerte habe - Entfernungen die alle 1,8° gemessen wurden.

Also hat man sozusagen 200 Vektoren in Kreiskoordinaten

Das genaugenommen zweimal, also 2x 200 Werte.

Wenn nun die zweiten Werte gegenüber den ersten Verdreht sein sollen, ist das sehr leicht - man "shiftet" einfach das eine Feld gegenüber dem anderen.

Will man aber eine X- oder Y-Verschiebung zieht das eine heftige Rechnerei nach sich, denn zunächst müssen die Werte in karthesische Koordinaten gewandelt werden, dann um ein dX und dY verschoben und nun, und das ist das Problem, in Kreiskoordinaten zurückgewandelt werden - jedoch dürfen die Vektoren nur in 1,8°-Schritten stehen...
Da aber durch die X-/Y-Verschiebung die ursprünglichen Vektoren nicht mehr passen, gibt es üble Rundgsfehler.

Beispiel:
Stell dir vor, du hast eine analoge Armbanduhr.
Du nimmst 12 Vektoren, die vom Mittelpunkt auf die Zahlen zeigen.
Vektor 0 auf 12 Uhr, Vektor 1 auf 1 Uhr etc...

Wenn du nun die Vektoren drehen willst ist das sehr leicht, du "shiftest" sie einfach: Aus Vektor 12 := Vektor 11, aus Vektor 11 := Vektor 10 ...

Wenn du aber die Uhr unter den Vektoren weg, ein Stück zur Seite bewegst, den Vektoren-Mittelpunkt also konstant hälst, so zeigen nun nur noch ein paar Vektoren auf Punkte auf der Uhr - denn die Winkelteilung zwischen den Vektoren ist fix, nur die Vektor-Länge ist variabel.