久久久91-久久久91精品国产一区二区-久久久91精品国产一区二区三区-久久久999国产精品-久久久999久久久精品

    唐俊奇  (1967－)
男，福建莆田人，副教授/高級(jí)工程師，工學(xué)學(xué)士，(湄洲灣職業(yè)技術(shù)學(xué)院，福建  莆田  351254)研究方向?yàn)橛?jì)算機(jī)系統(tǒng)結(jié)構(gòu)、計(jì)算機(jī)網(wǎng)絡(luò)。

摘要：單處理機(jī)系統(tǒng)難于滿足大型數(shù)字圖像的實(shí)時(shí)處理要求，多處理機(jī)并行工作系統(tǒng)可以提高數(shù)字圖像處理的效率和效果。本文分析多處理機(jī)系統(tǒng)在數(shù)字圖像處理中的并行化機(jī)會(huì)，運(yùn)用數(shù)字圖像處理中傅里葉變換的特點(diǎn)，在多處理機(jī)中實(shí)現(xiàn)流水線算法、FFT算法的并行化(二元交換算法)、快速傅里葉變換、基本的主從實(shí)現(xiàn)等算法，解決了傅里葉變換和快速傅里葉變換中N取較大值時(shí)所產(chǎn)生的順序復(fù)雜性，進(jìn)而使多處理機(jī)系統(tǒng)中能夠使多個(gè)處理機(jī)之間能夠更加協(xié)調(diào)工作，更加有效地利用CPU。

關(guān)鍵詞：多處理機(jī)；傅里葉變換；并行算法

Abstract: It’s difficult for single processor to satisfy real time processing requirements of large digital image and multiprocessor parallel operation system can enhance the efficiency and result of digital image processing. This paper analyses the parallel opportunity of the multiprocessor system in digital image processing, uses the characteristics of the Fourier Transform in the digital image processing, fulfils the pipeline algorithm, FFT algorithm parallel (dual exchange algorithm) fast Fourier transform, basic master/slave realization and other algorithms in the multiprocessor, settles the sequence complexity when n selects higher value in Fourier transform and FFT, by which a number of processors can work together better in a multiprocessor system and make better use of CPU.

Key words: Multiprocessor; Fourier transform; Parallel algorithm

    圖像的增強(qiáng)、恢復(fù)和壓縮主要手段是傅里葉變換和快速傅里葉變換。多年來，人們一直在單處理機(jī)的計(jì)算機(jī)環(huán)境下進(jìn)行數(shù)字圖像處理和科學(xué)試驗(yàn)。由于單處理機(jī)的計(jì)算機(jī)系統(tǒng)的處理速度、效率和效果不盡人意，因此人們渴望著有更高性能和更高計(jì)算速度的計(jì)算機(jī)出現(xiàn)。多處理機(jī)系統(tǒng)正可以滿足這方面的要求[1，2，3]。

    在數(shù)字圖像處理中常常要用經(jīng)過適當(dāng)?shù)臄?shù)學(xué)處理后不帶比例因子的離散傅里葉變換的顯示方式表示[1]，即

   
    
    在該式中求和計(jì)算比較容易，特別是如果指數(shù)項(xiàng)的值存放在查找表中時(shí)，對(duì)于N點(diǎn)（如方程式所列出的那樣）仍需N2次乘法和加法，即其順序復(fù)雜性為O（N2）。一般情況下人們很難接受這種順序復(fù)雜性(特別是N取較大值時(shí))[2]，需要研究一個(gè)合理的算法，以適應(yīng)科學(xué)和生產(chǎn)的需要。本文分析多處理機(jī)系統(tǒng)在數(shù)字圖像處理中的并行化機(jī)會(huì)，闡述了多個(gè)處理機(jī)在數(shù)字圖像處理中的傅里葉變換和快速傅里葉變換并行化算法，它對(duì)克服N取較大值時(shí)所產(chǎn)生的順序復(fù)雜性并解決如何使多個(gè)處理機(jī)間并行協(xié)調(diào)工作，尋找合適的并行算法（傅里葉變換時(shí)）以提高整個(gè)系統(tǒng)的性能具有極其重要的現(xiàn)實(shí)意義。

1　圖像處理中傅里葉變換并行化的可行性

    在圖像處理中，輸入的形式是離散二級(jí)函數(shù)的一組像素。使用j和k坐標(biāo)，在（j,k）坐標(biāo)中像素是x(j,k)。假定該圖像是一個(gè)方陣，即N＝M，這樣二維的傅里葉變換可表示為：

   

    式中的內(nèi)部累加和是作用于一行中N個(gè)點(diǎn)上的一維DFT操作，它將生成一個(gè)經(jīng)變換的行；而外部累加和是作用于一列中N個(gè)點(diǎn)上的一維DFT作用。可寫成：

   

    因此，二維的DFT能被分為兩個(gè)順序階段，一個(gè)階段作用于行元素而另一階段作用于（已經(jīng)過變換）列元素。因此需要實(shí)現(xiàn)的僅是一維DFT算法[4]。很顯然，此過程也可從列開始，然后再是行。具體選擇則依賴于為實(shí)現(xiàn)有效并行原始數(shù)據(jù)是如何存放的。由于行變換相互獨(dú)立，且列變換也相互獨(dú)立，因而存在有很多的并行化機(jī)會(huì)，這樣也為使用多處理機(jī)提供優(yōu)越性。

2　傅里葉變換在多處理機(jī)數(shù)字圖像處理中的優(yōu)越性

    在頻率域內(nèi)，圖像處理和分析的應(yīng)用非常廣泛。DFT的一個(gè)應(yīng)用領(lǐng)域之一是頻率濾波，在平滑和邊緣中都要用到它（低通和高通濾波器）。頻率濾波早期采用加權(quán)掩碼，它可用卷積操作描述[3]：
　　  
    h(j,k)=g(j,k)*f(j,k)

    與對(duì)稱掩碼的互相關(guān)函數(shù)的操作相同，式中g(shù)(j,k)描述加權(quán)掩碼（濾波器），而f(j,k)描述圖像。可以證明函數(shù)積的傅里葉變換可由各函數(shù)變換的卷積確定。

    因此，兩個(gè)的卷積可將每個(gè)函數(shù)先進(jìn)行傅里葉變換，然后將兩個(gè)變換相乘得到
  
    H(j,k)=G(j,k) ×F(j,k)

    式中F(j,k)是f(j,k)的傅里葉變換，則G(j,k)是g(j,k)的傅里葉變換。此后對(duì)其取反變換，就可使結(jié)果回到原來的空間域。這種濾波方法比起在空間域中使用簡單的加權(quán)掩碼方法需要更多的計(jì)算量，但它可完成其他更復(fù)雜的操作。也可對(duì)兩個(gè)完整圖像進(jìn)行卷積以產(chǎn)生一個(gè)新的圖像。重要的是，由于兩者的變換是相互獨(dú)立的，因此它們可并行地完成，同樣也為使用多處理機(jī)提供可能性。

3 離散傅里葉變換算法的并行化

    基本的DFT算法以及它的并行化方法可以從以下公式[1]開始：

   

    在使用記號(hào)w=e-2πi/N后，可得:

   

    式中w為旋動(dòng)系數(shù)(twiddle factor)。每個(gè)輸入值必須乘以旋動(dòng)系數(shù)。用w -1替代w就可得到反變換。

    3.1　順序代碼——單處理機(jī)使用的代碼
 
    產(chǎn)生全部N點(diǎn)的DFT的順序代碼形式可為：

  for (k =0 ; k < N; k++) {      /* for every point */
   x [k] =0;
   for (j =0 ; j<N; j++)
     x[k] =x[k] +wj*k* x[j];     /* compute summation */
  }

    其中X[k]為第k個(gè)被變換點(diǎn)，x[k]為第k個(gè)輸入，共有N個(gè)輸入點(diǎn)，而w=e-2πi/N。求累加和的計(jì)算要進(jìn)行復(fù)數(shù)運(yùn)算。由于每步求累加和要使用前一點(diǎn)的w的升冪值并乘以wk（即w(j-1)*k*wk=wj*k），因此，上述代碼可重寫成：

　　for (k =0 ; k < N; k++) {
  x [k] =0;
  　a=1;
   for (j =0 ; j<N; j++)｛
     x[k] =x[k] +a * x[j]; 
     a=a*wk;
  }
　 }
　
    其中a為臨時(shí)變量。

    3.2　并行代碼的實(shí)現(xiàn)——多處理機(jī)中使用的代碼

    在多處理機(jī)系統(tǒng)中，可以采用幾種方法使上述代碼并行化。這里將只簡單涉及最明顯的主從方法、較明顯的流水線方法以及在最后敘述的矩陣－向量乘積方法。

    3.2.1 基本的主從實(shí)現(xiàn)

    在主從方法中，N個(gè)從進(jìn)程中的每一個(gè)可被指定來產(chǎn)生一個(gè)變換值，即第k個(gè)從進(jìn)程生成x[k]。所需的a值可由主進(jìn)程預(yù)先求得，如圖1所示。也可使每個(gè)從進(jìn)程同時(shí)計(jì)算它們各自的值，該方法要求每個(gè)從進(jìn)程擁有一份所在輸入點(diǎn)的拷貝，從而會(huì)使存儲(chǔ)需要增加到N倍。并行求解的時(shí)間復(fù)雜性為O（N），相對(duì)于順序算法實(shí)現(xiàn)的O（N2），該并行方法有了很大的優(yōu)化。但是，數(shù)據(jù)點(diǎn)數(shù)很可能遠(yuǎn)大于可用的進(jìn)程數(shù)。此時(shí)，每個(gè)從進(jìn)程將需要進(jìn)行多次累加和。

圖1  直接實(shí)現(xiàn)DFT的主從方法

    3.2.2 流水線實(shí)現(xiàn) 

    該算法可采用流水線結(jié)構(gòu)加以實(shí)現(xiàn)，因?yàn)閮?nèi)層循環(huán)中的每次迭代需要使用前一次迭代生成的值。將X[h]的內(nèi)層循環(huán)展開可得：

 x[k]=0;
 a=1;
 x[k]=x[k]+a*x[0];
 a=a*wk；
 x[k]=x[k]+a*x[1]
 a=a*wk；
　　x[k]=x[k]+a*x[2]
　　a=a*wk;
　　x[k]=x[k]+a*x[3]
  ????
　
    其中的每一對(duì)語句

 x[k]=x[k]+a*x[0]
 a=a*wk;

    可由一個(gè)分離的流水線級(jí)完成。

    因?yàn)閣0＝1，w項(xiàng)的某些可以歸約掉。

4　快速傅里葉變換

    快速傅里葉變換（Fast Fourier Transform,FFT）是獲取離散傅里葉變換的快速算法，它可使時(shí)間復(fù)雜性從O（N2）降為O（NlogN）。在下面的論述中，我們假定N是2的次方。

    筆者從具有比例因子的離散傅里葉變換方程開始進(jìn)行討論，以表明比例因子不會(huì)影響算法的推導(dǎo)：

   

    式中w=e-2πi/N。下面我們描述的一個(gè)公式是將求和分解成下兩部分來進(jìn)行的：

   

    其中第一項(xiàng)求和處理具有偶下標(biāo)的x值，而第二項(xiàng)求和處理具有奇下標(biāo)的x值。重寫后可得：

   

    或是

   

    現(xiàn)在可將每個(gè)和看成是一個(gè)N/2離散傅里葉變換分別作用于N/2偶數(shù)點(diǎn)和N/2奇數(shù)點(diǎn)。因此有：

     

    其中k=0，1，…，N－1，X偶是具有偶下標(biāo)數(shù)x0，x2，x4，…的N/2點(diǎn)的DFT，而X奇則是具有奇下標(biāo)數(shù)x1，x3，x5，…的N/2點(diǎn)的DFT。
 
    現(xiàn)在，若假設(shè)k限制為0，1，…，N/2-1，即全部N個(gè)值的前N/2個(gè)值。這樣整個(gè)序列可分成為兩部分：

    
   

    因?yàn)閣k+n/2=-wk，其中0≤k≤N/2。這樣我們可用兩個(gè)N/2個(gè)點(diǎn)變換來計(jì)算xk和xk+N/2。
 
    以上每一個(gè)N/2個(gè)點(diǎn)的DFT又可分解成兩個(gè)N/4個(gè)點(diǎn)的DFT，此分解可一直進(jìn)行下去直到對(duì)單點(diǎn)進(jìn)行變換。一個(gè)單點(diǎn)的DFT即是該點(diǎn)的值。對(duì)每個(gè)要變換的點(diǎn)都要進(jìn)行上述的計(jì)算。應(yīng)注意到，根據(jù)X偶和X奇中所使用的數(shù)的個(gè)數(shù)以及指定的X變換的輸出下標(biāo)，在不同級(jí)上出現(xiàn)的不同值。注意到由于數(shù)的個(gè)數(shù)以2倍系數(shù)減少，相應(yīng)地w的冪以2倍系數(shù)增加，從而方便了旋動(dòng)系數(shù)的獲得。（w=e2kπi/(N/2)，e2kπi/(N/4)=w2，e2kπi/(N/8)=w4等）。為清晰起見，1/2比例因子也已被省略，從而在原來的DFT方程中若沒有比例因子，則它就不會(huì)存在。

    4.1　順序代碼的實(shí)現(xiàn)方法

    順序計(jì)算的時(shí)間復(fù)雜性基本上是O（logN），因?yàn)楣灿衛(wèi)ogN步，而每一步需要進(jìn)行正比于N的計(jì)算，這里的N是指共有N個(gè)數(shù)。該算法可用遞歸或迭代方法加以實(shí)現(xiàn)。

    4.2　FFT算法的并行化(二元交換算法)

    由于FFT的順序計(jì)算的時(shí)間復(fù)雜性為O（NlogN），因而當(dāng)使用N個(gè)處理器時(shí)，理想的成本優(yōu)化并行計(jì)算時(shí)間復(fù)雜性為O(logN)。下面闡述并行化的方法：在圖2中，假定為每個(gè)數(shù)據(jù)點(diǎn)（對(duì)第j個(gè)進(jìn)程為x[j]，相應(yīng)于圖2中的一行）分配一個(gè)處理器。每個(gè)進(jìn)程最終將生成一個(gè)變換點(diǎn)。圖2中的連接模式稱為蝶形連接，如果每一行分配一個(gè)處理器，則它可很好地映射到超立方體上，這是因?yàn)楸炯?jí)產(chǎn)生的結(jié)果將傳送給下一級(jí)的進(jìn)程，而該進(jìn)程所擁有的地址僅與本級(jí)的地址有一位不相同。例如，在第一個(gè)通信步中，處理0將與處理器8通信，而在下一步中與處理器4通信，再一下步與處理器2通信，最后一步與處理器0通信。

    同樣地，如果處理器數(shù)小于數(shù)據(jù)點(diǎn)數(shù)，每個(gè)處理器將分配有一組數(shù)據(jù)點(diǎn)，但此時(shí)的處理器間通信模式仍具有相同特征。假定有p個(gè)處理器和N個(gè)數(shù)據(jù)點(diǎn)，則每個(gè)處理器有N/p行。如果N和p均為2的乘方，則下面處理器的編號(hào)取數(shù)據(jù)點(diǎn)下標(biāo)中l(wèi)ogp高位，余下的位則用來標(biāo)識(shí)組內(nèi)的數(shù)據(jù)點(diǎn)。圖3中顯示了N/p=4的情況。

    4.3   分析

    （1）計(jì)算 給定p個(gè)處理器和N個(gè)數(shù)據(jù)點(diǎn)，每個(gè)處理器在每一步將計(jì)算N/p個(gè)點(diǎn)，而每一個(gè)點(diǎn)的計(jì)算需進(jìn)行一次乘法和一次加法。因共需logN步，故并行計(jì)算的時(shí)間復(fù)雜性由下式確定：

　　  tcomm=O(NlogN)

圖 3   將處理器映射到16點(diǎn)FFT計(jì)算

    （2）通信  若p=N，則每一步都需通信，因而在logN步中的每一步在處理器對(duì)之間要進(jìn)行一次數(shù)據(jù)交換。假定所使用的是超立方體或其他允許進(jìn)行同時(shí)交換的互連網(wǎng)絡(luò)，則此時(shí)的通信時(shí)間復(fù)雜性由下式給定：

　　   tcomm=O(logN)

    如果p<N，處理器間通信僅出現(xiàn)在前l(fā)ogp步中。在第一步中，所有p個(gè)處理器進(jìn)行交換；在下一步時(shí)，僅有一半處理器進(jìn)行數(shù)據(jù)交換；在再下一步時(shí)，僅有1/4處理器進(jìn)行交換，以此類推。如果互連網(wǎng)絡(luò)允許同時(shí)進(jìn)行交換，則通信時(shí)間復(fù)雜性可簡化成由下式確定：

tcomm=O(logP)

    當(dāng)然，如果互連網(wǎng)絡(luò)只允許進(jìn)行順序通信，則上述的這些復(fù)雜性將變?cè)恪?BR>
5　結(jié)束語

    充分運(yùn)用數(shù)字圖像處理中傅里葉變換和快速傅里葉變換的特點(diǎn)在多處理機(jī)中巧妙地實(shí)現(xiàn)流水線算法、FFT算法的并行化(二元交換算法)、快速傅里葉變換、基本的主從實(shí)現(xiàn)等算法，解決了傅里葉變換和快速傅里葉變換中N取較大值時(shí)所產(chǎn)生的那種令人難于接受的順序復(fù)雜性；進(jìn)而使多處理機(jī)系統(tǒng)中多個(gè)處理機(jī)之間能夠更加協(xié)調(diào)工作，更加有效地利用CPU，為工作提供了方便，達(dá)到了預(yù)期效果。

參考文獻(xiàn)：

    [1] 陳國良.并行算法的設(shè)計(jì)與分析[M].北京：高等教育出版社，2002.

    [2] [美]Rafael C.Gonzalez，Richard E.Woods等著，阮秋琦，阮宇智等譯，數(shù)字圖像處理[M].北京：電子工業(yè)出版社，2003.

    [3] 陳智勇. 計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)[M].西安：西安電子科技大學(xué)出版社，2004.

    [4] WAH B.W., G-J.LI,AND C.F.Yu (1985), ”Multiprocessing of Combinational Search Problems,” Computer,Vol.18,NO 6,pp.93-108.

    [5] 尚明生.相關(guān)任務(wù)圖的一種有效并行調(diào)度算法[J].計(jì)算機(jī)工程,2005,31(14),18-21.