Code 39 Сканер штрих-кода

Код 39 , разработанный в 1974 году, является одной из наиболее часто используемых символик или типов штрих-кодов, хотя именно система UPC / EAN чаще всего встречается в розничных продажах. Штрих-коды Code 39 могут кодировать заглавные буквы, цифры и некоторые символы, и их легко распечатать из компьютерного программного обеспечения специальным шрифтом. Это привело к их широкому коммерческому и промышленному использованию (например, идентификационные значки компаний, отслеживание активов, автоматизация производства).

Создать самую короткую программу или функцию для считывания штрих-кода Code 39 в любой ориентации с изображения в оттенках серого 512x512 пикселей; штрих-код может быть не выровнен по горизонтали или вертикали.

• Ваша программа должна принимать стандартный формат файла изображения и выводить данные, закодированные в штрих-коде, в качестве стандартного выходного или возвращаемого значения (не включая символы запуска / остановки).
• Ни одно изображение не содержит более одного действующего штрих-кода Code 39, и ни один штрих-код не кодирует пробел (ASCII 32).
• Если на изображении нет действительного штрих-кода Code 39, программа должна вывести один знак вопроса ( ?).

Я подготовил эталонную реализацию JavaScript и тестовый набор изображений в формате PNG, как с допустимыми штрих-кодами, так и без. Эталонная реализация, которая не проходит только 3 из 46 тестовых случаев в большинстве современных веб-браузеров, предназначена для демонстрации одного возможного алгоритма декодирования, а не для строгого соответствия приведенной выше спецификации.

Действительная отправка проходит не менее 80% этих тестов (37/46) и занимает не более одной минуты для каждого изображения на достаточно быстром ЦП (например, четырехъядерный процессор с частотой 2,6 ГГц). Моя эталонная реализация проходит 93% тестов и обрабатывает каждое изображение в течение 10 секунд (на моем настольном компьютере с Google Chrome).

(Этот вопрос был предложен на Мете 28 мая 2011 года.)

Питон, 899 символов

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

Этот код принимает изображение формата pnm в качестве входных данных, поэтому я обычно запускаю его так:

pngtopnm s01.png | ./barcode.py

Сам код просто выбирает множество случайных строк развертки и пытается сопоставить черно-белые прогоны на этой линии сканирования с шаблонами code39. Он рандомизирован, поэтому при определенных обстоятельствах может не найти штрих-коды. (Я получаю около 20% ложных отрицательных отказов на тестовых изображениях.) Если он терпит неудачу, его запуск занимает около минуты, а когда он успешен, он часто делает это намного быстрее. Я никогда не видел ложного позитива.