本页使用了标题或全文手工转换

離散小波變換

维基百科,自由的百科全书
(重定向自离散小波变换
跳转至: 导航搜索

離散小波變換(Discrete Wavelet Transform)在數值分析和時頻分析中很有用。第一個離散小波變換由匈牙利數學家發明,離散小波轉換顧名思義就是離散的輸入以及離散的輸出,但是這裡並沒有一個簡單而明確的公式來表示輸入及輸出的關係,只能以階層式架構來表示。

定義[编辑]

  • 首先我們定義一些需要用到的信號及濾波器。
  • x[n]:離散的輸入信號,长度为N。
  • :low pass filter低通濾波器,可以將輸入信號的高頻部份濾掉而輸出低頻部份。
  • :high pass filter高通濾波器,與低通濾波器相反,濾掉低頻部份而輸出高頻部份。
  • Q:downsampling filter降采样濾波器,如果以x[n]作為输入,則輸出y[n]=x[Qn]。此處舉例Q=2。
舉例說明:DiscreteWaveletTrans1.jpg
清楚規定以上符號之後,便可以利用階層架構來介紹如何將一個離散信號作離散小波轉換:
DWT2ndLayer.jpg
架構中的第1層(1st stage)
架構中的第2層(2nd stage)


可繼續延伸

Wavelets - Filter Bank.png



架構中的第層( stage)


注意:若輸入信號的長度是N,則第層中的的長度為

二维离散小波转换[编辑]

2D DWT.jpg
此時的輸入信號變成,而轉換過程變得更複雜,說明如下:
首先對n方向作高通、低通以及降頻的處理
接著對延著m方向作高低通及降頻動作
經過(1)(2)兩個步驟才算完成2-D DWT的一個stage。


實際範例[编辑]

以下根據上述2-D DWT的步驟,對一張影像作二維離散小波轉換(2D Discrete Wavelet Transform)

原始影像2D DWT Original.png
2D DWT的結果2D DWT pre-process.png
2D DWT process.png

複雜度(Complexity)[编辑]

在討論複雜度之前,先做一些定義,當x[n]*y[n]時,x[n]之長度為N,y[n]之長度為L:

其中,

為(N+L-1)點離散傅立葉反轉換(inverse discrete Fourier transform)

為(N+L-1)點離散傅立葉轉換(discrete Fourier transform)

(1)一維離散小波轉換之複雜度(沒有分段卷积(sectioned convolution)):

(2)當 N >>> L 時,使用 “分段卷积(sectioned convolution)”的技巧:

將x[n]切成很多段,每段長度為,總共會有段,其中

複雜度為:

在這裡要注意的是,當N>>L時,一維離散小波轉換之複雜度是呈線性的(隨N),

(3)多層(Multiple stages )的情況下:

1.若不再分解時:

2.若也細分時:

(4)二維離散小波轉換之複雜度(沒有分段卷积(sectioned convolution)):

上式中,第一部分需要M個一維離散小波轉換並且每個一維離散小波轉換的輸入有N個點;第二部分需要N+L-1個一維離散小波轉換並且每個一維離散小波轉換的輸入有M個點。

(5)二維離散小波轉換之複雜度,使用 “分段卷积(sectioned convolution)”的技巧:

假設原始尺寸為,則每一小部分的尺寸為

所以若是使用分段摺積,則二維離散小波轉換之複雜度是呈線性的(隨MN),

(6)多層(Multiple stages )與二維的情況下:

首先x[m,n]的尺寸為

1.若不細分,只細分時,總複雜度為:

2.若也細分時,總複雜度為:

其他應用[编辑]

  • 壓縮、去除雜訊:使用低通濾波器,將小波轉換的高頻濾掉,即保留而將其他部分捨棄。
  • 邊緣偵測:使用高通濾波器,將小波的低頻濾掉,即保留而捨棄其他部分。
  • R语言小波分析wavelet
  • 作為 JPEG2000 的內部架構
  • 模式辨認:由於可以利用低頻的部分得到原圖的縮略版,加上模式通常為整體的特性,藉由在縮略圖上進行工作,小波轉換可以有效減少尋找模式與比對模式的運算時間
  • 濾波器設計:小波轉換保留部分時間資訊,可以據此資訊加上訊號的強度資訊,保留特定時點的資訊而同時去除雜訊

同時參閱[编辑]

參考[编辑]