Überlegungen zum Mapbuilding [Archiv]

Reinald

23.10.2006, 21:58

Hallo Zusammen,

mich würde mal interressieren, wie sich eure Roboter so die Umgebung merken, da gibt es ja grundsätzlich einige unterschiedliche Möglichkeiten:

- 2-D "Bitmap" mit fester Auflösung und "vorprogrammiert"
- 2-D "Bitmap" und der Roboter scannt selber
- Vektorkarte ind 2D oder 3D

Aber da sind mir doch einige Fragen offen, vielleicht hat sich da ja schon mal jemand Gedanken gemacht:
z.B. Welche Auflösung - sollte die Auflösung kleiner sein als der Roboter groß ist? Dann müsste man den Roboter selber mit seinem "Flächenbedarf" mitrechnen. Wenn die Auflösung der Karte kleiner ist als der Roboter, dann wäre das nicht so wichtig.

Unterscheidet man in der Karte zwischen "befahrbar", "nicht befahrbar", "keine Information"?

Wie kann man (oder soll man) zwischen "festen" und "beweglichen" Hindernissen unterscheiden? Die Katze als klassisches Beispiel - kann sich zwischen den Scanvorgängen bewegen. Oder einfach nur eine statistische Methode, die Daten zu bewerten?

Hat sich schon jemand Gedanken zu einem "Standard-Format" gemacht? Treffen sich zwei Roboter, sagt der eine "ey, haste mal ne Karte", sagt der andere "ja klar, aber da hinten ist nix los, brauchste nicht hinfahrn..." ;-) Für ein solches Format könnte man dann auch einen Viewer bauen, um die Ergebnisse zu kontrollieren.

Meine Überlegungen bis jetzt:
- Für die einfachste Variante ist vermutlich eine 2D-Bitmap ausreichend. Das Minimiert auch den Speicherbedarf, so daß es auch in den Microcontroller paßt.
- genauer und für größere Datenmengen wird dann irgendwann die Vektorkarte günstiger. Vermutlich aber erst bei Datenmengen > 100kb. Dafür wird die Verarbeitung aufwändiger. Eine moderne GPU könnte dann aber z.B. Kollisionsberechnung in Echtzeit machen. Braucht vermutlich eine übergeordneten Rechner (PC oder extern), ist mit einem Mikrocontroller nicht zu lösen. Oder Spezialhardware resp. Vektor-Rechner mit größerem Speicher.
- Ein Standard "Dateiformat" würde die Entwicklung vereinfachen, Ergebnisse können besser verglichen werden. Für die Kooperation mehrerer Einheiten ist eine gemeinsame Datenbasis unumgänglich.

Eure Meinungen dazu?

Gruß
Reinald

NumberFive

24.10.2006, 05:52

Zum Thema Karte gibt es hier im Forum doch so einige Threads aber wirklich relaisiert habe ich es noch nicht gesehen bis jetzt. bis auf bei http://www.wiesolator.de/

wie du auch ein kleine Bimapkarte in den controller bringen willst ist mir nicht so klar den wenn wir mal das von aus gehen die karte hat ein auf lösung von 50 cm du brauchst drei bit mindestens um eine punkt zu beschreiben wird der speicher bedarf doch sehr schnell sehr groß.

20 m² raum 5 x 4 m = 80 Quadarte * 3 Bit macht 240 bit = 30 Byte infor mation die relativ schwer zu decodieren ist da du ja die bytes in bit zerlegen mußt und bei drei immer über die byte grenze kommst.

Standard-Format währe klasse weil man sich dann die Arbeit teilen könnte Anzeigen, Routing und so weiter.

Mein Gedanke war immer drei Karten zu haben 0 cm höhe 20 cm höhe und 40 cm höhe. Um überfahrbare Hindernisse ein zeichnen zu können aber nicht den Aufwand für 3D zu haben.

Währe ein nettes Addon für hier:
https://www.roboternetz.de/phpBB2/viewtopic.php?t=16297

Soweit erst mal

marvin42x

24.10.2006, 11:10

Freu freu,

Wie NumberFive schon andeutete haben wir ein RN -Projekt, das solch eine Komponente in der nächsten Ausbaustufe braucht.
Das Projekt stellt in Kürze ein paar Demos vor, da es von der text mäßigen Beschreibung der Sache her etwas unhandlich zu verstehen ist.
Mit den fertigen Komponenten könnte man das Mapbuilding auch gleich praktisch ausprobieren. Und herausfinden welche Überlegungen machbar/nützlich sind und welche nicht.

Mapbuilding:
Dazu ein Standard zu vereinbaren wäre für den Erfolg eines verwertbaren Map –Buildings aus meiner Sicht ausschlaggebend.
Nebenher: Das macht dann auch viel mehr Spaß, wenn man mit Freunden zusammen an einem Mapbuilding –Motor bastelt kann :-)

Zum mir bekannten Umfeld:
MrNiemand hat eine Software die eine 3D gerenderte Darstellung eines Bots innerhalb einer Map bereits kann. Wenn er Koordinaten bekommt kann er das 3d darstellen.
Schuldigung MrNiemand, das ich hier so über Deinen Kopf hinweg mit deinen Sachen angebe.
Ganz oben genanntes Projekt stellt die Infra -Struktur der Kommunikation und ein µC Betriebssystem welches damit umgehen kann nebst PC –Komponenten zur Steuerung und Überwachung der Robs.
Der Von NumberFive gepostete Link zeigt ein sehr gelungenes Projekt.

Das war jetzt mal zum beleuchten der Umgebung gedacht um erstmal ein paar praktische Optionen ins Bild zu bringen.

Netter Gruß

marvin42x

24.10.2006, 11:56

@Reinald:
Deine ersten Überlegungen sind meiner Meinung nach eine gute Ausgangsbasis um sich der Sache zu näher.

Allgemein:
Die kleinen µC’s können da nicht die großen Sprünge machen.
Was ich mir vorstellen könnte ist ein kleines µMapsystem und einen großen Bruder der auf einem PC gehostet wird.

PC:
Auf dem PC würde mir eine Datenbank –Anbindung vorschweben. Damit kann man große Datenmengen in akzeptabler Geschwindigkeit verhütten ohne eigenen Speicher und Verwaltungsprogramme zu schreiben.
Das ist bewährte Technik, die zudem auch Netzwerkfähig ist.
Davor oder dahinter schaltet man Auswertesoftware die mit den bereitgestellten Daten was anfangen kann.
Viewer für das Ganze stehen in den Startlöchern.

µController
Auf den Kleinen fällt mir nicht viel ein. Es ist sehr eng.
Dort kann eigentlich nur ein kleiner aktueller Kartenausschnitt überleben welcher ihn aber durchaus autark macht. Das Format der Koordinaten sollte auch Speichersparsamer sein, anders als auf dem PC.
Hier birgt auch die Vernetzung der Kleinen Vorteile, also so wie Du Eingangs schon gesagt hast.
Ich vermute, dass man nur Koordinaten von existierenden Messungen ablegt, ohne ganze Arrays zu errichten die eine Map repräsentieren.

Netter Gruß

Reinald

24.10.2006, 16:10

So, um das Ganze ein bischen zu strukturieren:

Step 1: Vereinbarung einer Datenstruktur, um µ-Maps auf einem µ-Controller zu speichern. Dateiformat ist hier wohl zu hoch gegriffen. Eine einheitliche Struktur würde aber die Wiederverwendung von Code-Snippets vereinfachen. Mein Vorschlag: Rasterdaten mit 4 Bit / Pixel. Damit lassen sich genug Werte codieren, um
- befahrbar
- nicht befahrbar
- hier bin ich
- hier steht eine Bake
- undefiniert
- "gestern war hier noch frei heute steht hier was ist es vielleicht die katze?"
zu codieren.
Für den Zugriff auf die Karte sollte man einen Satz passender Funktionen bauen, damit ist dann auch das Aufsplitten in die oberen/unteren 4 Bit verkapselt. Im ersten Schritt könnte die Karte auch erstmal "fest" codiert werden, d.h. händisch erstellt und geladen. Man kann davon ausgehen, den Bot beim Start auf ein definierte Position zu stellen bzw. ihm seine Position mitzuteilen. Orientierung und Rückkehrgenauigkeit stellen die erste Herausforderung an den Bot und seine Steuerung - Navigation - Odometrie. Eine zweite/dritte "Ebene" würde ich an der Stelle für überflüssig halten (oder gibt es da einen Anwendungsfall für?)

Step 2a: Aufbau der Karte durch den Bot selber. Dabei sollte es darum gehen, die Daten vom Bot selber erfassen zu lassen. Heraus kommt dabei eine Karte, die weniger in "go vs. nogo" eingeteilt ist, als grundsätzliche "wo könnte ich fahren"- Informationen. Praktische Herausforderungen werden sein, passende Filter für die Bewertung der Sensorinformationen zu entwickeln. Wann wird ein Pixel "schwarz", wann wird es "weiß"? Was mache ich mit wiedersprüchlichen informationen unterschiedlicher Sensoren? Was mache ich mit Wiedersprüchlichen Informationen zwischen Karte und Sensor-Input?

Step 2b: Die Orientierung innerhalb der Karte. Geht man in Step 1 und 2a noch davon aus, daß der Bot auf einem definierten Startpunkt steht, ist es natürlich spannender wenn er "spontan" beim Einschalten seine Position erkennen kann. Was man Outdoor mit DGPS halbwegs lösen kann, ist indoor eine andere Aufgabenstellung. Hier finde ich die Überlegungen zu einem "Local Positioning System" sehr gut, "Leuchttürme" die rotieren und dabei die Winkelinformation verschicken. Damit können die aufsummierten Fehler der Wegeerfassung wieder ausgeglichen werden.

Bis hierhin sollte das alles auf dem Mikro-Controller gelöst werden können.

Step 3ff: Kommunikation mit einem Steuer-PC. Dabei spielt es keine Rolle, ob der PC "onboard" sitzt oder per Funk angebunden ist. Also:
- Karten upload
- Karten download
- Statusabfragen
- Steuerbefehle
- rendern einer Pixel-Karte aus der "großen" Vektorkarte

Als Datenformat auf dem PC würde ich entweder ein XML-basiertes Format vorschlagen, oder einen offenen Standard aus der 3-D Welt. Letzteres hätte den Vorteil, daß es Viewer fertig gibt. Ersteres wäre "human readable" und könnte einfach in Datenbanken abgelegt werden.

Soweit erst mal.
Reinald

wkrug

24.10.2006, 18:23

Ich hätt da noch mal eine vieleicht blöde Frage - bin selber kein Roboterbauer:

Wenn man Karten benutzen will muß man doch wissen wo sich der Bot befindet um eine Route oder das nächste Hindernis finden zu können.

Müsste das dann nicht auch noch irgendwie realisiert werden ?
Das mindeste wäre doch ein fester Bezugspunkt ?

Und wenn Ja, wie realisiert man das, ohne im gewünschten Zielgebiet umfangreiche Installationen zu machen?

Tschuldigung - ich frag blos aus Neugier...

MrNiemand

24.10.2006, 19:08

Hi,

ich halte eine dynamische Verwaltung für viel zu Aufwendig, und ein Array mit fester Größe kann ein µC auch noch effektiv verwenden.

als Beispiel:

ein Array mit 512x512 Werten jeder Wert entspricht dabei 10cm
=> die Maßfläche liegt bei 5120cmx5120cm

das ganze braucht dabei nur 32kbyte Speicher wenn nur abgespeichert werden soll ob ein Hinderniss auf diesem Punkt ist oder nicht.
(Das macht durchaus Sinn, denn so weis der Bot gleich "holla da war ich schon, da will ich nimmer hin")

Ok für den Fall "da war ich noch noch nicht" muss man sich was einfallen lassen, aber ich finde 4bit doch reichlich viel, für die Position des Bots reicht ja z.b. ein Datensatz, da muss man nicht das ganze Array zuschmeißen damit, zumal es für den Bot dann schwer ist, sich auch selbst wieder zu finden in dem Teil.
Eine Katz z.b. ist schnell erledigt, beim letzten Scan war ein Hinderniss da, nun nicht mehr => Hindernissinfo löschen.

marvin42x

24.10.2006, 19:41

Na das hört sich doch schon nicht schlecht an.

Reinald, ich muss sagen, ich bin ganz auf Deiner Linie.
Auch die 3D –Engins habe ich im Augenwinkel.

Ich habe mich die letzte Zeit nur mit dem Kommunikationsprojekt befasst.
Das wird dabei auch voll zum Tragen kommen.
Dadurch sind diese Einzelkomponenten wie Map -Building bei mir noch nicht bis ins Detail durchdacht.
Das mindert meine Kritikfähigkeit :-)

Mal sehen ob noch ein paar Kundige was dazu sagen. Damit das Bild rund wird.
MrNiemand wird ja dazu auch schon konkret.

Die Frage ob und wie dynamisch, und welche Lastenverteilung zwischen PC und µC die richtige Wahl ist werden wir abwägen müssen.

Des weiteren ob der Robi Arrays benutzt oder nur Koordinaten von Hindernissen und dem „Zaun„ des Gebietes was er schon gescannt hat speichert.

Auch das Format in dem Kommuniziert werden soll ist Thema.

Ich freu mich erstmal, dass das so konkret losgeht.

Netter Gruß

PicNick

24.10.2006, 19:55

Ich wär mal für ein "RAW" Format.

Was ist denn eigentlich eine Karte ?
Ein Karte ist eine Sammlung von koordinaten + zugeordneter Sensorwert,
die nach den Koordinaten sortiert ist.

Übermitteln kann man das en block oder einzeln, das ändert erstmal nix.

Was muß ein Empfänger wissen ?
Type xy(z) oder vektor
Sensortyp
Units (cm, m, inch, etc.) /absolut/relativ
Das braucht wohl nur einmal zwischen den Partnern festgelegt zu werden.

Und je "Pixel" Information eben x, y, (z bei 3D) und der Sensorwert.

Das kann ein Robby nun direkt zum PC schicken, er kann natürlich auch selbst seine Informationen rausholen, muß er aber nicht.

Gerade für eine langsame Robby-PC Strecke word man wohl eine art RLE Verfahren anwenden, dh. heißt sendung nur dann, wenn sich der Sensorwert um einen gewissen Wert ändert (parametrisierbarer Threshold ?)
Dann sollte er aber schon auch seine Odometriedaten auch schicken.
Für die gilt wieder Ähnliches, also ganz primi nur steps links/rechts oder schon aufbereitet .

marvin42x

24.10.2006, 20:24

Hi PicNick :-)
Das wird ja ein netter Abend.

So wie Du das beschrieben hast könnte ich mir das vorstellen.
Eine Frage dazu:
Brauchen wir zu den Koordinaten x,y, eventuell z noch einen Sensorwert?
Oder können wir den einspaaren?

Auch die Datengröße der Koordinaten müsste man mal abschätzen.
Ob 8 bit, 16 oder was weis ich.

Netter Gruß

Reinald

24.10.2006, 21:06

Hallo zusammen,

So, dann wären wir also bei Step 1 ;-) :

Ich hatte nicht an ein dynamisches Array gedacht. Ich bin davon ausgegangen, daß man sich erstmal in einem festen Array bewegt. Um die Sache im Mikro-Controller nicht unnötig zu komplizieren, geht man erstmal von individuell, aber fest definierten Rasterweiten aus. Je nach größe des Bots und dem Terrain können das 5cm Steps sein oder vielleicht auch 20cm - das hängt halt von den individuellen Anforderungen ab. Dabei würde ich in erster Näherung auch nur von einem flachen Terrain ausgehen.

Im Folgenden werde ich die Rastereinheit "Pixel" nennen, das scheint mir passend.

Pro Pixel wollte ich ein halbes Byte für den Wert nehmen, das scheint nicht ganz deutlich geworden zu sein. Also nicht den Sensorwert speichern. Meine Planung sieht mehrere unabhängige Senoren vor. Gespeichert zu werden braucht dann nur das Gesamtergebnis als "da kann ich hinfahren" oder "da kann ich nicht hinfahren". Daneben sind aber möglicherweise noch andere Zustände Interressant:
- Wo bin ich?
- Wo stehen Baken?
- Unbekannte "tote Winkel", die noch nicht "gescannt" sind.
- Wiedersprüchliche Informationen der unterschiedlichen Sensoren / Unsicherer Wert

Wenn man alles zusammenzählt, kommt man möglicherweise mit weniger als 4 bit hin, aber das erscheint mir auch im Hinblick auf die Speicherorganisation praktisch. Wenn man noch die Unterscheidung auf andere "Mitspieler" hinbekommt, dann können also auch noch andere Zustände ins Spiel kommen.

Gruß
Reinald

MrNiemand

24.10.2006, 21:37

Naja ich bin da eigentlich sowieso ehr für Vektorbasiered:

Denn ich kuck da dabei natürlich auf meine 3D Oberfläche, und ich befürchte es sieht hässlich aus, wenn versucht wird, aus den Feldinformationen die Hindernisskoordinaten zu berechen
(Beispiel: ein Hinderniss geht 3Felder nach rechts und 1Feld nach hinten. (Ergebniss zeigt Paint denk ich mal recht deuchtlich wenn man eine Linie zeichnet).

Aber zu den festen Feldern, wäre es nicht sinnvoller auf weniger Bit zurück zu greifen? 32kybte effektiv handeln halte ich z.B. für machbar aber *4 wären das 128kbyte, das ist schon eine ganze Menge mehr.

Evl kann man doch krumme werte wie 2bit oder so recht einfach verwenden, da das ganze ja sowieso auf einen externen Ram auf µC Seite rausläuft, kann die Layer Wahl leicht durch Tooglen der Adressleitungen erledigt werden.

Evl macht es doch z.b. mehr Sinn Infos wie Standort des Bots oder Standort von Baken einfach absolut zu speichern mit ihren Koordinatenwerten (warum z.b. 512*512bit verschwenden für eine Bake)?

marvin42x

24.10.2006, 21:41

Ich bin jetzt nicht sicher ob ich was falsch interpretiere.
Bei 4 bit als x
Und 4 bit als y
sehen ich ein Quadrat mit einer Kantenlänge von 16 Pixel vor mir?

Wenn ich mir ein Wohnzimmer vorstelle, sagen wir mal 5 x 5 Meter.
Bei einem Raster von 20cm wäre das ein Quadrat von 25 x 25 Pixel.

Ein Infrarot Entfernungssensor liefert im Idealfall Werte die auf wenige Zentimeter bis hin zu einem Zentimeter genau sein können.

Wenn ich zwischen Stuhl und Wand durch will muss ich vorher wissen ob das geht oder nicht.

Ich sehe hier zwei Anforderungen:
Grobes Raste für “Wo bin ich im allgemeinen“
Feines Raster für „Fahr ich dagegen oder dran vorbei“

Ich vermute, das wird man mit 4bits nicht hinbekommen.

Kann aber auch sein das ich was missverstehe.

Netter Gruß

Reinald

24.10.2006, 22:05

@Marvin: 4 bit PRO Pixel. Also:
Zimmer 5x5m Raster 20cm --> 25x25 Pixel --> 625 pixel *0,5Byte --> 313Byte Speicherbedarf.

Zimmer 5x5m Raster 1cm --> 500x500 Pixel --> 250k pixel *0,5Byte --> 125kByte Speicherbedarf

Die 4 Bits hätte ich vorgesehen, um den Pixeln etwas mehr Informationsgehalt zu verpassen, also zwischen schwarz und weiß noch ein bischen abstufen zu können. Ich bin sicher, die Anforderung dafür taucht auf (frei, besetzt, unbekannt, wiedersprüchliche Infos, andere Agenten, ...)

jetzt nachvollziehbarer erklärt?

@MrNiemand:
Natürlich ist verkorbasiert eigentlich die saubere Lösung.
mit 8Bit Genauigkeit könnte man im obigen Beispiel eine Genauigkeit von 2cm erreichen, in einem Koordinatensystem mit 5m Kantenlänge. Allerdings braucht man pro Vektor 4 Byte (in 2D). Bei Vergleichbarem Speicherbedarf kann man 7812 Vektoren modellieren, gegenüber 62,5k Pixeln. Wenn man mal davon ausgeht, eine Fläche innerhalb des Koordinatensystems (256*256) zu beschreiben, und dabei nur die kürzest-möglichen Vektoren zu verwenden, kann man mit ca. 1000 Vektoren einmal die Außenkontour abfahren, oder schon recht komplexe Konturen innerhalb des Systems zusammenbauen.

In der Praxis wird allerdings eher 16 oder 32Bit integer Genauigkeit gefragt sein, wenn nicht sogar Floating Point.

Was mir allerdings völlig unklar ist: Wie gut kann der AVR mit Vektoren rechnen? Insbesonders, wenn nicht die kürzestmögliche Schrittweite gewählt wird? Es soll ja auch ein guter Teil auf einem Micro-Controller laufen können.

Gruß
Reinald

marvin42x

24.10.2006, 22:38

Danke Reinald.
Dann ist das klar, dann ist die Frage die ich vorher in den Raum gestellt habe noch gültig.

Zitat:
Auch die Datengröße der Koordinaten müsste man mal abschätzen.
Ob 8 bit, 16 oder was weis ich.

Damit entscheidet sich ja im wesendlich der Speicher und auch Kommunikationsbedarf.

Netter Gruß

Reinald

25.10.2006, 07:44

Hallo Marvin,

ich habe den Datenbedarf mit 4 Bit angenommen - wo siehst Du den Bedarf für 8 Bit oder 16 Bit pro koordinate?

Was hältst du von einer Vektorbasierten Lösung? Das scheint auch im Bezug auf den Speicherbedarf attraktiv zu sein, aber kann man im AVR-Mikrocontroller damit effizient rechnen? Die Vektoren ermitteln aus passenden Sensordaten? Das erscheint mir bei einer "Bitmap"-Karte doch etwas einfacher zu sein.

Gruß
Reinald

PicNick

25.10.2006, 07:54

Ihr habt euch offenbar auf sowas wie 0/1 (befahrbar/nicht befahrbar)
eingeschossen. Und ihr wollt tatsächlich ALLE Koordinaten in einem Array X x Y ablegen ?

Reinald

25.10.2006, 10:19

@PicNick: es ist halt eine naheliegende und einfache Lösung. Aber vielleicht hast Du eine bessere Idee? Flexibler und Leistungsfähiger ist vermutlich eine vektorbasierte Variante, die Frage ist wie das aussehen soll und ob das in einem Mikrocontroller noch zu verarbeiten ist.

Gruß
Reinald

PicNick

25.10.2006, 10:24

Würde sagen, das Mindeste wär wohl eine RLE Speicherung, das spart Platz und ist auch für den µC kaum ein Problem. (RLE brauch ich nicht zu erläutern ?)

marvin42x

25.10.2006, 10:30

Bitmap bzw. Array:
Da ich glaube, es gibt zwei Gruppen, das ist Reinal und MrNiemand auf der einen Seite PicNick und ich auf der anderen Seite, die noch an einander vorbeireden
Möchte ich sicherheitshalber zwei Sätze von mir ins Spielfeld zurück rollen:

Zitat :
1. „Das wird ja ein netter Abend“. (Der hat nun überhaupt nichts mit der Sache zu tun :-)

2. „Des Weiteren ob der Robi Arrays benutzt oder nur Koordinaten von Hindernissen und dem „Zaun„ des Gebietes was er schon gescannt hat speichert.“

Der Begriff Koordinate bedeutet in unserem Fall doch, dass man den Ort eines Pixels mit einer Längenangabe und einer Breitenangabe beschreiben muss damit man ihm eine Eigenschaft wie z.B. frei oder Hindernis zuweisen kann.
Diese Längen und –Breitenangabe wird im Moment m.E. unter den Tisch fallen gelassen.
Sie ist aber der wahre Speicherfresser.
Und Hier lohnt es sich mit intelligenten Strategien Einspaarungen vorzunehmen.

Das gesagte betrifft jetzt erstmal nur den Punkt Array.

Netter Gruß

Edit:
Ich werde mich bemühen schneller zu schreiben damit ich hier "just in Time " bin und nicht hinterher hinke.

marvin42x

25.10.2006, 10:42

RLE habe ich eben nachgeschlagen:
http://de.wikipedia.org/wiki/Laufl%C3%A4ngenkodierung
Das wäre eine Sache die wir generell im Auge behalten sollten.

Netter Gruß

MrNiemand

25.10.2006, 16:03

Also ich habe mich kennesfalls auf 1/0 abspeichern eingeschossen ;)
Ich bin an sich auf für eine Vektorbasierende Speicherung.

Ich denke den Grund dafür habe ich bereits in meinem letzen Post erläutert (ich denke an meine 3D Oberfläche...)

PicNick

25.10.2006, 16:33

Bei wirklichem 3D könnt' man fast auch über "Meshes" nachdenken.

MrNiemand

25.10.2006, 16:41

daran habe ich schon gedacht, zumindest für die 3D Berechnungen mit hilfe meiner beiden Webcams (du wirst dich sicher an den Thread erinnern ;)

bis lang verwende ich als Grundlage 2D Vektoren, daraus werden dann die restlichen Punkte automatisch berechnet, die für eine 3D Darstellung benötigt werden.

Denn ich halte es durchaus für machbar den µC mit Vektoren rumschubsen zu lassen. Das schwierige (was mir demnächst bevor steht) ist einem µC bezubringen, wie er aus den ganzen Einzelmessungen meiner Sharps (drehbar) vereinfachen kann, um die nötigsten Vektoren als Ergebnis zu bekommen.

PicNick

25.10.2006, 16:45

..ganzen Einzelmessungen meiner Sharps (drehbar..
Weil du es grad sagst: Ich kämpfe mit sehr schwankenden Meßwerten vom GP2D12. Wie sieht es da bei dir aus, und, wenn besser, wie hast du das beschaltet ?

MrNiemand

25.10.2006, 16:49

direkt daran diverse Kondis (100n helfen schon sehr).
Über die Versorgung kommt gerne noch was rein (bzw stört der Sharp sich u.U. selbst. Einfach mal Oszi darauf ansetzen dann sieht man doch gut, woran es hapert.
Desweiteren sind bei mir die Sharps wie auf http://mrnd.dyndns.org/elektronik/botbilda/bot3.jpg zu sehen befestigt, das verhindert die fehlerhaften Messwerte an senkrechten Kanten.

Ansonsten werde ich mich mal daran versuchen die Messungen auf die Ausgabe eines neuen Sensorwertes zu syncnen (hab mein Oszi schonmal am Sharp gehabt, gibt da eingies an evl. verwendbaren Signalen), damit will ich bei max. Messrate die Fehlmessungen stark verkleinern (z.b. kann es sonst passieren das ich den Messwert der letzten Messung für den der aktuellen verwende.)

Reinald

25.10.2006, 16:55

Hallo Marvin42x,

ja, es scheint daß es da noch ein Mißverständnis gibt.

a) Bei meinem "Bitmap"-Vorschlag gehe ich davon aus, entsprechenden Speicherplatz komplett zu allozieren. In diesem Array von 4Bit x X-Coord x Y-Coord kann man entsprechende Werte Eintragen/Auslesen. Die X/Y-Koordinaten ergeben sich aus der Position im Array. Das ist simpel, braucht aber für genauere Karten viel Speicherplatz.

b) Mal schaun, ob ich den anderen Vorschlag richtig verstanden habe:
- erstmal gehen wir davon aus, das alles befahrbar ist
- wir speichern nur die Hindernisse bzw. den "Zaun" drumherum
- dafür brauchen wir im Datensatz die Angabe von X/Y-Koordinate + evtl. noch ein paar Bit für Zusätzliche Informationen

Letzteres ist wiederum gar nicht weit weg von einer 2D-Vektor-Lösung. Lediglich die Länge der Vektoren wäre einheitlich "1 Rastereinheit".

@MrNiemand: Hast Du schon mal mit 2D oder gar 3D-Vektoren auf einem Mikrocontroller gearbeitet? Da sehe ich im Moment das größte Problem:
Bei einer Bitmap kann ich ausgehend von meiner eigenen Position relativ schnell ermitteln , ob ich in das gewünschte angrenzende Feld fahren kann/darf, bzw. in welche Position ich fahren kann. Bei einer Vektorbasierten Lösung muss ich immer gegen alle Vektoren in der Karte Prüfen, die könnten ja schließlich auch länger sein und ich muss errechenen, ob sie sich mit meinem Bewegungsvektor schneiden.

Grüße,
Reinald

PS: Ich favorisiere keine spezielle Lösung und bin offen für alle Vorschläge, mein Interesse gilt einer praktikablen Lösung, die auf einem Mikrocontroller lauffähig ist und einige Grundlegende Anforderungen löst.
3D-Laserscan, Video-Bildanalyse, Bau eines 3D-Gitternetzes und Kollisionsberechnung darin scheiden daher leider aus.

PicNick

25.10.2006, 17:04

Ist die Frage, wieweit sich eine Karten-Bitmap von einer Video-Bitmap eigentlich unterscheidet (jetzt mal prinzipiell).

Dass 3D immer eins drauf, is natürlich logo.

Reinald

25.10.2006, 17:08

@PicNick: Was verstehst Du unter "Video-Bitmap"?

Gruß
Reinald

PicNick

25.10.2006, 17:11

Naj, Karte ist x, y und ein Wert
Video(ein Frame) ist x, y und auch ein Wert (Farbe, Helligkeit)

marvin42x

25.10.2006, 17:53

Wenn ich bei euch mitlesen will, muss ich ständig was nachgooglen.
Mesh:
http://erbsen.er.funpic.de/.theprodukkt/Building%20a%20Demo/meshes.htm
Habt ihr noch mehr so Wörter die ich nicht kenne?

Das mit der Bilddatei, oder einem Videoframe ist mir auch durch den Kopf gegangen.
Das ist aus meiner Sicht dasselbe.
Wenn ich das damals beim Amiga richtig verstanden habe, haben die einen großen Leistungssprung im Datentransfer gemacht als sie einfach die Videodatenschaufel benutzt haben. Die war notgedrungen schnell und eben schneller als der Rest der Speicherverwaltung.
Beim Amiga gab es keine strikte Trennung zwischen Hauptspeicher und Videospeicher. Das war alles einer.

Aus diesem Grund lohnt sich aus meiner Sicht schon, mal zu gucken wie Frames behandelt werden und vielleicht auch Routinen aus der Frame -Fummelei zu adoptieren.

Der Amiga hatte auch das erste ernst zu nehmende Bilddateiformat:
IFF Intechange File Format. Mit Haeder und Boddy und so.

Des Weiteren hatte er eine witzige Art Speicher zu sparen.
Die hieß HAM.
Hold and Modify. Da wurde für den Nachbarpixel nur der Differenzwert gespeichert.
Also: Alten Wert halten und neuen Modifizieren. Damit haben sie farbtiefen generiert die eigentlich unmöglich für das System waren.

Zum Thema speziell:
Insgesamt kann man ja ein komplettes Array real, oder virtuell errichten. Aber die Koordinaten die fürs Leben wichtig sind machen nur einen Bruchteil davon aus.

Man könnte übrigens, wenn wir hier grob was klar haben auch in einen Evolutionären Prozess eintreten und mal was Prototypenhaftes auf die Beine stellen.
Und mal sehen wie sich das macht.
Das ganze könnte man im ersten Durchlauf auf dem PC machen um die Logik und Funktionalität zu entwickeln. Erst dann verkleinern und auf den µC.
Dabei können zwei Modelle verfolgt werden:
Array und Vector.
Der Zustrom von Sensordaten müsste idealer weise erstmal künstlich sein. Denn nicht jeder hat einen lauffähigen Robi im Schrank oder unter dem Sofa(wo ihn Mutti nicht findet).

So für ein Post genug

Netter Gruß

marvin42x

25.10.2006, 18:13

@PicNick:
Wäre es mit erträglichem Aufwand möglich Deinen Server dazu zu bringen TCPClient zu TCPClient zu routen?.

Damit könnten wir eine lebende Entwicklungsumgebung herstellen.
Die Clientfunktionalität haben wir ja auch schon.

Netter Gruß

gast1234

25.10.2006, 18:14

Hallo,

wenn ich mich mal reindrängen darf. An die Pixelfreunde, vielleicht interessiert euch ja die Datenstruktur des Oct-Trees.

Hier werden 3 dimensional orientierte Daten (binär besetzt/frei oder auch skalare) in einer Baumstruktur repräsentiert, die genau wie ein Array Nachbarschaften fest definiert und zugleich eine Art dreidimensionale Lauflängenkodierung beinhaltet.
Das ganze kann problemlos um eine Dimension reduziert werden.
http://de.wikipedia.org/wiki/Octree

PicNick

25.10.2006, 19:08

@PicNick:
Wäre es mit erträglichem Aufwand möglich Deinen Server dazu zu bringen TCPClient zu TCPClient zu routen?.

Kein Aufwand. Aber die Clients müßten ihre IDs bekanntgeben.

Zwischenmöglichkeit:
Alles wird ge-broadcastet. (ausser dorthin, wo's herkommt)

Gruß ins Tal (wo die vielen Brücken sind) :mrgreen:

PicNick

25.10.2006, 19:23

Bei den Speicherungsmöglichkeiten auf µC wird man (oder halt nur ich) den Kopf mal schief halten, damit das Hirn in einer Ecke zusammenläuft und man besser nachdenken kann.
Aus dem Bauch zumindest weiß ich, daß es keine einzelnen seligmachenden Weg geben kann, es wird drauf ankommen, was man für Auswertungen braucht.

@gast1234: angeguckt, danke. Die meisten Verfahren beruhen darauf, daß man hemmungslos "new" sagen kann, und wenn's nicht reicht, kauft man einen größeren PC. Denen (für Games) kommt's primär auf die Geschwindigkeit an.
Dem µC fehlt halt sowohl als auch. :-(

Reinald

25.10.2006, 20:52

Ahh, jetzt ja ;-)

Also, so langsam kommen wir zu einem gemeinsamen Verständnis.
Was ich als "Bitmap" und "Pixel" bezeichnet habe, meint genau das, was auch mit "Frame" gemeint ist - eine "Bilddatei". Ohne Header. Ohne Kompression. Einfach 1:1 als Array im Speicher abgelegt. Mit 4 Bit "Farbtiefe" pro Pixel.

Hat schon mal jemand Erfahrungen mit komprimierten Daten auf einem Microcontroller gemacht? Der Zugriff auf die Daten ist sicherlich langsamer und umständlicher, als wenn man direkt auf die Daten in einem Array zugreifen kann. Nach meiner Einschätzung muss man die Daten zum Zugriff ja zumindest teilweise wieder "expandieren", lohnt der Aufwand dafür?

Bleibt die spannende Frage, ob die speichereffiziente Variante einer Speicherung in Vektoren hinreichend gut zu verarbeiten ist. Spannender ist es allemal, die Frage ist ob es auch effizient zu implementieren ist.

Lineare Algebra war nicht so meine Stärke - gibt es einen coolen Trick, den Schnittpunkt zweier Vektoren zu berechnen, oder läuft das auf das lösen eines Gleichungssystems raus?

Gruß
Reinald

gast1234

26.10.2006, 01:27

Die meisten Verfahren beruhen darauf, daß man hemmungslos "new" sagen kann, und wenn's nicht reicht, kauft man einen größeren PC

gast1234

26.10.2006, 09:49

Nachtrag:

Wenn man sich mal das Verhältniss der meisten Flächen zu ihren Umfängen ansieht, erkennt man, dass mit steigendem Umfang die Fläche annähernd quadratisch zunimmt. Im Umkehrschluss bedeutet dies hier, dass eine Verfeinerung des Rasters, den Einspareffekt überlinear erhöht.

Geht man jetzt noch in den Raum oder Hyperraum, gehen die Einsparungen in Richtung dritte, vierte ... Potenz zur Verfeinerung des Rasters.

Das Verfahren ist nicht für performancesüchtige Grafikfreaks ausgelegt, sondern war mal Idee einer speichereffizienten und nicht verlustbehafteten Speicherung von Voxeldaten, wie sie bei einer Magnetresonanz/Kernspin- oder Computertomograhpie vorkommen.

marvin42x

26.10.2006, 12:09

@gast1234:
Mein lieber Mann.......
Schwere Kost.
Sieht aber sehr interessant aus.
Danke für die ausführliche Mühe.
Das hat ja richtig Arbeit gekostet.
Für meinen Teil brauch ich etwas Zeit um das genauer zu beleuchten.
Im ersten Hinschauen wäre das durchaus ein Kandidat den man mal realisieren sollte.

@all:
Wenn ich schon am Anfang hier mit Prototypen rum fuchtele bevor überhaupt der theoretische Überbau steht.
Geschieht das aus meiner Erfahrung mit dem RN-Comm Projekt in dem ich gerade mit mache.
Dort haben wir uns sehr viel Mühe im Vorfeld mit der Theorie gegeben. Was sicher auch wichtig war.
Als dann die ersten Programme das laufen lernten konnten wir aber aus den praktischen Erfahrungen heraus einiges über Board werfen und neu definieren.
Im Rückblick gesehen hätten wir meiner Meinung nach schon viel früher etwas Hemdsärmeliger rangehen können um die Praxis und Theorie gleich zeitig wachsen zu lassen.
Das ist aber jetzt, wie gesagt, meine ganz persönliche Meinung dazu.

@PicNick:
Prima, das Angebot ist angenommen :-)
Ich bestelle hiermit einen RN-Comm Server mit Client ->Sever->Broadcast Funktionalität.
Ausbaustufe: Völlig egal
Liefertemin: Ab jetzt
Preis: Eine Huldigung.
Ich würde dann mal einen Sendeclient und einen Empfangsclient herstellen wollen(in VB2005).
Der Sendeclient sollte mal eine Reihe von Koordinaten ausgeben die im Sendeclient empfangen werden.
Daran kann man dann Programmteile Knüpfen die mit den Daten was machen.
Das wäre Programmtechnisch mal ein Vorschlag.
Um Meinungsäußerung wird gebeten.
Genug für den Post.

Netter Gruß