2018の18日目の記事です。昨日は@kawano-fusicがOJTで作った社内の振返り会システムを全力で振り返っていました。最近の世の中はQRコードで溢れています。Webサイト行くにもQRコード、飛行機乗るにもQRコード、友達になるにもQRコード、電子決済するにもQRコード、猫も杓子もQRコード、QRコード...。16日目で@gorogoroyasuが触れていましたが、先日リリースされたOpenCV4.0でもQRコードまわりの強化がなされているようです。このQRコードの仕組みを知っている人はあまりいません。マーカーと生のビット列を並べてあるだけなんて思ってやしませんか?もしそう思っていたならば、この脳みそがとろけそうな複雑さに驚愕するでしょう。今回は、QRコードにDeepにDiveして、データ符号化や誤り訂正について解説してみようと思います!実務的にはあんまり役には立たないかもしれませんが、単に技術的な読み物として純粋にQRコードを楽しんで、QRコードスゲェ!となってくれれば幸いです。面白いですよ、QRコード。QRコードの特徴まずは手始めに、QRコードはどんな特徴を持っているのかを見ていきましょう。略なだけあって、高速に読み取ってくれます。(今のコンピューターの性能だと多少効率悪くても人間には高速に感じそうですが、誕生したのが1994年なので...)また、回転したり歪んだりしても安定して読み取れるようにもなっています。存在感のある位置検出パターン/位置合わせパターンはもちろんですが、大きくあと2つあります。目立つ3つの隅のシンボルもあるし、よーく見ると白黒が交互に現れるラインが...白ばっかり、黒ばっかりのQRコードって見たことなくないですか?詳しくはまた後ほど。安定した読み取り性能を持つため、かなり大きなQRコードの作成も可能です(最大で177x177)。英数字(+一部の主要な記号)であれば、最大の177x177のQRコードで4,296文字が格納できます。4,296[文字]このデータ符号化手法についても後ほど解説します。汚れ・破損に強いQRコードには、「リード・ソロモン符号」を使った誤り訂正方式を採用しています。DVDなんかにも使われている一般的なものです。仕様として誤り訂正のレベルは4段階用意されていますが、最大30%欠損しても読み取れてしまいます。この誤り訂正の内容についてもできる限り解説してみます。実は日本製これはちょっと有名かもしれませんが、QRコードはデンソー(現在は分離しデンソーウェーブ)が開発したものです。そのため、かなや漢字(Shift_JIS)が格納できる仕様があったりします。QRコードの構造QRコードは次のような構造になっています。機能パターン画像からの読み取りを行いやすくするためにある領域です。クワイエットゾーンシンボルを囲むセル4つ分の空白領域です。周囲のノイズからシンボルを切り離すことで読み取るべき領域を明確にします。位置検出パターンシンボルの3つの隅に配置された7x7のパターンです。1つの隅にこのパターンが無いので、シンボルの位置と同時に向きも分かってしまいます。360度どの方向からスキャンしても、このパターンの中心を通る場合は必ず黒白黒白黒の比率が1:1:3:1:1になります。画像から読み取る際は、これを目印に位置検出パターンを認識します。位置検出パターンの周囲にある分離パターンも、検出のしやすさに地味に貢献しています。位置合わせパターン大きなシンボルになると出現する、5x5のパターンです。斜め上から読み取られてシンボルが台形になったり、ちょっと歪んだりしていた場合に変形を補正するために使われます。タイミングパターン言われないと気づかない、白黒が交互に現れるライン。こちらも同様に変形の補正用です。符号化領域データを持っている領域です。型番情報QRコードのバージョンの情報を持っている領域です。バージョンといっても、ここではシンボルの大きさを表します。21x21のバージョン1から、4セル刻みで177x177のバージョン40まで存在します。型番情報を持っているのはバージョン7からです。7未満は小さいので、型番情報がなくてもセルの数を数えるやり方で十分ということではないかと。ちなみに、2箇所に存在していますが同じ値が入っています。汚れなどで片方が読めなくなっても大丈夫なように冗長化しています。誤り訂正レベルとマスク識別子の情報を持っている領域です。誤り訂正レベルは訂正できるエラーの数を決めます。レベルは4段階用意されています。マスク識別子はデータ格納時に適用するマスクパターンの種類を表します。このマスクによって読み取り性能を向上させます。こちらも冗長化されており、左上の位置検出パターンの周囲の領域と、他の2か所を合わせたものには同じ値が入ります。データおよび誤り訂正コード語QRコードの仕様に沿って符号化されたデータとそれに対する誤り訂正コードが入っています。以降は、このデータの符号化手法と誤り訂正方式について解説していきます。データ符号化さて、ようやく本題です。QRコードは、情報を詰め込むために独自の手法でデータを符号化しています。符号化データは、次の要素を順に並べたものです。誤り訂正コード語ここでは、それぞれの要素を順に解説していきます。モード指示子QRコードでは、少しでも多くのデータを格納するため、扱う文字種によって詰め込み方を変えます。これを符号化モードと呼び、以下の4種類が用意されています。この符号化モードを表す4ビットのデータがモード指示子です。小文字のアルファベットは扱えない。バイナリがそのまま入れられるのでオールマイティ。漢字、2バイトのひらがな・カタカナ・英数字など。文字数指定子その名の通り、格納される文字数を指定するものです。バージョンと符号化モードによって格納できる文字の最大数が決まるため、それに合わせて文字数指示子に使われるビット数が変わります。符号化モードごとに符号化の手法が異なります。数字モードデータを3文字ずつに区切り、それぞれを3桁の数字とみなして10ビットで表します。余りが出たら、1桁なら4ビット、2桁なら7ビットで表します。0101101英数字モードこのモードでは、各文字に数値が割り当てられています。44そして、データを2文字ずつに区切り、それぞれを45進数的に解釈して11ビットで表します。1文字目の値に45を掛け、2文字目の値を加えます。余りが出たら、対応する値を6ビットの値にします。0010118ビットモードバイナリそのままです。漢字モード各文字のShift_JIS表現を以下のように変換します。途中で符号化モードを切り替えることも可能です。データコード語を繰り返していくことになります。むやみに符号化モードを切り替えるとモード指示子と文字列指示子のオーバーヘッドによって却ってサイズが大きくなる可能性があるので注意が必要です。そのあたりを完全に最適化しようと思うと...ものすごくめんどくさいコードが見えます。終端パターンデータコード語のあとに付け加えて終端を示すパターンです。具体的には0000の4ビット。データ容量の残りが4ビット未満であれば、溢れた部分は省略可能です。埋め草ビットQRコードでは8ビット(バイト)単位でデータを格納していくので、きれいに8ビットごとに区切れるようにする必要があります。そのため、終端パターンまでのデータサイズが8で割り切れるように、埋め草ビットとして0を追加します。埋め草コード語QRコードが格納可能なバイト数はバージョンと誤り訂正レベルによって決まります。埋め草ビットまでのデータのバイト数が格納可能なバイト数に満たない場合は、埋め草コード語と呼ばれるビット列で埋めていきます。具体的には、11101100と00010001を交互に追加していきます。埋め草コード語までのデータに対する、誤り訂正のためのデータです。誤り訂正の概要QRコードには、「リード・ソロモン符号」と呼ばれる誤り訂正符号が採用されています。全体的なイメージを持ってもらうために、ひとまず概要だけ説明します。端的に一つの式で表すと、次のようになります。埋め草コード語)のベクトル(1バイト/要素)。$\mathrm{T}$はあまり気にしなくて大丈夫です。計算できるように転置しているだけなので。検査行列データを格納するとき$\boldsymbol{m^{\mathrm{T}}}$に生成行列$\boldsymbol{G}$を掛け合わせると、$\boldsymbol{m}$は誤り訂正機能付符号に変換されます。$\boldsymbol{m}$対応する誤り訂正符号を生成してくっつけるイメージです。今後の説明のために、以下のように$\boldsymbol{x}$を定義しておきます。\boldsymbol{G}QRコードには、この$\boldsymbol{x}$が格納されています。データを読み取るとき読み取ったデータを以下のように定義します。\boldsymbol{e}$\boldsymbol{e}$は各要素のエラーをベクトルにしたものです。0となります(設定した誤り訂正能力の範囲内では)。エラーが検出された場合、頑張って計算すればエラーの数や位置、内容まで特定することができます。先に検査行列を使ってどのように誤り訂正を行うのかを見ていきましょう。リード・ソロモン符号では、誤り行列は以下の$n\times2t$行列として定義されます。$n$は$\boldsymbol{x}$の長さ、$2t$は誤り訂正符号の長さ(つまり$n-2t$が本来のデータの長さ)になります。説明は長くなるので省略しますが、$t$は訂正可能なエラーの数になります。$\alpha$は今のところは深く考えなくて大丈夫です。便宜的に置いている未知数で、エラー情報を求める過程で消えてなくなります。1$なので、法則性が見えてきますね。\end{array}\right)\end{eqnarray}QRコードからデータを読み取るときを考えます。以下の式が成り立ちます。\boldsymbol{H}\end{align}$\boldsymbol{s}$と$\boldsymbol{H}$の値は分かっているので、そこから$\boldsymbol{e}$を求める問題になります。分かるのでめでたしめでたしです。残念ながら単純には求められません。$\boldsymbol{e}$は$n$次のベクトル、$\boldsymbol{H}$は$n\times2t$行列です。未知数が多すぎます(ちなみに$\boldsymbol{H}$のランクは$2t$です)。やって求めるのかというと...先ほど、さらっと「$t$は訂正可能なエラーの数になる」と書きました。未知数は$n$個あるものの、本当に求める必要のある未知数は最大でも$t$個で、それ以外は$0$です(それ以上のエラーがあるときは訂正不可能なので諦める)。そのためにはまず、エラーがいくつあるのか、エラーがどこにあるのかを特定しなければなりません。それができれば、あとは普通に解けるはずです。p_{j-1}$番目にエラーがあるとします。\boldsymbol{H}$を展開すると次のようになります。\right.\end{eqnarray}結論から書くと、$j=t$から1つずつ$j$の値を小さくしていき、次の行列式が最初に0以外の値になったときの$j$の値がエラーの数になります。\\\end{vmatrix}なぜそうなるのか。この行列式を次のように変形します。やってこの等式を導き出したのかもはやわかりませんが、計算してみるとたしかに合っています。\alpha^{p_{j-1}(j-1)}\\\end{vmatrix}右辺の両端の行列式は$0$になることはありません。この行列式が$0$になるということは、右辺真ん中の行列式が$0$になるということです。右辺真ん中の行列式を計算してみると次のようになります。e_{p_{j-1}}$の中に$0$が混ざることになり、結果として行列式が$0$になります。そのため、$j=t$から1つずつ$j$の値を小さくしていき、行列式が$0$以外になったときの$j$の値がエラーの数になります。エラーの位置を特定するここでは次の式を考えます。\alpha^{-1},\alpha^{-2},\cdots,\alpha^{-(n-1)}$を順次入力していき、$0$になるものがあればそれがエラー位置だ!という寸法です。w_1$の求め方ですが、ここでは結論だけ...。頑張って展開すると成り立つはずです。ちなみに、左辺の右側の行列は、エラーの数を求めるときに出てきた行列式と中身が同じですね。s_{2j-1}\end{pmatrix}エラーの内容を特定するここまでで、求めるエラーの数と位置、つまり、$\boldsymbol{e}$の中のどの要素を未知数とすればよいのかが分かりました。\boldsymbol{H}$から求められるようになりました。具体的には、以下の式を解くことになります。\boldsymbol{O}の$\boldsymbol{G}$を求めることです。\boldsymbol{x^{\mathrm{T}}})$なので、$\boldsymbol{x}$には$\boldsymbol{m}$が含まれていなければならないという条件付きです。誤り訂正ができても、元のデータが分からなければ意味がないですからね。今回は$\boldsymbol{G}$を求めるのではなく、$\boldsymbol{m}$から$\boldsymbol{x}$を求めることを考えてみます。(理論的には$\boldsymbol{G}$は存在するはずですが...。)リード・ソロモン符号となる条件まずは、$\boldsymbol{x}$がリード・ソロモン符号となる条件を考えてみましょう。\boldsymbol{O}を盛大に展開すると、次の式になります。この方程式をすべて満たす$\boldsymbol{x}$がリード・ソロモン符号というわけです。\right.\end{eqnarray}これらの方程式を共通化すると、以下のようになります(エラー位置特定で出てきた$f(z)$とは無関係です)。0混乱してしまいそうになりますが、ここでは$\boldsymbol{x}$は決まった値なので、$f(z)$は$z$を変数に持つ単純なn-1次の多項式です。\alpha^{2t-1}$をそれぞれ入れていくと、元の式になりますね。0$の解なので、以下のように変形できるはずです。(z-\alpha^{2t-2})(z-\alpha^{2t-1})$を括りだした残りを適当に置いているだけなので気にしなくていいです。(z-\alpha^{2t-2})(z-\alpha^{2t-1})$で割り切れるという点です。これを満たしていれば、$\boldsymbol{x}$はリード・ソロモン符号です。条件が分かったところで、その条件を満たすように$\boldsymbol{m}$からリード・ソロモン符号$\boldsymbol{x}$を作ってみましょう。$\boldsymbol{m}$から以下の関数を作ります。$k$は$\boldsymbol{m}$の長さ(バイト数)です。z^{k-1}m_{k-1}これをいろいろ変形して先ほどの$f(z)$の形に持っていく方針で行きます。$f(z)$はn-1次関数だったので、まず次数を揃えるために両辺に$z^{n-k}$を掛けます。(z-\alpha^{2t-2})(z-\alpha^{2t-1})$で割ってみます。R(z)$はリード・ソロモン符号の条件を満たしています。R(z)$の内容を詳しく見て見るために、$R(z)$について考えてみましょう。(z-\alpha^{2t-2})(z-\alpha^{2t-1})$の次数は$2t$なので、$R(z)$の次数はは$2t-1$以下です。そのため、以下のように書けます。R(z)$は以下のようになります。m_{k-2},m_{k-1})ということです。(z-\alpha^{2t-2})(z-\alpha^{2t-1})$で割ったときの各項の係数」が誤り訂正符号です!!ガロア体さて、誤り訂正符号の求め方を解説してきましたが、このまま実装するのは大変です。(z-\alpha^{2t-2})(z-\alpha^{2t-1})$なんてまともに展開したいですか?そこで、実際は「ガロア体」というものを利用して比較的簡単に実装できるようにしています。ガロア体は、ざっくりいうと四則演算ができる有限集合です。ここでいう四則演算のルールは普通のやつでなくても、独自に定義したもので大丈夫です。ガロア体であるための条件はいろいろありますが、割愛しちゃいます。1}$は2進数的な演算を考えるとガロア体になります($GF(2)$という名前が付いています)。1$といった具合です。このガロア体、何が便利かって、有限集合なので計算するときに有限個の値しか出てこないんです。同じ結果が得られるなら、無限個の値が出てくる実数の世界で計算するより、有限個の値しか扱わないでいいガロア体の世界で計算したほうが簡単だよね、ということです。ちなみに、リード・ソロモン符号で使われるガロア体には、256個の値しか出てきません。1バイトのすべての値を表すのにぴったりな数ですね。ガロア拡大体そのガロア体はガロア拡大体$GF(2^8)$と呼ばれるのですが、なんと多項式の集合になります。具体的には、係数が$GF(2)$で、(最高)次数が7の多項式の集合です。以下のように1バイトの範囲で取りうる値が一対一で$GF(2^8)$の各要素に紐付けられます。\\ところで、ガロア体は四則演算可能なのでした。足し算は問題ありません。係数が$GF(2)$なので、各項の係数同士を足しても$GF(2)$に収まります。0しかし、掛け算をしようとするとこのままでは問題が...。7次の多項式同士を掛け算すると14次の項が出てくる可能性がありますよね。そこで、$\alpha$を次のように定義します。\alpha^8+\alpha^4+\alpha^3+\alpha^2+1=0そうすると$\alpha^8=\alpha^4+\alpha^3+\alpha^2+1$となるので、8次以上の項はこれを使って7次以下に落とすことができます。雰囲気的な説明になってしまいましたが、ちゃんと四則演算可能な気がしますよね(実際可能なんですが)。αを10進数の世界と紐付ける唐突ですが、$\alpha^0$から$\alpha^{255}$までを$\alpha^8=\alpha^4+\alpha^3+\alpha^2+1$を使って7次以下に落とし、対応するビット列、さらにその10進数表現を見ていきましょう。1途中省略していますが、$\alpha^0$から$\alpha^{254}$までに出てくるビット列はすべてユニークです。1$ということは、ここから先はループするということを表しています。ガロア体をリード・ソロモン符号の計算に使う今まで出てきた数式の中で、いたるところに$\alpha$が出てきました。これを$GF(2^8)$の$\alpha$として考えていきます。(z-\alpha^{2t-2})(z-\alpha^{2t-1})$なんかもまともに展開すると各項の係数がスゴいことになりますが、$GF(2^8)$で計算すると、例えば$t=5$のときは次のようにスッキリします。m_{k-2},m_{k-1})$も、それぞれ$\alpha^0$から$\alpha^{254}$を使って表せます。最後に、先ほど出した表から対応する10進数表現を参照すれば、QRコードに格納する実際の値が得られます!データの格納ようやくQRコードに格納すべきデータが求められるようになりました。あとはデータを格納するだけです。格納データに対して一気に誤り訂正符号をくっつけようとすると計算が大変なことになるので、分割して計算していきます。例としてバージョン3、誤り訂正レベルH(30%)の場合を見てみましょう。今回の例の場合は、格納できるデータ量は26バイト、分割数が2です。分割した各13バイトにそれぞれ22バイトの誤り訂正符号が付きます。分割したデータとそれに対する誤り訂正符号を合わせてRSブロックと呼びます。格納できるデータ量は誤り訂正符号含めては70バイト、そのうち純粋なデータは26バイトです。これを2つに分割して13バイトずつとし、それぞれ誤り訂正符号を計算します。RSブロックのデータ、誤り訂正ブロックの各バイトに以下のように名前を付けます。E44これを配置していくのですが、単純に並べるわけではないんです。RSブロック1の1番目のデータバイト、RSブロック2の1番目のデータバイト、...、RSブロックnの1番目のデータバイト、RSブロック1の2番目のデータバイト、RSブロック2の2番目のデータバイト、...、RSブロックnの2番目のデータバイト、...RSブロック1の1番目の誤り訂正バイト、RSブロック2の1番目の誤り訂正バイト、...、RSブロックnの1番目の誤り訂正バイト、RSブロック1の2番目の誤り訂正バイト、RSブロック2の2番目の誤り訂正バイト、...、RSブロックnの2番目の誤り訂正バイト、...という順番で格納していきます。推測ですが、こうやって各RSブロックを分散して配置することで読み取り不可になる可能性を下げようとしているのではないかと思います。単純に並べてしまうとRSブロックのバイト同士が近くなるので、例えばインクがポタっと落ちたりしたら一発で読み取り不可になったり。今回の例の具体的な格納場所は英語版のWikipediaにあります。単純にデータを格納しただけでは、位置検出パターンに似た模様が出現したり、白黒のバランスが悪くなったりして読み取り性能に悪影響を及ぼす可能性があります。そのような事態を防ぐため、適当なパターンでマスクします。マスクパターンは以下の8種類が用意されています。0実際にどんなパターンになるかも、英語版のWikipediaにありました。(式が若干違いますが、結果は同じです。)どのマスクパターンを選択するかは、実際にそれぞれ適用してみて望ましくないパターンに失点を与えることで評価します。誤り訂正レベルとマスクパターン参照子からなります。誤り訂正レベルは訂正できるエラーの数を決めます。レベルは4つ用意されています。30%マスクパターン参照子は先に示したとおりです。この2つをつなげて5ビットにして、BCH符号という別の誤り訂正符号を求めて15ビットにします。バージョン7以上のQRコードに入ります。それぞれQRコードの以下の位置に2箇所に冗長化して配置されます。以上で解説はすべて終了ですが、QRコードの秘密を知った皆様は、新たな遊びを得ることができました。適当なQRコードを用意します。適当にセルを塗りつぶします(どれだけ塗りつぶしてもOK)。QRコードリーダーで読み取ります。読み取れればターン交代。読み取れなければ負け。どのような仕組みで誤り訂正が行われているかを知っていると、より楽しめると思いますまとめところどころ説明を省略したにも関わらずかなり長くなってしまいましたが、いかがだったでしょうか?普段何気なく使っているQRコードですが、裏では結構大変な処理をしていました。今後QRコードを目にしたときに、これらの処理に思いを馳せてもらえたら幸いです。requestStockLike49@Kta-MFollow株式会社Fusic受託開発・自社サービスの2本柱で「日本を代表する福岡の企業」を目指している企業です。upLoginユーザーは見つかりませんでした。