EAN-13 Barcodes

Neulich waren QRCodes und Datamatrix-Codes bei mir Thema.
Doch wie sieht es mit den älteren und am weitesten verbreiteten Barcodes aus?

Hier finde ich im OpenSource Bereich nur “böse” LGPL Varianten, oder Komponenten mit Abhängigkeiten zu OpenCV und Schlimmeren.

Natürlich kommt dann die Frage auf: Kann man das auch selbst schreiben?

Barcodes gab es offenbar schon viele und bevor ich mich zu weit wo verlaufe, dachte ich, fange ich mal mit dem an, was auf jedem und zwar wirklich jedem Artikel im Kaufhaus klebt: Ein EAN-13 Barcode.

EAN-13

Diese Art von Barcodes kann 13 Ziffern kodieren, und steht für “European Article Number”, die aber inzwischen weltweit für Artikel benutzt werden.
Jede Ziffer wird durch 7 Bits definiert, wobei eine Null einem weißen und eine Eins einem schwarzen Block entspricht. Je nachdem wie die Bits gesetzt sind, werden die finalen Striche und Abstände damit breiter oder schmaler.

Eingeleitet wird ein EAN13 Code auf beiden Seiten mit den Bits 101, woraus sich zwei dünne Striche an den Rändern abbilden, die in der Regel auch nach unten hin länger gezeichnet werden.
So definiert sich die Breite eines einzelnen Bits und alle folgenden Abstände und Strichdicken sind ein ganzzahliges Vielfaches davon.
Es ist auch definiert, dass vor und nach dem Barcode ein weißer Rand freigelassen werden muss, um den Barcode von der Umgebung abzuheben.

In der Mitte befindet sich ein 5-Bit breiter Separator nach dem Schema 01010, was dort ebenso zu zwei dünnen Strichen führt, die ebenso nach unten länger gezeichnet werden.

Links und rechts von der Mitte werden jeweils 6 Ziffern durch die 7 Bit breite Strichmuster abgebildet. Man ließt also über die Strich bzw. Abstandsbreite 7 Bits aus und sieht in einer Mapping-Tabelle nach, welche Ziffer sich dahinter verbirgt. Doch dadurch kommt man erst auf 12 Ziffern in Summe. Die 13. Ziffer ergibt sich aus dem Muster der im Linken Block stehenden 6 Ziffern. Denn hier gibt es zwei Code-Tabellen (A und B), die zum Einsatz kommen können und je nach Kombination, welche Tabelle benutzt wurde, ergeben sich weitere 6 Bits und aus diesen 6 Bits lässt sich die 13. Ziffer ableiten.

Man scannt also die Bits der linken Hälfte und schaut nach, ob die Bits in Tabelle A oder B vorkommen. Wenn man einen Treffer in A hat, nutzt man die Ziffer und merkt sich eine Null als Bit. Andernfalls sieht man in B nach, nutzt die Ziffer von dort, und notiert sich eine Eins. Am Ende hat man 6 Bits gesammelt, die man über eine Zusatztabelle in eine Ziffer umwandeln kann. Diese Zahl wird übrigens dem EAN13-Code voran gestellt. Es ist eigentlich die erste Ziffer, danach folgen die 6 Ziffern der linken und abschließend die 6 Ziffern der rechten Hälfte.

Die rechte Seite benutzt nur eine einzige Bit-Mapping-Tabelle (C) und kann damit am einfachsten ausgelesen werden.

Zu erwähnen wäre noch, dass bei den linken Codes das höchste (== erste) Bit immer Null ist, während auf der rechten Seite das niedrigste (== letzte) Bit stets eine Null aufweist.

Im Sourcecode sehen die Tabellen bei mir etwa so aus:

 /* first number encoding table for left side */
 static gate_uint8_t const EAN13_CODETABLE_A[] = {
         0b00001101,        /* 0 */
         0b00011001,        /* 1 */
         0b00010011,        /* 2 */
         0b00111101,        /* 3 */
         0b00100011,        /* 4 */
         0b00110001,        /* 5 */
         0b00101111,        /* 6 */
        0b00111011,        /* 7 */
        0b00110111,        /* 8 */
        0b00001011         /* 9 */
};

/* second number encoding table for left side */
static gate_uint8_t const EAN13_CODETABLE_B[] = {
        0b00100111,        /* 0 */
        0b00110011,        /* 1 */
        0b00011011,        /* 2 */
        0b00100001,        /* 3 */
        0b00011101,        /* 4 */
        0b00111001,        /* 5 */
        0b00000101,        /* 6 */
        0b00010001,        /* 7 */
        0b00001001,        /* 8 */
        0b00010111         /* 9 */
};

/* number encoding table for right side */
static gate_uint8_t const EAN13_CODETABLE_C[] = {
        0b01110010,        /* 0 */
        0b01100110,        /* 1 */
        0b01101100,        /* 2 */
        0b01000010,        /* 3 */
        0b01011100,        /* 4 */
        0b01001110,        /* 5 */
        0b01010000,        /* 6 */
        0b01000100,        /* 7 */
        0b01001000,        /* 8 */
        0b01110100         /* 9 */
};

/* left-table (A or B) usage pattern for very first digit */
static gate_uint8_t const EAN13_PATTERNTABLE_LEFT[] =
{
        0b00000000,        /* 0 */
        0b00001011,        /* 1 */
        0b00001101,        /* 2 */
        0b00001110,        /* 3 */
        0b00010011,        /* 4 */
        0b00011001,        /* 5 */
        0b00011100,        /* 6 */
        0b00010101,        /* 7 */
        0b00010110,        /* 8 */
        0b00011010,        /* 9 */
};

Implementierungsansatz

Nun, ich habe weiß Gott keine große Erfahrung mit Bildverarbeitung und manche bestehende OpenSource Libs nutzen OpenCV für die Stricherkennung.
Doch … ein bisschen nachgedacht, stellt sich raus, dass es keine Raketenwissenschaft ist.

1. Man wandelt ein Bild mit einem Barcode in eine Monochrom-Grafik um.
2. Dann läuft man in einer Zeile die Pixel durch und zählt die Anzahl der gleichfarbigen Pixel als “Längen” und füllt damit ein Array von Weiß-Schwarz Übergängen.
3. Das Array beinhaltet nun potentielle Strich- und Abstand-Längen.
4. Nun sucht man die kürzeste Strichlänge als kleinsten Wert im Array und nutzt ihn als Referenz.
5. Jetzt werden alle Längen durch die Referenz-Länge dividiert. Das Resultat ist ein neues Array von der mit der Anzahl an gleichen aufeinander folgenden Bits. (Man sollte hierbei ein paar Toleranzen bei der Rundung von Fließkommazahlen einbauen).
6. Aus den Längen wird nun ein Array von Bits aufgebaut. z.B.: { W:8, S:1, W:1, S:1, W:2, S:3 } würde dann zu 0000000010100111
7. Nun sucht man nach dem Muster 01010 und geht davon aus, dass es der Beginn eines EAN13-Barcodes ist.
8. Nun kann man nach dem einleitenden 0101 jeweils 6 mal 7 Bits mit den Code-Mapping-Tabellen der Linken Seite abgleichen. Dann erwartet man erneut ein 01010 und danach werden die 6 Ziffern der rechten Hälfte dekodiert.
9. Wird ein Bitmuster nicht erkannt, kann man nach einer späteren 01010 Sequenz suchen und dort erneut zu lesen probieren oder man erhöht die Referenzbreite eines Streifens und beginnt wieder bei Punkt 5.

Fazit

Tatsächlich funktioniert mein Ansatz prototypisch und nun kann ich mit meiner Webcam Barcodes aus Artikeln auslesen.

Die Sache mit der Längen-Ausdividierung erforderte ein paar Experimente. Denn bei geringeren Auflösungen oder Unschärfe, werden auch gleich breite Striche nicht immer in die exakt gleiche Anzahl an Pixel übersetzt. Und dickere Striche und Abstände sind kein exaktes Vielfaches einer Referenzbreite.
Man braucht also immer einen “Spielraum” und ein paar Versuche mit einer anwachsenden Referenzbreite, bis der gesamte Barcode fehlerfrei ausgelesen werden kann.

In Summe bin ich aber zufrieden. Etwa 300 Zeilen purer C Code im GATE Projekt haben gereicht, um provisorisch EAN13 Barcodes auslesen zu können. Und daraus lassen sich ISBN Nummern von Büchern und vieles mehr generieren.

Ich denke … ich sollte die Codebase irgendwie mal auf ein Android Phone bringen und dann im Supermarkt mal Scanexperimente starten um zu sehen, wie gut oder schlecht das nun wirklich funktioniert.

However … wieder etwas gelernt … und eine mögliche Karriere als Kassenprogrammierer ist nun auch etwas näher gerückt.