QRコードを人力で読み取る

QRコードといえば1994年にデンソーが開発した四角いバーコードですが、これ、何も見ずに読めたらかっこよくね？ という安易な考えで人力読み取りしてみようと思います
目grepがあるなら目OpenCVもあっていいと思う...うん

QRコードの生成

まず人力読み取りするために必要なQRコードを生成していきましょう

今回はGoogle Charts APIのQRコード生成を利用していきます。 Reference
しかしこのAPIはDeprecatedなのでいつ消えてもおかしくありません... 使用は非推奨です

このAPIの使い方は基本的にこんな感じです、文字コードを指定しないとデフォルトでUTF-8になります。
https://chart.googleapis.com/chart?cht=qr&chs=<width>x<height>&chl=<data>
今回は"Sweak"という文字列を300×300の大きさでQRコードにしていきたいと思うのでこんな感じになります
https://chart.googleapis.com/chart?cht=qr&chs=300x300&chl=Sweak
ブラウザで先程のURLを開くとこんな感じのQRコードが生成されると思います

QRコードの読み取り

QRコードの基本構造

QRコードは3辺に大きな四角があるのが基本です。
これはコードが上下左右どこを向いているのか読み取り機に示すものになります。
この画像で紫や赤で囲われた所がフォーマット情報が記載されている場所です。
(赤と紫が2箇所ずつありますが、同じデータです。)

bit	機能
14:13	誤り訂正レベル
12:10	マスク情報
9:5	誤り訂正機能情報
4:0	エラー訂正bit

この上の値に対してマスクが掛けられているので、解読する場合は101010000010010とXORします。

オレンジがモード指定 (数字, 英数字, バイナリ(8bit)、漢字(13bit))
黄色がデータ内の文字数指定
緑色が実データになります。

※MSB: 最上位bit, LSB: 最下位bit

マスク判定

QRコードには真っ黒や真っ白にならないようにマスクというものが施されています。
QRコードには8種類のマスクがあり、内容を解読するためにはマスクを解く必要があるので、どのマスクが掛けられているのか判定します。
マスクを判定するにはフォーマット情報の中からマスク情報が記述された部分(12:10のbit)を101とXORした数になります。

8種類のマスク概要

Mask Number	Pattern
000	(i + j) % 2 = 0
001	i % 2 = 0
010	j % 3 = 0
011	(i + j) % 3 = 0
100	(i / 2 + j / 3) % 2 = 0
101	(i * j) % 2 + (i * j) % 3 = 0
110	((i * j) % 3 + i * j) % 2 = 0
111	((i * j) % 3 + i + j) % 2 = 0

(WikipediaにCC0ライセンスでとても分かりやすい画像が添付してあったので引用させて頂きました)

今回のQRコードでのマスクは010なので101とXORすると111になります
ということは8つ目のマスクでパターンと重複した色を反転します

反転した後のQRコードがこちらになります (データ部のみ反転済み)

いざ解読

QRコードは右下から

12	11	10	9
14	13	8	7
16	15	6	5
18	17	4	3
20	19	2	1

の順番で読んでいくので

モード指定部を見ていくと0100 (バイナリモード(8bit))
文字数指定部 (00000101)₂ = 5文字
となっていることが分かります。

緑色のデータ部を読み、UTF-8-character tableと照らし合わせると

(01010011)₂ : S
(01110111)₂ : w
(01100101)₂ : e
(01100001)₂ : a
(01101011)₂ : k

となり、解読することが出来ました

感想

(Qiita初投稿がこんな物で本当に良いのだろうか...？)

参考

What Is A QR Code And How Does It Work? http://www.ucreative.com/articles/what-is-a-qr-code-and-how-does-it-work/
QR code - Wikipedia https://en.wikipedia.org/wiki/QR_code
https://en.wikipedia.org/wiki/QR_code#/media/File:QR_Character_Placement.svg
QRコードの概要 - 株式会社デンソーエスアイ https://www.denso-si.jp/dictionary/dic_qr/GeneralDescriptionoftheQRCode.pdf