QR Code Decoding: From Finder Patterns to Data Extraction#

Building a mobile QR scanner got me curious about the underlying decoding algorithm. It’s way more sophisticated than I expected—here’s how it actually works.

QR Code Anatomy: The Three Finder Patterns#

The most obvious feature of a QR code is the three square blocks in the corners. These are finder patterns, and they’re the key to fast positioning regardless of rotation or perspective distortion.

Each finder pattern is a 7×7 structure: black-white-black-white-black. Why three? Because three points define a plane’s rotation and perspective transformation. Two points only give you rotation.

Beyond finder patterns, QR codes have:

• Timing patterns: Alternating black/white lines connecting finder patterns
• Alignment patterns: For version ≥2, compensates for perspective distortion
• Format information: Error correction level + mask pattern
• Version information: For version ≥7

The Decoding Pipeline#

The complete decoding flow:

Raw image → Grayscale → Binarize → Detect finder patterns → 
Perspective transform → Extract modules → Read data → 
Error correction → Parse data → Final result

Step 1: Finder Pattern Detection#

How do we find finder patterns? Use their 1:1:3:1:1 width ratio.

Scan each row of the image, tracking black/white transitions. When five consecutive segments match the 1:1:3:1:1 ratio, it’s likely a finder pattern.

function detectFinderPattern(row: number[], pos: number[]): boolean {
  const [a, b, c, d, e] = [
    pos[1] - pos[0],
    pos[2] - pos[1],
    pos[3] - pos[2],
    pos[4] - pos[3],
    pos[5] - pos[4]
  ]
  
  const moduleSize = (a + b + d + e) / 4
  const centerSize = c
  
  return (
    Math.abs(centerSize - 3 * moduleSize) < moduleSize * 0.5 &&
    Math.abs(a - moduleSize) < moduleSize * 0.5 &&
    Math.abs(b - moduleSize) < moduleSize * 0.5 &&
    Math.abs(d - moduleSize) < moduleSize * 0.5 &&
    Math.abs(e - moduleSize) < moduleSize * 0.5
  )
}

Once we find three finder patterns, calculate their centers to determine rotation angle and perspective transformation matrix.

Step 2: Perspective Transformation#

Camera capture introduces skew and distortion. We need to map the trapezoid back to a square.

Perspective transformation formula:

x' = (a*x + b*y + c) / (g*x + h*y + 1)
y' = (d*x + e*y + f) / (g*x + h*y + 1)

Solve for the 8 transformation coefficients using the four corner points (3 finder patterns + 1 inferred point).

function perspectiveTransform(
  srcPoints: Point[],
  dstPoints: Point[]
): Matrix {
  const A = buildCoefficientMatrix(srcPoints, dstPoints)
  const b = buildConstantVector(srcPoints, dstPoints)
  return solveLinearSystem(A, b)
}

After transformation, each module maps to an integer grid position for easy reading.

Step 3: Module Extraction#

QR codes consist of black/white modules, each representing one bit (black=1, white=0). Module size is determined from timing patterns.

Reading order isn’t left-to-right—it’s a snake pattern:

↑↑↑↑│
│││││
↓↓↓↓│
←←←←

Start at bottom-right, go up two columns, then down two columns, repeat. Skip function modules (finder patterns, alignment patterns, etc.).

function readBitMatrix(matrix: number[][], size: number): number[] {
  const bits: number[] = []
  let x = size - 1
  let y = size - 1
  let direction = -1
  
  while (x >= 0) {
    if (!isFunctionModule(x, y, size)) {
      bits.push(matrix[y][x])
    }
    
    const nextY = y + direction
    if (nextY < 0 || nextY >= size) {
      x -= 2
      if (x === 6) x--
      direction *= -1
    } else {
      y = nextY
    }
  }
  
  return bits
}

#