Large-Scale Integer Programs in Image Analysis

Geir Dahl (), Geir Storvik () and Alice Fadnes ()
Additional contact information
Geir Dahl: University of Oslo, Department of Mathematics and Department of Informatics, P.O. Box 1080, Blindern, 0316 Oslo, Norway
Geir Storvik: University of Oslo, Department of Mathematics, P.O. Box 1053, Blindern, 0316 Oslo, Norway
Alice Fadnes: University of Oslo, Department of Informatics, P.O. Box 1080, Blindern, 0316 Oslo, Norway

Operations Research, 2002, vol. 50, issue 3, 490-500

Abstract: An important problem in image analysis is to segment an image into regions with different class labels. This is relevant in applications in medicine and cartography. In a proper statistical framework this problem may be viewed as a discrete optimization problem. We present two integer linear programming formulations of the problem and study some properties of these models and associated polytopes. Different algorithms for solving these problems are suggested and compared on some realistic data. In particular, a Lagrangian algorithm is shown to have a very promising performance. The algorithm is based on the technique of cost splitting and uses the fact that certain relaxed problems may be solved as shortest path problems.

Keywords: Integer programming: applications; image analysis; Networks/graphs: applications; Statistics: Bayesian (search for similar items in EconPapers)
Date: 2002
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.50.3.490.7741 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:50:y:2002:i:3:p:490-500

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().