In this thesis we discuss the use of updating techniques in multidimensional
filtering. We restrict oursevles to image restoration. The emphasis is on
parallel versions of certain updating algorithms for matrix decompositions -
problems which usually arise in signal/image processing. The parallel
algorithms are described using a systolic model.
We begin with the brief description of the parallel computing model called
systolic arrays introduced in 1978 by H.T. Kung and C. Leiserson (H.T. Kung
and C. Leiserson, 1978). We review the brief history of the development of
parallel architectures for signal/image processing. We also describe some basic
systolic designs for solving linear systems of equations using Gaussian
eliminations and Givens rotations. In the end, we describe a systolic array for
computing the Faddeev algorithm which can be used for computing all the
algorithms mentioned above.
We proceed with some preliminary concepts on image restoration, concentrating on
linear algebraic restoration. We describe techniques such as inverse filter,
constrained least-squares filter, parametric Wiener filter and pseudo-inverse
filter. We propose an alternative method for computing the pseudo-inverse
filter using the rank-revealing URV decomposition, which is computationally less
expensive than the singular value decomposition normally used. We justify the
use of this method with some theoretical and numerical results.
The main part of the thesis is the chapter on the updating techniques. We present the updating algorithms and their systolic versions for some matrix problems arising in image restoration. First, we propose a systolic array for computing the inverse of rank-one modified matrix using the Sherman-Morrison formula. This algorithm is then extended to solving the updated systems of linear equations on a linear systolic array. We also show the generalisation to the updates of higher ranks. Then, we describe the rank-one updating algorithm for the QR decomposition. Solutions found here are then used in updating two-sided decompositions such as the SVD and the rank-revealing URV decomposition. The most important part of the updating method for the SVD is the bidiagonalisation of the diagonal matrix with an appended row which should be performed in O(n^2) flops. We propose two such schemes of plane rotations together with their systolic versions. Finally, we present an updating algorithm for the URV decomposition when a row is appended to a matrix which can be realised on a linear array of processors.