10
\$\begingroup\$

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.)

\$\endgroup\$
  • \$\begingroup\$ There appears to be a bug in your barcode generator - it puts a wide space between characters instead of a narrow one. \$\endgroup\$ – Keith Randall Jun 7 '11 at 4:21
  • \$\begingroup\$ @Keith: The intercharacter gap (I) does not have to be equal to the width of a narrow bar (X), although it often is. Valid submissions should be able to read barcodes where I ≤ 3X. My test case generator intentionally randomizes the intercharacter gap. adams1.com/39code.html \$\endgroup\$ – PleaseStand Jun 7 '11 at 16:57
  • \$\begingroup\$ a Code 39 barcode with anintercharacter gap between 1X and 3X can be read by most common scanners? I will testify it and see whether it works this way. By the way, in my eyes, the intergap can only enlarge the Code 39 printout size, so why should we expand its intercharacter gap? \$\endgroup\$ – user7636 Mar 28 '13 at 2:07
5
\$\begingroup\$

Python, 899 chars

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

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.

\$\endgroup\$
  • \$\begingroup\$ M=dict(zip('UK.-RQA+HGYXON*TEDJ1/87$%540WVML SCBIZPF3296',[385,259,...])) \$\endgroup\$ – ugoren Mar 28 '13 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.