76回生 watcol
はじめまして。76回生(高1)のwatcolです。初めて部誌を書きます。拙い文章ですが、最後まで目を通していただけると幸いです。それでは、早速本題に移りましょう。
さて、みなさんは下のようなものを見たことがあるでしょうか。
図4.1: QRコード
近年見かけることの多い(この文化祭の会場でもよく見かけますね)この形、ご存知の方も多いと思いますが、QRコードと呼ばれるものです。
ここにURLなどの情報を入れておくと、読み取った時にWebサイトへアクセスできたり、LINEなどでは友達が追加できたりもします。(ちなみに、上のQRコードを読み取るとNPCAの公式Webサイト*1にアクセスできます。)
このQRコードは「マトリックス型2次元コード」と呼ばれるものの一つで、一種のバーコードのようなものです。しかし、一般的なバーコードに比べて多くの情報を詰め込める*2ほか、汚れや破損に強く、少しなら壊れていても読み取ることができます(経験がある方もいるのではないでしょうか)。
[*1] https://www.npca.jp
[*2] 数字のみだと7,089文字、英語だと4,926文字、日本語でも1,817文字詰め込めます。
しかし、このQRコードには一つ致命的な欠点があります。それは人間には理解できないということです。これでは手元に携帯やスマートフォンがなければ何が書いてあるか全くわかりません。皆さんも読めるようになりたいですよね??
そこで、この記事では、QRコードの読み方について紹介していこうと思います。
QRコードでは、2進数の1を黒いセル(1つ1つのブロックのこと)に、0を白いセルに置き換え、決まった順番で並べることによってデータを数値の列として表現しています。なので、どんなデータがどのように並べられているか、そしてそれをどのように解釈すればいいのかがわかれば、(理論上は)我々人間にもQRコードの内容を理解することができます。ということで、まずはQRコードの大まかな構造を見てみましょう。
図4.2: QRコードの構造
図4.2を見てください。これは、先程のQRコードをデータの役割ごとに色付けしたものです。早速、それぞれの部分について見ていきましょう。
図4.3: 定常部の詳解図
どのQRコードでも同じ形をしている部分です。次のように分類されます。
フォーマット情報領域は、そのQRコードについての情報を表す部分です。この情報によって後述するデータ本体の読み方が変わるため、注意して読む必要があります。
図4.4: フォーマット情報領域の読み方
さて、この領域の読み方ですが、まず上の図のような順番で黒を1
、白を0
として1セルずつ読んでいきます。このとき①と②では同じ情報になっているはずです。これはどちらかがかくれていたり、汚れていたりする場合でも読み取れるようにするための工夫なのですが、今回はどちらかを無視してもらって構いません。
その後、このデータ(上のQRコードでは111110110101010
になります。)をそれぞれの桁について101010000010010
と比べて、次のようなルールで処理します。(このような処理をXOR演算といって、競技プログラミングなどでよくつかわれます。)
0
とします。1
とします。この例では次のようになります。
010100110111000
となりましたね。このうち最初の2桁は「誤り訂正レベル」、その次の3桁は「マスクパターン」と呼ばれる情報です。残りの10桁は「誤り訂正符号」と呼ばれる、読み取りが間違っていないか調べるためだけの情報なので無視して構いません。では、この2つの情報について詳しく見ていきましょう。
QRコードがどのくらいの汚れを許容するかという情報が入っていて、低い方から「L」(7%の誤りを許容)、「M」(15%の誤りを許容)、「Q」(25%の誤りを許容)、「H」(30%の誤りを許容)です(ここでのパーセンテージは後述するデータ領域を100としたときのもの)。上で求めた数との対応は以下の通りです。
表4.1: 誤り訂正レベル
コード | 誤り訂正レベル |
---|---|
01 | L |
00 | M |
11 | Q |
10 | H |
誤り訂正レベルが高くなるほど汚れには強くなりますが、その代わりにQRコードが大きくなったり、読み取りに時間がかかったりするので、シチュエーションに合ったものを選ぶ必要があります。
ここまで言っておいてなんですが、正直誤り訂正レベルはQRコードを読むときには関係無いので、今回は無視してもらって構いません。
QRコードでは、コード内の白と黒のバランスを良くしたり、コード内に誤ってファインダーパターンが出て来たりしないようにするために、後述のデータ領域を加工するのですが、そのために使われるのがこのマスクパターンです。上で求めた数との対応は以下の通りです。
表4.2: マスクパターン
コード | マスクパターン |
---|---|
000 | \( (i+j) \bmod 2 = 0 \) |
001 | \( i \bmod 2 = 0 \) |
010 | \( j \bmod 3 = 0 \) |
011 | \( (i+j) \bmod 3 = 0 \) |
100 | \( ((i \div 2) + (j \div 3)) \bmod 2 = 0 \) |
101 | \( ij \bmod 2 + ij \bmod 3 = 0 \) |
110 | \( (ij \bmod 3 + ij) \bmod 2 = 0 \) |
111 | \( (ij \bmod 3 + i + j) \bmod 2 = 0 \) |
ここで、\( i \)は一番上の行を0としたときの行番号、\( j \)は一番左の列を0としたときの行番号です。この数式が成り立つようなセルを反転(白を黒に、黒を白にする)して読む必要があります。
数式を見ても分かりにくいと思うので、図にしてみました。
図4.5: \( (i+j) \bmod 2 = 0 \)
図4.6: \( i \bmod 2 = 0 \)
図4.7: \( j \bmod 3 = 0 \)
図4.8: \( (i+j) \bmod 3 = 0 \)
図4.9: \( ((i \div 2) + (j \div 3)) \bmod 2 = 0 \)
図4.10: \( ij \bmod 2 + ij \bmod 3 = 0 \)
図4.11: \( (ij \bmod 3 + ij) \bmod 2 = 0 \)
図4.12: \( (ij \bmod 3 + i + j) \bmod 2 = 0 \)
この図のピンクの部分を白黒反転させることになります。
これまでの作業、正直面倒ですよね。
ということでフォーマット情報から誤り訂正符号、マスクパターンが一瞬で分かる表を作りました。
表4.3: 早見表
フォーマット情報 | 誤り訂正符号 | マスクパターン |
---|---|---|
111011111000100 | L | \( (i+j) \bmod 2 = 0 \) |
111001011110011 | L | \( i \bmod 2 = 0 \) |
111110110101010 | L | \( j \bmod 3 = 0 \) |
111100010011101 | L | \( (i+j) \bmod 3 = 0 \) |
110011000101111 | L | \( ((i \div 2) + (j \div 3)) \bmod 2 = 0 \) |
110001100011000 | L | \( ij \bmod 2 + ij \bmod 3 = 0 \) |
110110001000001 | L | \( (ij \bmod 3 + ij) \bmod 2 = 0 \) |
110100101110110 | L | \( (ij \bmod 3 + i + j) \bmod 2 = 0 \) |
101010000010010 | M | \( (i+j) \bmod 2 = 0 \) |
101000100100101 | M | \( i \bmod 2 = 0 \) |
101111001111100 | M | \( j \bmod 3 = 0 \) |
101101101001011 | M | \( (i+j) \bmod 3 = 0 \) |
100010111111001 | M | \( ((i \div 2) + (j \div 3)) \bmod 2 = 0 \) |
100000011001110 | M | \( ij \bmod 2 + ij \bmod 3 = 0 \) |
100111110010111 | M | \( (ij \bmod 3 + ij) \bmod 2 = 0 \) |
100101010100000 | M | \( (ij \bmod 3 + i + j) \bmod 2 = 0 \) |
011010101011111 | Q | \( (i+j) \bmod 2 = 0 \) |
011000001101000 | Q | \( i \bmod 2 = 0 \) |
011111100110001 | Q | \( j \bmod 3 = 0 \) |
011101000000110 | Q | \( (i+j) \bmod 3 = 0 \) |
010010010110100 | Q | \( ((i \div 2) + (j \div 3)) \bmod 2 = 0 \) |
010000110000011 | Q | \( ij \bmod 2 + ij \bmod 3 = 0 \) |
010111011011010 | Q | \( (ij \bmod 3 + ij) \bmod 2 = 0 \) |
010101111101101 | Q | \( (ij \bmod 3 + i + j) \bmod 2 = 0 \) |
001011010001001 | H | \( (i+j) \bmod 2 = 0 \) |
001001110111110 | H | \( i \bmod 2 = 0 \) |
001110011100111 | H | \( j \bmod 3 = 0 \) |
001100111010000 | H | \( (i+j) \bmod 3 = 0 \) |
000011101100010 | H | \( ((i \div 2) + (j \div 3)) \bmod 2 = 0 \) |
000001001010101 | H | \( ij \bmod 2 + ij \bmod 3 = 0 \) |
000110100001100 | H | \( (ij \bmod 3 + ij) \bmod 2 = 0 \) |
000100000111011 | H | \( (ij \bmod 3 + i + j) \bmod 2 = 0 \) |
ご参考までに。
ところで、上の例でのフォーマット情報領域は111110110101010
でしたね。これを上の早見表に照し合わせると、マスクパターンは「\( j \bmod 3 = 0 \)」であることが分かります。ルールに従ってセルを反転させると以下のようになります。
図4.13: マスク処理後
さらに、これを色分けすると以下のとおりです。
図4.14: データ領域
この章(節?)では、これらの領域を解読していきます。
はじめに、このデータ領域の読み進め方ですが、以下のように右下から2列ずつ、ギザギザに読んでいきます。この場合も白は0
、黒(と赤)は1
に変換します。
図4.15: データ領域の読み方
例えば図4.14の右下の黄緑の部分は「0100
」となります。それではこのことを頭に入れつつ、データ領域を解読していきましょう。
QRコードでは扱える文字数を少しでも増やすために扱うデータの種類(数字、英語、日本語など)に応じて符号化モードと呼ばれるものが存在します。このモード指示子はそのQRコードで使われる符号化モードを示すためのものです。
表4.4: モード指示子
モード指示子 | 符号化モード | 扱える文字 | データ密度 |
---|---|---|---|
0001 | 数字モード | 数字(0~9) | 10セル/3文字 |
0010 | 英数字モード | 数字(0~9)、大文字アルファベット(A-Z)、空白、$、%、*、+、-、.、/、: | 11セル/2文字 |
0100 | 8ビットモード | 全てのデータ | 8セル/1バイト |
1000 | 漢字モード | 漢字、ひらがな、カタカナ、全角英数字など | 13セル/1文字 |
後述するデータコード語の文字数(8ビットモードの場合はバイト数)を表すものです。この領域の大きさはQRコードの大きさや符号化モードによって変わり、その対応は以下の通りです。(QRコードの大きさは「バージョン」というもので表現され、例の場合はバージョン2です。)
表4.5: 文字数指示子の大きさ(セル数)
バージョン | 数字モード | 英数字モード | 8ビットモード | 漢字モード |
---|---|---|---|---|
1~9 | 10 | 9 | 8 | 8 |
10~26 | 12 | 11 | 16 | 10 |
27~40 | 14 | 13 | 16 | 12 |
上の例ではバージョン2、8ビットモードなので8セル読み進めると、00010011
で、10進数に変換すると19になります。なので、下のデータコード語は8セル×19バイトで152セルあることが分かります。
やっと本題です。ここからQRコードの中身(「https://・・・」といった情報)を読んでいきます。符号化モードによって読み方が大きく異なるので、それぞれ見ていきましょう。
まず10セル読み進めて、10進数に直します。例えば0001111011
の場合「123」です。このように、上で得た文字数と照し合わせながら、3文字ずつ読み進めていきます。最後に1文字余ったら4セル、2文字余ったら7セル読み進めて、10進数に直します。これを順番に繋ぎ合わせると、数字が出来上がります。
まず11セル読み進めて、10進数に直します。そして、これを45で割って、商、余りをそれぞれ以下の表を見て英数字に直します。
表4.6: 英数字モード
コード | 文字 |
---|---|
0 | 0 |
1 | 1 |
︙ | ︙ |
9 | 9 |
10 | A |
︙ | ︙ |
35 | Z |
36 | 空白 |
37 | $ |
38 | % |
39 | * |
40 | + |
41 | - |
42 | . |
43 | / |
44 | : |
例えば10000011000
の場合10進数に直すと1048で、45で割ると商が23、余りが13だから「ND」となります。このように2文字ずつ読み進め、1文字余ったら6セル読んで10進数に直し、上の表で英数字に直します。これを繋ぎ合わせると、英数字の文字列が出来上がります。
このモードは様々な種類のデータを表現できるのですが、英数字の文字列として読むときは、8セルずつ読み進めて、10進数に直し、以下の表(Asciiコード表といいます。)を使って文字に変換します。
表4.7: アスキーコード表
コード | 文字 |
---|---|
32 | 空白 |
33 | ! |
34 | " |
35 | # |
36 | $ |
37 | % |
38 | & |
39 | ' |
40 | ( |
41 | ) |
42 | * |
43 | + |
44 | , |
45 | - |
46 | . |
47 | / |
48 | 0 |
49 | 1 |
︙ | ︙ |
57 | 9 |
58 | : |
59 | ; |
60 | < |
61 | = |
62 | > |
63 | ? |
64 | @ |
65 | A |
︙ | ︙ |
90 | Z |
91 | [ |
92 | \ |
93 | ] |
94 | ^ |
95 | _ |
96 | ` |
97 | a |
︙ | ︙ |
122 | Z |
123 | { |
124 | | |
125 | } |
126 | ~ |
これを繋ぎ合わせると、文字列ができます。コードがこの表に無い場合、諦めて別の方法で読む必要があります。(ここでは解説しません。)
まず13セル読み進め、16進数(123456789abcdef
で表す)に直します。例えば0000100100000
なら120
になります。そしてこれをc0
で割った商について、00
〜1e
なら81
を、1f
〜2a
ならc1
を足します。(例の場合は120÷c0=01
だから01+81=82
)また、余りについては40
を足します。(例だと120%c0=60
だから60+40=a0
)そしてこれらをつなげたもの(82a0
)をこちらの表を使って文字に変換します。(例だと「あ」)このように13セルずつ読んでいき、一文字ずつ繋げると文字列が出来上がります。
こんな感じ
図4.16: QRコードを読む
ということでこのQRコードの中身は「https://www.npca.jp」(NPCAの公式サイト)であることが分かりました。ここからはおまけです。
白を最低4つ、残りのセル数が8で割り切れるようになるまで続けます。入っているデータがギリギリの場合は省略できます。ちなみに「埋め草」とは元々穴を埋めるために使った草や雑木のことで、そこから転じて新聞や雑誌ではスペースを埋めるための記事のことを「埋め草」と言ったりします。ここでは空いたスペースを埋めるデータ列のことを言います。(話題不足)
「11101100
」、「00010001
」が交互に並んでいるものです。なぜ「00000000
」ではダメかというと白が極端に多くなるからです。ちなみに「埋め草」とは元々穴を埋めるために使った草や雑木のことで、そこから転じて新聞や雑誌ではスペースを埋めるための記事のことを「埋め草」と言ったりします。ここでは空いたスペースを埋めるデータ列のことを言います。(2回目)(ホントに話題がない)
QRコードに汚れなどがあったり、真ん中に変なロゴが入っていたり、単純に読み取りミスをしたりしたときなど、それを確認・修正できないと読み取り精度が格段に下がってしまいます。そこで、誤り訂正という読み取り時のミスを訂正するための技術があり、そのためのデータがここに入っています。QRコードではリード・ソロモン符号という技術が使われているのですが、僕には何のことかさっぱり分かりません。数学などに詳しいという方は調べてみてください。そして僕に教えてください。
これで長い長い解説は終わりです。とはいえ、読み方自体の説明はごく少量でしたね。ほんまか?
ということで、これからはQRコードを最速で読む方法を解説します。
ということで、暇なときに試してみてはいかがでしょうか。時間が溶けますよ。
気付けばなかなかの大作になってしまいましたが、これでやっとおしまいです。軽い気持ちでページを開けて、後悔した方もいるのではないのでしょうか。ちなみに、この記事中に大量に存在する画像は「Krita」というソフトで作成しました。興味のある方は調べてみてください。非常にドット絵を作るのに向いています。(個人の感想)最後に、この記事を最後まで読んでくださった奇特な方、本当にありがとうございました。