TY - GEN

T1 - Beyond connecting the dots

T2 - 12th International Conference on Computer Vision, ICCV 2009

AU - Windheuser, Thomas

AU - Schoenemann, Thomas

AU - Cremers, Daniel

PY - 2009

Y1 - 2009

N2 - We propose a polynomial-time algorithm for segmentation and (open) boundary estimation which takes into account a series of user-specified attraction points. In contrast to existing algorithms which impose that the segmenting boundary passes through these points, our algorithm allows an imprecision in the user input. An energy minimization approach imposes that the segmenting boundary optimally passes along high-contrast edges in such a way that at least one point along the computed boundary is as close as possible to any given attraction point. In this sense, the user input can be seen as a soft constraint. We prove that the resulting optimization problem is NP-hard. We prove that in the case that the user attraction points are ordered, then optimal solutions can be computed in polynomial time using a shortest path formulation in an appropriately constructed four-dimensional graph spanned by the image pixels, a set of tangent angles and the user attraction points. Experimental results on a variety of images demonstrate that good quality segmentations can be obtained with a few imprecise user clicks.

AB - We propose a polynomial-time algorithm for segmentation and (open) boundary estimation which takes into account a series of user-specified attraction points. In contrast to existing algorithms which impose that the segmenting boundary passes through these points, our algorithm allows an imprecision in the user input. An energy minimization approach imposes that the segmenting boundary optimally passes along high-contrast edges in such a way that at least one point along the computed boundary is as close as possible to any given attraction point. In this sense, the user input can be seen as a soft constraint. We prove that the resulting optimization problem is NP-hard. We prove that in the case that the user attraction points are ordered, then optimal solutions can be computed in polynomial time using a shortest path formulation in an appropriately constructed four-dimensional graph spanned by the image pixels, a set of tangent angles and the user attraction points. Experimental results on a variety of images demonstrate that good quality segmentations can be obtained with a few imprecise user clicks.

UR - http://www.scopus.com/inward/record.url?scp=77953179288&partnerID=8YFLogxK

U2 - 10.1109/ICCV.2009.5459281

DO - 10.1109/ICCV.2009.5459281

M3 - Conference contribution

AN - SCOPUS:77953179288

SN - 9781424444205

T3 - Proceedings of the IEEE International Conference on Computer Vision

SP - 717

EP - 722

BT - 2009 IEEE 12th International Conference on Computer Vision, ICCV 2009

Y2 - 29 September 2009 through 2 October 2009

ER -