Book chapter
Maximum Weight Digital Regions Decomposable into Digital Star-Shaped Regions
Algorithms and Computation, pp.724-733
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2011
DOI: 10.1007/978-3-642-25591-5_74
Abstract
We consider an optimization version of the image segmentation problem, in which we are given a grid graph with weights on the grid cells. We are interested in finding the maximum weight subgraph such that the subgraph can be decomposed into two ”star-shaped” images. We show that this problem can be reduced to the problem of finding a maximum-weight closed set in an appropriately defined directed graph which is well known to have efficient algorithms which run very fast in practice. We also show that finding a maximum-weight subgraph that is decomposable into m star-shaped objects is NP-hard for some m > 2.
Details
- Title: Subtitle
- Maximum Weight Digital Regions Decomposable into Digital Star-Shaped Regions
- Creators
- Matt Gibson - University of IowaDongfeng Han - University of IowaMilan Sonka - University of IowaXiaodong Wu - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Algorithms and Computation, pp.724-733
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-642-25591-5_74
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Language
- English
- Date published
- 2011
- Academic Unit
- Roy J. Carver Department of Biomedical Engineering; Electrical and Computer Engineering; Radiation Oncology; The Iowa Institute for Biomedical Imaging; Fraternal Order of Eagles Diabetes Research Center; Injury Prevention Research Center; Ophthalmology and Visual Sciences
- Record Identifier
- 9984186689802771
Metrics
16 Record Views