FFTを使った連続ウェーブレット変換の高速化

Oct 20, 2013 0 min read

そもそもウェーブレット変換って何

Jump to wikipedia

いわゆる時間周波数解析の手法の一つで、音声、音楽、画像の解析に使われる。直感的には、STFTでいう窓関数の幅を周波数に応じて拡大・伸縮させて、時間変化する信号の特徴を上手く捉えようとする手法のこと

高速化の仕組み

さて、本題。ウェーブレット変換は、(スケールパラメータを固定すれば)入力信号とマザーウェーブレットのたたみ込みで表されるので、たたみ込み定理よりフーリエ変換を使った計算方法が存在する。

つまり、

  • 入力信号とマザーウェーブレットをそれぞれフーリエ変換する
  • 掛け算する
  • 逆フーリエ変換する

というプロセスでウェーブレット変換を求めることができて、かつフーリエ変換にはFFTという高速なアルゴリズムが存在するので、計算を高速化できるという仕組み。まぁ原理としてはシンプルなんだけど以外と面倒くさい（気のせい？）。

色々調べたので、メモ代わりにまとめておく。解説ではなくリンク集です

Torrence, C. and G.P. Compo “A Practical Guide to Wavelet Analysis”, Bull. Am. Meteorol. Soc., 79, 61–78, 1998.

結論から言えばここが一番わかりやすかった。

  • 実装よりで理論の解説がある
  • matlab/fortran のコードがある

がいいところ

基本的にはこれ読めばわかる。数学全然わからん俺でも読めた。特に、離散表現でのウェーブレットについても書かれているのは良い。連続ウェーブレットといっても、デジタル信号処理で扱う上では離散化しないといけないわけなので

さて、僕が参考にしたmatlabコードへの直リンクは以下

その他、fortanコードなどいくつかあるので、それらはウェブサイトからどうぞ

Matlab

mathworksさんのwavelet toolboxのドキュメントもよかった。ここから上記のpracticalなんちゃらのリンクもある

コードは転がってないですね。まぁ有料なので

日本語でわかりやすいもの

書籍

今回は調べてない。数年前にちょいちょい調べたことがあるけど忘れた

その他

さいごに

以上。ウェーブレット変換は難しいことがわかった（こなみ）。ウェーブレットの利点欠点については書かなかったけれど、音声や音楽を解析したい場合に、時間周波数解析によく用いられる短時間フーリエ解析よりもウェーブレット解析の方が望ましい場合は非常によくあると思っているので、ぜひもっと使われてほしいですね。作ってるライブラリには必ず入れます。

ちなみに

計算コストがそこまでボトルネックにならないなら、畳み込みでウェーブレット計算してもいいんじゃないかと思ってる。FFTを使う方法の場合、あるスケールパラメータに対する時間方向のウェーブレット変換係数を一気に求められても、あるシフトパラメータに対する周波数方向のウェーブレット変換係数（つまりある時間でのスペクトルのようなもの）は一気に求められない気がしている。つまり、STFTみたいな形でインクリメンタルにスペクトルは求めにくいんじゃないかってこと（少なくとも自明には思えない）。畳み込み計算するなら、間違いなくできるけど。このあたり理解がまだあやふやなので、間違ってる可能性大

さらにちなみに、僕が作ってたリアルタイムで動く自動伴奏システムは畳み込みでウェーブレット変換してたよ。ウェーブレットよりもアルゴリズムのほうがボトルネックになっていたので全然気にならなかった。参考まで

Signal Processing Wavelett Transform Continuous Wavelet Transform FFT
Ryuichi Yamamoto
Ryuichi Yamamoto
Engineer/Researcher

I am a engineer/researcher passionate about speech synthesis. I love to write code and enjoy open-source collaboration on GitHub. Please feel free to reach out on Twitter and GitHub.

Related