Exact Maximum <i>A Posteriori</i> Estimation for Binary Images

Abstract

SUMMARY In this paper, for a degraded two-colour or binary scene, we show how the image with maximum a posteriori (MAP) probability, the MAP estimate, can be evaluated exactly using efficient variants of the Ford–Fulkerson algorithm for finding the maximum flow in a certain capacitated network. Availability of exact estimates allows an assessment of the performance of simulated annealing and of MAP estimation itself in this restricted setting. Unfortunately, the simple network flow algorithm does not extend in any obvious way to multicolour scenes. However, the results of experiments on two-colour images suggest that, in general, simulated annealing, according to practicable ‘temperature’ schedules, can produce poor approximations to the MAP estimate to which it converges.