QRコードを段階的に生成する方法

 (nayuki.io)
5 ポイント 投稿者 GN⁺ 2024-11-19 | 1件のコメント | WhatsAppで共有
  • テキストがQRコードに変わる内部処理を 0〜9段階の可視化 で追いながら、Nayuki QR Code generator library の動作原理を確認できる
  • 例の入力 Hello, world! 123 は 17 個の Unicode コードポイントとして解析され、Numeric・Alphanumeric・Kanji ではない Byte モード でエンコードされる
  • モードビット、文字数、セグメントデータ、終端ビットを連結した結果、19 個のデータコードワード が作られ、Version 1 の ECC L 容量に収まる
  • Version 1 の QR コードは、1 個のブロックにデータコードワード 19 個と Reed–Solomon ECC コードワード 7 個を追加したあと、固定パターンとデータモジュールを配置する
  • 8 個のマスクのペナルティを比較し、合計点が最も低い Mask pattern 3 を選択しており、最終結果は単純なエンコードではなく品質評価まで経て決定される

デモの目的と入力処理

  • この Web アプリケーションは、テキスト文字列が QR コード にエンコードされる過程を段階的に可視化する
  • ページでは QR Code generator library の内部動作を理解できるよう、エンコード過程を分解して表示している
  • ユーザー入力項目は、テキスト文字列、誤り訂正レベル、最小 Version の強制、マスクパターンの強制で構成される

0段階: Unicode 文字解析

  • 例の文字列は Hello, world! 123 で、入力テキストのコードポイント数は 17 個
  • 各文字は、Numeric、Alphanumeric、Byte、Kanji モードでエンコード可能かどうかを検査される
  • 文字列全体のモード別エンコード可否は次のとおり
    • Numeric: 不可
    • Alphanumeric: 不可
    • Byte: 可能
    • Kanji: 不可
  • 文字列全体を格納するために選ばれたセグメントモードは Byte

1段階: データセグメント生成

  • 各文字はビット列に変換される
  • Numeric および Alphanumeric モードでは、連続した文字をまとめてエンコードする
  • Byte モードでは、1 文字が 8、16、24、32ビット のいずれかを生成する
  • 例では各文字の 16 進値が 8 ビットに変換される
    • H: 48 → 01001000
    • e: 65 → 01100101
    • 1: 31 → 00110001
    • 2: 32 → 00110010
    • 3: 33 → 00110011
  • デモプログラムは簡略化のため、常に 単一セグメント を作成する
  • 全体のビット長をより短くする最適分割方式は optimal text segmentation for QR codes で別途扱われている

2段階: Version 番号の適合

  • セグメント一覧を表現するのに必要な全ビット長は Version の範囲によって変わる
    • Version 1〜9: 148ビット、19コードワード
    • Version 10〜26: 156ビット、20コードワード
    • Version 27〜40: 156ビット、20コードワード
  • コードワードは 8ビット、つまり 1 バイトとして定義される
  • QR コードのデータコードワード容量は Version と誤り訂正レベルによって異なる
  • 例の入力は、選択された誤り訂正レベルで Version 1 に収まる
  • 最終的に選択された Version 番号は 1

3段階: セグメント連結、パディング、コードワード生成

  • 複数のビット文字列を連結してデータビット列を作る
    • Segment 0 mode: 0100, 4ビット
    • Segment 0 count: 00010001, 8ビット
    • Segment 0 data: 136ビット
    • Terminator: 0000, 4ビット
  • 累積ビット数は 152ビット
  • 例では Bit padding と Byte padding はどちらも 0 ビット
  • 全データコードワードのバイトは 8 ビット単位に分割され、16 進で表示される
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30

4段階: ブロック分割、ECC 追加、インターリーブ

  • 例のブロック統計は次のとおり
    • データコードワード数: 19
    • ブロック数: 1
    • 短いブロックあたりのデータコードワード: 19
    • 長いブロックあたりのデータコードワード: 該当なし
    • ブロックあたりの ECC コードワード: 7
    • 短いブロック数: 1
    • 長いブロック数: 0
  • データコードワード列を短いブロックと長いブロックに分け、各ブロック末尾に ECC コードワード を計算して追加する
  • Reed–Solomon 誤り訂正コード計算の数学的過程は、長く退屈で興味深くないとして省略されている
  • 最終コードワード列は、データと ECC コードワードをインターリーブして構成される
    • 41 14 86 56 C6 C6 F2 C2 07 76 F7 26 C6 42 12 03 13 23 30 85 A9 5E 07 0A 36 C9
  • ジグザグ走査で描画する最終ビット列も、このコードワード列から生成される

5〜6段階: 固定パターンとコードワード配置

  • 固定パターン段階では、行 6 と列 6 に timing pattern を描画する
  • 3 つの角には、separator を含む 8×8 finder pattern をそれぞれ配置する
  • finder の周囲には一時的な dummy format bits が入る
  • コードワード配置段階では、右下隅から始まる ジグザグ走査 を計算する
  • ジグザグ走査は、機能モジュール (function module) を飛ばし、まだ埋まっていないモジュールを訪問する
  • データ、ECC、remainder モジュールは、最終コードワードのビット値とジグザグ順に従って描画される
  • 例として 16 進コードワード C5 は 2 進数 11000101 であり、[dark, dark, light, light, light, dark, light, dark] のモジュール列を生成する

7〜9段階: マスク適用とペナルティ計算

  • 各マスクパターンは非機能モジュール (non-function module) にのみ影響する
  • マスクはデータ、ECC、remainder モジュールに XOR で適用される
  • 実際の format bits は finder の周囲に描画される
  • ペナルティ探索では次の要素を検査する
    • 同じ色のモジュールが 5 個以上連続する横方向の run
    • 同じ色のモジュールが 5 個以上連続する縦方向の run
    • 同じ色の 2×2 box
    • 横方向の finder-like pattern
    • 縦方向の finder-like pattern
    • dark モジュールと light モジュールのバランス
  • 例の QR コードのサイズと色比率は次のとおり
    • 一辺の長さ: 21
    • 全モジュール数: 441
    • light モジュール: 221
    • dark モジュール: 220
    • dark モジュール比率: 49.887%
    • 半分からの偏差: −0.113%
  • 8 個のマスクの総ペナルティは次のとおり
    • Mask 0: 1204
    • Mask 1: 1134
    • Mask 2: 1084
    • Mask 3: 1081
    • Mask 4: 1121
    • Mask 5: 1100
    • Mask 6: 1189
    • Mask 7: 1137
  • 最も低い総ペナルティを記録したマスクは Mask pattern 3

ソースコード

  • Web アプリケーションの TypeScript ソースコードは file 0、file 1 として提供されている
  • コンパイル済みの JavaScript コードは creating-qr-code-steps.js で確認できる

関連記事

1件のコメント

 
GN⁺ 2024-11-19
Hacker News のコメント
  • QRコードの解説は、オンラインのどこを見ても Reed-Solomon誤り訂正計算を省いているようで残念
    ここでも著者は「長くて、退屈で、あまり面白くない」と言っていたが、みんながそう考えるせいで、今では見つけるのがかなり難しくなっている
    • 大学院で 符号理論 の授業を取ったが、受けた授業の中で最も厳密で、5人全員にとって難しかったものの、受けてよかったと思っている
      Reed-Solomonは学期の中盤を少し過ぎたあたりで扱い、要点は多項式に基づいているということ。十分な点があれば多項式は正確に決まるので、余分な点を入れておけば一部が失われても復元できる
      残りはこれをバイナリデータに適用する方法、つまり有限体を使う部分で、数学的には美しいがかなり複雑になる
    • 誤り訂正計算は、この2つのチュートリアルが説明している
      https://www.thonky.com/qr-code-tutorial/error-correction-cod...
      https://dev.to/maxart2501/let-s-develop-a-qr-code-generator-...
    • https://www.quaxio.com/an_artisanal_qr_code.html と PagedOut! Issue #2 には、長除法での誤り訂正計算まで含めてQRコードを一から作る内容がある
    • 長くて退屈だが、実は全体で いちばん面白い部分
    • 関連する Wikipedia記事 がある
  • 最近のVeritasiumの動画 I used to hate QR codes. But they're actually genius もこのテーマを扱っている
    https://www.youtube.com/watch?v=w5ebcowAJD8
  • 著者が受け取ったフィードバック集がかなり面白い: https://www.nayuki.io/page/poor-feedback-from-readers
    • 英語が苦手な人をあざ笑い、メールを送ってきた人たちがその国の代表的な標本であるかのように 国全体を見下すコメント は、送った人たちよりもブログ主について多くを物語っている
      コメントからエリート主義的な雰囲気が強く感じられる。ブログをざっと見たところ、Bitcoinでの寄付を求めつつ3ドルを提案しているが、手数料でかなりの部分が消える可能性は考慮していないようだ
    • 気に入らないメッセージを受け取ったとしても、不満を述べるときに 軽い人種差別 と書き手の英語力批判を混ぜないほうがいい
    • つたない英語をからかうのは、いつでも 愚かさのしるし。賢い人でも愚かな振る舞いはする
    • 悪いけれど、ブログの作者はかなり嫌な人に見える
      「いや、君の大学プロジェクトのチャットボットに私のGitHubリポジトリのコードを使ってはいけない。君のコーディング基準は私の基準に達していない。それに君の英語もひどい」みたいな感じ
    • 個人ブログの運営がどれほど大変になり得るかは分かる。あらゆる人を相手にしなければならない
      幸い、良いフィードバックも別に共有している: https://www.nayuki.io/page/decent-feedback-from-readers
  • かなり素晴らしい。同じ方式で デコーダ も見てみたい
    • コンピュータなしでQRコードを読む方法を扱ったPikoとblinryのガイドも気に入るかもしれない: https://qr.blinry.org/
    • 同感。スマホが、暗くてぼやけていて、4分の1ほど画面外に出ているQRコードでもあんなに速く解読するのを見ると、いつも驚く
    • QRリーダーをゼロから実装するガイドをずっと探している
      Googleで見かけるような「このコンピュータビジョンライブラリを差し込んで画像を入れれば結果が出る」というものは望んでいない
      すでにデコード済みの生の画像データがあると仮定したうえで、必要なすべてのアルゴリズムを実装していくガイドを探している
  • 解説があってよい。個人的にはただ素早く作りたかっただけなのに、検索すると広告だらけのサイトや「登録しないと利用不可」のサイトが出てきた
    GitHubでもいくつか見つけたが別の問題があったので、以前使ったことのある設計のよいライブラリで自分でさっと作り、15分ほどかかった
    https://greggman.github.io/qr-code/
    オプションをさらに追加することもできるが、実際のところ、ほとんどのユーザーにはそうしたオプションは不要だと思う
    • 役に立ったならうれしい。自分も以前から実装を自分で書いてみたかったが、見つけられたのはPythonやGolang向けの 完成パッケージ だけだった
      QRコードに関して、誤り訂正部分が分かる有用な資料があれば知りたい
  • 以前 Rust実装 を作った
    https://github.com/aabiji/qr
  • 現在の年の記事でないなら、タイトルに記事の年、ここでは 2018 を付けるのがよい慣例
    • 同意。元リンクには私の見る限り日付がなく、今はもう修正できない
  • よい。QRコードがどう動くのか学ぶことはずっと前からやることリストに入っていたが、よい 入門記事 だった
  • これで動作の仕組みが分かったので、SQLクエリでも使える: https://github.com/Florents-Tselai/pgQR