NONPARAMETRIC STATISTICAL LEVEL SET SNAKE BASED ON
THE MINIMIZATION OF THE STOCHASTIC COMPLEXITY
P. Martin
1,2
, Ph. R
´
efr
´
egier
1
, F. Galland
1
,F.Gu
´
erault
2
1
Physics and Image Processing group, Fresnel Institute, UMR CNRSTIC 6133
Universit
´
e Paul C
´
esanne Aix-Marseille III, EGIM 13397 Marseille France.
2
Simag D
´
eveloppement, 2 all
´
ee Sacoman 13016 Marseille France.
Keywords:
Segmentation, Level-set, Minimum Description Length principle, Statistical Estimation.
Abstract:
In this paper, we focus on the segmentation of objects not necessarily simply connected using level set snakes
and we present a nonparametric statistical approach based on the minimization of the stochastic complexity
(Minimum Description Length principle). This approach allows one to get a criterion to optimize with no free
parameter to be tuned by the user. We thus propose to estimate the probability law of the gray levels of the
object and the background of the image with a step function whose order is automatically determinated. We
show that coupling the probability law estimation and the segmentation steps leads to good results on various
types of images. We illustrate the robustness of the proposed nonparametric statistical snake on different
examples and we show on synthetic images that the segmentation results are equivalent to those obtained with
a parametric statistical technique, although the technique is non parametric and without ad hoc parameter in
the optimized criterion.
1 INTRODUCTION
An important goal of computational vision and im-
age processing is to automatically recover the shape
of objects from various types of images. The first
snakes (Kass et al., 1988) were driven by the mini-
mization of a function in order to move them towards
desired features, usually edges. They are well adapted
to a certain class of problems, but they can fail in the
presence of strong noise although several improve-
ments and reformulations have been proposed to over-
come these limitations. An other strategy consists
in considering not only the edges, but also the in-
ner and the outer regions defined by the active con-
tour (Leclerc, 1989; Ronfard, 1994). Different statis-
tical region-based formulations have been proposed
in (Figueiredo and Leit
˜
ao, 1992; Storvik, 1994) and
some of their advantages have been illustrated in (Jain
et al., 1996; Germain and R
´
efr
´
egier, 1996).
Concerning the region approaches, the contour is
deformed in order to minimize a criterion which is the
sum of two terms : the external energy which is based
on the gray levels of the image and on a statistical
model, and the internal energy which allows one to
regularize the contour. It has been shown (Figueiredo
et al., 2000; Ruch and R
´
efr
´
egier, 2001; Martin et al.,
2004) that one can determine the external energy for a
given probability density function (pdf) model and the
complexity of the contour model with the minimum
stochastic complexity (Rissanen, 1989) approach.
Nevertheless, even if the pdf models (which belong
to the exponential familly) proposed in (Chesnaud
et al., 1999; Ruch and R
´
efr
´
egier, 2001; Martin et al.,
2004) allow one to deal with many aplications (radar
images, low photon flux, ...), the user may not know
the physical origin of the image. More important,
some pdf can not be easily described by a parametric
pdf model. To overcome these limitations, the authors
propose in (Kim et al., 2002) a nonparametric statis-
tical approach by estimating the pdf with the Parzen
window (Parzen, 1962) method. However, the width
σ
P
of the Gaussian kernel needs to be tuned in this
approach. If σ
P
is too small, the histogram estima-
tion could be noisy and if σ
P
is too large, it could be
too smooth.
We thus propose to simultaneously segment the im-
age with a level set snake and estimate the pdf of the
object and the background with a step function whose
order is automatically determined.
463
Martin P., Réfrégier P., Galland F. and Guérault F. (2006).
NONPARAMETRIC STATISTICAL LEVEL SET SNAKE BASED ON THE MINIMIZATION OF THE STOCHASTIC COMPLEXITY.
In Proceedings of the First International Conference on Computer Vision Theory and Applications, pages 463-467
DOI: 10.5220/0001363204630467
Copyright
c
SciTePress
2 MINIMUM STOCHASTIC
COMPLEXITY APPROACH
2.1 General Model
Our purpose is to segment an image s =
{s(x, y)|(x, y) ∈ [1,N
x
] × [1,N
y
]} with N
x
× N
y
pixels, assumed to have been quantized in Q lev-
els such as s ∈ [1,Q] with Q ∈ N (for example,
Q = 256) and composed of two regions Ω
t
and Ω
b
(not necessarily simply connected) denominated the
target and the background regions. The target’s gray
levels t (with N
t
pixels) and the background gray lev-
els b (with N
b
pixels) are assumed to be spatially
uncorrelated and independently distributed (bold font
symbols will denote vectors). Furthermore, their re-
spective pdf will be noted P
t
and P
b
.
With statistical region-based snakes, the criterion
which has to be optmized in order to obtain the final
contour Γ can be determined by minimizing the sto-
chastic complexity of the image (Minimum Descrip-
tion Length principle) (Figueiredo et al., 2000; Ruch
and R
´
efr
´
egier, 2001; Martin et al., 2004). In that case,
one has to determine the sum of the number of bits
needed for the description of the data with an appro-
priate dictionary and of the number of bits needed to
describe the dictionary (Rissanen, 1989). For snake
segmentation, considering the image s and a contour
Γ, the stochastic complexity is the sum of 3 terms
∆(s, Γ,P
t
,P
b
)=∆
S
(s, Γ,P
t
,P
b
)
+∆
P
(Γ,P
t
,P
b
)+∆
C
(Γ),
(1)
where ∆
S
(s, Γ,P
t
,P
b
) is the number of bits needed
fog the description of the gray levels of the image s
with a given contour Γ and a given dictionary for cod-
ing the gray levels, ∆
P
(Γ,P
t
,P
b
) is the number of
bits needed to code the dictionary and ∆
C
(Γ) is the
number of bits needed to describe the contour Γ.In
the following, the number of bits will be measured in
nats, or in other words, the natural logarithm will be
considered (1bit = log(2)nats).
2.2 Determination of the Stochastic
Complexity and Estimation of
the PDF
Our goal is to estimate the contour Γ assuming the
pdf of the object and the background gray levels are
nuisance parameters. We thus propose to demonstrate
that a simple pdf estimation technique can lead to ef-
ficient results for the estimation of Γ. Let us consider
the estimation of the pdf in each region Ω
t
and Ω
b
with an irregular step function
P
u
q
(s) (u = t, b)of
order q defined as follow
P
u
q
(s)=
q
j=1
p
u
(j)R
j
(s), (2)
with u = {t, b} , R
j
(s)=1if s ∈ [a
j
,a
j+1
[ and
R
j
(s)=0otherwise where a
j
∈ [1,Q], a
j
>a
i
if
j>i, a
q +1
= Q +1and a
1
=1. The step function is
irregular since the different steps are not necessarily
of equal length.
The Maximum Likelihood estimated of p
u
(j) is
p
u
(j)=
N
u
(j)
b
j
Nu
where b
j
= a
j+1
− a
j
, N
u
is the
number of pixels in Ω
u
and N
u
(j) is the number of
pixels in Ω
u
such as s ∈ [a
j
,a
j+1
[. One can show
that, for
P
u
q
=
q
j=1
p
u
(j)R
j
(s) and Γ given, the
number of nats needed to code the gray levels of s is
given by
∆
S
(s, Γ,
P
t
q
,
P
b
q
)=−
u∈{t,b}
q
j=1
N
u
(j)log
N
u
(j)
b
j
N
u
.
(3)
The number of nats required to code the dictionary
for the gray levels can be approximated by
∆
P
(Γ, P
t
q
, P
b
q
)=−
u
q
j=1
log
N
u
(j)
N
u
+
q
j=1
log(1 + b
j
).
(4)
In the following the contour will be described with
a level set snake which allows one to segment ob-
jects not necessarily simply connected. It has been
shown (Martin et al., 2004) that in that case, the num-
ber of nats needed to code the contour can be ap-
proximated by ∆
LS
C
(Γ) = log(8)|Γ|, where |Γ| is the
length in pixel units of the contour. These expresions
of ∆
S
(s, Γ,
P
t
q
,
P
b
q
), ∆
P
(Γ,
P
t
q
,
P
b
q
) and of ∆
LS
C
(Γ)
allow one to obtain ∆(s, Γ,P
t
q
,P
b
q
) (see eq. 1) which
is the free parameter criterion to minimize in order to
get the level set snake convergence.
The contour Γ, the order q of the step function, the
values of a
j
and p
u
(j) are estimated by minimizing
the stochastic complexity ∆(s, Γ,P
t
,P
b
). More pre-
cisely, a first segmentation (i.e. estimation of Γ)is
performed with q = Q which corresponds to a
j
= j.
Then, the adjacent steps R
j
(s) and R
j+1
(s) whose
fusion leads to the largest decrease of the stochastic
complexity criterion are merged and Γ is again de-
formed to optimize the stochastic complexity crite-
rion. The optimal estimation of q and of the a
j
cor-
respond to the values which minimize the stochastic
complexity. This criterion thus does not include any
free parameter.
VISAPP 2006 - IMAGE ANALYSIS
464
(a) (b) (c) (d) (e)
Figure 1: (a) Synthetic image without noise (72 × 96 pixels) with initial contour. (b) Noisy version of image (a), pdf of the
background and object gray levels are shown in Fig. 2. (d) Noisy version of image (a), gray levels of the object region are
distributed with a Gaussian pdf and gray levels of the background have a bi-valuated pdf with the same mean and variance
values as those of the object region. (c), (e) Final contour respectively obtained on image (b) and (d) with the proposed
approach.
3 EXPERIMENTAL RESULTS
We show in Fig.1c a result of segmentation on an im-
age quantized with Q = 256 levels. The noisy image
in Fig.1b has been generated with a step function of
order q =4for the pdf models of the object and the
background. One can see the histograms in Fig.2a and
Fig. 2b in solid line. The minimum value of the sto-
chastic complexity is obtained for q =4(Fig.2a and
Fig.2b in dotted line) which corresponds to the true
value. In Fig.1e, we show the segmentation result on
an image with a Gaussian noise on the object region
and a bi-valuated noise on the background region cho-
sen in order to get the same mean and variance values
in both regions.
An example of application of this approach to a
RGB image is shown in Fig.3a. The final contour Γ is
obtained on the saturation component S in HSV rep-
resentation. One can see in Fig.3c the final contour
on a real SAR image corrupted with speckle noise. In
Fig. 4, one can see a segmentation result on a textured
image. In order to get homogeneous regions, the im-
age s has been preprocessed to obtain the new image
f defined by f (x, y)=F ∗ s(x, y) where F is the
Roberts filter (Jain, 1989) defined with 3 × 3 pixel
neighborhoods and ∗ is the convolution operator.
4 ROBUSTNESS OF THE
PROPOSED TECHNIQUE
Let us analyse in this section the efficiency of the pro-
posed nonparametric approach pdf estimation based
on irregular step functions. For that purpose, we com-
pare the results obtained either with this approach or
with a parametric modelization of the actual pdf of the
background and object gray levels which will be dis-
tributed with a pdf which belongs to the exponential
familly (Martin et al., 2004).
The results shown in Fig.5 demonstrate that the
proposed approach leads to segmentation results
equivalent to those obtained with a parametric model
for the pdf which is adapted to the noise which
describe the gray level fluctuations. On the other
hand, if an inadapted parametric model is used for
the pdf, one can see that poor results can be ob-
tained. It has been shown (Goudail et al., 2003) for
polygonal (Ruch and R
´
efr
´
egier, 2001) and level set
snakes (Martin et al., 2004) that the Bhattacharyya
distance (Cover and Thomas, 1991), defined by B =
− log
P
t
(z)P
b
(z)dz, is an appropriate measure
of contrast between the target and the background.
We have thus determined the average number of
misclassified pixels (ANMP) obtained as a function
of B on the images described in Fig.5 for the pre-
vious discussed parametric and nonparametric ap-
proaches. The number of misclassified pixels is de-
termined from the final contour by counting the pixels
which belong to the true target shape but lie outside
the contour, and those which belong to the true back-
ground but lie inside the contour. Both approaches
lead to equivalent ANMP (with a precision lower than
1.7%) when B≥0.29. The parametric statistical ap-
proach leads to lower ANMP than the proposed non-
parametric statistical technique only when B < 0.29.
5 CONCLUSION
We have proposed a nonparametric statistical level
set snake based on the minimization of the stochas-
tic complexity. We have demonstrated that this ap-
proach leads to good segmentation results when the
pdf of the object and the background are approxi-
mated by a step function whose values and order are
estimated. This approach leads to minimize a crite-
rion without free parameter to be tuned by the user.
We have seen that this technique provides good results
on SAR, video (color) and textured images. More-
over, we have shown that the segmentation results of
the proposed approach are closed to those obtained
with a parametric statistical approach but with a bet-
ter robustness.
There exists different perspectives to this work. It
will be interesting to generalize this technique to a
multi region approach and to take into account possi-
ble spatial correlations.
NONPARAMETRIC STATISTICAL LEVEL SET SNAKE BASED ON THE MINIMIZATION OF THE STOCHASTIC
COMPLEXITY
465
REFERENCES
Chesnaud, C., R
´
efr
´
egier, P., and Boulet, V. (1999). Statisti-
cal region snake-based segmentation adapted to differ-
ent physical noise models. IEEE Trans. Pattern Anal.
and Machine Intell., 21(11):1145–1157.
Cover, T. M. and Thomas, J. A. (1991). Elements of Infor-
mation Theory. Wiley-interscience, New York.
Figueiredo, M. and Leit
˜
ao, J. (1992). Bayesian estimation
of ventricular contours in angiographic images. IEEE
Trans. Medical Imaging, 11.
Figueiredo, M., Leit
˜
ao, J., and Jain, A. K. (2000). Unsu-
pervised contour representation and estimation using
B-splines and a minimum description length criterion.
IEEE Trans. Image Processing, 9:1075–1087.
Germain, O. and R
´
efr
´
egier, P. (1996). Optimal snake-based
segmentation of a random luminance target on a spa-
tially disjoint background. Opt. Lett., 21(22):1845–
1847.
Goudail, F., R
´
efr
´
egier, P., and Ruch, O. (2003). Definition
of a signal-to-noise ratio for object segmentation us-
ing polygonal mdl-based statistical snakes. In Energy
Minimization Methods in Computer Vision and Pat-
tern Recognition, pages 373–388. Springer.
Jain, A. K. (1989). Fundamentals of digital image process-
ing. Prentice Hall information and system sciences
serie, New Jersey.
Jain, A. K., Zhong, Y., and Lakshmanan, S. (1996). Ob-
ject matching using deformable template. IEEE Trans.
Pattern Anal. and machine intell., 18:268–278.
Kass, M., Witkin, A., and Terzopoulos, D. (1988). Snakes:
Active contour models. International Journal of Com-
puter Vision, 1:321–331.
Kim, J., Fisher, J., Yezzi, A., Cetin, M., and Willsky, A.
(2002). Nonparametric methods for image segmenta-
tion using information theory and curve evolution. In
IEEE Int. Conf. on Image Processing, volume 3, pages
797–800. Rochester, N.Y.
Leclerc, Y. (1989). Constructing simple stable descriptions
for image partitionning. Computer Vision, 3:73–102.
Martin, P., R
´
efr
´
egier, P., Goudail, F., and Gu
´
erault, F.
(2004). Influence of the noise model on level set ac-
tive contour segmentation. IEEE Trans. Pattern Anal.
and Machine Intell., 26:799–803.
Parzen, E. (1962). On estimation of a probability density
function and mode. Annals Mathematical Statistics,
33:1065–1076.
Rissanen, J. (1989). Stochastic Complexity in Statistical In-
quiry. World Scientific, Singapore.
Ronfard, R. (1994). Region-based strategies for active con-
tour models. International Journal of Computer Vi-
sion, 2(13):229–251.
Ruch, O. and R
´
efr
´
egier, P. (2001). Minimal-complexity seg-
mentation with a polygonal snake adapted to different
optical noise models. Opt. Lett., 26(13):977–979.
Storvik, G. (1994). A Bayesian approach to dynamic con-
tours through stochastic sampling and simulated an-
nealing. IEEE Trans. Pattern Anal. Machine Intell.,
16(10):976–986.
VISAPP 2006 - IMAGE ANALYSIS
466
0
0.004
0.008
0.012
0 50 100 150 200 25
0
FREQUENCY
OBJECT
STEP FUNCTION (q=4)
NUMBER OF BINS
HISTOGRAM (256 BINS)
0
0.002
0.004
0.006
0.008
0 50 100 150 200 25
0
FREQUENCY
STEP FUNCTION (q=4)
BACKGROUND
NUMBER OF BINS
HISTOGRAM (256 BINS)
(a) (b)
Figure 2: (a), (b) Histograms (solid line) and estimated pdf (dotted line) of the object and the background of Fig.1b.
(a) (b) (c)
Figure 3: (a) RGB image acquired with a CCD camera (231 × 228 pixels) with the initial contour. (b) Segmentation result
obtained on the saturation component S in HSV representation with the proposed approach. (c) Segmentation result obtained
on a SAR image (97 × 127 pixels) of an agricultural area obtained by the ERS-1 satellite (distributed by the ESA and provided
by the CNES). A multi-initialization analogous to the one of Fig.3a has been used.
(a) (b) (c) (d)
Figure 4: Segmentation of an image (73 × 69 pixels) acquired with a CCD camera. (a) Segmentation result with a Gaussian
model for the pdf. Results of the segmentation on a preprocessed version of (a) obtained with different models for the pdf :
(b) Gaussian, (c) Gamma, (d) the proposed approach. A multi-initialization has been used.
(a) (b) (c) (d)
Figure 5: (a) Synthetic images (72 × 96 pixels) perturbated with Gaussian (first line) and Gamma (second line) noises with
B =0.29. Segmentation results obtained with a Gaussian and Gamma models for the pdf (Martin et al., 2004) and the
proposed approach are shown respectively in (b), (c) and (d). The initial contour is the one of Fig.1.
NONPARAMETRIC STATISTICAL LEVEL SET SNAKE BASED ON THE MINIMIZATION OF THE STOCHASTIC
COMPLEXITY
467
