3
1.3 Real-Time Applications
The algorithm described in this paper was developed keep-
ing in mind the need for real-time operation, having image
segmentation for robots as our first objective. Due to the
large resolution of modern frame grabbers and cameras, im-
age segmentation requires fast techniques in order to satisfy
the real-time demands of robotic applications, ranging from
simple tracking to autonomous vehicle guidance and video
surveillance. Since there are no efficient global solutions to
the general problem of unsupervised estimation of mixture
models, we have developed a greedy approach where the
design choices are taken to specifically address the image
segmentation problem achieving simultaneously fast perfor-
mance and results competitive with the state-of-the-art. For
evaluation purposes, we also perform experiments on 2D
synthetic data, where the method’s performance can be more
easily visualized and compared. However, we stress that the
main aspect considered in writing the algorithm’s specifica-
tion is a fast performance in image segmentation. Several
results on this domain, both with generic images and with
images taken in our robotic platform, are presented and com-
pared with the state-of-the-art.
1.4 Outline
The paper is organized as follows. In sec. 2 we summarize
the main results of the classical Expectation Maximization
algorithm. In sec. 3 we introduce the proposed algorithm.
Specifically, we describe its formulation in sec. 3.1, the ini-
tialization in sec. 3.2, the component split operation in sec.
3.4, and the decision thresholds update rules in sec. 3.5. Fur-
thermore, in sec. 5 we describe our experimental set-up for
testing the validity of our new technique and in sec. 6 we
discuss our results. Finally, in sec. 7 we draw the main con-
clusions of this work.
2 Expectation Maximization Algorithm
The Expectation-Maximization algorithm serves to find the
maximum likelihood estimates of a probabilistic model with
unobserved data. A common usage of the EM algorithm is
to identify the ”incomplete, or unobserved data”:
Y =
¯y
1
, ¯y
2
, . . . , ¯y
j
(1)
given the couple (X , Y ) - with X defined as:
X = { ¯x
1
, ¯x
2
, . . . , ¯x
N
}
(2)
also called ”complete data”, which has a probability density
(or joint distribution) p
X , Y |
¯
ϑ
= p
¯
ϑ
(X , Y ) depending
on the parameter
¯
ϑ
. More specifically, the ”complete data”
are the given input data set X to be classified, while the
”incomplete data” are a series of auxiliary variables in the
set Y indicating for each input sample which mixture com-
ponent it comes from. We define E
′
(·) the expected value
of a random variable, computed with respect to the density
p
¯
ϑ
(X , Y ).
We define:
Q
¯
ϑ
(n)
,
¯
ϑ
(n−1)
= E
′
L
¯
ϑ
(n−1)
(3)
with L
¯
ϑ
(n−1)
being the log-likelihood of the observed
data at step n− 1:
L
¯
ϑ
(n−1)
= log p
X , Y |
¯
ϑ
(n−1)
(4)
The EM procedure repeats the two following steps until
convergence, iteratively:
– E-step: It computes the expectation of the joint probabil-
ity density:
Q
¯
ϑ
(n)
,
¯
ϑ
(n−1)
= E
′
h
log p
X , Y |
¯
ϑ
(n−1)
i
(5)
– M-step: It evaluates the new parameters that maximize
Q; this, according to the ML estimation, is:
¯
ϑ
n
= argmax
¯
ϑ
Q
¯
ϑ
n
,
¯
ϑ
(n−1)
(6)
The convergence to a local maxima is guaranteed. How-
ever, the obtained parameter estimates, and therefore, the ac-
curacy of the method greatly depend on the initial parame-
ters
¯
ϑ
0
.
2.1 EM Algorithm: Application to a gaussians Mixture
When applied to a gaussian mixture density we assume the
following model:
p( ¯x) =
nc
∑
c=1
w
c
· p
c
( ¯x)
p
c
( ¯x) =
1
(2
π
)
d
2
|
Σ
c
|
1
2
e
−
1
2
( ¯x−
¯
µ
c
)
T
|
Σ
c
|
−1
( ¯x−
¯
µ
c
)
(7)
where p
c
( ¯x) is the component prior distribution for the class
c, and with d,
¯
µ
c
and
Σ
c
being the input dimension, the mean
and covariance matrix of the gaussians component c, and nc
the total number of components, respectively.
Let us consider nc classesC
nc
, with p( ¯x|C
c
) = p
c
( ¯x) and
P(C
c
) = w
c
being the density and the a-priori probability of
the data of the class C
c
, respectively. Then:
p( ¯x) =
nc
∑
c=1
P(C
c
) · p( ¯x|C
c
) =
nc
∑
c=1
w
c
· p
c
( ¯x)
(8)