デレステのタップ音からプレイ中の曲を推定する(eeic Advent Calendar 2017)

この記事は eeic Advent Calendar 2017 の 4 日目の記事です。

今日はチノちゃんのお誕生日だけど、ごちうさネタなどいつものように思いつかないので今年もデレステネタで。

さて、デレステ(アイドルマスター シンデレラガールズ スターライトステージ)は今年で 2 周年を迎え、収録曲数も増え【秋風に手を振って】実装により 130 曲を迎えた。しかし研究室でイヤホンをしながらドカドカプレイをしていると、130 曲もあるのにスマホの画面を叩いている音だけでプレイしている曲がわかってしまう。

これをコンピュータでできないか、すなわちスマホを叩いているだけの音声からどの曲をプレイしているかを自動推定できないか、と思うわけである。

1. 課題設定

真面目に課題を設定していこう。ここでは次のような条件で解くことにした。

  • スマホを叩いている音だけから、プレイ中の曲を推定する
  • 雑音下での検出は難しそうなので、ある程度静かな環境を想定する
  • 譜面は Master と恒常 Master+ の全譜面を対象とする(およそ 190 種類)
  • リアルタイムに、どの譜面をプレイしているかの確からしさを出す

※ デレステは Android および iOS 上で動く、音ゲーメインのアイドル育成ゲームです。
※ 音ゲー譜面の難易度は 5 段階あり、Master と Master+ は上位 2 つを指します。Master+ が実装されていない曲もあります。ここでは特別に記さない限り譜面は Master のことを指し、Master+ については必ず(Mas+)と表記します。
※ 曲名かどうかわかりにくい可能性があるので、曲名は統一して【すみつきかっこ】で表すことにしました。

2. タップ音検出

まずはタップ音を検出しよう。これは音声系の分野では音響イベント検出(AED: Acoustic Event Detection)にあたる。わかりたいことは「録音開始から何ミリ秒にタップ音があったか」だ。

実際にスペクトログラムを見てみよう。次の図は【風色メロディ】プレイ中のスマホを叩いている音のスペクトログラムである。サンプリング周波数は 16000 Hz とした。
【風色メロディ】プレイ中のスペクトログラム
0.15 秒程度の尾を引いて断続的に見えるのが打鍵音。本当はインパルスのような形になって欲しいが、現実世界なのでそうはいかない。これの叩いた場所だけ 1 になるように処理したい。

この処理には隠れマルコフモデル(HMM: Hidden Markov Model)や非負値行列逆畳み込み(NMFD: Non-negative Matrix Factor Deconvolution)などの手法が知られている。一方でこういった処理は結構実装が面倒な上計算がかなり必要なので、今回のようなかんたんなタスクを考えるとコスパが悪い感じがする。

そこでとりあえず、10 ミリ秒を 1 フレームとして、1 フレームあたりのエネルギーをプロットしてみる。エネルギーは波形のデータの 2 乗和である。
フレームあたりのエネルギー
これを見ると、叩いた瞬間のフレームがエネルギーのピークとして現れていることがわかる。こうなれば、難しいことは考えずピークの場所を求めれば済みそうだ。

実はピーク検出も奥が深く、どのようなピークを検出したいかによってもやり方が変わってくる。ここではピークの条件として、

  1. 前後 5 フレームずつとくらべて、自分自身が最も大きい
  2. 前後 5 フレームの平均とくらべて、自分自身が明確に大きい(ここでは 5 倍程度とした)

の 2 つを満たすものとした。こうすることで誤検出を少なくできるし、ピーク検出の遅れも 5 フレーム(50 ミリ秒)しかない。実際にピーク検出をしてみると、次の図のようになる。青が先程のエネルギー、オレンジが検出結果である。
ピークの検出結果
エネルギーのピークがあるところだけをピッタリ検出できていることがわかる。

この手法は 0.05 秒以下のズレで押した場合検出できない。実際に譜面中にも 0.05 秒以下の間隔で押さなければいけない箇所がいくつかある。ただこれは数えるほどなので、そこまで検出には大きな影響がないと思うので許して。

※ ここでは平均をとっていない単純な波形の 2 乗和なのでエネルギーと表現しています。
※ 2 つめのグラフの軸を書き忘れました。許してください。
※ 最もタップ間隔が短いのは【命燃やして恋せよ乙女】【命燃やして恋せよ乙女(Mas+)】のところどころに出てくるほぼ同時押しのやつです(BPM 112 の 64 分=0.0335 秒)。
※ 2 番目に間隔が短いのは【LET’S GO HAPPY!!(Mas+)】のラストサビ「一緒だから大丈夫!」の直後です(BPM 192 の 32 分=0.0391 秒)

3. DP マッチングによるコスト計算

どの曲をプレイしているかは、辞書になっている譜面と実際のプレイを比較して、その 2 つの距離(コスト)を計算し、そのコストが一番小さいものを選べばいい。譜面と検出したタップ音がずれていたらコストが大きく、逆にピッタリ合っていたらコストが小さくなるような、そんな指標(コスト関数)を設計したい。

スマホも PC も処理落ちすることなく、しかも人間が完璧正確にプレイできれば、単純に時刻ごとに譜面と環境音の ON / OFF を比較すればいい。しかし、2 つの時系列が微妙に違っていたり、タップ音を誤検出したりプレイ中にミスしたりすることを考えると、簡単に比較するだけではコストが出せない。

音声系の処理では、こういったものでは動的時間伸縮(DTW: Dynamic Time Warping)というアルゴリズムが知られている(英語版 Wikipedia / 解説記事)。フレームごとに、譜面を「0 1 0 0 0 1 0 0 1 0 0」、検出タップ音を「1 0 0 0 1 0 0 0 1 0 1」などと表現しておけば、(たとえ全体の時間の長さが違っていても)この 2 つを DTW によってマッチさせることでそのズレの大きさを数値にできる。

しかし、10 ミリ秒で 1 フレームだからめちゃめちゃ計算回数が多い気がするし、0 と 1 しかないんだからわざわざこんな表現しなくてもいい気がする。つまり 1 の場所(1 が立つ時刻)だけでこのコスト計算をしたい。

そこで、DTW と同様にこれを動的計画法(DP: Dynamic Programming)を利用した DP マッチングによって実現しよう。

ここでは簡単に、次のような譜面データ(全部で 5 ノーツ)とタップ音検出結果(全部で 4 回)があったとする。譜面のデータは曲開始からの秒数、タップ音は録音開始からの秒数を表している、と考えてよい。

score |  tap
0.10  |  0.20
0.25  |  0.35
0.40  |  0.40
1.00  |  1.30
1.30  |

結局何が欲しいのかというと、ペアの作り方を全パターン試してコストを計算してみたうちで、最も小さいものである。ペアというのは、譜面でのタップと検出されたタップのペアである。ここでは当然片方がない(独りぼっちの)ペアがあってもよいとする(もしくは複数の人とペアを組んでいるものがあってもいいとする)(そうしないと合計数が合わなかったときに困る)。このペアの作り方をなるべく効率よく全探索(ビタビ探索)できるのが DP マッチングである。

ここからは画像を示しつつやり方を説明していこう。まずは表を作る。何も難しくない。

ペアの作り方は、この表の上での経路にあたる。適当な制約(たとえば 1 つ右 or 上にしか進めない制約)のなかで経路を決めることで、その経路のコストが決まる。コストはどう決めるかというと、経路を構成する 1 つ 1 つの局所パス(たとえば 1 つ右 or 上に進むという行為)のコストを決めることで、その経路全体のコストが定めることができる。この局所パスの選び方やそのコストの計算方法は様々に考えられるが、今回は次のように定めた。局所パスとしてはそれぞれ 1 つ右/上/右上に進むことにあたる。

  • 1 つ左のマスからくるパス(コストはタップ音の時間差)
  • 1 つ下のマスからくるパス(コストは譜面上のノーツの時間差)
  • 1 つ左下のマスからくるパス(コストはタップ音の時間差とノーツの時間差の差の絶対値)

これをもとに、次からマスをうめる手続きをしていこう。

マスには何を入れるかというと、そのマスに至るために考えられるすべての経路のコストのうち最小のものを入れる。最終的には一番右列のところまでの経路を考えたいけれど、そこまで一気にかんがえると大変だ。だから、まずは短い経路でいろんなパターンを計算しておいて、その結果を利用することで効率よく探索しようというのがこの DP マッチングである。

とりあえず順番にやっていこう。まず境界条件を定める。別に直前まで放置してもいいのだが、面倒なので先に埋めておく。一番左側は全部ゼロで、一番下は最初のタップ音からの時間差を入れている。

最下段の処理は、上で述べた局所パスの定義と一致している。最左列をすべてゼロにしたのは、1 番目のタップ音がどのノーツに対応していてもいい、すなわち録音が途中から始まったとしてもよいという仮定から得ている。この仮定は、経路が左列のどこから始まってもいいことと同じで、これを端点フリーと言ったりする。

次に中のマスを埋めていく。まずは下図で色をつけたマスについて。先ほど述べたコストの定義にしたがって埋める。タップ音の時間差は 0.15 秒、譜面の時間差も 0.15 秒なので、この 2 つの差は 0 秒になる。それぞれが左からのコスト、下からのコスト、左下からのコストにあたる。

局所パスのコストがそれぞれ計算できたら、もとのマスとの和の中で最小を選んでマスに埋める。これが、そのマスに至るための最小コストにあたる。左からのパスは 0+0.15=0.15、下からのパスは 0.15+0.15=0.30、左下からのパスは 0+0=0 なので、最小値は 0 であり、左下からの局所パスが選ばれる。

あとはこれをひたすらに繰り返す。左列から、下から順番に埋めていけばできる。

最後に一番右の列の中で最小のものを、観測タップ音列と譜面の間のコストとする。この結果は、このタップ音列がもしこの譜面をプレイしているとしたら、最後にタップしたのは 1.00 秒にあるノーツのことであろう、ということを推定していることになる。

一番右上をコストとする場合もあるが、これは最後のタップ音と譜面の最後のノーツの対応は取れていると仮定する場合である。今回は途中までしか叩いていなくてもコストを出したいので、最右列の最小値を選ぶ。これも端点フリーである。今回は左と右の両方を端点フリーにしたので、両端点フリーの DP マッチングになる。

たとえタップ音がこれから増えて表が 1 列右に伸びても、今まで計算した分は変わらないので最後の 1 列分だけ計算すればいい。これも DP マッチングを使うメリットだ。

タップ音を検出するたびにこの方法で各譜面とのコストを計算しなおせば、どの譜面とマッチしているかをリアルタイムに数値で表すことができる。

※ 実際に自分で表を書いて埋めてみるとよくわかると思います。動的計画法のいいところは、人の手でも動きが追いやすいところです。
※ 局所パスの選び方、局所コストの決め方によって結果は大きく変わります。若干今のままでは誤検出に弱い気もするのですが、結構ちゃんと動いてくれるので、細かいことを考えるのはやめました。

4. 実装

まず譜面データの作成に関して。デレステには「叩く必要がないノーツ」もしくは「叩く音が原理的に発生し得ないノーツ」というのがある。これらは無視して譜面データを作る。

  • フリック
  • ロングノーツの終端
  • スライドノーツの途中点
  • スライドノーツの終端

さらに、同時押しをする場合は検出タップ音が 1 回になることが想定されるので、これは 1 つにまとめた。

あとは上の処理を全部 MATLAB でちょちょいと書きました。

5. 実際にやってみた

コストが小さい方から 5 つを順番に表示してみた。どの場所のことだと認識しているのかを確かめるために、推定される今の歌詞も同時に表示するようにしてみた。動画中のパーセンテージが大きいほどコストが小さくもっともらしい。

表示はタップ音を検出したときのみ更新するようにしている(なのでタップ音を検出していないときには表示は動かない)。

通常のパターン

【ØωØver!!】をプレイしながらやらせてみた。

イントロが終わる頃には既に曲の目星がついていて、その後は他を引き離していくかたちになっている。A メロが終わった段階で 99% を超えている。かんぺき。

途中からのパターン

曲の途中から判定させた。曲は【We’re the friends!】を用いている。

30 秒しかないので若干厳しいが、最後には完全に特定が終了して正解している。とてもよい。

どうでもいいけど再開ボタン押すときにピークを誤検出している(いや、タップをしているのである意味誤検出ではない)。これ以外にもフレーム送りで見るとところどころ誤検出しているのがわかるが、これでもちゃんと曲の推定はできている。

ちなみに最後の方に Mas+ の譜面も検出されていることがわかる。これは他の Mas+ 実装譜面でもよく起きる。たとえ譜面が違っていても、曲が似ているとランクインされやすいのかもしれない。

めっちゃ雑音が多いパターン

大音量でプレイしてみた。曲は【Shine!!】を用いている。

このくらい大きなノイズが入ると、ピークが検出できず正しく推定できない。残念。

※ 動画中の音声はローパスフィルタと背景雑音抑制処理をしています。実際にはもっと雑音の乗った音声を処理しています。
※ パーセンテージは、コストの最小値を引いた値に対して負をとったものの softmax としています。
※ 本当は Web アプリでも作ろうかと思いましたが、そこまで手が回らないのでやめました。

6. まとめ

というわけで、簡単なピーク検出と DP マッチングだけで、タップ音からプレイしている曲を推定することができた。実際には上の【ØωØver!!】の動画よりもめちゃくちゃ動いておもしろい。【薄荷 -ハッカ-】や【TOKIMEKI エスカレート】などは 10 ノーツ程度で 1 位に選ばれるなど、曲によってもわかりやすさが違うようだ。

現状の問題点として、ピーク検出が雑なので非定常な(突発的な)雑音に弱いこと、DP マッチングのアルゴリズム上でタップ音の間隔が短い場合に差がつきにくいことなどが挙げられる。このへんも解決したいけどまあ動くしいいんじゃないかな。

音声波形処理と動的計画法を組み合わせてデレステのプレイを分析する、という結構 eeic っぽい内容になったと思う。もっとゴリゴリの音声処理をして複雑なモデルを使ってもよかったなぁとも思うけれど、結構きれいに動いたのでよし。ぜひ皆さんも他の音ゲーで実装したり、何か別のことに応用したりしてみてください。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です