日本在线www-日本在线播放一区-日本在线不卡免费视频一区-日本在线不卡视频-成人影院久久久久久影院-成人影院一区二区三区

    唐俊奇  (1967－)
男，福建莆田人，副教授/高級工程師，工學學士，(湄洲灣職業技術學院，福建  莆田  351254)研究方向為計算機系統結構、計算機網絡。

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

關鍵詞：多處理機；傅里葉變換；并行算法

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

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

    在數字圖像處理中常常要用經過適當的數學處理后不帶比例因子的離散傅里葉變換的顯示方式表示[1]，即

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

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

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

   

    式中的內部累加和是作用于一行中N個點上的一維DFT操作，它將生成一個經變換的行；而外部累加和是作用于一列中N個點上的一維DFT作用。可寫成：

   

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

2　傅里葉變換在多處理機數字圖像處理中的優越性

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

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

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

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

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

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

   

    在使用記號w=e-2πi/N后，可得:

   

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

    3.1　順序代碼——單處理機使用的代碼
 
    產生全部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個被變換點，x[k]為第k個輸入，共有N個輸入點，而w=e-2πi/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為臨時變量。

    3.2　并行代碼的實現——多處理機中使用的代碼

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

    3.2.1 基本的主從實現

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

圖1  直接實現DFT的主從方法

    3.2.2 流水線實現 

    該算法可采用流水線結構加以實現，因為內層循環中的每次迭代需要使用前一次迭代生成的值。將X[h]的內層循環展開可得：

 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]
  ????
　
    其中的每一對語句

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

    可由一個分離的流水線級完成。

    因為w0＝1，w項的某些可以歸約掉。

4　快速傅里葉變換

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

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

   

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

   

    其中第一項求和處理具有偶下標的x值，而第二項求和處理具有奇下標的x值。重寫后可得：

   

    或是

   

    現在可將每個和看成是一個N/2離散傅里葉變換分別作用于N/2偶數點和N/2奇數點。因此有：

     

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

    
   

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

    4.1　順序代碼的實現方法

    順序計算的時間復雜性基本上是O（logN），因為共有logN步，而每一步需要進行正比于N的計算，這里的N是指共有N個數。該算法可用遞歸或迭代方法加以實現。

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

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

    同樣地，如果處理器數小于數據點數，每個處理器將分配有一組數據點，但此時的處理器間通信模式仍具有相同特征。假定有p個處理器和N個數據點，則每個處理器有N/p行。如果N和p均為2的乘方，則下面處理器的編號取數據點下標中logp高位，余下的位則用來標識組內的數據點。圖3中顯示了N/p=4的情況。

    4.3   分析

    （1）計算 給定p個處理器和N個數據點，每個處理器在每一步將計算N/p個點，而每一個點的計算需進行一次乘法和一次加法。因共需logN步，故并行計算的時間復雜性由下式確定：

　　  tcomm=O(NlogN)

圖 3   將處理器映射到16點FFT計算

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

　　   tcomm=O(logN)

    如果p<N，處理器間通信僅出現在前logp步中。在第一步中，所有p個處理器進行交換；在下一步時，僅有一半處理器進行數據交換；在再下一步時，僅有1/4處理器進行交換，以此類推。如果互連網絡允許同時進行交換，則通信時間復雜性可簡化成由下式確定：

tcomm=O(logP)

    當然，如果互連網絡只允許進行順序通信，則上述的這些復雜性將變糟。

5　結束語

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

參考文獻：

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

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

    [3] 陳智勇. 計算機系統結構[M].西安：西安電子科技大學出版社，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] 尚明生.相關任務圖的一種有效并行調度算法[J].計算機工程,2005,31(14),18-21.