Nachmittag in Dartmoor

Heute Nachmittag war ich nochmal kurz mit der Kamera Unterwegs:
Nachmittag in Dartmoor

Auslandsjahr in England

Vor ungefähr zwei Wochen hat ein weiteres Langzeitexperiment begonnen. Ich arbeite für ein Jahr in England als Freiwilliger in einer Jugendherberge die sehr abgelegen in Dartmoor im Südwesten Englands liegt. Darüber zu schreiben ist mir wahrscheinlich zu aufwändig aber ich versuche in regelmäßigen Abständen Bilder hier zu veröffentlichen. Die Rechte an allen Bildern sind zunächst bei mir. Wer eins verwenden möchte kann mich aber gerne fragen.

Die ersten Paar Bildergalerien sind hier zu finden:

• Hinflug
• Tag in Dartmoor (1)
• Meine Gemächer
• Tag in Dartmoor (2)

Raumbestimmung per W-Lan

Die zunehmende Popularität von Routern mit W-Lan Funktion hat dazu geführt, dass besonders im Urbanen Umfeld innerhalb eines Gebäudes mehrere W-Lan Netzwerke aufgespürt werden können. Jedes dieser Netzwerke hat eine einzigartige ID (die MAC Adresse) anhand der es identifiziert werden kann. Die Signalstärke dieser Netzwerke schwankt — basierend auf einigen Umweltfaktoren wie z.B. die Entfernung zur Basisstation, die Anzahl und Beschaffenheit der Wände die zwischen dem Computer und der Basisstation liegen (besonders Feuchtigkeit spielt eine Rolle) etc.

Das führt dazu, dass die Anzahl und die Signalstärke der W-Lan Netzwerke in jedem Raum unterschiedliche Charakteristika aufweist anhand derer jeder Raum erkannt werden kann. So kann man ohne zusätzliches Equipment (eine W-Lan Karte vorausgesetzt) eine erstaunlich gute Raumbestimmung realisieren, die sich auf die Funkabdeckung per W-Lan stützt.

Diese Anwendung umzusetzen hatte ich Zeit nach meinem Abitur im Juni.

Die Unterscheidung der Räume erfolgt über ein feed forward Multilayer Perceptron mit der Architektur (AnzahlBekannterNetzwerke)-15-5-2. Das MLP hat für jedes bekannte Funknetzwerk ein Eingabeneuron, welches immer mit der aktuellen Signalstärke gefüttert wird. Sollte ein Netzwerk temporär nicht verfügbar sein (manche Netzwerke mit schwacher Signalstärke sind z.B. nur einzelnen Räumen zu empfangen), wird das entsprechende Eingabeneuron mit der geringstmöglichen Signalstärke versorgt. Wie vielleicht schon aufgefallen ist hat das MLP nur zwei Ausgangsneurone. Das hängt damit zusammen, dass ein MLP immer nur zwischen zwei Räumen unterscheiden kann. An dem Versucht einem MLP mehr als zwei Räume beizubringen bin ich leider gescheitert. Deshalb verwende ich mehrere MLP’s, die im KO-System entscheiden um welchen Raum es sich handelt.

25 Trainingsbeispiele pro kartografiertem Raum haben Sich als ideal erwiesen. Bei der doppelten Menge wurden die MLP’s nicht ordentlich Trainiert. Konkret bin ich mit meinem Laptop durch die zu kartografierenden Räume gegangen und habe sie einzeln „gescannt“. Dabei beeinflusst das „wie“ sehr stark die spätere Erkennungsrate der Räume. Die schlechtesten Ergebnisse habe ich erhalten als ich durch die Räume gelaufen bin um auch in wirklich jedem Winkel die Netzwerke zu erfassen. Anfangs dachte ich zwar, dass so die Räume besser voneinander abgegrenzt werden können aber letztlich wurden wahrscheinlich dadurch die Trainingseingaben für einen Raum so unterschiedlich, dass sie für das MLP schwer zu erlernen waren. Daraufhin habe ich das ganz gegenteilige Extrem ausprobiert (in der Hoffnung, dass einfachere Trainingsdaten besser gelernt werden) indem ich für den Scan für 25 Trainingsbeispiele das Laptop einfach in die Mitte des Raumes gehalten habe. Damit waren schon wesentlich bessere Erkennungsraten möglich; das System war aber noch lange nicht zufriedenstellend. Erst eine Mischung aus beiden Methoden hat gute Erkennungsraten ermöglicht. Dafür habe ich mich in einem Radius von ca. 2m um das Zentrum des jeweiligen Raumes bewegt. Dadurch waren die Trainingsdaten weder vollkommen Einseitig noch allzu komplex. Links abgebildet ist die Erkennungsqualität an Verschiedenen Orten in den kartografierten Räumen (ein Klick macht es größer). Ich habe an jedem Punkt 5 Messungen gemacht und jeweils die Anzahl der erfolgreichen Messungen eingetragen. Das ist zwar nur eine sehr grobe Messsicherheit, aber ich hatte nicht mehr Zeit und auch nicht mehr Lust (irgendwann wird so ein Laptop auch schwer). An den Türen und in der Nähe des Bücherregals sinkt die Genauigkeit leicht, bleibt aber stets über 50%iger Genauigkeit. Insgesamt bin ich mit der Genauigkeit von ca. 89,4% recht zufrieden.

Ein Sonderfall entsteht, wenn man das Laptop auf dem Boden und nicht (so wie auch bei den Scans vorher aufgezeichnet) in Brusthöhe versucht zu lokalisieren. Teilweise bleiben die Messwerte gleich; teilweise (wie z.B. oben links im Raum) sinkt aber die Erkennungsrate stark. Anscheinend spielt die Höhe eine recht große Rolle.

Zu überprüfen bleibt jetzt noch wie sich das System mit noch mehr als nur vier Räumen verhält.

Die Software habe ich in Java geschrieben, für die Neuronalen Netze habe ich die einfach zu bedienende und recht flotte Bibliothek „Snipe“ von David Kriesel benutzt. Um an die W-Lan Daten zu kommen habe ich (da ich ein Macbook benutze) den Befehl „airport -s“ mit dem ProcessBuilder verwendet weil Java diese Funktion leider nicht zur Verfügung stellt. Deshalb ist die Software auch noch nicht platformunabhängig. Da sie auch noch nicht ganz für den Endbenutzer fertig ist stelle ich sie hier nicht zum Download bereit. An Interessierte verschicke ich sie gerne samt Quellcode per Email. Vielleicht entsteht dann ja auch eine Version für Linux & Windows. Bei vielen Interessierten werde ich sie auf jeden fall bequemer zu bedienen machen.

Telefon als Nummernfeld

Während der letzten Weihnachtsferien habe ich durch diesen Kommentar auf hackaday.com inspiriert ein altes Telefon (PTT Typ T65 de Luxe Smaragt von Ericsson von einem Niederländischen Flohmarkt, das Modell entspricht ungefähr einem FeTap 611) mit meinem Arduino verdrahtet und ein kleines Sketch geschrieben um die Impulse zu zählen, die von der Wählscheibe beim Wählen kommen.

Die Schaltung gestaltet sich denkbar einfach; die Wählscheibe verhält sich nicht anders als ein Schalter, der ein und aus geht. SerialServer von Dan O’Sullivan und ein kleines Java Programm, das sich mit dem Server verbindet um den Tastendruck zu simulieren machen das Telefon zu einem (fast) vollständigen Nummernfeld, das unabhängig von der aktuellen Anwendung mit der es genutzt werden soll funktioniert (AAC Keys hätte es auch getan, läuft aber nicht auf Linux soweit ich weiß).

Natürlich wäre es noch besser gewesen eine USB-Tastatur zu simulieren, aber dann währe warscheinlich ein USB-Shield für mein Arduino notwendig gewesen und das wäre mir zu viel Aufwand.

Hier eine kurze Demonstration:

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.