Local watershed operators for image segmentation

• US 7,327,880 B2
• Filed: 09/27/2004
• Issued: 02/05/2008
• Est. Priority Date: 03/12/2004
• Status: Active Grant

• Current Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Original Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Inventors: Tek, Huseyin
• Primary Examiner(s): Ahmed; Samir
• Assistant Examiner(s): BLOOM, NATHAN J
• Application Number:
  US10/951,194
• Publication Number:
  US 20050201618A1
• Time in Patent Office: 1,226 Days
• Field of Search: 382173-180
• US Class Current: 382/173
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds

Abstract

We propose local watershed operators for the segmentation of structures, such as medical structures, from an image. A watershed transform is a technique for partitioning an image into many regions while substantially retaining edge information. The proposed watershed operators are a computationally efficient local implementation of watersheds, which can be used as an operator in other segmentation techniques, such as seeded region growing, region competition and markers-based watershed segmentation.

Claims

1. A method of segmenting an image, comprising:

determining a gradient of the image to form a gradient image;

forming a first layer by obtaining a user-selected region of interest in the gradient image;

forming a plurality of second layers immediately neighboring the first layer;

forming a plurality of third layers immediately neighboring the plurality of second layers;

merging the first layer with one of the plurality of second layers using a merging criteria to form a merged first layer;

performing a filling process starting from neighbors of the plurality of third layers; and

partitioning a plateau located between at least two of the first layer, the second layer and the third layer, comprising;

given a pixel P_i visiting its neighboring pixel P_j, computing a distance value at P_j

2. The method of claim 1, wherein determining a gradient of an image comprises applying a Sobel operator to the image to form the gradient image.

3. The method of claim 1, wherein forming a first layer comprises:

adding a pixel to the first layer if the height value of the pixel to be added is higher than the height value of the first layer found in the gradient image; and

initializing at least one of the plurality of second layers immediately neighboring the first layer, if the height value of the pixel to be added is lower than the height value of the first layer found in the gradient image.

4. The method of claim 1, wherein forming a plurality of second layers comprises:

adding a pixel to one of the plurality of second layers, if the height value of the pixel to be added is higher than the height value of the one of the plurality of second layers found in the gradient image; and

initializing one of the plurality of third layers immediately neighboring the one of the plurality of second layers if the height value of the pixel to be added is lower than the height value of the one of the plurality second layers found in the gradient image.

5. The method of claim 1, wherein forming a plurality of third layers comprises creating a dam on one of the plurality of third layers, if the height value of the one of the plurality of third layers is lower than the height value of one of the plurality of second layer, immediately neighboring the one of the plurality of third layers.

6. The method of claim 1, wherein merging the first layer with the plurality of second layers using a merging criteria comprises merging the first layer with one of the plurality of second layers using region composition.

7. The method of claim 6, wherein merging the first layer with one of the plurality of second layers using region composition comprises:

computing a mean intensity value between the plurality of second layers;

determining neighbors of each of the plurality of second layers;

choosing one of the neighbors with the lowest mean intensity value; and

adding the one of the neighbors to the first layer.

8. The method of claim 1, wherein merging the first layer with the plurality of second layers using a merging criteria comprises merging the first layer with one of the plurality of second layers using seeded region growing.

9. The method of claim 8, wherein merging the first layer with one of the plurality of second layers using seeded region growing, comprises:

computing statistics of similarity between the plurality of second layers;

determining neighbors of each of the plurality of second layers;

choosing one of the neighbors with the highest similarity based on the statistics; and

adding the one of the neighbors to the first layer.

10. The method of claim 9, wherein computing statistics of similarity between the plurality of second layers comprises computing a mean and standard deviation for each of the plurality of second layers.

11. The method of claim 9, wherein choosing one of the neighbors with the highest similarity based on the statistics comprises choosing one of the neighbors with the highest similarity based on an absolute difference between the means.

12. The method of claim 9, wherein choosing one of the neighbors with the highest similarity based on the statistics comprises choosing one of the neighbors with the highest similarity based on a Fisher exact test.

13. The method of claim 1, wherein merging the first layer with the plurality of second layers using a merging criteria comprises merging the first layer with one of the plurality of second layers using marker-based watershed segmentation.

14. The method of claim 13, wherein merging the first layer with one of the plurality of second layers using marker-based watershed segmentation, comprises:

determining neighbors of each of the plurality of second layers;

determining a lowest height value, V, between each of the plurality of second layers and the corresponding neighbors of the each of the plurality of second layers; and

adding one of the plurality of second layers with the lowest V to the first layer.

15. A machine-readable medium having instructions stored thereon for execution by a processor to perform method of segmenting an image, the method comprising:

determining a gradient of the image to form a gradient image;

forming a first layer by obtaining a user-selected region of interest in the gradient image;

forming a plurality of second layers immediately neighboring the first layer;

forming a plurality of third layers immediately neighboring the plurality of second layers;

merging the first layer with one of the plurality of second layers using a merging criteria to form a merged first layer,

performing a filling process starting from neighbors of the plurality of third layers; and

partitioning a plateau located between at least two of the first layer, the second layer and the third layer, comprising;

given a pixel P_i visiting its neighboring pixel P_j, computing a distance value at P_j

16. A system of segmenting an image, comprising:

means for determining a gradient of the image to form a gradient image;

means for forming a first layer by obtaining a user-selected region of interest in the gradient image;

means for forming a plurality of second layers immediately neighboring the first layer;

means for forming a plurality of third layers immediately neighboring the plurality of second layers;

means for merging the first layer with one of the plurality of second layers using a merging criteria to form a merged first layer;

means for performing a filling process starting from neighbors of the plurality of third layers; and

partitioning a plateau located between at least two of the first layer, the second layer and the third layer; and

wherein partitioning a plateau comprises;

given a pixel Pi visiting its neighboring pixel Pj computing a distance value at Pj