9 January 1984 An Efficient Algorithm for Constrained Image Restoration with the Viterbi Algorithm
Author Affiliations +
Linear filters are non-optimal for image restoration problems with a constrained original signal alphabet (e.g. blurred black-and-white images). Reference 1 gives an optimal solution to this problem under the criteria of maximum-a-posteriori probability with the Viterbi algorithm. The image distortion was formulated as a rather general Markov model including, for example, nonlinear and space-variant dispersions as well as the possibility of considering a restricted original data set like alphanumeric characters etc. The computational complexity, however, was still very high. For a one-dimensional problem of dimension N, dynamic programming reduces the exponentially growing number of calculations of a straightforward solution to a value proportional to N. In the two-dimensional case for images of dimension MxN it was possible' to reduce the .. computational complexity from 0(Bc•M•N) to 0(M•Bc•N) which is linear in one dimension but still exponential in the second dimension. As a consequence, only rather small images could be restored. This paper shows how to reduce the computational complexity further to 0(M•Bc•n). A value which is linear in the image dimension and where the exponential part is of the order of the size of the two-dimensional pulse response. Thus it is possible to apply the restoration algorithm to images of realistic dimension. This result holds for non-pathological dispersions. The algorithm turns out to be asymptotically optimal. However, in general it is suboptimal.
© (1984) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Herbert Schorb, Herbert Schorb, Hans Burkhardt, Hans Burkhardt, } "An Efficient Algorithm for Constrained Image Restoration with the Viterbi Algorithm", Proc. SPIE 0432, Applications of Digital Image Processing VI, (9 January 1984); doi: 10.1117/12.936636; https://doi.org/10.1117/12.936636


Back to Top