ウェーブレット変換
ウェーブレット変換（ウェーブレットへんかん、wavelet transformation）は、周波数解析の手法の一つ。基底関数として、ウェーブレット関数を用いる。フーリエ変換によって周波数特性を求める際に失われる時間領域の情報を、この変換においては残すことが可能である。フーリエ変換でも窓関数を用いる窓フーリエ変換で時間領域の情報は残せたが、窓幅を周波数に合わせて固定する必要があるため、広い周波数領域の解析には向かなかった。ウェーブレット変換では、基底関数の拡大縮小を行うので、広い周波数領域の解析が可能である。しかし、不確定性原理によって精度には限界がある。フーリエ変換では、N をデータのサイズとしたときに N logN のオーダーで計算量が増える(O(N logN))が、ウェーブレット変換では O(N) の計算量でできる利点がある。
VP6、JPEG 2000、信号解析、量子力学、フラクタル等の多くの分野に応用されている。
基本概念
基本的には、小さい波（ウェーブレット）を拡大縮小、平行移動して足し合わせることで、与えられた入力の波形を表現しようとする手法。ある信号が与えられた時に、時間的に局在した周波数成分を知りたい場合でも、フーリエ解析においては、サイン波、コサイン波を拡大縮小して足し合わせることで入力を表現しようとしていたが、波が局在化していないため、時系列の情報が失われていた。
フーリエ変換の式<math>(\mathfrak{F} f)(\omega)=\frac{1}{\sqrt{2\pi}}\int dt\, e^{-i\omega t}f(t)</math>に窓を掛け、<math>(T^{win} f)(\omega, t)=\frac{1}{\sqrt{2\pi}}\int ds\, g(s-t)e^{-i\omega s}f(s)</math>とするのがフーリエ変換における局在化の一般的な手法である。この場合、周波数によって窓の幅が変わることがない。そのため、例えば<math>\sin(\alpha t)+\delta (t-t_{1})</math>の様な波を解析しようとした場合、広い窓を取るとサイン波の周波数ははっきりとするが、パルスの波の情報はぼやける。逆に窓を狭くすればパルスの波ははっきりとするが、サイン波の周波数が見えにくくなるといったことがおこる。
ウェーブレット変換では、周波数に合わせてウェーブレットの幅が変化するので、周波数解像度が格段に良くなる。
ウェーブレット変換は連続量を扱う連続ウェーブレット変換が基本だが、計算機上では連続量を扱うのが難しい。このため信号を無理やり連続ウェーブレット変換の式に従って計算すると、かなりの情報が失われ、逆変換ができなくなる。そこで、逆変換を考慮した形のウェーブレット変換を離散ウェーブレット変換という。
連続ウェーブレット変換は逆変換を持たないものの、離散ウェーブレット変換よりも緻密な解析ができるという特徴がある。離散ウェーブレット変換は一度変換した情報を加工して逆変換することで、ノイズの除去などに応用することができる。
連続ウェーブレット変換
ウェーブレットは以下の許容条件を満たす。即ち、<math>\hat{\psi}</math>を<math>\psi</math>のフーリエ変換として、 テンプレート:Indent もし<math>\psi\in L^{1}(\mathbf{R})</math>ならば、そのフーリエ変換<math>\hat{\psi}</math>は連続であり、上の許容条件は<math>\hat{\psi}(0)=0</math>つまり<math>\int dx\,\psi (x)=0</math>の時にのみ満たされる。 この許容条件を満たすウェーブレットに対しウェーブレット変換が以下の様に定義される。 テンプレート:Indent
ここで、<math>a</math>はscale、<math>b</math>はtranslationを表す。<math>\psi(x)</math>を、マザーウェーブレットと言う。
元の関数は、以下の式で得られる。 テンプレート:Indent
例えばウェーブレットにはメキシカンハット関数<math> \psi(t)=(1-t^{2})\exp(-t^2/2)</math>や、 変形ガウシアン<math>\psi(x)=\pi^{-1/4}(e^{-ix\pi(2/\ln2)^{1/2}}-e^{-ix\pi^{2}(2/\ln2)})e^{-x^{2}/2}</math>などがある。
連続ウェーブレット変換は、FFT(高速フーリエ変換)を用いて計算できる。数値計算で連続ウェーブレット変換を求める場合、スケールパラメータ <math> a </math> を変化させながら、マザーウェーブレット <math> \psi(x) </math> と信号 <math> f(x) </math> のフーリエ変換を計算し、畳み込みを計算した後、逆フーリエ変換によって時間領域に戻す事で連続ウェーブレット変換を求める事が出来る。
離散ウェーブレット変換
離散ウェーブレット変換は、元信号を高周波成分と低周波成分に分解し、分解された低周波成分をまた高周波成分と低周波成分に分解するという処理を繰り返し行うことと等価である。そのため多重解像度解析とも呼ばれる。離散ウェーブレット変換は可逆変換であるため、変換そのものに圧縮効果は無いが、変換画像の効率的な符号化方式が開発されたため画像圧縮方式であるJPEG 2000に利用されるようになった。
連続ウェーブレット変換で用いたウェーブレットに対し、 <math>\psi_{m,n}(x)=a_{0}^{-m/2}\psi(a_{0}^{-m}x-nb_{0})</math> として離散化を行う。但し<math>a_{0}>1, b_{0}>0, m\in\mathbf{Z}, n\in\mathbf{Z}</math>とする<math>a_{0}, b_{0}</math>の値はウェーブレットに対して適切に選ぶ事になる。この場合連続ウェーブレット変換と異なり、単位の分解公式を用いる事が出来ないため、別の方法で元の関数を復元する必要がある。
離散ウェーブレット変換例(Haarウェーブレット) テンプレート:Indent をマザーウェーブレットとして用いるならアルゴリズムは
for freq in 適当な範囲:
for pos in データの範囲:
sum = 0
for t in データの範囲:
sum += data[t] * phi((t-pos)/freq)
result[pos][freq] = sum / sqrt(freq)
となるが、tについてのイテレーションに関してphiが明らかに0になる範囲を省くことができるので実際には
for t in range(t-freq, t+freq):
if t < pos:
sum += data[t]
else:
sum -= data[t]
となる。これがフーリエ解析より計算量が少なくて済むことの大きな原因である。（アルゴリズムの解説のための擬似コードであり添え字の範囲チェックなどがないことに注意）
多重解像度解析とウェーブレット変換
閉部分空間の系列<math>\left\{V_{j}:j\in\mathbf{Z}\right\}\sub L^{2}(\mathbf{R})</math>が次の条件(1)～(5)を満たすとき、<math>\left\{ V_{j} \right\}_{j\in\mathbf{Z}}</math>は多重解像度解析を成すという。
(1)<math>V_{j}\sub V_{j+1}, j\in \mathbf{Z}</math>
(2)<math>\cap_{j\in\mathbf{Z}}V_{j}=\{0\}, (\cup_{j\in\mathbf{Z}}V_{j})^{c}=L^{2}(\mathbf{R})</math>但し<math>A^{c}</math>は<math>A</math>の閉包を表す。
(3)<math>f(x)\in V_{j}\Longleftrightarrow f(2x)\in V_{j+1}</math>
(4)<math>f(x)\in V_{0}</math>ならば<math>f(x-k)\in V_{0}, \forall k\in\mathbf{Z}</math>
(5)<math>\phi (x)\in V_{0}</math>が存在して<math>\left\{\phi (x-k):k\in\mathbf{Z}\right\}</math>が<math>V_{0}</math>においてRiesz基底を成す。すなわち、任意の<math>f\in V_{0}</math>に対して数列<math>\left\{a_{k}:k\in\mathbf{Z}\right\}\in l^{2}</math>がただ一つ存在して、<math>f=\sum_{k}a_{k}\phi\left(x-k\right)</math>と表される。さらに定数<math>C_{2}\geq C_{1}>0</math>が存在して、任意の<math>\left\{a_{k}:k\in\mathbf{Z}\right\}\in l^{2}</math>に対して不等式 <math>C_{1}||a||_2\leq\parallel \sum_{j}a_{j}\phi (x-j)\parallel\leq C_{2}||a||_2</math> が成立する。
最後の条件はより厳しい条件として、
(5')<math>\phi (x)\in V_{0}</math>が存在して、<math>\left\{ \phi (x-k):k\in\mathbf{Z}\right\}</math>が<math>V_{0}</math>の正規直交基底となる。
が用いられる事も多い。ここではこの条件(5')を用いる。 条件(1)は空間が入れ子になっていること。条件(2)は<math>P_{j}</math>を空間<math>V_{j}</math>への直交射影作用素とすると、全ての<math>f\in L^{2}(\mathbf{R})</math>に対して<math>\lim _{j\rightarrow \infty}P_{j}f=f</math>であることを意味する。条件(3)は条件(1)の全ての空間がスケール変換で得られる事を意味する。条件(4)は平行移動に対して空間が普遍であることを意味する。
閉部分空間の集まりが条件(1)から(5')を満たすときには、いつでも正規直交ウェーブレット<math>\psi _{j,k}(x)=2^{j/2}\psi (2^{j}x-k)</math>による<math>L^{2}(\mathbf{R})</math>の基底<math>\left\{ \psi _{j,k}:j,k\in\mathbf{Z}\right\}</math>が存在し、
<math>P_{j+1}f=P_{j}f+\sum_{k\in\mathbf{Z}}\left\langle f,\psi _{j,k}\right\rangle \psi_{j,k}</math>が成立するということにある。
正規直交ウェーブレット変換の構成法
(1)Riesz基底を成す<math>\phi</math>を、<math>\phi</math>とそのフーリエ変換が適度に速く減衰し<math>\int dx\, \hat{\phi}(x)\neq 0</math>と成るように取る。
(2)直交化をする。即ち、新たな関数 <math>\hat{\phi ^{\ast}}(\xi)=\hat{\phi}(\xi)\left\{ 2\pi\sum_{l}\mid\hat{\phi}(\xi+2\pi l)\mid^{2}\right\}</math>を作る。
(3)<math>\phi_{j,n}^{\ast}=2^{j/2}\phi^{\ast} (2^{j}x-n)</math>に対し、<math>\phi^{\ast}=\sum_{n}h^{\ast}_{n}\phi^{\ast}_{1,n}</math>を満たす<math>h^{\ast}_{n}</math>を用いて、 <math>\psi=\sum_{n}(-1)^{n}h^{\ast}_{-n+1}\phi ^{\ast}(2x-n)</math>とする。
