音声の波形からピッチを検出するアルゴリズãƒ

去年のクリスマスに公開したカラオケ機能つき Quine の仕組みについて。

ref: 声の高さで操作するゲームを作ってみた

で解説されている内容と同一です。おわり。

で終わるのもつまらないので、簡単に解説します。でも思いだしながら書いているので嘘書いてたらごめんなさい。動画には図とかあるので、やはりそっち見た方がいいと思うけど。

「ピッチ検出なんて FFT するだけでしょ」と思ってる人は素人で、音叉みたいにきれいな正弦波を測りたいならともかく、声や楽器の音など倍音を含んだ音では誤判定が起きまくるようです。偉そうなこと言ってる私も素人です。そこで、Wikipedia の Pitch detection algorithm で挙げられている、MPM アルゴリズムを調べて実装してみました。以下の論文。

ref: P. McLeod and G. Wyvill. A smarter way to find pitch

波形から自己相関関数を計算する

自己相関関数とは、波形を時間軸方向にずらしてみて、元の波形とどのくらい一致しているか、という指標。その定義通りに計算すると非効率ですが、不思議な力によって、FFT 2 回で効率的に計算できるそうです。ちなみに Ruby で FFT は

F=proc{|n,t,a|n/=2;r=(0..n-1);n<1?(a):(F[n,t*2,r.map{|i|a[i]+a[i+n]}].zip(F[n,t*2,r.map{|i|(a[i]-a[i+n])*Complex.polar(1,t*i)}]).flatten)}

というように書けます (参考) 。定数オーダの効率はよくないですが、カラオケ判定程度ならぎりぎり実時間でできるようです。(8000 bps で 1024 点ずつ処理。1 秒あたりおよそ 8 * 2 = 16 回くらい FFT してる)

MPM アルゴリズムでは、自己相関関数を基にした Normalized Square Difference Function (NSDF) とかいう関数を使います。-1 から 1 に正規化されているし、インクリメンタルに計算できるし、何かと都合がいい関数のようです。

nsdf = F[N*2,-T,F[N*2,T,w+[0.0]*N].map{|v|v.abs2}].map{|v|v.real/N/2}[0,N].map{|v|v=2*v/m;m-=w[i]**2+w[-i+=1]**2;v}

NSDF のピークを見つける

波形のピッチを求めるには、元の波形とずらした波形の一致度が高いところ、つまり NSDF の値が大きいところを求めればいいわけです。しかし、誤検知を防ぐためのバッドノウハウのところのようで、なかなか dirty になっています。
まず波形を時間軸方向になめていって、値が負から正に入ってから、正から負に落ちるまでの間で、もっとも値の大きなところ (ピーク) を列挙していきます。単純なピーク (微分したら 0 になる地点) ではないことに注意。
さらに、各ピークの前後の値を見て、放物線補完を使ってより正確にピークの時刻・大きさを特定する。
そうして列挙されたピークの中で、最大ピークの大きさの 8 割以上の大きさを持つピークで、一番最初に現れるものを採用します。このピークが現れる時刻 (つまり波長) の逆数が、求めるピッチの周波数。
また、ピークの値の大きさは 0 から 1 に正規化されていて、ピッチ検出の確度として使えます (大きいほど確実) 。
図がないとわからないでしょうね。先の動画や論文を見てください。ソースコードで言うとこの部分。k が波長、v がピークの大きさになります。

nsdf.each_cons(3){|x,y,z|j+=1;x>0&&(0>=y&&(e<<[k*11,h];g<h&&g=h;h=0.0);y-x>0&&z-y<=0&&(d=(x-z)/t=2*(x-2*y+z);(h<c=y-t*d*d/4)&&(k,h=j+d,c)))};k,v=e.find{|i,v|v>g*0.9}

ピッチから音階に直す

音の波長から音階に直すのは、log で計算できます。440Hz がオクターブ 4 のラの音なので

Math.log(440/k,2) * 12

の mod 12 が 0 ならラ、1 ならラ# 、2 ならシ、……、11 ならソ#、という感じです。

まとめ

音声からピッチを検出する MPM アルゴリズムについて、せっかく調べたのでメモがてら簡単に書いてみました。
でも、図なしで説明してもわからないですね。動画の方がいくぶん分かりやすいです。詳しく知りたければ論文みましょう。門外漢にも分かりやすくて self-contained で、4 ページと短いアルゴリズム論文で、すばらしいです。
しかしこんな解説よりデモ動画の方が必要なんだけど、歌声とか公開したくないのだった。誰か歌って。