killerschafs blog

Heyho

hier ist lange nichts passiert. Das liegt zum Einen an meinem zweiwöchigen USA-Aufenthalt und zum Anderen am schönen Wetter draussen.

Dennoch: Die nächsten Schritte sind klar: Tracking der Fahrbefehle, Ansteuern von bestimmten Koordinaten, Rekalibrierung der durch die Akkumulation kleiner Fehler entstehenden Koordinatendifferenzen.

Die ersten beiden Punkte sind einfach, der letzte nicht.

Bisher wurde der Kyosho nur mit der originalen Fernbedienung gesteuert. Das Tracking des Fahrzeugs wurde ausschließlich über die Webcambilder gemacht. Dieses Verfahren allein ist, wie wir gesehen haben, nicht sonderlich geeignet um allein die Positionserfassung zu ermöglichen. Damit das Fahrzeug autonom fahren kann, muss der PC es steuern können. Die Steuerungsinformationen des Fahrzeugs können genutzt werden das bisherige Tracking zu ergänzen. Doch wie kann ein handelsüblicher PC ein RC-Fahrzeug steuern?

Möglichkeit 1. Auf das Fahrzeug kommt ein Mikrokontroller, der über WLAN ansprechbar ist und die Servomotoren mit gängiger PWM (Pulsweitenmodulation) anspricht. Dagegen spricht: Eine ähnliche Variante hatten wir bereits mit dem ersten LEGO-Auto. Letztlich muss das Auto viel zusätzliche Hardware transportieren und mit Strom versorgen. Eine TCP/IP Kopplung ist für Echtzeitanwendungen auch nicht unbedingt prädestiniert. Diese Variante scheidet also aus.

Möglichkeit 2. Man nutzt die vorhandene Fernbedienung, und bringt sie dazu das zu senden, was man möchte. Wie tut man dies? Ich habe absichtlich eine billige Fernbedienung gekauft, in der Hoffnung, die verbaute Technik ist simpel. Und das ist sie auch. Die Fernbedienung ist ein 40MHz  FM Sender. Gesendet wird ein sogenannter PPM-Code. Dies steht für Pulse Position Modulation. Über die Länge von Pausen zwischen zwei Impulsen werden die einzelnen Kanäle (und somit Servostellungen) sequentiell über eine 40MHz Frequenz gefunkt. Die Impulse selbst sind immer gleich lang. Synchronisiert wird über eine überlange Pause am Anfang/Ende der Sequenz. Ein Frame ist dabei ca 20ms lang.

 Hierbei ist zu beachten: In der Literatur findet sich auch eine andere Beschreibung von PPM. Hier wird über die Länge von Pulsen moduliert, ein überlanger Startpuls dient als Synchronisation und die Abständer zweier Pulse ist immer gleich. Diese beiden Beschreibungen sind identisch, wenn man Puls und Pause vertauscht.

Jeder, der schon einmal eine Windows/Linux-Anwendung programmiert hat und versucht hat dabei einen Timer zu verwenden, der Millisekundengenau auflöst und dabei kläglich gescheitert ist, wird sich jetzt fragen: Wie soll so etwas funktionieren? Gängige Timer unter Windows/Linux lösen nur 16ms auf. Weiterhin kann das Multitasking einem einen Strich durch die Rechnung machen, in dem es einfach mal einen Prozess ein paar Millisekunden aussetzen lässt. Die Lösung ist dennoch denkbar einfach: Man nimmt die Soundkarte! Eine Soundkarte feuert bei einer Samplingrate von 44.1kHz (CD-Qualität) 44100 Samples in einer Sekunde auf die Lautsprecher. Dabei sind die Soundkarten bestrebt, dies so gut wie möglich zu machen, damit einem beim Hören einer CD nicht die Ohren abfallen. Ein PPM-Frame umfasst etwa 20ms. In 20ms kann eine Soundkarte bei CD-Qualität 20ms*44.1Samples/ms = 882 Samples losschicken.  In diesen 882 Samples kann ich nun meine Kanäle modulieren. Für einen Kanal steht etwa 1ms zur Verfügung, dies entspricht damit 44.1 Stufen pro Kanal. Dies ist nicht sonderlich gut, aber ausreichend und vor allem in Echtzeit und ohne zusätzlichen Hardwareaufwand. Also wurde die Fernbedienung kurzerhand auseindergebaut und das PPM Signal auf einem Oszilloskop betrachtet. Dann wurde dieses Signal über die Soundkarte nachgebaut.

Intern habe ich DirectX, bzw genauer XAudio2 (Nachfolger von Direct Sound) verwendet und einen PPM-Frame mit einer Streamingvariante über zwei abwechselnde Audiobuffer abgespielt. Soweit so gut, man kann also PPM über eine Soundkarte ausgeben. Hören kann man das somit natürlich auch. Aber wie kommt das Signal nun zum Auto? Die FM-Modulation auf die 40MHz Trägerfrequenz übernimmt weiterhin die Fernbedienung. Hierzu musste man lediglich kurz vor der Hochfrequenzeinheit der Fernbedienung das Signal der Soundkarte einspeisen. Damit ich meine Fernbedienung nicht gleich vernichte, hat mein Vater wieder einmal den Lötkolben geschwungen und nun hat meine Ansmann W3 Fernbedienung eine Stereobuchse bekommen. Musik sollte man hier jedoch nicht einspielen, das Auto interpretiert diese Signalfolgen nämlich ebenfalls als PPM und versucht dann zur Musik passend zu tanzen!

In den letzten Wochen habe ich hier nicht viel geschrieben. Dies hole ich jetzt hiermit nach. Was ist geschehen?

Es wurden einige Versuche gemacht, die Fahrzeugbewegungserfassung mit Hilfe des optischen Flusses zu verbessern. Ich habe hierzu noch das ein oder andere Paper gelesen, welche allesamt vielversprechend klangen, aber in der Praxis kaum eine Verbesserung brachten. Optischer Fluss bleibt immer eine Schätzung. Eine präzise Ableitung einer Bewegung kann nicht alleine mit optischem Fluss realisiert werden. Die Ergebnisse, die es in der Praxis gibt, sind allerdings bereits in der Horn/Schunk Variante so gut, dass die bisherigen Paper, die ich gelesen und teilweise implementiert habe, diese kaum verbessern können. Daher bleibe ich bei dieser Variante, nicht zuletzt weil sie die einfachste Variante ist.

Folgende Versuche wurden unternommen um die Verfolgung zu optimieren:

•  Ein Wohnungsmodell wurde auf Basis eines vorhandenen Grundrisses erstellt. In das Modell wurden absichtlich keine Möbelstücke eingezeichnet, da dies erstens zu viel Aufwand ist, und zweitens sich diese Möbelstücke zum Teil zu verschiedenen Zeiten an verschiedenen Orten befinden können (z.B. Stühle, Couchtisch etc). Berechnet man nun ein Tiefenmodell dessen, was das Modellfahrzeug in der Modellwohnung sehen müsste, so kann man die gewonnenen Tiefen mit dem Tiefenbild der Webcam vergleichen. Da in dem Modell allerdings die Möbel fehlen, so hat man es selbst bei einer perfekten Tiefenberechnung der Webcambilder immer mit Abweichungen zwischen Modell und Wirklichkeit zu tun. Eine Situation kann hiermit jedoch halbwegs sinnvoll verbessert werden: Sieht das Fahrzeug mit der Webcam z.B. eine Tiefe von 4m in der Mitte des Bildes, und zeigt das Modell eine Tiefe von 3m an dieser Stelle, so muss das Fahrzeug eine Korrektur nach hinten erfahren. Andersherum gilt dies nicht, da Möbelstücke einen geringeren Tiefeneindruck als die des Modells bewirken. Einen weiteren Vorteil durch das Modell hat man: Das Fahrzeug kann nicht durch Wände fahren. Fährt das Modell durch eine Wand so kann hier vorher eingegriffen werden und das Modell seitlich verschoben werden, in die Richtung, die besser zu dem Tiefenbild der Webcam passt. In der Praxis führt dies zu Sprüngen des Fahrzeugs innerhalb seiner 3D-Welt. Allerdings können somit auch längere Fahrten gemacht werden, ohne dass sich das Fahrzeug völlig verirrt. Dies kann natürlich nie ausgeschlossen werden, denn die korrigierenden Eingriffe sind einfachster Natur und können die Situation durchaus auch verschlechtern.

• Reifentracking. Da der optische Fluss eine Schätzung ist und das zu Grunde liegende Material beliebig komplex sein kann, habe ich versucht das zu Grunde liegende Bildmaterial zu vereinfachen. Die Kamera wurde auf die Vorderreifen des Modells ausgerichtet. Der optische Fluss des Stollenprofils der Reifen sollte Testweise genutzt werden um die Fahrzeugbewegung zu verfolgen. Das Tracking gelingt auf Anhieb erstaunlich gut. Der Fluss des Stollenprofils der Reifen ist gut geeignet um verschiedene Geschwindigkeiten und Lenkeinstellungen präzise zu ermitteln. Leider gibt es bei diesem Verfahren ein Problem. Überschreitet das Fahrzeug eine bestimmte Geschwindigkeit kehrt sich der optische Fluss des Stollenprofils um und das Fahrzeug invertiert seine Geschwindigkeit. Dies ist ein Phänomen, welches wohl jedem Zuschauer von Glücksrad bekannt sein dürfte. Die optische Wirkung der Drehrichtung kehrt sich bei hohen Geschwindigkeiten plötzlich um. Leider liegt diese Kipp-Geschwindigkeit hier bereits bei 1/3 der maximalen Geschwindigkeit des Fahrzeugs. Des weiteren geht sehr viel Bildeindruck verloren, da die Reifen einen Großteil des Bildes einnehmen. Aus diesen Gründen wurde dieses Verfahren nicht weiter verfolgt.

Wieder mal was Neues. Gestern habe ich mich mal ein wenig in die Konzepte von Rechnen auf der Grafikkarte eingearbeitet. Und ich bin fast vom Stuhl gefallen.... Meine schon 1 1/2 Jahre alte GeForce 8800 GTS stellt mein Core2Duo mit 3GHz sowas von in den Schatten, das ist schon erstaunlich. Habe den Optischen Fluss Algorithmus nun auf der GPU implementiert. Vorher waren etwa 5 Iterationen pro Bild in Echtzeit möglich (wenn man nicht die gesamte CPU blockieren wollte). Die vorherige Version lief auf einem 1/25 großen Originalbild (5x5 Blöcke). Die jetzige Version auf der GPU läuft auf 128 Cores parallel und schafft auf den nicht verkleinerten Bildern etwa 200 Iterationen. Die Dinger sind echte Rechenmonster.

Viel besser werden die Ergebnisse zwar nicht, aber dafür hat man mehr CPU Power für andere Dinge übrig. Ich werde sie versuchen weise einzusetzen :-)

Für einen autonomen Roboter ist es unbedingt notwendig, eine echtzeitfähige Hinderniserkennung zu nutzen. Die Aufgabe ist also aus einem Bild, oder aus einer Sequenz von Bildern für jeden Bildpunkt eine Tiefe abschätzen zu können. Es gibt zahllose Ansätze und Paper, die diese Aufgabe versuchen zu erfüllen. Eine große Anzahl an Papern bedeutet allerdings nicht, wie man hoffen könnte, dass es zahllose Algorithmen gibt, die diese Aufgabe zufriedenstellend erfüllen können. Das Gegenteil ist der Fall. Je mehr wissenschaftliche Paper es zu einer Problemstellung gibt, desto eher versagen alle darin vorgestellten Algorithmen in der Realität. Warum? Angenommen jemand findet eine ganz hervorragende Lösung für eine Problemstellung, welche sehr akkurate Ergebnisse in Echtzeit ermittelt. Dann gäbe es keinen Forschungsbedarf mehr für diese Aufgabenstellung. Dann gäbe es aber auch keine neuen Paper mehr zu dieser Aufgabe.

Das Schlimme an der Vielzahl der Paper ist: Ein Author eines Papers würde nie einen Algorithmus vorstellen um hinterher im Ergebnisteil seines Papers zu schreiben, dass der Algorithmus totale Grütze ist, eine gigantische Rechenzeit benötigt und die Ergebnisse nur unter Laborbedingungen brauchbar sind.

In der Informatik lernt man, dass manche Problemstellungen einfach so schwierig sind, dass man keine brauchbare Lösung finden kann, wenn man die Aufgabenstellung nicht spezialisiert. Es ist in der Regel einfacher einen Algorithmus für ein spezielles Problem zu schreiben, als einen Algorithmus für ein Allgemeines. So bin ich nach dem Studium einiger Paper und der Implementierung eines der vielversprechensten Paper (welches grandios versagt hat!) dazu gekommen, mir eine eigene Lösung auszudenken. Wenn man nicht alles selber macht....

Zunächst gilt, dass das Fahrzeug den Boden vor sich sieht. Jetzt kann man davon ausgehen, dass alles, was sich direkt vor dem Fahrzeug befindet kein Hindernis ist, da das Fahrzeug ja grundsätzlich nicht vor ein Hindernis vorfahren soll. Also liegt es nahe, dass alles, was ausgehend vom Fahrzeug so aussieht, wie das, was sich direkt vor einem befindet, Boden und somit kein Hindernis ist. Welche Informationen kann man verwenden um die Ähnlichkeit zweier Elemente im Bild zu vergleichen? Die Auswahl der Informationen wird Feature genannt. Verwendet werden folgende Features:

• Änderung einzelner Farbkanäle (,,)
• Änderung von Farbton, Farbsättigung und Farbhelligkeit (,,)
• Änderung der Texturenergien ( mit  Helligkeitsinformationen und Laws Texturmasken, )

Die eingeführten Funktionen und Abkürzungen bedeuten folgendes:

• Rotkanal, Grünkanal,  Blaukanal 
• Farbton (Hue), Sättigung, Helligkeit (Value)
•  Helligkeitsinformationen, Laws Texturmasken (Dies sind kleine Masken, mit denen man ein Bild falten kann, um entsprechende Merkmale des Bildes feststellen zu können.
• ist die Umgebung um die Polarkoordinaten
• Texturenergie

Das hier verwendete Koordinatensystem ist ein Polarkoordinatensystem. Es werden letztlich Strahlen vom Bodenursprung ( Kartesisch) in einem Kreisförmigen Bogen verfolgt. Sollten sich auf dem Strahlenweg obige Constraints zu stark ändern, so hat man ein Hindernis gefunden. Die Länge des Strahls entspricht dabei der approximierten Entfernung. Die Strahlgeraden ergeben sich dabei durch

Und hier wie gewohnt das zugehörige Video...