Eine simple Mustererkennung

Das folgende Beispiel soll einmal zeigen, wie eine recht einfache Mustererkennung mit VB.NET programmiert werden kann, wenn es nicht um Echtzeitperformance geht. Vielmehr ging es in meinem letztem Miniprojekt (bzw. Freundschaftsdienst) um die Auswertung von Ultraschallaufnahmen, in denen ein grauer Kasten einen bestimmten Bereich markiert und dessen Größe automatisch erkannt werden sollte. Das Problem dabei: Auf Grund der jpg-Komprimierung kann kein eindeutiger RGB-Wert dem Kasten zugeordnet werden, eine bestimmte Toleranz ist also nötig. Außerdem ist nicht garantiert, dass die Kastenfarbe auch nirgendwo anders im Ultraschallbild vorkommt.

Dies ist also ein klarer Fall für Mustererkennung. Theoretisch könnte man probieren, den Kasten als Ganzes zu erkennen. Einfacher ist es jedoch, die Ecken per Mustererkennung herauszusuchen.

Das Prinzip ist dabei das folgende. Man erstellt für eine Ecke ein exemplarisches Bild, das hier nur aus zwei Farben besteht, nämlich ein helles Grau sowie irgendwas sehr dunkles. Diese Farben findet man sehr leicht mit dem Pipette-Werkzeug eines Grafikprogramms. 

Dieses Bild wird nun anschaulich gesprochen von dem Algorithmus über jede Stelle des Bildes gehalten und diejenige ermittelt, an der es am besten passt. Dies geschieht, indem man von dem gewählten Bildausschnitt das exemplarische Bild subtrahiert. Je kleiner die Differenz, desto ähnlicher sind sich die Bilder. Eine Differenz von null wird aber so gut wie nie auftreten, schließlich besitzt das Bild ja die oben genannten Störungen.

Um zwei Bilder von einander abzuziehen, ist zunächst einmal der Zugriff auf die einzelnen Pixel nötig. Liegt das Bild als "System.Drawing.Bitmap" vor, so können wir dazu die "GetPixel()"-Methode verwenden. Diese ist leider recht langsam und da wir die Pixel des Bildes mehrfach auslesen müssen, lohnt es sich, das Bild erstmal in ein zweidimensionales Array umzuwandeln, denn aus ihm zu lesen geht schneller.

Da es sich bei den Ultraschallbildern nur um Graustufen handelt, genügt es, nur die Helligkeit der Pixel zu verwenden und Farbinformationen zu ignorieren. Hierzu eignet sich das HSV-Format, das Farben nicht wie bei RGB in Rot-, Gelb- und Blauanteile zerlegt sondern sie als Hue (Farbton), Saturation (Sättigung) und Brightness (Helligkeit) darstellt. Genau der letzte Parameter ist für uns interessant. Die "GetPixel"-Methode gibt eine "System.Drawing.Color", die die Methode "GetBrightness()" besitzt.

Die folgende Prozedur erledigt die Umwandlung des Bildes in ein Array, wobei  jedes Element des Arrays den Brightness-Wert des entsprechenden Bildpixels bekommt.

Diese Prozedur benötigen wir zweimal - sowohl für das exemplarische Bild der Ecke (Pattern) sowie das zu untersuchende Bild (Probe). Beide habe ich in jeweils eine PictureBox eingefügt und dann über "Me.PictureBox_Pattern1.Image" bzw. "Me.PictureBox_Probe.Image" aufgerufen.

Nun muss das Bild vollständig durchlaufen werden, dies erledigen zwei For-Schleifen, die an jeder Position die Funktion "Execute_PatternTest(...)" aufruft, die wir gleich danach programmieren werden.

Die beiden globalen Variablen speichern die Position der am besten passenden Position sowie einen Wert vom Typ Single, der angeben muss, wie gut das Pattern dort passt. Diesen Wert wird uns die Funktion "Execute_PatternTest(...)" zurückgeben. Je kleiner der Wert, desto besser ist die gefundene Position. Beim Durchlaufen des Bildes wird immer überprüft, wie gut das Pattern an dieser Stelle passt. Ist die aktuelle Position besser als die gespeicherte, wird diese übernommen und die alte verworfen. Dabei wird natürlich auch der neue Wert von "Pattern1_Recog" gespeichert.
Schauen wir uns nun die noch ausstehende Testfunktion an.

Es tauchen wieder zwei For-Schleifen auf, die das Pattern durchlaufen. Hier ist jetzt jeweils eine Abbruchbedingungen nötig, die verhindert, dass dabei der Rand der Probe überschritten wird. Befinden wir uns beispielsweise am rechten Rand des Bildes, so kann das Pattern gar nicht mehr vollständig überprüft werden.
Bei jedem Schleifendurchlauf wird der Brightnesswert von Probe und Pattern aus dem jeweiligen Array gelesen, subtrahiert und zur Variable "DiffSum" addiert. Diese enthält am Ende die Summe der Helligkeitsdifferenzen an der getesteten Stelle des Patterns in der Probe. Die Variable "PixelSum" enthält die Anzahl der betrachteten Pixel, sodass wir als Rückgabewert die durchschnittliche Helligkeitsdifferenz zurückgeben.

Es ist wichtig, dass hier nicht einfach "DiffSum" zurückgegeben wird. Da nämlich an den Rändern nicht das gesamte Pattern auf die Probe passt, ist dort "DiffSum" prinzipiell kleiner, denn es werden einfach weniger Helligkeitsdifferenzen aufaddiert.

Und das war es schon. Da wir hier letztlich 4 verschachtelte For-Schleifen haben, in denen die Helligkeitsinformationen abgefragt werden, ist es also wirklich vernünftig, die Bilder zunächst in ein Array zu verwandeln, wie oben beschrieben wurde. Dies ist jedoch auch die einzige Optimierung, die hier vorgenommen wurde. Das Prinzip einer Mustererkennung ist aber an diesem Beispiel denke ich sehr leicht nachzuvollziehen. Große Auswirkung auf die Laufzeit hat die Größe der Patterns. Hier muss man experimentieren, was für eine Mindestgröße vorhanden sein muss, um relativ sichere Treffer zu erhalten.

Um zum Ausgangsproblem zurückzukehren: Um die Abmessungen des grauen Kastens zu ermitteln, müssen wir mit dem geschilderten Verfahren nach der linkeren oberen und der rechteren unteren Ecke suchen. Liegen genau an deren Stellen jedoch gleichfarbige Bereiche im Ultraschallbild, so kann es gut passieren, dass die Erkennung fehlschlägt. Solche Fälle muss man dann erkennen und zum Beispiel alternativ die beiden anderen Ecken suchen.