一、小波分析算法的計(jì)算

　　1、Mallat算法［經(jīng)典算法］

　　在小波理論中，多分辨率分析是一個(gè)重要的組成部分。多分辨率分析是一種對(duì)信號(hào)的空間分解方法，分解的最終目的是力求構(gòu)造一個(gè)在頻率上高度逼近L2（R）空間的正交小波基，這些頻率分辨率不同的正交小波基相當(dāng)于帶寬各異的帶通濾波器。因此，對(duì)于一個(gè)能量有限信號(hào)，可以通過(guò)多分辨率分析的方法把其中的逼近信號(hào)和細(xì)節(jié)信號(hào)分離開，然后再根據(jù)需要逐一研究。多分辨率分析的概念是S.Mallat在構(gòu)造正交小波基的時(shí)候提出的，并同時(shí)給出了著名的Mallat算法。Mallat算法在小波分析中的地位相當(dāng)于快速傅立葉變換在經(jīng)典傅立葉變換中的地位，為小波分析的應(yīng)用和發(fā)展起到了極大的推動(dòng)作用。

　　MALLAT算法的原理

　　在對(duì)信號(hào)進(jìn)行分解時(shí)，該算法采用二分樹結(jié)構(gòu)對(duì)原始輸入信號(hào)x（n）進(jìn)行濾波和二抽取，得到第一級(jí)的離散平滑逼近和離散細(xì)節(jié)逼近，再采用同樣的結(jié)構(gòu)對(duì)進(jìn)行濾波和二抽取得到第二級(jí)的離散平滑逼近和離散細(xì)節(jié)逼近，再依次進(jìn)行下去從而得到各級(jí)的離散細(xì)節(jié)逼近對(duì)，即各級(jí)的小波系數(shù)。重構(gòu)信號(hào)時(shí)，只要將分解算法中的步驟反過(guò)來(lái)進(jìn)行即可，但要注意，此時(shí)的濾波器與分解算法中的濾波器不一定是同一濾波器，并且要將二抽取裝置換成二插入裝置才行。

　　2、多孔算法

　　多孔算法是由M.shen于1992年提出的一種利用Mallat算法結(jié)構(gòu)計(jì)算小波變換的快速算法，因在低通濾波器和高通濾波器中插入適當(dāng)數(shù)目的零點(diǎn)而得名。它適用于的二分樹結(jié)構(gòu)，與Mallat算法的電路實(shí)現(xiàn)結(jié)構(gòu)相似。先將Mallat算法的電路實(shí)現(xiàn)的基本支路作一下變形。令的z變換為，下兩條支路完全等價(jià)，只不過(guò)是將插值和二抽取的順序調(diào)換一下罷了。圖中其它的上下兩條支路也為等效支路，可仿照上面的方法證明。這樣，我們便可由Mallat算法的二分樹電路結(jié)構(gòu)得出多孔算法的電路級(jí)聯(lián)圖，原Mallat算法中的電路支路由相應(yīng)的等效支路所取代，所以整個(gè)電路形式與Mallat算法非常相似。如果舍去最后的抽取環(huán)節(jié)們實(shí)際上相當(dāng)于把所有點(diǎn)的小波變換全部計(jì)算出來(lái)。

　　3、基干FFT的小波快速算法

　　Mallat算法是由法國(guó)科學(xué)家StephaneG.Mallat提出的計(jì)算小波分解與重構(gòu)的快速算法，能大大降低小波分解與重構(gòu)的計(jì)算量，因此在數(shù)字信號(hào)處理和數(shù)字通信領(lǐng)域中得到了廣泛的應(yīng)用。但是如果直接采用該算法計(jì)算信號(hào)的分解和重構(gòu)，其運(yùn)算量還是比較大。主要體現(xiàn)在信號(hào)長(zhǎng)度較大時(shí)，與小波濾波器組作卷積和相關(guān)的乘加法的計(jì)算量很大，不利于信號(hào)的實(shí)時(shí)處理。故有必要對(duì)該算法作進(jìn)一步的改進(jìn)。眾所周知，F(xiàn)FT是計(jì)算離散傅里葉變換（DFT）的一種快速算法，如能將它和Mallat算法結(jié)合在一起，勢(shì)必會(huì)進(jìn)一步降低小波分解和重構(gòu)的計(jì)算量，事實(shí)證明這一想法是可行的。

　　基于FFT的小波變換快速算法是通過(guò)離散傅里葉變換建立起FFT和mallat算法之何的橋梁，從而將、FFT引入到小波變換中來(lái)，達(dá)到改小波變換快速算法及硬件實(shí)現(xiàn)的研究進(jìn)Mallat算法的目的。

　　當(dāng)信號(hào)長(zhǎng)度較小時(shí)，F(xiàn)FT算法效率不及直接算法;隨著長(zhǎng)度的增加，特別是對(duì)于長(zhǎng)度是2的幕次方的信號(hào)，F(xiàn)FT算法比直接算法更適用，能大大降低計(jì)算t。當(dāng)信號(hào)是長(zhǎng)序列信號(hào)時(shí)，小波分解與重構(gòu)中，濾波器要補(bǔ)很多的零，這對(duì)信號(hào)的實(shí)時(shí)計(jì)算很不利，我們可以采用長(zhǎng)序列快速相關(guān)卷積算法對(duì)信號(hào)進(jìn)行分段后再運(yùn)用FFT算法，提高運(yùn)算速度。

　　4、基于算術(shù)傅里葉變換的小波變換快速算法

　　算術(shù)傅里葉變換（AFT）是1988年由Tufts和Sadasiv提出的一種用Mobius反演公式計(jì)算連續(xù)函數(shù)傅里葉系數(shù)的方法。它具有乘法運(yùn)算t僅為O（N）算法簡(jiǎn)單、并行性好的優(yōu)點(diǎn)。根據(jù)DPT和連續(xù)函數(shù)傅里葉系數(shù)的關(guān)系，可以用AFT計(jì)算DFT。同直接算法相比，APT方法可以將DFT的計(jì)算時(shí)間減少90%，尤其是對(duì)于含有較大素因子，特別是其長(zhǎng)度本身為素?cái)?shù)的DFT，它的速度比傳統(tǒng)的FFT更快。另一方面，Mallat算法的分解和重構(gòu)算法也可由DFT來(lái)計(jì)算，從而將AFT與Mallat算法聯(lián)系了起來(lái)，從而為小波變換快速算法開辟了新的途徑。

　　對(duì)于尺度

　　1）為j的快速分解算法步驟如下：

　　1）選定濾波器系數(shù)h（n）和g（n），再根據(jù)FFT的性質(zhì)2，用N點(diǎn)的AFT分別計(jì)算出H（k）和G（k），分別取共扼，進(jìn)而得到H*（k），G*（k）。

　　2）在已知cj（n）的情況下，用N點(diǎn)的AFT求出其DFTCj（k）

　　3）分別計(jì)算出H*（k）Cj（k），G*（k）Cj（k），即C’j（k）和D’j（k）

　　4）用N點(diǎn)的AFT求出C’j+1（k）和D’j+1（k）IDFT，得到C’j+1（n）和D’j+1（n）IDFT，再分別對(duì)它

　　們作二抽取，就可求出Cj+1（n）和Dj+1（n）。

　　在進(jìn)行分解計(jì)算時(shí)，H（k）G（k）只要計(jì)算一次即可。重復(fù)步驟（2）一（4）可實(shí)現(xiàn)下一尺度小波分解，直到達(dá)到規(guī)定的尺度為止。不過(guò)要注意：尺度增加一個(gè)級(jí)別，信號(hào)長(zhǎng)度減半。

　　2）對(duì)于尺度為j+1的快速重構(gòu)算法為：

　　1）對(duì)Cj+1（n）和Dj+1（n）進(jìn)行二插值，得到C’j+1（n）和D’j+1（n）;

　　2）用N點(diǎn)的AFT分別求出h（n）、g（n）的DFTH（k）和G（k）

　　3）用N點(diǎn)的AFT分別求出C’j+1（n）和D’j+1（n）的DFTC’j+1（k）和D’j+1（k）;

　　4）根據(jù)（17）式求出Cj（k），再用N點(diǎn)的AFT進(jìn)行IDFT，可求出cj（n）。

　　5、基于Hermite插值的小波變換模極大值重構(gòu)信號(hào)快速算法

　　信號(hào)在不同尺度上的小波變換模極大值包含了信號(hào)中的重要信息，因此研究如何由小波變

　　換模極大值重構(gòu)信號(hào)是很有意義的。論文提出了一種基于Hermite插值多項(xiàng)式由二進(jìn)小波變換模極大值重構(gòu)信號(hào)的快速算法。數(shù)值試驗(yàn)表明，與S.Mallat提出的經(jīng)典交替投影算法相比，該算法可以在保證重構(gòu)質(zhì)量的前提下簡(jiǎn)化計(jì)算過(guò)程，提高計(jì)算效率，計(jì)算所需時(shí)間與交替投影算法相比大大減少，是一種實(shí)用性較強(qiáng)的信號(hào)重構(gòu)算法。

　　Hermite插值［11］方法是一種具有重節(jié)點(diǎn)的多項(xiàng)式插值方法，由于它要求在節(jié)點(diǎn)處滿足相應(yīng)的導(dǎo)數(shù)條件，因此也稱為切觸差值。由于小波系數(shù)模極大值點(diǎn)的導(dǎo)數(shù)為零，這與Hermite插值對(duì)節(jié)點(diǎn)的導(dǎo)數(shù)要求不謀而合，因此我們選用Hermite插值多項(xiàng)式作為改進(jìn)的插值方法。

　　6、強(qiáng)奇異積分方程小波Petrov-Galerkin快速算法

　　通過(guò)構(gòu)造具有高階消失矩、小支集和半雙正交性質(zhì)的分片多尺度小波基底，給出第2類強(qiáng)奇異積分方程的小波Petrov-Galerkin快速算法，并證明該算法收斂階達(dá)到最佳，條件數(shù)有界，計(jì)算復(fù)雜性幾乎最佳。構(gòu)造配置泛函的思想，構(gòu)造分片多項(xiàng)式空間Xn上2列具有半雙正交性的小波基，其中一列具有高階消失矩性質(zhì)。

　　二、小波分析算法的C語(yǔ)言實(shí)現(xiàn)

　　小波變換程序：

　　voidDB4DWT（doubleData［］，intn）

　　{

　　if（n》=4）

　　}

　　inti，j;

　　intbalf=n》》1;

　　double*tmp=newdouble［n］;

　　i=0;

　　for（j=0;j《half;j++）

　　{

　　tmp［j］=Data［（2*j）%n］*h0+

　　Data（2*j+l）%n］*h1+

　　Data［（2*j+2）%n］*h2+

　　Data［（2*j+3）%n］*h3;

　　tmp［j+half］=Datal（2*j）%n］*g0+

　　Data［（2*j+I）%n］*g1+

　　Datal（2*j+2）%n］*g2+

　　Data［（2*j+3）%n］*g3;

　　}

　　for（i=0;i《n;i++）

　　{

　　Data［i］=tmp［i］;

　　}}}

　　提升算法的程序

　　小波的分解算法的提升過(guò)程如下：

　　使用提升算法的程序:

　　voidDB4LiftDWT（doubleData［］，intn）

　　應(yīng)用研究

　　inti，half=n》》1;

　　double*pS=newdouble［half］;

　　//臨時(shí)變量存放平滑系數(shù)

　　double*pD=new

　　double［half］;

　　//臨時(shí)變量存放細(xì)節(jié)系數(shù)

　　for（i=0;i《half;it+）/賦值

　　{

　　pS［j］=Data［2*i］：//even，

　　pD［i］=Data［2*i+1］：//odd

　　}

　　for（i=0;i《half;i++）11DB4變換Update1

　　{

　　pS［i］=pS［i］+pD［i］*sqrt_3;

　　}

　　for（i=0;i《half;i++）//DB4的predict

　　{

　　pD［i］=pD［i］-sqrt_3*p$［i14

　?。╯qt_3-2）*pS［（-1）》=0？（i-1）：（halfti-1）14;

　　//邊界是采用周期延拓

　　}

　　for（i=0;i《half;i++）//DB4的update2

　　{

　　pS［i］=pS［i］-pD［（i+1）%half］;

　　/1邊界采用周期延拓

　　}

　　for（i=0;i《half;i++）

　　{

　　p$［i］=（sqt_3-1）*pS［iV（sqnt_2）;/比例系數(shù)

　　pD［i］=（sqrt_3+1）*pD［i］（sqrt_2）;

　　}

　　for（i=0;i《half;i++）

　　{

　　Data［i］=pS［i］;//將平滑系數(shù)放回原數(shù)組

　　}

　　for（i=half;i《length;i++）

　　{

　　Data［i］=pD［i-half］;

　　/將細(xì)節(jié)系數(shù)放回原數(shù)組

　　}

　　deleteOpD;

　　delete［DpS;

　　在目述程序中用到了兩個(gè)臨時(shí)變量數(shù)組，雖然程

　　序結(jié)構(gòu)清楚，容易閱讀但消耗較大的內(nèi)存空間，這里給

　　出另一種方法不用輔助數(shù)組，帶來(lái)節(jié)約內(nèi)存，但耗時(shí)。

　　voidsplit（doubleData［］，intn）

　　{intstart=1;

　　intend=n-1;

　　while（start《end）

　　{for（inti=start;i《end;i=i+2）

　　{doubletmp=Data［i］;

　　Data［i］=Data［i+1］;

　　Data［i+l］=tmp;}

　　start=start+1;

　　end=end-1;}}

　　對(duì)原數(shù)組調(diào)用split函數(shù)進(jìn)行處理后，則Data數(shù)組的前半部分是偶數(shù)索引值，后半部分是奇數(shù)索引值。再對(duì)提升算法的程序進(jìn)行一些修正就可以起到節(jié)約內(nèi)存的目的。具體的實(shí)現(xiàn)限于篇幅不多介紹。利用提升算法的小波程序結(jié)構(gòu)清楚，與Mallat算法相比運(yùn)算量也?。?］。同時(shí)它的反變換也很易實(shí)現(xiàn)，這里由于篇幅限制，不對(duì)反變換作多的介紹。

　　本文給出了一維小波變換的C的實(shí)現(xiàn)，可在基礎(chǔ)上實(shí)現(xiàn)：二維的小波變換，希望對(duì)要自己實(shí)現(xiàn)小波變換的讀者有一定的幫助。