Pipelined Execution of Windowed Image Computations
|
Title | Pipelined Execution of Windowed Image Computations |
Authors | |
Abstract | Many image processing operations manipulate an individual pixel using the values of other pixels in the neighborhood. Such operations are called windowed operations. The size of the windowed operation is a measure of the size of the given pixel´s neighborhood. A windowed computation applies a windowed operation on all pixels of the image. An image processing application is typically a sequence of windowed computations. While windowed computations admit high parallelism, the cost of inputting and outputting the image often restricts the computation to a few computational units.In this paper we analytically study the running of a sequence of z windowed computations, each of size w, on a z-stage pipelined computational model. For an N×N image and n×n input/output bandwidth per stage, we show that the sequence of windowed computations can be run in at most N2/n2(1+δ) steps, where δ=(n/N+6n3/(wN2)+zw/N+zn2N2). This produces a speed-up of z/(1+δ) over a single stage; delta, the overhead is quite small. We also show that the memory requirement per stage is O(wN+n2). With values of N, n and w that reflect the current state-of-the-art, over 20 pipeline stages can be sustained with less than 5% overhead for a 10M-pixel image. Each of these stages would require less than 128 Kbytes of storage. |
Publisher | International Journal of Networking and Computing |
Date | 2013-01-21 |
Source | 2185-2839 |