Image segmentation using star-convexity constraints is described. In an example, user input specifies positions of one or more star centers in a foreground to be segmented from a background of an image. In embodiments, an energy function is used to express the problem of segmenting the image and that energy function incorporates a star-convexity constraint which limits the number of possible solutions. For example, the star-convexity constraint may be that, for any point p inside the foreground, all points on a shortest path (which may be geodesic or Euclidean) between the nearest star center and p also lie inside the foreground. In some examples continuous star centers such as lines are used. In embodiments a user may iteratively edit the star centers by adding brush strokes to the image in order to progressively change the star-convexity constraints and obtain an accurate segmentation.