Skaner kodów kreskowych Code 39

Kod 39 , opracowany w 1974 r., Jest jedną z najczęściej używanych symboli kodów kreskowych, chociaż jest to system UPC / EAN najczęściej spotykany w sprzedaży detalicznej. Kody kreskowe Code 39 mogą kodować wielkie litery, cyfry i niektóre symbole i są łatwe do wydrukowania z oprogramowania komputerowego za pomocą specjalnej czcionki. Doprowadziło to do ich powszechnego zastosowania komercyjnego i przemysłowego (np. Identyfikatory firmowe, śledzenie zasobów, automatyzacja fabryki).

Utwórz najkrótszy program lub funkcję do odczytu kodu kreskowego Code 39 w dowolnej orientacji z obrazu w skali szarości 512 x 512 pikseli; kod kreskowy może nie być wyrównany poziomo lub pionowo.

• Twój program musi zaakceptować standardowy format pliku obrazu i wygenerować dane zakodowane w kodzie kreskowym jako jego standardową wartość wyjściową lub zwracaną (bez uwzględnienia żadnego znaku start / stop).
• Żaden obraz nie zawiera więcej niż jednego poprawnego kodu kreskowego Code 39 i żaden kod kreskowy nie koduje znaku spacji (ASCII 32).
• Jeśli na obrazie nie pokazano prawidłowego kodu kreskowego Code 39, program musi wygenerować pojedynczy znak zapytania ( ?).

Przygotowałem implementację referencji JavaScript i pakiet testowy obrazów w formacie PNG, zarówno z poprawnymi kodami kreskowymi, jak i bez nich. Implementacja referencyjna, która nie spełnia tylko 3 z 46 przypadków testowych w najnowszych przeglądarkach internetowych, ma na celu pokazanie jednego możliwego algorytmu dekodowania, a nie ścisłą zgodność z powyższą specyfikacją.

Prawidłowe przesłanie przechodzi co najmniej 80% tych testów (37/46) i zajmuje to nie więcej niż jedną minutę dla każdego obrazu na stosunkowo szybkim procesorze (np. Czterordzeniowy procesor 2,6 GHz). Moja referencyjna implementacja przechodzi 93% testów i przetwarza każdy obraz w ciągu 10 sekund (na moim komputerze stacjonarnym z Google Chrome).

(To pytanie zostało zaproponowane Meta w dniu 28 maja 2011 r.)

Python, 899 znaków

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

Ten kod pobiera obraz w formacie PNM jako dane wejściowe, więc zwykle uruchamiam go w następujący sposób:

pngtopnm s01.png | ./barcode.py

Sam kod po prostu wybiera wiele losowych linii skanowania i próbuje dopasować czarno-białe przebiegi na tej linii do wzorców kodu39. Jest losowy, więc czasami może nie znaleźć kodów kreskowych. (Otrzymuję około 20% odsetek fałszywie ujemnych błędów na obrazach testowych.) Gdy się nie powiedzie, uruchomienie zajmuje około minuty, a gdy się powiedzie, często robi to o wiele szybciej. Nigdy nie widziałem fałszywie pozytywnego wyniku.