Code 39 Barcode Scanner Code 39, developed in 1974, is one of the most commonly used symbologies, or types, of barcodes, although it is the UPC/EAN system that is most often seen in retail sales. Code 39 barcodes can encode uppercase letters, numbers, and some symbols and are trivial to print from computer software using a special font. This led to their widespread commercial and industrial use (e.g. company ID badges, asset tracking, factory automation).

Create the shortest program or function to read a Code 39 barcode in any orientation from a 512x512 pixel grayscale image; the barcode might not be aligned horizontally or vertically.


Your program must accept a standard image file format and produce the data encoded in the barcode as its standard output or return value (not including any start/stop character).
No image contains more than one valid Code 39 barcode, and no barcode encodes a space character (ASCII 32).
If no valid Code 39 barcode is shown in the image, the program must output a single question mark (?).


I have prepared a JavaScript reference implementation and test suite of images in PNG format, both with valid barcodes and without. The reference implementation, which fails only 3 of 46 test cases in most recent Web browsers, is intended to show one possible decoding algorithm, not to strictly conform to the above specification.

A valid submission passes at least 80% of these tests (37/46) and takes no more than one minute to do so for each image on a reasonably fast CPU (e.g. 2.6 GHz quad-core). My reference implementation passes 93% of tests and processes each image within 10 seconds (on my desktop PC running Google Chrome).

(This question was proposed on Meta on May 28, 2011.)
Python, 899 chars

import sys,random
raw_input()
X,Y=map(int,raw_input().split())
input()
I=[' x'[v&lt;'~']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&lt;0:y=len(A)
  z+=y&gt;K;A=A[y:]
  z*=2;y=A.find('x')
  if y&lt;0:y=len(A)
  z+=y&gt;L;A=A[y:];c+=2
  if c&gt;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


This code takes a pnm format image as input, so I normally run it like:

pngtopnm s01.png | ./barcode.py


The code itself just picks lots of random scanlines and tries to match the black and white runs on that scanline to the code39 patterns.  It is randomized so it can fail to find barcodes on occasion.  (I get about a 20% false negative failure rate on the test images.)  When it fails it takes about a minute to run, when it succeeds it often does so much quicker than that.  I've never seen a false positive.