Share Email Print
cover

Proceedings Paper

An Efficient Algorithm for Constrained Image Restoration with the Viterbi Algorithm
Author(s): Herbert Schorb; Hans Burkhardt
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

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.

Paper Details

Date Published: 9 January 1984
PDF: 5 pages
Proc. SPIE 0432, Applications of Digital Image Processing VI, (9 January 1984); doi: 10.1117/12.936636
Show Author Affiliations
Herbert Schorb, Universitat Karlsruhe (West Germany)
Hans Burkhardt, Universitat Karlsruhe (West Germany)


Published in SPIE Proceedings Vol. 0432:
Applications of Digital Image Processing VI
Andrew G. Tescher, Editor(s)

© SPIE. Terms of Use
Back to Top