Network flow optimization for restoration of images

DOI10.1155/S1110757X02110035MaRDI QIDQ700929zbMATH OpenFDO

Authors Boris A. Zalesky

Publication date 15 October 2002

Published in Journal of Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0106180, https://eudml.org/doc/53256

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Integer programming (90C10) Programming involving graphs or networks (90C35) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Abstract: The network flow optimization approach is offered for restoration of grayscale and color images corrupted by noise. The Ising models are used as a statistical background of the proposed method. The new multiresolution network flow minimum cut algorithm, which is especially efficient in identification of the maximum a posteriori estimates of corrupted images, is presented. The algorithm is able to compute the MAP estimates of large size images and can be used in a concurrent mode. We also describe the efficient solutions of the problem of integer minimization of two energy functions for the Ising models of gray-scale and color images.

Review text

Summary: 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}({\mathbf x})=\lambda \sum_{i} | y_{i}-x_{i}| + \sum_{i,j} \beta_{i,j} | x_{i}-x_{j}|\) and \(U_{2}(x)= \sum_{i} \lambda_{i} (y_{i}-x_{i})^{2} + \sum_{i,j} \beta_{i,j}(x_{i}-x_{j})^{2}\), with parameters \(\lambda,\lambda_{i},\beta_{i,j}>0\) and vectors \({\mathbf x} = (x_{1},\dots,x_{n})\), \({\mathbf y} = (y_{1},\dots,y_{n})\in \{0,\dots,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}({\mathbf x}),U_{2}({\mathbf x})\) by the network flow algorithms is described.

Recommendations

• Reconstruction of gray-scale images
• Image restoration with discrete constrained total variation. I: Fast and exact optimization
• Parametric maximum flow algorithms for fast total variation minimization
• Image restoration with discrete constrained total variation. II: Levelable functions, convex priors and non-convex cases
• scientific article; zbMATH DE number 1849127

Cited in

(10)

• New algorithms for convex cost tension problem with application to computer vision
• Graph MBO on star graphs and regular trees. With corrections to DOI 10.1007/s00032-014-0216-8
• Mean curvature, threshold dynamics, and phase field theory on finite graphs
• Image restoration with discrete constrained total variation. I: Fast and exact optimization
• A new variational model for removal of combined additive and multiplicative noise and a fast algorithm for its numerical approximation
• Total variation on a tree
• scientific article; zbMATH DE number 1834036 (Why is no real title available?)
• New time dependent pretreat models based on total variational image restoration
• A Network Flow Algorithm for Reconstructing Binary Images from Continuous X-rays
• Global optimization for first order Markov random fields with submodular priors

This page was built for publication: Network flow optimization for restoration of images

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q700929)