EP1934936A2

EP1934936A2 - A method of segmenting an image

Info

Publication number: EP1934936A2
Application number: EP06806125A
Authority: EP
Inventors: François Bernard LAUZE; Mads Nielsen
Original assignee: Nordic Bioscience AS
Current assignee: Nordic Bioscience AS
Priority date: 2005-10-10
Filing date: 2006-10-09
Publication date: 2008-06-25
Also published as: WO2007042251A3; WO2007042251A2

Abstract

A method of segmenting an image having a background region and an area of interest, wherein the area of interest is surrounded by part of the background region, which method comprises: taking a starting set of digital data representative of the image; (1 ) estimating a boundary of the area of interest; (2) inpainting the area of interest within the boundary using information from the remainder of the background region; (3) computing the difference between the starting set of digital data and the inpainted set of digital data to obtain a result representative of the degree of disocclusion of the background region; (4) moving the position of the estimated boundary to produce a further generation estimated boundary; (5) inpainting the area within the further generation estimated boundary; and (6) computing the difference between the starting set of digital data and the inpainted set of digital data; continuing iterations of steps (4), (5) and (6) until a maximum degree of disocclusion is obtained, using information of the boundary of the area of interest at the time the maximum degree of disocclusion is obtained to segment the image.

Description

A METHOD OF SEGMENTING AN IMAGE

The present invention relates to a method of segmenting an image including a background region and an area of interest.

lnpainting is a technique that originates from retouching paintings where one wants to recreate lost or damaged structures in a legible way. Digital inpainting uses spatial or frequency information to restore partially damaged/removed images.

Various inpainting techniques are known that enable image restoration, in particular for photographs, videos and films.

Active contours, or snakes, have been used extensively in computer vision and medical imaging, for the purpose of segmentation, in order to overcome the locality problem of. edge detectors. They are curves with built-in regularity properties and preferences for edges in an image. Although very simple to implement, they suffer from initialisation problems that necessitates reparameterisation.

Several approaches have previously been suggested in order to overcome initialisation problems, including balloon forces and gradient vector flows. Geodesic active contours introduce a parameterisation independent formulation. All these models deal only with contours, not with the regions they separate.

Based on a simplification of the Mumford-Shah segmentation described in "Communications on Pure and Applied Mathematics (42:577-684, 1989)", Chan and Vese in "Active contours without edges (IEEE Transactions on Image Processing)" proposed a region based algorithm that leads to a contour evolution coupled with the estimation of the mean values in the regions delimited by this contour. More complex statistical descriptors have also been proposed instead of the mean. In a series of papers, Paragios and Deriche in "Geodesic active regions: a new paradigm to deal with frame partition problems in computer vision (Journal on Visual Communication and Image

Representation, 13 (1/2):249-268, March/June 2002)" proposed a new paradigm called Geodesic Active Regions where both contour based and region based terms are used. Many declinations on these ideas have been proposed to tackle a variety of situations encountered in computer vision and medical imaging.

Usual region based active contours assume that the image is divided into several semantically meaningful regions and attempt to differentiate them through recovering dynamically statistical optimal parameters for each region. For example, a prior art method is illustrated in Figure 1 , where Figure 1A represents the flag of the Greenland territory and Figure 1 B shows an object added on a smooth background via addition of intensities, similar to the presence of transparent layers, known as "pseudo-classifications".

Referring to Figure 1 A, contour based active contour methods can provide a segmentation of the circle. Although sensitive to the initialisation, region based active contours using statistical parameters of intensity/colour distribution for each region will fail to isolate the circle in the flag from the rest of the image, since the two regions have the same statistics. Referring to Figure 1 B, the pseudo-classification image, the difficulty comes from the hardly visible edge information.

The present inventors have recognised that it would be desirable to provide an alternative method of segmentation, using region based active contours with image inpainting.

According to a first aspect of the present invention, there is provided a method of segmenting an image having a background region and an area of interest, wherein the area of interest occludes part of the background region, comprising the steps of: taking a starting set of digital data representative of the image; (1 ) estimating a boundary of the area of interest;

(2) inpainting the area of interest within the boundary using information from the remainder of the background region;

(3) computing the difference between the starting set of digital data and the inpainted set of digital data to obtain a result representative of the degree of disocclusion of the background region;

(4) moving the position of the estimated boundary to produce a further generation estimated boundary; - -

(5) inpainting the area within the further generation estimated boundary; and

(6) computing the difference between the starting set of digital data and the inpainted set of digital data; continuing iterations of steps (4), (5) and (6) until a maximum degree of disocclusion is obtained, using information of the boundary of the area of interest at the time the maximum degree of disocclusion is obtained to segment the image.

It will be appreciated that a maximum degree of disocclusion would result in optimum information about the boundary of the area of interest. However, a useful segmentation can also be obtained if steps (4), (5) and (6) are repeated until the degree of disocclusion approaches a maximum.

Preferably the result representative of the degree of disocclusion is additionally determined by the size.of the area within the estimated boundary.

In an embodiment, the result representative of the degree of disocclusion is biased in a positive way in response to an increase in the difference between the starting set of digital data and the inpainted set of digital data and a decrease in the area within the estimated boundary.

Preferably, the step of moving the position of the estimated boundary comprises using information derived from the result representative of the degree of disocclusion to determine how the position of the estimated boundary should be moved.

More preferably, the step of moving the position of the estimated boundary comprises moving portions of the boundary in subsequent iterations in a direction determined by the factor that yields improvement in the result representative of the degree of disocclusion.

In an embodiment, the step of moving the position of the estimated boundary in subsequent iterations comprises moving a portion of the boundary to increase the area within the boundary in response to an increase in the result representative of the degree of disocclusion resulting from an increase in . -

the difference between the starting set of digital data and the inpainted set of digital data.

In an alternative embodiment, the step of moving the position of the estimated boundary in subsequent iterations comprises moving a portion of the boundary to increase the area within the boundary in response to an increase in the result representative of the degree of disocclusion resulting from an increase in the previous iteration of the difference between the starting set of digital data and the inpainted set of digital data.

Preferably, the result representative of the degree of disocclusion is a generalised statistical moment of the difference between the starting set of digital data and the inpainted set of digital data on the area of interest.

The present invention also extends to a method of computing the shape and size of a calcification of a blood vessel by processing an image of at least a part of the blood vessel containing said calcification, which method comprises: taking a starting set of digital data representative of an image of at least part of a blood vessel containing an area of calcification, said area of calcification being set against a background area;

(1 ) estimating a boundary of the area of calcification;

(2) inpainting the area of calcification within the estimated boundary using information from the remainder of the background area;

(4) moving the position of the estimated boundary to produce a further generation estimated boundary;

(5) inpainting the area within the further generation estimated boundary; and

(6) computing the difference between the starting set of digital data and the inpainted set of digital data; continuing iterations of steps (4), (5) and (6) until a maximum degree of disocclusion is obtained, using information of the boundary of the calcification at the time of the maximum degree of disocclusion to compute the shape and size of the calcification. The present invention further extends to a method of reconstructing the background of an image having an area of interest in the foreground, comprising: taking a starting set of digital data representative of the image;

(1 ) estimating a boundary of the area of interest of the foreground;

(5) inpainting the area within the further generation estimated boundary; and

(6) . computing the difference between the starting set of digital data and the inpainted set of digital data; continuing iterations of steps (4), (5) and (6) until a maximum degree of disocclusion is obtained.

The present invention also extends to a pre-programmed computational means and an instruction set for performing the above described invention.

Embodiments of the present invention will hereinafter be described, by way of example, with reference to the accompanying drawings, in which:

Figures 1A and 1 B show two examples where segmentation is required for inpainting;

Figures 2A and 2B show an example of the segmentation required in the present invention;

Figure 3 shows the results of a first experiment where the four square blocks on white are the background;

Figure 4 shows the results of a second experiment where an image in the foreground is isolated from the background image to enable segmentation; Figure 5 shows the image of the second experiment being defined from a first starting contour; - -

Figure 6 shows the various stages of the present invention starting with an image having a background region with an occluding area and ending with an image where the occluding area has been segmented;

Figures 7 A to 71 illustrate an example of the present invention when used to determine the shape and size of an area of calcification in a blood vessel;

Figures 8A to 81 show the example of Figures 7A to 71 illustrating the progression of the area within the boundary;

Figures 9A to 91 show the example of Figures 7A and 71 illustrating the background image when the area within the boundary is inpainted;

Figures 1 OA to 10D illustrate an example of the present invention starting with a small misplaced initial contour;

Figures 1 1 A to 11 F illustrate an example of the present invention starting with an initially manually placed contour derived from the detection of regions of calcification in an x-ray;

_ Figure .12 illustrates the present invention when applied to the Greenland flag; and

Figure 13 illustrates the present invention when used to remove an image of a bus from a background image.

To summarise, the present invention introduces a novel methodology within the framework of active contours. This belongs to the region based family of active contours, but instead of considering that the image domain is partitioned into two (or several regions), the present invention consists in considering the following problem:

If the region Ω containing the object of interest is known, and if enough information is present on the type of background, it may be possible to construct the occluded background image. If a positive answer to this question is assumed, then it can be questioned whether a given region Ω contains an object occluding the background in the following way:

If Ω delimits the area occupied by a foreground object, then there should be sufficiently large difference between the observed image and the reconstructed one within this region. This naturally leads to a variational problem, if Ω is a given region of the image plane D , M₀ the observed image, w(Ω) = /(M₀ , Ω) the reconstructed background and if this background/foreground difference is called 7(Ω) , we may look for the true region b as an extremum for 7(Ω) . The goal of this work is to propose such a measure, first in general terms, and then a specific instance based on a relatively simple variational inpainting formulation, which essentially corresponds to TV inpainting as disclosed by Chan and Shen in "Mathematical models for local nontexture inpainting (Siam journal of applied Mathematics, 62(3): 1019-1043, 2002)", and a simple measure of discrepancy between two images, based on pixel value differences. From it, a corresponding active contour algorithm is derived.

It is required to try and separate the background from the foreground. In traditional segmentation described above, an area is segmented by differentiating between an area of foreground having different characteristics to the background and the area of background that surrounds the foreground. By contrast, in the present invention, the image is segmented by differentiation between the foreground and the background as a whole - as if the foreground did not exist.

It will be understood that the foreground that requires segmentation may be considered to be an area of interest that occludes or is set against the background.

The present invention will be described below in context of the mathematics used to enable the various functions to be found. However, to summarise, the following steps, as shown in Figure 2, are taken:

1. An assumption is made that an image consists of a background region 2 and an area of interest 4, where the area of interest occludes part of the background region. 2. An initial estimate is made of the location of the boundary 6 of the area of interest located in the background region.

3. The background region is assigned a positive function and the area of interest is assigned a negative function.

4. Information from the assumed background region is used to inpaint the assumed area of interest i.e. the foreground region. 5. The intensity values of the original image, prior to inpainting, are compared with the intensity values of the inpainted image to derive a disocclusion quality measure.

6. The assumed boundary of the area of interest is adjusted. 7. Steps 4 and 5 are repeated such that the assumed area of interest is once again inpainted using information from the background region and the intensity values of the original image and the inpainted image are compared to derive a disocclusion quality measure.

8. Steps 4 to 7 are repeated until the disocclusion quality measure reaches a maximum, thus fulfilling the convergence criteria described below. At this time, the assumed boundary should correlate with the actual boundary of the area of interest.

9. The image may then be segmented into two separate and distinct images (as shown in Figure 2A) as required.

In the present invention, the term "disocclusion" is used to describe the removal of an area of interest occluding part of the background region. The disocclusion quality measure gives a numerical indication of how successful the boundary estimation and therefore the inpainting has been.

The present invention is described with reference to "an image". It will be apparent that by "taking an image" this involves starting with an image previously acquired by some imaging means, for example, an x-ray image. The starting point of the present invention is digital information representing an image.

Described below are background disocclusion ideas and corresponding variational formulae that lead to an active contour evolution equation.

Let D be the image domain, w_ή the background image defined on D .

Let Ω c D an unknown region and u_f the foreground image with support Ω . One supposes that the observed image u₀ is obtained through a combination operation

Ii₀ = C (Ub ₁ Uf ) . - -

The basic problem is to be able to determine, from u₀ , the region Ω and information on u_b and u_f . We now assume that if Ω is known, we can confidently estimate u_h using an inpainting or disocclusion operation u_h - /(M₀, Ω) . The following two assumptions are made:

1. M₀ and u_h should differ significantly inside the foreground region Ω

2. the foreground region should be relatively small.

These two assumptions are used to form a "disocclusion quality measure", that attributes a numerical score to a given region Ω c D belonging to an admissible set P of regions of D

J(J?) = / I (J(-u₀, J7), «o_! J?) rf.x' (1)

where the "Lagrangian" L -. SixSixP → %(χ, y, A) \→ L(x, y, A) incorporates measures of the difference between x and y as well as measure of the size of its argument.

The true region Ω should be an extremal point of 7(Ω) and we therefore search for a necessary condition for the function /(Ω) to achieve an extremum. The next step is to consider the case of noisy additive signals u_h + u_f +η,η being some noise, as it would be in the case of, for example, X-rays or reflection.

With this additive model, an elementary way to measure the discrepancy between u₀ and u_h in the region of inpainting consists in summing up a function of pixelwise intensity differences, while a measure of the region can be given by its area, or a function of it. A simple form for the function L incorporating these measures is:

- -

With I A I denoting the area of the set A , and p > 0,q - 1 or 2 , and we therefore want to maximise /(Ω) . Another option is:

In both options, the resulting J(Ω) can be seen as a "generalised moment" of u₀ -u_b on Ω , a moment that we want to maximise.

As set out in the above equations, J(Q) is biased by the two following properties:

1. The difference between the intensity values of the original image and the inpainted image u_o - ϊϊ_h , that is, as the difference in intensity values increases, the resultant value for the disocclusion quality measure also increases; and 2. The area that is inpainted A . As the area increases, the disocclusion quality measure decreases.. .. . . .. .. .. . .

Therefore, the disocclusion quality measure seeks to optimise itself by finding the maximum difference in intensity between the original image and the inpainted image within the minimum possible area.

The present invention uses the computation from Aubert et al in "Image Segmentation using active contours: Calculus of variations or shape gradients? (SIAM Journal of Applied Mathematics, 63(6):2128-2154, 2003)" of 7'(Ω) using shape derivative tools. Let rthe boundary of Ω , N the inward normal to r , the Gateaux derivative of /(Ω) in the direction of V is, using the chain rule:

(J(Ω)'_t V) = / L, (J(W₀, Ω), u₀, Ω) I₈(U₀, Ω, V) dx

+ / L _s (J(U₀ > Ω), U₀. Ω. V) ) dx - I L (J(W₀ - Ω), U₀ , P) (V - N) da(x) . (4) Jn Jr

In order to obtain a contour evolution equation, it is necessary to calculate the first term, involving the shape derivative Z₅(M₀₅Q₁V)Of the inpainting with respect to the inpainting domain, as well as the second term, involving the shape derative of the Lagrangian L(x, y,A) . - π -

The next step is to apply the inpainting operation and compute the shape derivate related terms.

The present invention has been described using a relatively simple inpainting formulation. However, it will be appreciated that the same method will apply to various other inpainting methods, for example Elastica Inpainting (as described in Chan and Shen).

The inpainting formulation used in the present invention is: u = /(w_o,Ω) is defined as:

u = arg.min .F(ι^;. Mn, Ω) υ

With

T(υ. «„. Ω) = ± f (r - _U())² d.r + I - ( yfivϊf+ ε*) ^'' cLr (5)

where 1 ≤ r < 2. For r = l,ε = 0 , this corresponds to the total variation inpainting of Chan and Shen. Assuming nevertheless that ε > 0 when 1 < r < 2 , this makes the solution of the minimisation unique (standard arguments show the uniqueness of the solution in the case r = 2 and a formal justification in the settings for r and ε as used in the present invention will be presented below) and allows to define the inpainting operator («₀,Ω) ι→ /(w_o,Ω,V) .

The choice of a simple inpainting technique enables the assumption of a high level of regularity for the partially unknown background, and this is an important restriction for the domain of the validity of the final algorithm.

The derivation of the inpainting related shape derivate is now performed.

If v is a test function on D , define /(T) = F(u +τv) . Since u is assumed to be a minimiser for F , the first variation of F in the direction v,/'(0) , must vanish and it provides the optimality condition - -

0 = /(Λγmr>('i - «<))<^•+ (|V//,|)'--²V</ ^• Vr) d.r (G)

JD

χD \Ω denotes the characteristic function of D\Ω . The inpainting PDE is the Euler-Lagrange equation

T_u(u,ι_khΩ) = 0. (9) extracted from equation (7), which allows to implicitly define u = /(M₀, Ω) by

T_a(I(uo, Ω),u_{hΩ) = 0. - --

Assuming that F_u is differentiable with respect to its first and last variables, this expression allows to compute w_s(V) via the implicit function theorem:

U₃[V) = - {T_uu(ιι,u₀,Ω))-¹ T_UH{u,u_{),Ω,Y) (10)

F_uu denoting the partial differential of F_u with respect to its first variable is explicited below as a linear elliptic operator, while F_m denotes the shape derivative of F₁₁ and can be computed as:

F_as(u> wo, V) = X(a - U₀)(V ^■ N)ό> δ_r being the Dirac distribution along r . The first term of the Gateaux derivative (4) can be written:

-λ / \_ΩL_x(u,u₀.Ω)T ({u- U₀)(V -N)(Jr) dx J 'DD where u and χ_n is the characteristic function of Ω . Using the formal adjoint of T* of T , this term can be rewritten as: -λ / r {\_ΩL_ε(u. U₀. Ω)){u- U₀)(V ^■ Words ■ID

and finally as the boundary integral:

An expression can now be provided for the operator T = Fj . Setting g(τ) = (F_u(u + τw,u₀,Ω),v) for a test function w on D , the operator F_uu is obtained from

(T_uu(u,t_khΩ){w), v) =y'(0). A straightforward computation using for instance expression (6) gives:

the last equality by integration by part and adequate boundary conditions, and where A[V _u] is the 2x2 symmetric matrix

which, under the assumptions made on rand ε is positive and definite. It can also be noted that the quadratic form F_HH(κ,«₀,Ω),(v),v is /"(0), the second variation of F in the variation of v and is positive, as it can be seen from equation (11). This means that the inpainting energy is strictly convex, explaining the uniqueness of the minimiser. Expression (12) provides the expression of F_uu(u,u_Q,Ω) as the differential operator - -

T_iiU(u. Uo, Ω)(w) = - άiv(A[Vu]Vw)

Positive definiteness also implies here that F_uu is formally invertible, and from equation (1 1 ) and the symmetry of A[Vw] , it is self-adjoint

(F_uu(u, Uo, Ω) (;w), v) = (w, J⁷ _Uu (U- Uo, Ω) (v)) .

The operator T = Fj which consequently self-adjoins, T = T * , is given by v ι→ T(v) , and is defined as the unique solution of

The next step is involved with writing the curve evolution equation. To do this, it is necessary to compute the second term in equation (4). The shape derivative in the direction of V of the area | Ω | is given by - J (V ^■ N)da(x) and with the

Lagrangian L being defined by either (3) or (2), one gets: . .

/ (^{v • N}) Mx)-

Collecting all these calculations, we find that the Gateaux derivative (/(Ω)',V) is given by J F(V ^• N)da(x) where F is

p-— λ(w - Uo)T (XQL_X (V,, UQ , Ω)) + L(u, U₀, Ω) (15) I^{J /}I

The goal is to maximise the "disocclusion criterion".

This leads to the following evolution equation — = FN . This curve evolution is

Bt rewritten into the Osher-Sethian in "Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid MechNics, Computer Vision, and Materials Sciences. (Cambridge Monograph on Applied and Computational Mathematics, Cambridge University Press 1999)" framework of level sets as φ, = F | V^ | where φ represents implicitly T(t) and Ω(t) via T(O = {φ(x,t) = 0} and Ω(0 = (φ(x,t) < 0} .

A first order space convex scheme is used to solve this equation, it is ψ'f¹ O)V^"] .

This leads to the following algorithm:

1. Choose an original contour r° , compute φ° as the signed distance function φ° (x) = dist_r0 (x) and Ω° = [x, H(-φ° (x)) = 1} , where H is a 1 -dimensional heaviside function

2. For i = 0 to N - 1 or a convergence condition has been fulfilled (a) compute the inpainting u" = /(«„, Ω") and r(j_ΩL_c(w",w₀,Ωⁿ )) and the disocclusion measure 7(Ω") .

(b) Compute F" from the previous calculations

(c) Compute φ^n+ι with the above scheme

(d) Extract rⁿ⁺¹ and Ωⁿ⁺¹ from it (e) Reinitialise φⁿ⁺ⁱ as a signed distance φ"^+ι(χ) = dist_r+t (x)

3. return t^ and Ω^N

The time step Δπs chosen at each iteration as 1/ Il F" 11 =>o . The discretisation used for the inpainting /(«₀,Ω" ) follows closely the one proposed by Chan and Shen in "Mathematical models for local non texture inpainting" ([SIAM Journal of Applied Mathematics, 62(3), 1019-1043, 2001]). The digital inpainting is computed using a Full Multigrid Scheme, with one V-cycle at each resolution where each level of the V-cycle implements a Full Approximation Scheme (FAS) (following the description given in "A Multigrid Tutorial" (SIAM)). The Grid transfer operations use the ones proposed in "Variational Optical Flow

Computation in Real Time" (IEEE Transactions on Image Processing, 14(5), 608-615, 2005) except for the downsizing of the digital characteristic function XD\Ω where a nearest neighbourhood interpolation is used.

The computation of T(χ_ΩL_x(uⁿ,u₀,Ω." )) as the solution w of the PDE

XΩLΛ'U" , U₀, Ω") (1C) requires some care. Indeed, apart from the trivial case r = 2 in (13) where A I VM" I reduces to the 2 x 2 matrix, the divergence term will normally contain spatial cross-derivatives and thus needs special attention for the discretisation. The linear resulting from equation (16) is again solved with a Full Multigrid Scheme, each V-cycle implementing a linear multilevel solver. - 1 -

Finally, the heaviside function used is implemented with almost no regularisation of most region based algorithms. Too much regularisation would bias the inpainting.

An example of the iterative process used to adapt the contour from the initial estimate to fit the contour of the area to be inpainted is described below with reference to the example shown in Figure 5, where an area of interest 8 is shown as the foreground to a slightly noisy background 10.

The initial estimate for the boundary to eventually define the contour of the area of interest is in the shape of a giraffe. As set out above, the invention relies on inpainting an area within the estimated boundary using information from the remainder of the background. Therefore, in this example, information derived from the area outside of the giraffe is used to inpaint the area inside the giraffe. Following this, the disocclusion quality measure is derived based upon the difference in intensity values between the original image and the inpainted image with reference to the size of the area within the giraffe.

The boundary is deemed to be split into portions. For each portion a decision is made based on information derived from the disocclusion quality measure. For example, we will first consider the left leg 12 of the giraffe. It is clear from the image that this left leg does not cover the area of interest. Therefore, a decision will be made to have a first attempt at moving the portion of boundary at the bottom of the left leg so that the overall area of the giraffe increases. A move of this nature will result in the same difference of intensity values between the orginal image and the inpainted image as in the previous iteration. As the area within the boundary has increased, the overall disocclusion quality measure will have decreased. Therefore, in the next iteration, it will be apparent that this particular portion of the boundary should be moved to result in a decrease in the overall area of the giraffe.

Conversely, if we consider the left side of the neck 14 of the giraffe, it is clear from the image that this boundary falls within the area of interest. Moving this portion of the boundary to result in an increase in area of the giraffe will result in a greater difference between the intensity values of the original image and the inpainted image. This will, in part, be offset by the increase in area of the inpainted section. However, the overall result will either be that the disocclusion quality measure will increase, or that it will stay the same. Therefore, in the next iteration, it will be apparent that this portion of the boundary should be moved to result in a further increase in the overall area of the giraffe. This iterative process will continue for this portion of the boundary until a move of this portion of boundary results in no increase in the difference of intensity values between the original image and the inpainted image, i.e. this portion of the boundary now falls outside the area of interest, and therefore the overall result will be a decrease of the disocclusion quality measure.

By this iterative process, the estimated boundary is gradually adapted to fit the contour of the area of interest as shown in Figure 5 (middle image).

Results are given below from experiments performed on synthetic as well as real data. They present an increasing level of complexity in the image content. The method of inpainting used in these experiments is regularised Total Variation one, i.e. r = 1 in the energy, and the function L being the one given by (2), with q = 1.0 .

Experiment 1 As shown in Figure 3, experiment 1 is based on an image of four black squares on a white background. Thus, based on the assumption of the present invention, the two areas to be segmentised are the white background, following its reconstruction, and the foreground of four black squares. The parameters are λ = 1, p = 0.25. The first row shows a snapshot of the contour evolution at iterations 1 , 7, 15 and 30. From this it can be seen that as the iterations continue, the contours more clearly define the black squares in the foreground. The second row shows the corresponding domain and the last row shows the inpainting result. The circles in row 1 provide the starting point for finding the contours of the areas of segmentation. The contours are then iteratively adapted until the foreground areas have been depicted. The final row shows the result of inpainting within the segmentation.

Experiment 2 As shown in Figure 4, experiment 2 is based on a dark non convex object on a light background with 30% added Gaussian noise. In this experiment, λ - 0.1, p = 0.55. This is illustrated in the right part of Figure 4. The first row shows a snapshot of the contour evolution of iterations 1 , 10, 20 and 30. From this it can be seen that gradually, the mathematical formulae result in the contour clearly defining the foreground shape. The second row shows the corresponding domains and the last one of the inpaintings.

Experiment 3 As shown in Figure 5, experiment 3 uses the same image as experiment 2. It illustrates some stability with respect to the initial contour, as well as the role of the area penaliser exponent p in L . Two experiments were performed, the first with a value of p = 0.55 , as in the previous case and the second with a value of p = 0.60. In both cases, the λ weight in the inpainting was set of 0.1. In the first case, a correct segmentation has been achieved, while in the second, the right part of the horizontal ellipse could not be fully recovered. As can be seen from Figure 5, the initial contour is in the shape of a giraffe, but this is gradually adapted to fit the shape of the foreground object.

Experiment 4 Shown in Figure 6, experiment 4 shows a "pseudo classification" image. This image could represent an image typically found in medical imaging, for example, of an area of calcification. This image is made of a smooth background (a 4^th order polynomial in the image coordinates), with an object added (by adding intensity values). While the intensities in background are in the range [0,1], the original intensity of the added object is constant, equal to 0.065. From the experimentation, it was possible to produce some good quality measure using the function L given by (3), however, it proved difficult to control. So the same function was used as for the other examples, with p = 0.5. In order to prevent the inpainter/denoiser from smoothing too much of the background, a value of λ = 8 was chosen in (5). As illustrated in Figure 6, the first row shows the original object and the pseudo classification. The two next rows show snapshots of contour evolution at different iterations, for two different initialisations. The second initialisation, while "more creative" is also closer to the true contour and allows for a much faster convergence (260 iterations in the first case, 50 in the second).

A further example of use of the present invention in determining the shape of a calcification is shown in Figures 7 A-I, Figure 8 A-I and Figures 9 A- I. Figures 7A-I show various iterations of the contour evolution starting with an initial random estimate of the boundary of the area of calcification. As can be seen, as the iterations progress, the boundary is adapted to fit the contour of the area of calcification. This sort of technique would be useful for locating and assessing calcifications found in blood vessels, for example, an aorta. Figures 8A-I show corresponding images of the areas within the boundary. Figures 9A- I show the images of the background with the area within the boundary inpainted using information from the remainder of the background. As can be seen in Figure 91, the area of calcification is no longer visible.

In accordance with the algorithm and the factors that contribute to determining the disocclusion quality measure, it can be seen from Figure 71 that the boundary does not exceed the actual area of calcification. In this respect, the mathematics used to calculate this disocclusion quality measure is biased against increasing the area of the boundary without the increase resulting in an increase in the difference in intensity between the original image and the inpainted image.

Figures 1OA to 1OD illustrates the robustness of the segmentation algorithm described above. As can be seen from Figure 1OB, the initial boundary provided at the beginning of the algorithm is relatively small and misplacedjn comparison to the area of interest. However, using the algorithm above this initial small curve evolves into a meaningful boundary that can subsequently be used for segmentation.

Experiment 5 Figures 11 A to 11 F illustrate the results of a segmentation initialised by a calcification detection method. In this experiment the initial contours shown in Figures 1 1 B and 11 E are applied manually following the detection of areas of calcification using the calcification detection method described in Bruijne in "Shape Particle Guided Tissue Classification". These contours are used as the initial boundaries in the above defined algorithm which is subsequently executed to result in the boundary locating the edge of the area of interest, in this case an area of calcification.

Experiment 6 This experiment uses the Greenland flag with added Gaussian noise, with a standard deviation of 50% of the intensity range of the image. The function L is used with /? = 0.85 this time. The contour differentiates the circular part of the flag from the remainder of the background. The two areas of segmentation are the circle and the background rectangle, ignoring the circle. The inpainting takes information from the remainder of the surroundings to inpaint the area of segmentation within the circle. Results are shown in Figure 12, where the evolution of the disocclusion measure is also plotted. As can be - -

seen, the disocclusion quality measure continues increasing until the contour fits the area to be segmented - based on the calculations made following inpainting of the foreground region.

Experiment 7 This last experiment presented shows a different use of the present invention, for example when used in photography, or special effects. A rather complex input image is used, with the third frame from the Ettlinger-Tor sequence, frequently used in optical flow estimation. As can be seen from Figure 13, the image is of a road with a bus. In this case, the road is the background image and the bus is the foreground image. The results, although perhaps of lesser quality than may be obtained with state of the art algorithms, show that the described invention can produce meaningful results, even when the background smoothness assumption is largely violated as in the present case. The parameters used here were λ = 0.5 and p = 2^~η , a very small value. It can be seen that the background is gradually reconstructed to remove the bus from the image. It is apparent that this technique could therefore be used in various applications, for example image restoration or special effects.

Thus it can be seen from these experiments that the contour evolution equation derived is effective when used to segment images having a background with a foreground image present.

It will be appreciated that modifications to or variations of the embodiments described and illustrated may be made within the scope of this application as set out in the appended claims.

Claims

- -CLAIMS

1. A method of segmenting an image having a background region and an area of interest, wherein the area of interest is surrounded by part of the background region, which method comprises: taking a starting set of digital data representative of the image;

(1 ) estimating a boundary of the area of interest;

(5) inpainting the area within the further generation estimated boundary; and

2. A method as claimed in claim 1 , wherein the result representative of the degree of disocclusion is additionally determined by the size of the area within the estimated boundary.

3. A method as claimed in claim 2, wherein the result representative of the degree of disocclusion is biased in a positive way in response to an increase in the difference between the starting set of digital data and the inpainted set of digital data and a decrease in the area within the estimated boundary.

4. A method as claimed in claim 3 wherein the step of moving the position of the estimated boundary comprises using information derived from the result representative of the degree of disocclusion to determine how the position of the estimated boundary should be moved. - T) .

5. A method as claimed in claim 3 or claim 4, wherein the step of moving the position of the estimated boundary comprises moving portions of the boundary in subsequent iterations in a direction determined by the factor that yields improvement in the result representative of the degree of disocclusion.

6. A method as claimed in claim 5, wherein the step of moving the position of the estimated boundary in subsequent iterations comprises moving a portion of the boundary to increase the area within the boundary in response to an increase in the result representative of the degree of disocclusion resulting from an increase in the previous iteration of the difference between the starting set of digital data and the inpainted set of digital data.

7. A method as claimed in claim 5, wherein the step of moving the position of the estimated boundary in subsequent iterations comprises moving a portion of the boundary to decrease the area within the boundary in response to a decrease in the result representative of the degree of disocclusion resulting from either an increase in the size of the area within the boundary or a decrease in the difference between the starting set of digital data and the inpainted set of digital data.

8. A method as claimed in any of claim 2 to claim 7, wherein the result representative of the degree of disocclusion is a generalised moment of the difference between the starting set of digital data and the inpainted set of digital data on the area of interest.

9. A method of computing the shape and size of a calcification of a blood vessel by processing an image of at least a part of the blood vessel containing said calcification, which method comprises: taking a starting set of digital data representative of an image of at least part of a blood vessel containing an area of calcification, said area of calcification being set against a background area;

(1 ) estimating a boundary of the area of calcification;

(2) inpainting the area of calcification within the estimated boundary using information from the remainder of the background area; (3) computing the difference between the starting set of digital data and the inpainted set of digital data to obtain a result representative of the degree of disocclusion of the background region; (4) moving the position of the estimated boundary to produce a further generation estimated boundary;

(5) inpainting the area within the further generation estimated boundary; and

(6) computing the difference between the starting set of digital data and the inpainted set of digital data; continuing iterations of steps (4), (5) and (6) until a maximum degree of disocclusion is obtained, using information of the boundary of the calcification at the time of the maximum degree of disocclusion to compute the shape and size of the calcification.

10. A method of reconstructing the background of an image having an area of interest in the foreground, comprising: taking a starting set of digital data representative of the image; (1 ) estimating a boundary of the area of interest of the foreground;

(2) _. inpainting the area of interest within the boundary using information from the remainder of the background region;

(5) inpainting the area within the further generation estimated boundary; and

(6) computing the difference between the starting set of digital data and the inpainted set of digital data; continuing iterations of steps (4), (5) and (6) until a maximum degree of disocclusion is obtained.