【Python + OpenCV】🍔エブリバーガーまちがいさがし攻略🍔 ~ テンプレートマッチングで攻略 ~ 

[[Python + OpenCV] 🍔エブリバーガーまちがいさがし攻略🍔](https://qiita.com/ari3/items/8fdca5f2a7c857f8f7ba) の続きです。
前回結果を踏まえたうえで、おそらく一番シンプルなやり方で改善を図りたいと思います。

# 前回まで
難易度: 「むずかしい🍔🍔🍔」
まちがい: 4つ
![img.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/8121f681-826a-8a1e-42e2-8af630dc9455.png)
https://www.bourbon.co.jp/burger.kikori/burger/

導き出した答え（たぶん合ってる）
![answer.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/f59f6df1-cf3a-f5dc-76c4-f57d38657e71.png)

しかし、当該の問題画像にのみ特化している部分が大きく、「やさしい🍔」「ふつう🍔🍔」の問題に至っては途中でプログラムがオチてしまうなど、実はたまたまきれいに答えが出ていたにすぎなかったのではという問題が残った。

# 今回の方針
目標はいずれの問題に対しても一定の結果を得ることができるように汎用的なプログラムにすることとします。

最終的に「左の絵」と「右の絵」の差分を取得するという方針は継続します。
今回改善するのは、比較対象となる **左右それぞれの絵を切り出す** という部分になります。

## 前回手法の問題点
前回は1枚の問題画像を対象とした輪郭抽出からそれぞれの絵を囲む枠により囲まれる領域を求めて左右それぞれの絵を切り出していました。この手法だと問題画像によっては下記のような結果が得られることとなり不安定な手法であることがわかりました。

☟「やさしい🍔」の例。画像全体を囲む大枠はともかくとして左右それぞれの絵が二つの領域で分割されてしまっている。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/0d72dcb8-0f4e-57c9-e2c4-d7a488ec5893.png)

☟「ふつう🍔🍔」の例。一見すると正しそうだが、それぞれ切り出された領域のサイズが **(376, 307)**, **(377, 307)** のように一致していませんでした。 これにより比較対象となる2つの絵のサイズは等しくなるはずという前提があった前回のプログラムではうまく動かなかったようです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/fa3147ef-10d1-9218-0ba8-20750e94eaf1.png)

## 今回の提案手法
まず、今回の手法においては、比較対象とする左右それぞれの絵の切り出しについて下記を保証することとします。

+ 左右それぞれの絵の領域内で別の領域に分割されたりしない
+ 左右それぞれの絵の領域の大きさは一致させる

これに関しては、問題画像を縦半分に分割して左右の絵の領域として切り出すということで解決します。
そうすると問題となるのが、左の絵と右の絵の間の余白部分（分割時にそれぞれ等分される）によって、そのまま左右の絵の差分を取ると下図のように全体的に差分が大きくなってしまうということです。
☟中央の余白の（半）分だけ右の絵が右側にずれてしまうため下図のように差分が取れてしまうの図。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/98a8c945-1476-2271-09c0-74ed129ad8bd.png)

そこで今回は、このずれの量を **テンプレートマッチング** によって計測しずれを補正したのちに2枚の絵の差分からまちがいを検出します。

1. 左の絵を基準とし、左の絵の一部分をテンプレートとして切り出しマッチングに使用する
1. 右の絵とテンプレートとでテンプレートマッチングを行いマッチングした座標からずれの量を算出する
1. 右の絵に対してずれを打ち消すような補正をかけたのち左の絵との差分をとる

という手順で最終的にまちがいを検出します。
ソースコードは最後に貼ります。

# 結果
## むずかしい🍔🍔🍔
☟左右の絵の切り出し（左の絵、右の絵）
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/923c2fd5-8f2c-150e-b3ad-f16f25affc89.png)


☟テンプレート画像、テンプレートについてですが左の絵の中央から適当な大きさの領域を切り出しました。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/470b6c19-74e2-d6e4-2d46-5baeae9d64ef.png)

☟テンプレートマッチング
**(88, 125)**： 右の絵の中からテンプレートにマッチングした領域の基準点(left, top)
**(82, 125)**： テンプレート画像の左の絵の中での上記点との対応点(left, top)
ですので、ずれ (x,y) は (6, 0) と算出できます。横軸方向にのみ 6 平行移動していることになります。

☟ずれを補正した後の右の絵、ずれを打ち消す量 (-6, -0) だけ平行移動します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/140a52ac-2cc6-77bc-9a5f-37b38aaf7f8b.png)

☟(左の絵とずれを補正した後の右の絵の)差分画像、上部のキャプション部分及びずれを補正した分だけ補間された右端部分が差分として検出されてしまっています。こちらは差分をとる前後において除去が可能な領域になりますが今回は省略しています。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/fd918911-5bff-19c3-d792-aa3c6c16178d.png)

前回の記事同様今回の手法についても「むずかしい🍔🍔🍔」を攻略することができました。

## やさしい🍔 （問題画像と差分画像のみ）
☟問題画像
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/8d3108c2-aa3f-3cf3-955a-4be503ae077f.png)

☟差分画像
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/fe3ab9bb-adc1-2306-2adc-88c4a2f24b3d.png)

若干まだ全体的にずれていますね。しかしそのずれに対してまちがい部分の差分の方が大きく出ているので、ここからまちがい部分の判定をすることは可能なような気がします。

## ふつう🍔🍔（問題画像と差分画像のみ）
☟問題画像
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/15794cd2-c337-ac7b-a552-22ae9ddc1045.png)

☟差分画像
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/174132/5dfba67c-1bbd-4536-f4fb-c1a69b287df7.png)

やさしい🍔と同じような感じですね。

# まとめ
エブリバーガーまちがい探し攻略においてテンプレートマッチングによるずれの補正はある程度効果的であることがわかりました。
行き当たりばったりな前回とは違いある程度方針を定めたうえで攻略を進めることでより汎用的なプログラムとなったと思います。
次回は特徴点マッチングなどを使用してずれ補正の精度向上を試みるかあるいは差分画像に対してのまちがい部分の評価手法を考えるかという感じにしようと思っています。

# 参考
+ [【Python/OpenCV】テンプレートマッチング（SAD）の実装例](https://algorithm.joho.info/programming/python/opencv-template-matching-sad-py/)
+ [OpenCVによる画像処理〜アフィン変換とか〜](https://sites.google.com/site/lifeslash7830/home/hua-xiang-chu-li/opencvniyoruhuaxiangchuliafinbianhuantoka)
+ [サイゼリヤの間違い探しが難しすぎたので大人の力で解決した](http://kawalabo.blogspot.com/2014/11/blog-post.html)
+ [エブリバーガー](https://www.bourbon.co.jp/burger.kikori/burger/)

# ソースコード

```python
import cv2
import numpy as np
import math

img = cv2.imread("images/img.png")
img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
height, width = img_gray.shape
# print(height, width) # 415 656

# 左右の絵の切り出し
img_left = img_gray[0:height,0:width//2]
img_right = img_gray[0:height,math.ceil(width/2):math.ceil(width/2)+width//2]
cv2.imshow("left", img_left)
cv2.imshow("right", img_right)

height, width = img_left.shape
# print(height, width) # 415, 328

# テンプレートの切り出し
template_height = width//2
template_width = width//2
template_top = (height-width//2)//2
template_left = width//4
template = img_left[
    template_top:template_top+template_height,
    template_left:template_left+template_width
    ]
cv2.imshow("template", template)

# テンプレートマッチング
match = cv2.matchTemplate(img_right, template, cv2.TM_SQDIFF_NORMED)
min_value, max_value, min_pt, max_pt = cv2.minMaxLoc(match)
pt = min_pt
# print((template_left, template_top)) # (82, 125)
# print(pt) # (88, 125)

# ずれの算出と補正
moving_x = pt[0] - template_left
moving_y = pt[1] - template_top
# print(moving_x, moving_y) # 6 0
M = np.float32([[1, 0, -moving_x], [0, 1, -moving_y]]) # ずれ(移動量)を打ち消す
shifted_img = cv2.warpAffine(img_right, M, (width, height))
cv2.imshow("shifted_img", shifted_img)

# 差分
img_diff = cv2.absdiff(img_left, shifted_img)
cv2.imshow("diff", img_diff)

cv2.waitKey(0)
cv2.destroyAllWindows()

```