Article ID: | iaor20032058 |
Country: | United States |
Volume: | 50 |
Issue: | 3 |
Start Page Number: | 490 |
End Page Number: | 500 |
Publication Date: | May 2002 |
Journal: | Operations Research |
Authors: | Dahl Geir, Storvik Geir, Fadnes Alice |
Keywords: | image processing |
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.