Journal of Applied Mathematics
Volume 2 (2002), Issue 4, Pages 199-218
doi:10.1155/S1110757X02110035
Network flow optimization for restoration of images
Institute of Engineering Cybernetics NAN, Surganov Street 6, Minsk 220012, Belarus
Received 5 October 2001
Copyright © 2002 Boris A. Zalesky. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
The network flow optimization approach is offered for restoration
of gray-scale and color images corrupted by noise. The Ising
models are used as a statistical background of the proposed
method. We present the new multiresolution network flow minimum
cut algorithm, which is especially efficient in identification of
the maximum a posteriori (MAP) estimates of corrupted images. The
algorithm is able to compute the MAP estimates of large-size
images and can be used in a concurrent mode. We also consider the
problem of integer minimization of two functions,
U1(x)=λ∑i|yi−xi|+∑i,j βi,j|xi−xj|
and
U2(x)=∑i λi (yi−xi)2+∑i,j βi,j (xi−xj)2, with parameters
λ,λi,βi,j>0
and vectors
x=(x1,…,xn),
y=(y1,…,yn)∈{0,…,L−1}n.
Those functions constitute the energy ones for the Ising model of
color and gray-scale images. In the case L=2, they coincide,
determining the energy function of the Ising model of binary
images, and their minimization becomes equivalent to the network
flow minimum cut problem. The efficient integer minimization of
U1(x),U2(x)
by the network flow
algorithms is described.