Pixel Clustering

Im Moment studiere ich mit meiner Schulklasse ein Theaterstück ein (,,Wie es euch gefällt” von William Shakespeare), so dass ich während den Szenen, in denen ich nicht mitspiele viel Wartezeit habe, während der ich nichts zu tun habe. So kam ich zu folgendem Gedankenexperiment, dass ich noch am selben Tag in die Tat umgesetzt habe.

Ich habe mich gefragt, was wohl passiert, wenn man jeden Pixel eines Bildes als Punkt in einem fünfdimensionalen Raum ansieht. Dabei sind die ersten beiden Koordinaten die x- und y Koordinaten des Pixels im Bild selber und die letzten drei Koordinaten ergeben sich aus den RGB-Werten des Pixels. Ein Pixel an der Stelle x=7 und y = 23 mit der Farbe R=55, G=88, B = 180 hat ist also ein Punkt im fünfdimensionalen Raum: P(7|23|55|88|180).

Wenn man dann alle Pixel eines Bildes in Punkte umwandelt erhält man also Punktwolken im fünfdimensionalen Raum, die man mit einem einfachen Clusteringverfahren zusammenfassen kann. Wenn man das tut und die so als ,,zusammenhängend” erkannten Pixel gleichfarbig einfärbt, so dachte ich mir, müssten doch ganz nette Bilder entstehen.

Nach der Umsetzung bestätigte sich das auch:

Ich habe die Bilder direkt von meiner Webcam genommen, leider ist an ein in Echtzeit berechneter Effekt  nicht umsetzbar, da es sehr lange dauert, bis der Clustering-Algorithmus bei so vielen Bildern sehr lange zum terminieren braucht. Wer an dem Programm interessiert ist, kann gerne mit mir in Kontakt treten. Es ist in Java geschrieben und dadurch einigermaßen plattformunabhängig.

Biologisch motiviertes Training neuronaler Netze

Schon vor längerer Zeit habe ich mir Gedanken darüber gemacht, wie man neuronale Netze ,,biologischer” trainiert.

Gegeben sei dazu ein neuronales Netz mit folgender Topologie:

Es gibt mehrere Schichten, die untereinander vollverknüpft sind, genau wie bei einem Multilayer Perceptron (blaue Verknüpfungen). Jedes Neuron übergibt während jedem Simulationsschritt seine Aktivierung — über eine gewichtete Verbindung (rot) — an jedes Gewicht weiter (aus Gründen der Übersicht habe ich das linke Gewicht mit seinen Verknüpfungen ausgelassen).

Während jedem Zeitschritt werden dann die einkommenden Aktivierungen in jedem Gewicht verarbeitet, indem alle Aktivierungen aufsummiert werden und dem Gewicht aufaddiert werden (es folgt daraus, dass die roten Verbindungen sehr schwach sein müssen, damit die Gewichtsveränderungen in den blauen Verbindungen nicht zu hoch sind).

Das Netz mit den roten Verbindungen ist also das ,,Lehrernetz”, das Netz mit den blauen Verbindungen ist das ,,Schülernetz”. Die beiden Netze teilen sich die Neuronen, haben aber eigene Verknüpfungen. Die Gewichte des Lehrernetzes müssen jetzt nur noch so verändert werden, dass sie in der Lage sind das Schülernetz zu trainieren. Das könnte mit einem evolutionären Algorithmus herbeiführen.
Jeweils ein Organismus besteht aus einem Lehrer- und einem Schülernetz. Zur Berechnung der Fitness werden zunächst die Gewichte des Schülernetzes zufällig initialisiert. Die Aufgabe des Lehrernetzes ist es dann dem Schülernetz ausgewählte Probleme beizubringen. Je nachdem wie gut das Schülernetz nach einer bestimmten Zeit oder Anzahl von Simulationsschritten im Lösen der Aufgabe ist, wird der Organismus bewertet. Die zu lehrenden Probleme müssen natürlich zunächst einfach sein und dürfen nicht zu ,,spezifisch” oder zu ,,schwer” werden.

Eine mögliche Erweiterung könnte sein, zwischen jedes Neuron des Schülernetzes und jedes Gewicht des Schülernetzes (die ja durch das Lehrernetz verbunden sind), ein Neuron zu platzieren, dass allein dem Lehrernetz vorbehalten ist. Dadurch ist das Lehrernetz ,,schlauer”.

Hier gibt es eine ausführlichere Version der obigen Grafik.

Anlass für diesen Artikel war übrigens dieser Thread im Board von David Kriesel

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.

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.

Helle Stelle im Bild ohne Pixelreduktion.

Helle Stelle im Bild mit Pixelreduktion.

Mit einer kleinen LED Taschenlampe kann man jetzt direkt in die Luft malen.

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

Wie 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

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).

Der 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.

Hello world!

Dass ich vor ungefähr zwei Stunden in meinen gespeicherten ICQ Unterhaltungen über ein Experiment gelesen habe, das ich vor einem halben Jahr durchgeführt und interessant gefunden habe, aber zu Gunsten eines anderen Experiments “verschoben” und anschließend vergessen habe, hat mich zunächst an meiner Merkfähigkeit zweifeln lassen und anschließend dazu bewegt ein(en) Blog einzurichten, in dem ich für mich Experimente aufzeichnen und ggf. wieder finden kann. So ist also dieser/dieses Blog entstanden. Ein weiterer Grund meiner Entscheidung war natürlich auch meine Hoffnung, dass durch die Kommentarfunktion Anregungen, Tipps oder Diskussionen entstehen, die meine Beiträge ergänzen.