QRコード(はデンソーウェーブの登録商標です。ISO/IEC 18004の二次元コー ド)の検出(デコードはしません)

一枚の画像ファイルの中からいわゆるQRコードを切り出したい(座標を抽出した い)…と思ったのですが、探しても意外とオープンソースなツールがなかった ので自作してみました。

基本戦略

QRコードには位置決めパタン（3隅にある四角いあれ）があります。これを 見つけるのが正攻法、ということでそうします。以下がアルゴリズムです。 要するにアスペクト比が1に近い中心が黒 (ここでは説明のため白地に黒のコードがあると仮定しています。) の環状の領域を探すだけ、です。 まず擬似コードで書くとこんな感じです。 

 1 makeImageBW()
 2 foreach p in all_pixel{
 3   [cog, aspectRatio] = paintWhiteAndCalcCoGAndAspectRatio(p)
 4   if(isBlack(cog) and isAlmostOne(aspectRatio)){
 5     addCandidate(cog)
 6   }
 7 }

続いて日本語で説明します。

  1. 白黒に2値化します(1行目)。
  2. 端の方から順番(2行目)に白で『ペイント』します。この『ペイント』ってのは 8bit機時代のBASICのPAINT文みたいに、任意形状で囲まれた領域を 塗りつぶすあれです。また、ペイントしながら同時にペイントした 領域の重心およびアスペクト比(単にx, yそれぞれの最大値と最小値の差の比で ok)を求めておきます(3行目)。
    なお、『端の方から順番に』と書きましたが、ふつうに左上からラスター スキャン順で大丈夫です(いきなり位置決めパタンの中心部から塗り始め てはダメです)。
  3. 重心のピクセル値が黒、かつアスペクト比が1に近ければ、十中八九は そこが検出パタンです(4, 5行目)。

なぜこんな単純でいいのか、ということですが、どうも検出パタンのような 『中心に黒がある黒い環形領域』って、そうそうないからみたいです。 だからこんなんで けっこう精度良く検出できます。デンソーウェーブのQR作った人、偉いです。 もちろん意図的に 目玉みたいな模様を書いたらバッチリ誤検出しますが、そしたら3つのパタンの 位置関係あたりから何とかしてみてください。

コード例

準備中

Valid XHTML 1.0!