Computer VisionProjectTutorial

“Do It Yourself” – Texterkennungssoftware


Heute sehen wir uns an, wie man mit einfachen Mitteln und Methoden eine Texterkennungssoftware basteln kann, ohne dabei abhängig von Tesseract u.ä. zu sein.
Wir werden dabei folgendes kennen lernen:

  • Semantic Local Binary Patterns (S-LBP): Als Feature Extraction-Methode1
  • Histogramme: Als Möglichkeit einzelne Features effizient zusammen zu fassen
  • k-Nearest-Neighbor Classifier: Als einfache aber mächtige Möglichkeit zur Klassifizierung von Daten

Eine unter Windows lauffähige Binary-File gibt es unter: SimpleOCR
Diese Binary orientiert sich stark an diesem Tutorial, hat aber noch ein paar Kniffe und Tricks extra eingebaut.


Voraussetzungen

Prinzipiell halten sich die Voraussetzungen in Grenzen, man sollte nur wissen wie Bilder grob aufgebaut sind und folgenden Post einmal durchgearbeitet haben:


Ausgangssituation

Wir beschränken uns bei diesem kleinen Projekt auf Zahlen und zwar nur auf Zahlen desselben Schrifttyps. Das mag auf den ersten Blick alles außergewöhnlich einfach machen, aber so einfach wie man denkt wird es nicht werden. Unser Ansatz soll auch für leichte Änderungen (wie Größenänderung oder Verschiebung) funktionieren.
Ich habe vor einiger Zeit aus einem Spiel einige Zahlenfolgen extrahiert. Diese Zahlenfolgen gaben den aktuellen Punktestand an und sind ausreichend komplex und dennoch einfach genug, um an Hand von diesen Zahlen eine simple Texterkennung zu schreiben. Ein paar Beispiele der extrahierten Zahlen:

2781 1781 1798 1801

Wir sehen, die Bilder sind unterschiedlich groß und die Zahlen können theoretisch beliebig lang oder kurz sein (mindestens jedoch eine Ziffer).
Um uns das Leben noch ein klein wenig schwerer zu machen, fügen wir ein paar Zahlenfolgen mit unterschiedlichen Farben hinzu:

1809  290 1339

Das komplette Set an Zahlen gibt es unter Download Numbers.

Am besten ist es bei derartigen Problemen immer die Mustererkennung-Pipeline abzuarbeiten. Vor allem am Anfang verhindert das etwas zu vergessen.


Preprocessing

Das erste was auffällt sind die unterschiedlichen Farben. Die Farben haben keinerlei Einfluss auf die Ziffern. Eine 2 in gelb sieht genau so aus wie eine 2 in rot oder blau. Daher ist der erste Schritt die Zahlen einheitlich einzufärben. Das Optimum wäre natürlich die Zahlen zu binärisieren das heißt die Zahlen schwarz zu färben und den Hintergrund weiß. Aber je länger man darüber nachdenkt, desto schwerer scheint dieser Preprocessing-Schritt zu werden. Immerhin können wir nicht einfach sagen:
“Die dunkelsten Pixel auf dem Bild werden schwarz und die hellsten weiß” (oder andersrum). Denn wir haben sowohl Zahlen in sehr hellen Farben als auch Zahlen in sehr dunklen Farben. Man kann sich jetzt komplexe Algorithmen überlegen, aber manchmal ist es in solchen Situationen sinnvoll nicht zu viel Zeit ins Preprocessing zu stecken, weil sich das Problem später bei der Feature Extraction von selbst erledigen könnte. So ganz ohne Preprocessing ist aber auch nicht gut. Was wir jedoch einfach machen können ist das Farbbild in ein Graubild umzuwandeln. Das Umwandeln von Farbbilder in Grauwert-Bilder ist sehr einfach und schnell gemacht. Alles was man dafür machen muss, ist über jedes Pixel im Bild zu gehen und folgende Formel anzuwenden:

Es gibt noch andere Formeln um ein Grauwertbild zu erzeugen, für uns reicht diese Formel aber vollkommen. Wenn man das dann auf alle Bilder anwendet, kommt in etwa so etwas raus:

290_gray 1798_gray  2765_gray

Offensichtlich unterscheiden sich die unterschiedlich gefärbten Bilder immer noch, aber sie besitzen jetzt zumindest alle dieselbe Farbe, nämlich Grau. Ein weiterer Preprocessing-Schritt wäre alle Ziffern auf dieselbe Größe zu bringen oder den Rand links von den Zahlen abzuschneiden. Alle Zahlen auf dieselbe Größe zu bringen lohnt sich auf Grund unserer Feature Extraction Methode ebenfalls nicht. Den Rand links zu entfernen ist codetechnisch nicht aufwendig und wir werden in einem späteren Schritt sowieso die komplette Zahl in einzelne Ziffern aufsplitten lassen. Deswegen verschieben wir den Schritt auch nach später. Die Bilder in Grauwertbilder umwandeln zu lassen, ist also der einzige Preprocessing-Schritt, den wir für dieses Datenset wirklich anwenden.


Feature Extraction

Im nächsten Schritt extrahieren wir aus unserem Grauwert-Bild einige Features, die dem Computer helfen Regeln zu erkennen.Es gibt viele mögliche Feature Extraction – Methoden, die wir anwenden könnten und die alle ähnlich gute oder Ergebnisse liefern würden. Wir beschränken uns jedoch auf eine Abwandlung von Local Binary Patterns (auch abgekürzt als LBP).


Local Binary Pattern

LBP ist eine gute Feature Extraction-Methode, die sehr leicht umzusetzen und zu verstehen ist. Daher erfreut sie sich großer Beliebtheit. Die Idee hinter LBP ist einfach. LBP analysiert jeden Pixel im Bild einzeln und schaut sich die direkte Nachbarschaft dieses Pixels genauer an. Jedes Pixel das deutlich heller als das analysierte Pixel ist, wird mit einer 1 gekennzeichnet und jedes Pixel das dunkler als oder ähnlich hell wie das Pixel im Zentrum ist, wird mit einer 0 gekennzeichnet. Im Normalfall setzt man feste Grenzen ab wann ein Pixel sich deutlich vom Pixel in der Mitte in der Helligkeit unterscheidet. Bei einem Grauwertbild mit Werten von 0 bis 255, nimmt man meistens Werte im Bereich 10-40. Die Folge von 0en und 1en um der Pixel in der Mitte drumherum fasst man dann als binäre Zahl auf und weist dem Pixel in der Mitte diesen Wert zu. Wenn wir uns das Ganze grafisch anschauen, sollte das Prinzip relativ schnell klar werden (in diesem Beispiel muss der Nachbarpixel mindestens um 10 heller sein):

lbp

So kompliziert sind LBPs also nicht. LBPs an sich sind schon gut geeignet für verschiedenste Probleme, aber noch besser ist eine Erweiterung der LBPs, die Semantic-LBPs1. In einem Researchpaper vor einiger Zeit, wurde herausgefunden1, dass zur Mustererkennung diejenigen Muster wichtig sind, die keine Unterbrechung in der 1en bzw. 0en folge beinhalten. Das heißt das hier wären LBPs, die keine Unterbrechung in der jeweiligen 1en bzw. 0en Folge besitzen:

  • 01110000
  • 11000000
  • 11111111
  • 00000000
  • 00000100
  • usw.

Diese Folgen hingegen haben Unterbrechungen:

  • 10100000
  • 00010001
  • 11110010
  • 01111010
  • usw.

Laut den Ergebnisse von Mu et al.1 haben diejenigen Muster ohne Unterbrechung also den größten Einfluss auf die Erkennungsrate. Diese Erkenntnis kommt uns natürlich zu Gute, denn wir reduzieren unsere Daten ja gerne auf das Nötigste, um die Verarbeitungszeit zu reduzieren und um nur die nötigsten Regeln zu extrahieren.

Wir schmeißen also alle berechneten LBPs, die Unterbrechungen besitzen raus. Ebenso schmeißen wir LBPs, die nur aus 1en oder nur aus 0en bestehen raus. LBPs, die nur aus 0en bestehen bedeuten, dass sich kein Pixel in der Nachbarschaft vom Pixel in der Mitte unterscheidet. Das heißt also wir haben eine Fläche gefunden. Die größte Fläche ist der Hintergrund und den wollen wir natürlich nicht erkennen, daher brauchen wir auch diese LBPs nicht. Anders ist es, wenn sich alle Pixel außenrum zu stark unterscheiden, dann betrachten wir scheinbar einen isolierten Pixel, der nicht zu einer Ziffer gehört, denn keine Ziffer der Welt besteht aus nur einem einzigen Pixel. Nachdem wir den LBP-Algorithmus auf das komplette Bild angewendet haben und die nicht gebrauchten LBPs rausgeschmissen haben, kriegen wir ein Bild, das etwa so aussieht:

lbpimage

In diesem Bild habe ich alle LBPs, die nicht rausgeschmissen wurden mit weiß dargestellt und alle Anderen mit schwarz. Man sieht, dass die übrigen LBPs in etwa die Kanten der Ziffern darstellen. Der erste Schritt in Richtung S-LBP ist damit getan. Aber es gibt noch ein paar Kleinigkeit, womit sich das LBP verbessern lässt. Um die weiteren Schritte zu verstehen, müssen wir aber erst einmal verstehen was Histogramme sind und wofür wir sie verwenden wollen.


Histogramm

Histogramme werden sehr gerne benutzt, um die Feature Extraction robuster gegenüber Größenänderung, Verschiebungen und ähnlichem zu machen.
Die Idee eines Histogramms ist dabei sehr einfach. Man zählt einfach wie oft ein bestimmtes Feature in einem Bild vorkommt. Wir verdeutlichen das wieder an einem Beispiel. Stellen wir uns vor wir haben die Aufgabe zu entscheiden ob ein Bild einen Kreis oder nur einen Strich enthält. Sowohl der Kreis als auch der Strich werden durch weiße Pixel dargestellt und der Hintergrund ist immer schwarz. Der Kreis und der Strich sind immer gleich lang/groß, können aber irgendwo im Bild auftauchen. Einige Beispiele:

kreis3 strich1 strich2 strich3 kreis1 kreis2

Die einfachste Möglichkeit um herauszufinden, ob ein Kreis oder ein Strich sichtbar ist, ist das Zählen der weißen bzw. schwarzen Pixel. Da der Kreis deutlich größer ist und aus mehr weißen Pixeln besteht, kann man einfach über die Summe der weißen Pixel zwischen Strich und Kreis unterscheiden. Diese Summe nennt man auch Histogram. Bei einem Histogram zählt man also alle Pixel von einer Farbe und speichert es ab. Sehen wir uns einmal einen kleinen Bildausschnitt aus einem Grauwertbild an (Zahlen in den Zellen entsprechen konkreten Pixelwerten):

gray

Das dazugehörige Histogram sähe dann so aus (alle nicht vorkommenden Werte wurden weggelassen):

  • 3: 2
  • 4: 2
  • 8: 2
  • 11: 2
  • 15: 3
  • 201: 2
  • 211: 3

Alle anderen, nicht sichtbaren Werte (auch Bins genannt), wären dementsprechend 0.
Sehr oft stellt man das Histogramm auch als Säulendiagramm dar:

lbp_diag

Jetzt erstellen wir für ein paar unserer Kreise und Striche das jeweilige Histogramm.
Das Histogramm ist immer rechts vom Bild.

kreis3

0 (= schwarz):  3219
1 (= weiß): 1681

 

strich2

0 (= schwarz): 4619
1 (= weiß): 281

 

strich3

0 (= schwarz): 4619
1 (= weiß): 281

 

kreis2
0 (= schwarz):  3219
1 (= weiß): 1681

 

Man sieht, egal wo sich der Kreis oder der Strich befindet, die Summe der weißen Pixel ist immer gleich. Damit ist es ein Kinderspiel zwischen Kreis und Strich zu unterscheiden. Jetzt wollen wir aber einen Schritt weitergehen, wir wollen nicht nur unterscheiden ob ein Kreis oder ein Strich sichtbar ist, sondern auch auf welcher Seite sich der Strich befindet (links, rechts, oben, unten). Auch das ist mit Histogrammen leicht möglich. Der Vorteil von Histogrammen ist gleichzeitig auch ihr größter Nachteil. Histogramme sind robust gegenüber Verschiebungen. Das heißt aber gleichzeitig, dass man mit einem Histogramm alleine nicht den Ort bestimmen kann an welchem sich ein Objekt befindet. Manchmal ist das gewollt, meistens will man aber nur bis zu einem gewissen Grad robust gegenüber Verschiebung sein. In solchen Fällen bedient man sich einem Trick. Das ganze Bild wird nicht in einem Histogram zusammengefasst, sondern das Bild wird in Bereiche unterteilt für die jeweils ein eigenes Histogram berechnet wird. Damit erlauben wir leichte Verschiebungen und können trotzdem grob das Objekt lokalisieren. Wir unterteilen unser Bild immer in 9 gleich große Histogramme:

strich2_9 kreis2_9 kreis3_9

Anschließend berechnen wir für jedes Histogram wie viele weiße Pixel in diesem Bereich liegen:

strich_hist  kreis2_hist  kreis3_hist

Es ist offensichtlich, dass wir jetzt zwar ein paar mehr Überprüfungen machen müssen, um zwischen Kreis und Strich zu unterscheiden. Dafür haben wir es geschafft bis zu einem gewissen grad robust gegenüber Verschiebungen zu sein und dennoch das Objekt grob lokalisieren zu können. Zusammenfassend kann man sagen: Immer wenn Robustheit gegenüber Verschiebung gefragt ist, sollte man überlegen ein oder mehrere Histogramme zu verwenden.


Semantic Local Binary Pattern

Nachdem uns klar ist was LBPs sind und wofür man Histogramme braucht, können wir endlich zu den S-LBPs übergehen. Die LBPs wurden von uns schon auf unterbrechungsfreie Muster reduziert. Aber ein Problem bleibt vorhanden. Offensichtlich unterscheidet sich das Muster “00111110” von dem Muster “00011100” nicht besonders stark, wenn man sich beide Muster graphisch anschaut wird das noch klarer:

bin1  bin2

Ihr resultierender Wert hingegen unterscheidet sich deutlich. So würde “00011100” dem Wert 28 entsprechen und “00111110” dem Wert 62. Diese zwei Werte unterscheiden sich deutlich, obwohl sie eigentlich sehr ähnlich sind. Aus diesem Grund schlagen Mu et al.1 vor nicht den Wert der entstehenden Zahl pro Pixel zu speichern, sondern die Stelle der mittleren 1 und die Anzahl an 1en zu speichern. Damit speichern wir die zwei angegebenen Zahlen wie folgt:

  • 00111110 –> Stelle: 4; Länge: 5
  • 00011100 –> Stelle: 4; Länge: 3

“Ja alles schön und gut aber warum interessiert uns das überhaupt?”, geistert möglicherweise jetzt in euren Köpfen herum. Die Antwort ist relativ einfach: Wir wollen unsere LBPs mit Histogrammen kombinieren, um Robustheit gegenüber Verschiebungen zu erlangen. Wenn wir unsere LBPs aber direkt speichern, würden alle Werte “00011100” einen extra Platz bekommen und alle “00111110” Muster ebenfalls, obwohl sie eigentlich sehr ähnlich sind. Mit der neuen Schreibweise umgehen wir dieses Problem, indem wir nach Stellen gruppieren. Damit landen “00011100” und “00111110” auf demselben Platz. Um dennoch die zwei Muster unterschiedlich behandeln zu können, addieren wir nicht pro vorkommendes Muster 1 auf den jeweiligen Platz im Histogramm, sondern die Länge des LBPs. Konkret würde für unsere zwei Muster also dieses Histogramm herauskommen:

  • 4: 8

SLBP Plus

Um unsere SLBPs perfekt zu machen, fehlt noch eine Kleinigkeit. Wenn man sich einmal die entstehenden SLBPs für einen simplen Strich ansieht, merkt man schnell, dass LBPs eigentlich immer paarweise auftreten:

lbp_strich_paar

Wir haben in einem vorherigen Kapitel schon festgestellt, dass unsere LBPs ohne Unterbrechungen hauptsächlich auf Kanten sind. Das sieht man auch an dem Bild oben gut. Logischerweise Hat jedes Objekt mit Hintergrund eine Kanten auf der linken Seite und eine Kante auf der rechten Seite. Die entstehenden LBPs sind dementsprechend nur gespiegelt. Das heißt aber, dass wir unsere SLBPs zusammenfassen können, indem wir das original SLBP und die gespiegelte Version ebenfalls in den selben Platz im Histogram einrechnen. Wir definieren also die Stellen 0 bis einschließlich 3 als “original” SLBPs und 4 bis 8 als “Spiegelung”.

Damit kommen folgende SLBPs alle in den selben Platz (nämlich an Stelle 1):

  • 11100000 –> Stelle: 1; Länge: 3
  • 00001110 –> Stelle: 5; Länge: 3
  • 00000100 –> Stelle: 5; Länge: 1

Feature Extraction Überblick

In den letzten Kapiteln haben wir kennen gelernt, dass LBPs die Nachbarschaft eines Pixels beschreiben. Sie besitzen an den Stellen an den die Nachbarpixel deutlich heller sind eine 1 und sonst eine 0. SLBPs reduzieren LBPs auf diejenigen Muster ohne Unterbrechungen, weil diese Muster deutlich aussagekräftiger sind als diejenigen Muster mit Unterbrechungen. Außerdem haben wir Histogramme kennen gelernt, die uns Robustheit gegenüber Verschiebungen gewähren. Wir habe herausgefunden, dass das Aufteilen des Bildes in mehrere Histogramme ein Kompromiss zwischen Verschiebungsrobustheit und Lokalisierung des Objektes darstellt. Zum Schluss haben wir die SLBPs noch etwas verfeinert und uns klar gemacht, dass ein Gruppieren nach der mittleren 1 in SLBPs gut ist. Nachdem wir nun endlich die Feature Extraction umfangreich gelöst haben, können wir zum Classifier kommen.


k-Nearest-Neighbor Classifier

Das Prinzip des k-Nearest-Neighbor Classifiers (gerne abgekürzt mit kNN-Classifier, nicht zu verwechseln mit KNN für Künstliches Neuronales Netz) ist denkbar einfach. Ein Classifier ist dafür da, um ein Array an extrahierten Features (auch gerne Featurevektor genannt) einer Klasse zuzuordnen. In unserem Fall hat der Classifier die Aufgabe basierend auf unseren extrahierten SLBP-Histogrammen herauszufinden welche Zahl sich dahinter verbirgt. Der kNN-Classifier benutzt dafür die Holzhammermethode. Wir wissen, dass jeder Classifier, bevor er benutzt werden kann, ein “Training” durchlaufen muss. Der Classifier muss zuerst Beispiele für 1en, 2en, usw. sehen, damit er sich daraus Regeln basteln kann. Auch der kNN-Classifier muss diese Phase durchlaufen. Bei dem kNN-Classifier ist die Trainingsphase jedoch denkbar einfach. Der kNN-Classifier speichert sich beim Training einfach alle gezeigten Beispiele ab. Das heißt das Training eines kNN-Classifiers beschränkt sich auf das Kopieren der Trainingsdaten. Dementsprechend schnell ist ein kNN-Classifier auch trainiert. Wenn man dem kNN-Classifier jetzt eine zu klassifizierende Zahl gibt, macht der Classifier nichts anderes als die gegebene Zahl mit jeder abgespeicherten Zahl zu vergleichen. Er speichert sich für jedes antrainierte Beispiel wie gut das Beispiel mit der gegebenen Zahl zusammenpasst. Anschließend sortiert der kNN-Classifier die Wertung pro Beispiel so, dass die antrainierten Beispiele mit der größten Ähnlichkeit am Anfang stehen. Danach schnappt sich der kNN-Classifier die ersten k Wertungen und schaut welche Zahl am häufigsten vorkommt. Diese am häufigsten vorkommende Zahl ist dann das Ergebnis des Classifiers. Wir verdeutlichen uns das wieder einmal an einem konkreten Beispiel. Stellen wir uns vor dem Classifier wurden pro Zahl 3 verschiedene Beispiele gezeigt und die ersten 10 Wertungen sehen wie folgt aus (je größer die Zahl desto ähnlicher ist das gespeicherte Beispiel der gegebenen Zahl):

Gegebene Zahl: 2
Generierte Ähnlichkeitsliste:

  • 5: 0.94
  • 2: 0.93
  • 2: 0.85
  • 2: 0.71
  • 5: 0.53
  • 8: 0.44
  • 0: 0.22
  • 8: 0.21
  • 8: 0.19
  • 0: 0.19

Ein kNN-Classifier mit k=1 schaut sich jetzt die erste Zahl mit der höchsten Wertung an. In diesem Beispiel ist das die Zahl 5. Damit ist für den Classifier die Lösung 5, was aber natürlich falsch ist. Dummerweise sieht die gegebene Zahl wohl zufällig so aus wie diese eine 5. Derselbe Classifier mit k=4 hingegen schaut sich die obersten 4 Ergebnisse an und gibt dasjenige Ergebnis zurück, das dominiert. Die obersten 4 Ergebnisse sind:

  • 5: 0.94
  • 2: 0.93
  • 2: 0.85
  • 2: 0.71

Damit kommt die 2, dreimal vor und die 5 nur einmal.
Der Classifier mit k=4 würde jetzt als Ergebnis 2 zurückgeben. Das Ergebnis stimmt dieses Mal. Es kann also hilfreich sein sich die ersten k Ergebnisse anzusehen und nicht nur das Beste. Dennoch sollte man k nich zu groß wählen, sonst könnte man dreimal die 2 und dreimal die 5 finden und hätte wieder keine Ahnung was das richtige Ergebnis ist. Dazu auch ein kleines Bild (Classifier mit k=4):

knn

Graphisch gesehen wollen wir das Fragezeichen im Bild bestimmen, indem wir uns die k nächsten Nachbarn ansehen.


Das Große Ganze

In diesem Kapitel programmieren wir endlich unsere Zahlenerkennung. Bevor wir jedoch unser ganzes gelerntes Wissen kombinieren können, müssen wir noch die komplette Zahl in einzelne Ziffern zerlegen. Denn wir können ja nur einzelne Ziffern erkennen, nicht jedoch ganze Zahlen. Das Aufsplitten der Zahlen ist jedoch nicht großartig schwer. In unserem Fall ist zwischen zwei Ziffern normalerweise immer ein kleiner Leerraum. Das heißt wir splitten immer dann unsere Zahlen, wenn wir in einer Pixelspalte nur schwarze Pixel besitzen. Zusätzlich fügen wir als Bedingung hinzu, dass wir jedoch nach spätestens 15 Pixeln splitten. Damit umgehen wir Probleme bei Zahlen, die keinen solchen schwarzen Leerraum haben.

Unser kNN-Classifier misst die Ähnlichkeit von den gespeicherten Daten und dem aktuellen Datum, indem er für jedes Histogram die Differenz zwischen jeder Position bildet und alle Differenzen aufsummiert.

Das heißt diese Funktion macht nichts anderes als zu schauen, wie viele SLBPs von welcher Länge/Postion in dem jeweiligen Histogram vorhanden sein sollten und je weniger vorhanden sind als es sein sollten, desto unähnlicher sind sich die zwei gegebenen Daten.

Alles in allem sieht unser komplettes Programm in Pseudo-Code dann so aus (basierend auf OpenCV Befehle):

Artikel zitieren:
Marcel Rupprecht, "Do It Yourself – Texterkennungssoftware", in Neural Ocean, 2016, //neuralocean.de/index.php/de/2016/10/08/texterkennung/.

BibTex:
@misc{NeuOcSimpleOCR2016,
    title="Do It Yourself – Texterkennungssoftware",
    url="\url{//neuralocean.de/index.php/de/2016/10/08/texterkennung/}",
    journal="Neural Ocean",
    author="Marcel Rupprecht",
    year="2016 (accessed März 30, 2020)"
}

1.
Mu Y, Yan S, Liu Y, Huang T, Zhou B. Discriminative local binary patterns for human detection in personal album. Computer Vision and Pattern Recognition, 2008 CVPR 2008 IEEE Conference on. 2008:1-8.

2 Gedanken zu „“Do It Yourself” – Texterkennungssoftware

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.