Mehrere Trackpoints

Heute Abend habe ich ein bisschen die Anwendung erweitert, so dass die verschiedenen Punkte wiedererkannt werden können. Jetzt ist es erstmals wirklich möglich mehrere Trackpoints zu erfassen. Als Beispielanwendung habe ich das Malprogramm so erweitert, dass mehrere Personen (bis jetzt nur 2) über die gleiche Kamera malen können.

mehrere_trackpoints

Motion Tracking

Die letzten Tage habe ich Captain Tomates Catchup Games – Folge 3 bei Ehrensenf gesehen und dabei einen Link gefunden, der mich sehr beeindruckt hat. Leider bin ich kein glücklicher Besitzer einer Wii wie Herr Jhony Chung Lee und habe mir deshalb gedacht, dass  meine iSight zwar nicht eine so hohe Auflösung hat wie die Infrarotkamrea der Wii Remote, aber trotzdem genauso im Stande ist Infrarotlicht zu sehen. Die hardwarebeschleunigte Trackingfunktion in der Wii Remote, so dachte ich mir, kann ja auch nicht schwer nachzuahmen sein.

Da die Programmiersprache, die mir am meisten liegt Java ist, und ich an einem Mac arbeite, auf dem die JMF leider nur eingeschränkt lauffähig ist, habe ich die alten Klassen von meinem TicTacToe Projekt im Rahmen meiner 12 Klassarbeit mit denen ich dieses Problem mit Hilfe von Quicktime für Java umgangen hatte wieder herausgekramt und auf meine JVM losgelassen. Nach einigen Fehlstarts hatte ich auch ein Bild mit ordentlicher Framerate.

Um nun Trackingpunkte zu extrahieren, habe jeweils alle Pixel des einkommenden Bildes untersucht und sie, wenn ihre Helligkeit einen bestimmten Schwellwert überschreitet, zu einer Liste hinzugefügt. Auf die Pixel in der Liste habe ich dann ein Clusteringverfahren (eine leicht angepasste und speedoptimierte Version von hirachical clustering) angewendet um die Pixel zu Trackpoints zusammen zu fassen. Anschließen habe ich noch die Anzahl der in die Liste aufgenommenen Pixel auf ein Fünftel reduziert, indem ich nur die Pixel aufgenommen habe, die nicht komplett von hellen Pixeln umgeben sind, um die Performance zu erhöhen. Es werden dann nur die Randpixel eines hellen Punktes aufgenommen. Die Genauigkeit leidet so gut wie garnicht darunter.

Die erfassten Koordinaten der hellen Stelle können dann für beliebige Zwecke genutzt werden. Zum Beispiel um ein kleines Zeichenprogramm daraus zu basteln.

Unter dunkleren Lichtverhältnissen (am besten Abends) funktioniert es sogar erstaunlich gut mit einer kleinen LED Taschenlampe.

In Planung ist jetzt einen IR-Filter vor die Kamera zu kleben und mit einem IR-Pen zu arbeiten. Dann gehts auch bei hellerem Licht (hoffentlich). Mehrere Trackpoints zu erkennen funktioniert auch schon, habe ich aber noch nicht angewendet, da ich noch nicht das Problem gelöst habe die Trackpoints in jedem Bild wieder zu erkennen und zuzuordnen, so dass mehrere Trackpoints nicht verwechselt werden.

Geschwindigkeitsoptimierung

FitnessberechnungWie ich Gestern schon geschrieben habe, habe ich die Geschwindigkeit bei der Berechnung der Fintess deutlich erhöhen können, indem ich einfach die Simulationsumgebung „recycle“. Dazu habe ich einige Messergebnisse festgehalten. Der Graph zeigt die Berechnungszeit der Fitness (in Millisekunden) in Abhängigkeit von der Anzahl der Individuen, für die die Fitness errechnet wird. Die obere Kurve zeigt die Gesamtzeit, die zur Berechnung der Fitness benötigt wurde; die untere Kurve zeigt die Zeit, die letztendlich zur Berechnung der Simulation nötig war. An der Differenz kann man ablesen, wie viel Zeit zum Aufbau der Simulation benötigt wird (ich empfehle die Grafik anzuklicken um bei besserer Auflösung mehr zu erkennen).

Je mehr Individuen berechnet werden, desto größer wird der Anteil der effektiv genutzten Simulationszeit, während der Anteil der Zeit, die zum Aufbau genutzt wird, immer weniger der Gesamtzeit ausmacht.

Aktueller Stand der Labyrinth Bots

Mittlerweile habe ich Simbad, meine Netzwerk Simulation und die evolutionären Verfahren auf einen gemeinsamen Nenner gebracht, noch ein paar Klassen um Graphen mit GNUPlot zu erstellen geschrieben und schon die ersten Ergebnisse erzielt. Die Labyrinth Roboter sind mittlerweile in der Lage Wänden und anderen Objekten auszuweichen.

Labyrinth Welt

Labyrinth Welt

Ich habe jeweils 14 Quader zufällig in der Testumgebung verteilt und die Fitness danach berechnet, wie weit es die Roboter jeweils geschafft haben sich vom Ausgangspunkt zu entfernen. Man konnte dann nach einiger Zeit (ca. 50 Epochen, mit 80 Individuen) erkennen, dass die Roboter Hindernissen ausweichen und in Sackgassen (manchmal) umkehren.

Zu schaffen gemacht hatte mir noch Gestern die langsame Berechnung der Fitness. Sechs 15 Sekunden lange Simulationen benötigten ca. 4,5 Sekunden Berechnungszeit. Nach genauerem Messen habe ich herausgefunden, dass während diesen 4500 Millisekunden nur 250 Millisekunden für die eigentliche Simulation abläuft; der Rest geht auf die Kappe von Simbad, das 4250 Millisekunden für 6 Initialisierungen gebraucht hat. Deshalb habe ich das Framework jetzt so erweitert, dass ich beliebig Roboter hinzufügen und entfernen kann. Es reicht nun aus eine Simulationsumgebung zu initialisieren; dann kann man sie immer wieder verwenden. Was jetzt noch fehlt ist, dass die Quader in der Umgebung ab und zu neu organisiert werden können, damit die Roboter sich nicht auf eine bestimmte Umgebung spezialisieren.

Labyrinth Bots — technische Umsetzung

Nachdem ich meine Zielsetzung definiert hatte, habe ich mir Gedanken zur Umsetzung des Experimentes gemacht. Eine Simulation für neuronale Netze und ein Evolutionsframework habe ich bereits in Java geschrieben, deswegen habe ich mich entschieden auch dieses Projekt mit Hilfe von Java umzusetzen.

Um den Roboter in seiner physikalischen, dreidimensionalen Welt zu simulieren, habe ich mich für Simbad entschieden, da es die nötigen Tools wie Entfernungsmesser und Physikengine in einer 3D-Welt bereits bereitstellt und nebenbei noch recht schnell ist.

Um die Berechnungen der Fitness der Roboter zu beschleunigen habe ich außerdem noch ein kleines Client-Server System entwickelt, mit dem ich Rechenaufgaben auf andere Computer im Netzwerk auslagern kann.

Ausgestattet mit diesen neuen Werkzeugen konnte ich mit meinen Experimenten beginnen.

Labyrinth Bots — Zielsetzung

Nachdem ich meine Arbeit zum Thema neuronale Netze abgeschlossen hatte, wollte ich mich näher mit evolutionären Verfahren in Kombination mit neuronalen Netzen beschäftigen. Als erstes „kleineres“ Ziel habe ich mir gesetzt einen Roboter in einer physikalisch einigermaßen korrekten, dreidimensionalen Umgebung dazu zu bringen, dass er sich in einem Labyrinth zurechtfindet, nicht gegen die Wände läuft und zumindest versucht einen Ausgang zu finden (den Anspruch auf die Erfolgreiche Befreiung aus dem Labyrinth lasse ich zunächst in Klammern).

Labyrinth BotDer Einfachheit halber ist der Roboter rund und hat 20 Entfernungssensoren mit einer Reichweite von 1,5 Metern.

Als „Gehirn“ ist ein vollverknüpftes neuronales Netz vorgesehen. Es gibt 22 Eingabeneuronen; 20 für die Entfernungssensoren und 2 für einen Beschleunigungssensor jeweils in X und Z Richtung. Dazu gibt es 2 Ausgabeneuronen, jedes für eins der Antriebsräder. Die Anzahl der restlichen Neuronen soll im Verlauf der Evolution variieren können.

Künstliche neuronale Netze

Wie hier bereits beschrieben, interessiere ich mich unter anderem auch sehr für künstliche neuronale Netze. Das sind sehr abstrakte Modelle der biologischen neuronalen Netze wie sie beispielsweise im Hirn des Menschen zu finden sind, mit denen man, nachdem sie in einige Zeilen Programmcode gefasst wurden, am Computer fabelhafte Dinge anrichten kann. In vielen Bereichen werden diese neuronalen Netze bereits angewendet wie zum Beispiel in der Bilderkennung.

Deshalb habe ich mich schon im letzten Jahr im Rahmen einer umfassenden Schularbeit mit dem Thema theoretisch und praktisch auseinandergesetzt. Der schriftliche Teil, der eine kleine Einführung zu den neuronalen Netzen und eine Beschreibung meines Praktischen Teils enthält ist hier einzusehen.