Image Processing Reference
In-Depth Information
K-means Algorithm:
Given M training vectors
{
X
1
X
2
...
X
M
}
, we need to
find the L reconstruction vectors
{
r
1
r
2
...
r
L
}
and their corresponding regions
{
D
1
D
2
cation problem that can be solved iteratively
by K-means algorithm. Following is a summary of the K-means algorithm:
...
D
L
}
. This is a classi
1. Initialization: Start with an initial estimate of reconstruction vectors ri
i
for
i
¼
, L. They can be picked randomly or we can pick L vectors from
the training data set.
2. Classification: Classify the M training vectors into L groups.
Vector
1, 2,
...
X
belongs to Di,
i
,
if and only if
k
X
r
i
k< k
X
r
j
k
, or all
1
j
L,
where
stands for Euclidean norm.
3. Total distortion: Compute the overall average distortion
D
¼
kk
M
P
i
¼
1
k
X
i
X
i
k
where X
i
¼
r
k
if Xi
i
is in cell D
k
.
4. If the average distortion is small (less than a prescribed threshold), stop the
iteration. Otherwise, continue to the next step.
5. Centroid: Find a new estimate of the reconstruction vector ri
i
by computing
the centroid of the ith cell Di
i
1
and go to step 2. The centroid of Di
i
is
K
i
P
(all vectors in
D
i
)
1
computed by r
i
¼
, where K
i
is the number of
vectors in cell Di.
i
.
Example 2.7
Given the
five training vectors:
2
4
3
5
,
2
4
3
5
,
2
4
3
5
,
2
4
3
5
2
4
3
5
1
1
2
0
2
2
1
0
2
2
X
1
¼
2
2
X
2
¼
X
3
¼
X
4
¼
and X
5
¼
2
0
2
design a 1 bit vector quantizer using K-means algorithm.
S
OLUTION
For a 1 bit quantizer L ¼
2 and there are two reconstruction vectors. Let the initial
2
4
3
5
and r
2
¼
2
4
3
5
.
1
1
2
vectors be r
1
¼
2
2
2
kX
1
r
1
k¼
0,
kX
1
r
2
k¼
5
:
656
! X
1
2 D
1
kX
2
r
1
k¼
5
:
656,
kX
2
r
2
k¼
0
! X
2
2 D
2
kX
3
r
1
k¼
4
:
123,
kX
3
r
2
k¼
4
:
123
! X
3
2 D
1
kX
4
r
1
k¼
2,
kX
4
r
2
k¼
4
:
472
! X
4
2 D
1
kX
5
r
1
k¼
3
:
605,
kX
5
r
2
k¼
5
:
385
! X
5
2 D
1
Search WWH ::
Custom Search