數(shù)字圖像處理課件(岡薩雷斯第三版).ppt

《數(shù)字圖像處理課件(岡薩雷斯第三版).ppt》由會員分享，可在線閱讀，更多相關(guān)《數(shù)字圖像處理課件(岡薩雷斯第三版).ppt（133頁珍藏版）》請在裝配圖網(wǎng)上搜索。

數(shù)字圖像處理 Digital Image Processing,合肥工業(yè)大學(xué)理學(xué)院 信息與計算科學(xué)系 二零零九年,內(nèi)容提要,八周教學(xué)內(nèi)容依次如下： 第1、2章 緒論、圖象處理的基本概念。 第3、4章 空域和頻域變換 第5、8章 圖象增強(qiáng)和圖象復(fù)原。,第6章 圖象編碼 第7、9章 圖象分割和形態(tài)學(xué)。 第10章 其他,第1章 緒論,1.1 從圖象到圖像工程 圖象和數(shù)字圖象 圖象技術(shù)和圖象工程 相關(guān)學(xué)科和領(lǐng)域 1.2 圖象處理和分析 圖象處理和分析系統(tǒng) 圖象采集、顯示、存儲、通訊、處理和分析模塊,圖象處理,圖象分析,圖象理解,,,,抽象程度,,數(shù)據(jù)量,圖象基礎(chǔ),,1.1.1 圖象和數(shù)字圖象 什么是圖象？ 圖象(image)是泛指照片、動畫等等形成視覺景象的事物。圖象與計算機(jī)圖形學(xué)中的圖形的區(qū)別是：計算機(jī)圖形學(xué)是從建立數(shù)學(xué)模型到生成圖形，而圖象通常是指從外界產(chǎn)生的圖形。 客觀世界是三維空間，但一般圖象是二維的。二維圖象在反映三維世界的過程中必然丟失了部分信息。即使是記錄下來的信息也可能有失真，甚至于難以識別物體。因此，需要從圖象中恢復(fù)和重建信息，分析和提取圖象的數(shù)學(xué)模型，以至于形成人們對于圖象記錄下的事物有正確和深刻的認(rèn)識。這個過程就成為圖象處理過程。,1.1 從圖象到圖像工程,為什么需要數(shù)字圖象(digital image )？ 普通圖象包含的信息量巨大，需要使用計算機(jī)對圖象進(jìn)行處理。因此，需要把普通圖象轉(zhuǎn)變成計算機(jī)能處理的數(shù)字圖象?，F(xiàn)在的數(shù)碼相機(jī)可以直接地把視覺圖象變成數(shù)字圖象。數(shù)字圖象類似于光柵圖形，由有限行和有限列組成。每個基本單元叫做一個象素(pixel)。三維圖象的象素又叫做體素(voxel)。通常的二維數(shù)字圖像是一個矩型，可以用一個二維數(shù)組 I(x,y) 來表示，其中 x,y是二維空間中的某坐標(biāo)系的坐標(biāo)，I(x,y)表示圖像在該點(diǎn)處的灰度值等性質(zhì)。彩色可以是紅綠藍(lán)三個單色的一定灰度值的合成。一般來說，這些坐標(biāo)和灰度值是實數(shù)，不僅依賴于坐標(biāo)系的選取，而且依賴于灰度值的度量單位。但是，數(shù)字計算機(jī)只可能表示有限字長的有限個數(shù)字。所以必須把灰度值離散化。簡單地說，數(shù)字圖象等同于一個整數(shù)值的有限矩陣。數(shù)字圖像是數(shù)字圖像處理和分析的對象。,左邊的圖象是圖象處理技術(shù) 中常用來檢驗計算機(jī)算法的 實際效果的標(biāo)準(zhǔn)圖象。 這幅圖象的名稱是lenna。它 是由一組數(shù)字組成的。原圖象 的寬和高都是256個象素，每 象素有八位。它在BMP格式下 有約66K字節(jié)的大小。,數(shù)字圖象處理的簡史 數(shù)字圖象的產(chǎn)生遠(yuǎn)在計算機(jī)出現(xiàn)之前。最早有電報傳輸?shù)臄?shù)字圖象。六、七十年代，隨著計算機(jī)硬件的發(fā)展和快速傅立葉變換算法的發(fā)現(xiàn)使得用計算機(jī)能夠處理圖象。八十年代開始處理三維圖象，九十年代以來，隨著計算機(jī)性能的大幅提高和廣泛使用，圖象處理技術(shù)已經(jīng)涉及社會的各個角落。圖象逐漸在傳播媒體中占據(jù)了主導(dǎo)地位，產(chǎn)生的許多的新行業(yè)新商機(jī)。未來圖象處理的發(fā)展是不可限量的。數(shù)字圖象處理屬于計算機(jī)科學(xué)，但是它的90%依賴于數(shù)學(xué)。從這個特點(diǎn)來看，對于本專業(yè)的學(xué)生來說，數(shù)字圖象處理技術(shù)是一個十分理想的發(fā)展方向。,1.1.2 圖象技術(shù)和圖象工程,哪些屬于圖象技術(shù)？ 圖象技術(shù)是與圖象有關(guān)部門的技術(shù)的總稱。它是一類綜合技術(shù)工程。它包括圖象的采集、獲取、編碼、存儲和傳輸、圖象的生成、顯示和輸出、圖象的變換、增強(qiáng)、恢復(fù)和重建、圖象的分割、目標(biāo)的檢測、表達(dá)和描述、特征的提取、圖象的分類、識別、圖象模型的建立和匹配、圖象和場景的理解。 狹義的數(shù)字圖象處理是指圖象的增強(qiáng)、恢復(fù)和重建，操作的對象是圖象的象素，輸出的是圖象。,什么是圖像工程？（廣義的數(shù)字圖像處理） 它是由圖像處理、圖像分析和圖像理解三個系統(tǒng)所組成。圖像處理包括圖像采集和從圖像到圖像的變換，以改善主觀的視覺效果和為圖像分析和圖像理解作初步的處理。圖像分析是從圖像中取出感興趣的數(shù)據(jù)，以描述圖像中目標(biāo)的特點(diǎn)。圖像理解是在圖像分析的基礎(chǔ)上研究各目標(biāo)的性質(zhì)和相互關(guān)系，以得出圖像內(nèi)容的理解和對原場景的解釋。圖像處理、圖像分析和圖像理解是處在從低到高的三個不同的抽象程度上的過程。本課程著重于圖像處理和分析系統(tǒng)。,圖像處理,圖像理解,圖像分析,,,抽 象 程 度,數(shù) 據(jù) 量,圖像,數(shù)據(jù),符號,,,,,,1.1.3 相關(guān)學(xué)科和領(lǐng)域,圖象工程是一門系統(tǒng)地研究各種圖象理論、技術(shù)和應(yīng)用的交叉學(xué)科。 從它的研究方法看，它與數(shù)學(xué)、物理學(xué)、生物學(xué)、心理學(xué)、電子學(xué)、計算機(jī)科學(xué)可以互相借鑒，從它的研究范圍看，它與模式識別、計算機(jī)視覺、計算機(jī)圖形學(xué)等學(xué)科交叉。,1.2 圖象處理和分析,1.2.1 圖象處理和分析系統(tǒng) 圖像處理和分析系統(tǒng)包括如下模塊：圖像采集模塊、圖像顯示模塊、圖像存儲模塊、圖像通訊模塊和圖像處理和分析模塊。 1.2.2 模塊 圖象采集模塊 CCD 圖象顯示模塊 CRT，LCD 圖象存儲模塊 內(nèi)存、幀緩存、硬盤 圖象通訊模塊 LAN、WAN 圖象處理和分析模塊,圖象文件的數(shù)據(jù)結(jié)構(gòu),一個完整的圖象處理程序的基本功能有:打開圖象文件、顯示圖象、對圖象文件進(jìn)行指定的處理、存儲圖象文件。由于圖象文件比較大，通常需要在儲存前進(jìn)行壓縮。所以打開和存儲圖象文件涉及到文件的格式。 圖象文件的格式 圖像文件指包含圖像數(shù)據(jù)的文件。文件內(nèi)除圖像數(shù)據(jù)本身以外，一般還有圖像的描述信息，以便圖像的讀取和顯示。表示圖像常用矢量形式或光柵形式。 矢量形式中圖像用一系列線段或線段的組合體來表示，線段的灰度可以不同，組合體的各部分可用不同的灰度來填充。矢量形式文件中有一系列的命令和數(shù)據(jù)，執(zhí)行的結(jié)果是畫出圖像來。,圖像數(shù)據(jù)文件主要是用光柵形式,即圖像是一些圖像點(diǎn)的集合，比較適合變化復(fù)雜的圖像。它的主要缺點(diǎn)是缺少對象和像素點(diǎn)之間的聯(lián)系,且在伸縮圖像的過程中圖像會改變。例如，常見的圖象文件類型有bmp,jpg等等。圖象處理的程序必須考慮圖象文件的格式，否則無法正確地打開和保存圖象文件。 pgm格式 美國的許多大學(xué)用pgm格式，避免使用壓縮文件格式，對初學(xué)者來說是很方便的。下面是一幅該格式的圖象。,這是一幅pgm格式的彩色照片,這是pgm格式彩色照片16進(jìn)位制部分代碼。原代碼是不分行的字符串。這里寫成分行的形式 (注意：LF=換行；SP=空格； #=注解行)： 0x50 0x35 0x0A 表示P5 (LF); 0x23 0x20 0x20 0x49 …0x0A表示#(SP)(SP)I…(LF) ; 0x36 0x34 0x30 0x20 0x34 0x38 0x30 0x0A 表示640(SP)480(LF); 0x32 0x35 0x35 0x0A 表示255(LF) 0x27 0x27 … 表示23, 23,…(像素灰度值),………………………………… …………………………………,這幅圖象文件的解碼:,P5 # Imported from SUN image: LEGGO_HOUSE_1.0.intensity 640 480 255 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x26 0x27 0x27 0x27 0x28 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x26 0x27 0x26 0x27 0x28 0x27 0x27 0x26 0x27 0x27 0x27 0x28 0x27 0x27 0x27 0x27 0x27 0x27 0x28 0x28 0x27 0x28 0x29 0x28 0x27 0x28 0x28 0x28 0x27 0x27 0x27 0x27 0x27 0x27 0x27 0x28 0x27 0x28 0x28 0x28 0x28 0x28 0x28 0x28 0x28 0x28 0x29 0x29 0x29 0x28 0x28 0x28 0x28 ……………………………………………………………….,pgm格式的數(shù)字圖像文件是美國計算機(jī)科學(xué)專業(yè)圖像處理教學(xué)和研究的常用格式，雖然文件體積比較大，但是像素直接與數(shù)字相聯(lián)系，易于檢查和修改。它由兩部分組成： 1、第一部分是文件頭，它由若干行組成： 第一行說明文件的類型，例如，P2（表示黑白圖像）或P5（表示彩色圖像）； 接著是以#開頭的注解行，在軟件打開圖像時不執(zhí)行注解行，可以沒有注解行，或有多個以#開頭的注解行； 注解行后的第一行指定數(shù)字圖像的大小，例如，640 480（寬640個像素，高480個像素，中間有一個空格）； 接下來的一行指定圖像的灰度等級，例如，255。各行的結(jié)尾沒有標(biāo)點(diǎn)符號。 2、第二部分是不再分段的位圖列陣，例如，在256灰度的場合，P2類型是一個像素一個字節(jié)（8位）， P5類型是一個像素三個字節(jié)（R、G、B各8位）。,bmp(Bitmap)格式,BMP(Bitmap-File)圖形文件是Windows采用的圖形文件格式，在Windows環(huán)境下運(yùn)行的所有圖象處理軟件都支持BMP圖象文件格式。Windows系統(tǒng)內(nèi)部各圖像繪制操作都是以BMP為基礎(chǔ)的。 Windows 3.0以前的BMP圖文件格式與顯示設(shè)備有關(guān)，因此把這種BMP圖象文件格式稱為設(shè)備相關(guān)位圖DDB(device-dependent bitmap)文件格式。 Windows 3.0以后的BMP圖象文件與顯示設(shè)備無關(guān)，因此把這種BMP圖象文件格式稱為設(shè)備無關(guān)位圖DIB(device-independent bitmap)格式（注：Windows 3.0以后，在系統(tǒng)中仍然存在DDB位圖，象BitBlt()這種函數(shù)就是基于DDB位圖的。,bmp(Bitmap)格式 bmp格式又稱位圖文件。由三部分組成：位圖文件頭、位圖信息和位圖列陣。位圖文件頭有54個字節(jié)長，它給出文件的類型、大小和位圖的起始位置等。位圖信息給出圖像的長、寬和每個像素的位數(shù)（1，4，8，24）、壓縮方法、目標(biāo)設(shè)備的水平和垂直分辨率。位圖列陣給出原始像素的值。另外，有一些常用的壓縮文件格式，如：GIF(8位)、TIFF、JPEG等等。 下面是一個Matlab程序,% 打開蝴蝶圖象,進(jìn)行Fourier變換 h=imread(butterfly.jpg); % open an image figure; imshow(h); % 因為圖像的格式uint8不能做加減法, % 所以需要把格式uint8變成格式double h=double(h); [m,n,p]=size(h); hf=fftshift(fft2(h)); % 2D Fourier變換, 得到2D復(fù)數(shù)值圖像 hfa=log(abs(hf)); % 模的圖像,用log來調(diào)整灰度的對比度 % 求出模的灰度最大值，從而把其灰度的值域變?yōu)閇0，255] m=max(max(max(hfa))); hfa=hfa*255/m; figure; imshow(uint8(hfa)); Imwrite(uint8(hfa),’butterfly_fft.jpg’,’jpg’);,補(bǔ)充：圖象和視覺基礎(chǔ),2.1 概論和綜述 2.2 人眼與亮度視覺 2.3 顏色視覺 2.4 光度學(xué)和成象模型 2.5 成象變換 2.6 采樣和量化 2.7 象素間聯(lián)系 2.8 算術(shù)和邏輯運(yùn)算 2.9 坐標(biāo)變換,第2章 圖象和視覺基礎(chǔ),2.1 概論和綜述 該基礎(chǔ)包括視覺基礎(chǔ)、成像基礎(chǔ)和圖像基礎(chǔ)三部分： 視覺基礎(chǔ)（人眼與亮度視覺，顏色視覺） 成像基礎(chǔ)（模型、幾何和采樣量化） 圖像基礎(chǔ)（像素間聯(lián)系、圖像運(yùn)算和圖像坐標(biāo)變換） 注意： 視覺：指光對感官的刺激和視覺系統(tǒng)的感覺。 視知覺：指如何通過視覺形成關(guān)于外部世界的表象。,2.2 人眼與亮度視覺,2.2.1 人眼成象 人的眼球是一個復(fù)雜的視覺器官。眼球的前部有晶狀體，相當(dāng)于照相機(jī)的鏡頭。眼球內(nèi)側(cè)的后部有視網(wǎng)膜。視網(wǎng)膜表面分布著兩種感光細(xì)胞：錐細(xì)胞和柱細(xì)胞。眼內(nèi)有六、七百萬的錐細(xì)胞，它們對明亮的光和顏色很敏感。人眼借助于錐細(xì)胞來區(qū)分細(xì)節(jié)，因為每個錐細(xì)胞都連到神經(jīng)末梢。錐細(xì)胞的視覺稱為適亮視覺。眼內(nèi)有75萬到150萬柱細(xì)胞。它們分布面大，且?guī)讉€柱細(xì)胞連到一個神經(jīng)末稍。分辨率低，主要提供整體視覺印象。雖然它們對顏色不敏感，但是對弱光較敏感。柱細(xì)胞的視覺稱為適暗視覺。 視網(wǎng)膜的中心是中央凹，面積約1.5?1.5mm2，錐細(xì)胞的密度達(dá)到150000個/mm2,是眼內(nèi)最敏感的區(qū)域。,人眼的構(gòu)造,人眼成像,錐細(xì)胞和柱細(xì)胞的密度和分布,2.2.2 亮度適應(yīng)和區(qū)分,主觀亮度和主觀適應(yīng)性 由于數(shù)字圖象以客觀亮度顯示圖象，人眼以主觀亮度感受取得視覺，所以人眼的亮度適應(yīng)性影響了圖象處理的結(jié)果。人眼的視覺系統(tǒng)能適應(yīng)的光的亮度等級從可以看見的昏暗到眩目相差能達(dá)到1010等級。但是人眼并不能同時在這么大的范圍內(nèi)看清物體，而只能在同一時間內(nèi)適應(yīng)一個小的亮度變化范圍（106等級）。,在一定條件下，一個視覺系統(tǒng)當(dāng)前的敏感度叫做亮度適應(yīng)級。這個敏感度是用實驗來驗證的。在實驗中，逐漸增加光照射的強(qiáng)度I，改變量為?I，達(dá)到多個觀察者能感知的程度， 當(dāng)有一半的人感知增加時的?I/I成為Weber ratio,作為視覺系統(tǒng)當(dāng)前的敏感度。在很強(qiáng)的光下，需要改變較強(qiáng)的光照射才能使多個觀察者感知；相反，在某強(qiáng)度光照下，些微的光強(qiáng)度變換就會使人感知。,人眼的主觀亮度是非線性的，例如Mach帶,人眼的光學(xué)錯覺,2.3 顏色視覺,根據(jù)人眼的 結(jié)構(gòu)，所有 的顏色是三 種基本顏色 的不同組合．,所有的顏色可以 看作是三種基本 顏色的迭加，也 可以看作三種補(bǔ) 色（從白色中除 去某種顏色）的 迭加,顏色的三種基本 特征：灰度、色 調(diào)和飽和度，后 兩者又稱色度。 灰度與物體的反 射率成正比；色 調(diào)與光照中主要 光譜有關(guān)；飽和 度與色調(diào)的純度 有關(guān)。組成顏色 C的三個刺激量 X，Y，Z所占的 百分比數(shù)為x,y,z x = X/(X+Y+Z), y = Y/(X+Y+Z), z = 1 – x – y.,,2.5 成像變換,設(shè)W(X,Y,Z)是3D空間中的任意點(diǎn)的坐標(biāo),Z?. 根據(jù)相似三角形的性質(zhì)， x/? = X/(?-Z), y/? = Y/(?-Z), x = ?X/(?-Z), y = ?Y/(?-Z) 利用點(diǎn)wh齊次坐標(biāo)(kX, kY, kZ, k),令 1 0 0 0 P= 0 1 0 0 0 0 1 0 0 0 -1/? 1 ch = Pwh = P(kX, kY, kZ, k) =(kX, kY, kZ, -(k/?)Z+k）= (x,y,z,1) x = kX/(-k/?Z+k)=?X/(?-Z), 同理求得y和z,,,x,Z,?,(X,Y,Z),,,,,0,wh = P-1ch 1 0 0 0 P-1= 0 1 0 0 0 0 1 0 0 0 1/? 1 wh = P-1 (x,y,0,1) = (x,y,0,1). 其中沒有坐標(biāo)分量z，所以無法表示3D的點(diǎn)． 如果能知道額外的深度信息z,那么就能表示3D的點(diǎn)， (X,Y,Z,1) = wh = P-1(x,y,z,1) = (x,y,z, z/?+1). 其中， X = ?x/(?+z), Y = ?y/(?+z), Z = ?z/(?+z),,2.6 采樣和量化,一幅圖像需要經(jīng)過離散化成為數(shù)字圖像后才能被計算機(jī)處理。圖像的空間坐標(biāo)的離散化叫做空間采樣,灰度的離散化叫做灰度量化。采樣分為均勻采樣和量化和非均勻采樣和量化。假設(shè)圖像是一個長方形。在平面上取M?N個大小相同的網(wǎng)格，并把灰度分成G個等級。取各網(wǎng)格中的某點(diǎn)處的灰度值最接近的整數(shù)作為該網(wǎng)格的灰度。通常，取M=2m, N=2n和G=2k。則存儲一幅圖像的需要的位數(shù)等于b=MNk。例如，一幅128?128、64個灰度等級的圖像需要220位，512?512、256個灰度等級的圖像需要226位。采樣的個數(shù)和灰度等級的選取與分辨率和儲存的能力兩者有關(guān)，需要綜合考慮。例如： 圖像空間分辨率變化產(chǎn)生的效果。 圖像灰度分辨率變化產(chǎn)生的效果。 圖像空間和灰度分辨率同時變化產(chǎn)生的效果。,圖像空間分辨率變化產(chǎn)生的效果,圖像灰度分辨率變化產(chǎn)生的效果,圖像灰度分辨率變化產(chǎn)生的效果（2）,非均勻采樣和量化,對給定的空間分辨率，圖像的質(zhì)量可以根據(jù)圖像特性利用自適應(yīng)的采樣過程來改進(jìn)。例如，在灰度變化顯著的有很多細(xì)節(jié)的區(qū)域應(yīng)當(dāng)采用較密的采樣。又例如，可以計算所有灰度值出現(xiàn)的頻率。若某范圍內(nèi)的灰度值出現(xiàn)頻繁，而在其他范圍內(nèi)灰度值出現(xiàn)較稀，則在該范圍內(nèi)量化灰度就要較密，在其他范圍內(nèi)較稀。,2.7 像素間聯(lián)系,像素有四鄰域N4和八鄰域N8。 像素的連通有4-連接、8-連接和混合連接(m-連接)。稱點(diǎn)r和p是混合連接，如果r和p是4-連接的，或者r與p是8-連通的但不是4-連通的?；旌线B接避免了8-連通所產(chǎn)生的歧義。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,等價關(guān)系和傳遞閉包,定義：在集合A上的二元關(guān)系R,記為aRb，a,b?A,稱為等價關(guān)系，如果R具有如下性質(zhì)： 自反性 對每個a,成立aRa; 對稱性aRb當(dāng)且僅當(dāng)bRa; 傳遞性 aRb和bRc蘊(yùn)涵著aRc。 可以記aRb為(a,b). 例如用R表示4-連接。則自反性蘊(yùn)涵 對角元都是一。 例如R={(a,a), (a,b), (b,d),(d,b),(c,e)} 可以得到二值矩陣的表示。由傳 遞性，(a,b)和(b,d)蘊(yùn)涵(a,d)。包涵 這些隱含關(guān)系的集合稱為傳遞閉包 記為R+,a b c d e 1 1 0 0 0 a 0 0 0 1 0 b R= 0 0 0 0 1 c 0 1 0 0 0 d 0 0 0 0 0 e,,a b c d e 1 1 0 1 0 a 0 1 0 1 0 b R+= 0 0 0 0 1 c 0 1 0 1 0 d 0 0 0 0 0 e,例如R={(a,a), (a,b), (b,d),(d,b),(c,e)}時， R+=R ?{(a,d),(b,b),(d,d)} 一般地說， R+ = R + RR + R(RR) +… + Rn．,,距離量度 設(shè)有三個像素p,q,r，坐標(biāo)分別為(x,y), (s,t), (u,v)。D是距離，滿足： （1）D(p,q) ? 0, D(p,q) = 0 當(dāng)且僅當(dāng)p = q。 （2）D(p,q) = D(q,p)． （3）D(p,r) ? D(o,q) + D(q,r) 歐氏空間距離ＤE(p,q) = ((x-s)2 + (y-t)2)1/2 4-連通空間距離D4(p,q) = |x-s| + |y-t| 8-連通空間距離D4(p,q) = max{|x-s|, |y-t|} m-連通空間距離Dm(p,q)與路徑有關(guān)。,2.8 算術(shù)和邏輯運(yùn)算 圖像的四則運(yùn)算中是逐個像點(diǎn)進(jìn)行的。加法常用來去除噪音，減法常用在醫(yī)學(xué)成像，乘除法常用來矯正圖像中的灰度陰影。 常用的邏輯運(yùn)算有 （1）與（AND） （2）或（OR） （3）補(bǔ)（NOT) 以上運(yùn)算既可用于整幅圖像的運(yùn)算，也可以用于鄰域運(yùn)算。例如，一點(diǎn)及其８-鄰域的算術(shù)平均作為該點(diǎn)的新值?，F(xiàn)在常用算術(shù)和邏輯運(yùn)算的單元ALU來加速運(yùn)算。,2.9 坐標(biāo)變換 請復(fù)習(xí)已學(xué)過的教材．,第3章 象素空間關(guān)系,圖象是由象素組成。圖象以象素為單位建立坐標(biāo)系。通常是x軸向左，y軸向下。 圖象的坐標(biāo)變換就是象素的坐標(biāo)變換。所謂空間變換就是把象素從一個空間變換到另一個空間的坐標(biāo)變換。 坐標(biāo)變換的一個應(yīng)用是對圖象的幾何失真進(jìn)行校正。,一個象素的鄰域是指該象素周圍的象素集合。 一個象素p的周圍有八個象素，它們共同組成了該象素的8-鄰域N8(p) 。一個象素與上下左右的四個象素組成了4-鄰域N4(p)。一個象素與四個角上的象素組成了對角鄰域ND(p)。 同類灰度的象素間的鄰接，連接和連通問題： 兩個象素彼此落在對方的4-鄰域內(nèi)，稱為4-連接 兩個象素彼此落在對方的8-鄰域內(nèi)，稱為8-連接 如果兩個象素或者是4-連接，或者不是4-連接但落在對方的對角鄰域ND(p)內(nèi)，那么稱為混合連接（m-連接）。,3.1 象素間聯(lián)系,,,,,,,,,,混合連接可以避免8-連接造成的多路問題。 兩個象素集合的連通是指它們在指定的鄰域內(nèi)有一條通路。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,例如圖中的左上角和右下角 按4-連接是不連通的； 按m-連接是連通的； 按8-連接是連通的,但是道路不是唯一的。,兩個象素p和q之間的距離即滿足下列三個條件的一個函數(shù)D： D(p,q) ? 0，當(dāng)且僅當(dāng)p=q時D(p,q)=0. D(p,q)= D(q,p), D(p,q) +D(q,r) ? D(p,r).,DE(p,q)表示p=(x_p,y_p)和q =(x_q,y_q)之間的歐氏距離 DE(p,q) = [(x_p – x_q)2 + (y_p – y_q)2]1/2 D4(p,q)表示1-范數(shù)下的距離 D4(p,q) = |x_p – x_q|+ |y_p – y_q|. D8(p,q)表示?-范數(shù)下的距離 D4(p,q) = max{|x_p – x_q|,|y_p – y_q|}.,1,0,1,1,1.4,1,1.4,1.4,1.4,0,1,1,1,1,2,2,2,2,0,1,1,1,1,1,1,1,1,,,,,,,,,1,,,1,1,1,1,1,1,1,1,1,1,1,1,1,1,最右邊的圖中象素到邊界的距離是多少？,各象素到中心的距離D：,3.2 基本坐標(biāo)變換,在計算機(jī)圖形學(xué)中已經(jīng)講過?；镜淖鴺?biāo)變換是平移、伸縮、旋轉(zhuǎn)。,,,,,,,,,復(fù)雜坐標(biāo)變換是它們的級連。,錯切是三種基本變換的乘積嗎？,3.3 形態(tài)變換,3.3.1 變換體系 1、形態(tài)變換及其分類 形態(tài)變換是將平面區(qū)域映射到平面區(qū)域的變換。,形態(tài)變換,表、規(guī)則,解析式,非連續(xù),連續(xù),不光滑,光滑,線性,非線性,仿射變換,歐氏變換,剛體變換,相似變換,平移變換,旋轉(zhuǎn)變換,放縮變換,,,,,,,,,,,,,,,,點(diǎn)p到q的投影變換,可以寫成,其中A是2?2矩陣。投影變換可以寫成非奇異三階齊次矩陣的形式。注意：一般地說，投影是二階的非線性變換，但是都可以寫成三階矩陣的齊次形式。,仿射變換是一個非奇異的線性變換接上一個平移變換：,或?qū)懗?仿射變換的性質(zhì),仿射變換把原點(diǎn)映射為(t1,t2,1)，一般不再是原點(diǎn)。所以一般的仿射變換不是線性變換。如果做一個平移變換，使上面公式中的t = 0，那么仿射變換就是任何的非奇異矩陣A。另一方面，仿射變換的形式也說明它不包含投視投影。因此，它是三種基本變換的連乘，而具有如下的性質(zhì)。 （1）仿射變換將有限點(diǎn)映射成有限點(diǎn)。 （2）仿射變換將直線變成直線。 （3）仿射變換將平行直線映射成平行直線。 （4）當(dāng)區(qū)域P和Q是沒有退化的三角形時，有唯一的仿射變換A將P變成Q。,特殊的仿射變換：相似變換 當(dāng)上述仿射變換中A=sR時稱為相似變換，其中，s是實數(shù)，R是旋轉(zhuǎn)變換。 當(dāng)s=?1和R為正交矩陣時上述仿射變換稱為剛體變換，屬于等距變換。 當(dāng)s=1和R為正交矩陣時上述仿射變換稱為歐氏變換。 仿射變換的另一種說法：一個經(jīng)過平移的非奇異線性變換。,3.4 幾何失真校正,采樣的過程中圖象中象素之間的空間位置可能發(fā)生變化，產(chǎn)生幾何失真。我們需要校正幾何失真。 設(shè)原圖象在(x,y)處的灰度為f(x,y)，失真后變成在(x?,y?)處的灰度g(x?,y?)。因此，校正幾何失真包括兩部分： （1）空間變換 把點(diǎn)(x?,y?)恢復(fù)到位置(x,y) （2）灰度插值 把灰度g(x?,y?)恢復(fù)到f(x,y)。,空間變換,設(shè)點(diǎn)(x?,y?)與(x,y)的關(guān)系是,最簡單的情況是線性：,較復(fù)雜的情況是二次的：,如果知道s(x,y)和t(x,y)的解析表達(dá)式，就可以通過求 反函數(shù)來得到x和y。,,,,,,,對于一個四邊形的空間變換，可以首先確定四個對應(yīng)頂點(diǎn)， 然后用雙線性插值的方法：,問題：怎樣用兩次線性插值來作呢？ 如果幾何失真的面積比較大，那么如果用分塊來 提高校正的效果呢？,灰度插值,盡管(x?,y?)坐標(biāo)分量是整數(shù)值，但是計算出來的新坐標(biāo)(x,y)未必有整數(shù)分量，而且確定新坐標(biāo)處的灰度值。,,,,,,,,,,,,,,,,,,,,有兩種方案：前向映射和后向映射 前向映射：把從實際采集的失真圖象的象素灰度值賦給原始 不失真圖象的象素。如果失真圖象的象素P映射到Q，Q落在 四個原始不失真圖象的象素之間，就取這四點(diǎn)處的灰度值作 雙線性插值，作為象素Q的灰度值。,后向映射：把灰度值從原始不失真圖象的象素P映射到實際采集的失真圖象的象素P?上。如果實際采集的象素Q落在四個象素P?（非整數(shù)點(diǎn)）之間，就取這四點(diǎn)P?的灰度值作雙線性插值，作為象素Q的灰度值。,,,,,,,,,,,,,,,,,,,,,,,,插值灰度的計算： -零階插值：取最近的點(diǎn)的灰度 -雙線性插值： -三次線性插值：,雙線性插值：,設(shè)(xi,yi),i=1,2,3,4,是按反時針方向包圍Q的矩形的四個象素。 先作,然后，,第4章 空域增強(qiáng)技術(shù),圖象增強(qiáng)技術(shù)是使圖象的某種指定效果更好。例如，使X透視照片更清晰。 分成兩大類：空域增強(qiáng)技術(shù)和頻域增強(qiáng)技術(shù)。其中，空域指象素組成的空間。 空域增強(qiáng)技術(shù)直接作用于象素?？梢员硎緸?g(x,y) = EH(f(x,y)) 其中f和g分別是增強(qiáng)前后的圖象.這個變換不改變象素的位置，僅改變象素的灰度f(x,y)。,4.1空間技術(shù)分類,如果變換EH僅用一個點(diǎn)，稱EH為點(diǎn)運(yùn)算（點(diǎn)處理）。如果變換EH還用到點(diǎn)(x,y)鄰域內(nèi)的點(diǎn),那么記變換EH為 g(x,y)=EH(f(x,y)，n)， 稱為模板處理。 點(diǎn)操作可以分為灰度操作和集合操作,它們僅根據(jù)該點(diǎn)的灰度和位置,分別改變原灰度為新灰度(稱為灰度變換或灰度映射)和原位置為新位置的象素. 灰度操作可以把不同的灰度變成同一個灰度,集合操作可以把不同位置變成同一個位置.因此,它們可能不是可逆的變換.,4.2 圖象間運(yùn)算,4.2.1 算術(shù)和邏輯運(yùn)算 算術(shù)運(yùn)算一般用于兩個象素p,q: p+q,p-q,p*q和p/q. 應(yīng)用: 圖象之間f(x,y)和h(x,y)的差異用減法求出 g(x,y) = f(x,y) – h(x,y). 圖象之加法可以消去噪音e(x,y)。設(shè)圖象信號為f(x,y) 加上噪音后變成gi(x,y) = f(x,y)+ei(x,y).假設(shè)噪音ei 互不相關(guān)和E(ei)=0,那么n幅圖象的平均將壓制噪音:,邏輯運(yùn)算 補(bǔ)NOT, 與AND, 或OR, 異XOR 應(yīng)用:檢測目標(biāo)的邊界,向右移動一個象素后,依次作與運(yùn)算、差運(yùn)算得到左邊界。類似做出上、下、左邊的邊界。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,直接灰度映射,4.3.1 灰度映射原理 將圖象中的灰度值按某種規(guī)律映射成新灰度。在對于彩色圖象做灰度映射時應(yīng)注意保持色調(diào)和飽和度相同，只改變亮度。（HSV）,,,t,0,原灰度,新灰度,,,,,s,典型灰度映射,圖象求反 對圖象求反是將原圖象的灰度值反轉(zhuǎn)。例如，黑底的照片變成白底的照片。設(shè)灰度有L個等級。原灰度是d,新灰度是L-1-d。,,,,L-1,L-1,0,原灰度,新灰度,,,d,,增強(qiáng)對比度 增加圖象的各部分的反差。例如，圖象落在灰度s1和s2之間的部分是感興趣的部分，而其他部分不重要。那么可以把灰度s1和s2之間的部分的灰度反差變大。,,,,,,,,,,S1,S2,L-1,0,L-1,動態(tài)范圍壓縮 原圖象的灰度范圍過大，因此，需要壓縮到可以顯示的堆度范圍。例如，t = C log(1+|s|). C為尺度比例常數(shù)。,,,,s,t,,,灰分切分 把某部分的灰度變得突出。,,,,,,,,s,t,直方圖變換,直方圖和積累直方圖 圖象的灰度統(tǒng)計稱為直方圖。假設(shè)圖象有n個象素，灰度等級有k = 0,1,…,L-1個。sk為第k個等級的象素的灰度，設(shè)該象素在圖象中共有nk個，那么該象素出現(xiàn)的頻率是 為了規(guī)范化，把sk限制在0到1內(nèi)。當(dāng)k跑遍0,1,…,L-1時，就給出了一個函數(shù)圖形，稱為直方圖。直方圖是一個1D的離散函數(shù)。 積累直方圖就是由前k等級之和所生成的積累直方圖。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,L-1,L-1,,,Ps(sk),EH(sk),k,k,直方圖均衡化 設(shè)ps(sk) = nk/n，0?sk ?1, k=0,1,…,L-1.即灰度sk的象素占全體象素的比例是ps(sk) 。令,EH(sk)是單調(diào)增加函數(shù)，它等于灰度在sk以下的象素所占的比例。可以寫出反函數(shù)：,,,,,,,,,,,,,sk,tk,,sk,tk,,,假設(shè)tk = EH(sk)=1/4，那么， 灰度sk映射到tk意味著tk=1/4 以下的灰度占象素總數(shù)的1/4。 如果tk = EH(sk)=1/2，那么tk=1/2 以下的灰度占象素總數(shù)的1/2。 即tk的直方圖是均勻分布。,直方圖的計算,直方圖均衡化的計算：假設(shè)原圖象有L個灰度，不妨記sk就是灰度k。 依次計算頻率p(k)＝nk/n, k=0,1,…,L-1. 計算積累直方圖EH(k), k=0,1,…,L-1. 用下式計算tk的近似值： 由于tk在零與一之間，應(yīng)該把tk映射到在[0,L-1]范圍內(nèi)的一個整數(shù)，所以用L-1乘以tk后取整,即[(L-1)tk]。由此來確定灰度k到[(L-1)tk]的灰度映射關(guān)系。,,的pk,直方圖的規(guī)定化,規(guī)定化即把圖象的直方圖變成指定的直方圖。 作法是先把它們都變成均衡化的直方圖，再把第一步得到的變換反轉(zhuǎn)過來使用。,變換反轉(zhuǎn)需要確定對應(yīng)的規(guī)則。 SML選使下式最小的k和l:,GML使用組映射規(guī)則，設(shè)有一個整數(shù)函數(shù)Ｉ(l), l=0,…, N-1，使得0?I(0) ?I(1) ?… ?I(N-1) ?M-1.現(xiàn)在確定能使,最小的I(l)。如果l＝０，將i=0,…,I(0)的ps(si)對應(yīng)到pu(u0), 否則，將i=I(l-1)+1,…,I(l)的ps(si)對應(yīng)到pu(ul).,４.5 線性濾波器,4.5.1 技術(shù)分類和實現(xiàn)原理 技術(shù)分類 根據(jù)功能分成平滑濾波和銳化濾波。 平滑濾波減弱和消除高頻分量，使圖象灰度平滑。 銳化濾波減弱和消除低頻分量，是圖象反差增大。 ２. 模板卷積 方形模板在圖象中漫游，中心對準(zhǔn)一個象素。,4.5.2 線性平滑濾波器 1. 鄰域平均 g(x,y) = 模板中象素灰度的平均 ２. 加權(quán)平均 g(x,y) = 模板中象素灰度的加權(quán)平均。 常用高斯分布來計算各系數(shù)值。常用小模板。,可選模板M=2n+1, n=2?+1。也有用3?作為窗口半徑。,4.6 非線性濾波,分成三個發(fā)展方向：邏輯、幾何和代數(shù)，分別基于集合、形狀和排序。下面介紹基于排序的方向。 4.6.1 非線性平滑濾波器 1-D中值濾波原理 非線性、基于模板。設(shè)模板尺寸Ｍ＝2r+1,r為半徑。 給定一維信號{fi}, I=1,2,…,N.則中值濾波的輸出為 gj = 數(shù)組fj-r,fj-r+1,…,f0,…,fj+r-1,fj+r的中值。 其中，fj的下標(biāo)在0到N之間。這意味著對該數(shù)組排序，然后 輸出一個數(shù)， 使它既不大于又不小于其中的r+1個數(shù)。 中值濾波能完全消除孤立的脈沖（零脈沖響應(yīng)）和不影響理想的階躍響應(yīng)。 能被中值濾波完全除去的脈沖的最大長度依賴于濾波器的模板長度Ｍ。,２. ２-D中值濾波原理 取模板尺寸n?n，對數(shù)組排序，然后取一個數(shù)，使它使它既不大于又不小于其中的n2/2個數(shù)。實際操作時，讓模板在圖象中游動。中值濾波能消除孤立的脈沖。 鄰域平均濾波器在去掉孤立脈沖時模糊了圖象，中值濾波器在去掉孤立脈沖時不影響圖象。但是，中值濾波不能去掉服從高斯分布的噪音。 ３. 中值濾波的模板 效果與模板的大小有關(guān)，也與模板中參與運(yùn)算的象素個數(shù)有關(guān)。用稀疏模板運(yùn)算速度較快。,４. 均值、中值和最頻值 最頻值是出現(xiàn)頻率最高的值。如果圖象有單個峰值的對稱直方圖，那么均值、中值和最頻值相等。如果圖象有單個峰值的直方圖，那么最頻值對應(yīng)最高峰，而中值比均值更接近最頻值。 ５. 序統(tǒng)計濾波器 中值濾波是序統(tǒng)計濾波器的特例，例如，最大值濾波器和最小值濾波器也是序統(tǒng)計濾波器。中點(diǎn)濾波器是最大值濾波器和最小值濾波器的平均。,4.6.2 非線性銳化濾波器 １. 微分方法可以銳化圖象。,用兩個差商來代替微分：,分別用１范數(shù)、２ 范數(shù)和?范數(shù)計算時,２. 銳化濾波器的通用性質(zhì) (1)零位移。銳化濾波器不改變邊緣的位置。應(yīng)具有反對稱性。 (2)消除均值。銳化濾波器均值為零。 (3) 無選擇性的微分。微分操作只對象素灰度敏感。 (4)對稱性質(zhì)。 ３. 最大最小銳化變換,最大最小銳化變換的迭代實現(xiàn)：,局部增強(qiáng),對圖象的一部分進(jìn)行增強(qiáng) 例如, 將圖象分成一系列子圖象,并對子圖象進(jìn)行直方圖等操作 利用局部的均值m和均方差? g(x,y) = A(x,y)[f(x,y)-m(x,y)]+m(x,y), 其中,A(x,y)=kM/?(x,y)稱為局部增益函數(shù),M為平均灰度,k為比例系數(shù).g(x,y)右邊的第一項能放大圖象的局部變化,第二項恢復(fù)均值.,第5章 基本圖象變換,5.1 基本圖象變換 5.2 可分離和正交圖象變換 5.3 傅里葉變換 5.4 沃爾什/哈達(dá)瑪變換 5.5 離散余弦變換 5.6 Radon變換,圖象變換,可分離變換,統(tǒng)計變換,傅氏變換,其他變換,霍特林變換,,5.2 可分離和正交圖象變換,1D變換:T(u)是f(x)的變換.,g(x,u)稱為正向變換核.反變換是,h(x,u)稱為反向變換核.,2D變換:T(u,v)是f(x,y)的變換.,如果核具有下列性質(zhì),則稱g是可分離核:,如果g1 = g2,那么,2D對稱可分離變換可以寫成兩個相繼的1D變換:,分別記S(x,v),f(x,y),g(y,v)和T(u,v)組成的矩陣為 S,F,A和T,那么,S(x,v)是A的第u行與F的第y列的乘積, 即S=AF,而T(u,v)是S的第u行與G的第v列的乘積,即T=SA. T = SA = AFA.,其中,F是N?N圖象,A是N?N對稱.取B為A的逆矩陣,那么, BTB = BAFAB = F. 如果B不等于A-1,那么F*= BAFAB是F的一個近似.,5.3傅里葉變換,離散的傅里葉變換和性質(zhì) 1、由1維傅里葉變換（FT）和逆變換的公式,,,離散的1維傅里葉變換（DFT）和逆變換的公式是,，u = 0, 1,…, N-1;,，x=0,1,…,N-1.,這里把f(x)理解為一個離散函數(shù)，,其中，,除了x=0,1,…,N-1處以外f(x)等于零。,因為F(u)是周期函數(shù)，u取值0,1,…,N-1時，exp[-2ju/N]以N為周期。所以F(u)是在整個頻率域內(nèi)有定義的。取且僅取一個周期就包含了足夠的原來f(x)的信息。特別地，,,離散的2維傅里葉變換（DFT）和逆變換的公式。,其中記,u=0,1,…, M-1, v=0,1,…,N-1; x=0,1,…,M-1, y=0,1,…,N-1.,分別為,這些公式的推導(dǎo)如下。以間隔?x和?y，從圖像中取M?N個樣本，x = 0,1,…,M; y = 0,1,…,N。同樣地，在圖像的傅里葉變換的像中，以間隔?u和?v，取M?N個樣本，u = 0,1,…,M; v = 0,1,…,N；使得?x?u = 1/M和?y?v = 1/N。,,,,這就完成了證明.,另一方面,,傅里葉變換的像是一個二維復(fù)數(shù)矩陣。它是,值得注意的是：顯示器不能正確地顯示F(u,v)。這是因為傅里葉變換的像是一個復(fù)數(shù)矩陣。必須分別顯示它的實部和虛部，或它的模和幅角。 二維DFT的性質(zhì)： 1、分離性,,因此，二維DFT可以用相繼的兩個一維的DFT來計算：,,2、平移性,傅里葉變換象在零頻率處為，它的模反映了背景光照的強(qiáng)度，通常是比較亮的。但是，由于空間坐標(biāo)是從左上角的(0,0)開始的，對應(yīng)零頻率的點(diǎn)也就落在頻率窗口的左上角，造成左上角比較亮。再由于傅里葉變換的周期性，在窗口的四個角處都比較亮。其實這四個角的頂點(diǎn)是同一個點(diǎn)。因此，希望把傅里葉變換象的中心（零頻率）移到窗口中心去。注意到傅里葉變換的u和v是從低頻到高頻排列的。當(dāng)取(u0,v0)為圖像作傅里葉變換后的像的中心時，即u0 = M/2, v0 = N/2時，根據(jù)上面的性質(zhì)，,,所以，只要先對f(x,y)作變換f(x,y)(-1)x+y，然后作傅里葉變換，就可以把傅里葉變換象的零頻率移到窗口中心去。反過來，當(dāng)把這樣的傅里葉變換后的像變回到原時間函數(shù)時，需要把所得到的f(x,y)再作變換f(x,y)(-1)x+y。這里有一個問題：圖象f(x,y)是灰度值，總是不小于零的。但是，f(x,y)(-1)x+y會交替的變號。如果用顯示器來顯示變號的灰度圖象，那么顯示的結(jié)果依賴于設(shè)備的設(shè)置。通常，顯示時負(fù)的灰度值自動取為零。進(jìn)一步，一幅灰度范圍在0-100內(nèi)的圖形未必比灰度范圍在0-255內(nèi)的圖形暗淡。這是因為在前一種情況下，顯示器可能自動地把最高的亮度賦予100灰度。換句話說，顯示器的自動設(shè)置可能會改變圖象的顯示結(jié)果。,1 3、 周期性和共扼對稱性 設(shè)M和N分別是橫縱軸的周期。,如果f是實函數(shù)，那么,,,事實上，,如果f是實函數(shù)，那么,,4、旋轉(zhuǎn)性質(zhì) 做變換 x = r cos?, y = r sin?,和u = w cos?，v = w cos?， 那么,,事實上，,5． 分配律 6． 尺度變換 7． 平均值 是 8． 一維卷積,,,的平均值。,,例如，設(shè)f(z) = ?[0,1](z), g(z)=0.5?[0,1](z)。那么，f(z)g(x-z) = 0.5?[0,1](z)?[0,1](x-z)中，當(dāng)且僅當(dāng)z和x-z都落在區(qū)間[0,1]內(nèi)的時候才是一，否則是零。0 ? z ? 1和 0 ? x-z ? 1。即 當(dāng)0 ? x ? 1時0 ? z ? x；當(dāng)1 x ? 2時x-1 ? z ? 1。 當(dāng)0 ? x ? 2時，f(z)g(x-z) = 0.5，否則等于零。 它們的卷積等于,,卷積有下列性質(zhì)：設(shè)F和G分別是f和g的傅里葉變換。則,,事實上，卷積經(jīng)過傅里葉變換，,,離散采樣的兩個函數(shù)的卷積問題需要考慮到周期的長度影響。假設(shè)兩個函數(shù)f和g有相同的周期M。根據(jù)卷積f*g的定義，該卷積也有相同的周期M。計算卷積時，只能使用f的一個周期內(nèi)的數(shù)值和g的一個周期內(nèi)的數(shù)值。如果f采樣A個f(0),f(1),…,f(A-1)，g采樣B個g(0),g(1),…,g(B-1)，隨著x的變化，乘積f(z)g(x-z)不等于零的長度是A+B-1。當(dāng)M?A+B-1時，該乘積才不會越出一個周期的范圍而造成重疊取樣。此時，為了便于使用離散卷積公式，補(bǔ)充規(guī)定 f(x) = 0 當(dāng)A ? x ? M-1, g(x) = 0當(dāng)B ? x ? M-1。 離散卷積公式是 ：,,x = 0,1,…,M-1。,相關(guān)性,,例如，設(shè)f(z) = ?[0,1](z), g(z)=0.5?[0,1](z)。那么， f(z)g(x+z) = 0.5?[0,1](z)?[0,1](x+z)， 當(dāng)且僅當(dāng)0 ? z ? 1和 0 ? x+z ? 1時才是一，否則是零。即 當(dāng)-1 ? x ? 0時-x ? z ? 1； 當(dāng)0 x ? 1時0 ? z ? 1-x。 當(dāng)- ? x ? 1時f(z)g(x+z) = 0.5，否則等于零。 它們的卷積等于,,快速傅里葉變換,我們推導(dǎo)快速傅里葉變換公式。假設(shè)N是2的冪，即N = 2n。記N = 2M。令,。,,,在已知WN的條件下，計算每一個F(?)至少需要作N次乘法和一次除法，計算所有的F(?)共需要作不少于N2次乘法。 改寫變換：,容易看出WN有“折半”的性質(zhì)：,,定義,,,,? = 0,1,…,M-1,我們還需要計算在? = M,M+1,…,N-1處的值。為此，注意到,,,? = 0,1,…,M-1,根據(jù)上面分析，我們只需要在M個點(diǎn)? = 0,1,…,M-1處分別求出 和 的值，并且每次用 乘以 ，就可以用公式(4)和(5)來計算在2M個點(diǎn) ? = 0,1,…,2M-1處 的值。公式(4)和(5)就是一維的快速傅里葉變換公式。,最后，我們證明FFT算法的時間復(fù)雜性是?(NlogN)。設(shè)計算一個有N個點(diǎn)的FFT算法的時間復(fù)雜性是T(N)。根據(jù)以上的公式，一個有N個點(diǎn)的FFT運(yùn)算分成兩個各有N/2點(diǎn)的FFT運(yùn)算，并且，其中的一個每次要與作一次乘法，共有?(N)次乘法，所以， T(N) = 2T(N/2) + ?(N)。 依此可得 T(N) = T(2n) = 2T(2n-1) + ?(2n) = 22T(2n-2) + 2?(2n) = …= n?(2n) = ?(NlogN)。,% open an image h=imread(butterfly.jpg); figure; imshow(h); % 因為圖像的格式uint8不能做加減法,所以需要把格式uint8變成double. h=double(h); [m,n,p]=size(h); %變成黑白圖像 if(p1) bw(:,:)=(h(:,:,1)+h(:,:,2)+h(:,:,3))/3; h=bw/3; end %調(diào)整灰度到0到255之間。否則 maxValue=max(max(h)); h1=h*255/maxValue; figure; imshow(uint8(h1));,% 2D Fourier變換和平移頻率0到中心, 得到2D復(fù)數(shù)值圖像 hf=fftshift(fft2(h)); % 畫出其模的圖像。如果直接用imshow(uint8(hf))將得到下面的圖象. hfa=log(abs(hf)); maxValue=max(max(hfa)); h2=hfa*255/maxValue; figure; imshow(uint8(h2)); % 低通濾波器（半徑平方在1000以內(nèi)） a=m/2; b=n/2; for i=1:m for j=1:n if((i-a)*(i-a)+(j-b)*(j-b)1000) hf(i,j)=0; end end end,hfa=log(abs(hf)); maxValue=max(max(hfa)); h3=hfa*255/maxValue; figure; imshow(uint8(h3)); ih=ifft2(fftshift(hf)); hfa=log(abs(ih)); maxValue=max(max(hfa)); h4=hfa*255/maxValue; figure; imshow(uint8(h4)); h2=h; for i=1:m-1 for j=1:n-1 h2(i,j)=h(i,j)-h(i+1, j+1); end end,hfa=log(abs(h2)); maxValue=max(max(hfa)); h5=hfa*255/maxValue; figure; imshow(uint8(h5));,3.4 Walsh 變換,令N是整數(shù)，n = log2N,,,其中，bk(z)是z的二進(jìn)制表達(dá)式中的第k位上的數(shù)字（k=0,1,…,n-1），它等于0或1。例如n=3時, z=4的二進(jìn)制數(shù) z= 1002 的b0(3)=0,b1(3)=0,b2(3)=1。 z=6的二進(jìn)制數(shù) z= 1102 的b0(3)=0,b1(3)=1,b2(3)=1。 g(6,4)=g(1102,1002)=(-1)0?1+1?0+1?0 =1. g(6,3)=g(1102,112)=(-1)0?0+1?1+1?1=1. g(6,2)=g(1102,102)=(-1)0?0+1?1+1?0=-1. g(6,4)=g(1102,12)=(-1)0?0+1?0+1?1=-1.,,可以看出：GN是對稱的，列和行都是兩兩正交的，如果用N-1/2代替N-1。則GN是正交矩陣。其逆是GN的轉(zhuǎn)置，即其自身。再考慮到正變換中采用N-1，所以逆變換是,,,一維Walsh變換是(u=0,1,…,N-1),快速的Walsh變換的公式是(M=N/2),二維的Walsh變換是,u=0,1,…,M-1.,3.4 Hadama 變換,令N是整數(shù)，n = log2N,,,其中，bk(z)是z的二進(jìn)制表達(dá)式中的第k位上的數(shù)字（k=0,1,…,n-1），它等于0或1。例如n=3時, g(6,4)=g(1102,1002)=(-1)0?0+1?0+1?1 =-1. g(6,3)=g(1102,112)=(-1)0?1+1?1+1?0=-1. g(6,2)=g(1102,102)=(-1)0?0+1?1+1?0=-1. g(6,4)=g(1102,12)=(-1)0?1+1?0+1?0=1.,,可以看出：Hadama變換是對稱正交的。逆變換是,,一維Hadama變換是(u=0,1,…,N-1),二維的Hadama變換是,8. 圖象恢復(fù),,8.2 退化模型和對角化,8.2.1退化模型,H,,,+,,,f(x,y),n(x,y),g(x,y),退化系統(tǒng)H滿足: ?常數(shù)k, a,b,有 線性 H(kf+g)=kH(f)+H(g) 位移不變性 H(f(x-a,y-b))=H(f(x,y)),8.2.2 退化模型的計算,1D場合 對f(x)和h(x)分別采樣A和B: f(x), x=0,1,…,A-1; h(x), x=0,1,…,B-1.用加零的方式延拓到M, M?A+B-1. 由模型,2D場合 對f(x,y)和h(x,y)分別采樣A?B和C?D,用加零的方式延拓到M?N, M?A+C-1和N?B+D-1.由模型,8.2.3 輪換矩陣的對角化,H可以寫成 H=WDW-1 其中W = (w0, w1, …, wM-1), wk是H的對應(yīng)于??k的特征向量.,