Einleitung
In Vorbereitung auf ein möglicherweise kommendes Projekt aber wohl in erster Linie aus technischem Interesse habe ich mich mit der Erkennung von Ziffern in Ersatzteil Zeichnungen beschäftigt.
Ziel ist es, die in der Grafik enthaltenen Ziffern inklusive Koordinaten zu erkennen, um damit eine interaktive Darstellung der Grafik zu implementieren.
Im ersten Versuch habe ich ein paar freie OCR Tools auf die Bilder angesetzt. Die Ergebnisse waren schlecht. Dies hatte verschiedene Gründe:
- Bescheidene Qualität des Bildmaterials
- OCR-Tools sind auf Fließtext optimiert und nicht auf Grafiken, in denen an verschiedenen Stellen nur vereinzelte Zahlen stehen
Ein Bekannter hat mir dann von OpenCV erzählt. Dabei handelt es sich um eine Bibliothek mit Funktionen und Algorithmen zur Bildverarbeitung, Objekterkennung usw.
Es ist eine C-Bibliothek mit Schnittstellen für C, C++, Python und Java. Ich habe das Java JNI Interface genutzt.
Bevor es losgeht schonmal ein Bild mit dem was am Ende herauskommt. Das ist eine alte Explosionszeichnung aus den 50er Jahren. Ich habe diese gescannt und das fertige Programm damit gefüttert.
Erkannte Zahlen sind rot eingerahmt und der Zahlenwert steht darüber. Blau eingerahmte Objekte sind als mögliche Zahl erkannt worden aber brachten keine ausreichende Übereinstimmung:
 |
| Bild 1: Verarbeitete Zeichnung mit erkannten Ziffern |
Wie funktioniert es grundsätzlich?
Inspiriert wurde ich durch folgenden Link:
Abgeleitet aus dem was dort steht soll meine Routine folgendes tun:
- Input Bild laden
- Konturensuche durchführen. Konturen sind geschlossene Linien. Bei der "1" läuft die Kontur ein Mal um die Zahl herum. Eine "6" hat zwei Konturen - aussen herum und der Bauch innen. Eine "8" hat drei Konturen.
- Größenprüfung: Zu große bzw. zu kleine Konturen werden verworfen
- Klassifizierung: Für jede Kontur wird ermittelt, ob und um welche Ziffer es sich handelt.
- Zusammenfassung benachbarter Ziffern: Aus "1" und "0" nebeneinander wird eine "10".
- Erzeugen des Ausgabebildes
Die Klassifizierung erfolgt durch Ermittlung des nearest Neighbours. Diese Methode muss angelernt werden, d.h. es muss zu einer bestimmten Menge Ziffernbilder vorgegeben werden welche Ziffer das Bild zeigt.
Einrichtung Betriebssystem und IDE
Ich nutze Ubuntu 14.04 und Eclipse. Das OpenCV Java Interface habe ich über die Paketverwaltung installiert (2 Pakete):
sudo apt-get install libopencv2.4-java libopencv2.4-jni
In Eclipse legt man am einfachsten eine User Library an. Wie das geht steht hier:
http://docs.opencv.org/doc/tutorials/introduction/java_eclipse/java_eclipse.html
Wenn man wie ich die Standard Ubuntu Pakete verwendet, müssen bei der User Library folgende Pfade eingestellt werden:
JAR: /usr/share/OpenCV/java/opencv-248.jar
Native library location: /usr/lib/jni
Die native library location kann man einstellen, wenn man die angelegte User library aufklappt (im Preferences Dialog). Ich habe das nicht gleich gesehen und das hat etwas Zeit gekostet.
Vorbereitung der Bilder
Nach vielen Versuchen hat sich folgende Vorgehensweise zum Erstellen des Eingabematerials bewährt:
- Scannen der Zeichnung mit 300 DPI, Graustufen
- Festlegen des relevanten Ausschnitts
- Konvertierung in schwarz/weiss Bild mit convert (imagemagick)
peter@gorgonzola:~$ convert seite5.png -threshold 67% 5.png
Die hier gezeigten Bilder haben im Original einen graubraunen leicht gefleckten Hintergrund. Dies führt bei der Konturensuche zu einem enormen Aufwand, da sehr viel kleine Konturen erkannt werden. Durch convert -threshold 67% wird dieser Hintergrund weiss ohne das die Ziffern verschwinden.
Je nach Eingabematerial muss man die Aufbereitung anpassen. Eine Lösung für alles gibt es in diesem Fall nicht.
 |
| Bild 2: Konvertierung Graustufen in S/W mit 67% threshold |
Einlesen des Eingabematerials, Konturensuche
Jetzt kann es losgehen. Das folgende Snippet lädt ein Eingabebild und führt eine Konturensuche durch. Die Konturensuche benötigt ein BINARY image. Da ich S/W-Bilder verwende kann ich diese 1:1 für die Konturensuche verwenden.
1
2
3
4
5
6
7
8
9
10
11
| // OpenCV Library laden - einmalig beim Programmstart
System.loadLibrary( Core.NATIVE_LIBRARY_NAME );
// Input laden (UNCHANGED, da bereits S/W)
Mat image = Highgui.imread(inputFilename, Highgui.CV_LOAD_IMAGE_UNCHANGED);
// Ergebnisliste für Konturensuche
List contours = new ArrayList<>();
// Konturen suchen
Imgproc.findContours(image, contours, new Mat(), Imgproc.RETR_TREE, Imgproc.CHAIN_APPROX_NONE);
|
Hinweis: findContours verändert das übergebene image. Es ist danach mehr oder weniger invertiert. Wenn man also mit dem image im Anschluß noch etwas vor hat, muss man findContours eine Kopie der Mat übergeben:
// Kopie erstellen, da Konturensuche das Eingabebild invertiert
Mat copy = new Mat();
image.copyTo(copy);
Größenprüfung, Extrahierung Teilbild und Weichzeichner
Im Anschluß werden die Konturen durchlaufen und anhand der BoundingBox (kleinstes einschließendes Rechteck) eine Größenprüfung vorgenommen.
Über subMat() werden die Teilbilder der Konturen extrahiert und mittels resize() auf eine fixe Größe gebracht. Die feste Größe ist für die Klassifizierung (Nearest Neighbour) notwendig. Auf die Teilbilder wird ein Gaußscher Weichzeichner angewendet. Durch das Weichzeichnen werden sich die Bilder ähnlicher, da die Kanten verwischen. Dies bringt bei der Klassifizierung bessere Ergebnisse. Wenn der Weichzeichner zu stark eingestellt wird, kommt es aber zu Falscherkennungen, d.h. Kleinteile werden als Ziffern erkannt.
Die besten Einstellungen hängen wieder vom Eingabematerial ab.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| // Größenfilter
Rect sizeFilter = new Rect(new Point(8, 16), new Point(50, 32));
// Feste Größe für Teilbilder
Size digitSize = new Size(15,15);
// Gefundene Konturen durchlaufen
for (Iterator i = contours.iterator(); i.hasNext(); ) {
MatOfPoint contour = i.next();
// Bounding Box der Kontur
Rect box = Imgproc.boundingRect(contour);
// Größenfilter für Kontur
if (box.width < sizeFilter.tl().x ||
box.width > sizeFilter.br().x ||
box.height < sizeFilter.tl().y ||
box.height > sizeFilter.br().y) {
i.remove();
continue;
}
// Einzelbild
Mat subImg = new Mat();
Imgproc.resize(image.submat(box), subImg, digitSize);
// Weichzeichner auf Einzelbild anwenden
blurImage = new Mat();
Imgproc.GaussianBlur(subImg, blurImage, new Size(5,5), 3);
// Einzelbild abspeichern (z.B. zum Anlernen des Nearest Neighbour)
Highgui.imwrite("path/to/image.png", blurImage);
}
|
Anlernen der Nearest Neighbour Klassifizierung
Damit die Teilbilder klassifziert werden können (Erkennung der Ziffer) wird zunächst eine Menge an Teilbildern benötigt, zu den die entsprechende Ziffer vorgegeben wird.
Um dies einfach zu realisieren bin ich folgenden Weg gegangen:
- Erstellung einer Main-Klasse zum Erzeugen von Trainingsbildern
- Konturensuche in allen EIngabebildern.
- Speichern der Teilbilder in einem Unterverzeichnis (train/Nummer des Eingabebildes). Als Dateiname wird eine fortlaufende Nummer verwendet.
- Erzeugung einer Java-Properties Datei unter train/Nummer des Eingabebildes.txt. Diese Properties Datei enthält leere Eigenschaften für alle erzeugten Einzelbilder.
Zum Anlernen öffnet man die properties Datei und notiert dort die Ziffern, die auf den entsprechenden Teilbilder zu sehen sind.
 |
| Bild 3: Einzelbilder nummeriert und Properties Datei mit Ziffern zum Anlernen |
Die Abbildung zeigt die Properties Datei und dahinter den Ordner mit den Einzelbildern. Bild 0 zeigt eine 9, Bild 1 eine 1. Die Bilder 2 bis 7 sind keine Ziffern. Bild 8 zeigt eine 2 usw.
NACHTRAG: Die Abbildung enthält einen Fehler. Bild 0 zeigt keine "9".
Hierzu ist natürlich etwas Basis Programmierarbeit erforderlich auf die ich jetzt nicht weiter eingehe.
Zum Anlernen der Klassifizierung müssen die Informationen aus der Properties Datei zusammen mit den Einzelbildern wieder in OpenCV Matrizes geladen werden (Mat).
Da dies nicht wirklich selbsterklärend ist hier der gesamte Code, um das Model zur Klassifizierung zu erzeugen:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| public CvKNearest getModel() throws Exception {
// Trainingsmaterial einlesen
File trainDir = new File(TRAIN_DIR);
// Mat mit den angelernten Einzelbildern (alle hintereinander)
Mat trainingImages = new Mat();
// Mat mit den entsprechenden Ziffern als double (hintereinander)
Mat trainingLabels = new Mat();
// Verzeichnisse mit Einzelbildern durchlaufen (1 pro Eingabebild)
for (File f: trainDir.listFiles()) {
// Only directories
if (!f.isDirectory())
continue;
// Get imgId from dirname
int imgId = StringHelper.toInt(f.getName());
if (imgId == -1) continue;
// Trainingfile
File propFile = new File(trainDir, imgId + ".txt");
// No trainingfile found => ignore dir
if (!(propFile.isFile())) continue;
// Load training properties
Properties props = new Properties();
props.load(new FileInputStream(propFile));
// List PNGs train/imgid
for (File imgFile: f.listFiles()) {
// Alles ausser png ignorieren
if (!imgFile.getName().endsWith(".png"))
continue;
int trainImgId = StringHelper.getIntFromFileName(imgFile);
if (trainImgId == -1) continue;
// Vorgabewert für Einzelbild
String propValue = props.getProperty(getPropName(trainImgId));
// Einzelbilder ohne Vorgabe ignorieren
if (propValue == null || propValue.isEmpty()) continue;
try {
int propValueInt = Integer.parseInt(propValue);
// Einzelbild laden
Mat imgData = Highgui.imread(imgFile.getAbsolutePath(),
Highgui.CV_LOAD_IMAGE_GRAYSCALE);
// Einzelbild in Mat schreiben (reshape setzt Dimension)
trainingImages.push_back(imgData.reshape(1, 1));
// Vorgabeziffer in Mat schreiben
Mat mat = new Mat(new Size(1,1), CvType.CV_32FC1);
mat.setTo(new Scalar(propValueInt));
trainingLabels.push_back(mat);
} catch (NumberFormatException e) {
// Ignore non int prop values
}
}
}
// Matrixtyp setzen (erforderlich für CvKNearest)
trainingImages.convertTo(trainingImages, CvType.CV_32FC1);
// Model erzeugen
CvKNearest model = new CvKNearest();
// Model anlernen
model.train(trainingImages, trainingLabels);
return model;
}
|
Mit der Anweisung
trainingImages.push_back(imgData.reshape(1, 1));
werden die angelernten Teilbilder in eine große Matrix hintereinander geschrieben. Die Methode CvKNearest.train() erwartet dies so. Zuvor muss noch mit
trainingImages.convertTo(trainingImages, CvType.CV_32FC1);
eine Matrix des richtigen Typs erzeugt werden.
Durchführen der Klassifizierung (Erkennung von Ziffern)
Das angelernte Model kann nun verwendet werden, um Einzelbilder zu klassifizieren. Die Methode CvKNearest.find_nearest() ermittelt dazu zu einem Bild die beste Übereinstimmung aus dem angelernten Material.
Außerdem kann der Abweichungssgrad abgefragt werden. Anhand der Abweichung entscheide ich, ob ich die Ziffer akzeptiere. Bei zu hoher Abweichung zeigt das Bild in der Regel keine Ziffer sondern ein kleines Einzelteil o.ä.
Um die Klassifizierung auszuführen müssen die zu klassifizierenden Bilder wieder hintereinander in eine Matrix geschrieben werden (wie beim Anlernen).
Wie man CvKNearest nutzt und auf die Ergebnisse zugreift sollte in folgendem Beispiel klar werden:
Hinweis: Die Klasse Match ist eine kleine Hilfsklasse, die ein Ergebnis der Konturensuche enthält.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| // Ergebnisse der Klassifizierung (Zahlen)
Mat results = new Mat();
// Abweichungen
Mat distances = new Mat();
// Zu klassifizierende Bilder
Mat samples = new Mat();
// Gefundene Bilder durchlaufen
for (Match box: boxes) {
// Bilder hintereinanderschreiben
samples.push_back(box.img.reshape(1, 1));
}
samples.convertTo(samples, CvType.CV_32FC1);
// Klassifizierung ausführen
model.find_nearest(samples, 1, results, new Mat(), distances);
for (int i=0; i<boxes.size(); i++) {
Match box = boxes.get(i);
// Ergebnis Klassifizierung
double[] digit = results.get(i, 0);
int digitInt = (int) digit[0];
// Abweichung
double[] dists = distances.get(i, 0);
// Prüfung der Abweichung
if (dists[0] > 200000) {
continue; // Zu groß => ignorieren
}
box.digit = digitInt;
}
|
Zusammenfassen von mehrstelligen Zahlen
Dicht nebeneinander stehende Ziffern auf gleicher Höhe müssen zu mehrstelligen Zahlen zusammengefasst werden. Also aus "1" "0" muss eine "10" werden.
Die lässt sich realtiv einfach umsetzen:
- Erkannte Ziffern durchlaufen
- In der Schleife übrige Ziffern durchlaufen und X und Y-Differenz berechnen. Sobald Schwellenwerde unterschritten werden kann man davon ausgehen, dass die Ziffern zusammengehören.
- Box der ersten Ziffer um die Box der zweiten erweitern.
- Erste Ziffer * 10 + zweite Ziffer der ersten Box als Zahl zuweisen
- Zahl bei zweiter Box auf -1 setzen (keine).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| // Gefundene Konturen durchlaufen
for (Match box: boxes) {
// Falls zur Kontur keine Ziffer erkannt wurde => ignorieren
if (box.digit == -1) continue;
// Übrige Konturen durchlaufen
for (Match box2: boxes) {
if (box == box2) continue;
if (box2.digit == -1) continue;
// X-Differenz
double diffX = box.box.tl().x - box2.box.tl().x;
// Schwellenwert X-Differenz
if (diffX < -9 || diffX > 0)
continue;
// Y-Differenz
double diffY = box.box.tl().y - box2.box.tl().y;
// Schwellenwert X-Differenz
if (diffY > 4 || diffY < -4) continue;
// Ziffern gehören zusammen
// Box1 erweitern => Boundingbox für beide Boxes bestimmen
MatOfPoint points = new MatOfPoint(box.box.tl(), box.box.br(),
box2.box.tl(), box2.box.br());
Rect newBox = Imgproc.boundingRect(points);
box.box = newBox;
// Wert berechnen
box.digit = box.digit * 10 + box2.digit;
// Wert aus Box2 entfernen
box2.digit = -1;
}
}
|
Darstellung der Ergebnisse
Im letzten Schritt werden die gefundenen Konturen und die erkannten Ziffern in einem Ausgabebild dargestellt. Man möchte ja auch sehen was das Programm kann.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| // Input laden (FARBE)
Mat image = Highgui.imread(inputFilename, Highgui.CV_LOAD_IMAGE_COLOR);
// Gefundene Konturen druchlaufen
for (int i=0; i<boxes.size(); i++) {
Match box = boxes.get(i);
// Kontur ohne erkannte Ziffer
if (box.digit == -1) {
// Blaues Rechteck
Core.rectangle(image, box.box.tl(), box.box.br(), colorGreen, 2);
} else { // Kontur mit erkannter Ziffer
// Rotes Rechteck
Core.rectangle(image, box.box.tl(), box.box.br(), colorRed, 2);
// Ziffer als Text
Core.putText(image, "" + box.digit, box.box.tl(), Core.FONT_ITALIC,
sizeFilter.tl().y / 20, colorRed, 2);
}
}
// Ausgabebild schreiben
Highgui.imwrite(OUTPUT_DIR + "/" + imgId + ".jpg", image);
|
Offene Probleme
Die Routine hat leider ein paar Schwachstellen, die je nach Eingabematerial mehr oder weniger stark zum Tragen kommen:
- Die Ziffern müssen frei stehen. Wenn z.B. ein Zeigestrich bis an die Zahl heranreicht wird dieser mit in die Kontur einbezogen. Als Lösung kann man die Schwellenwerte für die Konturengröße höher setzen und die entsprechenden Einzelbilder mit Strich anlernen.
Eine andere Lösung ist eine Vorbearbeitung der Eingabebilder bei der man bis an die Zahlen heranreichende Striche kürzt.
- Wenn Ziffern zu dicht zusammen stehen, werden diese ebenfalls zu einer Kontur zusammen gefasst. Auch hier kann man durch Erhöhung der Schwellenwerte und Anlernen des entsprechenden Einzelbildes eine Lösung erreichen.
- Sobald die Ziffern in größere Teile hineinragen scheitert die Routine ebenfalls.
Ein weiteres Problem sind alle Pixelangaben im Programm. Diese korrespondieren natürlich mit der Schriftgröße im Eingabematerial. Folgende Pixelangaben müssen in Abhängigkeit der Zifferngröße in Pixel angepasst werden:
- Größenfilter für Bounding Boxes
- Größe der Einzelbilder für CvKNearest
- Einstellung für Weichzeichner. Je größer die Ziffern sind, um so stärker kann der Weichzeichner eingestellt werden.
- Toleranzschwellen (x/y) zum Zusammenfassen von Ziffern.
- Toleranzschwelle für Abweichungsgrad. Je größer die Einzelbilder sind, um so höher werden die Abweichungen bei gleicher Ähnlichkeit. Möglicherweise wird die Abweichung pro Pixel quadriert und aufsummiert bzw. etwas vergleichbares.
Daher muss der Schwellenwert erhöht werden sobald die Einzelbildgröße erhöht wird.
In einem ersten Schritt könnte man dem Programm die Schriftgröße in Pixel als Parameter mitgeben und die übrigen Einstellungen und Schwellenwerte werden daraus ermittelt. Das wäre ein Anfang.
Zur Erkennung nicht 100% frei stehender Ziffern ist mir auch noch etwas eingefallen: Sobald die Bounding Box für eine Ziffer deutlich zu groß ist, werden die 4 Ecken in Zifferngröße weiterverarbeitet. Mit dieser Lösung würde man zusammenstehende mehrstellig Zahlen trennen (zumindest 2-stellige). Falls von einer Seite ein Strich o.ä. bis an die Zahl reicht würde man diesen ebenfalls abschneiden.
Diese Idee werde ich bei Gelegenheit auf jeden Fall noch einarbeiten.
Fazit
Damit die hier gezeigte Erkennung gut arbeitet, braucht man eine größere Anzahl Eingabebilder mit sehr ähnlichem Schriftbild. Die Ziffern müssen frei stehen.
Ich habe mit vier Beispielbildern gearbeitet. Ich musste allerdings bei diesen Bildern ein paar Striche retuschieren, da diese bis an die Ziffern reichten.
Bild 1 und 2 habe ich komplett manuell klassifiziert und damit das CvKNearest Model angelernt.
Bei Bild 3 (siehe 1. Bild im Blog oben) betrug die Erkennungsrate gut 90%. Man sieht, dass einige mehrstellige Ziffern als eine Kontur erkannt und damit nicht klassifiziert wurden.
Bei Bild 4 wurden alle Ziffern erkannt - also 100%.
 |
| Bild 4: 100% Erkennung ohne Vorgabe |
Man kann die Verfahrensweise bestimmt noch an der ein oder anderen Stelle verbessern. Mal schauen ob daraus ein Projekt wird.
Auf jeden Fall ein spannendes Thema.
Wer bis hierhin durchgehalten hat: Vielen Dank für Euer Interesse und bis bald ...
Haltet durch!
1. Verbesserung - Aufteilen übergroßer Konturen
Sobald Ziffern nicht 100% freistehen treten die folgenden Probleme auf:
- Sich berührende mehrstellige Ziffern werden als eine Kontur erkannt und müssen manuell klassifiziert werden.
- Falls Striche o.ä. eine Ziffer berühren wird die Kontur ebenfalls erweitert und die Klassifizierung erschwert bzw. unmöglich.
Um diese Fehler zu reduzieren habe ich die Größenprüfung der Konturen umgearbeitet:
- Zu kleine Konturen werden verworfen (zu klein für eine Ziffer)
- Konturen die 30% breiter als die eingestellte Ziffernbreite und/ oder 30% höher als die eingestellte Ziffernhöhe sind werden geteilt und einzeln verarbeitet.
- Je nach Überschreitung werden 4 Eckbereiche, Links/Rechts oder Oben/Unten getrennt.
 |
| Bild 5: Aufgeteilte Kontur - linker und rechter Bereich |
Das Bild zeigt die Ziffern der 36. Diese berühren sich und werden daher als eine gesamte Kontur gefunden. Da die Breite der Bounding-Box mehr als 30% über der eingestellten Ziffernbreite (hier 16 Pixel liegt), die Höhe der Bounding-Box jedoch nicht diesen Schwellenwert überschreitet wird die Box in den linken und rechten Bereich geteilt und getrennt verarbeitet.
Nach der Klassifizierung wurden die Ziffern wieder zur 36 vereint, da die Boxes als zusammengehörend erkannt wurden (erkennbar am roten und blauen Rahmen sowie den roten Ziffern).
Im Test brachte diese Verbesserung sehr gute Resulate. Die Erkennungsrate in den beiden unbekannten Bildern liegt jetzt bei 100%.
2. Verbesserung - Erneute Konturensuche in den geteilten Konturen
Um die Erkennung noch weiter zu verbessern könnte in den mit Verbesserung 1 aufgeteilten Bereichen eine erneute Konturensuche durchgeführt werden.
Sobald Ziffern durch Striche o.ä. mit größeren Objekten verbunden sind, wird die Gesamtkontur zwar in die 4 Ecken geteilt, jedoch befindet sich dort nicht unbedingt die Ziffer.
Diese befindet sich wahrscheinlich in einem der 4 Randstreifen und müsste dort mit einer erneuten Konturensuche gefunden werden.
 |
| Bild 6: Randbereiche (rot) einer übergroßen Kontur in denen eine neue Konturensuche gemacht werden müsste |
Diese Verbesserung habe ich noch nicht umgesetzt. Es besteht auch das Risiko, dass sich in den Randbereichen weitere Ziffern befinden, die nicht zu der Konture gehören aus der die Bounding-Box ermittelt wurde.
Diese werden dann doppelt gefunden und müssten aussortiert werden.
