Schrifterkennung

Um so komplexer ein Problem ist und um so größer die Herausforderung, desto mehr reizt es mich eine Lösung zu finden. In diesem Fall handelt es sich um den Capcha-Code bei einem Browsergame, den ich doch als so nervig empfinde, dass ich mich herausgefordert fühle, allein aus Protest einen Bot zu schreiben. Bei besagtem Capcha sind allerdings einige Maßnahmen ergriffen worden um genau dies zu erschweren. Die Buchstaben sind annähernd willkürlich Positioniert, wobei die Reihenfolge allerdings halbwegs erhalten ist. Zusätzlich haben sie zufällige Schriftgröße, Schriftart und sind in verschiedenen Winkeln gedreht. Neben den Buchstaben ist das Bild auch mit eine Art Rauschen versehen. Welches sich aus zufällig platzierten Punkten und Strichen zusammensetzt. Insgesamt hört es sich also nach einer Herausforderung an.

Neben den aufgelisteten Schwierigkeiten hat der Capcha allerdings auch die ein oder andere Schwäche. Die erste Schwäche betrifft das Rauchen. Im Gegensatz zu den Buchstaben, welche ausschließlich in Grautönen dargestellt werden, besteht das Rauschen aus farbigen Elementen. Daher konnte man das Rauschen einfach los werden, indem man das Bild ausschließlich auf Pixel filtert, bei denen der Rot-Wert mit dem Grün- und Blau-Wert überein stimmt. Anschließend hat man nur noch die Buchstaben, die allerdings durch das Rauschen die ein oder andere Lücke aufweisen.

Um diesen Lücken zu begegnen habe ich eine weitere Filterung implementiert. Bei einem ungefärbten Pixel prüft diese ob die gegenüberliegenden benachbarten Pixel eine identische Farbe haben. Ist dies der Fall, so übernimmt der ungefärbte Pixel diese Farbe. Durch dieses Verfahren werden die Lücken geschlossen. Ein weiteres ungewolltes Phänomen sind die Übergänge. An den Rändern der Buchstaben treten abgestufte Grautöne auf, damit die Konturen der Buchstaben weicher in den Hintergrund übergehen. Dies ist für die Buchstabenerkennung allerdings lästig. Daher hat diese Filterung noch die Aufgabe bei einem gefärbten Pixel zu prüfen ob die zwei nächsten Pixel in jede Richtung eine abweichende identische Farbe hat und der nächste Pixel in die entgegengesetzte Richtung ebenfalls beliebig abweicht. Ist dies der Fall erhält das untersuchte Pixel die Farbe der beiden benachbarten Pixel. Klingt erst einmal Kompliziert, daher will ich es versuchen Grafisch zu veranschaulichen:

Filter 1 bei ungefärbten Pixeln:

Filter 2 bei gefärbten Pixeln:

Ich hoffe die grafische Darstellung konnte das Ganze etwas veranschaulichen. Leider haben diese Filter einen Nachteil: sie sind sehr Rechenaufwändig und müssen für ein zufriedenstellendes Ergebnis auch mindestens zwei mal durchgeführt werden. Dies schlägt sich auch sichtbar in der Rechenzeit wieder.

Hiernach ist das Bild genug gefiltert und es geht daran die Buchstaben zu erkennen. Dafür werden wieder alle Pixel durchgegangen, bis man auf einen Farbigen stößt. Anschließend wird eine Rekursive Funktion gestartet die versucht in einem drei Pixel-Radius Pixel einer ähnlichen Farbe zu finden. Dabei merkt sich die Funktion die dabei gefundenen jeweils größten und kleinsten x- bzw. y-Werte. Haben diese Werte eine bestimmte Minimaldifferenz kann davon ausgegangen werden, dass es sich bei dem ermittelten Bereich um einen Buchstaben handelt. Die erkannten Pixel werden aus dem Gesamtbild entfernt und in einen Puffer geschrieben.

Jetzt hat man ein Gebilde bei dem es sich wahrscheinlich um einen Buchstaben handelt, nun muss man diesen nur noch identifizieren. Dafür habe ich mir überlegt aus den Buchstaben eine Art Hash zu errechnen. Dabei wird das Bild theoretisch gesehen auf fünf mal sechs Pixel heruntergerechnet wobei jeder Pixel entweder gefärbt oder ungefärbt ist. Ordnet man die Pixel anschließend linear an erhält man eine dreißig stellige Binärzahl. Diese Zahl lässt sich dann leicht vergleichen. Durch eine binäre Quersumme der Differenz (welche per xor ermittelt werden kann) zweier Werte kann auch ermittelt werden, wie stark sich zwei Buchstaben unterscheiden. Um den Buchstaben also zu identifizieren muss ich eine Datenbank mit Referenzwerten aufbauen, die dann mit eine berechneten Hash abgeglichen werden kann. Durch eine minimale Differenzquersumme kann auch eine näherungsweise Bestimmung vorgenommen werden. Also grob gesagt, jeder Buchstabe wird in eine Zahl konvertiert, welche dann mit bereits erkannten Zahlen verglichen wird. So kann dann ein Buchstabe angenommen werden.

Leider ist die Buchstabenerkennung nicht absolut zuverlässig und es kann passieren, dass Buchstaben gar nicht oder fehlerhaft erkannt werden. Um dies auszugleichen kann man die andere Schwäche des Capchas verwenden, denn er zeigt lediglich die Zahlen von eins bis hundert als Worte an. Das heißt, dass es nur eine bestimmte relativ geringe Anzahl von möglichen Buchstabenkombinationen gibt. Anhand dieser kann man also versuchen Buchstabenfehler zu korrigieren. Dies geschieht in mehreren Schritten. Der erste und bisher einzig intelligente Filter untersucht die erkannte Zeichenkette auf unübliche Doppelbuchstaben und entfernt diese. Anschließend wird versucht das Wort zu erkennen. Zuerst wird abgefragt, ob es eine identische Kombination als Wort gibt, anschließend ob es eine Kombination gibt in der die erkannten Buchstaben in der erkannten Reihenfolge vorkommen. Die ist leider bisher selten mit Erfolg gekrönt, da die Fehlerrate bei der Buchstabenerkennung leider noch ein wenig zu hoch ist. Der nächste Schritt entfernt dann nach und nach immer wieder Buchstaben und versucht den Rest der verbleibenden Buchstaben in den möglichen Wörtern wieder zu finden, bis ein Wort erkannt wird.

Da es Sehr viele mögliche Kombinationen gibt ist diese Verfahren leider auch wieder sehr aufwändig. Daher sehe ich das meiste Verbesserdungspotential noch in der Fehlerkorrektur. Die Buchstabenerkennung werde ich versuchen noch weiter zu verbessern, indem ich weiteres Referenzmaterial zur Verfügung stelle. Wünschenswert wäre noch eine Intelligente Fehlerkontrolle, welche nicht derartig aufwändig ist. Aber darüber denke ich ein anderes mal nach. Ich hoffe ich konnte ein wenig Einblick in meine Überlegungen zum Thema Schrifterkennung geben und dies auch nicht all zu unverständlich.