月を眺める孤島

多分デレステとポケモンの話がメインのブログです

デレステの譜面をOpenCVでデータに起こしてみる

こんばんは、むぅんです。

今回は1年以上前にやったデレステの譜面をOpenCVを用いてデータ化する手法を簡単ではありますが書いていきたいと思います。
これ自体は数年前から構想していたのですが、完璧なタイミングでPERFECTを取り続ける動画の撮影が人力では不可能という点で諦めていました。音ゲーによっては放置(全MISS)でもいけるものもあるかもしれませんが、デレステの場合ロングやスライドは手で取らないとそこから先が消失してしまうためこれも不可能です。
そんな中実装されたデモプレイ機能がまさに待ち望んでいたものだったので、無事に実現することができた次第です。

大まかな流れ

1. デモプレイ機能を用いてプレイ動画をノーツ速度10で撮影
2. 動画を1フレームごとに切り出す
3. あらかじめ用意したノーツアイコンの画像でテンプレートマッチングを行う
4. ノーツが検出されたフレーム数や座標から秒数やノーツの種類を割り出し記録
5. 全て記録し終えたらcsvファイルとして出力


録画環境

今回、録画はiPad Pro 10.5インチ(2017年モデル)で行いました。OSはiPadOS 13.3です。古いOSの場合、音がモノラルでしか録音できませんが、今回のプログラムとは一切関係ないので大丈夫です。
Androidでできるかは不明ですが、60fpsで録画できるならおそらく問題ないと思われます。
これ以降、iPadで録画したものとして話を進めていきます。


デレステは今いる画面によってfpsが変動します。例えば、楽曲のプレイ中は60fpsですが、リザルト画面に以降した直後から30fpsに切り替わります。なお、これは後に詳しく解説しますが、OpenCVの cap.get(cv2.CAP_PROP_FPS) は全く当てになりません。これで取得できるfpsは動画の総フレーム数を動画時間で割っただけのものであり、フレームレートが可変な動画であってもお構いなしに平均値が得られるだけです。たとえ60fpsである楽曲のプレイ画面だけを録画しても、録画を終了する際に起動するコントロールセンターが30fpsなのでどの道60fpsにはなりません。逆に、楽曲のプレイ中はそもそも60fpsから動くことはほぼないのでこの関数でfpsを取得する必要はありません。


テンプレートマッチング

テンプレートマッチングには cv2.matchTemplate() 関数を用います。なお、テンプレートマッチングでは普通画像をグレースケールに変換してから処理を行います。
第3引数ではいくつかあるマッチング方法を指定しますが、ここでは cv2.TM_CCOEFF_NORMED を指定します。これはZNCC(ゼロ平均正規化相互相関)と呼ばれる手法で、返り値は  -1 から  1 までの値を取り、より  1 に近いほど類似度が高いことを示します。
類似度  s は、入力画像の輝度値を  I(i, j) 、テンプレート画像の輝度値を  T(i, j) とすると次のように計算できます。なお、テンプレート画像のピクセル数は  M \times N で、左上の座標を  (0, 0) 、右下の座標を  (M-1, N-1) とします。

 s = \frac{\displaystyle \sum_{j=0}^{N-1} \sum_{i=0}^{M-1} ( (I(i, j) - \bar{I}) (T(i, j) - \bar{T}) ) }{\sqrt{\displaystyle \sum_{j=0}^{N-1} \sum_{i=0}^{M-1} ( (I(i, j) - \bar{I}) )^{2} \times \sum_{j=0}^{N-1} \sum_{i=0}^{M-1} ( (T(i, j) - \bar{T}) )^{2} }}

この関数で得られた結果を cv2.minMaxLoc() に代入することで、最大類似度やその最大類似度が得られた部分の左上の座標が得られます。

試しに、以下のテンプレート画像を用意します。


f:id:shinemoon227:20201103044924p:plain


これを実際のプレイ画面の画像で検出してみます。検出範囲は  170 \leq x \leq 470, \ 900 \leq y \leq 1100 で、その範囲内にノーツの一部のみが写り込んだときと端から端までノーツが全て写り込んでいる2パターンで検証します。


f:id:shinemoon227:20201103045330p:plain
よしのんかわいいですよね


まずは一部写り込んでいるほう(下図左側)ですが、最大類似度はわずか  0.0887 と到底テンプレートと一致しているとは言えないような結果でした。下図にはテンプレートと同じ大きさの矩形を最大類似度が得られた座標を基準に描画していますが、まるで違う場所に描画されていることがわかるかと思います(ちなみに左上の座標はこの検出範囲内基準で  (128, 55) でした)。
一方、全て写り込んでいるほう(下図右側)では最大類似度は約  0.9282 となり、ほぼ一致している部分が存在していたということがわかります。左上の座標は  (101, 44) で、描画された矩形は綺麗にノーツのある部分を指し示していることが見て取れます。矩形の中心座標もバッチリど真ん中ですね。


f:id:shinemoon227:20201103050041p:plain


実際には、次の画像に示した5箇所の範囲内でノーツが通過するのを監視します。ノーツを検出したら、6種類あるノーツのうちどれが通過したかを判断し、通過したフレーム数からおおまかな秒数を測定するという寸法です。


f:id:shinemoon227:20210225223443p:plain
一部重なっているため見づらいですが、全部で5つの矩形の範囲内で検出を行います



ノーツの種類を分類する

現在、デレステのWIDE譜面にはタップ、ロング、左フリック、右フリック、スライド始点(終点)、スライド中間点の6種類のノーツアイコンがあります。この内のどれが通過した判断するには類似度を比較します。要は1フレームごとに6枚全てのテンプレートと比較し、その中で最も類似度が高かったものをそのノーツの種類と判断するわけです。実際にこれはおおよそうまくいき、例えば正解がタップアイコンの画像に対しタップアイコンのテンプレートを用いてマッチングを行った場合、類似度は限りなく  1 に近くなります。一方、他のテンプレートを用いてマッチングしても基本的に  0.5 から  0.8 程度に留まります。  0.8 は十分に高い値ではありますが、たいていそういうときは正解がさらに高い値を示すので普通は問題ありません。このことから、今回は類似度のいずれかが  0.8 を超えたときノーツが通過していると判断し、その中で最大値であったテンプレートを通過しているアイコンとみなします。閾値は割と適当なので、これで上手くいかなければ適当な値に調整してみてください。

一方で、最大値を見るだけでは判断がつかない例外もあります。それがスライド始点とスライド中間点です。これらはただ明るさが異なっているだけで、デザインそのものは同じアイコンです。よって、場合によっては類似度がかなり近くなってしまい、判定に疑問が残る形となってしまいました。そこで「そもそも人間もこれらのアイコンを見分けるときに明るさを用いて判断している」という点に着目し、スライドのどちらかである可能性が高まったときだけ画像の画素全ての輝度値の平均値を比較することで始点か中間点のどちらであるかを判断することにしました。OpenCV上では、グレースケール画像は2次元リストに各ピクセルごとの輝度値を持っているだけなので、Numpyの np.average() などを用いて簡単に平均値を算出できます。

なお、今回ノーツを検出しているのは前述の通り  900 \leq y \leq 1100 の範囲ですが、ノーツ速度10で録画した場合、ノーツはおおよそ4フレーム写りこみます。稀にフレームごとにノーツの種類が違うものと判定されることもあるので、ここでは保険として最頻値をノーツの種類としています。例えば、3回タップノーツ、1回ロングノーツと判定された場合はタップノーツであったと判断します。

ノーツの始点と終点を判断する

終点は前述の通り、マッチングを行う範囲を5箇所に分けていることから自明ですが、始点はどう判断すれば良いのでしょうか?様々な方法を考えましたが、最終的には  {\rm atan2} (y, x) 関数を用いることで解決しました。これは  {\rm tan} (x)逆関数  {\rm atan} (x) とは似て非なるもので、  {\rm atan} (x) {\rm tan} (θ) = x となるような  x を求めているのに対し、  {\rm atan2} (y, x) xy 直交座標における  (x, y)偏角を求める関数です。定義は次の通りです。



{\rm atan2} (y, x) = \begin{cases} {\rm atan} (y/x) & (x > 0) \\ {\rm atan} (y/x) + \pi & (y \geq 0, x < 0) \\ {\rm atan} (y/x) - \pi & (y < 0, x < 0) \\ \pi / 2 & (y > 0, x = 0) \\ -\pi / 2 & (y < 0, x = 0) \\ {\rm undefined} & (y = 0, x = 0) \end{cases}


この関数を用いて、時刻  t に検出されたノーツの座標  (x(t), y(t)) と時刻  t+1 に検出されたノーツの座標  (x(t+1), y(t+1)) からノーツが進んでいる角度  r = {\rm atan2} ( (y(t+1)-y(t)) / (x(t+1)-x(t)) ) を計算し、その値によってノーツがどの始点から終点へ向けて流れているか調べようというのが今回の手法です。
例えば、真ん中(左から順に1~5と番号を振るデレステおなじみの記法での3にあたる終点)に向かって流れてくるノーツを考えます。もし3より左側からノーツが流れているとすると、  r < \pi / 2 となることは自然だと思います(  y 軸は下向きに正であることに注意してください)。一方、右側からノーツが流れていれば  r > \pi / 2 であるはずです。このように、角度を見れば始点がある程度わかるので、後は各々の始点と終点で角度がだいたい何度くらいになるかを1パターンずつ地道に調べていき、その値に応じて泥臭く場合分けするだけです。

ちなみに、  {\rm atan2} (y, x) の何が嬉しいかというと、値域が  [-\pi, \pi] であることから、たとえ3から3へ向かって流れてくるようなパターンでもエラーにならないという点です。  {\rm tan} (x) = \pi / 2 となるような  x は存在せず、  {\rm atan} (x) では「ちょうど角度が  ±\pi / 2 の方向へ向かって進んでいるもの」の検出に不向きなのです。ゲームプログラミングなどにおいて角度の取得はごく一般的なので、どのような角度でも正しく角度を返してくれる  {\rm atan2} (y, x) はたびたび利用されています(というより  {\rm atan} (x) は滅多なことがない限り使われない気がします)。

ここでも、ノーツの種類同様始点候補が複数あったときは最頻値に基づき一番可能性の高いものを始点とします。

ノーツの流れてきた時刻を計測する

ノーツの流れてきた時刻は経過したフレーム数をもとに算出し、そこからy座標による微調整を行います。フレーム数からでは1/60秒の精度でしか秒数を割り出せませんが、ノーツは画面下部では  42[\mathrm{px} / \mathrm{f}] ほどの速さで動いており、これを利用することでさらに42倍の精度を得ることができます。細かな調整は環境によって異なると思うのでここでは省略します。

コマ落ちしてしまったフレームを補完する

ここが今回のプログラムのキモであり、大変苦労した部分になります。フレームごとに動画を観察していけばわかるのですが、2~3分ほど録画した場合10箇所程度、最大で3フレームほどまとめてコマ落ちが生じることがあります。3フレーム程度微々たるものと思われるかもしれませんが、前述した通りノーツの流れてきた時刻は1フレームのさらに1/42、すなわち0.0004秒程度の精度で取得できるため3フレームも抜け落ちてしまっては問題です。事実、Frostに見られるようなスライド中間点が密集したような配置でこの現象が起こると目に見えて譜面データの質が悪くなります。

そこで、これを解消するためにffprobeコマンドを利用し動画ファイルの解析を行います。今回はこちらのサイトを参考にしました。


www.cresco.co.jp


このコマンドで動画ファイルを解析し、その中のpkt_pts_timeという部分に着目すると、各々のコマの正確な時刻がわかります(単位は秒)。例えば、60fpsの動画から次のような時刻のデータが得られたとします。

…, 60.000000, 60.016666, 60.050000, 60.066666, …


皆さんはこの時刻の不自然な点に気付いたでしょうか?60fpsであるならば1フレームごとに進む時間はおよそ0.016666秒であるはずですが、ここでは60.033333秒にあたるコマが抜け落ちていることがわかります。このように、ffprobeコマンドを用いれば各コマごとの時刻がわかるため、本プログラムではフレーム数を1/60倍したものを秒とする単純な方法ではなく、ffprobeコマンドで得た正確な時刻を利用します。もし運悪くノーツの流れてきた時刻を計測するタイミングのコマが抜け落ちてしまった場合は正確な譜面データが得られませんが、そのようなことはめったに起きないため問題はありません。万一奇跡的にそうなった場合は素直に録画しなおしましょう(録画するたびにコマ落ちする箇所は変わるため2回続けて同じことが起きることはないと言っていいでしょう)。

ただし、このコマンドで動画ファイルの解析を行うのには数十秒から数分程度の時間がかかります。そこはぐっと我慢しましょう。


動画の回転について

さて、ここまでテンプレートマッチングで得られたデータからノーツの情報を取得する方法を書いてきましたが、実は前提となる動画に致命的な欠陥が存在しています。それは、iPadiOSおよびiPadOS?)でデレステを録画すると、必ず90°または270°回転した状態で保存されるという問題です。

これがなかなか厄介で、各フレームごとに画像を回転させるとなると処理にとんでもない時間がかかるのです。これを何とかする方法はないのか調べても情報が出てこず、自分なりに回避する方法を模索した*1のですが、そもそもデレステに限らず横向きで録画した動画は全て同じような現象が発生することがわかっただけでした。これは自分1人ではどうにもならんと悟ったので何を血迷ったかAppleのサポートに直接電話で問い合わせたのですが、どうやらそれは(おそらく)仕様であるらしく回避の方法はないとのことでした。

完全に八方塞がりとなってしまったため、僕が行き着いた手段は縦向きのままテンプレートマッチングを行うという方法でした。そして、得られた座標を後から回転すれば、回転するデータは数百万分の一となり*2処理にかかる時間が大幅に減少します。*3そればかりか、得られた座標さえ回転してしまえば、以降のプログラムは一切書き換えることなく横向きのまま処理を行うことができるのです。

また、それに合わせテンプレートも次のように回転させます。


f:id:shinemoon227:20210225223834p:plain


あれ?さっき見たテンプレートより細くね?と思われるかもしれませんが、これは極端に密集したスライドでも判定を行えるようにするための工夫です。この程度テンプレートを縮めることで、Frost並に詰まったスライドでも正確に検出できます。


余談ですが、Appleのサポートに問い合わせた日、ちょうど東京へインターンに行っており、宿泊先のホテルがなんと携帯の電波が届かない圏外だったためサポートからの電話が受け取れず迷惑をかけてしまいました。Appleのサポートセンターの方々、その節は大変申し訳ありませんでした。


まとめ

以上が大まかな流れになります。正直ここに書いてない細かな処理は山ほどあるのですが、手が疲れてきたため今回はここまでとします。また書き足りていなかった部分があれば都度追記したいと思います。

ちなみに、得られたデータから譜面画像を出力すると次のような画像が得られます。フリックやスライドの補助線こそない*4ものの、かなり良い結果ではないでしょうか?


f:id:shinemoon227:20210225225033p:plain
Gossip Clubの譜面は"出力映え"しますね


Q&A(一部内容が被ってます)

あれ?フリックやスライドの補助線は?

テンプレートマッチングではどうしようもありません。誰か自動で読み取れるような手法を思いついた方は是非とも教えてください。

ノーツ速度10で録画しているわけは?

少しでもマッチングの精度を上げるためです。密度の濃い譜面の場合、速度が低ければノーツ同士が重なり合って正しく識別できない可能性があります。

テンプレート画像細すぎない?なんで?

ノーツ速度を上げることで密集したノーツを回避すると説明しましたが、それでもどうしようもないFrostなどの縦に細かく連なったスライドの対策です。

ノーツを押すところではなくそれより上のほうを見ているのはなぜ?

デモプレイなので正確にノーツを叩いてくれはするものの、「ノーツが消失した」ことを検出するよりも「ノーツが通過した」ことを検出するほうが遥かに楽だからです。上に行けば行くほど(ノーツが発射されてからの時間が短ければ短いほど)時間などの精度は悪くなることが予想されますが、少なくともノーツを叩く瞬間より数フレーム程度手前ならばほぼ影響はありませんでした。

ノーツのアイコンがTYPE3である理由は?

TYPE1や2、その他コラボで追加されたアイコンより区別しやすいアイコンだと判断したためです。普段TYPE6でプレイしているのでできればTYPE6で作りたかったのですが、あいにくこのプログラムを書いていた頃はまだ未実装だったため対応できませんでした。今からテンプレートを差し替えてもいいのですが割と面倒なので…。


ノーツの種類を見分けるのは色を見るのではダメだったの?

そのほうが精度はより良くなると思います。ただ、マッチングをフルカラー画像で行うと処理に時間がかかる他、そもそもグレースケール画像でも誤認識しているものは確認できなかった(複数候補があるときは最頻値を採用する手法において)ため問題ないと判断しています。


*1:縦向きの状態でデレステを起動するなど

*2:回転対象が全画素から1ピクセルのみになるため

*3:自分の環境では、データを出力するのにかかる時間が18分から3分ほどに短縮されました。

*4:なお、ロングの補助線は一意に定まるため補完の必要はありません。