Multigrid Computation for
Variational Image Segmentation Problems:
Euler equations and approximation
 Rosa
Maria Spitaleri
Istituto per le Applicazioni del Calcolo-CNR
Viale del Policlinico 137, 00161 Rome, Italy
e-mail: [email protected]
Advances in Numerical Algorithms Graz, September 10-13, 2003
Istituto per le Applicazioni del Calcolo "M. Picone"
Variational Image Segmentation
and Computational Approach
 minimization
of the Mumford-Shah functional
 definition of a sequence of -convergent functionals
 solution of associated Euler equations
 finite difference approximation
 nonlinear system solution
 multigrid computation
 geometric and synthetic images
 visualization : computed solution (reconstructed
image and edge ), convergence histories
Istituto per le Applicazioni del Calcolo "M. Picone"
Segmentation Problem
decomposition of the domain 
of a function f(x,y)
(computer vision )
 appropriate

f(x,y) is the strength of the light signal
striking a plane domain  at the point with
coordinates (x, y)
 the
function f(x,y) is called image
Istituto per le Applicazioni del Calcolo "M. Picone"
Discontinuity Causes
reflected off surfaces S i of solid objects O i ,
seen from P , the camera or eye point, will strike the
domain  (retina or film) in various open subsets R i
which could have common boundaries (“edges” of the
objects in foreground),
 light

surfaces with different orientation (“edges” of a cube),
 discontinuity
 textured,
in illumination (shadows),
partially transparent, highly-reflecting objects, ...
Istituto per le Applicazioni del Calcolo "M. Picone"
 the
segmentation problem consists in computing a
decomposition of 
D  R ... R
1
n
such that
 the image f(x,y) varies smoothly and/or slowly
within each R i
 the image f(x,y) varies discontinuously and /or
rapidly across most of the boundary between
different R i
optimal approximations of f(x,y) by
piece-wise smooth functions u(x,y )
(restrictions ui to the pieces R i differentiables)
 computing
Istituto per le Applicazioni del Calcolo "M. Picone"
Mumford-Shah Functional
 Given
the image f(x,y) let u be a real
function defined on a domain  and
(u)
(u)
D  {R , ..., R } a decomposition of 
1
n
n
(u)

R i  Su ,
such that
where S u 
and
n
i 1
i 1
(u)

i
(u)
(u)
the boundary of R i
i
Istituto per le Applicazioni del Calcolo "M. Picone"
MSF Definition
 the
MSF is defined in the following form:
E(u)   (u - f ) dxdy 
2

 
/S
u
2
1
dxdy   H
(Su )
u
2
 (u/ x)  (u/ y)
u) the Hausdorff measure of Su
 ,   0 assigned parameters.
where
H1 (S
u
Istituto per le Applicazioni del Calcolo "M. Picone"
2
2
,
,
MSF Minimization

approximation of f(x,y)


(u - f)2 dxdy
(u)
u smooth on each R i


by u
/Su u
the boundary
possible
2
dxdy
S
u
H1 (Su)
Istituto per le Applicazioni del Calcolo "M. Picone"

n
i 1
(u)

i
as short as
Parameters

 ,   0 can be calibrated to eliminate
“false edges” , created by noise, and save the actual
image;


is a scaling parameter,

controls the noise
effects;

2

defines the threshold to detect the edge
Istituto per le Applicazioni del Calcolo "M. Picone"
Interest and Expectation
any of the three terms inf E = 0 :
u  0, S   ,
s without the first:
u
s without the second: u  f, S   ,
u
 droping
s without the third: u  mean
Ri
f ,S
u
 N  N grid,
D  N 2 small squares

(u,Su ) is a cartoon of the actual image f(x,y) :
s a new image in which the edges are drawn sharply and
precisely and the objects are drawn smoothly without
texture,
s idealization of a complicated image, representing
essentially the same scene
Istituto per le Applicazioni del Calcolo "M. Picone"
Variational Convergence
problem of minimizing E has been conjectured to
be well posed (open problem),
 these functionals have minimizers in the spaces of
Special functions of Bounded Variation (SBV),
 the minimization problem is difficult for the presence of
the set of discontinuity contours Su as unknown
 variational convergence to solve minimization of
functional depending on discontinuities:
– approximation of a variational problem by a sequence
of more tractable problems
 the
Istituto per le Applicazioni del Calcolo "M. Picone"
-Convergence
k
sequence of functionals {F (u)} on a metric
space U is -convergent to the functional F(u)
if,  u0  U :
(i)  sequence {uk} converging to u0
 the
k
lim inf F (uk )  F(u0 )
k
(ii)
 a sequence {uk} converging to u0 such
that
k
lim sup F (uk )  F(u0 )
k
Istituto per le Applicazioni del Calcolo "M. Picone"
Properties
k
property- {F (u)} sequence of
functionals on U -convergent to F(u) k
*
-if a sequence {uk} of minimizers of {F (u)}
converges, then the limit is a minimizer of F(u)
and {Fk (u*k )} converges to the minimal value of
F(u) k the-convergence is a variational
convergence
 -convergence stability under continuous
perturbations- Let G be a continuous functional


k
k
F 

F F  G 

F G G
 variational
Istituto per le Applicazioni del Calcolo "M. Picone"
-Convergent Functionals
 sequence
k
E (u, z) 
of -convergent functionals
 (u - f)
2
dxdy 
2
z 2
k(1-z)
  z u dxdy    ( k
+ 4 )dxdy

2
or
2
E k (u, z)   (u - f)2 dxdy  Eˆ k (u,z)


k
 stability property: E 
 E
Istituto per le Applicazioni del Calcolo "M. Picone"
Discontinuity Curves by Control Function
function z(x,y ) controls the gradient of u
and has values ranging between 0 and 1,
*
 the minimizer z k
is close to 0 in a
neighbourhood of the set Su , which shrinks as
k   , and close to 1 in the continuity regions
*
 the gradient of u k thus is permitted to become
arbitrarily large along Su (jumps in the solution)
*
 the minimizers z k converge to a function equal
to 0 along Su and 1 everywhere else :
the -limit E(u) does not depend on z
 the
Istituto per le Applicazioni del Calcolo "M. Picone"
Euler Equations
 minimizers
of
E k (u, z) are the solutions of the
following coupled Euler equations
 (z 2u )   (z 2u )  1 (u  f )
x
y
x
y

2
2
z  k z u  k4 (1  z)
 Neumann
boundary conditions
 local minimum of the associated functional
 more accurate approximation as k increases
Istituto per le Applicazioni del Calcolo "M. Picone"
Finite Difference Approximation

the discretization of  with grid spacing h andthe
h
finite difference operator L a ( complete
c
approximation of u and z )


1
1
4 2 
4 2˜
1

z
u

z
u

z
z
u

z
u

f
x
x
y
y
2
2
2

 h
 h
2h
2
2

2
2
k

4
k

4
k
z
ux  uy  2  4  2 ˜z  4  0
2
4 h
 h
h


˜  1 4 w(x  h,y)  w(x  h,y )  w(x,y  h)  w(x,y  h)
w
wx  w(x  h,y)  w(x  h,y)
wy  w(x, y  h)  w(x,y  h)
where w = (u,z )
Istituto per le Applicazioni del Calcolo "M. Picone"
Solution Algorithm
systems on the grid G
and covering the domain  :
 equation
M
, with mesh size h
L w F
M
ac
M
M
( l  M , l is the grid level ) computation of
the solution
 onegrid
*
wk



0
RelaxM w k ,L a ,F
Istituto per le Applicazioni del Calcolo "M. Picone"
 Gauss-Seidel
relaxation
 rotated lexicographical ordering: a grid point x1 ,y 1 
precedes another point x 2 , y 2  if and only if
x1  x 2 or

x1  x 2, y1  y2
0
w k initial guess for GS-relaxation applied to each
k
system associated to the functional E (u, z) for a
fixed value of the index k
 observations:
 the discretization step of the finite difference method
should decrease as k increases
 optimal choice of the parameters  and  is a
delicate problem
Istituto per le Applicazioni del Calcolo "M. Picone"
Image Segmentation

f(x,y) a given image, and
Su  x, y   : zx, y   0
 geometrical
and realistic problems:
– one or more squares and circles, a vase
*
u
 computed results: smoothed image k and
*
z
control function k (discontinuity contours)
 convergence
histories: residuals, norms,
logarithm values, iteration numbers
 result visualization
Istituto per le Applicazioni del Calcolo "M. Picone"
Experimental Evaluation
 experimental
choice of the parameters:
  3. ,   0.05
 image
resolution:
64x64, 128x128, 256x256, 101x101
 brightness measurements : 256 levels
0
0
 initial guess: u k equal to the input image, z k
equal to 1 everywhere
 even “small” values of k can be used
Istituto per le Applicazioni del Calcolo "M. Picone"
k2
Lhac
Istituto per le Applicazioni del Calcolo "M. Picone"
k3
k5
h
Circle64x64 L a
c
log ( resz )
log(resu)
Istituto per le Applicazioni del Calcolo "M. Picone"
k and h link
Su discontinuity set, we can define
z(x,y)  ( (x, y)) in Bk  x,y :  (x, y)   k ,
where  (x,y) is the distance of (x, y) from Su and
 kt
 k (t)  1  e 2 (convergence in Bk )
2

5l,5l

l

z
(x,y
)
 k
between 1 and 0 in
,
k :
we have mh =10 l = 20/k where m is the node
number in this interval for a given h
 by p = hk we can control the “gap” approximation

Istituto per le Applicazioni del Calcolo "M. Picone"
Conclusion
 We
have defined a multigrid finite difference method
able to improve numerical solution of Euler equations
in variational image segmentation
 Application
to segmentation problems shows the
capabilities of the method in computing solutions and
providing satisfactory convergence histories
 Future
research deals with improving performances of
multigrid computation
Istituto per le Applicazioni del Calcolo "M. Picone"