數(shù)字圖像處理

DigitalImageProcessing合肥工業(yè)大學(xué)理學(xué)院信息與計(jì)算科學(xué)系二零零九年1精選ppt內(nèi)容提要八周教學(xué)內(nèi)容依次如下：第1、2章緒論、圖象處理的基本概念。第3、4章空域和頻域變換第5、8章圖象增強(qiáng)和圖象復(fù)原。第6章圖象編碼第7、9章圖象分割和形態(tài)學(xué)。第10章其他2精選ppt第1章緒論1.1 從圖象到圖像工程圖象和數(shù)字圖象圖象技術(shù)和圖象工程相關(guān)學(xué)科和領(lǐng)域1.2 圖象處理和分析圖象處理和分析系統(tǒng)圖象采集、顯示、存儲(chǔ)、通訊、處理和分析模塊圖象處理圖象分析圖象理解抽象程度數(shù)據(jù)量圖象基礎(chǔ)3精選ppt1.1.1圖象和數(shù)字圖象什么是圖象？ 圖象(image)是泛指照片、動(dòng)畫等等形成視覺景象的事物。圖象與計(jì)算機(jī)圖形學(xué)中的圖形的區(qū)別是：計(jì)算機(jī)圖形學(xué)是從建立數(shù)學(xué)模型到生成圖形，而圖象通常是指從外界產(chǎn)生的圖形。 客觀世界是三維空間，但一般圖象是二維的。二維圖象在反映三維世界的過程中必然丟失了部分信息。即使是記錄下來的信息也可能有失真，甚至于難以識別物體。因此，需要從圖象中恢復(fù)和重建信息，分析和提取圖象的數(shù)學(xué)模型，以至于形成人們對于圖象記錄下的事物有正確和深刻的認(rèn)識。這個(gè)過程就成為圖象處理過程。1.1從圖象到圖像工程4精選ppt為什么需要數(shù)字圖象(digitalimage)？ 普通圖象包含的信息量巨大，需要使用計(jì)算機(jī)對圖象進(jìn)行處理。因此，需要把普通圖象轉(zhuǎn)變成計(jì)算機(jī)能處理的數(shù)字圖象。現(xiàn)在的數(shù)碼相機(jī)可以直接地把視覺圖象變成數(shù)字圖象。數(shù)字圖象類似于光柵圖形，由有限行和有限列組成。每個(gè)基本單元叫做一個(gè)象素(pixel)。三維圖象的象素又叫做體素(voxel)。通常的二維數(shù)字圖像是一個(gè)矩型，可以用一個(gè)二維數(shù)組I(x,y)來表示，其中x,y是二維空間中的某坐標(biāo)系的坐標(biāo)，I(x,y)表示圖像在該點(diǎn)處的灰度值等性質(zhì)。彩色可以是紅綠藍(lán)三個(gè)單色的一定灰度值的合成。一般來說，這些坐標(biāo)和灰度值是實(shí)數(shù)，不僅依賴于坐標(biāo)系的選取，而且依賴于灰度值的度量單位。但是，數(shù)字計(jì)算機(jī)只可能表示有限字長的有限個(gè)數(shù)字。所以必須把灰度值離散化。簡單地說，數(shù)字圖象等同于一個(gè)整數(shù)值的有限矩陣。數(shù)字圖像是數(shù)字圖像處理和分析的對象。5精選ppt左邊的圖象是圖象處理技術(shù)中常用來檢驗(yàn)計(jì)算機(jī)算法的實(shí)際效果的標(biāo)準(zhǔn)圖象。這幅圖象的名稱是lenna。它是由一組數(shù)字組成的。原圖象的寬和高都是256個(gè)象素，每象素有八位。它在BMP格式下有約66K字節(jié)的大小。6精選ppt數(shù)字圖象處理的簡史 數(shù)字圖象的產(chǎn)生遠(yuǎn)在計(jì)算機(jī)出現(xiàn)之前。最早有電報(bào)傳輸?shù)臄?shù)字圖象。六、七十年代，隨著計(jì)算機(jī)硬件的發(fā)展和快速傅立葉變換算法的發(fā)現(xiàn)使得用計(jì)算機(jī)能夠處理圖象。八十年代開始處理三維圖象，九十年代以來，隨著計(jì)算機(jī)性能的大幅提高和廣泛使用，圖象處理技術(shù)已經(jīng)涉及社會(huì)的各個(gè)角落。圖象逐漸在傳播媒體中占據(jù)了主導(dǎo)地位，產(chǎn)生的許多的新行業(yè)新商機(jī)。未來圖象處理的發(fā)展是不可限量的。數(shù)字圖象處理屬于計(jì)算機(jī)科學(xué)，但是它的90%依賴于數(shù)學(xué)。從這個(gè)特點(diǎn)來看，對于本專業(yè)的學(xué)生來說，數(shù)字圖象處理技術(shù)是一個(gè)十分理想的發(fā)展方向。1.1.2圖象技術(shù)和圖象工程7精選ppt哪些屬于圖象技術(shù)？ 圖象技術(shù)是與圖象有關(guān)部門的技術(shù)的總稱。它是一類綜合技術(shù)工程。它包括圖象的采集、獲取、編碼、存儲(chǔ)和傳輸、圖象的生成、顯示和輸出、圖象的變換、增強(qiáng)、恢復(fù)和重建、圖象的分割、目標(biāo)的檢測、表達(dá)和描述、特征的提取、圖象的分類、識別、圖象模型的建立和匹配、圖象和場景的理解。 狹義的數(shù)字圖象處理是指圖象的增強(qiáng)、恢復(fù)和重建，操作的對象是圖象的象素，輸出的是圖象。8精選ppt什么是圖像工程？（廣義的數(shù)字圖像處理） 它是由圖像處理、圖像分析和圖像理解三個(gè)系統(tǒng)所組成。圖像處理包括圖像采集和從圖像到圖像的變換，以改善主觀的視覺效果和為圖像分析和圖像理解作初步的處理。圖像分析是從圖像中取出感興趣的數(shù)據(jù)，以描述圖像中目標(biāo)的特點(diǎn)。圖像理解是在圖像分析的基礎(chǔ)上研究各目標(biāo)的性質(zhì)和相互關(guān)系，以得出圖像內(nèi)容的理解和對原場景的解釋。圖像處理、圖像分析和圖像理解是處在從低到高的三個(gè)不同的抽象程度上的過程。本課程著重于圖像處理和分析系統(tǒng)。圖像處理圖像理解圖像分析抽象程度數(shù)據(jù)量圖像數(shù)據(jù)符號9精選ppt1.1.3相關(guān)學(xué)科和領(lǐng)域圖象工程是一門系統(tǒng)地研究各種圖象理論、技術(shù)和應(yīng)用的交叉學(xué)科。 從它的研究方法看，它與數(shù)學(xué)、物理學(xué)、生物學(xué)、心理學(xué)、電子學(xué)、計(jì)算機(jī)科學(xué)可以互相借鑒，從它的研究范圍看，它與模式識別、計(jì)算機(jī)視覺、計(jì)算機(jī)圖形學(xué)等學(xué)科交叉。10精選ppt1.2圖象處理和分析1.2.1圖象處理和分析系統(tǒng) 圖像處理和分析系統(tǒng)包括如下模塊：圖像采集模塊、圖像顯示模塊、圖像存儲(chǔ)模塊、圖像通訊模塊和圖像處理和分析模塊。1.2.2模塊圖象采集模塊 CCD圖象顯示模塊 CRT，LCD圖象存儲(chǔ)模塊 內(nèi)存、幀緩存、硬盤圖象通訊模塊 LAN、WAN圖象處理和分析模塊11精選ppt圖象文件的數(shù)據(jù)結(jié)構(gòu)

一個(gè)完整的圖象處理程序的基本功能有:打開圖象文件、顯示圖象、對圖象文件進(jìn)行指定的處理、存儲(chǔ)圖象文件。由于圖象文件比較大，通常需要在儲(chǔ)存前進(jìn)行壓縮。所以打開和存儲(chǔ)圖象文件涉及到文件的格式。圖象文件的格式 圖像文件指包含圖像數(shù)據(jù)的文件。文件內(nèi)除圖像數(shù)據(jù)本身以外，一般還有圖像的描述信息，以便圖像的讀取和顯示。表示圖像常用矢量形式或光柵形式。 矢量形式中圖像用一系列線段或線段的組合體來表示，線段的灰度可以不同，組合體的各部分可用不同的灰度來填充。矢量形式文件中有一系列的命令和數(shù)據(jù)，執(zhí)行的結(jié)果是畫出圖像來。12精選ppt

圖像數(shù)據(jù)文件主要是用光柵形式,即圖像是一些圖像點(diǎn)的集合，比較適合變化復(fù)雜的圖像。它的主要缺點(diǎn)是缺少對象和像素點(diǎn)之間的聯(lián)系,且在伸縮圖像的過程中圖像會(huì)改變。例如，常見的圖象文件類型有bmp,jpg等等。圖象處理的程序必須考慮圖象文件的格式，否則無法正確地打開和保存圖象文件。

pgm格式 美國的許多大學(xué)用pgm格式，避免使用壓縮文件格式，對初學(xué)者來說是很方便的。下面是一幅該格式的圖象。13精選ppt這是一幅pgm格式的彩色照片14精選ppt這是pgm格式彩色照片16進(jìn)位制部分代碼。原代碼是不分行的字符串。這里寫成分行的形式(注意：LF=換行；SP=空格；#=注解行)：0x50

0x35

0x0A表示P5

(LF);0x230x200x200x49…0x0A表示#(SP)(SP)I…(LF);0x360x340x300x200x340x380x300x0A表示640(SP)480(LF);0x320x350x35

0x0A表示255(LF)0x270x27…表示23,23,…(像素灰度值)……………………………………15精選ppt16精選ppt這幅圖象文件的解碼:P5#ImportedfromSUNimage:LEGGO_HOUSE_1.0.intensity6404802550x270x270x270x270x270x270x270x270x270x270x270x270x270x260x270x270x270x280x270x270x270x270x270x270x270x270x270x270x270x270x270x270x270x270x270x260x270x260x270x280x270x270x260x270x270x270x280x270x270x270x270x270x270x280x280x270x280x290x280x270x280x280x280x270x270x270x270x270x270x270x280x270x280x280x280x280x280x280x280x280x280x290x290x290x280x280x280x28………………...17精選ppt

pgm格式的數(shù)字圖像文件是美國計(jì)算機(jī)科學(xué)專業(yè)圖像處理教學(xué)和研究的常用格式，雖然文件體積比較大，但是像素直接與數(shù)字相聯(lián)系，易于檢查和修改。它由兩部分組成：1、第一部分是文件頭，它由若干行組成：第一行說明文件的類型，例如，P2（表示黑白圖像）或P5（表示彩色圖像）；接著是以#開頭的注解行，在軟件打開圖像時(shí)不執(zhí)行注解行，可以沒有注解行，或有多個(gè)以#開頭的注解行；注解行后的第一行指定數(shù)字圖像的大小，例如，640480（寬640個(gè)像素，高480個(gè)像素，中間有一個(gè)空格）；接下來的一行指定圖像的灰度等級，例如，255。各行的結(jié)尾沒有標(biāo)點(diǎn)符號。2、第二部分是不再分段的位圖列陣，例如，在256灰度的場合，P2類型是一個(gè)像素一個(gè)字節(jié)（8位），P5類型是一個(gè)像素三個(gè)字節(jié)（R、G、B各8位）。18精選pptbmp(Bitmap)格式BMP(Bitmap-File)圖形文件是Windows采用的圖形文件格式，在Windows環(huán)境下運(yùn)行的所有圖象處理軟件都支持BMP圖象文件格式。Windows系統(tǒng)內(nèi)部各圖像繪制操作都是以BMP為基礎(chǔ)的。Windows3.0以前的BMP圖文件格式與顯示設(shè)備有關(guān)，因此把這種BMP圖象文件格式稱為設(shè)備相關(guān)位圖DDB(device-dependentbitmap)文件格式。Windows3.0以后的BMP圖象文件與顯示設(shè)備無關(guān)，因此把這種BMP圖象文件格式稱為設(shè)備無關(guān)位圖DIB(device-independentbitmap)格式（注：Windows3.0以后，在系統(tǒng)中仍然存在DDB位圖，象BitBlt()這種函數(shù)就是基于DDB位圖的。19精選ppt

bmp(Bitmap)格式

bmp格式又稱位圖文件。由三部分組成：位圖文件頭、位圖信息和位圖列陣。位圖文件頭有54個(gè)字節(jié)長，它給出文件的類型、大小和位圖的起始位置等。位圖信息給出圖像的長、寬和每個(gè)像素的位數(shù)（1，4，8，24）、壓縮方法、目標(biāo)設(shè)備的水平和垂直分辨率。位圖列陣給出原始像素的值。另外，有一些常用的壓縮文件格式，如：GIF(8位)、TIFF、JPEG等等。 下面是一個(gè)Matlab程序20精選ppt%打開蝴蝶圖象,進(jìn)行Fourier變換h=imread('butterfly.jpg'); %openanimagefigure; imshow(h);%因?yàn)閳D像的格式uint8不能做加減法,%所以需要把格式uint8變成格式doubleh=double(h);[m,n,p]=size(h);hf=fftshift(fft2(h)); %2DFourier變換,得到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’);21精選ppt22精選ppt補(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)變換23精選ppt第2章圖象和視覺基礎(chǔ)2.1概論和綜述該基礎(chǔ)包括視覺基礎(chǔ)、成像基礎(chǔ)和圖像基礎(chǔ)三部分：視覺基礎(chǔ)（人眼與亮度視覺，顏色視覺）成像基礎(chǔ)（模型、幾何和采樣量化）圖像基礎(chǔ)（像素間聯(lián)系、圖像運(yùn)算和圖像坐標(biāo)變換）注意：視覺：指光對感官的刺激和視覺系統(tǒng)的感覺。視知覺：指如何通過視覺形成關(guān)于外部世界的表象。24精選ppt2.2人眼與亮度視覺2.2.1人眼成象 人的眼球是一個(gè)復(fù)雜的視覺器官。眼球的前部有晶狀體，相當(dāng)于照相機(jī)的鏡頭。眼球內(nèi)側(cè)的后部有視網(wǎng)膜。視網(wǎng)膜表面分布著兩種感光細(xì)胞：錐細(xì)胞和柱細(xì)胞。眼內(nèi)有六、七百萬的錐細(xì)胞，它們對明亮的光和顏色很敏感。人眼借助于錐細(xì)胞來區(qū)分細(xì)節(jié)，因?yàn)槊總€(gè)錐細(xì)胞都連到神經(jīng)末梢。錐細(xì)胞的視覺稱為適亮視覺。眼內(nèi)有75萬到150萬柱細(xì)胞。它們分布面大，且?guī)讉€(gè)柱細(xì)胞連到一個(gè)神經(jīng)末稍。分辨率低，主要提供整體視覺印象。雖然它們對顏色不敏感，但是對弱光較敏感。柱細(xì)胞的視覺稱為適暗視覺。 視網(wǎng)膜的中心是中央凹，面積約1.51.5mm2，錐細(xì)胞的密度達(dá)到150000個(gè)/mm2,是眼內(nèi)最敏感的區(qū)域。25精選ppt人眼的構(gòu)造26精選ppt人眼成像錐細(xì)胞和柱細(xì)胞的密度和分布27精選ppt2.2.2亮度適應(yīng)和區(qū)分主觀亮度和主觀適應(yīng)性由于數(shù)字圖象以客觀亮度顯示圖象，人眼以主觀亮度感受取得視覺，所以人眼的亮度適應(yīng)性影響了圖象處理的結(jié)果。人眼的視覺系統(tǒng)能適應(yīng)的光的亮度等級從可以看見的昏暗到眩目相差能達(dá)到1010等級。但是人眼并不能同時(shí)在這么大的范圍內(nèi)看清物體，而只能在同一時(shí)間內(nèi)適應(yīng)一個(gè)小的亮度變化范圍（106等級）。28精選ppt在一定條件下，一個(gè)視覺系統(tǒng)當(dāng)前的敏感度叫做亮度適應(yīng)級。這個(gè)敏感度是用實(shí)驗(yàn)來驗(yàn)證的。在實(shí)驗(yàn)中，逐漸增加光照射的強(qiáng)度I，改變量為I，達(dá)到多個(gè)觀察者能感知的程度，當(dāng)有一半的人感知增加時(shí)的I/I成為Weberratio,作為視覺系統(tǒng)當(dāng)前的敏感度。在很強(qiáng)的光下，需要改變較強(qiáng)的光照射才能使多個(gè)觀察者感知；相反，在某強(qiáng)度光照下，些微的光強(qiáng)度變換就會(huì)使人感知。29精選ppt人眼的主觀亮度是非線性的，例如Mach帶30精選ppt人眼的光學(xué)錯(cuò)覺31精選ppt2.3顏色視覺32精選ppt根據(jù)人眼的結(jié)構(gòu)，所有的顏色是三種基本顏色的不同組合．33精選ppt所有的顏色可以看作是三種基本顏色的迭加，也可以看作三種補(bǔ)色（從白色中除去某種顏色）的迭加34精選ppt顏色的三種基本特征：灰度、色調(diào)和飽和度，后兩者又稱色度?；叶扰c物體的反射率成正比；色調(diào)與光照中主要光譜有關(guān)；飽和度與色調(diào)的純度有關(guān)。組成顏色C的三個(gè)刺激量X，Y，Z所占的百分比數(shù)為x,y,zx=X/(X+Y+Z),y=Y/(X+Y+Z),z=1–x–y.35精選ppt36精選ppt2.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),令

1000 P=0100 0010 00-1/1ch=Pwh=P·(kX,kY,kZ,k)=(kX,kY,kZ,-(k/)Z+k）=(x,y,z,1)x=kX/(-k/Z+k)=X/(-Z),同理求得y和zxZ(X,Y,Z)037精選pptwh=P-1ch 1000 P-1=0100 0010 001/1wh=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)38精選ppt2.6采樣和量化

一幅圖像需要經(jīng)過離散化成為數(shù)字圖像后才能被計(jì)算機(jī)處理。圖像的空間坐標(biāo)的離散化叫做空間采樣,灰度的離散化叫做灰度量化。采樣分為均勻采樣和量化和非均勻采樣和量化。假設(shè)圖像是一個(gè)長方形。在平面上取MN個(gè)大小相同的網(wǎng)格，并把灰度分成G個(gè)等級。取各網(wǎng)格中的某點(diǎn)處的灰度值最接近的整數(shù)作為該網(wǎng)格的灰度。通常，取M=2m,N=2n和G=2k。則存儲(chǔ)一幅圖像的需要的位數(shù)等于b=MNk。例如，一幅128128、64個(gè)灰度等級的圖像需要220位，512512、256個(gè)灰度等級的圖像需要226位。采樣的個(gè)數(shù)和灰度等級的選取與分辨率和儲(chǔ)存的能力兩者有關(guān)，需要綜合考慮。例如：圖像空間分辨率變化產(chǎn)生的效果。圖像灰度分辨率變化產(chǎn)生的效果。圖像空間和灰度分辨率同時(shí)變化產(chǎn)生的效果。39精選ppt圖像空間分辨率變化產(chǎn)生的效果40精選ppt圖像灰度分辨率變化產(chǎn)生的效果41精選ppt圖像灰度分辨率變化產(chǎn)生的效果（2）42精選ppt非均勻采樣和量化

對給定的空間分辨率，圖像的質(zhì)量可以根據(jù)圖像特性利用自適應(yīng)的采樣過程來改進(jìn)。例如，在灰度變化顯著的有很多細(xì)節(jié)的區(qū)域應(yīng)當(dāng)采用較密的采樣。又例如，可以計(jì)算所有灰度值出現(xiàn)的頻率。若某范圍內(nèi)的灰度值出現(xiàn)頻繁，而在其他范圍內(nèi)灰度值出現(xiàn)較稀，則在該范圍內(nèi)量化灰度就要較密，在其他范圍內(nèi)較稀。43精選ppt2.7像素間聯(lián)系像素有四鄰域N4和八鄰域N8。像素的連通有4-連接、8-連接和混合連接(m-連接)。稱點(diǎn)r和p是混合連接，如果r和p是4-連接的，或者r與p是8-連通的但不是4-連通的?；旌线B接避免了8-連通所產(chǎn)生的歧義。44精選ppt等價(jià)關(guān)系和傳遞閉包定義：在集合A上的二元關(guān)系R,記為aRb，a,bA,稱為等價(jià)關(guān)系，如果R具有如下性質(zhì)：自反性對每個(gè)a,成立aRa; 對稱性aRb當(dāng)且僅當(dāng)bRa; 傳遞性aRb和bRc蘊(yùn)涵著aRc?？梢杂沘Rb為(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+ abcde 11000 a 00010 b R=00001 c 01000 d 00000 e45精選ppt abcde 11010 a 01010 b R+=00001 c 01010 d 00000 e例如R={(a,a),(a,b),(b,d),(d,b),(c,e)}時(shí)，R+=R{(a,d),(b,b),(d,d)}一般地說，R+=R+RR+R(RR)+…+Rn．46精選ppt距離量度

設(shè)有三個(gè)像素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/24-連通空間距離D4(p,q)=|x-s|+|y-t|8-連通空間距離D4(p,q)=max{|x-s|,|y-t|}m-連通空間距離Dm(p,q)與路徑有關(guān)。47精選ppt2.8算術(shù)和邏輯運(yùn)算 圖像的四則運(yùn)算中是逐個(gè)像點(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)算。48精選ppt2.9

坐標(biāo)變換請復(fù)習(xí)已學(xué)過的教材．49精選ppt第3章象素空間關(guān)系圖象是由象素組成。圖象以象素為單位建立坐標(biāo)系。通常是x軸向左，y軸向下。圖象的坐標(biāo)變換就是象素的坐標(biāo)變換。所謂空間變換就是把象素從一個(gè)空間變換到另一個(gè)空間的坐標(biāo)變換。坐標(biāo)變換的一個(gè)應(yīng)用是對圖象的幾何失真進(jìn)行校正。50精選ppt一個(gè)象素的鄰域是指該象素周圍的象素集合。一個(gè)象素p的周圍有八個(gè)象素，它們共同組成了該象素的8-鄰域N8(p)。一個(gè)象素與上下左右的四個(gè)象素組成了4-鄰域N4(p)。一個(gè)象素與四個(gè)角上的象素組成了對角鄰域ND(p)。同類灰度的象素間的鄰接，連接和連通問題：兩個(gè)象素彼此落在對方的4-鄰域內(nèi)，稱為4-連接兩個(gè)象素彼此落在對方的8-鄰域內(nèi)，稱為8-連接如果兩個(gè)象素或者是4-連接，或者不是4-連接但落在對方的對角鄰域ND(p)內(nèi)，那么稱為混合連接（m-連接）。3.1象素間聯(lián)系51精選ppt混合連接可以避免8-連接造成的多路問題。兩個(gè)象素集合的連通是指它們在指定的鄰域內(nèi)有一條通路。例如圖中的左上角和右下角按4-連接是不連通的；按m-連接是連通的；按8-連接是連通的,但是道路不是唯一的。兩個(gè)象素p和q之間的距離即滿足下列三個(gè)條件的一個(gè)函數(shù)D：

D(p,q)

0，當(dāng)且僅當(dāng)p=q時(shí)D(p,q)=0. D(p,q)=D(q,p), D(p,q)+D(q,r)D(p,r).52精選pptDE(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/2D4(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|}.10111.4011112222011111111111111111111111最右邊的圖中象素到邊界的距離是多少？各象素到中心的距離D：53精選ppt3.2基本坐標(biāo)變換在計(jì)算機(jī)圖形學(xué)中已經(jīng)講過。基本的坐標(biāo)變換是平移、伸縮、旋轉(zhuǎn)。

復(fù)雜坐標(biāo)變換是它們的級連。錯(cuò)切是三種基本變換的乘積嗎？54精選ppt3.3形態(tài)變換3.3.1變換體系1、形態(tài)變換及其分類形態(tài)變換是將平面區(qū)域映射到平面區(qū)域的變換。形態(tài)變換表、規(guī)則解析式非連續(xù)連續(xù)不光滑光滑線性非線性仿射變換歐氏變換剛體變換相似變換平移變換旋轉(zhuǎn)變換放縮變換55精選ppt點(diǎn)p到q的投影變換可以寫成其中A是22矩陣。投影變換可以寫成非奇異三階齊次矩陣的形式。注意：一般地說，投影是二階的非線性變換，但是都可以寫成三階矩陣的齊次形式。

仿射變換是一個(gè)非奇異的線性變換接上一個(gè)平移變換：或?qū)懗?6精選ppt仿射變換的性質(zhì)

仿射變換把原點(diǎn)映射為(t1,t2,1)，一般不再是原點(diǎn)。所以一般的仿射變換不是線性變換。如果做一個(gè)平移變換，使上面公式中的t=0，那么仿射變換就是任何的非奇異矩陣A。另一方面，仿射變換的形式也說明它不包含投視投影。因此，它是三種基本變換的連乘，而具有如下的性質(zhì)。（1）仿射變換將有限點(diǎn)映射成有限點(diǎn)。（2）仿射變換將直線變成直線。（3）仿射變換將平行直線映射成平行直線。（4）當(dāng)區(qū)域P和Q是沒有退化的三角形時(shí)，有唯一的仿射變換A將P變成Q。57精選ppt特殊的仿射變換：相似變換當(dāng)上述仿射變換中A=sR時(shí)稱為相似變換，其中，s是實(shí)數(shù)，R是旋轉(zhuǎn)變換。當(dāng)s=1和R為正交矩陣時(shí)上述仿射變換稱為剛體變換，屬于等距變換。當(dāng)s=1和R為正交矩陣時(shí)上述仿射變換稱為歐氏變換。仿射變換的另一種說法：一個(gè)經(jīng)過平移的非奇異線性變換。58精選ppt3.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)。59精選ppt空間變換設(shè)點(diǎn)(x,y)與(x,y)的關(guān)系是最簡單的情況是線性：較復(fù)雜的情況是二次的：如果知道s(x,y)和t(x,y)的解析表達(dá)式，就可以通過求反函數(shù)來得到x和y。60精選ppt對于一個(gè)四邊形的空間變換，可以首先確定四個(gè)對應(yīng)頂點(diǎn)，然后用雙線性插值的方法：問題：怎樣用兩次線性插值來作呢？ 如果幾何失真的面積比較大，那么如果用分塊來 提高校正的效果呢？61精選ppt灰度插值

盡管(x,y)坐標(biāo)分量是整數(shù)值，但是計(jì)算出來的新坐標(biāo)(x,y)未必有整數(shù)分量，而且確定新坐標(biāo)處的灰度值。有兩種方案：前向映射和后向映射前向映射：把從實(shí)際采集的失真圖象的象素灰度值賦給原始不失真圖象的象素。如果失真圖象的象素P映射到Q，Q落在四個(gè)原始不失真圖象的象素之間，就取這四點(diǎn)處的灰度值作雙線性插值，作為象素Q的灰度值。62精選ppt后向映射：把灰度值從原始不失真圖象的象素P映射到實(shí)際采集的失真圖象的象素P上。如果實(shí)際采集的象素Q落在四個(gè)象素P（非整數(shù)點(diǎn)）之間，就取這四點(diǎn)P的灰度值作雙線性插值，作為象素Q的灰度值。插值灰度的計(jì)算：-零階插值：取最近的點(diǎn)的灰度-雙線性插值：-三次線性插值：63精選ppt雙線性插值：設(shè)(xi,yi),i=1,2,3,4,是按反時(shí)針方向包圍Q的矩形的四個(gè)象素。先作然后，64精選ppt第4章空域增強(qiáng)技術(shù)圖象增強(qiáng)技術(shù)是使圖象的某種指定效果更好。例如，使X透視照片更清晰。分成兩大類：空域增強(qiáng)技術(shù)和頻域增強(qiáng)技術(shù)。其中，空域指象素組成的空間?？沼蛟鰪?qiáng)技術(shù)直接作用于象素?？梢员硎緸?/p>

g(x,y)=EH(f(x,y))

其中f和g分別是增強(qiáng)前后的圖象.這個(gè)變換不改變象素的位置，僅改變象素的灰度f(x,y)。65精選ppt4.1空間技術(shù)分類如果變換EH僅用一個(gè)點(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)的灰度和位置,分別改變原灰度為新灰度(稱為灰度變換或灰度映射)和原位置為新位置的象素.灰度操作可以把不同的灰度變成同一個(gè)灰度,集合操作可以把不同位置變成同一個(gè)位置.因此,它們可能不是可逆的變換.66精選ppt4.2圖象間運(yùn)算4.2.1算術(shù)和邏輯運(yùn)算算術(shù)運(yùn)算一般用于兩個(gè)象素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幅圖象的平均將壓制噪音:67精選ppt邏輯運(yùn)算 補(bǔ)NOT,與AND,或OR,異XOR應(yīng)用:檢測目標(biāo)的邊界,向右移動(dòng)一個(gè)象素后,依次作與運(yùn)算、差運(yùn)算得到左邊界。類似做出上、下、左邊的邊界。68精選ppt直接灰度映射4.3.1灰度映射原理 將圖象中的灰度值按某種規(guī)律映射成新灰度。在對于彩色圖象做灰度映射時(shí)應(yīng)注意保持色調(diào)和飽和度相同，只改變亮度。（HSV）t0原灰度新灰度s69精選ppt典型灰度映射圖象求反 對圖象求反是將原圖象的灰度值反轉(zhuǎn)。例如，黑底的照片變成白底的照片。設(shè)灰度有L個(gè)等級。原灰度是d,新灰度是L-1-d。L-1L-10原灰度新灰度d70精選ppt增強(qiáng)對比度 增加圖象的各部分的反差。例如，圖象落在灰度s1和s2之間的部分是感興趣的部分，而其他部分不重要。那么可以把灰度s1和s2之間的部分的灰度反差變大。S1S2L-10L-171精選ppt72精選ppt動(dòng)態(tài)范圍壓縮 原圖象的灰度范圍過大，因此，需要壓縮到可以顯示的堆度范圍。例如，t=Clog(1+|s|).C為尺度比例常數(shù)。st73精選ppt灰分切分 把某部分的灰度變得突出。st74精選ppt直方圖變換直方圖和積累直方圖圖象的灰度統(tǒng)計(jì)稱為直方圖。假設(shè)圖象有n個(gè)象素，灰度等級有k=0,1,…,L-1個(gè)。sk為第k個(gè)等級的象素的灰度，設(shè)該象素在圖象中共有nk個(gè)，那么該象素出現(xiàn)的頻率是

為了規(guī)范化，把sk限制在0到1內(nèi)。當(dāng)k跑遍0,1,…,L-1時(shí)，就給出了一個(gè)函數(shù)圖形，稱為直方圖。直方圖是一個(gè)1D的離散函數(shù)。積累直方圖就是由前k等級之和所生成的積累直方圖。75精選pptL-1L-1Ps(sk)EH(sk)kk76精選ppt直方圖均衡化

設(shè)ps(sk)=nk/n，0sk

1,k=0,1,…,L-1.即灰度sk的象素占全體象素的比例是ps(sk)。令

EH(sk)是單調(diào)增加函數(shù)，它等于灰度在sk以下的象素所占的比例?？梢詫懗龇春瘮?shù)：sktksktk假設(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的直方圖是均勻分布。77精選ppt直方圖的計(jì)算直方圖均衡化的計(jì)算：假設(shè)原圖象有L個(gè)灰度，不妨記sk就是灰度k。依次計(jì)算頻率p(k)＝nk/n,k=0,1,…,L-1.計(jì)算積累直方圖EH(k),k=0,1,…,L-1.用下式計(jì)算tk的近似值：由于tk在零與一之間，應(yīng)該把tk映射到在[0,L-1]范圍內(nèi)的一個(gè)整數(shù)，所以用L-1乘以tk后取整,即[(L-1)tk]。由此來確定灰度k到[(L-1)tk]的灰度映射關(guān)系。78精選ppt的pk79精選ppt直方圖的規(guī)定化規(guī)定化即把圖象的直方圖變成指定的直方圖。作法是先把它們都變成均衡化的直方圖，再把第一步得到的變換反轉(zhuǎn)過來使用。變換反轉(zhuǎn)需要確定對應(yīng)的規(guī)則。SML選使下式最小的k和l:80精選pptGML使用組映射規(guī)則，設(shè)有一個(gè)整數(shù)函數(shù)Ｉ(l),l=0,…,N-1，使得0I(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).81精選ppt82精選ppt４.5線性濾波器4.5.1技術(shù)分類和實(shí)現(xiàn)原理技術(shù)分類根據(jù)功能分成平滑濾波和銳化濾波。 平滑濾波減弱和消除高頻分量，使圖象灰度平滑。 銳化濾波減弱和消除低頻分量，是圖象反差增大。２.模板卷積 方形模板在圖象中漫游，中心對準(zhǔn)一個(gè)象素。83精選ppt4.5.2線性平滑濾波器1.鄰域平均

g(x,y)=模板中象素灰度的平均２.加權(quán)平均

g(x,y)=模板中象素灰度的加權(quán)平均。常用高斯分布來計(jì)算各系數(shù)值。常用小模板。１２１２４２１２１可選模板M=2n+1,n=2+1。也有用3作為窗口半徑。84精選ppt4.6非線性濾波

分成三個(gè)發(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ù)組排序，然后輸出一個(gè)數(shù)，使它既不大于又不小于其中的r+1個(gè)數(shù)。中值濾波能完全消除孤立的脈沖（零脈沖響應(yīng)）和不影響理想的階躍響應(yīng)。能被中值濾波完全除去的脈沖的最大長度依賴于濾波器的模板長度Ｍ。85精選ppt２.２-D中值濾波原理 取模板尺寸nn，對數(shù)組排序，然后取一個(gè)數(shù)，使它使它既不大于又不小于其中的n2/2個(gè)數(shù)。實(shí)際操作時(shí)，讓模板在圖象中游動(dòng)。中值濾波能消除孤立的脈沖。 鄰域平均濾波器在去掉孤立脈沖時(shí)模糊了圖象，中值濾波器在去掉孤立脈沖時(shí)不影響圖象。但是，中值濾波不能去掉服從高斯分布的噪音。３.中值濾波的模板 效果與模板的大小有關(guān)，也與模板中參與運(yùn)算的象素個(gè)數(shù)有關(guān)。用稀疏模板運(yùn)算速度較快。86精選ppt４.均值、中值和最頻值 最頻值是出現(xiàn)頻率最高的值。如果圖象有單個(gè)峰值的對稱直方圖，那么均值、中值和最頻值相等。如果圖象有單個(gè)峰值的直方圖，那么最頻值對應(yīng)最高峰，而中值比均值更接近最頻值。５.序統(tǒng)計(jì)濾波器 中值濾波是序統(tǒng)計(jì)濾波器的特例，例如，最大值濾波器和最小值濾波器也是序統(tǒng)計(jì)濾波器。中點(diǎn)濾波器是最大值濾波器和最小值濾波器的平均。87精選ppt4.6.2非線性銳化濾波器１.微分方法可以銳化圖象。用兩個(gè)差商來代替微分：－１－１－１１１１１－１１－１１－１分別用１范數(shù)、２范數(shù)和范數(shù)計(jì)算時(shí)88精選ppt２.銳化濾波器的通用性質(zhì)(1)零位移。銳化濾波器不改變邊緣的位置。應(yīng)具有反對稱性。(2)消除均值。銳化濾波器均值為零。(3)無選擇性的微分。微分操作只對象素灰度敏感。(4)對稱性質(zhì)。３.最大最小銳化變換最大最小銳化變換的迭代實(shí)現(xiàn)：89精選ppt局部增強(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)右邊的第一項(xiàng)能放大圖象的局部變化,第二項(xiàng)恢復(fù)均值.90精選ppt第5章基本圖象變換5.1基本圖象變換5.2可分離和正交圖象變換5.3傅里葉變換5.4沃爾什/哈達(dá)瑪變換5.5離散余弦變換5.6Radon變換圖象變換可分離變換統(tǒng)計(jì)變換傅氏變換其他變換霍特林變換91精選ppt5.2可分離和正交圖象變換1D變換:T(u)是f(x)的變換.g(x,u)稱為正向變換核.反變換是h(x,u)稱為反向變換核.2D變換:T(u,v)是f(x,y)的變換.92精選ppt如果核具有下列性質(zhì),則稱g是可分離核:如果g1=g2,那么2D對稱可分離變換可以寫成兩個(gè)相繼的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.93精選ppt其中,F是NN圖象,A是NN對稱.取B為A的逆矩陣,那么, BTB=BAFAB=F.如果B不等于A-1,那么F*=BAFAB是F的一個(gè)近似.94精選ppt5.3傅里葉變換離散的傅里葉變換和性質(zhì)1、由1維傅里葉變換（FT）和逆變換的公式,

離散的1維傅里葉變換（DFT）和逆變換的公式是，u=0,1,…,N-1;，x=0,1,…,N-1.這里把f(x)理解為一個(gè)離散函數(shù)，

其中，除了x=0,1,…,N-1處以外f(x)等于零。95精選ppt

因?yàn)镕(u)是周期函數(shù)，u取值0,1,…,N-1時(shí)，exp[-2ju/N]以N為周期。所以F(u)是在整個(gè)頻率域內(nèi)有定義的。取且僅取一個(gè)周期就包含了足夠的原來f(x)的信息。特別地，

離散的2維傅里葉變換（DFT）和逆變換的公式。其中記u=0,1,…,M-1,v=0,1,…,N-1;x=0,1,…,M-1,y=0,1,…,N-1.分別為96精選ppt這些公式的推導(dǎo)如下。以間隔x和y，從圖像中取MN個(gè)樣本，x=0,1,…,M;y=0,1,…,N。同樣地，在圖像的傅里葉變換的像中，以間隔u和v，取MN個(gè)樣本，u=0,1,…,M;v=0,1,…,N；使得xu=1/M和yv=1/N。97精選ppt這就完成了證明.另一方面,

98精選ppt傅里葉變換的像是一個(gè)二維復(fù)數(shù)矩陣。它是值得注意的是：顯示器不能正確地顯示F(u,v)。這是因?yàn)楦道锶~變換的像是一個(gè)復(fù)數(shù)矩陣。必須分別顯示它的實(shí)部和虛部，或它的模和幅角。 二維DFT的性質(zhì)：1、分離性99精選ppt因此，二維DFT可以用相繼的兩個(gè)一維的DFT來計(jì)算：2、平移性100精選ppt傅里葉變換象在零頻率處為，它的模反映了背景光照的強(qiáng)度，通常是比較亮的。但是，由于空間坐標(biāo)是從左上角的(0,0)開始的，對應(yīng)零頻率的點(diǎn)也就落在頻率窗口的左上角，造成左上角比較亮。再由于傅里葉變換的周期性，在窗口的四個(gè)角處都比較亮。其實(shí)這四個(gè)角的頂點(diǎn)是同一個(gè)點(diǎn)。因此，希望把傅里葉變換象的中心（零頻率）移到窗口中心去。注意到傅里葉變換的u和v是從低頻到高頻排列的。當(dāng)取(u0,v0)為圖像作傅里葉變換后的像的中心時(shí)，即u0=M/2,v0=N/2時(shí)，根據(jù)上面的性質(zhì)，101精選ppt

所以，只要先對f(x,y)作變換f(x,y)(-1)x+y，然后作傅里葉變換，就可以把傅里葉變換象的零頻率移到窗口中心去。反過來，當(dāng)把這樣的傅里葉變換后的像變回到原時(shí)間函數(shù)時(shí)，需要把所得到的f(x,y)再作變換f(x,y)(-1)x+y。這里有一個(gè)問題：圖象f(x,y)是灰度值，總是不小于零的。但是，f(x,y)(-1)x+y會(huì)交替的變號。如果用顯示器來顯示變號的灰度圖象，那么顯示的結(jié)果依賴于設(shè)備的設(shè)置。通常，顯示時(shí)負(fù)的灰度值自動(dòng)取為零。進(jìn)一步，一幅灰度范圍在0-100內(nèi)的圖形未必比灰度范圍在0-255內(nèi)的圖形暗淡。這是因?yàn)樵谇耙环N情況下，顯示器可能自動(dòng)地把最高的亮度賦予100灰度。換句話說，顯示器的自動(dòng)設(shè)置可能會(huì)改變圖象的顯示結(jié)果。

102精選ppt13、周期性和共扼對稱性設(shè)M和N分別是橫縱軸的周期。如果f是實(shí)函數(shù)，那么事實(shí)上，103精選ppt如果f是實(shí)函數(shù)，那么4、旋轉(zhuǎn)性質(zhì)

做變換

x=rcos,y=rsin,和u=wcos，v=wcos， 那么事實(shí)上，104精選ppt5．

分配律6．

尺度變換7．

平均值 是8．

一維卷積的平均值。105精選ppt

例如，設(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)的時(shí)候才是一，否則是零。0z1和

0x-z1。即 當(dāng)0x1時(shí)0zx；當(dāng)1<x2時(shí)x-1z1。 當(dāng)0x2時(shí)，f(z)g(x-z)=0.5，否則等于零。 它們的卷積等于0x106精選ppt卷積有下列性質(zhì)：設(shè)F和G分別是f和g的傅里葉變換。則事實(shí)上，卷積經(jīng)過傅里葉變換，107精選ppt離散采樣的兩個(gè)函數(shù)的卷積問題需要考慮到周期的長度影響。假設(shè)兩個(gè)函數(shù)f和g有相同的周期M。根據(jù)卷積f*g的定義，該卷積也有相同的周期M。計(jì)算卷積時(shí)，只能使用f的一個(gè)周期內(nèi)的數(shù)值和g的一個(gè)周期內(nèi)的數(shù)值。如果f采樣A個(gè)f(0),f(1),…,f(A-1)，g采樣B個(gè)g(0),g(1),…,g(B-1)，隨著x的變化，乘積f(z)g(x-z)不等于零的長度是A+B-1。當(dāng)MA+B-1時(shí)，該乘積才不會(huì)越出一個(gè)周期的范圍而造成重疊取樣。此時(shí)，為了便于使用離散卷積公式，補(bǔ)充規(guī)定

f(x)=0當(dāng)AxM-1, g(x)=0當(dāng)BxM-1。 離散卷積公式是：x=0,1,…,M-1。

108精選ppt相關(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)0z1和

0x+z1時(shí)才是一，否則是零。即 當(dāng)-1x0時(shí)-xz1； 當(dāng)0<x1時(shí)0z1-x。 當(dāng)-x1時(shí)f(z)g(x+z)=0.5，否則等于零。它們的卷積等于

109精選ppt快速傅里葉變換我們推導(dǎo)快速傅里葉變換公式。假設(shè)N是2的冪，即N=2n。記N=2M。令。在已知WN的條件下，計(jì)算每一個(gè)F()至少需要作N次乘法和一次除法，計(jì)算所有的F()共需要作不少于N2次乘法。改寫變換：容易看出WN有“折半”的性質(zhì)：110精選ppt定義111精選ppt=0,1,…,M-1

我們還需要計(jì)算在

=M,M+1,…,N-1處的值。為此，注意到=0,1,…,M-1

根據(jù)上面分析，我們只需要在M個(gè)點(diǎn)

=0,1,…,M-1處分別求出 和 的值，并且每次用 乘以 ，就可以用公式(4)和(5)來計(jì)算在2M個(gè)點(diǎn)

=0,1,…,2M-1處 的值。公式(4)和(5)就是一維的快速傅里葉變換公式。112精選ppt

最后，我們證明FFT算法的時(shí)間復(fù)雜性是(NlogN)。設(shè)計(jì)算一個(gè)有N個(gè)點(diǎn)的FFT算法的時(shí)間復(fù)雜性是T(N)。根據(jù)以上的公式，一個(gè)有N個(gè)點(diǎn)的FFT運(yùn)算分成兩個(gè)各有N/2點(diǎn)的FFT運(yùn)算，并且，其中的一個(gè)每次要與作一次乘法，共有(N)次乘法，所以，

T(N)=2T(N/2)+(N)。 依此可得

T(N)=T(2n)=2T(2n-1)+(2n) =22T(2n-2)+2(2n)=…=n(2n)=(NlogN)。113精選ppt114精選ppt%openanimageh=imread('butterfly.jpg');figure;imshow(h);%因?yàn)閳D像的格式uint8不能做加減法,所以需要把格式uint8變成double.h=double(h);[m,n,p]=size(h);%變成黑白圖像if(p>1)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));115精選ppt%2DFourier變換和平移頻率0到中心,得到2D復(fù)數(shù)值圖像hf=fftshift(fft2(h));%畫出其模的圖像。如果直接用imshow(uint8(hf))將得到下面的圖象.