在数值分析和泛函分析领域中，离散小波变换（Discrete Wavelet Transform，DWT）是小波被离散采样的小波变换。与其他小波变换一样，它与傅里叶变换相比的一个关键优势是时间分辨率：它既能捕获频率信息，又能捕获位置（时间上的位置）信息。

第一個離散小波變換由匈牙利數學家哈尔發明，離散小波轉換顧名思義就是離散的輸入以及離散的輸出，但是這裡並沒有一個簡單而明確的公式來表示輸入及輸出的關係，只能以階層式架構來表示。

定義
*首先我們定義一些需要用到的信號及濾波器。
*x[n]：離散的輸入信號，長度為N。
*g[n]：低通濾波器（low pass filter），可以將輸入信號的高頻部份濾掉而輸出低頻部份。
*h[n]：高通濾波器（high pass filter），與低通濾波器相反，濾掉低頻部份而輸出高頻部份。

\downarrow Q：降采样濾波器（downsampling filter），如果以x[n]作為输入，則輸出y[n]=x[Qn]。此處舉例Q=2。

::舉例說明:
:清楚規定以上符號之後，便可以利用階層架構來介紹如何將一個離散信號作離散小波轉換：
::
:架構中的第1層(1st stage)

: x_{1,L}[n]=\sum_{k=0}^{K-1} x[2n-k]g[k]
: x_{1,H}[n]=\sum_{k=0}^{K-1} x[2n-k]h[k]

:架構中的第2層(2nd stage)
: x_{2,L}[n]=\sum_{k=0}^{K-1} x_{1,L}[2n-k]g[k]

: x_{2,H}[n]=\sum_{k=0}^{K-1} x_{1,L}[2n-k]h[k]

:可繼續延伸

:: \vdots

架構中的第 \alpha 層( \alpha -th stage)
: x_{\alpha ,L}[n]=\sum_{k=0}^{K-1} x_{\alpha -1,L}[2n-k]g[k]

: x_{\alpha ,H}[n]=\sum_{k=0}^{K-1} x_{\alpha -1,L}[2n-k]h[k]

二維離散小波轉換
::

:此時的輸入信號變成 x[m,n] ，而轉換過程變得更複雜，說明如下：
::首先對n方向作高通、低通以及降頻的處理

: v_{1,L}[m,n]=\sum_{k=0}^{K-1} x[m,2n-k]g[k]
: v_{1,H}[m,n]=\sum_{k=0}^{K-1} x[m,2n-k]h[k]
::接著對 v_{1,L}[m,n]與 v_{1,H}[m,n]延著m方向作高低通及降頻動作
: x_{1,LL}[m,n]=\sum_{k=0}^{K-1} v_{1,L}[2m-k,n]g[k]
: x_{1,HL}[m,n]=\sum_{k=0}^{K-1} v_{1,L}[2m-k,n]h[k]
: x_{1,LH}[m,n]=\sum_{k=0}^{K-1} v_{1,H}[2m-k,n]g[k]
: x_{1,HH}[m,n]=\sum_{k=0}^{K-1} v_{1,H}[2m-k,n]h[k]
::經過(1)(2)兩個步驟才算完成2-D DWT的一個stage。

實際範例
以下根據上述2-D DWT的步驟，對一張影像作二維離散小波轉換(2D Discrete Wavelet Transform)
:原始影像
:2D DWT的結果
:\Rightarrow

複雜度(Complexity)
在討論複雜度之前，先做一些定義，當x[n]*y[n]時，x[n]之長度為N，y[n]之長度為L：
\ \Rightarrow
IDFT_{N+L-1}\left[ DFT_{N+L-1}(x[n]) DFT_{N+L-1}(y[n])\right]

其中，

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

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

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

\frac{3}{2}(N+L-1)\log_{2} {(N+L-1)}\approx \frac{3}{2} N \log_{2} N

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

將x[n]切成很多段，每段長度為\N_1，總共會有S=\frac{N}{N_1}段，其中N>N_1>>L。

則

\ x[n]g[n]=x_1 [n]g[n]+x_2 [n]g[n]+...+x_s [n]g[n]

\ x[n]h[n]=x_1 [n]h[n]+x_2 [n]h[n]+...+x_s [n]h[n]

複雜度為：

\begin{align}
\frac{3}{2} S(N_1 +L-1)\log_{2} {(N_1 +L-1)} & \approx \frac{3}{2} SN_1 \log_{2} (N_1 +L-1) \\
& \approx \frac{3}{2} N \log_{2} (N_1 +L-1)\\
& \approx \frac{3}{2} N \log_{2} N_1\\
\end{align}

在這裡要注意的是，當N>>L時，一維離散小波轉換之複雜度是呈線性的(隨N)，\mathit{O(N)}。

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

1.若\ x_{a,H} [n]不再分解時：

\begin{align}
Complexity & \approx \left( N+\frac{N}{2}+\frac{N}{4}+\frac{N}{8}+...+2 \right)\frac{3}{2} \log_{2} N_1\\
& = (2N-2)\frac{3}{2} \log_{2}N_1\\
& \approx 3N\log_{2} N_1\\
\end{align}

2.若\ x_{a,H} [n]也細分時：

\begin{align}
Complexity & \approx \left( N+2\frac{N}{2}+4\frac{N}{4}+8\frac{N}{8}+...+\frac{N}{2} 2 \right)\frac{3}{2} \log_{2} N_1\\
& = (N\log_{2} N)\frac{3}{2} \log_{2} N_1\\
\end{align}

(4)二維離散小波轉換之複雜度(沒有分段卷积(sectioned convolution))：
\ \Rightarrow
M \frac{3}{2}(N+L-1)\log_{2} {(N+L-1)}+ (N+L-1)\frac{3}{2}(M+L-1)\log_{2} {(M+L-1)}

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

\begin{align}
Complexity & \approx \frac{3}{2}MN\log_{2} N+\frac{3}{2}MN\log_{2} M\\
& = \frac{3}{2}MN(\log_{2} N+\log_{2} M)\\
& = \frac{3}{2}MN\log_{2} MN\\
\end{align}

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

假設原始尺寸為 M \times N ，則每一小部分的尺寸為 M_1 \times N_1

\begin{align}
Complexity & \approx \frac{MN}{M_1 N_1} \frac{3}{2} M_1 N_1 \log_{2} M_1 N_1\\
& = \frac{3}{2} M N \log_{2} M_1 N_1\\
\end{align}

所以若是使用分段摺積，則二維離散小波轉換之複雜度是呈線性的(隨MN)，\mathit{O(MN)}。

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

首先x[m,n]的尺寸為 M \times N ，

1.若\ x_{a,H_1} [n] ,x_{a,H_2} [n],x_{a,H_3} [n]不細分，只細分\ x_{a,L} [n]時，總複雜度為：

\begin{align}
total complexity & = \left( MN+\frac{MN}{4}+\frac{MN}{16}+... \right)\frac{3}{2}\log_{2} M_1 N_1 \\
& \approx \frac{4}{3} MN \frac{3}{2} \log_{2} M_1 N_1\\
& =2MN\log_{2} M_1 N_1\\
\end{align}

2.若\ x_{a,H_1} [n] ,x_{a,H_2} [n],x_{a,H_3} [n]也細分時，總複雜度為：

\begin{align}
total complexity & = \left( MN+4\frac{M}{2}\frac{N}{2}+16\frac{M}{4}\frac{N}{4}+... \right)\frac{3}{2} \log_{2} M_1 N_1 \\
& = \left[ MN\log_{2}(min(M,N)) \right] \frac{3}{2} \log_{2} M_1 N_1\\
\end{align}

重建(Reconstruction)
使用離散小波轉換，將訊號個別通過一個低通濾波器和一個高通濾波器，得到訊號的高低頻成分，而在重建()原始訊號的過程，也就是離散小波的逆轉換(Inverse Discrete Wavelet Transform. IDWT)，直觀而言，我們僅是需要將離散小波轉換做重建濾波即可得到原始輸入信號，以下將推導重建濾波器，也就是IDWT高低通濾波器的構成要件，以及如何來重建原始信號。

重建過程如下：
使用Z轉換：
X(z) = \sum x(n)z^{-n}

DWT低通濾波器 g(n) 的Z轉換為 G(z) ，DWT高通濾波器h(n)的Z轉換為H(z)

信號x(n)通過濾波器 g(n) 後，Z轉換為 X(z)G(z) ，信號x(n)通過濾波器 h(n) 後，Z轉換為 X(z)H(z)

降低採樣數(downsample)2倍後，

X_{1,L}(z) = \frac{1}{2}[X(z^\frac{1}{2})G(z^\frac{1}{2})+X(-z^\frac{1}{2})G(-z^\frac{1}{2})]

X_{1,H}(z) = \frac{1}{2}[X(z^\frac{1}{2})H(z^\frac{1}{2})+X(-z^\frac{1}{2})H(-z^\frac{1}{2})]

升頻(interpolation)2倍後，再通過IDWT的低通重建濾波器 g_1(n) ，

X_0(z) = \tfrac{1}{2}[X(z)G(z) + X(-z)G(-z)]G_1(z) + \tfrac{1}{2}[X(z)H(z) + X(-z)H(-z)]H_1(z)

=\tfrac{1}{2}[G(z)G_1(z)+H(z)H_1(z)]X(z)+\tfrac{1}{2}[G(-z)G_1(z)+H(-z)H_1(z)]X(-z)
若要完整重建，則X_0(z) = X(z)
條件1：G(z)G_1(z)+H(z)H_1(z) =2

條件2：G(-z)G_1(z)+H(-z)H_1(z) =0
因此，在設計高低通重建濾波器時，需要考慮上述條件，寫成矩陣形式如下：
\binom{G_1(z)}{H_1(z)}=\frac{2}{det(H_m(z))}\binom{H(-z)}{-G(-z)}

其中 det(H_m(z)) = G(z)H(-z)-H(z)G(-z)

離散小波轉換(DWT)設計
四大條件：
1.DWT通濾波器 g(n)，h(n)必須要是有限長度。

2.滿足h(n)是高通濾波器(high pass filter)，g(n)是低通濾波器(low pass filter)。

3.滿足完整重建要條件，\binom{G_1(z)}{H_1(z)}=\frac{2}{det(H_m(z))}\binom{H(-z)}{-G(-z)}，其中 det(H_m(z)) = G(z)H(-z)-H(z)G(-z)

4.若g(n)，h(n)為有限長度，則det(H_m(z)) = G(z)H(-z)-H(z)G(-z) = \alpha z^k ，且 k 為奇數。

第4點較難達成，是DWT設計的核心

*為什麼k是奇數？

假設k为偶数，

z=-1

det(H_m(-1)) = G(-1)H(1)-H(-1)G(1) = \alpha (-1)^k = 1

z=1

det(H_m(1)) = G(1)H(-1)-H(1)G(-1) = \alpha (1)^k = 1

G(1)H(-1)-H(1)G(-1) = G(-1)H(1)-H(-1)G(1)

H(1)G(-1) = G(1)H(-1)

代回

det(H_m(-1)) = G(-1)H(1)-H(-1)G(1) = 0

顯然出現矛盾。

所以k必須為奇数。

以下介紹兩種完美重建的DWT濾波器：
1.正交镜象滤波器（Quadrature Mirror Filter，QMF）

H(z)=G(-z)

\Longrightarrow h(n) = (-1)^ng(n)

G_1(z) = G(z)z^{-k}

\Longrightarrow g_1(n)=g(n-k)

H_1(z) = -G(-z)z^{-k}

\Longrightarrow h_1(n) = (-1)^{n-k+1}g(n-k)

det(H_m(z)) = G(z)H(-z)-H(z)G(-z) = 2 z^k，且 k 為奇數。

2.单位正交小波（Orthonormal Wavelet）

G(z)=G_1(z^{-1})

\Longrightarrow g(n) = g_1(-n)

H(z)=-z^kG_1(-z)

\Longrightarrow h(n) = (-1)^ng_1(n+k)

H_1(z)=-z^kG_1(-z^{-1})

\Longrightarrow h_1(n) = (-1)^ng_1(-n+k)

det(H_m(z)) = G(z)H(-z)-H(z)G(-z) = 2 z^k，且 k 為奇數。

多數小波屬於单位正交小波。

常見的小波族
在離散小波轉換中，選擇合適的小波基底（Mother Wavelet）對於分析結果至關重要。常見的小波族包括：

Daubechies 小波
由英格麗·道貝希（Ingrid Daubechies）提出，是最常用的正交小波族。

特性：

** 具有緊支撐（Compact Support）特性，即在有限區間外為零。
** 隨著階數 N 增加（dbN），其消失矩（Vanishing Moments）增加（為 N），平滑度也隨之增加。
缺點：除了 Haar 小波（db1）外，Daubechies 小波均為非對稱**的，這會導致信號處理時產生相位失真（Phase Distortion）。

Symlet
Daubechies 小波的改良版本，全名為 Symmlet（Symmetrical Wavelet）。

特性：

** 針對 Daubechies 小波非對稱的缺點進行改良，設計上盡可能接近對稱（Least Asymmetric）。
** 保留了正交性與緊支撐特性，且擁有與同階數 Daubechies 小波相同的消失矩數量。
** 由於其良好的對稱性，在影像處理與降噪應用中通常表現優於 Daubechies 小波。

Coiflet
由 Ronald Coifman 提出。

特性：

** 其特點在於 Scaling Function 與 Mother Wavelet 函數皆具有消失矩。
** 這使得 Coiflet 在數值分析（如積分運算）中具有更高的精確度。
** 代價是其支撐範圍（Support Width）比同階數的 Daubechies 小波更長，運算量稍大。

雙正交小波 (Biorthogonal Wavelet)
與上述的正交小波不同，雙正交小波使用兩組不同的濾波器進行分解（Analysis）與合成（Synthesis）。

特性：

** 解除了正交小波「不可同時具備對稱性與緊支撐」的限制。
可以設計出具有線性相位（Linear Phase）**的濾波器，這對於影像壓縮至關重要，因為它可以避免邊緣的相位扭曲。
著名的 CDF 9/7 與 CDF 5/3** 小波即屬於此類，被廣泛應用於 JPEG 2000 標準中。

其他應用

壓縮、去除雜訊：使用低通濾波器，將小波轉換的高頻濾掉，即保留 x_{1,LL}[m,n] 而將其他部分捨棄。
邊緣偵測：使用高通濾波器，將小波的低頻濾掉，即保留 x_{1,HL}[m,n] 或 x_{1,LH}[m,n] 而捨棄其他部分。
模式辨認：由於可以利用低頻的部分得到原圖的縮略版，加上模式通常為整體的特性，藉由在縮略圖上進行工作，小波轉換可以有效減少尋找模式與比對模式的運算時間。
濾波器設計：小波轉換保留部分時間資訊，可以據此資訊加上訊號的強度資訊，保留特定時點的資訊而同時去除雜訊。
[http://wenku.baidu.com/view/cd757ded6294dd88d0d26ba8.html R语言小波分析wavelet]

JPEG 2000
JPEG 2000 是一個包含無失真壓縮與失真壓縮的影像壓縮標準，其核心技術採用了離散小波轉換（DWT），而非傳統 JPEG 所使用的離散餘弦轉換（DCT）。

核心優勢
相比於傳統 JPEG，JPEG 2000 具有以下優勢：

無區塊效應（No Blocking Effect）：傳統 JPEG 將影像切割為 8x8 的區塊進行 DCT 轉換，在高壓縮率下會產生明顯的方格狀邊緣。JPEG 2000 使用全域或大區塊的 DWT，避免了此問題。
高壓縮品質：在相同的壓縮率下，JPEG 2000 的峰值信噪比（PSNR）通常優於 JPEG。特別是在高壓縮率（例如壓縮比 80:1）的情況下，JPEG 2000 仍能重建出品質不錯的影像。
支援多解析度：DWT 的金字塔結構使得影像可以被解碼為不同解析度的版本，方便縮圖預覽或分層傳輸。

編碼架構
JPEG 2000 的編碼流程包含以下步驟：

前處理：將影像色彩空間由 RGB 轉換為 YCbCr，並可能進行降取樣（如 4:2:0）。

離散小波轉換（DWT）：將影像分解為多個頻帶（Subbands）。

量子化（Quantization）：對小波係數進行量子化。

Tier 1 編碼：包含分數位元平面編碼（Fractional Bit-plane Coding）、零編碼（Zero Coding）、符號編碼（Sign Coding）與遊程編碼（Run Length Coding）。

Tier 2 編碼：負責組織碼流（Bitstream）並控制檔案大小，例如決定要截斷哪些較不重要的資料以符合目標位元率。

進階變形與發展
傳統的二維離散小波轉換（2D DWT）是藉由張量積（Tensor Product）將一維小波推廣到二維，因此它只有水平、垂直與對角線三個方向的特徵提取能力。這導致其在處理影像中的平滑曲線邊緣（Smooth Curves）時效率不佳，容易產生點狀雜訊。為了改善此問題，學者提出了多種具備「方向性」的新型轉換。

Contourlet 轉換
由 Minh N. Do 和 Martin Vetterli 提出。Contourlet 轉換是一種能有效捕捉影像中平滑輪廓（Contours）的「方向性多解析度」轉換。

架構：它結合了拉普拉斯金字塔（Laplacian Pyramid）用於捕捉點奇異點（Point Singularities），以及方向濾波器組（Directional Filter Banks, DFB）將奇異點連結成線性結構。
特點：具有各向異性（Anisotropy）與多方向性，能以比 DWT 更稀疏的方式表示包含平滑曲線的影像（如指紋、紋理）。

Bandlet 轉換
由和加布里埃爾·佩雷提出。Bandlet 轉換是一種「幾何自適應」的轉換方法。

原理：它不使用固定的濾波器方向，而是根據影像局部的幾何流（Geometric Flow）或紋理方向，動態調整小波基底的扭曲（Warping）方向。
特點：能夠「順著」邊緣的方向進行濾波，從而在邊緣處獲得極佳的稀疏表示，特別適合處理具有複雜幾何紋理的自然影像。

同時參閱
*小波分析
*連續小波轉換
*哈爾小波轉換
*信號處理
參考

Jian-Jiun Ding, Time frequency analysis and wavelet transform class notes, the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2025.

*Jian-Jiun Ding, Time frequency analysis and wavelet transform class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2009,2016 .[http://djj.ee.ntu.edu.tw/TFW.htm http://djj.ee.ntu.edu.tw/TFW.htm]
*Stéphane Mallat, [http://books.google.com/books?vid=ISBN012466606X&id=yW2kut44AsMC&dq=Wavelet+tour+of+signal+processing A Wavelet Tour of Signal Processing]

Wavelet-Transformation#Diskrete Wavelet-Transformation
Ondelette#Transformée en ondelettes discrète

離散小波變換