How Barcode Localization Works

Note on Terminology: “Localization” in this context refers to finding the physical location (position, bounding box) of a barcode within an image - not language localization (i18n). This is standard computer vision terminology.

This article explains the technical details of how Quagga2 locates and decodes barcodes in images. Understanding this can help you optimize performance and troubleshoot issues.

Overview

Quagga2 uses a two-stage process:

  1. Barcode Locator (blue box in the images below) - Finds regions that look like barcodes
  2. Barcode Decoder (red line in the images below) - Reads the actual barcode data

This approach is based on the paper Locating and decoding EAN-13 barcodes from images captured by digital cameras by Douglas et al., with adaptations and modifications for web browsers.

Stage 1: Barcode Locator

The locator finds patterns that look like barcodes. A barcode is typically characterized by:

Step 1: Creating a Binary Image

The first step is converting the color image to binary (black and white). Instead of using a simple threshold (e.g., everything below 127 is black), Quagga2 uses Otsu’s method, which adapts to lighting changes across the image.

Binary Image

Otsu’s method analyzes the image histogram and automatically separates foreground (barcode) from background, even with uneven lighting.

Step 2: Slicing into a Grid

The binary image is divided into a 20×15 grid (assuming 4:3 aspect ratio). Each cell is analyzed independently to determine if it contains barcode-like patterns.

Step 3: Extract Skeleton

Each cell undergoes skeletonization - reducing bars to their centerline (1px width). This is done through iterative erosion and dilation.

Skeleton Image

The skeleton clearly shows where parallel lines exist, making it easier to identify barcode regions.

Step 4: Component Labeling

Using connected-component labeling, each line in the skeletonized image is separated into individual components. This is done with a fast algorithm based on the paper “A Linear-Time Component-Labeling Algorithm Using Contour Tracing Technique” by Fu Chang et al.

Component Labeling

Each color represents a distinct labeled component (line). Notice how each cell is processed independently.

Here are zoomed examples of two cells:

Component labeling - barcode lines Good: Parallel lines indicate a possible barcode

Component labeling - text Bad: Random components indicate noise/text

Step 5: Determining Orientation

For each component, Quagga2 calculates its orientation using central image moments. This is a mathematical technique to extract the angle of a shape.

The orientation (θ) is calculated as:

Theta calculation

Where μ (mu) are central moments calculated from raw moments (M):

Mu calculation

The centroid (x̄, ȳ) is calculated from raw moments:

X Y bar calculation

And the raw moments (M) are computed as:

M calculation

Where I(x,y) is the pixel value at position (x,y) - either 0 or 1 in a binary image.

Don’t worry if the math looks intimidating - the key insight is that these formulas calculate which direction each line is pointing.

Step 6: Determining Cell Quality

Cells are evaluated based on how parallel their lines are:

  1. Filter out noise: Discard cells with fewer than 2 components, or components smaller than 6 pixels
  2. Cluster angles: Group similar angles together
  3. Select dominant cluster: Pick the cluster with the most members
  4. Quality threshold: Only accept cells where ≥75% of components share the same angle

Cells that pass this test are called patches and contain:

Found patches

Yellow boxes show patches that were classified as possible barcode areas. Note some false positives (text regions).

Step 7: Finding Connected Cells

Patches are grouped together if they’re neighbors with similar orientation (within 5% angle difference). This is done using recursive component labeling.

Connected patch labels

Each color represents a distinct group. Sometimes adjacent patches have different colors due to angle differences exceeding the 5% threshold.

Step 8: Selecting Groups

Groups are sorted by size (number of patches) and only the largest groups are kept - these are most likely to be actual barcodes.

Remaining patch labels

Small groups and false positives have been filtered out.

Step 9: Create Bounding Box

For each group, a minimum bounding box is calculated:

  1. Calculate average angle of all patches in the group
  2. Rotate all patches by this angle
  3. Find outermost corners (min/max x and y)
  4. Create bounding box
  5. Rotate box back to original orientation

Rotated cells with box Patches rotated to horizontal, bounding box calculated

Bounding box Final bounding box rotated back to match barcode orientation

The bounding box now precisely outlines the barcode, including its rotation and scale. This information is passed to the decoder.

Stage 2: Barcode Decoder

With the bounding box and orientation known, the decoder:

  1. Samples pixel intensities along scan lines within the box
  2. Detects transitions from black to white (edges of bars)
  3. Calculates bar widths
  4. Matches patterns against the selected barcode format(s)
  5. Validates checksums
  6. Returns the decoded data

Why This Approach?

Unlike simpler barcode scanners that require the barcode to be:

Quagga2’s localization algorithm is invariant to rotation and scale. It can find and decode barcodes:

This makes it much more practical for real-world camera scanning where users can’t always position the camera perfectly.

Performance Considerations

The localization algorithm is computationally intensive. Key factors affecting performance:

See Optimize Performance for practical tips.

Source Code

The localization algorithm is implemented in:

Contributions and improvements are welcome!