多贝西小波

**多貝西小波**（英語：Daubechies Wavelet），是以比利時女性物理暨數學家英格麗・多貝西（Ingrid Daubechies）的名字命名之一種小波函數，當初英格麗・多貝西發現了一種具有階層（hierarchy）性質的小波，便將此小波以她的名字命名。多貝西小波主要應用在離散型的小波轉換，是最常使用到的小波轉換，通常使用在數位信號分析、信號壓縮跟雜訊去除。

一般而言的離散小波轉換通常是以正交小波（orthogonal wavelet）為基底，而多貝西小波也是一種正交小波。由於它很容易經由快速小波轉換（fast wavelet transform（FWT））實現，所以常會放在數位信號處理的教科書中教學。

對於有限長度的小波，應用於快速小波轉換（fast wavelet transform（FWT））時，會有兩個實數組成的數列：一是作為高通濾波器的係數，稱作小波濾波器（wavelet filter, 也稱為 mother wavelet）；二是低通濾波器的係數，稱作調整濾波器（scaling filter, 也稱為 father wavelet）。

我們則以濾波器的長度 N 來形容濾波器為 DN，例如：N=2 的多貝西小波寫作 D2、N=4 的多貝西小波寫作 D4，以此類推（N 為偶數）。實際上常用的多貝西小波為 D2 到 D20。與之對應的另一種描述方式是 db N，其中 N 指消失矩的數量，由此，D4 和 db2 是同一種多貝西小波。

## 性質

* 分類方式

　
: 多貝西小波的分類是以消失動量（vanishing moment）的值 A（亦為消失動量的個數）為依據（A 稱為 tap），調整函式（scaling function）及小波函式（wavelet function）的平滑度（smoothness）皆會隨著消失動量的值（tap）增加而增加：例如，當 A=1 時，多貝西小波即是哈爾小波（Haar wavelet），調整函式及小波函式都是不連續的；當 A=2 時，多貝西小波的調整函式及小波函式為不能平滑微分的連續函式；當 A=3 時，調整函式及小波函式已經是連續可微的函式了。以此類推，當 A 愈大時，多貝西小波的兩個函式平滑度會愈來愈高。以下為多貝西小波跟不同 A 的調整及小波函式圖：
* 長度

　
: 多貝西小波的長度為消失動量（vanishing moment）值 A 的兩倍；所以當消失動量為 A 時，多貝西小波的小波濾波器（wavelet filter）及調整濾波器（scaling filter）長度皆為 2A（N=2A）。一般而言，我們仍是以 N 來形容多貝西小波的長度：例如，當 A=1 時，有一個消失動量，多貝西小波寫成 D2，長度為 2（也是 Haar 小波）；當 A=2 時，有兩個消失動量，多貝西小波寫成 D4，長度為 4；以此類推。但是，在 MATLAB 的使用上是以 dbA 描述多貝西小波，以下則為調整濾波器的係數及 A 的關係表：

## 建立

多貝西小波具有調整函式（低通濾波）及小波函式（高通濾波）兩個函式。因此，我們需先建立調整函式及小波函式的係數:

　
: 首先，調整函數在多尺度分析（multi-resolution analysis）中的每一層皆可寫為下列方程式：

　
: $\phi (x)=\sum _{k=0}^{N-1}a_{k}\phi (2x-k)$ ,

　
: 其中 $(a_{0},\dots ,a_{N-1})$ 為有限長度實數數列，稱作調整係數。同時，小波函數也可以調整函數的線性組合表示：

　
: $\psi (x)=\sum _{k=0}^{M-1}b_{k}\phi (2x-k)$ ,

　
: 其中 $(b_{0},\dots ,b_{M-1})$ 亦為有限長度的實數數列，稱做小波係數。

　
: 因為上述方程式必須是齊性的（homogeneous），在建立上，這兩個函式會正規化（normalize）為和（sum）及平方和（sum of square）皆是 2。

* 正交小波

　
: 正交性質在此指調整係數就必須和位移偶數間隔後的調整係數互相垂直（內積為 0），即為下式：

　
: $\sum _{n\in \mathbb {Z} }a_{n}a_{n+2m}=2\delta _{m,0}$ .
* : 由於正交的特性，小波係數會滿足下列條件：

　
: $b_{n}=(-1)^{n}a_{N-1-n}$ , .
* 消失動量及多項式估計

　
: 常用的多貝西小波為 D2 到 D20，由於多貝西小波的消失動量為有限個，所以調整及小波係數可以表示為有限長度的多項式

　
: $a[n]=a_{n}$

 

* : 上式經過 Z 轉換（Z-transform）後會變成：

　
: ${A}(Z)=a_{0}+a_{1}Z+\dots +a_{N-1}Z^{N-1}$ ,

 

* : 我們可以將上式轉換為正交離散小波轉換的一般表示式

　
: $a(Z)=2^{1-A}(1+Z)^{A}p(Z)$ , $order=A$ ，此時， $p(1)=1$ 、 $p$ 有實係數及 $deg(p)=A-1$ 。

 

* : 而正交的條件可寫成

　
: $a(Z)\,a(Z^{-1})+a(-Z)\,a(-Z^{-1})=4$ , 或是等同於 $(2-X)^{A}P(X)+X^{A}\,P(2-X)=2^{A}\dots $ (#),

　
: $X$ 定義為可以產生對稱數列的勞倫茲多項式 $X:=1/2\cdot (2-Z-Z^{-1})$ 滿足 $X(-Z)=2-X(Z)$
* : 因此 $P(X)$ 便成為對稱型勞倫滋多項式，即 $P(X(Z))=P(Z)P(Z-1)$ 。因為 $X(e^{iw})=1-cos(w)$ 及 $p(e^{iw})p(e^{-iw})=|p(e^{iw})|^{2}$ , ${P}$ 則會是區段 [0,2] 中的非負實數。
* : 方程式（#）如果除上 $X$ 的 truncated power series 則可求得對於每個 $A$ 的最小解

　
: $P_{A}(X)=\sum _{k=0}^{A-1}\left({{A+k-1} \atop {A-1}}\right)2^{-k}X^{k}$ .（明顯的值會是在（0,2）間的正數）
* : 而（#）的齊性方程式是一個對於 $x=1$ 的反對稱方程式，因此可得一般解為 $X^{A}(X-1)R((X-1)^{2})$ ，此一般解有 $R$ 個多項式實係數。

　
: 因此和為

　
: (sum) $P(X)=P_{A}(X)+X^{A}(X-1)R((X-1)^{2})$

　
: ${P}$ 的值在區間 [0,2] 中並有界線（界線為 $4^{A-r}$ ,）。為了將 $r$ 最大化的過程中會產生許多具有不等式條件的線性方程式。

　
: 為了解出 $P(X(Z))=P(Z)P(Z^{-1})$ 的 $P$ ，這裡使用 Fejer-Riesz-algorithm 這個方法（此為頻譜分解的方法）。多項式 $P(X)$ 會因此分開成許多線性因子（linear factor） $P(X)=(X-\mu _{1})\dots (X-\mu _{N})$ , 此時 $N=A+1+2deg(R)$ 。每一個線性因子代表可以分解成兩個線性因子的一個勞倫茲多項式 $(X(Z)-\mu )=-{\frac {1}{2}}Z+1-\mu -{\frac {1}{2}}Z^{-1}$ ，任選其中一個線性因子都可設為 $p(Z)$ 。所以 $p(Z)$ 會有 2N 個可能的答案。為了極端相位的目的，挑選所有根都是在單位圓上或是在單位圓內複數根的 $P(Z)$ 。

## 演算法

以下為示範小波轉換應用於影像壓縮，壓縮後為原本圖片的四分之一。

假設輸入的圖片大小為 M\*N，讓圖片對高頻和低頻進行卷積運算。

對 M 的基數進行取樣，這個結果會讓兩個維度都變成 (M/2)\*N。

把低頻的圖片放在上面，高頻的放在下面，低頻的圖片會長的像原本的圖片，高頻的圖片會是只有灰色的圖片。

對新的圖片再進行高頻和低頻的卷積，這時變成 M\*(N/2) 的大小，低頻放在左邊，高頻放在右邊，

最後可以看到 [0:M/2, 0:N/2] 就會是原本壓縮過後的圖片。

因小波轉換有良好的性質，經過多次壓縮還是能保有原本的資訊。也就是說可以修改以下的程式碼改成迴圈的方式，

進行多次小波轉換，經過類似的模式再使用多次的反小波轉換，還原出原本大小的圖片。

## 參照

* 小波分析

## 參考資料

1. A first course in Wavelets with Fourier Analysis, A.Boggess, F.J. Narcowich, 2001