Network flow optimization for restoration of images

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, U 1 ( x ) = λ ∑ i | y i − x i | + ∑ i , j β i , j | x i − x j | and U 2 ( x ) = ∑ i λ i ( y i − x i ) 2 + ∑ i , j β i , j ( x i − x j ) 2 , with parameters λ , λ i , β i , j > 0 and vectors x = ( x 1 , … , x n ) , y = ( y 1 , … , y n ) ∈ { 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 U 1 ( x ) , U 2 ( x ) by the network flow algorithms is described.