Reconstruction of Gray-Scale Images
Tóm tắt
We present an algorithm to reconstruct gray scale images corrupted by noise. We use a Bayesian approach. The unknown original image is assumed to be a realization of a Markov random field on a finite two dimensional region Λ ⊂ Z2. This image is degraded by some noise, which is assumed to act independently in each site of Λ and to have the same distribution on all sites. For the estimator we use the mode of the posterior distribution: the so called maximum a posteriori (MAP) estimator. The algorithm, that can be used for both gray-scale and multicolor images, uses the binary decomposition of the intensity of each color and recovers each level of this decomposition using the identification of the problem of finding the two color MAP estimator with the min-cut max-flow problem in a binary graph, discovered by Greig et al. (1989). Experimental results and a detailed example are given in the text. We also provide a web page where additional information and examples can be found.
Tài liệu tham khảo
E. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines, Wiley: New York, 1989.
F. Barahona, “On the computational complexity of Ising spin-glass models,” J. of Physics A, vol. 15 p. 3241, 1982.
P. A. Ferrari, A. Frigessi, and P. Gonzaga de Sá, “Fast approximate maximum a posteriori restoration of multicolor images,” J. R. Statisti. Soc. B p. 485, 1995.
T. A. Ferryman and S. J. Press, “A comparison of nine pixel classification algorithms,” Technical report, University of California, 1997.
L. R. Ford and D. R. Fulkerson, “Flows in networks,” Princeton: Princeton University Press, 1962.
A. Frigessi and M. Piccioni, “Parameter estimation for two-dimensional Ising fields corrupted by noise,” Stoch. Proc. Appl. vol. 34 pp. 297-311, 1990.
M. R. Garey and D. S. Johnson, “Computers and intractability: a guide to the theory of NP-completeness,” Freeman: San Francisco, 1979.
D. Geman, Random Fields and Inverse Problems in Imaging, Lecture Notes in Mathematics 1470, Springer Verlag: New York, 1990.
B. Gidas “Metropolis type Monte Carlo simulation algorithm and simulated annealing,” Topics in Contemporary Probability and its Applications, Probab. Stochastics Ser., CRC: Boca Raton, FL, pp. 159-232, 1995.
D. M. Greig, B. T. Porteous, and A. M. Seheult, “Exact maximum a posteriori estimation for binary images,” J. Royal Statistical Society, Series B vol. 51 pp. 271-279, 1989.
M. D. Jubb, Unpublished, Ph.D Thesis, University of Bath, UK, 1989.
P. Martin, “Potts models and related problems in statistical mechanics,” Series on Advances in Statistical Mechanics, 5. World Scientific Publishing Co., Inc.: Teaneck, NJ, 1991.
B. M. McCoy and T. T. Wu, “The two-dimensional Ising model,” Harvard University Press, 1973.
D. Ruelle, Statistical Mechanics: Rigorous Results. W. A. Benjamin, Inc.: New York/Amsterdam, 1969.
A. Trouvé “Cycle decompositions and simulated annealing,” SIAM J. Control Optim. vol. 34(3) pp. 966-986, 1996.