graph is divided into inter and intra clusters based on the
computed global optimum edge length.
2. GENARALIZED CLUSTERING TECHNIQUE
Generalized clustering technique uses the concept of neighbors.
Each point in the data set has set of atleast two neighbors, but
practically four or five in two dimensional data. The neighbors
are selected using triangulation. The steps of proposed
clustering technique are:
1. The points of the data set are triangulated using
Delaunay triangulation (Roourke, 1994; Lee et al.,
1980).
2. The edges of the triangles are used to generate edge
graph. The neighbors of any point in the graph are the
points in its adjacency set.
3. Determine the closest neighbors by choosing cut-off
edge length say p. All the edges between neighbors
that are longer than p are removed from the graph.
With optimum choice of p, all the edges between
clusters would be removed and all the edges within a
single cluster shall be preserved. The function T(p)
gives a measure to compute the optimum p. For a
given p value T(p) is defined as follows ( Eldershaw
and Hegland, 1997).
Let X be the set of lengths of edges in the graph between the
clusters. Let Y be the set of lengths of those edges contained
within the same cluster.
Nx ny
T(p) 2 (x -ix)?/n. * E (ycuy)"/ny (1)
j=1 izl
Where
x; belongs to X,
y; belongs to Y,
Nx
= Zu Xi / Ny
i=1
Ny
wy=2Zyi/ ny,
i=1
and n, and n, are the number of edges in X and Y respectively.
The optimum p value can be calculated by minimizing the
function T(p).
3. IMPLEMENTATION
This technique is implemented in C language on SGI
workstation. This program takes ACSII file containing X and Y
coordinates of the point data and generates output ASCII file
that contains cluster identification number for each point. The
advantage is that the noise points are manifest as small clusters
having a few data points. In the software, a provision is
provided for the user to define noise level by giving the
minimum number of data points in a valid cluster. The second
component of this work is development of program to compute
the convex hull for each cluster. The convex hull program takes
single cluster points and computes the convex hull to envelop
the cluster points. In order to minimize the user interaction, a
script in korn shell is developed to automate the user
operations. The script includes other modules for (1) extracting
data points from binary image into ASCII coordinated and pipe
to the cluster program; (2) sorting of clustered points based on
IAPRS & SIS, Vol.34, Part 7, “Resource and Environmental Monitoring”, Hyderabad, India,2002
cluster number; (3) sequentially extracting each cluster points
and pipe to the convex hull program; (4) writing the resulted
clustered points and convex hull points in two files in Arc/info
GIS UNGENERATE format (ESRI, 1992).
4. EXPERIMENTS
The problem of spatial clustering of trees outside the notified
forest is considered to test and evaluate the proposed technique.
The random and discrete spatial distribution of trees outside the
forest offers an excellent domain to test and evaluate proposed
clustering technique. IRS-1C PAN, 512 rows and 512 columns
(approx. 1.572 sq. km) image is processed to generate the
binary image (figure.2) showing only trees outside the notified
forest. This area contains 38769 pixels representing trees and
their spatial distribution is non-continuous and discrete. This
data is processed using the developed software for different
values of 10, 50 and 100 as the minimum number of data points
in a valid cluster. The generated convex hulls of clusters are
shown in figures 3 to 5. The figure 6 shows magnified two
clusters with their numbers and convex hulls.
RE TE
i s E Fe
pn e
II
EN
Figure 2. Binary Image showing vegetation
representing trees out side forest.
t
B oxp + p
D $n U + mp + Fa Ya
RE d oF x? Nt jum SN ar + =
+ + + y + s
a 5 oF + p p^ S NS + >
V M. i»? E i
se SW «
o RATER "4
3 ©
> +
Y $
EA
Q ve S / Fee
EN
>
+
E -
Se T e I >
Yep, yt S
Cy + X DD DD to
% + t
+ ^ NP +
SR he Tr Y
Pone SIS
+ + % of
n DO
^) ee ;
w®
Figure 3. Convex hulls of clusters with number
of 10 trees points in a valid cluster.
(Total 304 clusters)
(^8
Pow qe + 74) Mu N VN
IX
Fi;
