| Polynomial time algorithms for ratio regions and a variant of normalized cut. | |
| | |
MedLine Citation:
|
PMID: 20299712 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
In partitioning, clustering, and grouping problems, a typical goal is to group together similar objects, or pixels in the case of image processing. At the same time, another goal is to have each group distinctly dissimilar from the rest and possibly to have the group size fairly large. These goals are often combined as a ratio optimization problem. One example of such a problem is a variant of the normalized cut problem, another is the ratio regions problem. We devise here the first polynomial time algorithms solving optimally the ratio region problem and the variant of normalized cut, as well as a few other ratio problems. The algorithms are efficient and combinatorial, in contrast with nonlinear continuous approaches used in the image segmentation literature, which often employ spectral techniques. Such techniques deliver solutions in real numbers which are not feasible to the discrete partitioning problem. Furthermore, these continuous approaches are computationally expensive compared to the algorithms proposed here. The algorithms presented here use as a subroutine a minimum s,t-cut procedure on a related graph which is of polynomial size. The output consists of the optimal solution to the respective ratio problem, as well as a sequence of nested solutions with respect to any relative weighting of the objectives of the numerator and denominator. |
| | |
Authors:
|
Dorit S Hochbaum |
Publication Detail:
|
Type: Journal Article |
Journal Detail:
|
Title: IEEE transactions on pattern analysis and machine intelligence Volume: 32 ISSN: 1939-3539 ISO Abbreviation: IEEE Trans Pattern Anal Mach Intell Publication Date: 2010 May |
Date Detail:
|
Created Date: 2010-03-19 Completed Date: 2010-06-23 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9885960 Medline TA: IEEE Trans Pattern Anal Mach Intell Country: United States |
Other Details:
|
Languages: eng Pagination: 889-98 Citation Subset: IM |
Affiliation:
|
Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA 94720, USA. hochbaum@ieor.berkeley.edu |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Artificial Intelligence* Image Interpretation, Computer-Assisted / methods* Pattern Recognition, Automated / methods* Subtraction Technique* |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Nonnegative least-correlated component analysis for separation of dependent sources by volume maximi...
Next Document: Spatial-Temporal Fusion for High Accuracy Depth Maps Using Dynamic MRFs.