(1) 準備編
(2) 勉強編
(3) 盤面の正規化
 (4) 駒の認識

画像を盤面情報（駒の配置、持ち駒）に変換するためには、次のような処理が必要となる。

画像内でのボードの座標取得
画像内での各駒の座標取得
上記内容をもとに盤面情報を計算・生成

1, 2 はあらかじめボード・駒の画像を用意しておき、それを元に入力画像内での位置を検出する、マッチングという手法が使える。

Template Matching と Feature Detection and Description (特徴抽出と特徴記述) の内容を勉強する。

Template Matching

テンプレート画像と入力画像を与えて、入力画像の中でテンプレート画像が出現する箇所の座標を抽出する。

複数のアルゴリズムを選択できる。

しきい値で区切ることで、複数の出現を検出することができる。

Feature Detection and Description

大事そうな章だけ抜粋

Understanding Features

画像の「特徴」とは何か
- 面より辺、辺より角の方が、特定しやすい→特徴的
特徴とは、変化量が大きい領域
特徴を探すことを特徴抽出と呼ぶ

Harris Corner Detection

明度の変化量から、角を抽出するアルゴリズム

Introduction to SIFT (Scale-Invariant Feature Transform)

角は、拡大すると角じゃなくなるかもしれない（実は丸いかもしれない）
- つまり Harris Corner Detection はスケール不変ではない
- スケール不変な特徴が欲しい
SIFT はスケール不変な特徴を与える
4 つのステップからなる

1. Scale-space Extrema Detection

特徴点候補を見つける。

窓関数のサイズ (scale) と位置 (space) の 2 パラメータについて、近傍の変化量が極大となるような値を列挙する。

scale はガウシアンの分散 (幅)
scale 毎に, space 毎のラプラシアン (実際は Difference of Gaussian, DoG) を取る
- ラプラシアンは明暗の差が大きい部分で値が 0 から離れる
space と scale について極値を探す

2. Keypoint Localization

特徴点候補のうち無意味なものを除外する。

極値を与えるより詳細な scale / space を求め, 極値がしきい値以下であれば除外する
DoG が辺を強く抽出してしまうので, 除外する

3. Orientation Assignment

回転に対して不変性を得るために, 特徴点に方向を与える。

36 方向の勾配強度を求める
最大値の 80 % 以上のものを抽出して、別個の特徴点として保持する
- マッチングの安定性に寄与する

4. Keypoint Descriptor

特徴点周辺の情報を集めて、特徴点記述子を作る。

特徴点の周りの 16 * 16 の領域から、8 方向の勾配強度を取る
4 * 4 のサブブロックに分けて、8 方向の勾配強度の和を取る
合計 4 * 4 * 8 = 128 の値を特徴点記述子とする

資料だと説明が簡素で意味不明だが、論文の Figure 7 の説明が分かりやすい。

5. Keypoint Matching

2 つの画像の特徴点同士をマッチングする。

BRIEF (Binary Robust Independent Elementary Features)

SIFT の特徴点記述子はマッチングにおいて冗長である。

マッチングにおいては、速度面の理由から特徴点記述子が binary string に変換される。

BRIEF は同様に binary string に高速で変換可能な、圧縮された特徴点記述子である。

OpenCV では特徴点抽出器 (FeatureDetector)、特徴点記述子生成器 (DescriptorExtractor) がそれぞれインタフェースとして定義されている。

# Initiate STAR detector
star = cv2.FeatureDetector_create("STAR")

# Initiate BRIEF extractor
brief = cv2.DescriptorExtractor_create("BRIEF")

# find the keypoints with STAR
kp = star.detect(img,None)

# compute the descriptors with BRIEF
kp, des = brief.compute(img, kp)

Feature Matching

画像 A の特徴点を、画像 B の特徴点にマッチングする。

Brute-Force Matcher

ブルートフォース。

crossCheck を on にすると、画像 A の特徴 i にとって画像 B の特徴 j が最もマッチしているだけでなく、逆も成り立っている場合のみマッチしたとみなす。

FLANN Based Matcher

速い。

Feature Matching + Homography to find Objects

findHomography: マッチの集合から、ホモグラフィ行列とインライアー(正しいマッチ)/アウトライアーのマスクを求める
- RANSAC: インライアーとアウトライアーのしきい値を指定する
perspectiveTransform: 点をホモグラフィ行列をもとに投影変換する

まとめ

付け焼き刃なので間違いが多いと思います

マッチングには、テンプレートマッチングと特徴マッチングがある。

テンプレートマッチングはシンプルだが、テンプレートのサイズと角度が対象画像内のオブジェクトのそれと一致している必要がある。

特徴マッチングでは、スケール不変・回転不変な特徴を用いることで、拡大率が異なったり傾いた画像に対してもマッチングすることができる。ただし、対象画像内に対象オブジェクトが複数ある場合はそのままではマッチングできない。

今回の場合、盤面座標を求めるのには特徴マッチングが使える。求めた盤面座標を元に画像を正規化 (角度・拡大率をノーマライズ) することで、テンプレートマッチングを使って駒座標を求めることができる。

na_o_ysのブログ

プログラミングなど

どうぶつしょうぎの盤面認識アプリを作る (2) 勉強編