小波變換[4] -- 計算問題

2022-01-14 15:20 作者:nyasyamorina 0人讀過 | 我要投稿

函數(shù)近似

在第二篇專欄里提到過多分辨率框架下信號的分解和重構(gòu),? 可以看到這兩個步驟都只與尺度系數(shù) {p?} 有關(guān),? 而于尺度函數(shù)和小波函數(shù)的具體形式無關(guān).? 但是在特定場合,? 比如說可視化或者誤差評估的時候,? 則需要用到尺度函數(shù)的形狀了,? 下面介紹兩種逐漸收斂得到尺度函數(shù)的方法.

第一種??是由迭代式? $%5CPhi_%7Bn%2B1%7D(x)%3D%5Csum_%7Bk%5Cin%5Cmathbb%20Z%7Dp_k%5CPhi_n(2x-k)$ 給出.? 不斷應(yīng)用這個迭代式,? 可以有? $%5CPhi_n(x)%3D%5Csum_%7Bk%5Cin%5Cmathbb%20Z%7Dc%5E%7B(n)%7D_k%5CPhi_0(2%5Enx-k)$ ,? 由尺度函數(shù)的標(biāo)準(zhǔn)正交性可以知道? $c%5E%7B(0)%7D_k%3D%5Cdelta_%7B0%2Ck%7D$ ,? 由定義得? $c%5E%7B(1)%7D_k%3Dp_k$ .? 結(jié)合兩式:?? $%5CPhi_%7Bn%2B1%7D(x)%3D%5Csum_%7Bk%5Cin%5Cmathbb%20Z%7Dp_k%5Csum_%7Bl%5Cin%5Cmathbb%20Z%7Dc%5E%7B(n)%7D_l%5CPhi_0(2%5E%7Bn%2B1%7Dx-2%5Enk-l)$ ,? 使用?l-2?k?代替 l,? 交換 k?和 l?的累加順序后,? 得到? $%5Csum_%7Bl%5Cin%5Cmathbb%20Z%7D%5CPhi_0(2%5E%7Bn%2B1%7Dx-l)%5Csum_%7Bk%5Cin%5Cmathbb%20Z%7Dp_kc%5E%7B(n)%7D_%7Bl-2%5Enk%7D$ ,? 亦即? $c%5E%7B(n%2B1)%7D_l%3D%5Csum_%7Bk%5Cin%5Cmathbb%20Z%7Dp_kc%5E%7B(n)%7D_%7Bl-2%5Enk%7D$ .? 如果選取 Φ? 為 Haar,? 可以有? $%5CPhi_n(x)%3Dc%5E%7B(n)%7D_%7B%5Clfloor2%5Enx%5Crfloor%7D$ .

第二種??是由尺度關(guān)系式? $%5CPhi(x)%3D%5Csum_%7Bk%5Cin%5Cmathbb%20Z%7Dp_k%5CPhi(2x-k)$ ?推導(dǎo)二進(jìn)制點的值得出.? 因為 N 階 D-小波的支撐集在 (0,2N-1) 里,? 所以僅在整數(shù) x = 1, ..., 2N-2 上有可能不為零.? 記整數(shù)點上 Φ 的值為向量形式? $%5Cvec%20v%3D%5Cleft%5B%5Cbegin%7Bmatrix%7D%5CPhi(1)%26%5CPhi(2)%26%5Ccdots%26%5CPhi(2N-2)%5Cend%7Bmatrix%7D%5Cright%5D%5ET$ ,? 那么尺度關(guān)系式可以看作矩陣作用在向量上,? 稍加推導(dǎo)可以得出相應(yīng)的矩陣為? $%5Chat%20P_%7Ba%2Cb%7D%3Dp_%7B2a-b%7D$ ,? 亦即尺度關(guān)系式變?yōu)?P?v = v.? 由此可以解得?P? 特征值為 1 的特征向量 [實際上可以證得 P? 特征值為 1 的特征向量存在且只有一個,? 但是不太會線代就摸了],? 并且因為 D-小波滿足? $%5Cint_%5Cmathbb%20R%5CPhi(x)dx%3D1$ ,? 所以也滿足? $%5Csum_%7Bk%3D1%7D%5E%7B2N-2%7D%5CPhi(k)%3D1$ [證明在下方?*?],? 即求得 v 的值.? 假設(shè)已經(jīng)知道了二進(jìn)制點?x=2??k; k∈Z?的值,? 那么可以通過尺度關(guān)系式? $%5CPhi(2%5E%7B-(n%2B1)%7Dl)%3D%5Csum_%7Bk%5Cin%5Cmathbb%20Z%7Dp_k%5CPhi(2%5E%7B-n%7D(l%2B2%5Enk))%3B%5C%3Bl%5Cin%5Cmathbb%20Z$ ?求得下一級二進(jìn)制點的值.

有了尺度函數(shù)之后就可以使用? $%5Cphi(x)%3D%5Csum_%7Bk%5Cin%5Cmathbb%20Z%7D(-1)%5Ek%5Coverline%7Bp_%7B1-k%7D%7D%5CPhi(2x-k)$ ?求出小波函數(shù).? 用二進(jìn)制點表示,? 并使用 1-k 替換 k 得到? $%5Cphi(2%5E%7B-(n%2B1)%7Dl)%3D%5Csum_%7Bk%5Cin%5Cmathbb%20Z%7D(-1)%5E%7Bk-1%7D%5Coverline%7Bp_k%7D%5CPhi(2%5E%7B-n%7D(l%2B2%5En(k-1)))%3B%5C%3Bl%5Cin%5Cmathbb%20Z$ ,? 這個方法對于兩種函數(shù)近似都是通用的.

有限采樣點

當(dāng)采樣點為有限時,? 則有可能不能進(jìn)行足夠的分解步驟,? 這時候就需要對采樣點進(jìn)行延拓.? 常用的延拓方法有4種,? 下面介紹一下,? 假設(shè)采樣點的索引是從 0 到 n.

零延拓? 就是簡單地把在采樣點外的數(shù)據(jù)當(dāng)作 0,? 即? $s_k%3D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7Ds_k%3B%5C%3Bk%5Cin%5B0%2Cn%5D%5C%5C0%3B%5C%3B%5Cmathrm%7Belse%7D%5Cend%7Bmatrix%7D%5Cright.$ .? 適用于信號端點處無關(guān)緊要或者信號本身就是有始有終的.

周期延拓? 就是把信號當(dāng)作周期剛好是采樣區(qū)間那么長的信號,? 即 $s_k%3Ds_%7Bk%5C%25n%7D$ .

線性延拓? 把信號斷點處的兩個采樣點當(dāng)作線性插值的兩個樣本,? 向外面擴(kuò)展,? 即? $s_k%3D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7Ds_k%3B%5C%3Bk%5Cin%5B0%2Ck%5D%5C%5Cs_0%2Bk(s_1-s_0)%3B%5C%3Bk%3C0%5C%5Cs_n%2Bk(s_n-s_%7Bn-1%7D)%3B%5C%3Bk%3En%5Cend%7Bmatrix%7D%5Cright.$ .? 適用于在端點處信噪比比較高的信號.

對稱延拓? 就是在采樣點端點處放一個鏡子,? 讓采樣點對稱地擴(kuò)展到外面.? 對稱延拓有兩個不同的實現(xiàn),? 一個是把鏡子放在整數(shù)點處,? 另一個是把鏡子放在半整數(shù)點處,? 用式子寫起來怪麻煩的,? 可以看看我的源碼.

數(shù)列索引

可以注意到,? 在前3篇專欄里出現(xiàn)的累加絕大部分都是? $%5Csum_%7Bk%5Cin%5Cmathbb%20Z%7D$ ,? 因為計算機(jī)不能實現(xiàn)儲存無限數(shù)據(jù),? 所以所有數(shù)列都應(yīng)該是有限的 [除非有推導(dǎo)式].

這里出現(xiàn)的大部分累加都可以歸納為形式? $c_k%3D%5Csum_%7Bl%5Cin%5Cmathbb%20Z%7Da_%7B%5Calpha(l)%7Db_%7B%5Cbeta(k%2Cl)%7D$ ,? 其中 a, b 是已知的數(shù)列,? c 是需要求出的數(shù)列,? α, β 是相關(guān)的索引函數(shù),? 并且索引函數(shù)都是線性的.? 使用?a?1(l)?替換 l,? 并重新記?β(k,a?1(l)) 為?β(k,l),? 得到? $c_k%3D%5Csum_%7Bl%5Cin%5Cmathbb%20Z%7Da_lb_%7B%5Cbeta(k%2Cl)%7D$ ,? 需要注意的是,? 如果前者里?α(l) 里 l 的系數(shù)絕對值大于 1,? 那么后者 l 的累加范圍不再是整數(shù),? 而是二倍點,? 三倍點之類的.

為了方便,? 記 α? 為數(shù)列 a 里值不為零的最小索引,? α? 為值不為零的最大索引,? 類似地,? 數(shù)列 b 有 β?,? β?.? 又因為假設(shè)了索引函數(shù)是線性的,? 所以重新表達(dá)為? $c_k%3D%5Csum_%7Bl%3D%5Calpha_0%7D%5E%7B%5Calpha_1%7Da_lb_%7Buk%2Bvl%2Bw%7D$ .? 由 b 的索引 uk+vl+w 可以推導(dǎo)出數(shù)列 c 里值不為零的最小最大索引 [本來這里想貼代碼, 可是通用的實在太長了].? 求得了數(shù)列 c 的索引范圍后就可以先申請內(nèi)存再計算數(shù)值了.? 實際上,? b 的索引可以進(jìn)一步限制 l 的累加范圍.? 下面給出? $c%5E%7B(n%2B1)%7D_k%3D%5Csum_%7Bl%5Cin%5Cmathbb%20Z%7Dp_lc%5E%7B(n)%7D_%7Bk-2%5Enl%7D$ 在 julia 里的實現(xiàn)作為例子