Interactive image segmentation by precomputation

• US 8,000,527 B2
• Filed: 12/04/2007
• Issued: 08/16/2011
• Est. Priority Date: 04/17/2007
• Status: Expired due to Fees

• Current Assignee: Siemens Healthcare GMBH (Siemens AG)
• Original Assignee: Siemens AG
• Inventors: Sinop, Ali Kemal, Grady, Leo
• Primary Examiner(s): Ahmed; Samir A
• Assistant Examiner(s): Bayat; Ali
• Application Number:
  US11/949,832
• Publication Number:
  US 20080260247A1
• Time in Patent Office: 1,351 Days
• Field of Search: 382/173, 382/164, 382/171, 382/175, 382/190, 382/199, 382/181
• US Class Current: 382/173
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/7635 based on graphs, e.g. graph cuts or spectral clustering

Abstract

A method for interactive image segmentation includes receiving an image to be segmented, performing an offline computation of eigenvectors of a Laplacian of the image without using seed points, receiving seed points, and performing an online segmentation taking the seed points and the eigenvectors of the Laplacian as input and outputting a partition of the image.

Claims

1. A non-transitory computer readable medium embodying instructions executable by a processor to perform a method for interactive image segmentation, the method comprising:

receiving an image;

determining a plurality of generalized eigenvectors of the image without using seed points;

receiving a seed point for each of at least two portions of the image; and

determining a partition of the image, the determination of the partition comprising;

establishing a potential function assigning a label to each of a plurality of nodes of the image according to distances between the nodes and the seed points in a space defined by the generalized eigenvectors, wherein each of the labels correspond to one of the portions of the image; and

thresholding the potential function to produce the partition of the image.

2. The method of claim 1, wherein the partition of the image corresponds to an object captured by the image.

3. A non-transitory computer readable medium embodying instructions executable by a processor to perform a method for interactive image segmentation, the method comprising:

receiving an image to be segmented;

performing an offline computation of eigenvectors of a Laplacian of the image without using seed points;

receiving seed points; and

performing an online segmentation taking the seed points and the eigenvectors of the Laplacian as input and outputting a partition of the image,

wherein performing the online segmentation comprises;

determining a Normalized Cuts value based on the seed points and the eigenvectors of the Laplacian; and

partitioning the image according to the Normalized Cuts value.

4. The method of claim 3, wherein performing the offline segmentation further comprises:

determining edge weights of the image;

building a normalized Laplacian; and

determining the eigenvectors of the normalized Laplacian.

5. The method of claim 3, wherein a number of the eigenvectors computed is user selected.