Python & OpenCvでゴールデンクッキーを乱獲しようPart1
以前、Cookie Clickerでクッキーをクリックし続けるために、マクロパッドを作成した。その甲斐があって実績が大量に増えたのだが、ここにきてクリックで生産できるクッキーでは足らなくなってしまった。1
Cookie Clickerにはランダムに画面上にゴールデンクッキーというクッキーが出現することがある。ゴールデンクッキーをクリックすると以下に示すような様々な恩恵を受けることができる。
- 一定時間クッキーの生産速度を7倍にする。
- クッキーを取得。
- 一定時間施設の生産速度が向上する。
- 一定時間クリックの生産量が向上する。
そこで、ゴールデンクッキーもクリックすることによりにクッキーの生産量を増やすことができないかと考えた。
方針
ゴールデンクッキーを自動でクリックするためには、ゴールデンクッキーが画面上のどの位置に出現したか検出できなければならない。今回はOpenCvで簡単に実装できそうな、以下の二つの手法を比較することにした。
- テンプレートマッチング
- 特徴量マッチング(AKAZE)
テンプレートマッチング
テンプレートマッチングとは以下の手法をいう。
テンプレートマッチングは画像中に存在するテンプレート画像の位置を発見する方法です．
OpenCvは cv2.matchTemplate() 関数を用意しています．
この関数はテンプレート画像を入力画像全体にスライド(2D convolutionと同様に)させ，テンプレート画像と画像の注目領域とを比較します．
特徴量マッチング
特徴量マッチングとは以下の手法をいう。
最初の画像中のある特徴点の特徴量記述子を計算し，
二枚目の画像中の全特徴点の特徴量と何かしらの距離計算に基づいてマッチングをします．
特徴量については以下の文章が言い得て妙である。
皆さん，ジグソーパズルで遊んだことはありますよね?
一枚の写真を細かく分割したパズルピースを正しく組み合わせて元の写真を作るゲームです．
どうやってパズルを解きますか?
というのが質問です．
特徴量とは、人間がパズルをする際に行っている「このピースは○○だからこの辺かな。」という「定性的な直感」を「定量的な値」として表現したものなのである。
人によって「定性的な直感」が異なるのと同様に、アルゴリズムによって「定量的な値」も異なる。今回は複数あるアルゴリズムの中から「AKAZE」を選択することにした。
方法
今回は上述した二つのアルゴリズムのから、どちらが適しているか検証する。
検証のためのディレクトリ構成を以下に示す。
- dst/
- src/
| xxx.png
| yyy.png
...
gc.png
match.py
dst
dstディレクトリは各アルゴリズムの実行結果が保存されるディレクトリである。
src
srcディレクトリは各アルゴリズムに与える入力画像を保持している。各アルゴリズムは入力画像に対してゴールデンクッキーの位置を判定し、結果をdstディレクトリに保存することになる。
入力画像の作成は後の工程の簡易化のため以下の点に注意した。
オプション
- 「FANCY GRAPHICS」を「OFF」
- 「PARTICLES」を「OFF」
- 「NUMBERS」を「OFF」
- 「MILK」を「OFF」
- 「CURSOURS」を「OFF」
- 「WOBBLY COOKIE」を「OFF」
- 各施設を「Mute」
- 背景を「black」を選択
作成した入力画像の一例を示す。
一般的なゴールデンクッキーの出現
Frenzy状態
Halloween状態
gc.png
gc.pngは検出対象である「ゴールデンクッキー」の画像である。
各アルゴリズムは入力画像に対して、この検出画像がどの位置にあるのか判定することになる。
match.py
match.pyは各入力画像に対して、検出対象の位置を示した出力画像を出力する処理を各アルゴリズムで実装してある。ソースコードを以下に示す。
# matcher
import os
import shutil
import cv2
def xmkdir(dst):
shutil.rmtree(dst, ignore_errors=True)
os.makedirs(dst)
return dst
def walk(fn, src, dst):
for path in os.listdir(src):
cv2.imwrite(dst + path, fn(cv2.imread(src + path)))
def template_match():
img0 = cv2.imread('./gc.png', cv2.IMREAD_GRAYSCALE)
img0_w, img0_h = img0.shape
def walker(img):
gray_img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
result = cv2.matchTemplate(gray_img, img0, cv2.TM_CCOEFF)
min_val, max_val, min_loc, max_loc = cv2.minMaxLoc(result)
cv2.rectangle(img, max_loc, (max_loc[0] + img0_w, max_loc[1] + img0_h), 255, 2)
return img
walk(walker, './src/', xmkdir('./dst/template/'))
def akaze_match():
detector = cv2.AKAZE_create()
matcher = cv2.BFMatcher()
img0 = cv2.imread('./gc.png', cv2.IMREAD_GRAYSCALE)
img0_w, img0_h = img0.shape
kp0, des0 = detector.detectAndCompute(img0, None)
def walker (img):
gray_img = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
kp1, des1 = detector.detectAndCompute(gray_img, None)
matches = matcher.knnMatch(des0, des1, k=2)
return cv2.drawMatchesKnn(img0, kp0, img, kp1, matches, None)
walk(walker, './src/', xmkdir('./dst/akaze/'))
if __name__ == '__main__':
template_match()
akaze_match()
各アルゴリズムは入力画像を一つ受けとり出力画像を返すwalkerを実装している。
それぞれのアルゴリズムの中核となる処理を以下に示す。
# テンプレートマッチング
cv2.matchTemplate()
# 特徴量マッチング
detector.detectAndCompute()
結果
各アルゴリズムの入力画像に対する出力画像の一例を示す。
一般的なゴールデンクッキーの出現
入力画像
出力画像
テンプレートマッチング
特徴量マッチング
Frenzy状態
入力画像
出力画像
テンプレートマッチング
特徴量マッチング
Halloween状態
入力画像
出力画像
テンプレートマッチング
特徴量マッチング
ゴールデンクッキーがない場合
入力画像
出力画像
テンプレートマッチング
特徴量マッチング
考察
テンプレートマッチングでは、すべての入力画像に対して適切にゴールデンクッキーの座標を抽出できていた。今回のケースでは検出対象が回転しないため、高い精度でマッチングできるのは妥当な結果であるように思える。変則的なHalloweenの場合でも、形が似ているためか問題なく抽出できているようであった。ゴールデンクッキーがない場合、「クッキー」ではなく、施設「Idleverse」が誤検出されてしまっていた。色やチョコの量が多少異なるものの、「クッキー」の方が「Idleverse」よりも類似度が高いように思えるので意外な結果であった。
特徴量マッチングにおいても、すべての入力画像に対して最も類似している場所はゴールデンクッキーであった。ゴールデンクッキーがない場合にも「クッキー」が類似していた。「クッキー」がマッチングできているのは「丸くてチョコがある」といった定性的な情報が特徴量に反映されているからであると思われる。
まとめ
今回の用途ではテンプレートマッチングでも特徴量マッチングでも問題なく使用できそうなことがわかった。
テンプレートマッチングはソースコードをほとんど変更することなしにクリックすべき座標を指定できそうである。一方で、特徴量マッチングでは類似度が最も高そうな座標の決定処理や、クリックすべき座標の抽出処理が煩雑であるためテンプレートマッチングを採用することにする。
次回の記事でテンプレートマッチングを利用したゴールデンクッキーの自動クリックを実装する。
Source code
See also
[1] 現在10^53枚程度クッキーを生産したが、全実績解除には10^63枚焼く必要がある。