快速傅里葉變換的并行化研究

趙曉雷，王 敏

(渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，陜西渭南714000)

快速傅里葉變換的并行化研究

趙曉雷，王 敏

(渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，陜西渭南714000)

研究了傅里葉變換及其實(shí)現(xiàn)形式快速傅里葉變換(FFT)，并給出了圖像處理中FFT并行化算法，通過并行化模擬可以得出數(shù)據(jù)量愈大愈適合并行計(jì)算，當(dāng)處理節(jié)點(diǎn)達(dá)到一定數(shù)量時(shí)它們的并行效果已不明顯.

快速傅里葉變換;圖像處理;并行化

0 引言

離散傅里葉變換(Discrete Fourier Transform，DFT)在計(jì)算機(jī)學(xué)科的圖像處理領(lǐng)域有著廣泛的應(yīng)用，由cooley和Tukey［1］(1965)所研究出的計(jì)算離散傅氏變換的快速傅里葉變換(Fast Fourier Transformation，F(xiàn)FT)，將計(jì)算量從O(n2)下降到了Ο(nlog2n)，從而使FFT在諸多領(lǐng)域內(nèi)得到了廣泛的應(yīng)用.隨著數(shù)字圖像的廣泛應(yīng)用，人們對(duì)圖像處理提出了更高的要求，如何提高運(yùn)算的速度得到了大家的關(guān)注，同時(shí)高性能集群計(jì)算機(jī)具有較高的性價(jià)比及其強(qiáng)大的運(yùn)算能力得到了人們的重視，如何在PC并行集群計(jì)算機(jī)上提高離散傅里葉變換速度是研究熱點(diǎn).

1 傅里葉函數(shù)變換

1.1 傅里葉變換

假定f(m，n)是一個(gè)包含m和n兩個(gè)變量的函數(shù)，則該函數(shù)的二維傅里葉變換定義形式如下：

式 (1)中，ω1和ω2為頻域變量，其單位為弧度 /采樣單元.通常稱函數(shù)F(ω1，ω2)為f(m，n)的頻域表示，F(xiàn)(ω1，ω2)是復(fù)變函數(shù)，其中變量ω1和ω2的周期為2π，由于這種周期性，在圖像顯示時(shí)，兩個(gè)變量的取值大小為：-π≤ω1，ω2≤π.

傅里葉反變換［2］定義如下：

1.2 離散傅里葉變換及快速傅里葉變換

計(jì)算機(jī)在處理傅里葉變換時(shí)采用離散傅里葉變換(DFT)，采用離散傅里葉變換基于如下原因：

(1)由于離散傅里葉變換是建立在離散的數(shù)據(jù)基礎(chǔ)之上的，適合計(jì)算機(jī)參與運(yùn)算處理.

(2)可以采用一種快速傅里葉變換(FFT)來實(shí)現(xiàn)離散傅里葉變換.

快速傅里葉變換［3］的設(shè)計(jì)思想是：首先將原函數(shù)通過傅里葉變換將其分解為奇數(shù)項(xiàng)和偶數(shù)項(xiàng)，將分解得到的奇數(shù)項(xiàng)和偶數(shù)項(xiàng)不停地進(jìn)行相加減運(yùn)算，最終得到運(yùn)算的結(jié)果，實(shí)際上該算法的實(shí)現(xiàn)過程就是將較為復(fù)雜的乘法運(yùn)算轉(zhuǎn)換為簡(jiǎn)單的加減法運(yùn)算，通過一定量的加法運(yùn)算來代替乘法運(yùn)算，從而降低運(yùn)算的復(fù)雜度，提高運(yùn)算的速度.

對(duì)于的N=2m的DFT的計(jì)算，通過計(jì)算兩個(gè)N/2點(diǎn)的DFT來得到N個(gè)的DFT.

設(shè)離散函數(shù)f(m，n)在區(qū)域0≤m≤M-1，0≤n≤N-1內(nèi)非零，則二維的M×NFFT和M×N逆FFT關(guān)系如下：

從而可以得出，F(xiàn)(p，q)是f(m，n)的DFT系數(shù).

其中 p=0，1，…，M-1;q=0，1 ，…，N-1;m=0，1，…，M-1;n=0，1，…，N-1.

離散傅里葉變換(DFT)由于含有大量的加法和乘法從而其運(yùn)算量級(jí)在N2，快速傅里葉變換(FFT)是將DFT進(jìn)行分解為加法，從而使運(yùn)算量降低到Nlog2N.FFT算法在圖像上的實(shí)現(xiàn)過程如下：

讀入圖像矩陣后，對(duì)其轉(zhuǎn)置矩陣［4］按照以行進(jìn)行一維FFT變換，將經(jīng)過變換的轉(zhuǎn)置矩陣再進(jìn)行一次轉(zhuǎn)置變換得到一個(gè)新的矩陣，后對(duì)新矩陣做一維的FFT變換，最終得到的矩陣就為圖像的二維FFT變換矩陣.

1.3 集群計(jì)算機(jī)下基于BSP模型下的并行FFT

為了適應(yīng)圖像并行處理的實(shí)時(shí)性要求，在進(jìn)行圖像并行處理時(shí)需要一個(gè)并行計(jì)算機(jī)系統(tǒng)，從而引入了集群計(jì)算機(jī)系統(tǒng)架構(gòu)［5］，該系統(tǒng)是以網(wǎng)絡(luò)工作站NOW(net works of workstation)形式的集群計(jì)算機(jī)，在該系統(tǒng)上配以負(fù)載平衡、動(dòng)態(tài)任務(wù)分配機(jī)制、消息傳遞機(jī)制等技術(shù)，通過高速網(wǎng)絡(luò)連接構(gòu)成單一資源鏡的系統(tǒng)軟件，是COW(cluster of workstation)的一種集群形式，具有COW所具有的屬性，其性質(zhì)如下圖所示：

圖1 實(shí)時(shí)集群計(jì)算機(jī)處理系統(tǒng)結(jié)構(gòu)圖

2 圖像FFT處理并行化設(shè)計(jì)

圖像的快速傅里葉變換的并行算法設(shè)計(jì)如下：

首先假定圖像的大小為DateSize，參與并行運(yùn)算的處理機(jī)個(gè)數(shù)為TasKNum，在整個(gè)并行處理系統(tǒng)中，首先主控節(jié)點(diǎn)按照如下步驟運(yùn)行：

(1)首先接受用戶的輸入，便可以得到參與運(yùn)算的圖像的大小為DateSize，同時(shí)可以從外部輸入得到參與并行計(jì)算的從節(jié)點(diǎn)數(shù)TaskNum，從而得到一個(gè)大小為DateSize1的數(shù);

(2)主控節(jié)點(diǎn)產(chǎn)生TaskNum個(gè)進(jìn)程，通過集群計(jì)算機(jī)中負(fù)載平衡系統(tǒng)分配到各個(gè)從節(jié)點(diǎn)上進(jìn)行計(jì)算;

(4)主節(jié)點(diǎn)等待接收從節(jié)點(diǎn)傳來的結(jié)果數(shù)據(jù);

(5)在主節(jié)點(diǎn)上對(duì)接收的數(shù)據(jù)排序，并進(jìn)行IFFT反變換，結(jié)束程序.

從節(jié)點(diǎn)()

(1)接收主節(jié)點(diǎn)傳來的DataSize1、TaskNum和Id參數(shù);

(2)依據(jù)算法的思想，可以得到為每個(gè)節(jié)點(diǎn)分配的數(shù)據(jù)位為：Ptask_Node=DataSize1/TaskNum;

(3)在各個(gè)節(jié)點(diǎn)上進(jìn)行FFT計(jì)算，并得到計(jì)算的結(jié)果;

(4)將從節(jié)點(diǎn)中得到的計(jì)算結(jié)果通過進(jìn)程控制發(fā)送到主控節(jié)點(diǎn);

(5)從節(jié)點(diǎn)結(jié)束運(yùn)算.

2018年11月5日，以“新時(shí)代，共享未來”為主題的首屆中國國際進(jìn)口博覽會(huì)在上海隆重開幕。展會(huì)吸引了全球172個(gè)國家/地區(qū)和國際組織的3600多家企業(yè)參會(huì)，展覽總面積達(dá)30萬m2，進(jìn)博會(huì)既是世界期待、萬商云集的經(jīng)貿(mào)盛宴，也是中國向世界學(xué)習(xí)、與國際接軌的發(fā)展良機(jī)。SEW作為世界領(lǐng)先的傳動(dòng)領(lǐng)域供應(yīng)商之一，以其經(jīng)典的“SEW紅”精彩亮相2018進(jìn)博會(huì)，充滿濃重的工業(yè)色彩和強(qiáng)烈視覺沖擊的展位引起眾多觀眾駐足。

為了盡可能快的提高處理速度，在進(jìn)行圖像分塊時(shí)盡可能進(jìn)行整數(shù)分塊，假設(shè)有n個(gè)處理機(jī)，在進(jìn)行模塊分配時(shí)，模塊的大小應(yīng)為2n，這樣既能將圖像進(jìn)行充分的分配模塊，又能保證圖像完全進(jìn)行分配，不至于有多余的部分沒有分配，從而加長處理的總時(shí)間量，這些操作通過系統(tǒng)的進(jìn)程進(jìn)行分配管理.

3 實(shí)驗(yàn)結(jié)果分析

加速比

加速比［6］的定義：

上式中p為并行運(yùn)算中參與運(yùn)算的處理機(jī)的數(shù)目，Tp為在個(gè)處理機(jī)上進(jìn)行并行運(yùn)算及相互間通信所耗費(fèi)的時(shí)間，Ts為單機(jī)完成處理所需要的時(shí)間，研究并行算法的目的是：盡可能多的提高并行系統(tǒng)的加速比.通常在實(shí)際中引起加速比變化的原因如下：

(1)在算法的設(shè)計(jì)中，并行度不夠完全或負(fù)載平衡分配任務(wù)不夠合理;

(2)并行處理機(jī)相互間通信所在的時(shí)間比重過大;

(3)由于處理的任務(wù)量不夠大而導(dǎo)致的并行度過小.

效率

并行效率：并行效率指的是在并行處理系統(tǒng)中所產(chǎn)生的加速比和該系統(tǒng)參與運(yùn)算的處理機(jī)數(shù)目之比，并行效率的定義如下：

顯然，O ＜Ep≤1，當(dāng)Ep=1時(shí)，達(dá)到完全加速比.

為了驗(yàn)證該算法的有效性和可行性，對(duì)FFT變化和反變換在模擬并行環(huán)境中進(jìn)行運(yùn)算，表1是對(duì)圖像circuit.tif進(jìn)行FFT變換及其反變換，得到的測(cè)試結(jié)果.

實(shí)驗(yàn)中以256×256、512×512和1024×1024三個(gè)不同大小像素的圖像，分別對(duì)其進(jìn)行并行化模擬運(yùn)算，假設(shè)試驗(yàn)中處理機(jī)數(shù)依次為 1，2，4，8.

從表中的加速比和效率數(shù)據(jù)可以看出，伴隨著節(jié)點(diǎn)數(shù)的增加，它們的加速比有不斷增大的趨勢(shì)，但其效率伴隨著節(jié)點(diǎn)數(shù)的增多也有增大的趨向，當(dāng)處理機(jī)個(gè)數(shù)達(dá)到某個(gè)固定值4時(shí)，圖像的并行效率達(dá)到最大值，隨后隨著處理機(jī)數(shù)的增加而其并行效率在降低，緣由在于當(dāng)處理機(jī)個(gè)數(shù)不斷增加時(shí)，它們相互之間的通行量會(huì)隨著處理機(jī)個(gè)數(shù)增加而劇烈增大，從而使相互間的并行效率降低.從理論上可知，并行效率是伴隨著加速比的增加而增大的，但從實(shí)際的試驗(yàn)數(shù)據(jù)中可以看出加速比和效率并不是隨著處理機(jī)數(shù)的增加而無限增大的，當(dāng)處理機(jī)個(gè)數(shù)達(dá)到某個(gè)固定值時(shí)，并行的效率并不能再提高，而是隨著節(jié)點(diǎn)數(shù)增多時(shí)并行效率在降低，并行處理的意義已不再明顯.從實(shí)驗(yàn)中的數(shù)據(jù)可以看出，對(duì)于不同規(guī)模的數(shù)據(jù)，當(dāng)節(jié)點(diǎn)數(shù)趨于一個(gè)定值時(shí)，它們的并行處理效率達(dá)到最大;通過對(duì)效率分析，發(fā)現(xiàn)當(dāng)數(shù)據(jù)量愈大采用并行處理時(shí)的加速比和效率有明顯增大.

表1 圖像FFT變換和IFFFT變換的測(cè)試結(jié)果

4 結(jié)語

通過對(duì)快速傅里葉變換并行化的研究發(fā)現(xiàn)，當(dāng)數(shù)據(jù)量愈大時(shí)愈適合并行計(jì)算，而且它們的較大的加速比和較高的效率，但隨著并行節(jié)點(diǎn)數(shù)的增加，并行加速比在增加，但效率在達(dá)到一個(gè)較大值后隨之降低.

［1］［美］格拉法科斯.傅里葉分析(英文版)［M］.北京：機(jī)械工業(yè)出版社，2006.

［2］冷建華.傅里葉變換［M］.北京：清華大學(xué)出版社，2004.

［3］蔣長錦，蔣勇.快速傅里葉變換及其C程序［M］.合肥：中國科學(xué)技術(shù)出版社，2004.

［4］薛利敏，舒尚奇.利用行列式性質(zhì)求矩陣的特征值［J］.渭南師范學(xué)院學(xué)報(bào)，2010，25(2)：13-14.

［5］H.J.Siegel.Report of the Purdue Workshop on Grand Challenges in Computer Architecture for the Support of High Performance Computing［J］.Journal of Parallel and Distributed Computing，1992，16(3)：199-211.

［6］史鳳麗.基于集群計(jì)算機(jī)的圖像并行處理［D］.西安：西安科技大學(xué)碩士論文，2010.

Research on Parallelization of Fast Fourier Transformation

ZHAO Xiao-lei，WANG Min
(School of Mathematics and Information Science，Weinan Teachers University，Weinan 714000，China)

This paper studies Fourier Transformation and its applied form，F(xiàn)ast Fourier Transformation(FFT).Meanwhile，the parallelization algorithm of image processing based on FFT is introduced in the paper.The results of the parallelization stimulation indicate that the larger amount of data is more suitable for the parallelization computation.The effect of the parallelization is not obvious when the processing node reaches a certain amount.

Fast Fourier Transformation;image processing;parallelization

O174.2

A

1009—5128(2011)12—0027—04

2011—05—26

渭南師范學(xué)院研究生專項(xiàng)項(xiàng)目(11YKZ014)

趙曉雷(1978—)，男，河南洛陽人，渭南師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院講師，碩士.研究方向：圖形圖像處理.

［責(zé)任編輯 牛懷崗］