離散ウェーブレット変換

ウィキペディア

離散ウェーブレット変換

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/03/28 03:42 UTC 版)

離散ウェーブレット変換（りさんウェーブレットへんかん、英: Discrete wavelet transform, DWT）は、数値解析や関数解析において、離散的にサンプリングされたウェーブレットを用いたウェーブレット変換のアルゴリズムである。本来は異なる物だが、多くのソフトウェアでは多重解像度解析の事を離散ウェーブレット変換と呼んでいる。本項では本来の定義の方をふれ、多重解像度解析に関してはそちらの項目を参照。

概要

最初の離散ウェーブレット変換は、ハンガリーの数学者アルフレッド・ハールによって示された。ハールウェーブレットによる多重解像度解析は、 $2^{n}$ の長さを持つ数列が入力されると、隣接した値の差分と和を求めるものである。この処理は再帰的に行われ、和の数列は次の処理の入力となる。最終的には、 $2^{n}-1$ の差分値と一つの和の値を得る。

この単純な離散ウェーブレット変換は、ウェーブレットの一般的な特性を示している。多重解像度解析の計算量は $O(n)$である。また、この変換は、時間及び周波数の両方の特性をつかむことができる。これら2つの特徴は、高速フーリエ変換と比較した場合の多重解像度解析の大きな特徴である。

もっとも一般的な離散ウェーブレット変換は、ベルギーの数学者イングリッド・ドブシーによって1988年に証明された。この証明では、解像度が以前のスケールの2倍となっていく漸化式によって、もっとも密にサンプリングされたマザーウェーブレットを生成している。彼女の講義資料には、ドブシーウェーブレットと呼ばれるウェーブレットファミリーが提供されており、その中の最古のウェーブレットはハールウェーブレットである。このあと、これをベースとした多くのウェーブレットが開発された。

離散ウェーブレット変換の別の表現としては、定常ウェーブレット変換 （ダウンサンプリングが無い離散ウェーブレット変換）がある。また、関連した変換としては、ウェーブレットパケットや複素ウェーブレット変換がある。

離散ウェーブレット変換は、科学・工学・数学・計算機科学の分野で数多くの応用が存在する。 顕著な例としては、信号符号化やデータ圧縮などに用いられる。特に画像圧縮に対してはモスキートノイズが理論上ほとんど発生しないため、JPEG 2000のアルゴリズムにも採用されている。

本来の定義

本来の f(t) に対する離散ウェーブレット変換の定義は、連続ウェーブレット変換の解像度を2倍刻みにした、下記の形である。 $\psi (t)$ はウェーブレット関数。j と k は整数。

$d_{k}^{(j)}=2^{j}\int _{\mathbf {R} }f(t){\overline {\psi (2^{j}t-k)}}dt$

逆離散ウェーブレット変換は以下の形である。

$f(t)=\sum _{j}\sum _{k}d_{k}^{(j)}\psi (2^{j}t-k)$

しかしながら、これが使われる事は少なく、多重解像度解析が使われる事が一般的である。Mathematica や MATLAB をはじめとして、多くのソフトウェアでは、多重解像度解析の事を離散ウェーブレット変換と呼ぶ。多重解像度解析の詳細については、そちらの項目を参照。

参照

• Stéphane Mallat, A Wavelet Tour of Signal Processing (ISBN 9780124666061)

関連項目

• 多重解像度解析
• ウェーブレット
• ウェーブレット変換
• 直交ミラーフィルタ
• en:List of wavelet-related transforms

ウィキペディア小見出し辞書

離散ウェーブレット変換（パターンマッチング）

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/03/19 03:24 UTC 版)

「Standard ML」の記事における「離散ウェーブレット変換（パターンマッチング）」の解説

2の整数乗の長さの数列の1次元離散ウェーブレット変換はSMLでは簡単に実装でき、リスト上のパターンマッチの好例となっている。リストの先頭から2つの要素 （"h1" と "h2"）を取り出し、その総和をリスト "s" に、差分をリスト"d" に格納する。 - fun haar l = let fun aux [s] [] d = s :: d | aux [] s d = aux s [] d | aux (h1::h2::t) s d = aux t (h1 + h2 :: s) (h1 - h2 :: d) | aux _ _ _ = raise Empty in aux l [] [] end; val haar = fn : int list -> int list 実行例は次の通り。 - haar [1, 2, 3, 4, ~4, ~3, ~2, ~1]; val it = [0,20,4,4,~1,~1,~1,~1] : int list パターンマッチは複雑な変換を明確かつ簡潔に表現できる。さらに、SMLコンパイラはパターンマッチに最適化したコードを生成するので、単にコードが簡潔になるだけでなく高速である。