QRコードジェネレータを開発してください、パート6:マスク最適化

我々は最初のQRコードを作成しました.私たちのコードは完全ではありません、しかし、それは私たちのケース(バージョン2、バイトモード)に特有です、そして、我々は固定マスクを適用しました.
とにかく、これは結果です.

ためには、最高のマスクを選択するには、我々は、それぞれから取得ペナルティスコアを計算する必要がありますし、最低スコアでマスクを選択します.ペナルティスコアは、次のように4つのルールを使用して得られた罰則の合計です.

ルール1

第1の規則は、行または列の5つ以上の連続した暗黒／光モジュールの各シーケンスが、2の系列の長さのペナルティを得ると言う.
これはQRコードに対するペナルティです.

それは102まで合計します.垂直系列に対する罰則を追加するときは、ルール1の240の合計スコアに対して138を得るべきです.

インコード

ルール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;
}

現在、我々はそれを行と列の完全なペナルティスコアを計算するために使用するつもりです(matrixはUint8Arrayまたは0 - QRコードを含む1 sの配列であることを忘れないでください).

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;

ルール2

第2の規則は,サイズm×nの暗／軽モジュールの各矩形領域が3×(m−1)×(n−1)のペナルティを得るということである.
...しかし、特定の領域を分割するいくつかの方法があるなら、どのように我々はそのような長方形を特定するべきですか?
幸いなことに、我々は同等の戦略を持っている:ちょうど重複するものを含むダーク/ライトモジュールの各2×2の正方形の3のペナルティを追加します.

このような2×2乗は60枚で、全体のペナルティは180である.

インコード

この規則はとても簡単です.あなたがしなければならないのは、隣接するモジュールが現在のモジュールに等しいかどうかを調べることです.

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;

ルール3

第3の規則は、暗い明暗暗い暗い光暗い明かり光照明モジュールの各々のシーケンスが言うと言います⬛⬜⬛⬛⬛⬜⬛⬜⬜⬜⬜) またはそのリバース⬜⬜⬜⬜⬛⬜⬛⬛⬛⬜⬛), 任意の行または列で見つかったペナルティ40を追加します.

考えもつかない!真剣に、誰かがこれについての情報があれば、話してください!
とにかく、ここにQRコードで強調されたパターンがあります.

ペナルティ120パターン.

インコード

まず、これらのシーケンスを定数にしましょう.

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

次に、行と列ごとに、パターンやその逆の回数をチェックしてみましょう.

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;

ルール4

ルール4は大部分は計算されます.次の手順に従います

は、暗いモジュールのパーセンテージを計算します;

パーセントが50より大きいならば、

が5の最も近い倍数に丸くなるならばそうでなければ、それをラウンド;

は50を減算して、その差の絶対値を2倍にします.

我々の場合では、モジュールの50.4 %(625のうちの315)は暗いので、私たちは50まで丸くなります.
例えば、42 %のパーセンテージを持っていたならば、私たちは45 %まで丸めた.67 %のために、我々は65 %に丸くなって、30のペナルティを得ます.
あなたが実際に暗黒の代わりに光モジュールに基づいて計算をすることができることに注意してください:あなたが式をチェックするならば、それは同じことです.

インコード

まず、暗黒(または)光モジュールの量を計算しましょう.

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

Nの最も近い倍数に丸めるために、我々はNによって分割して、最も近い整数に丸くなって、nによって後ろへ逓倍します.

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

最後にペナルティスコアを計算しましょう.

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

基本的にMath.trunc = x => x > 0 ? Math.floor(x) : Math.ceil(x)年(MDN年)以来、このようなよりコンパクトな式を考え出すことができます.

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

完全なペナルティスコア機能

上記のすべてのコードを一つの関数で集めましょう.

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;
}

合計ペナルティスコア

したがって、この場合の合計ペナルティスコアは240＋180＋120＋0＝540である.新しいマスクはどのマスクを最低でも小さくする必要があります.

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];
}

他のマスクは、それぞれ495、415、575、597、579、472、779のペナルティスコアを得る.したがって、適用するための最良のマスクはCount 2であり、この最終結果は以下の通りです.

そして、それ!我々は最終的に我々の最終的なQRコードを持っている🎉. しかし、それでも、私たちはできるだけ早く結果に達するために非常に若干のものを考えて、角を切りました!

内容は、平易なLatin - 1コード化されたストリングです;

、より小さいQRコードに、内容の長さは収まる;

は、複数のコード・ブロックのデータを分割する必要はない.

次の部分では、これらの問題を解決するつもりですので、実際には完全に機能するQRコードジェネレータを開発することができます.