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