Multidimensional Dataflow Graphs - Signal Processing Systems - page 1132

4 Windowed Synchronous Dataflow (WSDF)

Processing multidimensional arrays is widely applied in digital signal processing. It
occurs for instance extensively in image processing such as filtering, compression
or medical analysis, as exemplified in Part I of this topic. Arrays of pixels having
two, three or more dimensions are analyzed and transformed into new result arrays.
In this context, point , local ,and global algorithms can be distinguished. For point
algorithms , each output pixel depends on a single input pixel. Given a video as a
sequence of images, thresholding is a simple example where each output pixel is
computed according to the following equation:

1 f i

( x , y , t ) ≥ 128

( , , )=

o x y t

0 f i ( x , y , t ) < 128

o ( x , y , t ) is the pixel at the coordinates ( x , y ) within the output image at time t

and i within the input image at time t .

Point algorithms can be well modeled with one-dimensional models of computation
discussed in [ 2 , 7 ] , because they basically transform a stream of pixels into another
stream of pixels.
Global algorithms on the other hand, need in the worst case the complete input
image before being able to compute a single pixel of the output. The rate control
procedure applied in the JPEG 2000 standard [ 9 ] belongs to this category, since it
needs to know all pixel values before being able to decide how many bits to spend
for each of them. At least on a coarse granularity, this kind of algorithms is also well
represented with one-dimensional models of computation when associating a token
with a complete image.
For local algorithms , however, the situation is more difficult. In this case, an
output pixel depends only on a small region of the input image. As a consequence,
they show particular properties such as high degree of parallelism, low memory
requirements or special data access patterns that can be exploited for efficient
implementations. All these nice properties are hidden in the model, if a token
represents a complete image. More fine-grained descriptions using 1D models of
computation are often cumbersome. CSDF graphs for instance tend to end up with
many phases in their vector valued token production and consumption cycle which
incurs high control overhead [ 7 ] .
The following subsections consider local algorithms in more detail and discuss
how they can be modeled using an appropriate type of multidimensional dataflow.
It extends MDSDF as presented in Sect. 2 by the ability to represent sampling with
overlapping windows, to read token values multiple times, as well as by border
processing.

( x , y , t ) is the pixel at the coordinates ( x , y )