數(shù)字圖像處理-正交變換

數(shù)字圖像處理1基本概念模擬圖像處理包括光學處理和電子學處理。如照相、電視圖像等的處理；速度快，但精度不高。數(shù)字圖像處理利用計算機或其他硬件對圖像進行處理。精度高，但是速度較慢。1.1數(shù)字圖像從物理的角度來看，一幅圖像記錄的是物體輻射能量的空間分布。如果不考慮波長和時間的因素，則圖像的一般表達形式為：1.1數(shù)字圖像數(shù)字圖像可以理解為圖像物體的一種數(shù)字化表示形式。對連續(xù)圖像可以進行空間和幅度抽樣，得到數(shù)字圖像。在空間和幅度上對圖像進行抽樣：x方向，抽樣M行y方向，每行抽樣N點整個圖像共抽樣MN個像素點一般取M=N=2n=64，128，256，512，1024，2048對每個像素點進行灰度級量化：G=2m常取m=6,7,8,9,10,11,12bit對應的灰度級為:64,128,256,512,1024,2048,4096級1.1數(shù)字圖像數(shù)字圖像常用矩陣來表示：1.1數(shù)字圖像矩陣中每一個元素稱為像素(pixel)，其值稱為圖像的灰度或亮度(intensity)，是離散的。矩陣的維數(shù)或大小稱為圖像的分辨率。無論是灰度還是分辨率，量化時一般都取2的整數(shù)冪。一般地，彩色圖像可以采用紅(R)、綠(G)、藍(B)三個矩陣表示或混合表示。1.2數(shù)字圖像的種類幾種基本數(shù)字圖像類型：二值圖像灰度圖像索引圖像RGB圖像(真彩圖像)其他圖像1.2數(shù)字圖像二值圖像:圖像的灰度級別僅有2個，即0和1。通常用于文字圖像。每個像素只用1bit表示?；叶葓D像:圖像灰度通常有較大的取值范圍，常用的為256級，即灰度值域為[0,255]。0表示黑色，255表示白色，其他灰度為從黑到白的變化情況。每個像素所需的字節(jié)數(shù)根據(jù)其灰度的變化范圍不同二不同。256級灰度圖像每個像素需用8bit表示。1.2數(shù)字圖像索引圖像每個像素的值并不表示該像素真正的灰度值，而是表示對應于色彩表中的索引號。色彩表為預先設(shè)置好的RGB色彩。通常用來表示256色的彩色圖像。每個像素需要8bit表示。RGB圖像圖像的灰度為該點的R、G、B值，直接存放在圖像灰度矩陣中。一般每個像素需要用3×8＝24bit位來表示。其色彩可為224

，一般稱為真彩圖像。其他圖像－還有圖像的透明因子，每個像素需要32bit來表示。1.3數(shù)字圖像處理的研究內(nèi)容

從計算機處理的角度可以由高到低將數(shù)字圖像分為三個層次。這三個層次覆蓋了圖像處理的所有應用領(lǐng)域。1.3數(shù)字圖像處理的研究內(nèi)容數(shù)字圖像處理是一門交叉學科，研究方法上，與數(shù)學、物理學、生理學、心理學、電子學、計算機科學相互借鑒；研究范圍上，與計算機圖形學、模式識別、計算機視覺相互交叉。1.3數(shù)字圖像處理的研究內(nèi)容圖像正交變換采用各種圖像變換方法對圖像進行間接處理。有利于減少計算量并進一步獲得更有效的處理。圖像增強與復原加強圖像的有用信息，消弱干擾和噪聲。 把退化、模糊了的圖像復原。模糊的原因有許多種，最常見的有運動模糊，散焦模糊等等。圖像編碼 簡化圖像的表示，壓縮表示圖像的數(shù)據(jù)，以便于存儲和傳輸。1.3數(shù)字圖像處理的研究內(nèi)容圖像重建 由原始圖像數(shù)據(jù)進行不同目的的圖像顯示。如二維圖像重建三維圖像。圖像分割與特征提取 圖像分割是指將一幅圖像的區(qū)域根據(jù)分析對象進行分割。圖像的特征提取包括了形狀特征、紋理特征、顏色特征等等。圖像分析和理解

對圖像中的不同對象進行分類、識別和描述、解釋。1.3數(shù)字圖像處理的研究內(nèi)容學習內(nèi)容正交變換復原和增強圖像編碼圖像分割形態(tài)學處理圖像識別2圖像的正交變換2.1圖像正交變換數(shù)字圖像是一個二維信號，可以寫成代數(shù)形式，也可寫成實數(shù)矩陣形式?？梢圆捎贸醯茸儞Q找到同型矩陣：數(shù)字圖像的變換要求能從反變換中完整地恢復過來。正交變換是滿足完整反變換要求的一種變換。2.1圖像變換的表達式－正交變換正交變換的變換核為正交函數(shù)。滿足正交性：。滿足完備性：函數(shù)集合中的函數(shù)可以完整的對其他函數(shù)進行分解表達。正交完備性意味著所有的正交函數(shù)都存在于完備函數(shù)集中，無論是在時域還是在變換域中其能量都是相同的，可以將函數(shù)分解成正交函數(shù)的表達形式。二維變換：N×N的二維函數(shù)f(x,y)2.1圖像變換的表達式－正交變換稱為正變換核，稱為反變換核。為了使信號完整重建，正變換核和反變換核都必須滿足正交性和完備性。變換核可分離性：將二維變換分解為2個一維變換的計算。2.1圖像變換的表達式－正交變換即可將二維變換進行分解計算，分別對行和列進行計算，簡化計算過程。2.2.1一維傅立葉變換1.一維連續(xù)函數(shù)的傅立葉變換（FT）定義：若函數(shù)滿足狄里赫利(Dirichlet)條件：

1）具有有限個間斷點；

2）具有有限個極值點；

3）絕對可積，則把下列變換成立：傅立葉正變換：傅立葉反變換：2.2傅立葉變換2.2.1一維傅立葉變換如果為實函數(shù)，傅立葉變換用復數(shù)表示：用指數(shù)形式表示：傅立葉譜：相角：能量譜：2.2.2二維傅立葉變換1.二維連續(xù)函數(shù)傅立葉變換（2DFT）定義:若f(x,y)是連續(xù)圖像函數(shù)反變換:正變換:變換對:2.幅度譜、相位譜、能量譜一般F(u,v)是復函數(shù),即:幅度譜:相位譜:能量譜:2.2.2二維傅立葉變換2.2.3離散傅立葉變換1.一維離散傅立葉變換（DFT）傅立葉正變換：傅立葉反變換：對于一個有限長序列{X(n)},(0≤n≤N-1),其傅立葉變換式為：2.2.3離散傅立葉變換令2.2.3離散傅立葉變換2.快速傅立葉變換流程圖基2、時間抽取算法，N=8x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x1(0)x1(1)x1(2)x1(3)x1(4)x1(5)x1(6)x1(7)x2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)x3(0)x3(1)x3(2)x3(3)x3(4)x3(5)x3(6)x3(7)x4(0)x4(1)x4(2)x4(3)x4(4)x4(5)x4(6)x4(7)-1w2w2w2w1w3-1-1-1-1-1-1-1-1-1-1-1F(u)f(x)2.2.3離散傅立葉變換3.如何提高FFT的速度？（1）減少乘法次數(shù)；（2）基4、基8算法；（3）實數(shù)FFT；（4）硬件實現(xiàn)（DSP芯片，F(xiàn)FT集成塊）因為：4.FFT舉例-1-1-1-1w2w2-1-1-1-1w2w1w3-1-1-1-11001-1001111-1-1-120F（u）2000001001f（x）其中：2.2.3離散傅立葉變換F（u）=[2，0，，，，，，]幅度譜：幅度譜圖：0121234567uF（u）定義:若f(x,y)是離散圖像函數(shù)，為N×N維大小，則其傅立葉變換為：正變換:反變換:2.2.4二維離散傅立葉變換1.求移中的傅立葉變換：2.求幅度譜：3.求幅度譜的對數(shù)函數(shù)：步驟:4.顯示D(u,v)若D(u,v)很小或很大，則將其線形擴展或壓縮到0-2552.2.4二維離散傅立葉變換1.可分離性正變換2.2.4二維離散傅立葉變換同樣，反變換也具有可分離性1.可分離性2.2.4二維離散傅立葉變換利用二維傅立葉變換的可分離性，可將二維DFT轉(zhuǎn)化成一維DFT計算。即，先在x（或y）方向進行一維DFT，再在y（或x）方向進行一維DFT：第一步：第二步：1.可分離性2.2.4二維離散傅立葉變換二維離散傅立葉變換過程圖示：第一步：第二步：f（x，y）=F（u，y）=先在x方向逐行進行一維FT再在y方向逐列進行一維FT1/NF（u，v）=1.可分離性2.2.4二維離散傅立葉變換二維離散傅立葉變換舉例例1：y方向FFTx方向FFT1/42.平移性FT則：相當于F（u，v）的坐標原點移到（u0，v0）點2.2.4二維離散傅立葉變換即：移中性同理：2.平移性2.2.4二維離散傅立葉變換移中性移中性的用途：圖像作傅立葉變換時，若采用以下公式變換，則變換后主要能量（低頻分量）集中在頻率平面的中心。移中性未移中的變換：FT移中的變換：能量集中于中心（示意圖）移中FT原圖像f（x，y）能量分布于四角（示意圖）移中FT移中FT3.周期性非周期性離散函數(shù)的FT是離散的周期性函數(shù)2.2.4二維離散傅立葉變換4.旋轉(zhuǎn)性當變量x，y，u，v都用極坐標表示時，即：則：若：此式含義是：當原圖像旋轉(zhuǎn)某一角度時，F(xiàn)T后的圖像也旋轉(zhuǎn)同一角度。2.2.4二維離散傅立葉變換旋轉(zhuǎn)性舉例：原圖像及其傅立葉幅度譜圖像原圖像旋轉(zhuǎn)45，其幅度譜圖像也旋轉(zhuǎn)455.卷積定理若：*卷積

?乘積

則：空域頻域2.2.4二維離散傅立葉變換6.相關(guān)定理若：則：空域頻域*共軛乘積相關(guān)2.2.4二維離散傅立葉變換7.共軛對稱性8.平均值9.線性10.比例變換2.2.4二維離散傅立葉變換2.2.5離散傅立葉變換的矩陣表示目的:（1）用矩陣乘法的程序進行FT；（2）理論推導用。1.一維DFT的矩陣表示根據(jù)定義:令:則:展開:令:正變換:反變換:(忽略1/N)2.2.5離散傅立葉變換的矩陣表示2.二維DFT的矩陣表示根據(jù)可分離性：令:忽略1/N2.二維DFT的矩陣表示FT：IFT：（忽略1/N）復數(shù)計算收斂速度較慢幅度衰減快2.2.6傅立葉變換的特點2.3離散余弦變換問題的提出：

Fourier變換的一個最大的問題是：它的參數(shù)都是復數(shù)，在數(shù)據(jù)的描述上相當于實數(shù)的兩倍。為此，我們希望有一種能夠達到相同功能但數(shù)據(jù)量又不大的變換。在此期望下，產(chǎn)生了DCT(DiscreteCosineTransform)變換。2.3.1一維離散余弦變換正變換：反變換：特點：（1）無虛數(shù)部分（2）正變換核與反變換核一樣2.3.1一維離散余弦變換其變換核為：滿足正交完備條件。實奇函數(shù)的DFT:

若,則

，僅有正弦項的虛部。

實偶函數(shù)的DFT:

若,則，僅有余弦項的實部。?偶函數(shù)的構(gòu)造

（1）奇對稱的偶函數(shù)

（a）原圖像（b）奇對稱的偶函數(shù)（c）偶對稱的偶函數(shù)（2）偶對稱的偶函數(shù)

?二維離散余弦變換（2D-DCT）公式將構(gòu)造的偶函數(shù)代入2D-DFT公式，進行整理后就得到2D-DCT公式：2D-DCT的反變換定義為：式中：，2.3.2二維離散余弦變換1.正變換F(0,0)F(u,0)F(0,v)F(u,v)2.3.2二維離散余弦變換2.反變換2.3.2二維離散余弦變換其變換核為：2.3.2二維離散余弦變換變換核是可分離的。二維DCT可分解為二次一維DCT。離散余弦變換對應于傅里葉變換中的實數(shù)部分。計算機中可以快速實現(xiàn)。2.3.3離散余弦變換的矩陣表示方法一維離散余弦變換：正變換：反變換：二維離散余弦變換：正變換：反變換：C為離散余弦變換矩陣，CT為C的轉(zhuǎn)置矩陣2.3.3離散余弦變換的矩陣表示方法當N=4時，變換矩陣C為：當N=2時，變換矩陣C為：已知：用矩陣算法求其DCT。由此例可看出：DCT將能量集中于頻率平面的左上角。2.3.3離散余弦變換的矩陣表示方法3.舉例DCT圖像經(jīng)DCT后,能量集中于頻率平面的左上角。DCT用于圖像數(shù)據(jù)壓縮。DCT變換的應用：余弦變換實際上是傅立葉變換的實數(shù)部分。余弦變換主要用于圖像的壓縮和語音處理，如目前的國際壓縮標準的JPEG格式中就用到了DCT變換。具體的做法與DFT相似。給高頻系數(shù)大間隔量化，低頻部分小間隔量化。2.3.4離散余弦變換的應用2.4沃爾什變換(WalshTransform)傅立葉變換和余弦變換:適合于頻域處理，可硬件實現(xiàn)，精度高。快速算法，復數(shù)運算，乘法，速度慢。Walsh變換:快速算法，實數(shù)運算，加減法，速度快，可硬件實現(xiàn)，精度低，適用于計算機技術(shù)和數(shù)字信號處理等。2.4.1引言2.4沃爾什(Walsh)變換

拉德梅克(Rademacher)函數(shù)的定義:其中：n為序號，n=0，1，，N-1t為連續(xù)時間變量把正弦函數(shù)無限放大得到。符號函數(shù)：拉德梅克(Rademacher)函數(shù):符號函數(shù)：+1-1+1-1+1-1+1-11ttttt+1-11111n=0n=1n=2n=3（2）是一個不完備的函數(shù)，只有奇函數(shù)，不能用于變換。拉德梅克函數(shù)的特點：（1）是正交函數(shù)族。（3）其值為+1或-1。2.4.2Walsh函數(shù)1.連續(xù)Walsh函數(shù)的定義(1)Walsh序的Walsh函數(shù)定義:其中:拉德梅克函數(shù)2.4沃爾什(Walsh)變換

二進制碼格雷碼nb2b1b0g2g1g0000000010010012010011301101041001105101111611010171111002.4沃爾什(Walsh)變換

2.4.2Walsh函數(shù)

二進制碼格雷碼nb2b1b0g2g1g000000001001001201001130110104100110510111161101017111100+1-1+1-1+1-11ttt11+1-1+1-1+1-11ttt1111111tttttWalsh序的Walsh函數(shù)的特點:(1)是完備的正交函數(shù),序號為偶數(shù)的是偶函數(shù),序號為奇數(shù)的是奇函數(shù);可用于正交變換。(2)一個周期內(nèi),過零點數(shù)與序號一致.2.4.2Walsh函數(shù)(2)Hadamard序的Walsh函數(shù)定義:其中:Ii是n的二進制碼的倒序碼的第i位

二進制碼倒序碼nb2b1b0I2I1I0000000010011002010010301111041000015101101611001171111112.4沃爾什(Walsh)變換

定義:(2)Hadamard序的Walsh函數(shù)2.4沃爾什(Walsh)變換

2.4.2Walsh函數(shù)2.離散Walsh函數(shù)的定義定義:(1)Walsh序的離散Walsh函數(shù)其中:2.4沃爾什(Walsh)變換

2.4.2Walsh函數(shù)定義:例:N=8,n=0,1,,7,t=0,1,,7計算WW(4,0)

n=4=(100)2t=0=(000)2t的格雷碼g=(000)22.4沃爾什(Walsh)變換

2.4.2Walsh函數(shù)(1)Walsh序的離散Walsh函數(shù)(1)Walsh序的離散Walsh函數(shù)例:N=8,n=0,1,,7,t=0,1,,7計算WW(4,t)

同理，可求出：實際上，這個序列就是從連續(xù)的Walsh序的Walsh函數(shù)WW（4，t）在等間距的N個點上的抽樣（取中間值）tWW(4,t)+1-1(1)Walsh序的離散Walsh函數(shù)例:N=8,n=0,1,,7,t=0,1,,7

同理，可求出：WW(n,t)

Walsh序的Walsh矩陣定義:(2)Hadamard序的離散Walsh函數(shù)例:N=8,n=0,1,,7,t=0,1,,7計算WH(4,t)

這個序列可看成從連續(xù)的Hadamard序的Walsh函數(shù)WH（4，t）在等間距的N個點上的抽樣而得到。tWH（4，t）2.離散Walsh函數(shù)的定義2.4沃爾什(Walsh)變換

2.4.2Walsh函數(shù)(2)Hadamard序的離散Walsh函數(shù)Hadamard序的Walsh矩陣2.4沃爾什(Walsh)變換

2.4.2Walsh函數(shù)3.Walsh矩陣(1)Walsh序的Walsh矩陣2.4沃爾什(Walsh)變換

2.4.2Walsh函數(shù)3.Walsh矩陣(2)Hadamard序的Walsh矩陣2.4沃爾什(Walsh)變換

2.4.2Walsh函數(shù)2.4.2Walsh函數(shù)2.4沃爾什(Walsh)變換

(2)Hadamard序的Walsh矩陣一般來說：2.4沃爾什(Walsh)變換

2.4.2Walsh函數(shù)3.Walsh矩陣2.4.3一維離散Walsh變換(WT)1.定義正變換:反變換:注意:Walsh正、反變換的變換核都一樣！2.4沃爾什(Walsh)變換

2.4沃爾什(Walsh)變換

2.4.3一維離散Walsh變換(WT)2.一維離散Walsh變換的矩陣算法正變換:展開：令：IWT：WT：(1/N可以忽略不寫)注意:（1）正反變換的變換矩陣W都一樣；（2）W代表Walsh序的Walsh矩陣。2.4沃爾什(Walsh)變換

2.4.3一維離散Walsh變換(WT)注意:當變換矩陣為Hadamard矩陣HN時,稱為Hadamard序的

Walsh變換。變換矩陣如下寫法：IWHT：WHT：(1/N可忽略不寫)其中H為Hadamard序的Walsh矩陣。2.4沃爾什(Walsh)變換

2.4.3一維離散Walsh變換(WT)Walsh序的Walsh變換：IWT：WT：舉例:求Walsh序的一維離散Walsh變換F(u).反變換：正變換：舉例:求Walsh序的一維離散Walsh變換F(u)。用WHT。用WHT：用WT：結(jié)果為Walsh序結(jié)果為Hadamard序?qū)P(guān)系W序H序00122331IWT：WHT：Hadamard序的Walsh變換：3.Walsh序和Hadamard序的相互轉(zhuǎn)換變換結(jié)果為Hadamard序的，要轉(zhuǎn)換為Walsh序可以推導出以下轉(zhuǎn)換方法（N=4）：二進制碼格雷碼倒序碼

0000

00010110101111111001（W序）（H序）對應關(guān)系W序H序001223312.4沃爾什(Walsh)變換

2.4.3一維離散Walsh變換(WT)N=8時的轉(zhuǎn)換方法：二進制碼格雷碼倒序碼

000000

000001001100010011110011010010100110011101111111110101101111100001（W序）（H序）對應關(guān)系W序H序0014263243576571Hadamard序的Walsh函數(shù)Walsh序的Walsh函數(shù)對應關(guān)系W序H序0014263243576571連續(xù)Walsh函數(shù)的定義2.4沃爾什(Walsh)變換

2.4.3一維離散Walsh變換(WT)變換結(jié)果為Hadamard序的，要轉(zhuǎn)換為Walsh序?qū)P(guān)系W序H序00122331用WHT：2.4沃爾什(Walsh)變換

2.4.3一維離散Walsh變換(WT)4.一維Walsh變換的物理意義正如一維傅立葉變換（連續(xù)）是將一個函數(shù)分解成無窮個正弦波的疊加，而傅立葉幅度譜是這些正弦波的幅度系數(shù)。一維Walsh變換（連續(xù)）是將一個函數(shù)分解成無窮個Walsh函數(shù)（方波）的疊加，而F(u)是這些Walsh函數(shù)的幅度系數(shù).2.4沃爾什(Walsh)變換

2.4.3一維離散Walsh變換(WT)0123t0123t31822.4沃爾什(Walsh)變換

2.4.3一維離散Walsh變換(WT)2.4.4快速Walsh變換(FWT)1.快速Walsh-Hadamard變換以N=8為例,2.4沃爾什(Walsh)變換

2.4.4快速Walsh變換(FWT)2.4沃爾什(Walsh)變換

2.4.4快速Walsh變換(FWT)2.4沃爾什(Walsh)變換

FWHT流程圖(N=8)f(0)f(1)f(2)f(3)f(4)f(5)f(6)f(7)x1(0)x1(1)x1(2)x1(3)x1(4)x1(5)x1(6)x1(7)x2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)x3(0)x3(1)x3(2)x3(3)x3(4)x3(5)x3(6)x3(7)-1-1-1-1-1-1-1-1-1-1-1-1F（u）f(x)F（0）F（1）F（2）F（3）F（4）F（5）F（6）F（7）規(guī)律性:每個蝶形運算都是上加下減.結(jié)果為Hadamard序,必須轉(zhuǎn)換為Walsh序FWHT舉例:,用FWHT求其WT.01234567-1-1-1-1-1-1-1-1-1-1-1-1F（u）f(x)3.5-0.5-10-200046810-4-4-4-41216-4-4-8-80028-4-80-16000FWHT舉例:若求FH(u)的反變換,采用與正變換同一流程,只是不乘系數(shù)1/8.01234567-1-1-1-1-1-1-1-1-1-1-1-1F（u）f(x)3.5-0.5-10-20001.5-0.5-105.5-0.5-10-0.50.5-0.52.54.5-0.56.5-0.5,求f(x).也可推導出FWT的流程圖(N=8):規(guī)律性:先將f(x)進行碼位倒置.每次迭代中,偶數(shù)分組每個蝶形運算都是上減下加,奇數(shù)分組每個蝶形運算則是上加下減.結(jié)果為Walsh序.f(0)f(1)f(2)f(3)f(4)f(5)f(6)f(7)x1(0)x1(1)x1(2)x1(3)x1(4)x1(5)x1(6)x1(7)x2(0)x2(1)x2(2)x2(3)x2(4)x2(5)x2(6)x2(7)x3(0)x3(1)x3(2)x3(3)x3(4)x3(5)x3(6)x3(7)-1-1-1-1-1-1-1-1-1-1-1-1F（u）f(x)F（0）F（1）F（2）F（3）F（4）F（5）F（6）F（7）x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)2.快速Walsh變換（FWT）0123456719513-1-1-1-1622-4-400-2-228-160-8000-4-1-1-1-1-1-1-1-1-1-1-1-1F（u）f(x)3.5-20-1000-0.504261537FWT舉例:,用FWT求其WT.快速Walsh反變換與正變換用同樣流程2.4.5二維離散Walsh變換1.定義:正變換:反變換:注意:正變換和反變換的變換核都一樣。變換核是可分離的和對稱的。2.4沃爾什(Walsh)變換

2.矩陣算法: