0
$\begingroup$

A barcode consists of alternating back and white stripes. Thin stripes are one "unit" wide. We'll assume fat stripes are 2 "units" wide. But how big is a "unit"?

I can't find any papers that describe an algorithm or discuss the benefits of different algorithms. I've found papers that discuss other parts of the barcode reading process but not that specific part.

I can think of a few ways of doing is - for instance a Fourier transform might be a good start - but none are quick on a small processor. A commercial laser scanner decodes a single line of pixels using a tiny processor. How?

As a bonus, I'd like to be able to decode skewed "perspective" views like this:

skewed perspective view of a barcode

Note how a "2-units" bar at the left is the same width as a "1-unit" bar at the right.

I think a single-pixel wide line of a barcode may be a form of anisochronous self-clocking signal but a Google search didn't help.

(I am NOT asking how to locate the barcode in the image. I am NOT asking how to find the angle of the barcode in order to rotate it. I am NOT asking how to threshold the barcode. There are several good papers on those. I am NOT asking for recommendations of barcode packages such as ZXing or OpenCV or zbar. I am NOT asking for alternatives to barcodes such as AprilTags, ShotCodes, PDF417, QR codes, Postbar, etc., etc. I'd prefer an algorithm that will run in a few tens of milliseconds on a small processor.)

$\endgroup$
4
  • $\begingroup$ people think microcontrollers are way slower than they actually are – while you're right that there's probably not a Fourier transform happening in most barcode scanners (we can't possibly know the inner workings of every scanner), a very modest entry-level ARM microcontroller (think: 1€ in quantity) will do a couple ten thousand to hundred thousand short fixed-point FFTs per second. These are >= 48 MHz machines, many with proper data caches, single-cycle addition and multiplication, pipelined cores, and memory bandwidths in the order of 100 MB/s. Don't worry about speed :) $\endgroup$ Commented May 1 at 11:37
  • $\begingroup$ Good point. I was thinking of using an ESP32cam and that can do a 512 sample FFT in 3mS. However, I suspect that a FFT isn't actually all that useful for the "perspective" example above. $\endgroup$ Commented May 1 at 12:14
  • $\begingroup$ there is no difference between the skewed view and the normal view in the pictures you provided ... the ratio between the bar widths is the same in both the views $\endgroup$
    – jsotola
    Commented May 1 at 16:40
  • $\begingroup$ No it isn't. If you assume the "unit" width is constant across the barcode then the skewed view is un-readable. But if you look at the ratio between each bar and its successor then I think it's easy to read. Maybe. I'd really like to read some papers on how other people do it. There are lots of ways it could be implemented. Which one is fast and reliable? $\endgroup$ Commented May 1 at 17:04

2 Answers 2

1
$\begingroup$

much like an UART; barcodes readers are self-clocking; they recover the rate at which to interpret the bars from the observation.

To that end, all important types of barcodes (there's many, so details of decoding will depend on what type you have) have defined markers at the end and the beginning (larger codes typically also have a mid-marker). Knowing that the beginning of a code always reads "101" (example from EAN-13), you can simply count the time, pixels, encoder wheel ticks… that a single bit symbol will take. From there on, you just keep that rate. In your second example picture, where the bars get "thicker" the closer the code comes to the observer, you can easily just compare the timing of the start and the end marker, and correctly linearly interpolate the symbol rate between; you really don't need much memory to hold a couple brightness values, or you just do another round of scanning after you've figured out the rate.

There's different types of barcode scanners, and thus, different algorithms to do that clock recovery (as a communications engineer would call that). There's scanners that can rely on a human or a conveyor or similar system to transport the barcode in a straight line at relatively fixed speed, there's rotating-mirror laser reflectometric scanners, there's line-sensor scanners, and there's full 2D-imagingcamera-based scanners (and I bet there's more).

The most common type you see e.g. in supermarkets is probably the laser style, because that can deal with distances, and just scans its beam across its field of view in many angles, so that it can deal with arbitrary rotations. However, the "hard part" is the mechanics of that, and you'll hardly buy the laser+mirror part alone – there's ASICs that do the laser and mirror control, and the barcode decoding all in one. Then, your own microcontroller just needs to accept the decoded data.

Anyway, you ask "what do I do if I only have a line of brightness values?"; and the answer will probably be something among the lines:

  • high-pass filter to get the general lightning/brightness out of the picture; your scan of a whole code should have an average of 0, so that white areas are as positive numerically as black areas are negative.
  • low-pass filter to suppress noise (giving, in the end, the response of a band-pass filter)
    • how much of these filters you do in analog or digital domain: depends on your system design.
  • because this is all relatively low-speed data, a simple straightforward correlator bank for the start-, combined with the end-markers, at different scales, would do to detect the presence of a potential code of a specific size.
  • You try that size. If the checksum works out, congratulations, you have a barcode.
  • If the checksum doesn't work out, you continue looking.

You're of course right, that correlator bank can be reduced in complexity. For that, you'd probably start by training a sufficiently bandlimited PLL on the edges of your signal (i.e., you convert, electronically or digitally, the transitions from bright to dark and vice versa, to pulses, and adjust your adjustable oscillator such that a zero-crossings coincides with each pulse), to give you a rough estimate of symbol rate, and use that knowledge to restrict the search space. (Trick: if you give the error feedback in that PLL memory, i.e., make it a second-order control loop, you can solve the perspective issue.)

You can then furthermore employ FFT-based fast convolution (correlation) to reduce the remaining cost of the correlator bank.

It's possible that if you can adjust the readout speed, you can let your microcontroller's UART peripheral do just that; baudrate detection is not that new a feature.

$\endgroup$
5
  • $\begingroup$ Thanks. I think you suggest: "binarize" the image; do cross-correlations with a bank of templates to locate specific start and end codes; use the codes to estimate the "unit" width. My initial reaction is that cross-correlations are fairly expensive and the bank may be large. One may have to do it with e.g. every Nth raster line to find the barcode. Good idea but I'd prefer a faster algorithm. (I'm looking for an alternative to AprilTags for robot navigation using e.g. an ESP32cam. The barcode may be across the room. I didn't say that in the OP because I don't want to restrict the answers.) $\endgroup$ Commented May 1 at 13:43
  • $\begingroup$ the binarization can happen after the cross-correlation, if compute power allows it; that gives you more margin. I was assuming you'd do anything but a camera approach on a microcontroller, so I went with the assumption of the low data rates coming out of the non-camera kinds of sensors (a couple kilosamples per second, at most). Barcodes aren't perfect for camera-based detection, as they don't have great features for perspective "deskewing" and rotation (unlike e.g. QR codes with their square markers in three of four corners), but that should genereally not be an inherent issue. Just try … $\endgroup$ Commented May 1 at 14:50
  • $\begingroup$ to find a bar code code in all rows, and if that fails, try to find one in all columns. It can either be perfectly horizontal or perfectly vertical, not both, and it will very likely be a mixture, thus making it very likely you can find it at least sliced in one of these two dimensions. Since you can take on the rows (or columns) individually without relation to any other row (or column), and it's unlikely that if one row contains no trace of a barcode, the next one contains a full one, you can start only by doing every, say, 50th row, keeping complexity at bay. However, I don't know the $\endgroup$ Commented May 1 at 14:54
  • $\begingroup$ …ESP32-cam platform, and googling it shows that people run neural networks on these, which would suggest there's some accelerator for CNNs on there, which lends itself excellently to detection of features like different scales of codes. But then you shouldn't worry about the general algorithm running on "a small microcontroller" (the ESP32 family is anything but "small microcontrollers", quite the opposite), but need to look into ways that accelerator can be put to use for your problem. I'd say saying that you have but "a small microcontroller", and then later mentioning you're dealing with $\endgroup$ Commented May 1 at 14:56
  • $\begingroup$ a SoC so powerful it can interface a camera and contains an CNN accelerator, that was a bit of a "Red Herring". $\endgroup$ Commented May 1 at 14:58
0
$\begingroup$

I'd really like to find some papers on how other people do it. There are plenty about thresholding or locating barcodes but I haven't found a single one that explains how they recover the clock and data.

So here's my suggestion.

Don't think about a regular clock, just compare the width of each bar with its neighbour. In the majority of barcode formats, bars are either narrow or wide (a "binary barcode"). Let's say their width is 1 or 2 units. So each bar is either

  • double the previous bar
  • the same as the previous bar
  • half the previous bar

In the "perspective" example in the OP, the widths of the black/white stripes are:

7 4 4 9 5 9 12 5 14 7 8 18 10 22 26

The ratio of each width to the previous width is

0.571 1.000 2.250 0.556 1.800 1.333 0.417 2.800 0.500 1.143 2.250 0.556 2.200 1.182

We assume a threshold of

  • b bad: ratio < 0.354
  • h half: 0.354 < ratio < 0.707
  • s same: 0.707 < ratio < 1.414
  • d double: 1.414 < ratio < 2.828
  • b bad: 2.828 < ratio

Then it decodes as "hsdhdshdhsdhds". Let's call it "hsd" format. It feels like one should be able to recover the original barcode from that.

In the most widely used barcodes (the EAN formats), the bars are 1,2,3,4 units wide so the algorithm would have to be modified to accept those.

I have no idea if anyone does it that way and I'd love to find out. Maybe "hsd" format discards too much useful information. Supermarket barcode scanners have been in use since 1974; whatever the algorithm was, it must have run on a microprocessor of the time.

I was considering using barcodes as fiducials for robot navigation (like AprilTags but faster). That means I can create my own barcodes with fat stripes which can be seen from a distance. For instance here is a set of 20 barcodes of 13 bits with a Hamming distance of 7 in the "hsd" format. (A "0" is a 1-unit wide bar, a "1" is 2 units wide.)

  • 1000101110001 bbwbwbbwbbwwbbwbwbb hssdhdsshssd
  • 1000110011010 bbwbwbbwwbwbbwwbwwb hssdshsdshdh
  • 1001000000100 bbwbwwbwbwbwbbwb hsdhsssssdhs
  • 1001010100001 bbwbwwbwwbwwbwbwbb hsdhdhdhsssd
  • 1001100101010 bbwbwwbbwbwwbwwbwwb hsdshsdhdhdh
  • 1010000001001 bbwbbwbwbwbwwbwbb hdhsssssdhsd
  • 1010001010010 bbwbbwbwbbwbbwbwwb hdhssdhdhsdh
  • 1010010110100 bbwbbwbwwbwwbbwbbwb hdhsdhdshdhs
  • 1011011011000 bbwbbwwbwwbbwbbwwbwb hdshdshdshss
  • 1100000010000 bbwwbwbwbwbbwbwb shsssssdhsss
  • 1100001000101 bbwwbwbwbbwbwbbwbb shsssdhssdhd
  • 1100100100110 bbwwbwbbwbwwbwbbwwb shsdhsdhsdsh
  • 1101001100010 bbwwbwwbwbbwwbwbwwb shdhsdshssdh
  • 1101010001000 bbwwbwwbwwbwbwwbwb shdhdhssdhss
  • 1110011000011 bbwwbbwbwwbbwbwbwwbb sshsdshsssds
  • 1110101010100 bbwwbbwbbwbbwbbwbbwb sshdhdhdhdhs
  • 0000110101100 bwbwbbwwbwwbwwbbwb sssdshdhdshs
  • 0100101001010 bwwbwbbwbbwbwwbwwb dhsdhdhsdhdh
  • 0101011010101 bwwbwwbwwbbwbbwbbwbb dhdhdshdhdhd
  • 0111000110010 bwwbbwwbwbwwbbwbwwb dsshssdshsdh

It ought to be fast to scan every Nth raster line of a camera image, convert it to an "hsd" format string and search the string for the "correct" answers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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