IBM Journal of Research and Development
IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
Journal of Research
and Development
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Recent publications  
    Author's Guide  
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 26, Number 6, Page 708 (1982)
Image Processing and Pattern Recognition
  Full article: arrowPDF   arrowCopyright info


Reduced Data Re-Order Complexity Properties of Polynomial Transform 2D Convolution and Fourier Transform Methods

by T. A. Kriz
This paper presents new results concerning the matrix data re-order requirements of polynomial-transform-based 2D convolution and 2D Fourier Transform methods which can be employed in digital processing of images and other 2D problems. The results indicate that several power-of-2 length-modified ring polynomial transform methods developed by Nussbaumer allow the total avoidance of the row-column matrix transpose commonly encountered in other algorithmic approaches, while also providing a number of other computational advantages. It is demonstrated that this property can be the source of significantly improved throughput on a number of existing data processing structures. An execution time comparison with an efficient Fast Fourier Transform algorithm base is made assuming the use of general register architecture and array processor units. It is also assumed that one makes use of recently developed efficient matrix transpose methods by Eklundh and Ari to support 2D FFT data re-order requirements. These comparisons demonstrate a two to four times throughput improvement for the use of the polynomial transform method in place of the 2D FFT approach to circularly convolve or generate 2D Fourier transforms for large 2D fields in the range 1024 × 1024 to 8192 × 8192.
Related Subjects: Algorithms; Complexity; Fourier transforms; Image processing; Mathematics (applied)