Autosplit Helper V1.43(a)と採用している比較方式について

Lemongrass
自作ソフト
Page content

（相変わらずブログというもので何を書けばよいのかわからない故の逃避行動）

というわけでタイトルの通りV1.43をアップしました。aがついているのは修正版です。修正だけでナンバリングを増やすのもどうなのかなと思っただけなのですが、過去の更新履歴を見ると修正だけでも平然とバージョンアップしていて、こんなところでも思考がふわふわとしてるんだなと見せつけられ。

V1.43は修正やちょっとした処理/UI変更がメインなのですが、画像比較の方法にヒストグラム比較、dHash、Norm（L2）、AKAZEを追加してみました。これで比較方法が8種類となりましたが、一旦それぞれどういう方法なのかをざっくり書こうかと。ライブラリがあってなんか良さそうだから使ってるっていうのが結構あるので解説はできません（

テンプレートマッチング Template matching

画像のマッチング方式は、大きく領域ベースマッチング、特徴ベースマッチングの2つに分けられます。テンプレートマッチングは領域ベースマッチングに分類されます。なお、ASHでは特徴ベースマッチングとしてAKAZEを入れています。 領域ベースは、テンプレートを事前に準備し（探索対象画像のサイズ≧テンプレートのサイズ）、探索対象内でテンプレートを少しずつずらしては比較、ずらしては比較…と、領域内を全探索していきます。計算方法は輝度値（画素値）の差の絶対値を累計したものや、フーリエ変換して計算量を減らして高速に類似度を求める等色々あるそうです（詳しくはぐぐって）。 探索対象内のどこに表示されても補足することが可能なため、特徴のある場面を見つけられれば大体これでマッチングさせられます。例えば、スーパーマリオワールドのクッパ戦では、攻撃タイミングによって撃破後のクラウンの位置が変わってしまいますが、どの位置になってもマッチングを行えます（一致率は若干落ちます）。マスク画像を作ればより正確にマッチングできます。対象が小さいと精度が落ちやすいので、その点は注意が必要。 ASHではCCOEFF Normed(Correlation coefficient：相関係数　を明るさで正規化)とSQDIFF(Sum of Squared Difference：差分相関)を採用しています。それぞれのアルゴリズムを比較してどうこうというわけではなく、単純に全部使ってみて最も結果が良さそうなものを選んだだけです。CCOEFFはマスク画像に対応していないので、対応している方法（CCORR Normed、SQDIFF）の中で良さそうな方を選択しました。CCOEFFのマスク画像対応版を作ろうと試行錯誤したこともありましたが、それっぽいのはできても処理速度が絶望的に遅く、全く使い物になりませんでした…公式対応が待ち望まれる。

AKAZE

特徴ベースマッチングです。画像から特徴点を抽出し、その周囲を切り出して特徴量を算出し、テンプレートにそれが存在するかどうかを確認する方法だそうです。領域ベースマッチングと異なる点は、画像の変形（回転や拡縮など）に強いというところです。領域ベースや↓で説明する比較方法は画像の変形に非常に弱いですが、特徴ベースの場合、画像の変形があっても特徴量に大きな変化は発生しにくく、比較に支障をきたしにくいのです。良い例えを思いつけませんが、ゲーム内で文字やアイコン、キャラが拡縮しながら表示されていたり回転していたりというのは見かけるので、そういう場面を対象にしたい場合に効果を発揮すると思います（そのような場面は対象にしないのが基本、また特徴点の抽出はCPU負荷が非常に高く、監視間隔を落とす等の対処が必要な可能性が高い。）。

上画像はAKAZEの結果を描画したものです。丸い印は特徴点を示し、それぞれの画像で類似した特徴点がある場合、線で結ばれます。なお、ASHではこの類似した特徴点の数を基準に判定をしています。「SHINE　GET！」のように、輪郭がはっきりしたものをテンプレートとすると、周囲が異なる映像でも反応してくれることが分かると思います（この場合は他の方式でマスク画像を利用しても同様の結果が得られるので、AKAZEは優先度低め）

■画像

RGB比較（ピクセル毎） RGB diff (per pixel)

最初期に使用していた方法です。原理は非常に単純で、探索画像とテンプレート（サイズは同じ）の同位置にある画素値を取り出し、RGB値を比較していくだけです。ほんの僅かな位置ずれが発生するだけでも使い物にならなくなるので画像マッチングとしては存在自体許されるものではないですが、対象がゲーム画面で、基本的に位置ずれは発生しないのでなんとか使い物になっています（が、スーパーマリオブラザーズ3のゴール時に表示される文字が1~pxずれることがあるようで、その場面では残念ながら使えないという結果に）。また、テンプレートサイズが1×1から比較ができるので、ほんの僅かな変化もトリガーにすることができる点では優秀なのかもしれません（他の方式の場合そういった変化は吸収されてしまう）。 全画素値を取得するので、例えばテンプレート中の探索対象から外したい部分を特定の色で塗ってマッチング時にその部分を排除するなど、ちょっとしたひらめきを適用しやすい点ではちょっと嬉しいかも。

RGB比較（累計） RGB diff (sum)

原理はRGB比較（ピクセル毎）と同じです。違いは結果の求め方です。 ピクセル毎の場合、各ピクセルが一致しているかどうかを判定し、一致しているピクセル数を求めます。一方で累計の方は、各ピクセルのRGB値の差（絶対値）を求め、その総和を算出し、この値が閾値より大きいか小さいかで一致判定を出します。正直なくても支障がないと思うので、使い道が見いだせなかったら消すかもしれません。一応ピクセル毎の比較より冗長性の高い方式としてなんか使えそうだなと思ったのですが…

RGB比較（色の割合） RGB color ratio

似た名前が続いてますね。 上2つは全画素値を取得しているのですが、だったら特定の色の全体に占める割合も算出できるなということで。探索画像内に指定した色が含まれる割合を算出し、その値を元に一致判定を出します。 これも使い所がなさそうに感じますが、意外にも特定の場面で力を発揮したりします。例えば、スーパーマリオ64の最終クッパ撃破後にスーパースターを取る場面。これはRTAの計測終了地点ですが、取り方によって映像が変わる、固定化することができないので、この場面でマッチングさせるのは非常に困難です。しかし、取得した瞬間に白い煙が発生し、この場面前後で白のピクセルが大きく変化することはないため、白のピクセルの量を見ることで一致判定を発生させることができます。 他には、スーパーマリオワールドのクッパ撃破後のピーチが出現する時（こちらも計測終了地点）。ピーチが出現する瞬間、1フレームだけピーチは左を向き、その後は着地するまで右を向きます。左を向いている場面をテンプレートにしたいのですが、1フレームしか表示されないため、キャプチャソフトやASHのフレームドロップ等により判定が発生しない可能性があります。また、ピーチが現れる時、周囲にキラキラと輝くパーティクルが表示されるのですが、これがピーチに大きく被ると一致判定が出ないことがあります。このような状況でも大きく変化が出ない情報の一つに、ピーチのドレス（ピンク色、ユニーク）が画面内に占める割合があるということですね。これならばピーチがどちらを向いていようが変わりませんし、パーティクルが被るといっても全身を覆うほどではなく、必ずドレスは表示されるので、この場面で一致判定を発生させることが可能になります。

ヒストグラム Histogram

2枚の画像のヒストグラムの類似度を求めます。OpenCV(Sharp)には比較方法としていくつか選択肢があったのですが、よく分からなかったので他の方の記事を参考にBhattacharyya distanceを採用しました。正確さは高く、速度は遅い、ということらしいです。実際に使ってみると速度に問題はなく、精度もなかなかでした。対象の表示位置がランダムで領域/特徴マッチングを使いたいが負荷は抑えたい、という場合等に使えそうです。全く異なる場面でもヒストグラムが似ていれば一致判定が出てしまうので、その点は注意が必要です（あまりそういう場面に出くわすことはないでしょうが）。

dHash

dHash (difference hash)は画像のために作られたハッシュのことです。あるデータを関数に入れて出てきたものがハッシュ値で、データが同じであればハッシュ値も変わらないため、データの破損確認、比較なんかに使われるそうです。例えばASH1.43、1.43aのハッシュ値（MD5）は、 V1.43_:cb87880bed9e33351b6095b2952b169f V1.43a:89a28b6bb66329930371c8e3446463cc

でした（Hashmyfiles使用）。ほとんど変更してないのですが全然違いますね。

これを画像比較に応用してしまおうということで。そのままだとほんの僅かな色情報の違いでハッシュ値が変わってしまって使いものにならないので、ある程度画像が似ていれば結果も近くなるように画像用のアルゴリズムが誕生した…んだと思います。

種類としてはAverage Hash、Perceptive Hash、Difference Hash、Wavelet Hashなどなど。それぞれの特徴はこちらの記事が綺麗にまとまっていると思います。

この中でdHashのみを採用しました。wHashとか使ってみたいなと思ったのですが、ウェーブレット変換てなんぞやなレベルなのでコーディングは端から諦めてました…　Imagehashで上記4つのアルゴリズムを試せるそうなので（要Python)、これは実装せざるを得ないと感じたら挑戦するかもしれない。

Norm (L2)

Normは…よく分からんです（ぉ ベクトルの大きさのことをノルムと呼ぶので、探索画像とテンプレート（サイズは同じ）を何らかの値（輝度値など）を基準に差を取って（OpenCV内では画像は行列として扱われる）、そのノルムを計算してるんでしょうかね？L2は高校数学で習うベクトルの大きさと同じものだそうです。

L(p)ノルム = √(|x1|exp(p) + |x2|exp(p) + … + |xn|exp(p)) と表され、p=2の時 L2ノルム = √(|x1|exp(2) + |x2|exp(2) + … + |xn|exp(2)) …n=2とすると確かにピタゴラスの定理の式になりますね。 精度に関しては検証不足なため、微妙な差を区別できるのか等気になる点はありますが、このあたりはそのうち。


説明になってない気しかしないですが、とりあえずASHで選択可能な比較方式について書いてみました。結局どれ使えばええんやって話ですが、テンプレートマッチング、Norm L2を主軸に、対象やPCスペックに合わせて適宜選択すればいいんじゃないかなと思います。