デッキ画像から駒名称を抜き出す【テンプレートマッチング編】

# はじめに
こんにちは。逆転オセロニアのYouTubeチャンネル「まこちゃんねる」の中の人です。
本稿では、**デッキ画像から駒名称を抜き出すこと**を目標にします。
抜き出す方法はいくつか存在すると思いますが、今回は**テンプレートマッチング**を使った方法を利用してみます。
<img width="780" alt="ファイル名" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2483501/7e79ed62-3d0e-728f-44b9-62b465c86b59.png">

# モチベーション
リスナーさん**「デッキに入ってる駒名称が分からない！教えて！」**
まこちゃん（うーん...毎回手動で書くの面倒くさいな...ある程度自動化したさ）

# テンプレートマッチングとは？
**入力画像（今回であればデッキ画像）からテンプレート画像に類似する箇所を探索する手法**です。類似度と座標を取得することができます。ただし、回転や拡縮に弱く処理も遅いのが欠点です。
<img width="780" alt="ファイル名" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2483501/7c8c1dd3-3137-220a-0fec-93d8ce0feea9.png">

# 環境
- macOS
- JupyterLab
- Python3.6
- OpenCV

# 実装の流れ
1. **テンプレート画像作成処理の実装**
    1. 入力画像から駒画像を16分割してテンプレート画像を作成する
    1. 16分割したテンプレート画像の手動アノテーションをする
1. **テンプレートマッチング処理より駒名称を取得する実装**
    1. テンプレートマッチング処理を行う
    1. 入力画像の駒画像を16分割して中心点を取得する
    1. テンプレート画像と一致した箇所に矩形描画する
    1. 駒名称を出力する

## テンプレート画像作成処理の実装
前述した通り、駒名称を抜き出すには**駒のテンプレート画像**が必要です。
オセロニアの公式攻略サイトには全駒の顔画像と名前がセットで公開されているので、これを利用できれば手間が省けるのですが、テンプレートマッチングは拡縮に弱いです。今回は入力画像がスマホのスクショなので、当然サイズも違ってきてマッチングできません。環境で使われている駒種には限りがあるので、今回は入力画像であるデッキ画像から駒のテンプレート画像を作成することにしました。

### 入力画像から駒画像を16分割してテンプレート画像を作成する
deck.png（デッキのスクショ画像）は**撮影する端末とゲーム内のデッキ描画の仕様が変わらなければ、毎回同じ座標から駒画像を抜き出すことができるはず**です。抜き出した各画像に連番を振り保存します。
<img width="780" alt="ファイル名" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2483501/21b4f820-6466-9107-b1fa-c8dbd689e7ff.png">

```python
import cv2
import matplotlib.pyplot as plt
%matplotlib inline

# デッキ画像の読み込み
img = cv2.imread("deck.png")
plt.imshow(cv2.cvtColor(img, cv2.COLOR_BGR2RGB))

# デッキ画像からテンプレート画像となる領域リストを取得する関数
def crop_roi_list(img, x_start=80, y_start=750, w=240, h=220):
    roi_list = []
    for column in range(4):
        for row in range(4):
            x1 = x_start + w * row
            x2 = x1 + w
            y1 = y_start + h * column
            y2 = y1 + h
            roi_list.append(img[y1 : y2, x1 : x2])
    return roi_list

# テンプレート画像の作成
roi_list = crop_roi_list(img)
for idx, roi in enumerate(roi_list, start=1):
    filename = f"{idx:0=2}.png"
    cv2.imwrite(f"template/{filename}", roi)
```

### 16分割したテンプレート画像の手動アノテーションをする
出力された16枚の画像を**気合い**で駒名にリネームする。
<img width="780" alt="ファイル名" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2483501/9f65f138-4920-9079-7182-dd8570a3173a.png">

## テンプレートマッチング処理より駒名称を取得する実装
テンプレート画像を網羅的にチェックすることで、入力画像に含まれる駒名称を全て抜き出します。今回は**類似度が0.7を超えた場合は、入力画像にテンプレート画像が含まれていると判断する**ことにします。また、入力画像を事前に16分割し各駒の中心点を取得しておきます。これは、**同じ中心点を含むテンプレート画像が複数枚マッチした時に、最も高い類似度の画像を採用するため**です。分かりやすいように、一致した箇所に矩形とその駒名称も描画します。

### テンプレートマッチング処理を行う
入力画像と作成したテンプレート画像を網羅的にテンプレートマッチング処理を行い、類似度が閾値を超える画像のみ取得する。
<img width="780" alt="ファイル名" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2483501/b8420115-a08e-f405-50ec-5876d8141e03.png">


```python
import cv2
import numpy as np
import glob
from PIL import ImageFont, ImageDraw, Image
from itertools import groupby

# 入力画像の読み込み
img = cv2.imread("input.png")
# グレースケール変換
img_gray = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)

# 駒名称と座標
piece_list = []

# テンプレート画像を網羅的に走査する
files = glob.glob("template/*.png")
for file in files:
    # テンプレート画像の読み込み
    template = cv2.imread(file)
    # グレースケール変換
    template_gray = cv2.cvtColor(template, cv2.COLOR_RGB2GRAY)
    # テンプレート画像の高さ・幅
    h, w = template_gray.shape
    # テンプレートマッチング
    match = cv2.matchTemplate(img_gray, template_gray, cv2.TM_CCOEFF_NORMED)
    min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(match)
    # 閾値を超えていたら出力する
    if max_val > 0.7:
        piece_name = file.split("/")[1].rstrip(".png")
        piece_list.append({
                "name": piece_name, 
                "max_val": max_val,
                "x1": max_loc[0], "x2": max_loc[0] + w, "y1": max_loc[1], "y2": max_loc[1] + h})
```

### 入力画像の駒画像を16分割して中心点を取得する
テンプレート画像作成時と同じ範囲で16分割し、中心点を取得しておく。中心点を含む複数枚の画像が閾値を超えた場合、**最も類似度が高い画像を採用するため**に利用する。
<img width="780" alt="ファイル名" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2483501/3931dd94-1a6d-3559-6d0c-57fbddd954f0.png">

```python
# 中点を取得する
x_start, y_start, w, h = 80, 750, 240, 220
piece_center_loc_list = []
for column in range(4):
    for row in range(4):
        x1 = x_start + w * row
        x2 = x1 + w
        y1 = y_start + h * column
        y2 = y1 + h
        cx = int((x1+x2)/2)
        cy = int((y1+y2)/2)
        piece_center_loc_list.append({"cx": cx, "cy": cy})

# 属する中心点を調べる
for piece in piece_list:
    for idx, piece_center_loc in enumerate(piece_center_loc_list):
        x1, x2, y1, y2 = piece["x1"], piece["x2"], piece["y1"], piece["y2"]
        cx, cy = piece_center_loc["cx"], piece_center_loc["cy"]
        if x1 < cx < x2 and y1 < cy < y2:
            piece["idx"] = idx
```

### テンプレート画像と一致した箇所に矩形描画する
テンプレート画像と一致した箇所に矩形を描画し、駒名称と類似度を表示しておくことで、出力された駒名称が正しいかどうかを**一目で把握できるよう**にしておく。
<img width="780" alt="ファイル名" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2483501/f8c0b3c0-65be-0f28-8e84-2ea8fd27efa0.png">

```python
# 駒名称リスト
piece_name_list = []
# フォントを読み込み
font = ImageFont.truetype("/System/Library/Fonts/ヒラギノ角ゴシック W9.ttc", 16)
# 矩形と駒名称を描画する
piece_list.sort(key=lambda item: item['idx'])
for key, piece_group in groupby(piece_list, key=lambda x: x['idx']):
    # 最も類似度が高い駒を採用する
    piece = sorted(piece_group, key=lambda x: x['max_val'], reverse=True)[0]
    x1, x2, y1, y2 = piece["x1"], piece["x2"], piece["y1"], piece["y2"]
    name = piece["name"]
    score = piece["max_val"]
    piece_name_list.append(name)
    # 矩形を描画する
    cv2.rectangle(img, (x1, y1), (x2, y2), (0, 0, 200), 2)
    # 類似度と駒名称を描画する
    img_pil = Image.fromarray(img)
    draw = ImageDraw.Draw(img_pil)
    draw.text((x1 + 4, y2 - 42), f"{round(score, 3)}", font = font, fill = (255,255,255), stroke_width=2, stroke_fill='black')
    draw.text((x1 + 4, y2 - 22), f"{name}", font = font, fill = (255,255,255), stroke_width=2, stroke_fill='black')
    img = np.array(img_pil)
        
cv2.imwrite("output.png", img) 
```

### 駒名称を出力する
最後は駒名称を出力して目的を達成する。出力されたテキストをコピペしてYouTubeのコメント欄にえいや！と貼り付けて終了！

```python
# 駒名称一覧を出力する
print("\n".join(piece_name_list))

[高みへ挑む者]イリオット
[吸殺の妖魔]ヴェルグレーデ
[ゆるダンス]ブランジェッタ
[駆ける山のニンフ]ハル
```

# おわりに
今回の実装は、私の端末、オセロニアのデッキ仕様が変わったら全てが終わります。
なので、次の目標としてはデッキ画像やテンプレート画像が変わっても対応できるような実装も考えていきたいですね。環境で使われている駒はそこまで多くないので、解像度はそのままで利用しましたが、速度が気になるようだったら加工も考えて行こうかなと思います。

# 参考

https://algorithm.joho.info/programming/python/opencv-template-matching-ssd-py/#toc1

https://symfoware.blog.fc2.com/blog-entry-2130.html