A fast Kalman filter for images degraded by both blur and noise

In this paper a fast Kalman filter is derived for the nearly optimal recursive restoration of images degraded in a deterministic way by blur and in a stochastic way by additive white noise. Straightforwardly implemented optimal restoration schemes for two-dimensional images degraded by both blur and noise create dimensionality problems which, in turn, lead to large storage and computational requirements. When the band-Toeplitz structure of the model matrices and of the distortion matrices in the matrix-vector formulations of the original image and of the noisy blurred observation are approximated by circulant matrices, these matrices can be diagonalized by means of the FFT. Consequently, a parallel set of N dynamical models suitable for the derivation of N low-order vector Kalman filters in the transform domain is obtained. In this way, the number of computations is reduced from the order of O(N 4 ) to that of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(N² log₂ N)</tex> for N × N images.