Wie funktioniert der Barcode?

    Hi, Habr!

    Der moderne Mensch sieht sich jeden Tag Barcodes gegenüber, ohne darüber nachzudenken. Wenn wir Produkte im Supermarkt kaufen, werden deren Codes mit einem Barcode gelesen. Auch Pakete, Waren in Lagerhäusern und so weiter und so fort. Nur wenige wissen, wie es wirklich funktioniert.

    Wie funktioniert der Barcode und was ist in diesem Bild verschlüsselt?



    Versuchen wir es herauszufinden, gleichzeitig schreiben wir einen Decoder solcher Codes.

    Einleitung


    Die Verwendung von Barcodes hat eine lange Geschichte. Die ersten Automatisierungsversuche begannen in den 50er Jahren, ein Patent für einen Codeleser wurde 1952 erteilt. Der Ingenieur, der an der Sortierung von Autos auf der Eisenbahn beteiligt war, wollte den Prozess vereinfachen. Die Idee war naheliegend - eine Zahl mit Streifen zu kodieren und mit Fotozellen zu lesen. Im Jahr 1962 wurden die Codes offiziell zur Identifizierung von Waggons der amerikanischen Eisenbahnen ( KarTrak- System) verwendet), wurde der Scheinwerfer 1968 durch einen Laserstrahl ersetzt, der die Genauigkeit erhöhte und die Größe des Lesers reduzierte. 1973 erschien das „Universal Product Code“ -Format, und 1974 wurde das erste Produkt mit Hilfe des Codescanners (Wrigleys Kaugummi - dies sind die Vereinigten Staaten;) im Supermarkt verkauft. 1984 benutzte ein Drittel der Läden Streches, in Russland wurden sie etwa in den 90er Jahren verwendet.

    Für verschiedene Aufgaben werden mittlerweile viele verschiedene Codes verwendet. Die Sequenz „12345678“ kann beispielsweise so dargestellt werden (und das ist noch nicht alles):



    Beginnen wir mit einer bitweisen Analyse. Alles, was im Folgenden geschrieben wird, bezieht sich auf den Typ „Code-128“ - einfach, weil das Format recht einfach und unkompliziert ist. Diejenigen, die mit anderen Arten experimentieren möchten, können sich öffnenOnline-Generator und überzeugen Sie sich selbst.

    Auf den ersten Blick scheint der Barcode nur eine zufällige Folge von Zeilen zu sein, seine Struktur ist eindeutig festgelegt:



    1 - Der leere Bereich, der erforderlich ist, um den Anfang des Codes eindeutig zu definieren.
    2 - Das Startsymbol. Für Code-128 gibt es 3 Optionen (A, B und C genannt): 11010000100, 11010010000 oder 11010011100, die verschiedenen Codetabellen entsprechen (weitere Informationen finden Sie unter Wikipedia ).
    3 - Tatsächlich der Code, der die Daten enthält, die wir benötigen
    4 - Checksum
    5 - Stop-Symbol. Für Code-128 ist dies 1100011101011.
    6 (1) - Leerer Speicherplatz.

    Nun, wie die Bits codiert sind. Es ist alles sehr einfach - wenn Sie die Breite der dünnsten Linie für "1" wählen, dann ergibt die Linie mit doppelter Breite den Code "11", dreifach "111" und so weiter. Der leere Speicherplatz wird nach dem gleichen Prinzip "0" oder "00" oder "000" sein. Interessenten können den Startcode im Bild vergleichen, um sicherzustellen, dass die Regel erfüllt wird.

    Nun können Sie mit der Programmierung beginnen.

    Holen Sie sich die Bitfolge


    Im Prinzip ist dies der schwierigste Teil, und er kann algorithmisch natürlich auf verschiedene Arten implementiert werden. Ich bin nicht sicher, ob der unten stehende Algorithmus optimal ist, aber für ein Lernbeispiel ist das ausreichend.

    Laden Sie zunächst das Bild, dehnen Sie es in der Breite, nehmen Sie eine horizontale Linie von der Bildmitte aus, konvertieren Sie es in Schwarzweiß und laden Sie es in ein Array.

    from PIL import Image
    import numpy as np
    import matplotlib.pyplot as plt
    image_path = "barcode.jpg"
    img = Image.open(image_path)
    width, height = img.size
    basewidth = 4*width
    img = img.resize((basewidth, height), Image.ANTIALIAS)
    hor_line_bw = img.crop((0, int(height/2), basewidth, int(height/2) + 1)).convert('L')
    hor_data = np.asarray(hor_line_bw, dtype="int32")[0]
    

    Beim Barcode entspricht Schwarz „1“ und bei RGB 0 (umgekehrt), so dass das Array invertiert werden muss. Gleichzeitig berechnen wir den Durchschnittswert.

    hor_data = 255 - hor_data
    avg = np.average(hor_data)
    plt.plot(hor_data)
    plt.show()
    

    Führen Sie das Programm aus, um sicherzustellen, dass der Barcode korrekt geladen ist:



    Jetzt müssen Sie die Breite eines Bits bestimmen. Dazu markieren wir den Beginn der Startsequenz „1101“ und zeichnen die Momente auf, in denen der Graph die Mittellinie kreuzt.

    pos1, pos2 = -1, -1
    bits = ""for p in range(basewidth - 2):
        if hor_data[p] < avg and hor_data[p + 1] > avg:
            bits += "1"if pos1 == -1:
                pos1 = p
            if bits == "101":
                pos2 = p
                breakif hor_data[p] > avg and hor_data[p + 1] < avg:
            bits += "0"
    bit_width = int((pos2 - pos1)/3)
    

    Wir schreiben nur die Übergänge durch die Mitte, so dass der Code "1101" als "101" geschrieben wird. Dies reicht jedoch aus, um die Breite in Pixel zu ermitteln.

    Nun die eigentliche Dekodierung. Wir finden den nächsten Übergang durch die Mitte und bestimmen die Anzahl der Bits, die in das Intervall fallen. Da die Übereinstimmung nicht absolut ist (der Code kann leicht gebogen oder gestreckt sein), verwenden wir eine Rundung.

    bits = ""for p in range(basewidth - 2):
        if hor_data[p] > avg and hor_data[p + 1] < avg:
            interval = p - pos1
            cnt = interval/bit_width
            bits += "1"*int(round(cnt))
            pos1 = p
        if hor_data[p] < avg and hor_data[p + 1] > avg:
            interval = p - pos1
            cnt = interval/bit_width
            bits += "0"*int(round(cnt))
            pos1 = p
    

    Nicht sicher, dass dies die beste Option ist, vielleicht gibt es einen besseren Weg, jeder kann in die Kommentare schreiben.

    Wenn alles richtig gemacht wurde, erhalten wir ungefähr folgende Ausgabe:

    11010010000110001010001000110100010001101110100011011101000111011011
    01100110011000101000101000110001000101100011000101110110011011001111
    00010101100011101011


    Dekodierung


    Es gibt grundsätzlich keine Schwierigkeiten, nein. Die Zeichen in Code-128 sind mit einem 11-Bit-Code codiert, der 3 Variationen (A, B und C) aufweist und entweder unterschiedliche Zeichencodierungen oder Zahlen von 00 bis 99 speichern kann.

    In unserem Fall ist der Beginn der Sequenz 11010010000, was „Code B ". Bei der manuellen Eingabe aller Codes aus Wikipedia war es furchtbar, dass die Tabelle einfach aus dem Browser kopiert wurde und das Parsing auch in Python durchgeführt wurde (Hinweis: Sie müssen dies in der Produktion nicht tun).

        CODE128_CHART = """
            0	_	_	00	32	S	11011001100	212222
            1	!	!	01	33	!	11001101100	222122
            2	"	"	02	34	"	11001100110	222221
            3	#	#	03	35	#	10010011000	121223
            ...
            93	GS	}	93	125	}	10100011110	111341
            94	RS	~	94	126	~	10001011110	131141
            103	Start Start A	208	SCA	11010000100	211412
            104	Start Start B	209	SCB	11010010000	211214
            105	Start Start C	210	SCC	11010011100	211232
            106	Stop Stop	-	- -	11000111010	233111""".split()
        SYMBOLS = [value for value in CODE128_CHART[6::8]]
        VALUESB = [value for value in CODE128_CHART[2::8]]
        CODE128B = dict(zip(SYMBOLS, VALUESB))
    

    Nun ist das einfachste übrig. Wir teilen unsere Bitsequenz in 11-stellige Blöcke auf:

    sym_len = 11
    symbols = [bits[i:i+sym_len] for i in range(0, len(bits), sym_len)]
    

    Zum Schluss bilden wir eine Zeichenfolge und zeigen sie auf dem Bildschirm an:

    str_out = ""for sym in symbols:
        if CODE128A[sym] == 'Start':
            continueif CODE128A[sym] == 'Stop':
            break
        str_out += CODE128A[sym]
        print("  ", sym, CODE128A[sym])
    print("Str:", str_out)
    

    Die Antwort auf das, was in der Tabelle verschlüsselt ist, wird nicht gegeben. Lassen Sie es sich als Hausaufgabe für den Leser betrachten (die Verwendung vorgefertigter Programme für Smartphones wird als Betrug angesehen :).

    Der Code implementiert auch keine CRC-Prüfung, jeder kann es selbst tun.

    Natürlich ist der Algorithmus unvollkommen und wurde in einer halben Stunde geschrieben. Für professionellere Zwecke gibt es fertige Bibliotheken, zum Beispiel pyzbar . Code, der eine solche Bibliothek verwendet, erfordert nur vier Zeilen:

    from pyzbar.pyzbar import decode
    img = Image.open(image_path)
    decode = decode(img)
    print(decode)
    

    (Sie müssen zuerst die Bibliothek installieren, indem Sie den Befehl "pip install pyzbar" eingeben.)

    Zusatz : Der Benutzer vinograd19 schrieb über die CRC-Berechnung in den Kommentaren : Der

    Prüfziffernverlauf ist interessant. Es entstand evolutionär.
    Die Prüfziffer wird benötigt, um eine falsche Dekodierung zu vermeiden. Wenn der Barcode 1234 war und als 7234 erkannt wurde, ist eine Validierung erforderlich, die die Ersetzung von 1 durch 7 verhindert. Die Validierung kann ungenau sein, so dass mindestens 90% der ungültigen Zahlen vorab festgelegt werden.

    1. Ansatz: Nehmen wir einfach den Betrag. Der Rest der Division durch 10 war 0. Nun, das heißt, die ersten 12 Zeichen tragen die Informationslast, und die letzte Ziffer wird so gewählt, dass die Summe der Ziffern durch 10 geteilt wird dies noch einmal. Beispielsweise ist Code 1234 gültig. 1 + 2 + 3 + 4 = 10. Der Code 1216 ist ebenfalls gültig, aber 1218 nicht.

    Dadurch werden Probleme mit der Automatisierung vermieden. Zum Zeitpunkt der Erstellung von Barcodes gab es jedoch einen Fallback in Form des Füllens der Nummer auf den Tasten. Und es gibt einen schlimmen Fall: Wenn Sie die Reihenfolge von zwei Ziffern ändern, ändert sich die Prüfsumme nicht, und dies ist schlecht. Das heißt, wenn der Barcode 1234 als 2134 eingegeben wurde, konvergiert die Prüfsumme, aber die Anzahl, die wir erhalten haben, ist falsch. Es stellt sich heraus, dass die Reihenfolge der Zahlen falsch ist - dies ist ein üblicher Fall, wenn Sie die Tasten schnell anschlagen.

    2. Ansatz Nun, machen wir den Betrag etwas komplizierter. So werden die Zahlen an geraden Stellen doppelt gezählt. Wenn Sie die Reihenfolge ändern, konvergiert der Betrag einfach nicht zum gewünschten Wert. Beispielsweise ist Code 2364 gültig (2 + 3 + 3 + 6 + 4 + 4 = 20) und Code 3264 ist ungültig (3 + 2 + 2 + 6 + 4 + 4 = 19). Dies stellte sich jedoch als weiteres schlechtes Beispiel für Vbitiya heraus. Einige Tastaturen haben zehn Zahlen, die in zwei Reihen angeordnet sind. Die erste Zeile ist 12345 und darunter die zweite zweite Zeile 67890. Wenn Sie anstelle der Taste "1" die Taste "2" nach rechts drücken, werden Sie durch die Prüfsumme vor falscher Eingabe gewarnt. Wenn Sie jedoch anstelle der Taste "1" unten die Taste "6" drücken, werden Sie möglicherweise nicht gewarnt. Immerhin ist 6 = 1 + 5, und wenn diese Zahl bei der Berechnung der Prüfsumme an einer geraden Stelle liegt, gilt 2 * 6 = 2 * 1 + 2 * 5. Das heißt, die Prüfsumme hat genau um 10 zugenommen, so dass sich die letzte Zahl nicht geändert hat. Beispielsweise sind die Prüfsummen Kodv 2134 und 2634 gleich. Der gleiche Fehler tritt auf, wenn anstelle von 2 die Taste 7 und anstelle von 3 die Taste 8 usw. gedrückt wird.

    3. Ansatz Ok, lass uns noch einmal etwas machen, nur die Zahlen an geraden Stellen werden berücksichtigt ... dreimal. Das heißt, der Code 1234565 ist gültig, weil 1 + 2 * 3 + 3 + 4 * 3 + 5 + 6 * 3 + 5 = 50.

    Die beschriebene Methode wurde zum Standard für die Berechnung der EAN13-Prüfsumme mit geringfügigen Korrekturen: Die Anzahl der Ziffern wurde festgelegt und 13 Dabei ist die 13. die gleiche Prüfziffer. Zahlen an ungeraden Stellen werden dreimal gezählt, an geraden Stellen - einmal.


    Fazit


    Wie Sie sehen, ist selbst ein so einfacher Vorgang wie ein Barcode sehr interessant. Übrigens, ein weiterer Hacker für diejenigen, die hier lesen - der Text unter dem Barcode (falls vorhanden) kopiert seinen Inhalt vollständig. Dies geschieht, damit der Bediener den Code bei unlesbarem Code manuell eingeben kann. Daher ist es normalerweise leicht, den Inhalt eines Barcodes zu finden. Schauen Sie sich einfach den darunter liegenden Text an.

    Wie in den Kommentaren angedeutet, ist der EAN-13-Code der beliebteste Code im Handel, die Bit-Codierung ist dort gleich und jeder kann die Struktur von Symbolen selbst sehen .

    Wenn die Leser das Interesse nicht verloren haben, können QR-Codes gesondert berücksichtigt werden.

    Vielen Dank für Ihre Aufmerksamkeit.

    Jetzt auch beliebt: