Multilevel image segmentation

• US 20060159342A1
• Filed: 12/20/2005
• Published: 07/20/2006
• Est. Priority Date: 01/18/2005
• Status: Active Grant

• Current Assignee: Siemens Healthcare GMBH (Siemens AG)
• Original Assignee: Siemens AG
• Inventors: Lombaert, Herve, Sun, Yiyong, Xu, Chenyang, Grady, Leo
• Granted Patent: US 8,913,830 B2
• Time in Patent Office: Days
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/20036 Morphological image processing
• CPC Class Codes: G06T 2207/20101 Interactive definition of point of interest, landmark or seed
• CPC Class Codes: G06T 2207/30048 Heart; Cardiac
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/162 involving graph-based methods
• CPC Class Codes: G06T 7/174 involving the use of two or more images
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds

Abstract

A multilevel image segmentation technique using graph cuts is disclosed. A reduced resolution image is generated from a full resolution image which is to be segmented. The reduced resolution image is then segmented in order to identify a boundary between an object and a background within the image. The identified boundary then identifies a portion of an increased resolution image which is segmented in order to refine the earlier identified boundary. The steps may be iterated for successively increasing image resolutions in order to refine the boundary as required by a particular application. An initial identification of object and background portions of the image may be provided as input by a user. Alternatively, a user may identify only the object portion, and the background portion may be automatically determined.

Claims

1. A method for processing a full resolution image comprising:

a) generating a reduced resolution image from said full resolution image;

b) segmenting said reduced resolution image to identify a boundary between an object and a background; and

c) segmenting a portion of an increased resolution image to generate a refined boundary, said portion based upon said prior identified boundary.

2. The method of claim 1 wherein said increased resolution image is said full resolution image.

3. The method of claim 1 further comprising the steps of:

receiving an identification of at least a portion of said object as user input; and

automatically determining at least a portion of said background.

4. The method of claim 3 wherein said step of automatically determining at least a portion of said background further comprises:

performing a region growing operation using said at least a portion of said object as a seed;

performing a dilation operation on a result of said region growing operation; and

identifying at least one point resulting from said dilation operation as background.

5. The method of claim 1 further comprising:

iteratively repeating step c using images having successively increasing resolutions.

6. The method of claim 1 wherein said step b comprises:

generating a graph of said reduced resolution image; and

performing a graph cut on said graph.

7. The method of claim 1 wherein said step c comprises:

generating a graph of said portion of an increased resolution image; and

performing a graph cut on said graph.

8. The method of claim 1 further comprising the step of identifying said portion by projecting said prior identified boundary onto said increased resolution image.

9. The method of claim 8 wherein said step of identifying said portion further comprises:

performing a dilation operation on said projected prior identified boundary.

10. The method of claim 9 further comprising the steps of:

identifying an outer portion of said dilated projected prior identified boundary as background; and

identifying an inner portion of said dilated projected prior identified boundary as object.

11. An apparatus for processing a full resolution image comprising:

a) means for generating a reduced resolution image from said full resolution image;

b) means for segmenting said reduced resolution image to identify a boundary between an object and a background; and

c) means for segmenting a portion of an increased resolution image to generate a refined boundary, said portion based upon said prior identified boundary.

12. The apparatus of claim 11 wherein said increased resolution image is said full resolution image.

13. The apparatus of claim 11 further comprising:

means for receiving an identification of at least a portion of said object as user input; and

means for automatically determining at least a portion of said background.

14. The apparatus of claim 13 wherein said means for automatically determining at least a portion of said background further comprises:

means for performing a region growing operation using said at least a portion of said object as a seed;

means for performing a dilation operation on a result of said region growing operation; and

means for identifying at least one point resulting from said dilation operation as background.

15. The apparatus of claim 11 further comprising:

means for iteratively repeating step c using images having successively increasing resolutions.

16. The apparatus of claim 11 wherein said means b comprises:

means for generating a graph of said reduced resolution image; and

means for performing a graph cut on said graph.

17. The apparatus of claim 11 wherein said means c comprises:

means for generating a graph of said portion of an increased resolution image; and

means for performing a graph cut on said graph.

18. The apparatus of claim 11 further comprising means for identifying said portion by projecting said prior identified boundary onto said increased resolution image.

19. The apparatus of claim 18 wherein said means for identifying said portion further comprises:

means for performing a dilation operation on said projected prior identified boundary.

20. The apparatus of claim 19 further comprising:

means for identifying an outer portion of said dilated projected prior identified boundary as background; and

means for identifying an inner portion of said dilated projected prior identified boundary as object.

21. A method for segmenting an image (I⁰) based on object seeds O and background seeds G comprising the steps of:

a) generating a plurality (K) of reduced resolution images (I¹, . . . , I^K);

b) generating a graph G^K for the lowest resolution image I^K;

c) calculating a minimum cut C^K of said graph G^K based on O and G;

d) generating a binary boundary image J^k to represent the image points identified by nodes in said minimum cut C^K;

e) projecting said image points onto a higher resolution boundary image J<sup>k−

1</sup>;

f) generating a graph G<sup>K−

1</sup> for said higher resolution boundary image J<sup>k−

1</sup>; and

g) calculating a minimum cut C<sup>K−

1</sup> for said graph G<sup>K−

1</sup>.

22. The method of claim 21 further comprising the step of:

recursively repeating steps d-g until a minimum cut C⁰ is calculated on a graph G⁰ to generate a segmentation of image I⁰.

23. The method of claim 21 further comprising the step of:

applying a dilation operation (where distance d≧

0) on said higher resolution boundary image J<sup>k−

1</sup>.

24. The method of claim 23 wherein d=1.

25. The method of claim 21 wherein said step of projecting said image points onto a higher resolution boundary image J^k−

1 is performed according to;

J<sup>K−

1</sup>(p)=J^K(a(p)).

26. The method of claim 21 wherein said step of generating a graph G^K−

1 for said higher resolution boundary image J<sup>k−

1</sup> uses the outer layer of said boundary image as object seeds (O) and the inner layer of said boundary image as background seeds (G).