Kartenausschnitt in Karte finden

[jcrypter]

Hallo liebes Forum,

ich programmiere gerade eine Robotersimulation bei der es darum geht, in einer Simulation Ansätze für die Lösung von Problemen eines realen Roboters zu finden.
Konkret geht es um einen Roboter der sich frei bewegt und eine Karte von seiner Umgebung zeichnet.
In der Simulation fährt er einfach so lange gerade aus bis er auf eine Wand stößt, ändert dann die Richtung und fährt gerade aus bis er auf eine Wand trifft... usw.
Die Informationen an welcher Stelle er auf eine Wand getroffen ist wird in eine (anfangs leere) Karte gezeichnet.
Das Ziel dabei kann nun sein einfach eine Karte zu zeichnen und sich anhand dieser bei zukünftigen Fahrten zu orientieren, allerdings möchte ich, dass der Roboter seine gesammelten Karteninformationen mit einer bestehenden Karte vergleicht um darüber seine Position auf dieser Karte festzustellen.
Bei beiden Karten handelt es sich um Raster bei denen jeder Koordinate ein Wert, Wand/keine Wand, zugeordnet ist.

Mir fehlt leider komplett der Ansatz wie ich daran gehen könnte.
Wie kann ich die gefundenen Punkte mit den bekannten in der Karte vergleichen.
Dabei muss ja auch die evtl notwendige Drehung der neu erstellten Karte berücksichtigt werden, zumindest in einem späteren Schritt.
Anfangs würde es wohl auch reichen, wenn man voraussetzt, dass bei beiden erstellten Karten "Norden" in der gleichen Richtung liegt.

Unter welchen Suchbegriffen kann ich etwas dazu finden?
Habt ihr eine Idee?

Crypi

[damfino]

Hallo Crypi,
ein brauchbarer Ansatz dazu ist eine Mustererkennung, man vergleich einen Ausschnitt der Karte mit der gesamten Karte bis man die beste Übereinstimmung findet. Bei Rasterkarten ist das einfach, 1 im Raster = Wand, 0 = leer. Jetzt vergleicht man dann einen Ausschnitt von zB 10x10 Kästchen mit der Karte.
Aber nur mit einer einzigen Koordinate geht das nicht, das hilft nur soweit das man im Umkreis um diesen Punkt mit dem Vergleichen anfängt. Man braucht zumindest die Abstände vorn-hinten-links-rechts zu den Wänden wenn das nur irgendwie gehen soll.
Zum testen kann man einfach auf einen karierten Blatt Papier mal einen 10x10 Kästchen großen "Raum" erstellen, dann auf einer Folie ein 5x5 großes Vergleichmuster malen und im Raum verschieben bis es passt. Das dann ins Programm umsetzen.

Ich hatte das so letzten Sommer umgesetzt, die Entfernungen über 8 Ultraschallsensoren ermittelt, in 45° Schritten genordet und mit der Gesamtkarte verglichen. Hat im Endeffekt nicht funktioniert, lag aber eher an der Entfernungsmessung. Im Arbeitszimmer hats funktioniert, im Freien hat er nicht mal die Hausmauer erkannt. Habe aber ehrlich gesagt nicht genau den Fehler ermittelt, hatte andere Baustellen (am Roboter und eine echte) die längere Tests verhinderten.

LG!

[schorsch_76]

Das funktioniert über Korrelation. Siehe dazu [1] bzw. [2].

Das sieht kompliziert aus. Die Musterfunktion ist das Bildarray mit dem gesuchten Ausschnitt und das andere Signal ist das grosse Bild das du durchsuchst. Der Bildausschnitt wird also über das andere Bild gelegt und dann der Korrelationskoeffizient berechnet und ins Zielbild eingesetzt. Ist das Ganze Suchbild abgelaufen worden kann über den Maximalen Korrelationskoeffizienten gesagt werden, dass hier das gefundene Teil liegt. Siehe hierzu [1]

So ermittle ich in der Firma welches Teil gerade vor der Kamera liegt. ;)

Gruß
Georg

[1] http://de.wikipedia.org/wiki/Korrelation_(Signalverarbeitung)#Anwendung_in_der_ Bildverarbeitung
[2] http://de.wikipedia.org/wiki/Korrelationskoeffizient#Empirischer_Korrelationsko effizient

[jcrypter]

Danke für eure Antworten!
Oha... das sieht kompliziert aus..
Da muss ich wohl etwas tiefer einsteigen.

Crypi

[schorsch_76]

Wichtig für dich ist der empirische Korrelationskoeffizient. xi ist eben der Wert eines Pixels. yi ist dann der Wert aus dem anderen Array. x strich ist dann eben der durchschnitt der Pixel und y strich der anderen Pixel.

[ichbinsisyphos]

So tief einsteigen wirst da ned brauchen, lass dich nicht von der Formel einschüchtern. Alles was da passiert ist, dass die kleine Karte (Werte x_i) mit einem genauso großen Auschnitt an einer bestimmten Stelle aus der großen Karte (Werte y_i) verglichen werden. Je größer der Koeffizient der rauskommt, desto größer die Übereinstimmung.

Das Problem ist nur, dass du dafür die kleine Karte probeweise auf der ganzen großen herumschieben musst, dummes Ausprobieren.
Mit einer gröberen Auflösung zu beginnen und erst später zu verfeinern wär auch eine Überlegung wert.

[schorsch_76]

Mit dem Pyramidensystem, kann das massiv beschleunigt werden.

Pseudoalgorithmus:
For Level=3 to 0
Karte/2^Level
Suchbild/2^Level
--> suchen
end_for

Man sucht dann eben in der nächsten iteration im gröseren Bild, aber nur an den Positionen, welche einen gewissen mindestscore überschreiten, bis man bei Level 0 angekommen ist.

[jcrypter]

Nochmal danke für eure Anregungen!
Ich versuche das nachzuvollziehen :)