コンピューターなしでQRコードを読む技術

 (qr.blinry.org)
4 ポイント 投稿者 GN⁺ 2024-01-23 | 1件のコメント | WhatsAppで共有
  • QRコードを手で解読できるように、バージョン1の21×21モジュール構造からマスク解除、バイト変換までを段階的に整理
  • 位置検出パターン、タイミングパターン、形式情報、quiet zoneのような特殊領域は認識には必要だが、実際のデータ読み取りでは飛ばす必要がある
  • データは形式情報からマスクパターンと誤り訂正レベルを確認した後、マスクの黒いモジュール位置ごとにQRコードのモジュールを反転して復元する
  • 右下から始めて2列ずつジグザグ順に読み、Byteモードでは長さ8ビットの後に続く8ビット単位のまとまりが文字バイトになる
  • 誤り訂正領域まで手で解く必要はなく、単純なQRコードなら長さフィールドが示す分だけバイトを読み、ASCII表に変換すれば解読できる

手で読むQRコードの準備

  • 練習用QRコードは3つの方法で用意できる
    • 任意のテキストを入力して、以下で説明するQRコードを更新する
    • カメラで既存のQRコードをスキャンして、読み方を学ぶ
    • ランダムな英単語で練習する。単語自体は表示されないため訓練用として使える
  • 例のQRコードは21×21モジュールの大きさ
  • QRコードでピクセルに相当する単位は**モジュール(module)**と呼ぶ
  • QRコードのサイズは**バージョン(version)**で区別される
    • 最小バージョンは21×21モジュール
    • 以後のバージョンでは一辺の大きさが4ずつ増える
    • 21×21モジュールのQRコードはバージョン1

QRコードで飛ばす特殊領域

  • 位置検出パターン(finder pattern) はスキャナーが最初にQRコードを識別するのに役立つ
  • 位置検出パターンの周囲の空白行は、内容を読むときに飛ばす必要がある
  • バージョン1のQRコードには**アライメントパターン(alignment pattern)**がない
    • アライメントパターンはスキャナーがQRコードを正しく読むのを助ける追加パターン
  • タイミングパターン(timing pattern) は白黒モジュールが常に交互に現れる2本の線で、スキャナーがQRコードを正しく読むのに役立つ
  • 形式情報はマスクパターンと誤り訂正レベルを決定する
    • 縦の形式情報と横の形式情報がある
    • タイミングパターンはその2本の線をどちらも横切って通る
  • quiet zoneはQRコードの周囲にある白い余白
    • スキャナーがQRコードの始まりと終わりを識別するのに役立つ

マスクパターンの解除

  • QRコードは大きな黒い塊や白い塊を避けるために**マスク(mask)**を使う
  • マスクには全部で8種類の選択肢がある
  • 例では黒いモジュールを1、白いモジュールを0として読んでマスクパターンのビットを確認する
    • 例のビットは2進数の110
    • 110は10進数の6に相当する
  • 各マスク種別にはあらかじめ定義されたパターンがある
  • 例のQRコードのパターンは白黒の虹の一部のように見えるパターン
  • マスクをデータ領域の上に繰り返し重ね、その中で黒いモジュールになっている位置ごとにQRコードのモジュールを反転する
  • すべてのマスク種別のチートシートを含むDIY zineが提供されている

エンコーディングモードと読み取り順

  • 内容の解読はまずエンコーディングモードを確認するところから始まる
  • エンコーディング情報は常に右下隅にある
  • エンコーディングモードも先にマスクを適用解除しなければならない
    • 例ではチートシートを見ながら2つのボックスをXORする
  • エンコーディングモードにはNumeric、Alphanumeric、Byte、ECI、Kanjiなどがある
  • 例のQRコードのエンコーディングモードはByte(4)
  • 内容は右下隅から始まる
    • 2列の間をジグザグに上がりながら読む
    • 次に左側の次の2列でジグザグに下がりながら読む
    • 特殊領域は常にすべて飛ばす

長さとバイトの解読

  • 最初の4ビットはエンコーディングモード
  • Byteモードでは次の8ビットが内容の長さを指定する
  • その後は8ビットごとに1つの内容バイトになる
  • 長さ情報もマスクを適用解除しなければならない
  • 例のマスク解除後の長さ情報は00001100
    • 10進数で12
    • 内容全体の長さが12バイトという意味
  • 最初のマスク解除バイトは01001000
    • 16進数で0x48
    • 対応するASCII文字はH
  • 2番目のマスク解除バイトは01100101
    • 16進数で0x65
    • 対応するASCII文字はe
  • 残りのバイトは練習用として残されており、先に読んだ長さフィールドが示す文字数だけ読めば止めてよい

ASCII表と誤り訂正

  • ASCII表を使って16進数の値を文字に変換できる
  • 小文字はaが0x61から始まり、zが0x7Aで終わる
    • 間の文字は数えて見つけられる
  • 残っている領域がすべて内容というわけではない
  • QRコードには**誤り訂正(error correction)**も含まれる
    • 一部が破損したり、ぼやけたり、欠けたりしてもQRコードを読めるようにする
    • 誤り訂正は数式で生成されるが、手で読む目的では扱わない
  • 単純なQRコードを手で解読する手順を身につけた後は、random codeボタンで短い英単語を練習したり、Scan codeボタンで実際のQRコードをスキャンできる
  • ソースコードはCodebergにある
    • UTF-8エンコーディングモードを説明するPRを特に歓迎する

関連記事

1件のコメント

 
GN⁺ 2024-01-23
Hacker News の意見

  • 90年代末か2000年代初めに、Atari 8ビットディスクの内容を PC に移したかった。
    Atari の SIO ポートと PC のシリアルポートをつなぐ SIO2PC ケーブルとソフトウェアのことは知っていたが、当時は自作できるほどの電子工学の腕がなかった。
    結局 Atari で Basic プログラムを書いてディスクをセクタ単位で読み、グラフィックモード 3 の大きな4色ピクセルで画面に描画し、PC の TV カードに Atari を接続したうえで Delphi プログラムにスクリーンショットを撮り続けさせ、データを復号させた。
    空セクタのせいでピクセル位置の補正がずれるので、マスクパターン、チェックサム、セクタアドレスまで入れた。その方法で全ディスクの内容を PC に移すことができた。
    今でもこれを自分の最高のエンジニアリング上の成果だと思っている。
    10年ほど後には AspeQt という SIO2PC プログラムを作った。より新しいコミュニティフォークである RespeQt は、今でもこの分野で最もよく使われているツールで、AtariAge には専用のサブフォーラムもある: https://forums.atariage.com/forum/184-respeqt-sio2pc-softwar...

    • 初代 iPod のファームウェアとキーをリバースエンジニアリングした方法を思い出す。
      LCD バックライトでビットパターンを点滅させ、カメラでそのデータを読み取ったそうだ: https://mastodon.social/@bagder/111538350617290554
    • ロックされたシステムが増えるほど、こうしたディスプレイベースのデータ流出には確かに将来性がありそうだ。

  • 「誤り訂正は複雑な数学なので、手で読む場合は気にしない」という説明は、もう少し詳しくあるべきだ。
    数学が難しいのは分かるが、誤り訂正データが末尾に付くのか、各バイトの後ろに付くのか、途中に入るのかくらいは知りたい。
    破損していない QR コードなら、誤り訂正があっても数学の部分だけ飛ばして手で読めるのかも知りたい。

    • バーコードは最後の数字をチェックサムとして使い、数字を足したり掛けたりしたあと % 10 のような計算をして 0〜9 のどれかになる。
      そのためデータが間違っていても偶然チェックサムが合う確率は 1/10 あり、いずれにせよ最後の数字は実際の商品固有のバーコード ID には重要ではない。
      Home Depot に返品していた商品のバーコードが破れてチェックサムの数字が擦れてしまったことがあり、店員が手動検索する前に計算しようと必死に急いだが、結局店員の方が早かった。忘れられない。
      https://www.gs1.org/services/how-calculate-check-digit-manua...
      https://www.simplybarcodes.com/barcode_check_digit_calculato...
    • QR コード内のデータは複数のアルファベットのいずれかでビットストリームとしてエンコードされ、バイトはその一つにすぎない。
      その後、サイズと誤り訂正レベルに応じてビットストリームをブロックに分け、各ブロックの誤り訂正データを計算してからブロックをインターリーブする。
      そのため、この方法は誤り訂正レベルに関係なく QR バージョン 5 を超えると失敗し、バージョン 3〜5 でも高い誤り訂正レベルなら失敗する。
    • An Artisanal QR Code は、筆算の割り算に似た算術でチェックサムを手計算する方法を示している。
      実際には情報の種類に応じて Reed-Solomon と BCH という少し異なる2つのコードが使われる。
      https://www.quaxio.com/an_artisanal_qr_code.html

  • 関連記事:
    Decoding small QR codes by hand (2012) - https://news.ycombinator.com/item?id=36173441 - 2023年6月、コメント69件
    How a QR code works - https://news.ycombinator.com/item?id=32837565 - 2022年9月、コメント114件
    Creating a QR Code step by step - https://news.ycombinator.com/item?id=24119124 - 2020年8月、コメント41件
    Creating a QR Code step by step - https://news.ycombinator.com/item?id=18360847 - 2018年11月、コメント34件

  • 記事自体も素晴らしいが、入力値に応じてすべての図を動的に生成している点がさらにすごい。

  • QR コードの読み方についての説明がよかったし、一般的な UPC のような一次元バーコードを解読する記事としてはこれも悪くない:
    [https://scanbot.io/blog/how-do-barcodes-work/](https://scanbot.io/blog/how-do-barcodes-work/）

  • 10年ほど前にQRコードを手で読もうとしたが、マスクパターンのせいで諦めた
    データタイプを突き止める前にも、マスクパターンをXORで適用しなければならない
    このマスクパターンが実際のQRコードリーダーにどれほど役立っているのか気になる
    先月は最適な誤り訂正設定を調べてみたが、画面に表示される完全なマトリクスのように破損していない場合、答えは「なし」だったし、この結論を見つけるのは簡単ではなかった
    複数の設定やスキャン実装を実環境で比較した資料は見つからず、自分で画面上の小さなQRをさまざまな誤り訂正レベルで表示し、カメラを揺らして読み取り問題を再現してみたが、設定間に有意な差は見られなかった
    位置合わせマーカーが少なくとも4つあり、大きな余白とタイミングパターンまであるのに、マスクがないせいで白い塊ができることが本当に大きな差を生むのかと思う
    視覚的にQRを読む試みを諦めた2つ目の理由は、たいてい下にURLが代替テキストとして書かれていたからだが、その後、代替テキストがないケースも何度か見たものの、非常にまれだった

    • 誤り訂正は不思議だ
      使わなければメッセージが占めるスペースは少なくなり、QRは小さくなる
      ステッカー印刷のように固定されたスペースに収める必要があるなら、ピクセルを物理的に大きくでき、安定した読み取りには誤り訂正よりも大きなピクセルのほうが役に立った
      メッセージ長によっては、最終的なQRサイズを変えずに誤り訂正レベルを上げられる場合があり、そのときは両方を得られることになる
    • 誤り訂正は、「メッセージをもっと小さくしてQRコードの可読性を高めるにはどうすればいいか」と考える人のためのものではない
      追跡パラメータが山ほど付いたURL全体をバージョン25、117x117コードに入れて大きな看板に貼り、鳥のフンが落ちたり誰かがステッカーを貼ったりしてもデータが生き残るようにしたい人のためのものだ
    • 昨年、似た実験をしたが、少なくとも3DプリントQRコードでは誤り訂正がないほうが最も良かった
      どれだけ小さく出力しても検出可能かを見る実験で、隣のコメントのように個々のピクセルが大きくなるためだと思われる

  • 10年ほど前に投稿されたQR解読動画: https://www.youtube.com/watch?v=KA8hDldvfv0（20分）
    QRコードを段階的に作る私のインタラクティブなWebページもある。基本的には逆方向のプロセスだ: https://www.nayuki.io/page/creating-a-qr-code-step-by-step

  • 誤り訂正が気になってきたが、QRコードは復元可能な割合を7%から30%まで変えて設計できるという
    興味深い: https://docs.beaconstac.com/en/articles/6018654-what-is-erro...

    • 誤り訂正は本当に興味深いテーマだ
      Shannonは20世紀半ばに理論的な限界を見つけたが、その限界に到達する方法は誰にも分からなかった
      1990年代にターボ符号の特許で突然その限界に近づくと、学界は信じがたいという反応を示した
      もちろん、こうした技術のおかげで高速で信頼性の高いモバイルネットワークが可能になった

  • 2023 Mystery Huntの派生パズルの中に、誤り訂正でも復元できないほど壊れたQRコードを手で解読しなければならない問題があった
    このコメント欄に出ているガイドはすべて見て、役には立ったが、非常に優れているというほどではなかった
    だから、こうしたより詳しい記事が増えるのはうれしいし、この記事は確かに完成度が高そうだ
    気になるならパズルはここにあり、QR解読は後半に出てくる: https://puzzles.mit.edu/2023/abcde.puzzlefactory.place/puzzl...

  • Wikipediaを見ると、QRコードは1994年に日本の自動車部品メーカーが自動車部品のラベリング用に発明したという
    もし今日発明されていたら、もっと改善できただろうかと思う
    もっと小さくできたり、もっと読みやすくできたりしたのだろうか？

    • 十分に優れた新設計を妨げるものは何もない
      1994年にもバーコードはすでにどこにでもあったが、QRコードが広まるのを妨げることはできなかった
      もしかすると、改善の余地はあまりないのかもしれない。概念を大きく変えてNFCのようなものに向かう場合を除けば
    • 今日発明されていたら、六角形だったように思う