沃爾什變換

若N=2^n，則離散 的沃爾什變換對(duì)為圖8

這里bi(z)為z的二進(jìn)制數(shù)的第i 1位的值（即0或1）。如N=8時(shí)的變換核和反變換作用矩陣形式表示為 9。

1923年，美國(guó)數(shù)學(xué)系J.L Walsh提出walsh函數(shù)。函數(shù)展開有三種：Walsh序的Walsh函數(shù)，佩利序的Walsh函數(shù)，哈達(dá)瑪序的Walsh函數(shù)。

沃爾什變換主要用于圖像變換，屬于正交變換。這種變換壓縮效率低，所以實(shí)際使用并不多。但它快速，因?yàn)橛?jì)算只需加減和偶爾的右移操作。沃爾什變換的定義如下：給定一個(gè)NXN像素塊Pxy（N必須是2的冪），二維WHT定義為如圖1：

沃爾什函數(shù)Wal(k，t)是美國(guó)數(shù)學(xué)家J．L．沃爾什(J．L．Walsh)1923年提出的，定義在半開區(qū)間0≤t<1的一組完備、正交矩形函數(shù)，其波形如圖所示。從圖中可見，函數(shù)只取 1和-1兩個(gè)值。顯然，它的抽樣也只有 1和-1兩個(gè)值，與數(shù)字邏輯中的兩種狀態(tài)相應(yīng)，特別適合于數(shù)字信號(hào)處理。沃爾什變換與傅里葉變換相比，由于它只存在實(shí)數(shù)的加、減法運(yùn)算而沒有復(fù)數(shù)的乘法運(yùn)算，使得計(jì)算速度快、存儲(chǔ)空間少，有利于硬件實(shí)現(xiàn)，對(duì)實(shí)時(shí)處理和大量數(shù)據(jù)操作具有特殊吸引力。在通信系統(tǒng)中由于它的正交性和具有取值和算法簡(jiǎn)單等優(yōu)點(diǎn)，便于構(gòu)成正交的多路復(fù)用系統(tǒng)。

沃爾什函數(shù)與正弦-弦函數(shù)相同，也是一種完備的正交函數(shù)系。所謂完備性，就是所有相互正交的函數(shù)全部包括在該函數(shù)組內(nèi)，再?zèng)]有別的非零函數(shù)與它正交。因而，與在一定條件下，函數(shù)可以表示為傅里葉級(jí)數(shù)相似，對(duì)任一在0≤t<1單位區(qū)間平方可積的周期函數(shù)x(t)均可展開為沃爾什級(jí)數(shù)，且此級(jí)數(shù)具有收斂性。即，按x(t 1)=x(t)，則對(duì)所有t都有如圖2.

式中a₀是直流項(xiàng)，a_k是序號(hào)為k的沃爾什波的幅度，其大小由下式確定，即如圖3

由此可見，沃爾什級(jí)數(shù)可用于信號(hào)序列率譜分析，特別是被逼近的波形不光滑而是階梯函數(shù)時(shí)，效果較傅里葉級(jí)數(shù)好。為了便于數(shù)字處理，對(duì)連續(xù)沃爾什函數(shù)進(jìn)行等間隔抽樣。設(shè)單位時(shí)間內(nèi)取N個(gè)樣點(diǎn)，則抽樣間隔△t=1/N，以X(k)代替a_k，故②式改寫成為如圖4

式③即離散沃爾什變換（DWT）的定義式。若已知輸入信號(hào)數(shù)據(jù)x(n)，可求得相應(yīng)序率譜幅度系數(shù)X（k）。同理，已知X（k)可通過逆變換求x(n)，即如圖5

按沃爾什編號(hào)的沃爾什函數(shù)

沃爾什函數(shù)與正弦函數(shù)有所不同，在單位區(qū)間內(nèi)由于不一定是周期函數(shù)，所以過零點(diǎn)的分布不一定是等間隔的。如圖6所示。但為了與正弦函數(shù)的頻率相對(duì)應(yīng)，因此沃爾什函數(shù)定義單位時(shí)間內(nèi)波形過零點(diǎn)數(shù)務(wù)(或變號(hào)數(shù) ）為序率，它的1/2為列率并以S_k表示，即如圖7

圖中8個(gè)波形的序率是按自然遞增的順序排列的，所以稱這種排列為按沃爾什編號(hào)（或列率排列）的沃爾什函數(shù)，以Wal_ω(k，t)表示。下腳注ω表示按沃爾什編號(hào)。此外還有佩利（Paley)編號(hào)Wal_p(k，t)和哈達(dá)理(Hadamard)編號(hào)Wal_h(k，t)共三類。這三類編號(hào)的沃爾什變換是完全等價(jià)的，實(shí)際上只是排列次序有所不同而已。由于按哈達(dá)瑪編號(hào)的沃爾什變換（WHT）其變換矩陣具有簡(jiǎn)單的遞推關(guān)系，且正、反變換矩陣完全相同，所以獲得廣泛應(yīng)用。如通信領(lǐng)域中的多路數(shù)字通信系統(tǒng)、語音加密、視頻編碼系統(tǒng)、雷達(dá)系統(tǒng)、圖像通信系統(tǒng)；在信號(hào)處理領(lǐng)域中的信號(hào)分析與綜合、功率譜分析、模式識(shí)別、圖像處理。特別是在圖像傳輸、存儲(chǔ)系統(tǒng)中，用于圖像壓縮非常有效。

沃爾什變換雖有上述許多優(yōu)點(diǎn)，但與建立在正、余弦函數(shù)基礎(chǔ)上的傅里葉變換相比，在理論上和實(shí)踐上還有許多問題需要研究和進(jìn)一步解決。如相關(guān)與卷積的運(yùn)算，以及如何從經(jīng)濟(jì)上和技術(shù)上解決以矩形波為基礎(chǔ)的設(shè)備，來取代現(xiàn)有以正弦波為基礎(chǔ)的大量設(shè)備等問題。

離散余弦變換(DCT for Discrete Cosine Transform)是與傅里葉變換相關(guān)的一種變換，它類似于離散傅里葉變換(DFT for Discrete Fourier Transform),但是只使用實(shí)數(shù)。離散余弦變換相當(dāng)于一個(gè)長(zhǎng)度大概是它兩倍的離散傅里葉變換，這個(gè)離散傅里葉變換是對(duì)一個(gè)實(shí)偶函數(shù)進(jìn)行的（因?yàn)橐粋€(gè)實(shí)偶函數(shù)的傅里葉變換仍然是一個(gè)實(shí)偶函數(shù)），在有些變形里面需要將輸入或者輸出的位置移動(dòng)半個(gè)單位(DCT有8種標(biāo)準(zhǔn)類型，其中4種是常見的)。

最常用的一種離散余弦變換的類型是下面給出的第二種類型，通常我們所說的離散余弦變換指的就是這種。它的逆，也就是下面給出的第三種類型，通常相應(yīng)的被稱為"反離散余弦變換"，"逆離散余弦變換"或者"IDCT"。

有兩個(gè)相關(guān)的變換，一個(gè)是離散正弦變換(DST for Discrete Sine Transform),它相當(dāng)于一個(gè)長(zhǎng)度大概是它兩倍的實(shí)奇函數(shù)的離散傅里葉變換；另一個(gè)是改進(jìn)的離散余弦變換(MDCT for Modified Discrete Cosine Transform),它相當(dāng)于對(duì)交疊的數(shù)據(jù)進(jìn)行離散余弦變換。

離散余弦變換，尤其是它的第二種類型，經(jīng)常被信號(hào)處理和圖像處理使用，用于對(duì)信號(hào)和圖像(包括靜止圖像和運(yùn)動(dòng)圖像)進(jìn)行有損數(shù)據(jù)壓縮。這是由于離散余弦變換具有很強(qiáng)的"能量集中"特性:大多數(shù)的自然信號(hào)(包括聲音和圖像)的能量都集中在離散余弦變換后的低頻部分，而且當(dāng)信號(hào)具有接近馬爾科夫過程(Markov processes)的統(tǒng)計(jì)特性時(shí)，離散余弦變換的去相關(guān)性接近于K-L變換(Karhunen-Loève 變換--它具有最優(yōu)的去相關(guān)性)的性能。

例如，在靜止圖像編碼標(biāo)準(zhǔn)JPEG中，在運(yùn)動(dòng)圖像編碼標(biāo)準(zhǔn)MJPEG和MPEG的各個(gè)標(biāo)準(zhǔn)中都使用了離散余弦變換。在這些標(biāo)準(zhǔn)制中都使用了二維的第二種類型離散余弦變換，并將結(jié)果進(jìn)行量化之后進(jìn)行熵編碼。這時(shí)對(duì)應(yīng)第二種類型離散余弦變換中的n通常是8，并用該公式對(duì)每個(gè)8x8塊的每行進(jìn)行變換，然后每列進(jìn)行變換。得到的是一個(gè)8x8的變換系數(shù)矩陣。其中(0,0)位置的元素就是直流分量，矩陣中的其他元素根據(jù)其位置表示不同頻率的交流分量。

一個(gè)類似的變換, 改進(jìn)的離散余弦變換被用在高級(jí)音頻編碼(AAC for Advanced Audio Coding)，Vorbis 和 MP3 音頻壓縮當(dāng)中。

離散余弦變換也經(jīng)常被用來使用譜方法來解偏微分方程，這時(shí)候離散余弦變換的不同的變量對(duì)應(yīng)著數(shù)組兩端不同的奇/偶邊界條件。

離散余弦變換被廣泛的應(yīng)用，像是資料壓縮、特征萃取、影像重建等等。多維度離散余弦變換為：