Image segmentation using star-convexity constraints

• US 8,498,481 B2
• Filed: 05/07/2010
• Issued: 07/30/2013
• Est. Priority Date: 05/07/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Blake, Andrew, Gulshan, Varun, Rother, Carsten, Criminisi, Antonio
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US12/776,082
• Publication Number:
  US 20110274352A1
• Time in Patent Office: 1,180 Days
• Field of Search: 382/173
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 2207/20168 Radial search
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation

Abstract

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.

Claims

1. A computer-implemented method of segmenting an image into a foreground and a background comprising:

receiving an image to be segmented;

obtaining at least one star center being a location in the image;

using the star center to calculate a geodesic distance map corresponding to the image, the geodesic distance map comprising a geodesic shortest path distance from each image element of the image to the star center;

specifying an energy function representing a problem of segmenting the image;

using the geodesic distance map, optimizing the energy function to obtain the foreground and background, the energy function incorporating a geodesic star-convexity constraint.

2. A method as claimed in claim 1 wherein the geodesic star-convexity constraint is that, for any point p inside the foreground, all points on a geodesic shortest path between the star center and p also lie inside the foreground.

3. A method as claimed in claim 1 comprising obtaining a plurality of star centers and wherein the geodesic star-convexity constraint is that, for any point p inside the foreground, all points on a geodesic shortest path between the nearest star center and p also lie inside the foreground.

4. A method as claimed in claim 3 wherein the star centers are discrete.

5. A method as claimed in claim 3 wherein the star centers form a line segment.

6. A method as claimed in claim 1 wherein the energy function is optimized using a graph cut process.

7. A method as claimed in claim 1 wherein the at least one star center is obtained from user input specifying at least one element of the image which is in the foreground.

8. A method as claimed in claim 7 which further comprises displaying the image and the foreground and receiving user input specifying a second star center.

9. A method as claimed in claim 8 which comprises incrementally computing the geodesic distance map using the second star center and using the incrementally computed geodesic distance map to re-optimize the energy function.

10. A method as claimed in claim 8 which further comprises re-computing the geodesic distance map such that no geodesic paths enter the foreground and re-optimizing the energy function using the re-computed geodesic distance map.

11. A method as claimed in claim 1 wherein the at least one star center is pre-specified.

12. A computer-implemented method of segmenting an image into a foreground and a background comprising:

storing an image to be segmented in memory;

obtaining a plurality of star centers each being a location in the image;

arranging a processor to specify an energy function representing a problem of segmenting the image, the energy function incorporating a star-convexity constraint based on the plurality of star centers;

using the processor to optimize the energy function to obtain the foreground and background.

13. A method as claimed in claim 12 wherein the star-convexity constraint is that, for any point p inside the foreground, all points on a shortest path between the nearest star center and p also lie inside the foreground.

14. A method as claimed in claim 12 wherein the star centers are discrete.

15. A method as claimed in claim 12 wherein the star centers form a line segment.

16. An image segmentation apparatus comprising:

a memory arranged to store an image to be segmented at least into a foreground and a background;

an input arranged to obtain a plurality of star centers each being a location in the image;

a processor arranged to use the star centers to calculate a geodesic distance map corresponding to the image, the geodesic distance map comprising a geodesic shortest path distance from each image element of the image to a nearest one of the star centers;

the processor being arranged to specify an energy function representing a problem of segmenting the image;

the processor being arranged to use the geodesic distance map to optimize a cost function and obtain the foreground and the background, the cost function incorporating a geodesic star-convexity constraint which is that, for any point p inside the foreground, all points on a geodesic shortest path between the nearest star center and p also lie inside the foreground.

17. An apparatus as claimed in claim 16 wherein the input comprises a graphical user interface arranged to receive user input specifying at least a plurality of image elements which are in the foreground.

18. An apparatus as claimed in claim 17 which further comprises an output arranged to display the foreground and background and wherein the graphical user interface is arranged to receive input adding a further star center.

19. An apparatus as claimed in claim 18 wherein the processor is arranged to change the star-convexity constraint only locally around the further star center.

20. An apparatus as claimed in claim 19 wherein the processor is arranged to incrementally compute the geodesic distance map using the further star center and to use the incrementally computed geodesic distance map to re-optimize the cost function.