Code 39 Barcode-Scanner

Der 1974 entwickelte Code 39 ist eine der am häufigsten verwendeten Symbologien oder Typen von Barcodes, obwohl das UPC / EAN-System im Einzelhandel am häufigsten verwendet wird. Code 39-Barcodes können Großbuchstaben, Zahlen und einige Symbole codieren und lassen sich mit einer speziellen Schriftart problemlos von Computersoftware aus drucken. Dies führte zu ihrer weit verbreiteten kommerziellen und industriellen Verwendung (z. B. Firmenausweise, Asset Tracking, Fabrikautomation).

Erstellen Sie das kürzeste Programm oder die kürzeste Funktion zum Lesen eines Code 39-Barcodes in einer beliebigen Ausrichtung aus einem 512 x 512 Pixel großen Graustufenbild. Der Barcode ist möglicherweise nicht horizontal oder vertikal ausgerichtet.

• Ihr Programm muss ein Standardbilddateiformat akzeptieren und die im Barcode codierten Daten als Standardausgabe- oder -rückgabewert erzeugen (ohne Start- / Stoppzeichen).
• Kein Bild enthält mehr als einen gültigen Code 39-Barcode, und kein Barcode codiert ein Leerzeichen (ASCII 32).
• Wenn im Bild kein gültiger Code 39-Barcode angezeigt wird, muss das Programm ein einzelnes Fragezeichen ( ?) ausgeben .

Ich habe eine JavaScript-Referenzimplementierung und eine Testsuite von Bildern im PNG-Format vorbereitet , sowohl mit gültigen als auch ohne gültigen Barcodes. Die Referenzimplementierung, bei der in den neuesten Webbrowsern nur 3 von 46 Testfällen fehlschlagen, soll einen möglichen Decodierungsalgorithmus aufzeigen, der der obigen Spezifikation nicht strikt entspricht.

Eine gültige Einreichung besteht mindestens 80% dieser Tests (37/46) und dauert nicht länger als eine Minute für jedes Bild auf einer relativ schnellen CPU (z. B. 2,6-GHz-Quad-Core). Meine Referenzimplementierung besteht 93% der Tests und verarbeitet jedes Bild innerhalb von 10 Sekunden (auf meinem Desktop-PC mit Google Chrome).

(Diese Frage wurde am 28. Mai 2011 auf Meta vorgeschlagen .)

Python, 899 Zeichen

import sys,random
raw_input()
X,Y=map(int,raw_input().split())
input()
I=[' x'[v<'~']for v in sys.stdin.read()]
M={196:' ',168:'$',148:'*',388:'.',52:'0',97:'2',49:'4',112:'6',292:'8',73:'B',25:'D',88:'F',268:'H',28:'J',67:'L',19:'N',82:'P',262:'R',22:'T',193:'V',145:'X',208:\
'Z',42:'%',138:'+',133:'-',162:'/',289:'1',352:'3',304:'5',37:'7',100:'9',265:'A',328:'C',280:'E',13:'G',76:'I',259:'K',322:'M',274:'O',7:'Q',70:'S',385:'U',448:'W'\
,400:'Y'}
N=500
for w in' '*30000:
 a,b,c,d=eval('random.random(),'*4);A=''.join(I[int((a+(c-a)*i/N)*X)+X*int((b+(d-b)*i/N)*Y)]for i in range(N)).lstrip();T=A.count(' x')+1;K=A.count('x')/T;L=A.count\
(' ')/T;s='';z=c=0
 while A:
  z*=2;y=A.find(' ')
  if y<0:y=len(A)
  z+=y>K;A=A[y:]
  z*=2;y=A.find('x')
  if y<0:y=len(A)
  z+=y>L;A=A[y:];c+=2
  if c>9:
   if z/2in M:s+=M[z/2];z=c=0
   else:break
 if s and'*'==s[0]and'*'==s[-1]and'*'!=s:print s[1:-1];break

Dieser Code verwendet ein Bild im PNM-Format als Eingabe, daher führe ich es normalerweise folgendermaßen aus:

pngtopnm s01.png | ./barcode.py

Der Code selbst wählt nur viele zufällige Scanlinien aus und versucht, die Schwarz-Weiß-Läufe auf dieser Scanlinie mit den Code39-Mustern abzugleichen. Es ist zufällig angeordnet, sodass gelegentlich keine Barcodes gefunden werden können. (Ich erhalte eine falsch negative Fehlerrate von etwa 20% für die Testbilder.) Wenn dies fehlschlägt, dauert die Ausführung etwa eine Minute. Wenn dies erfolgreich ist, geschieht dies häufig viel schneller. Ich habe noch nie ein falsches Positiv gesehen.