けむしろうの部屋別館

最近はあちこちで見かけるQRコード(*)ですが、この楽天広場でもQRコードの画像を表示できるようになりましたね。

QRコードはデンソーウェーブという会社が特許を持つ情報符号化技術で、現在はISOやJISで規格化されています。
JIS規格は以下のURLで見ることができます。
→ JISX0501 共通商品コード用バーコードシンボル (日本工業標準調査会)

QRコードの使用に関してはデンソーウェーブとのライセンス契約等は必要でなく、無償で使うことができます。
ただし「QRコード」はデンソーウェーブの登録商標であって、この用語を出版物やホームページなどで使用する場合は登録商標文を記載することが求められています。

さてこのQRコードは機械で読み取ることを想定していますが、読み取った画像の向きや大きさがずれていたとしても正しく元の情報を復元できることが大きな特徴です。
その特徴は、QRコードの3隅にある「目玉」のような模様が大きな役割を果たしています。

読み取ったQRコードの数学的な処理について考えてみました。



(1) 標準状態の定義
まずQRコードの標準状態を定義します。
上の図の(a)のように、3つの目玉の中心を結んで作られる三角形の直角部分にある目玉(直角目玉と呼びましょう)を原点とし、x軸とy軸の座標1の位置にもう2つの目玉があるとき、このQRコードは標準状態にあるとしましょう。

標準状態であれば、画像を横方向と縦方向にスキャンすることで容易に0(白い部分)と1(黒い部分)の情報を得ることができることは、画像処理の知識が少しでもあれば容易に分かると思います。

(2) 直角目玉の判定方法
さて読み取った画像はつねに標準状態にあるとは限らず、回転していたり原点からずれていたり拡大・縮小された状態になっていたりします。
ここで3つの目玉の位置関係によって3通りに場合分け出来ます。
位置的に上にある目玉から順にA、B、Cとします。
目玉が同じ高さにある場合は左にあるものを優先します。

すると線分ABとACの長さによって

• (1,1)型 (上図(b))
  
• (1,ルート2)型 (上図(c))
  
• (ルート2,1)型 (上図(d))

と分類でき、逆にこれ以外の組合わせは存在しません。

このように場合分け出きれば、直角目玉がそれぞれの型でA、B、Cとなることが判明します。

さらに点Aが直角目玉になるようにA、B、Cの名前をつけ直して、3つの型すべてが(1, 1)型を単に回転させただけのものとして扱えるようにしておきます。

(3) 目玉の判別
QRコードの最大の技術的な肝(まさに目玉技術)は、目玉画像の構造にあります。

目玉は黒い正方形の外枠の内側に黒い正方形が囲まれている構造になっていますが、(外枠の太さ, 白い隙間部分の太さ, 黒正方形の１辺の長さ)が(1, 1, 3)となるように定義しています。

目玉が斜めになっている場合(上図の(e)の場合)を考えます。目玉をx軸方向の直線が横切る場合、交互に現れる黒い部分と白い部分の長さの比率を求めると、直線L1とL2の間にある直線が目玉を横切る場合は常に(1, 1, 3, 1, 1)となります。

逆に言えば、読み取った画像を上から下に向かって横方向にスキャンしながら黒と白の長さの比が(1, 1, 3, 1, 1)となる場所を見つけることができれば、そこが目玉となります。
(厳密には目玉パターンが目玉以外の部分で現れないように情報を符号化しなければならない)

そして直線L1とL2のちょうど真ん中となる直線L3上にある(1, 1, 3, 1, 1)の3の部分の中心が、目玉の中心となります。
これにより、3つの目玉位置の正確な座標が求められます。

(4) 標準形への変換
ここまでくれば次の3つの変形の組合わせを計算する一次変換を求めることは容易ですので、その一次変換を行う行列と読み取った2次元画像の積を計算することで標準系への変換が可能になります。

• 直角目玉の原点への平行移動 (上図(f))
  
• 点B、Cを軸上にもっていくための回転 (上図(g))
  
• 点B、Cの座標を1とするような拡大(縮小) (上図(h))

* * *

QRコードの「目玉」の意義が分かったとき私は感動しました。
これを発明した人はすごい。

私もこんな発明をしてみたいものです。

---

(*) QRコードは(株)デンソーウェーブの登録商標です。