![](bg3.png)
space, they would not attract each other unless they
are spatial neighbors.
Figure 2: Mapping of a pixel
(a) 3×3 pixels in special domain connected by 4-neighbor
(b) specially neiboring pixels in color space
Figure 3: Pixels in spatial domain and in color space
3.2 Gravitational clustering utilizing
neighbour relations
As stated above, those pixels close to each other in
color space are clustered only if they are connected
by neighbor relations, not like other measurement
space algorithms such as (Yung, 1998). The
algorithm is as follows:
Step 1. Let each pixel be a particle.
Initialize parameters such as merging distance
.
Step 2. Update neighbor relations altered by merged
particles
(Initially 8-neighbor).
Step 3. Compute gravitational force among
neighbors, move particles in color space according
to the gravitational force attraction.
Step 4. If the distance to a neighbor is less than
,
merge it with the neighbor.
Step 5. If there is no more merge or movement of
particles, then stop.
Otherwise, go to step 2.
The Markov model discussed in section 2.1 is used
in step 3. The resulting particles are clusters, and
pixels in each cluster belong to a segment.
3.2.1 The merging distance
The
can be determined in many ways; we
considered the distance histogram which
accumulates distances between a pixel and its
neighbors in color space. Pixels in a segment have
similar color value, making a high peak near
distance zero in the histogram. The first valley of the
histogram where the histogram value starts
increasing after the decrease from the high peak near
zero distance can be a candidate for the
value.
However, if
is too small, the image may be over-
segmented. Thus, we selected the first valley beyond
a distance of 10 from the zero peak that is
empirically obtained. In most cases, a value of 16
produced good results. As clustering proceeds, those
neighboring clusters having similar colors are
merged, and their centers are replaced by the center
of mass. Thus, the inter-cluster distances get bigger,
while intra-cluster distances get smaller. If
is
large, the color error given in equation (5) of section
4 becomes large as the center value does not
represent the pixel values in the segment accurately,
but it will produce a small number of segments. If a
small
is used, the image may be over-segmented
even if the error gets smaller.
3.2.2 Extent of gravitation effect
If the process of gravitational clustering is
continued, all the particles will be merged to form a
single cluster eventually. We need some provision to
prevent this and find optimal clusters. Various
methods taken by others are reviewed first.
Wright(Wright, 1977) applied the gravitational force
to all the data at all times. The clustering process
was actually continued until all the particles were
merged, and the time was measured between every
merge event and the next. The best clustering is
considered to be the clustered state just before the
longest time elapse until anothermerge event occurs.
This method has the disadvantage of long computing
time since the process must be continued until all the
particles are merged.
Yung and Lai(Yung, 1998) took a different approach.
They restricted the extent of gravitational force; they
called it “force effective field (FEF)”, conceptually
similar to the neighbor function of the SOFM neural
net(Kohonen, 1997). They decreased the extent of
FEF as the iteration proceeded.
Another possible method is to let the data space
expand like the Universe and find the equilibrium
state of contraction and expansion.
The approach taken in this paper is to restrict the
merge distance such that particles are merged only
when they are within a certain distance, and the
gravitational force is applied only to ‘neighboring’
particles in the spatial domain..
Figure 4 shows how the neighbor relation is updated
after a merge event. In the figure, p0….p6 are
particles (clusters) in the color space. The lines
represent neighbor relations and their lengths
represent the distances. Consider p0 for example.
The gravitational forces on p0 by p1,p2,p3 and p4
are computed; if p0 and p4 are merged together, new
neighbors of p0 are p1,p2,p3 and p5,p6 which were
ICINCO 2005 - SIGNAL PROCESSING, SYSTEMS MODELING AND CONTROL
272