Multilevel image segmentation

• US 8,913,830 B2
• Filed: 12/20/2005
• Issued: 12/16/2014
• Est. Priority Date: 01/18/2005
• Status: Active Grant

• Current Assignee: Siemens Healthcare GMBH (Siemens AG)
• Original Assignee: Siemens AG
• Inventors: Sun, Yiyong, Lombaert, Herve, Grady, Leo, Xu, Chenyang
• Primary Examiner(s): Hung, Yubin
• Application Number:
  US11/313,102
• Publication Number:
  US 20060159342A1
• Time in Patent Office: 3,283 Days
• Field of Search: 382/164, 382/173, 382/282, 358/453, 358/538
• 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 CT scan image comprising:

a) generating at a computer a reduced resolution image from said full resolution CT scan image;

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

c) generating at said computer an increased resolution boundary image, said increased resolution boundary image corresponding to only a portion of an area of said full resolution CT scan image, based on said prior identified boundary; and

d) segmenting at said computer said increased resolution boundary image to generate a refined boundary by;

generating a graph of said increased resolution boundary image, wherein said step of generating a graph for said increased resolution boundary image uses an outer layer of said increased resolution boundary image as object seeds and the inner layer of said increased resolution boundary image as background seeds, and

performing a graph cut on said graph.

2. The method of claim 1 wherein said increased resolution boundary image has the same resolution as said full CT scan 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 steps c and d 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 further comprising the step of identifying said portion by projecting said prior identified boundary onto said increased resolution image.

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

performing a dilation operation on said projected prior identified boundary.

9. The method of claim 8 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.

10. The method of claim 1 wherein said increased resolution boundary image represents a boundary region of said full resolution CT scan image.

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

a processor; and

a non-transitory computer readable medium storing computer program instructions, which when executed by the processor cause the processor to perform operations 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;

c) generating an increased resolution boundary image, said increased resolution boundary image corresponding to only a portion of an area of said full resolution image, based on said prior identified boundary; and

d) segmenting said increased resolution boundary image to generate a refined boundary by;

generating a graph of said increased resolution boundary image, wherein said generating a graph for said increased resolution boundary image uses an outer layer of said increased resolution boundary image as object seeds and the inner layer of said increased resolution boundary image as background seeds, and

performing a graph cut on said graph.

12. The apparatus of claim 11 wherein said increased resolution image has the same resolution as said full resolution image.

13. The apparatus of claim 11 wherein the operations further comprise:

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

automatically determining at least a portion of said background.

14. The apparatus of claim 13 wherein said 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.

15. The apparatus of claim 11 wherein the operations further comprise:

iteratively repeating operations c and d using images having successively increasing resolutions.

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

generating a graph of said reduced resolution image; and

performing a graph cut on said graph.

17. The apparatus of claim 11 wherein the operations further comprise:

identifying said portion by projecting said prior identified boundary onto said increased resolution image.

18. The apparatus of claim 17 wherein said identifying said portion further comprises:

performing a dilation operation on said projected prior identified boundary.

19. The apparatus of claim 18 wherein the operations further comprise:

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.

20. The apparatus of claim 11 wherein said increased resolution boundary image represents a boundary region of said full resolution image.

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

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

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

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

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

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

1</sup>;

f) generating at said computer a graph G<sup>K−

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

1</sup> ; and

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

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

1</sup>,

wherein said step of generating a graph G<sup>K−

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

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

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)).