Scanner de código de barras Code 39

O Código 39 , desenvolvido em 1974, é uma das simbologias ou tipos de códigos de barras mais comumente usados, embora seja o sistema UPC / EAN que é mais frequentemente visto nas vendas no varejo. Os códigos de barras do Código 39 podem codificar letras maiúsculas, números e alguns símbolos e são fáceis de imprimir a partir de software usando uma fonte especial. Isso levou ao seu amplo uso comercial e industrial (por exemplo, crachás de identificação da empresa, rastreamento de ativos, automação de fábrica).

Crie o programa ou a função mais curta para ler um código de barras do Code 39 em qualquer orientação a partir de uma imagem em escala de cinza de 512x512 pixels; o código de barras pode não estar alinhado horizontal ou verticalmente.

• Seu programa deve aceitar um formato de arquivo de imagem padrão e produzir os dados codificados no código de barras como sua saída padrão ou valor de retorno (sem incluir nenhum caractere de início / parada).
• Nenhuma imagem contém mais de um código de barras válido do Code 39 e nenhum código de barras codifica um caractere de espaço (ASCII 32).
• Se nenhum código de barras válido do Code 39 for mostrado na imagem, o programa deverá gerar um único ponto de interrogação ( ?).

Eu preparei uma implementação de referência JavaScript e um conjunto de imagens de teste em formato PNG, com códigos de barras válidos e sem. A implementação de referência, que falha apenas em 3 dos 46 casos de teste nos navegadores da Web mais recentes, tem a intenção de mostrar um possível algoritmo de decodificação, para não estar em conformidade estrita com a especificação acima.

Um envio válido passa em pelo menos 80% desses testes (37/46) e não leva mais de um minuto para cada imagem em uma CPU razoavelmente rápida (por exemplo, quad-core de 2,6 GHz). Minha implementação de referência passa em 93% dos testes e processa cada imagem em 10 segundos (no meu PC desktop executando o Google Chrome).

(Esta pergunta foi proposta no Meta em 28 de maio 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

Esse código usa uma imagem no formato pnm como entrada, então eu normalmente a executo como:

pngtopnm s01.png | ./barcode.py

O próprio código apenas seleciona muitas linhas de verificação aleatórias e tenta combinar as execuções em preto e branco nessa linha de verificação com os padrões do código39. Ele é randomizado para não conseguir encontrar códigos de barras ocasionalmente. (Recebo cerca de 20% de taxa de falsos negativos negativos nas imagens de teste.) Quando falha, leva cerca de um minuto para ser executado, quando é bem-sucedido, geralmente é muito mais rápido que isso. Eu nunca vi um falso positivo.