Code 39 Barcode Scanner

El Código 39 , desarrollado en 1974, es una de las simbologías o tipos de códigos de barras más comúnmente utilizados, aunque es el sistema UPC / EAN que se ve con mayor frecuencia en las ventas minoristas. Los códigos de barras del código 39 pueden codificar letras mayúsculas, números y algunos símbolos, y son triviales para imprimir desde software utilizando una fuente especial. Esto condujo a su uso comercial e industrial generalizado (por ejemplo, credenciales de identificación de la empresa, seguimiento de activos, automatización de fábricas).

Cree el programa o la función más cortos para leer un código de barras del Código 39 en cualquier orientación desde una imagen en escala de grises de 512x512 píxeles; el código de barras podría no estar alineado horizontal o verticalmente.

• Su programa debe aceptar un formato de archivo de imagen estándar y producir los datos codificados en el código de barras como su salida estándar o valor de retorno (sin incluir ningún carácter de inicio / parada).
• Ninguna imagen contiene más de un código de barras válido del Código 39, y ningún código de barras codifica un carácter de espacio (ASCII 32).
• Si no se muestra un código de barras válido del Código 39 en la imagen, el programa debe generar un solo signo de interrogación ( ?).

He preparado una implementación de referencia de JavaScript y un conjunto de imágenes de prueba en formato PNG, tanto con códigos de barras válidos como sin ellos. La implementación de referencia, que falla solo en 3 de 46 casos de prueba en los navegadores web más recientes, pretende mostrar un posible algoritmo de decodificación, no ajustarse estrictamente a la especificación anterior.

Una presentación válida pasa al menos el 80% de estas pruebas (37/46) y no toma más de un minuto para cada imagen en una CPU razonablemente rápida (por ejemplo, cuatro núcleos a 2.6 GHz). Mi implementación de referencia supera el 93% de las pruebas y procesa cada imagen en 10 segundos (en mi PC de escritorio con Google Chrome).

(Esta pregunta fue propuesta en Meta el 28 de mayo de 2011.)

Python, 899 caracteres

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

Este código toma una imagen en formato pnm como entrada, por lo que normalmente lo ejecuto como:

pngtopnm s01.png | ./barcode.py

El código en sí solo selecciona muchas líneas de exploración aleatorias e intenta hacer coincidir las corridas en blanco y negro de esa línea de exploración con los patrones del código39. Está aleatorizado, por lo que puede fallar al encontrar códigos de barras en ocasiones. (Obtengo aproximadamente un 20% de tasa de fallas negativas falsas en las imágenes de prueba). Cuando falla, tarda aproximadamente un minuto en ejecutarse, cuando tiene éxito, a menudo lo hace mucho más rápido que eso. Nunca he visto un falso positivo.