An Efficient Algorithm for Constrained Image Restoration with the Viterbi Algorithm

Herbert Schorb; Hans Burkhardt

doi:10.1117/12.936636

9 January 1984 An Efficient Algorithm for Constrained Image Restoration with the Viterbi Algorithm

Herbert Schorb, Hans Burkhardt

Proceedings Volume 0432, Applications of Digital Image Processing VI; (1984) https://doi.org/10.1117/12.936636
Event: 27th Annual Technical Symposium, 1983, San Diego, United States

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•B^c•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.

Citation Download Citation

Herbert Schorb and 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); https://doi.org/10.1117/12.936636

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available