こんにちは．15 入学の kokoroyoku (@kokoroyoku) です．
私が昔作った百人一首ARに関して記事を書こうと思ったので，ご覧の記事を書きました．お付き合いください．
AR とは？
AR (Augmented Reality, 拡張現実) とは，最近 VR (Virtual Reality, 仮想現実) に押されている技術のことです．
VR が完全にゼロから世界を作っているのに対して， AR は，カメラで撮影された「現実」を拡張することに徹します．ポケモン GO は代表的な AR の例です．
百人一首 AR とは？
まずはこちらをどうぞ．
カメラに映った百人一首の取り札に対して，歌人や決まり字などの情報を重ね合わせています．
こちらを工大祭2017に展示したり，Maker Faire Tokyo 2017 に展示したりしていたところ，ニュースメディアに紹介していだだけました．
（このタイトル，誤字っている気がする・・・）
どうやって作った？
ここから本題で，技術的な話をします．
分野としては画像処理と呼ばれる領域です．言語は C++ を用いていて，ライブラリとして OpenCV を使用しています．
流れとしては，
- 百人一首の札がどこにあるか認識する
- それが何なのか認識する
- AR の表示を重ね合わせる
という感じです．
札の特徴
今回認識したい，百人一首の取り札はこのような形をしています．見た感じの印象としては，以下のようなものがあるかもしれません．
- 四角い
- 縁取り緑，背景白，文字黒のハイコントラスト
- ひらがな（濁点・半濁点なし）が規則正しく並んでいる
このような特徴を最大限活用して認識していきます．
1. 札の検出
まずは札がどこにあるか検出しなければ始まりません．検出しましょう．
このような四角い物体を検出するアルゴリズムに関する紹介はすでに数多くあるのでそちらに譲ります．「矩形検出」等で検索すれば出てきます．
認識結果はこのようになります．赤く縁取ったのが認識結果です．
2. 札情報の識別
札がどこにあるかわかったので，これを識別します．
まず，透視変換と呼ばれる変換を加えることで，札に書かれた文字領域を切り出します．
これにより，識別のしやすい形となりました．（この時点では札がどっちの向きを向いているかわかりません．この問題は，４方向全てに認識を試行することで解決します．）
これを二値化することにより，さらに認識しやすくします．何となく白黒反転をしています．
最初はこれをそのまま最近傍法に突っ込んでいました（後述）が，あまり結果が芳しくなかったので，文字ごとの認識に切り替えました．
つまり，ひらがなが規則正しく並んでいるという性質を利用し，次のように切り出します．
この切り出されたひらがなに対して，最近傍法により認識を行います．アルゴリズムは簡単です．
- 全てのひらがなのデータをあらかじめ用意しておく．
- 認識したいひらがなに対して，全てのひらがなとの「距離」を計算する．
- 一番「近い」ひらがなを認識結果とする．
というものです．（最近傍法やk-NNでは特徴空間での距離を用いる，という記述がよくあるのですが，ここでの距離は距離の公理を満たす必要があるんでしょうか．精度保証に必要とか？詳しい人教えてください．）
今回用いた「距離」は，次の２つのビット演算を組み合わせたものです．（距離の公理を満たしていないです）
XOR
まずは XOR です．「画像を重ね合わせて，はみ出た部分を白にする」が直感的な理解です．
XOR の例です．はみ出ている部分が少ない方が，画像として「近い」ということが理解いただけるかと思います．
AND
次には AND です．「画像を重ね合わせて，重なった部分を白にする」が直感的な理解です．
AND の例です．重なった部分が多い方が，画像として「近い」ということが理解いただけるかと思います．
この二つを用いて，(XOR した白い部分) – (AND した白い部分) により「距離」を導出します．
このようなひらがな認識を全ての文字に対して行うことにより，ひらがなの列が得られます．
歌とのマッチング
認識結果は多分にエラーを含みます．今回の方法では，認識率は結構低く，80 – 90 %くらいです．
しかし，百人一首の歌はたった 100 しかないので，実在する歌とのマッチングを行うことで解決します．ここでも最近傍法を用いています．
まず，歌と歌との距離をハミング距離により定義します．対応する場所の文字が異なれば１を加え，同じならそのままという素朴な定義です．Wikipedia を見てください．
そして，全ての歌との距離を計算し，一番小さいものを認識結果とします．
以上のような，２段階の最近傍法（一つはひらがなに対して，もう一つは歌に対して）を用いることによって認識を行なっています．
AR に関しては今後何かの機会があれば書こうと思います．ありがとうございました．