to a geometric primitive anc. thus the position of points in
isolation.
Jolion's algorithm is also “context-insensitive’, unlike
Krishnapuram and Munshi's (1991) and Hoffman and Jain's
(1987) algorithms. These algorithms require the input of a
maximum number of point groups to be formed in the feature
space, and thus exhibit the paradox of requiring knowledge
about the data set in order to interpret it (Quek et. al. 1993).
Jolion's algorithm dynamically selects the appropriate number
of point groups in a data driven process.
Jolion's algorithm makes direct use of uniformity indicators
without having to threshold them (i.e. map computed values
to -1, 0, or +1), as is required for Besl and Jain’s (1988)
algorithm. Abdelmalek (1990) and Krishnapuram and Munshi
(1991) note the difficulty associated with selecting appropriate
thresholds for the re-scaling of curvature values.
In addition to using uniformity indicators directly, Jolion’s
algorithm makes use of the entire data set when producing its
decompositions. Errors in the data set do not have significant
effects on the results of the segmentation. Other techniques,
such as region growing and boundary identification
(Krishnapuram and Munshi 1991) or selecting only a small
subset of ‘significant’ data points, may lead to spurious
segmentation of the data.
Jolion et. al (1991) have taken an ‘intelligent’ approach to the
target point grouping. The algorithm identifies a portion of the
feature space that will produce the most significant cluster, to
be refined in a ‘brute force’ process limited to only a portion
of the data set. Krishnapuram and Munshi’s (1991) algorithm
requires multiple clustering’s of the entire data set, from which
the best segmentation is selected. This ‘brute force’ approach
to clustering results in a slow and computational inefficient
algorithm (Krishnapuram and Munshi 1991).
As indicated earlier the point groups returned from an analysis
of the selected uniformity indicators may contain points from
more than one surface of the same type. Therefore, a proximity
measure must be used to split disjoint surfaces that have been
grouped together. To evaluate the proximity of the points, the
separation of all points in a group can be computed with
respect to one point in the group and in a given direction
(Figure 2). The separations from the common point of all
points on the same surface will be similar (Figure 2,
separations in range D; — D»). Points on the surface with the
same or opposite orientation will have distinctly different
separations from the common point (Figure 2, separations in
range D; — D,) The means of these two ranges will be
significantly different (Figure 2, D,; - D,2), indicating that
two point groups are not in close proximity. In a majority of
cases, the evaluation of point proximity's will separate points
on surfaces with the same or opposite orientations. However,
the algorithm can not successfully discriminate between points
on surfaces if they are parallel and close together, or when the
surfaces are duplicated next to each other, as there is no
significant difference in the separations of the points.
The descriptions of the point groups created by Jolion's
algorithm are to be produced using a modified version of
Newman's et. al. (1993) algorithm. The simplicity of this
algorithm, its compatibility with Jolion's algorithm and the
ease with which it can be modified were significant in its
8
selection as the classification algorithm. The details of this
selection process and the evaluation of this algorithm are
beyond the scope of this paper.
// >
: I ci
C r* Direction in
ommo which the
point from separations
which *
; of point are
separations to be
are
measured. .
measured.
Figure 2. Separation of points for the evaluation of data point
proximity.
2.4 Pre-processing Of Target Field Data Sets.
Target fields to be decomposed using the selected
segmentation algorithm require pre-processing before the point
grouping can be undertaken. The uniformity indicators upon
which the point grouping is to be based are computed from the
local continuous approximation:
w(u,v) = C; u° + C; uv - C4 V * Cau* C5 v * C,
to the discrete data set of target points. For a majority of cases
the surface features can be computed directly from the
continuous approximation, however, in the case of points that
belong to more than one surface, this is not possible. Direct
computation of the surface features from the local continuous
approximation would retum a single set of uniformity
indicators. If the point lies on more than one surface i.e. an
edge point, then one complete set of indicators is required for
each surface on which the point lies. Figure 3 shows this
concept for surface normals at an edge point. Points requiring
multiple surface features of each type could be dealt with by
creating *dummy points. The surface features of each these
‘dummy’ points relate to the different surface on which the
point lies.
N2
m N; 1 Surf. 1.
= ——P Ni N» .L Surf. 2.
Ns y” Surf. 1. N; 1 Surf. 3.
p
=
Surf. 3.
Figure 3. Edge point with multiple valid uniformity
indicators.
Points requiring ‘dummy’ points could be identified by
examining the uniformity indicators computed at each point
without regard for points being edge points or otherwise, i.e.
only one set of indicators for each point. In particular the
curvature measures could be analysed to find those points that
have curvatures greater than might reasonably be expected at
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B5. Vienna 1996
points lying «
on a sharp ed
3. COME
P]
3.1 Nature C
The algorithn
to computer -
of difficulties
These were d
sets and the c
Computer vi
portion of tl
target field d.
object. These
processing st
It was intend
information
dimensional
Krishnapurar
detailed bek
strategy bein;
3.2 Edge Poi
Edge points i
regardless of
the continua
identification
operators (Fa
edge points o
removed by ı
No simple an
points in the
could be com
isolation. A
curvatures ri
Furthermore,
Therefore,
identification
to be inappro;
The contami
computed at
removed. Ins
knowledge t
contaminatin
as isolated p
‘regular’ sur
consistent w
significantly |
3.3 Approxin
The initial a.
approximatin,
(1988):
w(u,v) :
