Image processing method including steps for the segmentation of a multidimensional image, and medical imaging apparatus utilizing this method

• US 6,332,034 B1
• Filed: 03/19/1999
• Issued: 12/18/2001
• Est. Priority Date: 03/24/1998
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Philip, Matthieu, Makram-Ebeid, Shérif
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): NAKHJAVAN, SHERVIN K
• Application Number:
  US09/273,281
• Time in Patent Office: 1,005 Days
• Field of Search: 382/128, 382/130, 382/131, 382/132, 382/171, 382/173, 382/174, 382/277, 382/284, 382/285, 378/4
• US Class Current: 382/128
• CPC Class Codes: G06T 2207/10116 X-ray image
• CPC Class Codes: G06T 2207/20152 Watershed segmentation
• CPC Class Codes: G06T 2207/30101 Blood vessel; Artery; Vein; Vascular
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06V 10/26 Segmentation of patterns in the image field; Cutting or merging of image elements to establish the pattern region, e.g. clustering-based techniques; Detection of occlusion
• CPC Class Codes: G06V 2201/03 Recognition of patterns in medical or anatomical images
• CPC Class Codes: G06V 40/14 Vascular patterns

Abstract

The invention relates to a method for the processing of a multidimensional image which is formed by points representing objects of different intensity and are delimited from a background by way of their edges; this method includes steps for the segmentation (100; 30, 40) of the image into cells belonging to the background and cells belonging to the objects, for the application of criteria which impose that said cells (C_i) have substantially uniform intensities, that the cells neither intersect nor enclose any object edge, and that the object edges coincide with cells edges; this method includes a step for the presegmentation (30) of the image into a first number of cells while performing a classification of the image points in the various cells as a function of intensity gradients of these points, and an actual segmentation step (40) for reducing the first number of cells by classifying the cells in the form of pairs of adjoining cells (C_j, C_k), by evaluating a merger threshold (λ₀(j,k)) for the cells of the pairs as a function of their intensity variance (σ²) and of their intensity gradients (∥G∥), by evaluating a specific merger threshold (l₀^p) below which a predetermined number (H₀^p) of adjoining cells of pairs is merged, and by performing the concomitant merger of adjoining cells of pairs whose merger threshold is below said specific threshold.

Claims

1. A method for the processing of a multidimensional image which is formed by points representing objects which have an intensity which differs from one object to another, and are delimited from a background by way of their edges, the method comprising:

segmenting the image into cells relating to the background and cells relating to the objects, by applying criteria which impose that said cells have respective, substantially uniform intensities, that said cells neither intersect nor enclose any object edge, and that the object edges coincide with cell edges.

2. A method as claimed in claim 1 wherein the segmenting further comprises

presegmenting the image into a first number of cells while performing a classification of the points of the image in the various cells in conformity with a criterion which is a function of intensity gradients (∥ G∥

) of said points, and

actually segmenting so as to reduce the first number of cells by

classifying the cells into pairs of adjoining cells (C_j, C_k) while evaluating a merger threshold (λ

₀(j,k)) of the cells of the pairs as a function of the intensity variance (σ

²) and the intensity gradients (∥

G∥

) in the cells of each pair and while evaluating a specific merger threshold (l₀^p) below which the adjoining cells of pairs are merged in a predetermined number (H₀(p)) and by

performing the concomitant merger of adjoining cells of pairs having intensity characteristics which lead to a merger threshold which is lower than the specific threshold.

3. A method as claimed in claim 2 wherein the presegmenting further comprises transforming the multidimensional image into a topographic image by way of intensity gradient functions of the image points while identifying (C_i) the cells searched in catch basins (CB) and while identifying the edges bounding said cells at watershed lines (WS) of the topographic image.

4. A method as claimed in claim 3 wherein the points of the watershed lines (WS) are collected in the adjoining catch basins (CB) which are situated to both sides of these lines, wherein the cells obtain a uniform intensity which is calculated as the mean value (I_i^MOY) of the intensity of the points within the catch basins and form a class of objects, and wherein interfaces (BD) are defined between pairs of edge points (VBD) of the pairs of adjoining cells and coincide with object edges.

5. A method as claimed in claim 2 wherein the actually segmenting further comprises:

defining a cost function (F) which comprises a first term which is a function of the intensity variance (σ

²) within the cells present in the image, and a second term which is weighted by a variable weighting factor (λ

) and is a function of intensity gradients at the edge points of cells, and

evaluating the merger threshold (λ

₀(j,k)) in order to perform the merging of two adjoining cells (C_j, C_k) of a pair as the value of the variable weighting factor (λ

) which cancels the difference (E₀) between the cost function (F₀) calculated before the merging of two cells and the cost function (F₁) calculated after this merger.

6. A method as claimed in claim 5 wherein the cost function is given by the formula:

$F=\underset{C_i}{\sum <br><br>}<br><br>{\left[I<br><br>\left(X,Y\right)-I_i^{\mathrm{MOY}}\right]}^2+\mathrm{\lambda <br><br>}<br><br>\underset{\mathrm{VBD}}{\sum <br><br>}<br><br>1/\left[1+{\left(<br><br>G<br><br>/<br><br>G_0<br><br>\right)}^2\right],$

in which the first term is the intensity variance function, expressed by a first function for the summing, over all cells (C_i), of the squares of the differences between the intensity (I(x,y)) of a voxel having the co-ordinates (x,y) and the mean intensity (I_i^MOY) in the cells (C_i) whereto this voxel belongs, and in which the second term is weighted by the weighting factor (λ

) and is formed by a second function for the summing, over all pairs of voxels situated at the interface of the cells, of a specific measure which takes into account the modulus of the normalized gradient (∥

G∥

/∥

G₀∥

) of the voxels of these interface pairs, and

wherein the merger threshold (λ

₀(j,k)) enabling the merger of two adjoining cells (C_j, C_k) to be performed is evaluated as a function of the differences of the mean intensities (I_i^MOY, I_k^MOY) of two cells to be merged, and of the number of points (m_j, m_k) in these cells, and of a second summing function in conformity with a formula;

${\mathrm{\lambda <br><br>}}_0<br><br>\left(j·<br><br>k\right)=m_j<br><br>{m_k<br><br>\left(I_j^{\mathrm{MOY}}-I_k^{\mathrm{MOY}}\right)}^2/\left(m_j+m_k\right)<br><br>\underset{\mathrm{VBD}}{\sum <br><br>}<br><br>1/\left[1+\left(<br><br>G<br><br>\right)/<br><br>G_0<br><br>\right].$

7. A method as claimed in claim 5 wherein evaluating the specific merger threshold (l₀^p), enabling the concomitant execution of several mergers of two adjoining cells (C_j, C_k), further comprises:

determination of merger thresholds (λ

₀(j,k)) for the cells of all pairs of cells of the image,

classification of these values (λ

₀(j,k)) of the merger threshold according to increasing values (λ

₀^p), the number of said values being at the most equal to the total number of interfaces present in the presegmented image (1≦

λ

₀^p≦

λ

₀^MAX),

determination of slices (l₀^p) of these values of merger threshold factors (λ

₀^p), classified according to increasing values,

formation of a simple histogram of the number (h₀^p) of merger events for adjoining cells in each respective slice (l₀^p) of the merger threshold values (λ

₀(j,k)),

formation of an accumulated histogram while inscribing in each slice (l₀^p) the accumulated sum (H₀^p) of the number of said events (h₀^p) from the first slice (l₀¹) until the slice considered (l₀^p), for all slices (l₀¹ l₀^MAX) of the merger threshold values (λ

₀^p), and

definition of said specific merger threshold as the slice (l₀^p) which comprises the number of events (H₀^p) corresponding to a predetermined number of concomitant mergers.

8. A method as claimed in claim 7 further comprising, after evaluating the specific merger threshold,

selecting a predetermined number of interfaces to be concomitantly eliminated between adjoining cells of pairs,

visiting the pairs of adjoining cells of the image and

merging adjoining cells of pairs whenever the merger threshold relating to these cells (λ

₀(j,k)) is below said specific merger threshold (l₀^p).

9. The method of claim 3 wherein the actually segmenting further comprises:

defining a cost function (F) which comprises a first term which is a function of the intensity variance (σ

²) within the cells present in the image, and a second term which is weighted by a variable weighting factor (λ

) and is a function of intensity gradients at the edge points of cells, and

evaluating the merger threshold (λ

₀(j,k)) in order to perform the merging of two adjoining cells (C_j, C_k) of a pair as the value of the variable weighting factor (λ

) which cancels the difference (E₀) between the cost function (F₀) calculated before the merging of two cells and the cost function (F₁) calculated after this merger.

10. The method of claim 9 wherein the cost function is given by the formula:

$F=\underset{C_i}{\sum <br><br>}<br><br>{\left[I<br><br>\left(X,Y\right)-I_i^{\mathrm{MOY}}\right]}^2+\mathrm{\lambda <br><br>}<br><br>\underset{\mathrm{VBD}}{\sum <br><br>}<br><br>1/\left[1+{\left(<br><br>G<br><br>/<br><br>G_0<br><br>\right)}^2\right],$

in which the first term is the intensity variance function, expressed by a first function for the summing, over all cells (C_i), of the squares of the differences between the intensity (I(x,y)) of a voxel having the co-ordinates (x,y) and the mean intensity (I_i^MOY) in the cells (C_i) whereto this voxel belongs, and in which the second term is weighted by the weighting factor (λ

) and is formed by a second function for the summing, over all pairs of voxels situated at the interface of the cells, of a specific measure which takes into account the modulus of the normalized gradient (∥

G∥

/∥

G₀∥

) of the voxels of these interface pairs, and

wherein the merger threshold (λ

₀(j,k)) enabling the merger of two adjoining cells (C_j, C_k) to be performed is evaluated as a function of the differences of the mean intensities (I_j^MOY, I_k^MOY) of two cells to be merged, and of the number of points (m_j, m_k) in these cells, and of a second summing function in conformity with a formula;

${\mathrm{\lambda <br><br>}}_0<br><br>\left(j·<br><br>k\right)=m_j<br><br>{m_k<br><br>\left(I_j^{\mathrm{MOY}}-I_k^{\mathrm{MOY}}\right)}^2/\left(m_j+m_k\right)<br><br>\underset{\mathrm{VBD}}{\sum <br><br>}<br><br>1/\left[1+\left(<br><br>G<br><br>\right)/<br><br>G_0<br><br>\right].$

11. The method of claim 10 wherein evaluating the specific merger threshold (l₀^p), enabling the concomitant execution of several mergers of two adjoining cells (C_j, C_k), further comprises:

determination of merger thresholds (λ

₀(j,k)) for the cells of all pairs of cells of the image,

classification of these values (λ

₀(j,k)) of the merger threshold according to increasing values (λ

₀^p), the number of said values being at the most equal to the total number of interfaces present in the presegmented image (1≦

λ

₀^p≦

λ

₀^MAX),

determination of slices (l₀^p) of these values of merger threshold factors (λ

₀^p), classified according to increasing values,

formation of a simple histogram of the number (h₀^p) of merger events for adjoining cells in each respective slice (l₀^p) of the merger threshold values (λ

₀(j,k)),

formation of an accumulated histogram while inscribing in each slice (l₀^p) the accumulated sum (H₀^p) of the number of said events (h₀^p) from the first slice (l₀¹) until the slice considered (l₀^p), for all slices (l₀¹ l₀^MAX) of the merger threshold values (λ

₀^p), and

definition of said specific merger threshold as the slice (l₀^p) which comprises the number of events (H₀^p) corresponding to a predetermined number of concomitant mergers.

12. A method as claimed in claim 1 further comprising,

prior to segmenting, acquiring two-dimensional (2-D) intensity images of a volume and reconstructing a noisy three-dimensional (3-D) image, and

subsequent to segmenting of the three-dimensional image into object cells and background cells, reconstructing a three-dimensional image by means of a method utilizing voluminal renditions where each object is attributed the respective individual intensity of the corresponding cell.

13. A method as claimed in claim 1 wherein the multidimensional image is a medical vascular image.

14. A medical imaging apparatus comprising:

an image acquisition system for providing data of an image, and

an image processing system which has access to the data of the image and to an image display system and comprises a processor for carrying out an image processing method as claimed in claim 1.

15. A medical imaging apparatus as claimed in claim 14 wherein the image acquisition system further comprises an x-ray source.