2011 | OriginalPaper | Chapter
Maximum Weight Digital Regions Decomposable into Digital Star-Shaped Regions
Authors : Matt Gibson, Dongfeng Han, Milan Sonka, Xiaodong Wu
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.