Image segmentation using spatial random walks

• US 8,218,869 B2
• Filed: 03/29/2009
• Issued: 07/10/2012
• Est. Priority Date: 03/29/2009
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Porikli, Fatih M., Li, Rui
• Primary Examiner(s): Liu, Li
• Application Number:
  US12/413,593
• Publication Number:
  US 20100246956A1
• Time in Patent Office: 1,199 Days
• Field of Search: None
• US Class Current: 382/173
• CPC Class Codes: G06T 2207/20076 Probabilistic image processing
• CPC Class Codes: G06T 2207/30096 Tumor; Lesion
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling

Abstract

The embodiments of the invention describe a method for segmenting an image. We perform an initial segmentation of the image to produce a previous segmented region and segment iteratively the image using a spatial random walk based on a shape prior of the previous segmented region to produce a next segmented region. We compare the next segmented region with the previous segmented region, and repeat the segmenting and the comparing until the previous and next segmented regions converge. After that, we select the next segmented region as a final segmented region.

Claims

1. A method for segmenting an image, comprising the steps of:

performing an initial segmentation of the image to produce a previous segmented region;

segmenting iteratively the image using a spatial random walk based on a shape prior of the previous segmented region to produce a next segmented region, wherein the spatial random walk is minimizing an energy function E with the shape prior according to E=E_rw+vE_sp, wherein E_rw is an energy of a random walk segmentation, E_sp is an energy of the prior shape, and v is a weight parameter controlling an impact of the shape prior into the spatial random walk;

comparing the next segmented region with the previous segmented region;

repeating the segmenting and the comparing until the previous and next segmented regions converge; and

selecting the next segmented region as a final segmented region.

2. The method of claim 1, further comprising:

aligning the shape prior with the previous segmented region.

3. The method of claim 2, further comprising:

smoothing the shape prior.

4. The method of claim 1, further comprising:

aligning the shape prior with the previous segmented region; and

smoothing adaptively the shape prior.

5. The method of claim 4, wherein an iteration of the segmenting is associated with an iteration index, and wherein the smoothing adaptively further comprising:

applying a smoothing function to the shape prior, wherein a parameter of the smoothing function is adjusted based on the iteration index.

6. The method of claim 1, further comprising:

selecting the shape prior from a set of shape priors.

7. The method of claim 6, wherein the selecting the shape prior further comprising:

comparing each shape prior in the set of shape priors with the current segmented region to determine a set of similarity scores;

selecting the shape prior with a highest similarity score from the set of similarity scores.

8. The method of claim 1, further comprising:

determining a Laplacian matrix of the image.

9. The method of claim 8, wherein the spatial random walk segmentation is according to

(L+v)r=vH(φ

₀),

wherein L is the Laplacian matrix, v is a weight of the shape prior, r is the next segmented region, H(•

) is a smoothing function, and φ

₀ is the shape prior.

10. The method of claim 9, further comprising:

choosing the weight adaptively according to an iteration.

11. The method of claim 1, wherein the spatial random walk segmentation using an image color intensity prior information.

12. The method of claim 1, wherein the shape prior is a predetermined shape of the segmented region.

13. The method of claim 1, wherein the shape prior represents a shape of a tumor.

14. The method of claim 1, wherein the energy of the prior shape is a shape distance function.

15. The method of claim 1, wherein the spatial random walk is minimizing an energy function E with the shape prior using a color intensity prior probability according to

E=E_rw+vE_spγ

E_color,

wherein E_rw is an energy of a random walk segmentation, E_sp is an energy of the prior shape, v is a weight parameter that controls the impact of the shape prior into the spatial random walk, and γ

is a weight parameter controlling an impact of the color intensity prior into the spatial random walk.

16. A method for segmenting an image, comprising the steps of:

segmenting iteratively an image with a spatial random walk segmentation based on a shape prior to produce a next segmented region until the next segmented region converges with a previous segmented region;

selecting the next segmented region as a final segmented region;

aligning the shape prior with the previous segmented region; and

smoothing adaptively the shape prior with a smoothing function, wherein the smoothing function is adjusted based on an iteration of the segmenting; and

rendering the image including the final segmented region.

17. The method of claim 16, wherein the spatial random walk segmentation is according to

(L+v)r=vH(φ

₀),

wherein L is a Laplacian matrix, v is a weight of the shape prior, r is the next segmented region, H(•

) is the smoothing function, and φ

₀ is the shape prior.