Image Partitioning on Spiral Architecture

Introduction

Image processing is a traditional area in computing science which has been used widely in many applications including the film industry, medical imaging, industrial manufacturing, weather forecasting etc. With the development of new algorithms and the rapid growth of application areas, a key issue emerges and attracts more and more challenging research in digital image processing. That issue is the dramatically increasing computation workload in image processing. The reasons can be classified into three groups: relatively low-power computing platform, huge image data to be processed and the nature of image-processing algorithms.

Inefficient computing is a relative concept. The microcomputer has been powerful enough in the last decade to make personal image processing practically feasible to the individual researcher for inexpensive image processing (Miller, 1993; Schowengerdt & Mehldau, 1993). In recent years, although such systems still functionally satisfy the requirements of most general purpose image-processing needs, the limited computing capacity in a standalone processing node has become inadequate to keep up with the faster growth of image-processing applications in such practical areas as real-time image processing and 3D image rendering.

The huge amount of image data is another issue which has been faced by many image-processing applications today. Many applications such as computer graphics, rendering photo realistic images and computer-animated films consume the aggregate power of whole farms of workstations (Oberhuber, 1998). Although the common sense of what is “large” to the image data being processed has changed over time, expression in Megabytes or Gigabytes is observed from the application point of view (Goller, 1999). Over the past few decades, the image to be processed has become larger and larger. Consequently, the issue of how to decrease the processing time despite the growth of image data becomes an urgent point in digital image processing.

Moreover, the nature of the traditional image-processing algorithms is another issue which reduces the processing speed. In digital image processing, the elementary image operators can be differentiated between point image operators, local imageoperators and global image operators (Braunl, Feyrer, Rapf, & Reinhardt, 2001). The main characteristic of point operator is that a pixel in the output image depends only on the corresponding pixel in the input image. Point operators are used to copy an image from one memory location to another, in arithmetic and logic operations, table lookup and image composition (Nicolescu & Jonker, 2002). Local operators create a destination pixel based on criteria that depend on the source pixel and the values of the pixels in some “neighbourhood” surrounding it. They are used widely in low-level image processing such as image enhancement by sharpening, blurring and noise removal. Global operators create a destination pixel based on the entire image information. A representative example of an operator within this class is the Discrete Fourier Transform (DFT). Compared with point operators, local operators and global operator are more computationally intensive.

As a consequence of the above, image processing-related tasks involve the execution of a large number of operations on large sets of structured data. The processing power of the typical desktop workstation can therefore become a severe bottleneck in many image-processing applications. Thus, it may make sense to perform image processing on multiple workstations or on a parallel processing system. Actually, many image-processing tasks exhibit a high degree of data locality and parallelism, and map quite readily to specialized massively parallel computing hardware (Chen, Lee, & Cho, 1990; Siegel, Armstrong, & Watson, 1992; Stevenson, Adams, Jamieson, & Delp, April, 1993).