第五章-圖像變換

數(shù)字圖像處理方法主要分為兩大類：一類方法是在空間域直接對圖像進行處理，稱為空域法；另一類是變換到變換域?qū)D像進行處理，稱為變換域處理法。在變換域處理法中，頻域變換法是運用最為廣泛的一種方法。數(shù)字圖像處理既有廣泛的技術(shù)基礎(chǔ)，也有嚴密的數(shù)學理論基礎(chǔ)。數(shù)學作為圖像變換的工具，發(fā)揮了重要作用。在數(shù)字圖像處理與分析中，圖像增強、圖像復(fù)原、圖像壓縮編碼、圖像分析等每一種處理手段和方法都要應(yīng)用圖像變換方法。第五章圖像變換本章內(nèi)容：圖像變換的作用傅立葉變換離散傅立葉變換傅立葉變換的性質(zhì)二維傅立葉變換離散K-L變換離散余弦變換離散沃爾什變換離散哈達瑪變換小波變換

一.圖像變換的作用

圖像變換的定義是將圖像從空域變換到其它域（如頻域）的數(shù)學變換

圖像變換的作用我們?nèi)祟愐曈X所感受到的是在空間域和時間域的信號。但是，往往許多問題在頻域中討論時，有其非常方便分析的一面。

1.方便處理

2.便于抽取特性常用的變換傅立葉變換FourierTransform2.離散余弦變換DiscreteCosineTransform3.沃爾什－哈達瑪變換Walsh-HadamardTransform二.傅立葉變換

傅立葉變換的作用（1）可以得出信號在各個頻率點上的強度。（2）可以將卷積運算化為乘積運算。（3）傅氏變換和線性系統(tǒng)理論是進行圖像恢復(fù)和重構(gòu)的重要手段。（4）傅立葉變換能使我們從空間域與頻率域兩個不同的角度來看待圖像的問題，有時在空間域無法解決的問題在頻域卻是顯而易見的。

傅立葉變換的定義

傅立葉變換若f(x)為一維連續(xù)實函數(shù)，則它的傅里葉變換可定義為：傅立葉逆變換定義如下：

函數(shù)f(x)和F(u)被稱為傅立葉變換對。即對于任一函數(shù)f(x)，其傅立葉變換F(u)是惟一的；反之，對于任一函數(shù)F(u)，其傅立葉逆變換f(x)也是惟一的。傅里葉變換的條件

傅里葉變換在數(shù)學上的定義是嚴密的，它需要滿足如下狄利克萊條件：(1)具有有限個間斷點；

(2)具有有限個極值點；

(3)絕對可積;F(u)可以表示為如下形式：|F(u)|稱為F(u)的模，也稱為函數(shù)f(x)的傅立葉譜，稱為F(u)的相角。稱為函數(shù)f(x)的能量譜或功率譜。高斯函數(shù)的定義為：例1高斯函數(shù)的傅立葉變換根據(jù)傅立葉變換的定義可得：令x+ju=t，上式可以化為：結(jié)論:與即，高斯函數(shù)的傅立葉變換依然是高斯函數(shù)為傅立葉變換函數(shù)對。例2.矩形函數(shù)

矩形函數(shù)形式如下:

根據(jù)傅立葉變換的定義，其傅立葉變換如下：可得矩形函數(shù)f(x)的傅立葉頻譜為：幾何圖形如下頁圖(b)所示線性系統(tǒng)與傅立葉變換低通高通

傅立葉變換在圖像濾波中的應(yīng)用首先，我們來看Fourier變換后的圖像，中間部分為低頻部分，越靠外邊頻率越高。因此，我們可以在Fourier變換圖中，選擇所需要的高頻或是低頻濾波。傅立葉變換在圖像壓縮中的應(yīng)用

變換系數(shù)剛好表現(xiàn)的是各個頻率點上的幅值。在小波變換沒有提出時，用來進行壓縮編碼?？紤]到高頻反映細節(jié)、低頻反映景物概貌的特性。往往認為可將高頻系數(shù)置為0，騙過人眼。傅立葉變換在卷積中的應(yīng)用直接進行時域中的卷積運算是很復(fù)雜的。傅立葉變換將時域的卷積變換為頻域的乘積。復(fù)雜簡單三.離散傅立葉變換

離散傅立葉變換的定義

要在數(shù)字圖像處理中應(yīng)用傅立葉變換，還需要解決兩個問題：一是在數(shù)學中進行傅立葉變換的f(x)為連續(xù)（模擬）信號，而計算機處理的是數(shù)字信號（圖像數(shù)據(jù)）；二是數(shù)學上采用無窮大概念，而計算機只能進行有限次計算。通常，將受這種限制的傅立葉變換稱為離散傅立葉變換（DiscreteFourierTransform，DFT)。

離散傅立葉變換

離散傅立葉變換的定義設(shè){f

(x)|

f

(0),

f

(1),

f

(2),…,

f

(N-1)}為一維信號f

(x)的N個抽樣，離散傅立葉正變換:離散傅立葉逆變換:四.傅立葉變換的性質(zhì)

共軛對稱性加法定理位移定理相似性定理卷積定理能量保持定理

共軛對稱性

加法定理時域加法頻域加法

位移定理

相似性定理結(jié)論：一個“窄”的函數(shù)有一個“寬”的頻譜

旋轉(zhuǎn)不變性

由旋轉(zhuǎn)不變性可知，如果時域中離散函數(shù)旋轉(zhuǎn)θ角度，則在變換域中該離散傅立葉變換函數(shù)也將旋轉(zhuǎn)同樣的角度。離散傅立葉變換的旋轉(zhuǎn)不變性如圖所示。(a)(b)(d)(c)圖離散傅立葉變換的旋轉(zhuǎn)不變性（a）原始圖像；（b）原始圖像的傅立葉頻譜；（c）旋轉(zhuǎn)45°后的圖像；（d）圖像旋轉(zhuǎn)后的傅立葉頻譜

卷積定理能量保持定理五.二維傅立葉變換1.二維連續(xù)函數(shù)傅立葉變換的定義二維傅立葉正變換:二維傅立葉逆變換:2.二維離散函數(shù)傅立葉變換的定義

根據(jù)一維離散傅立葉變換的定義和二維連續(xù)傅立葉變換理論，對于一個具有M×N個樣本值的二位離散序列f(x，y)，（x=0,1,2,3,…,M-1；y=0,1,2,3,…,N-1）其傅立葉變換為：(1)二維離散傅立葉正變換(2)二維離散傅立葉逆變換若已知頻率二維序列F(u，v)（u=0,1,2,3,…,M-1；v=0,1,2,3,…,N-1），則二維離散序列F(u，v)的傅立葉逆變換定義為：Δx、Δy和Δu、Δv，分別為空間域采樣間隔和頻率域采樣間隔兩者之間滿足如下關(guān)系：

式中序列R(u，v)和I(u，v)分別表示離散序列F(u，v)的實序列和虛序列。二維序列f(x，y)的頻譜（傅立葉幅度譜）、相位譜和能量譜（功率譜）分別如下：F(u，v)可以表示為如下形式：DFT變換（幅值譜）(1)．線性特性3.二維離散傅立葉變換的性質(zhì)(1)比例性質(zhì)=(3)平移性質(zhì)

二維傅立葉變換的移位特性表明，當用乘以f(x，y)，然后再進行乘積的離散傅里葉變換時，可以使頻率域u-v平面坐標系的原點從(0，0)平移到(u0，v0)的位置。(4)可分離性

二維傅立葉變換的可分離特性表明，一個二維傅立葉變換可通過2次一維傅立葉變換來完成，即：第一次先對y進行一維傅立葉變換在此基礎(chǔ)上再對x進行一維傅立葉變換變量分離步驟如圖所示先按行先按列結(jié)果都一樣

若已知頻率二維序列F(u，v)，則二維可分離性對傅立葉逆變換同樣適應(yīng)逆變換的分離性也同樣可以分解為2次一維傅立葉變換

(5)周期性

如果二維離散函數(shù)f(x，y)的傅里葉變換為F(u，v)，則傅立葉變換及其逆變換存在如下周期特性：(6)共軛對稱性(7)旋轉(zhuǎn)不變性

圖像f(x，y)可以表示為f(r，θ)。同樣，空間頻率域的F(u，v)采用極坐標可以表示為F(ρ，)。二維離散傅立葉存在如下旋轉(zhuǎn)特性：(a)原始圖像(c)原始圖像旋轉(zhuǎn)45o(b)DFT變換(d)旋轉(zhuǎn)之后DFT變換結(jié)果(8)微分性質(zhì)(9)平均值性質(zhì)平均值定義如下平均值性質(zhì)如下：即：

結(jié)論：二維離散函數(shù)的平均值等于其傅立葉變換在頻率原點處值的1/MN。二維傅立葉變換(幅值及相位)意義左邊一列:

上方為原始圖像,下方為本圖的相關(guān)說明說明;中間一列:

上圖幅值譜,下圖為根據(jù)幅值譜的傅立葉逆變換(忽略相位信息,設(shè)相位為0);右邊一列:

上圖相位譜,下圖為根據(jù)相位譜的傅立葉逆變換(忽略幅值信息,設(shè)幅值為某一常數(shù));圖像的說明5.3快速傅里葉變換由于普通離散傅立葉變換運算量非常之大，在一定程度上限制了它的應(yīng)用。因此，工程上特別需要一種傅立葉變換的快速算法。1965年Cooley和Tukey提出了快速傅立葉（FFT）算法。離散傅立葉變換的快速算法大大提高了傅立葉運算速度，開始應(yīng)用于一些重要的控制系統(tǒng)，在一些工程應(yīng)用中已經(jīng)實現(xiàn)實時處理。FFT通過分析DFT算法的規(guī)律，消除了許多重復(fù)的運算，大大減少了運算量，節(jié)省了運算時間，提高了處理速度。5.3.1DFT的運算量由于二維離散傅立葉變換具有可分離性，即它可由兩次一維離散傅立葉變換計算得到，因此，僅研究一維離散傅立葉變換的快速算法即可。先將一維離散傅立葉變換寫成式中，W=e-j2π／N

，稱為旋轉(zhuǎn)因子。這樣，可將上式所示的一維離散傅立葉變換（DFT）用矩陣的形式表示為（注意頻域中的坐標點!!!）式中，由Wux構(gòu)成的矩陣稱為W陣或系數(shù)矩陣。

觀察DFT的W陣，并結(jié)合W的定義表達式W=e-j2π／N，可以發(fā)現(xiàn)系數(shù)W是以抽樣點數(shù)N為周期的。這樣，W陣中很多系數(shù)就是相同的，不必進行多次重復(fù)計算，且由于W的對稱性，即因此可進一步減少計算工作量。5.3.2FFT算法原理例如，對于N=4，由展開得到

W陣為：F(0)F(1)F(2)F(3)FFT根據(jù)算法原理可以分為基于時間分解（DIT）和基于頻率分解（DIF）兩類算法，其中的典型代表分別是DIT基2算法和DIF基2算法。以下以DIT基2算法介紹由W的周期性得：W4＝W0，因此推出W6＝W4*W2=W2，同理可得W9＝W1；再由W的對稱性可得：W3＝－W1，推出W2＝－W0。于是上式可變?yōu)榭梢奛=4的W陣中只需計算W0和W1兩個系數(shù)即可。這說明W陣的系數(shù)有許多計算工作是重復(fù)的，如果把一個離散序列分解成若干短序列，并充分利用旋轉(zhuǎn)因子W的周期性和對稱性來計算離散傅立葉變換，便可以簡化運算過程，這就是FFT的基本思想。設(shè)抽樣點數(shù)N為2的正整數(shù)次冪，即如令M為正整數(shù)，且N=2M，即N分成2個長度為M的短序列

。離散傅立葉變換可改寫成奇、偶函數(shù)之和，如下形式：由旋轉(zhuǎn)因子W的定義可知 ，因此上式變?yōu)?/p>

現(xiàn)定義于是上式（即上半截短序列，u=0~M）變?yōu)?/p>

進一步考慮W的對稱性和周期性可知 和 ，于是，下半截短序列(u=0~M)為由此，可將一個N點的離散傅立葉變換分解成兩個N／2短序列的離散傅立葉變換，即分解為偶數(shù)和奇數(shù)序列的離散傅立葉變換Fe(u)和Fo(u)。

在此，以計算抽樣點N=8（=23=2*4）的DFT為例，此時n=3，M=4(折半)。由式(7-31)和式(7-32)可得(7-33)下半截F(u+M)上半截F(u)

式（7-33）中，u取0～7時的F(u)、Fe(u)和Fo(u)的關(guān)系可用圖7-7描述(F(0)-F(4);F(1)-F(5);F(2)-F(6);F(3)-F(7))。左方的兩個節(jié)點為輸入節(jié)點，代表輸入數(shù)值；右方兩個節(jié)點為輸出節(jié)點，表示輸入數(shù)值的疊加，運算由左向右進行。線旁的W18和－W18為加權(quán)系數(shù)，定義由F(1)、F(5)、Fe(1)和Fo(1)所構(gòu)成的結(jié)構(gòu)為蝶形運算單元,其表示的運算為(7-34)圖7-7蝶形運算單元（F(1)-F(5)）由于Fe(u)和Fo(u)都是4點的DFT，因此，如果對它們再按照奇偶進行分組(即M=2，計算F(u)及F(u+M))，則有（7-35a）（7-35b）M=4M=2圖7-84點DFT分解為2點（M=2）DFT的蝶形流程圖M=2圖5-88點DFT的蝶形流程圖（與編程循環(huán)關(guān)系）循環(huán)外層循環(huán)中層循環(huán)內(nèi)層圖5-78點DFT逐級分解框圖由圖5-8可知，由于每一級有8/2=4個基本碟形運算，8點離散序列完全分解以后總的運算次數(shù)CF8為：

CF8=8/2*log28=12，而直接采用DFT計算需要64次復(fù)數(shù)乘法，F(xiàn)FT的元算量不足DFT的20%。FFT另一個典型的算法是：DIF基2算法，即按頻率抽取法，其基本思路與DIT基2算法類似.關(guān)于倒位序：分析圖5-8可以發(fā)現(xiàn)，利用FFT快速算法計算傅立葉變換時，輸入序列f(n)并不是自然的順序，這是由于不斷分解為奇偶子序列的原因造成的，存在所謂的倒序位，見下表表7-2自然順序與碼位倒序（N=8）問題：采樣點數(shù)N與圖像的大小相關(guān)采樣分為水平采樣和垂直采樣快速傅里葉變換算法與VC++中的代碼如何對應(yīng)？函數(shù)的調(diào)用關(guān)系指針的作用——返回數(shù)值函數(shù)形參的作用：輸入，由外界傳入到函數(shù)內(nèi)部輸出，由函數(shù)內(nèi)部輸出到函數(shù)的外部，屬于指針型參數(shù)。5.4離散K-L變換（略）K-L變換（Karhunen-LoeveTransform）是數(shù)字圖像處理中具有廣泛應(yīng)用的一類重要變換，又稱為特征向量變換、主分量變換或霍特林變換。K-L變換既有連續(xù)形式的變換，又有離散形式的變換。數(shù)字圖像處理中主要是利用其離散變換形式，主要優(yōu)點是去相關(guān)性比較好，該變換在數(shù)據(jù)壓縮、圖像旋轉(zhuǎn)、遙感多光譜圖像的特征選擇和統(tǒng)計識別等方面具有重要應(yīng)用。5.4.1K-L變換的基本原理在實際應(yīng)用中，二維圖像可以視為隨機場。一幅N×N圖像f(x,y)在某個通信信道中傳輸了M次，由于受到隨機噪聲的干擾，接收到的可能是一個受到干擾的圖像隨機變量的樣本集合：{f1(x,y),f2(x,y),…,fM(x,y)}對于第i次獲得的圖像f(x,y)，可以用N2×1維向量Xi表示：Xi=[fi(0,0),fi(0,1),…,fi(0,N-1),fi(1,0),fi(1,1),fi(1,N-1),…,fi(N-1,0),fi(N-1,1),…fi(N-1,N-1)]若以Xij表示第i次獲得的圖像f(x,y)中的第j行的N個分量，則上式為：Xi=[Xi1，Xi2，…，XiN]T根據(jù)概率論和數(shù)理統(tǒng)計知識，圖像隨機場信號的隨機變量之間的相關(guān)程度可以采用協(xié)方差矩陣表示。因此，向量X的協(xié)方差矩陣的定義如下：

Cx=E[(X-mx)(X-mx)T]式中，Cx是N2×N2對稱方陣，對角線上的元素Cnn表示第n個分量的方差，Cnm表示第n個元素與第m個元素之間的協(xié)方差；E表示數(shù)學期望，mx表示向量X的平均值。向量X的平均值定義為：mx=E[X]對于M幅數(shù)字圖像，向量X的均值mx可以用全部樣本的平均值近似計算，即：向量X的協(xié)方差矩陣Cx可以采用同樣的方法計算，即Cx是N2×N2實對稱方陣，所以總可以求出協(xié)方差矩陣的N2個特征值及其對應(yīng)的正交特征向量。設(shè)特征值λi（i=1，2，…N2）。并將特征值按遞減排序，即λi>λ2>…>λN2,則定義K-L變換矩陣A如下：式中，eij表示第i個特征向量的第j個分量。于是，可得K-L變換形式為：

Y=A（X-mx）向量Y的形式與X相同，該變化可直接理解為，由中心化圖像向量（X-mx）與變換矩陣A相乘即可得到變換后的圖象向量Y5.4.2K-L變換的性質(zhì)(1)變換后圖像向量Y的均值向量為0（0向量），即：

my=E[Y]=E[A(X-mx)]=AE[X]-Amx=0(2)向量Y的協(xié)方差矩陣Cy可由A和Cx求得：

Cy=E[(Y-my)(Y-my)T]=…=ACxAT(3)經(jīng)過K-L變換后完全消除了元素之間的相關(guān)性，即協(xié)方差矩陣Cy是對角陣，且主對角線上的元素等于Cx的特征值。協(xié)方差矩陣Cy主對角線以外的元素全部為0，即變換圖像Y的各個元素是互不相關(guān)的。由于λi也是Cx的特征值，所以Cy和Cx具有完全相同的特征值和特征向量。5.4.3K-L變換的逆變換與其他變換類似，K-L變換也有逆變換，即可以通過Y來重建X。由于矩陣A的各行都是正交歸一化適量，所以有A-1=AT

根據(jù)K-L變換可得：

X=A-1Y+mx由于協(xié)方差矩陣特征值是由小到大排列的，在許多實際應(yīng)用中，可以充分利用K-L變換的這個性質(zhì)近似計算，例如可以只取一部分特征值及其對應(yīng)的特征向量，則Cx=Cy可以表示為由特征向量組成的對角陣。P121即可以只取前n個分量重建X的近似值

Xn=An-1Y+mx

因此可以得出Xn和X之間的均方誤差為：若K=N2，則均方誤差為0，即可精確地重構(gòu)X。由于特征值λi是單調(diào)遞減的，因此可以通過取不同的n值來控制Xn和X之間的均方誤差，即完全可以根據(jù)誤差的要求來控制所取特征值的數(shù)量?？梢詫崿F(xiàn)均方誤差最小意義下的最優(yōu)變換綜上所述，K-L變換具有許多優(yōu)點，最重要的優(yōu)點是去相關(guān)性能非常好，它可以完全解除數(shù)據(jù)之間的相關(guān)性，因此，K-L變換可廣泛應(yīng)用于圖像數(shù)據(jù)的旋轉(zhuǎn)或壓縮處理。缺點1：二維K-L變換不是可以分離的變換，不能通過在x與y方向上的兩次一維的K-L變換來完成二維K-L變換的運算。缺點2：對于圖像數(shù)據(jù)的K-L變換，必須計算圖像數(shù)據(jù)的N2XN2協(xié)方差矩陣的特征值和特征向量，計算量非常大，因而在實際圖像處理中并沒有得到所期望的普及程度。1.問題的提出：傅立葉變換的一個最大的問題是：它的參數(shù)都是復(fù)數(shù)，在數(shù)據(jù)的描述上相當于實數(shù)的兩倍。為此，我們希望有一種能夠達到相同功能但數(shù)據(jù)量又不大的變換。在此期望下，產(chǎn)生了DCT變換。

DCT有許多優(yōu)點：DCT變換陣的基向量很近似于Toeplitiz矩陣的特征向量，很好地體現(xiàn)了人類語音信號及圖像信號的相關(guān)特性。而且DCT變換還可以通過實偶函數(shù)的傅立葉變換建立與FFT之間的關(guān)系。六.離散余弦變換DCT由Ahned和Rao在1974年首先提出，隨后得到廣泛應(yīng)用，被認為是一種準最佳變換。在近年來頒布的一系列視頻壓縮編碼的國際標準建議中，都將DCT變換作為其中的一個基本處理模塊。其他優(yōu)點：DCT為實數(shù)變換，變換矩陣確定（與變換對象無關(guān)）具有多種快速算法，還有一種可分離的變換余弦變換實際上是傅立葉變換的實數(shù)部分。余弦變換主要用于圖像的壓縮，如目前的國際壓縮標準的JPEG格式中就用到了DCT變換。具體的做法與DFT相似。給高頻系數(shù)大間隔量化，低頻部分小間隔量化。5.5.1一維DCT變換一維DCT的變換核定義為式中，x,u=0,1,2,…,N－1；

一維DCT定義如下：設(shè){f(x)|x=0,1,…,N-1}為離散的信號列。式中，u,x=0,1,2,…,N－1。將變換式展開整理后，可以寫成矩陣的形式，即F=Gf其中F=[F(0),F(1),F(2),…,F(N-1)]Tf=[f(0),f(1),f(2),…,f(N-1)]T

一維DCT的逆變換IDCT定義為

式中，

x,u=0,1,2,…,N－1?？梢娨痪SDCT的逆變換核與正變換核是相同的。5.5.2二維DCT變換

考慮到兩個變量，很容易將一維DCT的定義推廣到二維DCT。其正變換核為式中，C(u)和C(v)的定義同前式；x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。二維DCT定義如下：設(shè)f(x,y)為M×N的數(shù)字圖像矩陣，則式中：x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。二維DCT逆變換定義如下：式中：x,u=0,1,2,…,M－1；

y,v=0,1,2,…,N－1。類似一維矩陣形式的DCT，可以寫出二維DCT的矩陣形式如下：F=GfGT

同時，由前面式可知二維DCT的逆變換核與正變換核相同，且是可分離的，即式中：C(u)和C(v)的定義同前式；

x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。

通常根據(jù)可分離性，二維DCT可用兩次一維DCT來完成，其算法流程與DFT類似，即5.5.3快速離散余弦變換

離散余弦變換的計算量相當大，在實用中非常不方便，也需要研究相應(yīng)的快速算法。目前已有多種快速DCT（FCT），在此介紹一種由FFT的思路發(fā)展起來的FCT。首先，將f(x)延拓為x=0,1,2,…,N-1x=N，N+1,…,2N-1按照一維DCT的定義，fe(x)的DCT為

由于 為fe(x)的2N點DFT。因此，在作DCT時，可把長度為N的f(x)的長度延拓為2N點的序列fe(x)，然后對fe(x)作DFT，最后取DFT的實部便可得到DCT的結(jié)果。同理對于離散余弦逆變換IDCT，可首先將F(u)延拓為u=0,1,2,…,N-1u=N,N+1,…,2N-1由前式可得，DCT的IDCT為

最后要注意的是二維DCT的頻譜分布，其譜域分布與DFT相差一倍，如圖5-10所示。從圖中可以看出，對于DCT而言，(0,0)點對應(yīng)于頻譜的低頻成分，(N-1,N-1)點對應(yīng)于高頻成分，而同階的DFT中，(N／2,N／2)點對應(yīng)于高頻成分（注：此頻譜圖中未作頻譜中心平移）。

由于DFT和IDFT已有快速算法FFT和IFFT，因此可用它們實現(xiàn)快速DCT和IDCT算法FCT及IFCT。不過，由于FFT及IFFT中要涉及到復(fù)數(shù)運算，因此這種FCT及IFCT算法并不是最佳的。圖5-10DFT和DCT的頻譜分布（a）DFT頻譜分布；（b）DCT頻譜分布低頻高頻低頻高頻返回返回Fourier變換的高通濾波另一幅圖像效果壓縮率為：1.7：1壓縮率為：2.24：1壓縮率為：3.3：1

返回壓縮率為：8.1：1壓縮率為：10.77：1壓縮率為：16.1：1返回Fourier變換的低通濾波5.6離散沃爾什變換DFT的快速運算是在復(fù)數(shù)范圍內(nèi)進行的，運算量龐大，運算復(fù)雜；DCT變換也要進行三角函數(shù)運算，運算的復(fù)雜程度依然很高。為了避免因數(shù)據(jù)本身原因所產(chǎn)生的運算復(fù)雜性，1923年美國數(shù)學家沃爾什提出了沃爾什函數(shù)，也就有了沃爾什變換。它由+1和-1兩個數(shù)值所構(gòu)成的完備正交基（而且是二值正交基）組成，與數(shù)字邏輯的兩個狀態(tài)相對應(yīng)，有利于計算機的處理。與DFT相比，沃爾什變換減少了存儲空間，提高了運算速度，對圖像處理非常有利。5.6.1一維沃爾什變換從排列次序上可以將沃爾什函數(shù)分為三種定義方法：一種是按照佩利排列來定義（按自然排序）；另一種是按照沃爾什排列來定義（按列率排列）；第三種是按哈達碼排列來定義，又稱為哈達碼變換。1.沃爾什變換設(shè)f(x)表示N點的一維離散序列，則一維沃爾什變換定義如下：其中，一維沃爾什變換核為：式中，u=0,1,2,3,…N-1