Sunday, November 8, 2009

Excerpt: Systollic Parallel Processing, Nikolay Petkov

Signal and image processing constitute another class of computationally intensive problems for which many systolic algorithms are available. The need for parallel processing in this area is especially strong, since in addition to the amounts of data and the computational intensiveness in many applications the processing has to be done under critical time constraints.

It should be noted that the research effort in this area has been most succesful at the low and intermediate levels of signal and image processing. At higher levels of representation, the call for parallel processing is not so strong, since the amounts of data to be processed are reduced considerably. Higher level representations also make use of data structures such as feature tuples or graphs which do not exhibit the regularity of the low-level representations such as 1-D and 2-D data arrays. Finally, high-level speech processing and computer vision recognition methods and techniques which deliver results comparable with those provided by the higher nervous system have still to be conceived.

Systolic algorithms for important problems of signal and image processing:

Convolution and correlation (one and two dimensional)
Finite impulse respone (FIR) filters
Infinite impulse response (IIR) filters
Adaptive filtering (least squares)
Kalman Filter
Discrete Fourier transform (direct computation)
Discrete cosine transform
Fast fourier transform
Winograd Fourier transform algorithm
Walsh Hadamard transform
Inversion of finite Radon transform
Median and rank filter (one and two dimensional)
Vector quantization
Signal interpolation
Image resampling
Image reconstruction
Thickening, thinning and sceletonization of binary images
Computation of histograms and coocurence matrices
Edge detection
Feature extraction
Image segmentation
Template matching
Dynamic time warping
Geometric warping
Scene matching
Minimum-distance classification
Syntactic pattern recognition
Cluster analysis
Dynamic scene analysis
Motion analysis

Systollic Parallel Processing
Nikolay Petkov
North-Holland 1993
Pag. 103 y 104