Let's develop a QR Code Generator, part VI: mask optimization

In part 5 we've created our first QR Code. Our code is not complete, but rather it's specific to our case (version 2, byte mode) and we've applied a fixed mask, violating the specification that tell us to choose the best mask among the predefined 8.

Anyway, this is the result:

In order to choose the best mask, we need to compute the penalty score that we get from each one, and select the mask with the lowest score. The penalty score is the sum of the penalties obtained using 4 rules, as follows.

Rule 1

The first rule says that each sequence of 5 or more consecutive dark/light modules in a row or column gets a penalty of the length of the sequence minus 2.

This is the penalties for the QR Code above just for the horizontal sequences:

It sums up to 102. When adding up the penalties for vertical sequences, we should get 138 more, for a total score of 240 for rule 1.

In code

Let's start with a pretty straightforward helper function to compute the penalty in a certain sequence of modules according to rule 1:

function getLinePenalty(line) {
  let count = 0;
  let counting = 0; // To keep trick of which modules we're counting
  let penalty = 0;
  for (const cell of line) {
    if (cell !== counting) {
      counting = cell;
      count = 1;
    } else {
      count++;
      if (count === 5) {
        penalty += 3;
      } else if (count > 5) {
        penalty++;
      }
    }
  }
  return penalty;
}

Now we're going to use it to compute the total penalty score of rows and columns (remember that matrix is supposed to be an array of Uint8Arrays containing either 0 or 1 - our QR Code):

let totalPenalty = 0;

const rowPenalty = matrix.reduce((sum, row) => sum + getLinePenalty(row), 0);
totalPenalty += rowPenalty;

const columnPenalty = matrix.reduce((sum, _, columnIndex) => {
  const column = matrix.map(row => row[columnIndex]);
  return sum + getLinePenalty(column);
}, 0);
totalPenalty += columnPenalty;

Rule 2

The second rule says that each rectangular region of dark/light modules of size m×n gets a penalty of 3×(m - 1)×(n - 1).

… ok. But how should we identify such rectangles, if there are several ways to split a certain area?

Fortunately, we have an equivalent strategy: just add a penalty of 3 for each 2×2 square of dark/light modules, including overlapping ones.

There are 60 of such 2×2 squares in the picture above, for a total penalty score of 180.

In code

This rule is quite simple: all you have to do is checking if three adjacent modules are equal to the current one:

let blocks = 0;
const size = matrix.length
for (let row = 0; row < size - 1; row++) {
  for (let column = 0; column < size - 1; column++) {
    const module = matrix[row][column];
    if (
      matrix[row][column + 1] === module &&
      matrix[row + 1][column] === module &&
      matrix[row + 1][column + 1] === module
    ) {
      blocks++;
    }
  }
}
totalPenalty += blocks * 3;

Rule 3

The third rules says that each sequence of dark-light-dark-dark-dark-light-dark-light-light-light-light modules (⬛⬜⬛⬛⬛⬜⬛⬜⬜⬜⬜) or its reverse (⬜⬜⬜⬜⬛⬜⬛⬛⬛⬜⬛), found on any row or column, adds a penalty of 40.

I have no idea! Seriously, if someone has any info about this, please speak up!

Anyway, here are said patterns highlighted in our QR Code:

Three patterns, for a penalty of 120.

In code

First of all, let's put those sequences in constants:

const RULE_3_PATTERN = new Uint8Array([1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]);
const RULE_3_REVERSED_PATTERN = RULE_3_PATTERN.slice().reverse();

Then, for each row and column, let's check how many times they contain the pattern or its reverse:

let patterns = 0;
for (let index = 0; index < size; index++) {
  // Checking the rows...
  const row = matrix[index];
  for (let columnIndex = 0; columnIndex < size - 11; columnIndex++) {
    if ([RULE_3_PATTERN, RULE_3_REVERSED_PATTERN].some(
      pattern => pattern.every(
        (cell, ptr) => cell === row[columnIndex + ptr]
      )
    )) {
      patterns++;
    }
  }
  // Checking the columns...
  for (let rowIndex = 0; rowIndex < size - 11; rowIndex++) {
    if ([RULE_3_PATTERN, RULE_3_REVERSED_PATTERN].some(
      pattern => pattern.every(
        (cell, ptr) => cell === matrix[rowIndex + ptr][index]
      )
    )) {
      patterns++;
    }
  }
}
totalPenalty += patterns * 40;

Rule 4

Rule 4 is mostly computational. Follow these steps:

1. compute the percentage of dark modules;
2. if the percentage is greater than 50, round down to the nearest multiple of 5; otherwise, round it up;
3. subtract 50 and double the absolute value of the difference: that's our penalty for rule 4.

In our case, 50.4% of the modules (315 out of 625) are dark, so we round down to 50, subtract 50 and double the difference: it's 0.

If we had, for example, a percentage of 42%, we'd have rounded up to 45%, then get a penalty of 10. For 67%, we'd round down to 65% and get a penalty of 30.

Note that you can actually make the computation based on the light modules instead of the dark: it's the same thing, if you check the formula.

In code

First, let's compute the amount of dark (or light) modules:

const totalModules = size * size;
const darkModules = matrix.reduce(
  (sum, line) => sum + line.reduce(
    (lineSum, cell) => lineSum + cell
  , 0)
, 0);
const percentage = darkModules * 100 / totalModules;

In order to round down to the nearest multiple of n, we divide by n, round down to the nearest integer and multiply back by n. It's similar when rounding up.

const roundedPercentage = percentage > 50
  ? Math.floor(percentage / 5) * 5
  : Math.ceil(percentage / 5) * 5;

Finally, let's compute the penalty score:

const mixPenalty = Math.abs(roundedPercentage - 50) * 2;
totalPenalty += maxPenalty;

Since basically Math.trunc = x => x > 0 ? Math.floor(x) : Math.ceil(x) (MDN, we can come up with a more compact formula like this:

const mixPenalty = Math.abs(Math.trunc(percentage / 5 - 10)) * 10;

The complete penalty score function

Let's gather all the code above in a single function:

const RULE_3_PATTERN = new Uint8Array([1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]);
const RULE_3_REVERSED_PATTERN = RULE_3_PATTERN.slice().reverse();

function getLinePenalty(line) {
  let count = 0;
  let counting = 0;
  let penalty = 0;
  for (const cell of line) {
    if (cell !== counting) {
      counting = cell;
      count = 1;
    } else {
      count++;
      if (count === 5) {
        penalty += 3;
      } else if (count > 5) {
        penalty++;
      }
    }
  }
  return penalty;
}

function getPenaltyScore(matrix) {
  let totalPenalty = 0;

  // Rule 1
  const rowPenalty = matrix.reduce(
    (sum, row) => sum + getLinePenalty(row)
  , 0);
  totalPenalty += rowPenalty;

  const columnPenalty = matrix.reduce((sum, _, columnIndex) => {
    const column = matrix.map(row => row[columnIndex]);
    return sum + getLinePenalty(column);
  }, 0);
  totalPenalty += columnPenalty;

  // Rule 2
  let blocks = 0;
  const size = matrix.length
  for (let row = 0; row < size - 1; row++) {
    for (let column = 0; column < size - 1; column++) {
      const module = matrix[row][column];
      if (
        matrix[row][column + 1] === module &&
        matrix[row + 1][column] === module &&
        matrix[row + 1][column + 1] === module
      ) {
        blocks++;
      }
    }
  }
  totalPenalty += blocks * 3;

  // Rule 3
  let patterns = 0;
  for (let index = 0; index < size; index++) {
    const row = matrix[index];
    for (let columnIndex = 0; columnIndex < size - 11; columnIndex++) {
      if ([RULE_3_PATTERN, RULE_3_REVERSED_PATTERN].some(
        pattern => pattern.every(
          (cell, ptr) => cell === row[columnIndex + ptr]
        )
      )) {
        patterns++;
      }
    }
    for (let rowIndex = 0; rowIndex < size - 11; rowIndex++) {
      if ([RULE_3_PATTERN, RULE_3_REVERSED_PATTERN].some(
        pattern => pattern.every(
          (cell, ptr) => cell === matrix[rowIndex + ptr][index]
        )
      )) {
        patterns++;
      }
    }
  }
  totalPenalty += patterns * 40;

  // Rule 4
  const totalModules = size * size;
  const darkModules = matrix.reduce(
    (sum, line) => sum + line.reduce(
      (lineSum, cell) => lineSum + cell
    , 0)
  , 0);
  const percentage = darkModules * 100 / totalModules;
  const mixPenalty = Math.abs(Math.trunc(percentage / 5 - 10)) * 10;

  return totalPenalty + mixPenalty;
}

Total penalty score

The total penalty score in our case is therefore 240 + 180 + 120 + 0 = 540. New we need to find which mask yields the lowest penaly, and this function should do the trick:

function getOptimalMask(version, codewords, errorLevel) {
  let bestMatrix;
  let bestScore = Infinity;
  let bestMask = -1;
  for (let index = 0; index < 8; index++) {
    const matrix = getMaskedQRCode(version, codewords, errorLevel, index);
    const penaltyScore = getPenaltyScore(matrix);
    if (penaltyScore < bestScore) {
      bestScore = penaltyScore;
      bestMatrix = matrix;
      bestMask = index;
    }
  }
  return [bestMatrix, bestMask];
}

The other masks yield a penalty score of, respectively, 495, 415, 575, 597, 579, 472, 779. So the best mask to apply is #2, with this final result:

And that's it! We finally have our final QR Code 🎉. But still, we assumed quite some things and cut corners in order to reach a result as soon as possible (and still needed 5-6 parts anyway!):

• the content is a plain Latin-1 encoded string;
• the length of the content fits in a smaller QR Code;
• no need to split the data in multiple code blocks.

In the next parts, we're going to solve these issue, so we can actually develop a fully functional QR Code generator.

Comments

[Neil Roberts]

Presumably rule 3 is to try to remove patterns in the QR code that might look like the finder pattern. Ie, if you take a 1-pixel-high cross section of the finder pattern it will look like 1011101. Note that in the spec it talks about ratios, not the actual pattern. So presumably you are also supposed to check for 11001111110011 and so on. For example there could be a huge scaled-up finder pattern in the middle of the QR code that would confuse the reader, but this rule would penalize that.

It’s not totally clear to me from the spec whether the quiet zone around the QR code is supposed to count towards the 4 modules of white space, but I think it would make a lot of sense if it did.