圖像傅里葉變換、反變換的實現(xiàn)

1、1#課程大作業(yè)實驗報告圖像傅里葉變幻、反變換的實現(xiàn)課程名稱：數(shù)字圖像處理組長：王文雄學(xué)號：200730590323年級專業(yè)班級：07通信3班成員一：龐柱堅學(xué)號：200730590318年級專業(yè)班級：07通信3班成員二：王彌光學(xué)號：200730590322年級專業(yè)班級：07通信3班成員三：學(xué)號：年級專業(yè)班級：07通信3班指導(dǎo)教師鄧繼忠#報告提交日期 2010年6月1日項目答辯日期2010年6月1日2目錄1. 項目要求 32. 項目開發(fā)環(huán)境 33. 系統(tǒng)分析 33.1. 系統(tǒng)的主要功能分析 33.2. 系統(tǒng)的關(guān)鍵問題及解決方法（或思路） 64. 系統(tǒng)設(shè)計 84.1. 程序流程圖及說明 84.2.

2、程序主要模塊（或功能）介紹 104.2.1. 一維 FFT 和 IFFT 104.2.2. 二維圖像 FFT 和 IFFT ： 115. 實驗結(jié)果與分析 125.1. 實驗結(jié)果 125.2. 項目的創(chuàng)新之處 135.3. 存在問題及改進設(shè)想 136. 心得體會 146.1. 系統(tǒng)開發(fā)的體會 146.2. 對本門課程的改進意見或建議 14附件一 1531. 項目要求1. 基本要求：自修教材相關(guān)內(nèi)容（P52-74）或其它參考資料，在CVI下編程對尺寸為2n（N 為正整數(shù)）的圖像進行FFT（快速傅里葉變換）和（快速傅里葉反變換）。（不能利用CVI下的函數(shù)）2. 題目拓展：編程實現(xiàn)任意大小圖像的二維傅

3、立葉的變換與反變換。2. 項目開發(fā)環(huán)境項目開發(fā)環(huán)境主要分為軟件環(huán)境和硬件環(huán)境軟件：Lab Windows/CVI 和 IMAQ_Vision for LabWindows/CVI。Lab Windows/CVI 是美國 National Instrument（簡稱NI）公司開發(fā)的基于C語言的虛擬儀器開發(fā)平臺，適用于自動 測試、自動控制、測試儀器通信、測試硬件控制、信號分析及圖像處理等軟件的開發(fā)。經(jīng)過版本的不斷更新，Lab Windows/CVI已經(jīng)成為測控領(lǐng)域應(yīng)用最為廣泛的軟件開發(fā)工具 之一。而 IMAQ_Vision for LabWindows/CVI是 NI 公司開發(fā)的基于 LabWin

4、dows/CVI 的高 級圖像處理和分析軟件包，是進行圖像處理和分析的教學(xué)和科研的有力工具。軟件包提 供了 3 個重要的文件：硬件：個人PC電腦（主頻：2.6GHZ*2 內(nèi)存：1G*2）3. 系統(tǒng)分析3.1. 系統(tǒng)的主要功能分析傅里葉變換是研究信號頻域特性首要數(shù)學(xué)工具。在數(shù)字圖像頻域處理中，常常要 對二維圖像做快速傅里葉變換，由于傅里葉變換的可分離性，二維快速傅里葉變可以 分解為對行、列兩個方向的一維快速傅里葉變換，所以在 LabWindows/CVI 集成開發(fā)環(huán)境下實現(xiàn)二維圖像的快速傅里葉變換的關(guān)鍵是一維傅里葉變換的實現(xiàn)。在本系統(tǒng)設(shè)計過程中，主要分成兩個部分完成：第一部分是一維快速傅里葉變換

5、，該部分所包含的變量函數(shù)基本上不依賴于特定 的軟件平臺，僅僅與C語言有關(guān)，這部分是為二維快速傅里葉服務(wù)的。主要有內(nèi)容及 其作用如表格1所示。表1 一維快速傅里葉變換及反變換功能模塊列表內(nèi)容C程序（數(shù)據(jù)定義、函數(shù)聲明等）功能復(fù)數(shù)數(shù)據(jù)類型定義typedef structdouble real; double img; complex;定義描述快速傅里葉變換及 其反變換數(shù)據(jù)的類型。復(fù)數(shù)類型的四則運算void add(complex a, complex b, complex *c);void mul(complex a, complex b, complex *c);void sub(complex

6、 a, complex b, complex *c);void divi(complex a, complex b, complex *c);這四個函數(shù)分別完成兩個復(fù) 數(shù)類型數(shù)據(jù)a和b的加法、 減法、乘法和除法運算，運 算結(jié)果存放于指針c指向的 數(shù)據(jù)空間。初始化快速傅里葉變換及其反變換變換核WNvoid ini tW(i nt leg nth);該函數(shù)完成wN0 wnn/2的計 算，wN0WnN/2在碟新運算時 需要用到；參數(shù)leg nth是一 次快速傅里葉變換或反變換 的數(shù)據(jù)長度?！暗刮恍颉碧幚砗瘮?shù)void cha nge(i nt leg nth, complex source);該函數(shù)完

7、成數(shù)據(jù)的自然順序 到“倒位序”的變換處理或 是“倒位序”到自然順序的變換處理；參數(shù)leg nth是一 次快速傅里葉變換或反變換 的數(shù)據(jù)長度，source是待變 換的數(shù)據(jù)?？焖俑道锶~變換void fft(i nt le ngth, complex src);該函數(shù)完成對2n個復(fù)數(shù)數(shù) 據(jù)的快速傅里葉變換；參數(shù) leg nth是一次快速傅里葉變 換的數(shù)據(jù)長度，source是待 變換的數(shù)據(jù)?？焖俑道锶~反變換void ifft(i nt len gth, complex src);該函數(shù)完成對2的N次方個 復(fù)數(shù)數(shù)據(jù)的快速傅里葉反變 換；參數(shù)leg nth是一次快速 傅里葉反變換的數(shù)據(jù)長度， source

8、是待變換的數(shù)據(jù)第二部分是二維快速傅里葉變換及其反變換，該部分主要是在一維快速傅里葉變 換及其反變換的基礎(chǔ)上，完成對一幅二維圖像的快速傅里葉變換及其反變換，并將結(jié) 果顯示出來。主要函數(shù)模塊及其功能如表格 2所示。表2二維快速傅里葉變換及反變換功能模塊列表781M2)-1WW(5)。K一I(0) _I圖1 N=8的快速傅里葉變換蝶形運算流圖32 系統(tǒng)的關(guān)鍵問題及解決方法(或思路)二維圖像的快速傅里葉變換及其反變換可以分解成行、列兩個方向上的一維快速傅 里葉變換及其反變換，由因為快速傅里葉變換和反變換的原理是一致的，所以，在整個 系統(tǒng)設(shè)計的過程中，最關(guān)鍵的問題就是如何用C語言程序描述模擬整個快速傅里

9、葉變換的運算流程。為了解決這個問題，根據(jù)快速傅里葉變換運算流圖，將整個變換過程分層描述，共 分解為3個層次：“級”、“組”和“個”。一個快速傅里葉變換運算過程分為i個級，每 個級包含j個組，每個組又包含k個單個蝶形運算。例如如圖1所示的N=8的快速傅里 葉變換的運算流圖，該流圖共分為 3個級：第一級包含4個組，每個組又1個單個蝶形 運算；第二級包含2個組，每個組有2個單個蝶形運算；第三級包含1個組，每個組有4 個蝶形運算。X(0)X(l)XXX(4)XX(6)X(7)在函數(shù)fft(int length, complex src)實現(xiàn)時使用3重for循環(huán)來描述，最外層for循環(huán)是對“級”的循環(huán)，

10、第二層for循環(huán)是對每一級里“組”的循環(huán)，最內(nèi)層 for循環(huán)是對每一組里“個“，即單個蝶形運算的循環(huán)。程序代碼如下所示:/*快速傅里葉變換*/void fft(i nt len gth, complex src)int i=0;int j=0;int k=0;int Dista nce=0;int Step=0;int grade=0;int group=0;int un it=0; complex up; complex dow n; complex product;1次FFT蝶形運算"級數(shù)"計數(shù)器 1級FFT蝶形運算"組數(shù)"計數(shù)器 1組FFT蝶形運算

11、"個數(shù)"計數(shù)器 1個FFT蝶形運算跨越的"距離" /計算一級運算當(dāng)前已經(jīng)走過的步長 /FFT蝶形運算級數(shù)寄存器 /FFT蝶形運算組數(shù)寄存器 /FFT蝶形運算個數(shù)寄存器1個蝶形運算中間結(jié)果寄存器 1個蝶形運算中間結(jié)果寄存器1個蝶形運算中間結(jié)果寄存器/*先對原始數(shù)據(jù)做"到位序"處理*/cha nge(le ngth, src);/*計算1次FFT的級數(shù)總數(shù)grade*/ grade=(i nt)(log(le ngth)/log(2);for(i=0;i< grade ;i+)/*計算第i級運算包含組數(shù)group*/ group=(

12、i nt)pow(2,(double)(grade-1-i);/*計算單個蝶形運算跨越距離*/Dista nce=1<<i;/* 一級蝶形運算*/for(j=0;jvgroup;j+ )/*計算一級運算當(dāng)前已經(jīng)走過的步長*/Step=2*Dista nce*j;/*計算一組蝶形運算中包含的蝶形運算個數(shù)unit*/un it=(i nt)pow(2,(double)(i);/* 一組蝶形運算*/for(k=0;k<u nit;k+)/* 一個蝶形運算*/mul(srcStep+k+Dista nce,Wle ngth*k/2/Dista nee,&product);ad

13、d(srcStep+k,product，&up);sub(srcStep+k,product，&dow n);srcStep+k=up;srcStep+k+Dista nce=dow n;4. 系統(tǒng)設(shè)計4.1. 程序流程圖及說明整體程序流程圖如下所示圖2整體程序流程圖說明：A.當(dāng)開始運行程序后，通過點擊“打開一幅圖像并顯示”按鈕，在彈出的對話框 中選擇一幅格式符合要求的圖像并確定，之后程序就會在另一個名為“源圖像” 的窗口中顯示原始圖像并在主界面中顯示原始圖像寬度和高度。按鈕“打開一幅圖像并顯示”左邊的指示LED丁亮，表示已經(jīng)打開一幅圖像，并可以開始下 面的操作。B. 打開一幅

14、圖像后，點擊“傅里葉變換”按鈕，對原始圖像進行二維FFT變換，得到變換后的數(shù)據(jù)，并在一個名為“ FFT圖像”的窗口中顯示經(jīng)過傅里葉變換 后的復(fù)數(shù)圖像。C. 點擊“傅里葉反變換”按鈕，對第二步中二維傅里葉變換變換得到的數(shù)據(jù)進行二維傅里葉反變換，恢復(fù)原始圖像，并在一個名為“IFFT圖像”的窗口中顯示。D. 如果此時要退出程序，那么就點擊“退出”按鈕；如果不想退出，想對另外一幅圖像進行13步的操作，那么就點擊“清除”按鈕，程序會重新回到剛運行 程序的狀態(tài)。42程序主要模塊（或功能）介紹421. 一維 FFT 和 IFFT流程圖:13#計算呎0二< I<= N/2）對輸入數(shù)據(jù)刈n）進彳施倒

15、序處理|（輸岀數(shù)據(jù)并結(jié)束）#圖3 一維FFT和IFFT流程圖說明：A.FFT和IFFT的運算及其總體流程圖是相同的，均是按以上流程圖來實現(xiàn)。B. 首先，先計算Wn oC. 對輸入數(shù)據(jù)x(n)進行位倒序處理。D. 接著，根據(jù)運算流圖進行三重for循環(huán)運算，最后得出結(jié)果。E. grade是指一次FFT或IFFT運算分級的總數(shù)；group是每個級分組的總數(shù); unit是每個組包含蝶形運算的總數(shù)。F. 對于得出自然順序的結(jié)果，可以用兩種方法去實驗，一是輸入數(shù)據(jù)經(jīng)過位倒 序處理后再運算，輸出數(shù)據(jù)為自然順序。二是不先對輸入數(shù)據(jù)做位倒序處理, 運算后在做處理也可以得到自然順序的結(jié)果數(shù)據(jù)。422. 二維圖像

16、FFT 和 IFFT :流程圖：圖4 二維FFT和IFFT流程圖說明：1、二維圖像FFT和IFFT的運算流程圖是相同的，均是按上圖所示2、先通過打開圖像來獲得 width 和height ，并定義二維數(shù)組Bufferwidthheight 。3、width和height分別是原始圖像的寬度和高度；Bufferwidthheight 是用來存放原始數(shù)據(jù)、中間運算數(shù)據(jù)及最終結(jié)果的緩沖區(qū)。4、其實，二維數(shù)組的運算就是一維數(shù)組的變換運算，對Buffer數(shù)組的第一行進行FFT或IFFT運算，之后對矩陣進行倒置，再對此矩陣的第一行進行FFT或IFFT運算，再進行多一次倒置，進而得出結(jié)果。5、對于最終結(jié)果的

17、顯示是通過在 CVI下用復(fù)數(shù)圖像顯示。5. 實驗結(jié)果與分析5.1. 實驗結(jié)果(應(yīng)有實驗結(jié)果的圖片，有結(jié)果分析或說明)下面表格里是3組實驗圖片，從左到右分別是原始圖像、經(jīng)過快速傅里葉變換后 的到的數(shù)據(jù)轉(zhuǎn)換而來的FFT圖像(complex image )以及通過對快速傅里葉變換得到 的數(shù)據(jù)進行快速傅里葉反變換恢復(fù)的圖像。從3組實驗圖片的FFT圖片表示中，可以看出圖像中央是直流低頻成分，四角是 高頻成分。從3組圖像的源圖像與IFFT圖像的比較中可知，從快速傅里葉變換結(jié)果數(shù)據(jù)用 反變換的來的圖像與原始圖像幾乎是相同的，由此證明程序是正確的。原始圖像FFT圖像IFFT圖像冬 J FF圖5三組實驗結(jié)果52

18、項目的創(chuàng)新之處本設(shè)計其實并沒有創(chuàng)新之處。如果要說做的比較好的地方的話，那就是使用malloc（）動態(tài)分配內(nèi)存空間，包括快速傅里葉變換及其反變換的緩沖區(qū)，用于數(shù)組到圖像轉(zhuǎn) 換的一維數(shù)組空間等。使用動態(tài)分配空間可以適應(yīng)不同大小的圖片（圖像寬度和高度可 以不同，但仍然需要滿足2的N次方條件），另外就是動態(tài)分配的內(nèi)存空間使用完后及時 回收，節(jié)省對內(nèi)存空間的資源和提高利用率。5.3.存在問題及改進設(shè)想對本設(shè)計中存在的問題是快速傅里葉變換及其反變換所用的時間比較長， 原因可能有 以下兩點：一是描述complex數(shù)據(jù)類型的實部虛部成員使用 double類型（64位）過大; 二是在快速傅里葉變換及其反變換程序

19、實現(xiàn)時，在一些運算量比較大的地方，例如for循環(huán)里，不必要的重復(fù)運算過多。針對上面問題，本組認為可以從選擇合適的數(shù)據(jù)類型和優(yōu)化程序代碼等方面入手,較少運算時間6. 心得體會6.1. 系統(tǒng)開發(fā)的體會在本設(shè)計中，本組成員體會比較深刻的是分層和面向過程的程序設(shè)計思想。首先，對于一個比較復(fù)雜的程序可以簡化思路， 提高代碼可讀性等等， 這是對程序設(shè) 計的縱向優(yōu)化。在本系統(tǒng)設(shè)計中，主要有兩個地方體現(xiàn)了這一思想。一是對于一維快速 傅里葉變換及其反變換的實現(xiàn)過程，結(jié)合運算流程的特點，將一個運算流程分解成若干 級，每個級中包含若干組，每個組中又分成若干個單個的蝶形運算，這樣子分層，可以 使得程序設(shè)計更為清晰，系統(tǒng)化，也便于理解；二是將一維快速福利葉變換及其反變換 與二維的分離開。其次是面向過程程序設(shè)計。 在系統(tǒng)設(shè)計中，把不同功能的程序封裝成各個獨立的函數(shù)， 使得代碼重用性，可讀性提高，也便于以后的修改。例如把一維快速傅里葉變換或反變 換封裝函數(shù)供二維變換調(diào)用。6.2. 對本門課程的改進意見或建議對本門課程的改進意見或建議：其實，課程的主要目的都是在于提高學(xué)生的學(xué)習(xí)熱 情和創(chuàng)新意識，這有利于多方面開發(fā)學(xué)生智力，提高學(xué)生的綜合素質(zhì)等。 所以，對于這 門課程更有利開展，如果條件允許的話，可以嘗試整合課程教學(xué)資源，例如包括課程