Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Parallelising a set of 2-D frequency transforms in a flexible manner

Parallelising a set of 2-D frequency transforms in a flexible manner

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IEE Proceedings - Vision, Image and Signal Processing — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© IEE
Published

The implementation of parallel two-dimensional frequency transforms intended for the acceleration of image-processing algorithms is described. The way these routines fit into a wider generic format for such parallel routines is also indicated. There is a brief consideration of the design decisions needed to combine choice of efficient routine with wide utility. Due consideration is given to auxiliary functions. Details are included of the book-keeping required to enable real-valued data to be efficiently transformed in a parallel setting.

Inspec keywords: convolution; discrete cosine transforms; parallel algorithms; discrete Fourier transforms; image processing

Other keywords: auxiliary functions; 1D FFT; convolution; image-processing algorithms; generic format; message passing multicomputer; DCT; 2D FFT; parallel 2D frequency transforms; parallel routines; vector radix algorithm; real-valued data

Subjects: Optical information, image and video signal processing; Parallel programming and algorithm theory; Other numerical methods; Computer vision and image processing techniques; Other numerical methods

References

    1. 1)
      • Clark, A.F.: `PRIAM: a demonstrator for PRIPS, design issues', Technical report, 1994.
    2. 2)
      • M. Fleury , L. Hayat , A.F. Clark . Parallel reconfiguration in an image-processingcontext. Concurrency: Pract. Exp.
    3. 3)
      • A.S. WAGNER , H.V. SREEKANTASWAMY , S.T. CHANSON . Performance models for the processor farm paradigm. IEEE Trans. Parallel Distrib. Syst. , 5 , 475 - 489
    4. 4)
      • H. Sava , M. Fleury , A.C. Downton , A.F. Clark . Parallel pipeline implementationof wavelet transforms. IEE Proc. Vision, Image Signal Process. , 6 , 355 - 359
    5. 5)
      • P.N. Swarztrauber . Multiprocessor FFTs. Parallel Computing , 197 - 210
    6. 6)
      • G.L. Anderson . A stepwise approach to computing the multidimensional Fast FourierTransform of large arrays. IEEE Trans. , 3 , 280 - 284
    7. 7)
      • J.J. Dongarra , G.A. Geist , R. Manchel , V.S. Sunderam , A.Y. Zomaya . (1996) Integrated PVM frameworksupports heterogeneous computing, Parallel computing:paradigms and applications.
    8. 8)
      • J.O. Eklundh . A fast computer method for matrix transpose. IEEE Trans. , 801 - 803
    9. 9)
      • Y. Huang , Y. Paker . A parallel FFT algorithm for transputer networks. Parallel Computing , 1 - 12
    10. 10)
      • R.E. Twogood , M.P. Ekstrom , S.K. Mitra . Optimal sectioning procedure forthe implementation of 2-dimensional digital filters. IEEE Trans. , 260 - 268
    11. 11)
      • I.J. Good . The interaction algorithm and practical Fourier analysis. J. Royal Stat. Society Series B , 361 - 372
    12. 12)
      • M.L. Uhrich . Fast Fourier Transforms without sorting. IEEE Trans. , 170 - 172
    13. 13)
      • O. Buneman . Stable on-line creation of sines and cosines of successive angles. Proc. IEEE , 1434 - 1435
    14. 14)
      • P. Duhamel . Implementation of ‘Split-Radix’ FFT algorithms for complex,real, andreal-symmetric data. IEEE Trans. , 2 , 285 - 295
    15. 15)
      • S. Winograd . On computing the Discrete Fourier Transform. Math. Computation , 141 , 175 - 199
    16. 16)
      • M.C. Pease . An adaptation of the fast Fourier transform for parallel processing. J. ACM , 252 - 264
    17. 17)
      • W.H. Press , S.A. Teukolsky , W.T. Vetterling , B.P. Flannery . (1996) Numerical recipes in C.
    18. 18)
      • H.J. Nussbaumer , T.S. Huang . (1981) Two-dimensional convolution and DFT computation. In,editor, Two dimensional digital signal processing II transforms and medianfilters.
    19. 19)
      • H.K. Sorensen , D.L. Jones , M.T. Heidman , C.S. Burrus . Real-valued Fast FourierTransform algorithms. IEEE Trans. , 6 , 849 - 863
    20. 20)
      • J. Makhoul . A fast cosine transform in one and two dimensions. IEEE Trans. , 1 , 27 - 34
    21. 21)
      • S. Zohar , T.S. Huang . (1981) Winograd's discrete Fourier transform algorithm, Two dimensional digital signal processing II transforms and medianfilters.
    22. 22)
      • B.R. Hunt . Minimising the computational time for using the technique of sectioningfordigital filtering of pictures. IEEE Trans. , 1219 - 1222
    23. 23)
      • M. Fleury , L. Hayat , A.F. Clark . Parallelising grey-scale coordinate transforms. IEE Proc. Vision, Image Signal Process. , 4 , 207 - 212
    24. 24)
      • P. Ling . Circumventing the cycle. New Electron. , 30 - 31
    25. 25)
      • M. Fleury , A.C. Downton , A.F. Clark . Modelling pipelines for embedded parallelprocessor system design. Electron. Lett. , 22 , 1852 - 1853
    26. 26)
      • Harvey, D.M., Kshirsagar, S.P., Hobson, C.A., Hartley, D.A., Moorehead, J.D.: `Digital signal-processing systems architectures for image processing', 5th international conference on Image processing and itsapplications, 1995, p. 460–464, IEE Conf. Publ. 410.
    27. 27)
      • D.E. Dudgeon , R.M. Mersereau . (1984) Multidimensional signal processing.
    28. 28)
      • C. van Loan . (1992) Computational frameworks for the Fast Fourier Transform.
    29. 29)
      • R.D. Singleton . An algorithm for computing the mixed radix fast Fourier transform. IEEE Trans. , 2 , 93 - 103
    30. 30)
      • D.H. Bailey . FFTs in external or hierarchical memory. J. Supercomputing , 23 - 35
    31. 31)
      • C. Temperton . Self-sorting mixed-radix Fast Fourier Transforms. J. Computational Phys. , 1 - 23
    32. 32)
      • U. Rüde . (1997) Iterative algorithms in high performance architectures, Euro-Par '97.
    33. 33)
      • Meyer, R., Schwarz, K.: `FFT implementation on DSP-chips — theory and practice', Proceedings of the international conference on ASSP, 1990, 3, p. 1503–1506.
    34. 34)
      • G.E. Rivard . Direct Fast Fourier Transform of bivariate functions. IEEE Trans. , 3 , 250 - 252
    35. 35)
      • Kunieda, H., Itoh, K.: `Parallel 2D-FFT algorithm on a practical multiprocessor system', Proceedings of the 3rd Transputer-Occam internationalconference, 1990, IOS, Amsterdamp. 77–89, .
    36. 36)
      • 3L Ltd., 86/92 CausewaysideEdinburgh, UK, EH9 1PY, `Parallel C user guide', 1991.
    37. 37)
      • Jeong, J., Williams, W.J.: `A fast recursive bit-reversal algorithm', Proceedings of the international conference on ASSP, 1990, 3, p. 1511–1514.
    38. 38)
      • A. Averbuch , E. Gabber , B. Gordissky , Y. Medan . A parallel FFT on an MIMD machine. Parallel Computing , 61 - 74
    39. 39)
      • C.S. Burrus , P.W. Eschenbacher . An in-place, in-order prime factor FFT algorithm. IEEE Trans. , 4 , 806 - 817
    40. 40)
      • Fleury, M., Sava, H., Downton, A.C., Clark, A.F.: `A real-time parallel image-processingmodel', 6th international conference on Image processing and itsapplications, 1997, 1, p. 174–178, IEE Conf. Publ. 443.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-vis_19981693
Loading

Related content

content/journals/10.1049/ip-vis_19981693
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address