Landmarkenerkennung [WEISSABGLEICH]

[vohopri]

Hallo,

Nachdem meine Bahnsteuerung schon zufriedenstellend funktioniert, will ich nun einen weiteren Baustein fürs autonome Navigieren erarbeiten:

Die Landmarkenerkennung auf Kamerabildern.

Die Landmarken stelle ich aus farbiger Folie her. Und für die Analyse der Kamerabilder habe ich mir wieder ein kleines GUI erstellt, wo ich die Teilschritte der Analyse und den Gesamtprozess komfortabel testen kann.

http://www.jbergsmann.at/screen1.GIF

So schauts ungefähr aus - vorerst zumindest. Die Rasterung ist im Original nicht vorhanden, die entsteht durch die Kompression, die ich vornehme, um mit dem Webspace wirtschaftlich umzugehen. Erst wurde die blaue Scheibe gesucht, anschliessend die gelbe:

http://www.jbergsmann.at/result2.GIF

Im Original ist das Bild der Webcam jpg komprimiert und hat eine Qualität, dass ich am Bildschirm keine Artefakte sehe. Die Qualität ist recht gut, aber erfahrungsgemäss stark Beleuchtungsabhängig.

Für die Analyse wird das Bild intern als Bitmap repräsentiert.

Im ersten Schritt habe ich mal zwei Folienscheiben in Nahaufnahme aufgenommen. Da geht alles noch seehr einfach. Das wird sich noch ändern.

Mal sehen, was ein geeigneter nächster Schritt wäre:

grüsse,
Hannes

[vohopri]

Hallo,

Bei der Programmiererei hab ich mich schwer verkalkuliert: In Wirklichkeit ist es viel schneller gegangen, als vermutet. Das darf auch mal sein.

Clustern und Mitte Finden geht schon brauchbar:

http://www.jbergsmann.at/result4-cluster-center.gif

Jetzt brauch ich als Nächstes mehr und bessere Testdaten.

grüsse,
Hannes

[vohopri]

Ok,

Testdaten liefert mir die Webcam.
http://www.jbergsmann.at/Bild%20002.jpghttp://www.jbergsmann.at/Bild%20003.jpghttp://www.jbergsmann.at/Bild%20004.jpg

Die Beleuchtung ist sehr unterschiedlich:
Energiesparlampe, Baustrahler, Tageslicht

Objektdurchmesser 94 mm, Entfernung 2000 mm, Weitwinkel.

Das alles sollte die Markierungserkennung OHNE Parameteranpassung verkraften. Das Kunstlicht ist sehr gelb und das Tageslicht ist durch Laubbäume vor dem Fenster stark grün gefärbt.

http://www.jbergsmann.at/result4-gruen-dunkel-260809.GIFhttp://www.jbergsmann.at/result4-gruen-hell-260809.GIFhttp://www.jbergsmann.at/result4-gruen-tali-260809.GIF

Unter allen 3 Bedingungen wurde die Markierung mit den selben Verarbeitungsparametern sicher erkannt. Weissabgleich und Belichtungsautomatik kommen später. Jetzt gehts zuerst um die Optimierung der Algorithmen.

Mein erster Eindruck ist, dass Farbscheiben leichter zu erkennen sind, als LEDs. Diese Vermutung werd ich noch weiter verfolgen.

grüsse,
Hannes

[jcrypter]

Guten Morgen,

beeindruckendes resultat! Finde ich.

Hast Du die Algorithmen zur Erkennung alle selber entwickelt oder hast Du da auf vorhandenes zurückgegriffen?

Beeindruckend... so oder so!

Gruß,
Crypi

[vohopri]

Hi Crypi,

Mich hats auch beeindruckt. Ich halte das für einen viel versprechenden Weg zur Navigation.

Der Algo oben ist selber ausgesucht, aus den wenigen Dingen der Mathematik, die ich verstehe.

Ich verwerfe die dunkelsten und die hellsten Partien des Bildes und erhebe dann die Cosinusse zwischen den Pixelvektoren und dem Kriteriumsvektor im RGB Raum. Das scheint sehr ähnlich zu sein mit einer Korrelation der Farbkomponenten.

Zur Zeit bin ich noch am Experimentieren mit unterschiedlichen Algorithmen.

grüsse,
Hannes

[Willa]

hi Hannes,

erhebe dann die Cosinusse zwischen den Pixelvektoren und dem Kriteriumsvektor im RGB Raum
Könntest du das mal mit ganzganz einfachen Mitteln erklären...? Klingt so kompliziert... Aber vielleicht könnte mir das für mein Projekt Denkanstösse geben. LEDs sind zwar schön und gut, aber mit Farbmarkern würde ich auch gerne mal experimentieren. Aber was sind nur Pixelvektoren und ein Kriteriumsvektor im RGB-Raum...?

[Nighthawk]

Hallo,

ich bin zwar nicht der Angesprochene, aber ich antworte mal, ich hoffe das ist ok?:

Ich habe mich nicht mit dem Thema beschäftigt, aber ich gehe davon aus, dass er jedem Pixel im Bild einen rgb-Wert zuordnet. Also jeweils eine Zahl zwischen 0-255 für Rot, Grün und Blau. Fasst man nun jede dieser Farben als eine Dimension auf, so kann man jeder Farbe im rgb-Raum einen Punkt im Dreidimensionalen Raum zuordnen (x entspricht also Rot, y entspricht Grün und z entspricht Blau). Zu diesem Punkt gibt es dann auch noch einen Ortsvektor, also der Vektor, der vom Nullpunkt zum betreffenden Punkt zeigt. Diese Vektoren nennt er Pixelvektoren.

Der Kriteriumsvektor wird wohl die Farbe sein, die er erkennen will, also zB Grün. Also sucht er sich den rgb-Wert der gewünschten Farbe und erhält wie oben beschrieben den zugehörigen Ortsvektor, den er Kriteriumsvektor nennt.

So und wie bestimmt er nun, dass die Farbe eines Pixels der Kriteriumsfarbe ähnlich sind? Er bestimmt den Winkel zwischen dem Pixelvektor und dem Kriteriumsvektor. Je kleiner dieser ist, desto ähnlicher sind die Farben. Wie bestimmt man einen Winkel zwischen zwei Vektoren? Das geht zum Beispiel über das Skalarprodukt, das u.a. folgende Eigenschaft hat: | a*b|=|a|*|b|*cos(winkel) (wobei a und b vektoren sind).
Als netter Nebeneffekt ist die Helligkeit des Bildes vollkommen irrelevant, da die Helligkeit nur die Länge eines Vektors bestimmt, nicht seine Ausrichtung.

@vohopri: Ich hoffe, dass ich es richtig erklärt habe?!

@Willa: Alles verstanden? Wenn nicht, bitte nachfragen :-)

MfG
Nighthawk

[vohopri]

Hi William, hi hawk,

sorry für die etwas zu knapp geratene Beschreibung: aber die Erklärung von nighthawk passt, danke dafür.

Die Kameraframes liegen meist als bitmaps vor, oder man kann sie sich in ein Bitmap umwandeln. Am komfortabelsten ist das 24bit Format. Da sind die Farben schon getrennt. Die Bitmap ist eine Matrix, die die Farbbytes blau grün rot für alle Bildpunkte zeilenweise von links oben nach rechts unten enthält. Die drei Farbwerte eines Pixels kann ich als Vektor auffassen und die drei Farbwerte vom Kriterium ebenfalls. Zwischen 2 Vektoren kann ich verschiedene Beziehungen herstellen, indem ich die Vektorrechnung zu Hilfe nehme. Der Winkel - oder besser der Cosinus des Winkels zwischen den Vektoren ist ein Ähnlichkeitsmass. Mein Kriterium sei hellgrün: $00,$FF,$00 sind die Farbbytes. Wenn das Pixel dunkelgrün ist ($00,$80,$00), dann ist der cos gleich 1. Usw. bei mehr Erklärungsbedarf kann ich auch mehr dazu schreiben. Im Endeffekt wird man den quadrierten Cos nehmen, da das dann das Wurzelziehen erspart.

Dass der Winkel zwischen den Farbvektoren unabhängig von der Helligkeit ist, wurde schon gesagt. Das macht das Verfahren vollkommen unabhängig von der Beleuchtungsstärke. ABER das ist ein Falle. Ein unscheinbares Holzbrett im Schatten, das auf dem Bild schwarz erscheint, kann dunkelorange sein und ist nach dem Farbwinkel von der hellorange leuchtenden Markierungsscheibe so nicht unterscheidbar. Darum kombiniere ich den Farbwinkel immer mit dem Verwerfen der hellsten und der dunkelsten Bildpartien.

Zur Zeit ziehe ich noch alle möglichen Verfahren in Betracht. Der Farbwinkel ist nur eines davon.

Als nächstes bau ich mir einen automatischen Weissabgleich und eine automatische Belichtungssteuerung.

Die Optimierung der Grösse von den Farbscheiben wird auch noch interessant sein. Die Grösse bringt Sicherheit gegenüber Fehlern, aber sie kostet verdammt viel Rechenzeit. Allerdings gibt es Tricks, um Rechenzeit zu sparen.

grüsse,
Hannes

[vohopri]

Hallo,

ein Stückchen bin ich doch weiter gekommen in diesem Neuland.

Als erstes hab ich mal die Testdaten verschärft:

http://www.jbergsmann.at/test12-300809.jpghttp://www.jbergsmann.at/test11-300809.jpg

Links Energisparlampe mit dem üblichen funselig sparsamen Ergebnis.
Rechts Tageslicht am Morgen, es ist fürs Auge in Natura nicht so dunkel wie auf dem Foto, aber richtig hell ist es doch noch nicht.

Jetzt hab ich mir einen Weissabgleich eingebaut. Aber ich gleiche nicht die Bilder ab, sondern das Farbkriterium zum Suchen der Markierung. Das spart immens viel Rechenzeit, wenn später bewegte Bilder verarbeitet werden. Also statt das Verfälschte Weiss aus allen Bildern raus zu rechnen, rechne ich einfach die Verfälschung ins Farbkriterium hinein.

Ich arbeite im RGB Raum und berechne für alle 3 Farbkomponenten:

AnzuwendenderKriteriumsWert:=sqrt(ReinerKriteriums wert*Weisswert)

Das reine, abstrakte Kriterium habe ich aber nicht, ich habe nur Bilder von Farbfolien ohen genaue Farbdefinition. Brauche ich auch nicht. Ich errechne den Reinen Kriteriumswert, wieder für alle Farbkomponenten.

ReinerKriteriumswert:=GemessenerKriteriumswert²/Weisswert

Voila, das funktioniert. Nachdem ich nichts über die Berechnung eines Weissabgleichs gefunden habe, habe ichs mal so versucht. Sollte jemand Info darüber haben, wie mans wirklich macht, würde mich das schon noch interessieren. Vielleicht hab ich da auch einen groben Denkfehler drin. Aber der sollte sich bei Tests zeigen.

Zunächst habe ich das Verfahren an beiden Bilder getestet und das hat mal funktioniert. Das ist nicht aussagekräftig, darum habe ich eine sogenannte Kreuzvalidierung vorgenommen. Das ist ein Verfahren, um statistische Parameter auf Unabhängigkeit von der Stichprobe zu prüfen. Klingt nur kompliziert, ist aber sehr einfach. Ich erhebe die reine Kriteriumsfarbe in einem Bild und wende sie mit Weissabgleich im anderen Bild an. Umgekehrt ebenfalls.

Hier das Ergebnis:

http://www.jbergsmann.at/12result4-300809.jpghttp://www.jbergsmann.at/11result4-300809.jpg

Auch das ist schön, passt.

Aus der Verarbeitung kann ich noch Zwischenschritte zeigen:

Verwendet habe ich diesmal nicht die Winkel zwischen den Farbvektoren (Kriterium - und alle Pixels) sondern die Distanz. Die errechnet sich bekanntlich aus den Komponentendifferenzen nach Pythagoras.

http://www.jbergsmann.at/12dresult2-300809.gifhttp://www.jbergsmann.at/11result2-300809.gif

Die Distanzen der Pixels zum Kriterium, das aus dem jeweils andern Bild stammt, aber im selben Bild abgeglichen wurde, ist dargestellt. Weiss stellt eine Distanz von 0 dar. Die Grauwerte wurden noch linear ins Dunkle transponiert, damit man die Unterschiede auch sieht. Die Eindeutigkeit des Verfahrens ist gut erkennbar.

Zum Vergleich hab ich ein Bild mit Farbwinkeln bearbeiten lassen:

http://www.jbergsmann.at/12aresult2-300809.gif

Wieder zeigt Weiss Nähe an. Das ist diesmal ein Cos von 1. Auch hier wurden die Grauwerte linear verschoben. Aber, was man sieht: Die Reflexionen auf dem Fussboden sind gefährlich wenig unterschieden vom Kriterium. Glanzlichter und Schatten sind sehr bunt, auch wenn man es auf dem Bild nicht sieht. Zusätzlich gibt es gerade in diesen Bereichen grauenhafte Artefakte der Kompression. Die Erkennung der Farbscheibe hat dennoch fehlerfrei funktioniert, aber so eindeutig wie mit den Differenzen ist das Ergebnis hier nicht.

Das nächste Bild zeigt das Clustern der Pixels nach dem Winkelwert.

http://www.jbergsmann.at/12aresult3-300809.gif

Jedes Pixel erhält als Wert nun den Mittelwert aus seiner Umgebung. Der Einfachheit wegen ist die Umgebung quadratisch. Die Grösse wird so gewählt, dass sie in die Abbildung der Farbscheibe rein passt. Dieses Verfahren hat zwei grosse Vorteile. 1.: wird so die Mitte der Scheibe gefunden, und 2. werden eventuell bestehende Fehler durch die Mittelwertbildung rausgerechnet. Vereinzelt oder in zu kleinen Gruppen vorkommende Pixels mit grosser Nähe zum Farbkriterium werden dennoch ignoriert, weil sie zu keinem nennenswerten Mittelwert beitragen.

Aber der Zeitbedarf ist schrecklich. Man fährt mit einer Matrix durch eine Matrix und rechnet. Im nächsten Bild ist ein Trick zu sehen, wie der Zeitbedarf drastisch reduziert wird.

http://www.jbergsmann.at/11result3-300809.gif

Man setzt einen Grenzwert, ab dem ein Pixel einen Mittelwert bekommt. Das sind die nicht schwarzen Stellen. Das beschleunigt das Verfahren stark. Dafür lohnt der Weissabgleich sehr. Die relevanten Differenzen sind dadurch gering und man kann das Limit knapp setzen.

Soweit mal eine erste Beschreibung. Detailfragen und Info zu Alternativen sind sehr erwünscht. Und ich hoffe auch, dass ich damit auch ein wenig Mut zur Bilderkennung mache. Viele Navigationsaufgaben lassen sich so leichter lösen, als mit US/IR.

grüsse,
Hannes

[mare_crisium]

Vohopri,

schön, wie Du das entwickelt hast :-). Der "Weissabgleich", wie man ihn in der Digitalphotographie verwendet, und die übliche Formel für den "Grauwert" dienen nur der Angleichung der Farbverteilung des Photos an die Farbempfindlichkeitskurven des Auges. Für Deine Arbeit spielt der visuelle Eindruck aber keine Rolle, deshalb kannst Du Dir Deine Methode so auswählen, wie es für die Anwendung am Günstigsten ist.

Mein Ratschlag ist, nicht den Cosinus des Farbwinkels zu nehmen, sondern den Sinus. Der Vorteil besteht im stärkeren Wachstum des Sinus bei kleinen Winkeln. Dadurch lassen sich kleine Farbunterschiede leichter unterscheiden ;-). Den Sinus bekommst Du entweder als

sinusWert = wurzel(1-cosinusWert)

oder direkt als normiertes Kreuzprodukt des Farbvektors mit dem Kriteriumsvektor. Nähe entspricht dann Null, der grösste Farbunterschied der Eins.

Dieselben Überlegungen hinsichtlicht der "Steilheit" der Farbnähefunktion gelten für Farbdistanzquadrat und Farbdistanz: Im Bereich kleiner Farbabweichungen reagiert das Distanzquadrat unempfindlicher als die Distanz.

Hinsichtlich der Mittelwertbildung usw.: Den Median- und den Gaussfilter kennst Du, oder? Wenn nicht, dann bietet das hier eine gute Übersicht.
http://www.mrt.uni-karlsruhe.de/download/rvmrt-b.pdf

Um die günstigste Lage von Schwellwerten festzulegen, ist es ratsam, ein Histogramm des entsprechenden Kriteriums (z.B. Farbwinkel zur Sollfarbe) für das Bild anzulegen.

Ciao,

mare_crisium

[vohopri]

Hallo mare crisium,

danke für deinen kompetenten Kommentar. Da kann ich ja beruhigt sein, du bestätigst mir viele Überlegungen und auch die Resevealternativen, die ich mir so zurecht gelegt habe.

Nur da scheint mir ein Tippfehler zugeschlagen zu haben:

sinusWert = wurzel(1-cosinusWert)

In Erinnerung habe ich:
sinusWert = wurzel(1-cosinusWert²)

grüsse,
Hannes

[Roboman93]

ich hab auchmal sowas gemacht, aller dings mit ner lib die "AForge" heißt. ich finde die recht gut, hat ne menge funktionen zur farberkennung.

mfg roboman

[mare_crisium]

vohopri,

au weia! :oops: Dein Gedächtnis täuscht Dich nicht: Die Formel muss so lauten, wie Du's geschrieben hast:

sinusWert = wurzel(1-cosinusWert^2)

Ciao,

mare_crisium