The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008
In a supervised interpretation of the segmentation result, let X =
{*,: i=l ...n} be the set of n training objects, assumed polygons,
relative to which the segmentation is to be judged. Let Y = (y,:
j=l ...m) be the set of all segments in the segmentation. Let f, be
a subset of Y such that:
Yi = {yj: area(Xj Oyj^O}.
For convenience, let area(x, fl yj) = the area of the geographic
intersection of training object x, and segment yj and area(-) be the
geographic area of •. For each training object X;, the following
subsets of Y exist:
Y a = {all yj where the centroid of X; is in yj
Y b = {all yj where the centroid of yj is in x,}
Y c = {all yj where area(x, fl yj) / area (yj) > 0.5}
Y d = {all yj where area(x, fl yj) / area(x,) > 0.5}
The union of these subsets is the subset Yj* = Y a KJ Y b LJ Y c C7
Y d where Yj is assumed to be the subset of segments that are
relevant to training object Xj. Processing over Y* is designed to
minimize if not eliminate the effects of spurious intersections with
very small parts of very large segments. Define #( Yj*) = p\ and
/fy Pi = P. Thus, for each training object, there are p x segments
i=l...n
deemed relevant to it.
Define the following properties of the segments in Yj*:
OverSegmentation,, = 1 - area(x, fl yj) / area(x,).
UnderSegmentationij = 1 - area(x, D yj) / area(y 7 ).
Here, we have simply rescaled Moller et al. (2007) RAsub (as
OverSegmentation) and RAsuper (as UnderSegmentation) in order
to facilitate their combination and minimization on a [0,1] scale.
We have also defined them on the Y* subset of intersecxted
segments. Observe that OverSegmentation and
UnderSegmentation are properties of the segments, but can be
averaged over the p { segments associated with each training object,
and in turn averaged over the n training objects. Alternatively,
OverSegmentation and UnderSegmentation can be averaged over
the P segmentation objects that interact with the set of all training
objects, X. The difference is related to whether these measures
should be weighted by the training objects, larger or more
extensive training polygons being likely to interact with more
segments than smaller ones. The un-weighted version first
averages OverSegmentation and UnderSegmentation for each
training object, then averages over all the training objects. Both
the weighted and un-weighted averages can be used as indicators
of overall segmentation quality relative to the training set X.
The range of OverSegmentation and UnderSegmentation is in
[0,1], where OverSegmentation=0 and UnderSegmentation=0
define a perfect segmentation, where the segments match the
training objects exactly. Obviously, imperfect segmentations, as
defined here, could result from poor delineation of training objects,
in combination with poor segmentation. Assuming that the
training objects in X are exact, OverSegmentation and
UnderSegmentation also have the nice property of identifying
segments that match the training objects more or less perfectly.
Combining the measures could result in a method to sort or rank
the segments (for classification purposes) in terms of agreement
with the furnished training objects.
The two dimensional space defined by OverSegmentation and
UnderSegmentation is the unit square S. As a result of the fact
that the ideal segmentation result is a point at the origin in this
space, the Euclidean norm of a vector with coordinates
(OverSegmentation, UnderSegmentation) is a measure for the
quality of a segmentation (Levine and Nazif (1982) first propose
this and an absolute value based combination of metrics). Let the
“distance” index D be as follows:
D = -yI OverSegmen tation 2 + UnderSegme ntation 2
This index D should be interpreted as the “closeness” in the space
defined above to an ideal segmentation result, in the context of a
pre-defined training set. In this context, D is in [0, 2 12 ]. The
distance index can be defined for each segment yj in Y*, averaged
over each training object x„ or averaged over the set of all training
objects X to produce a composite index for the entire segmentation
result.
METHODS
The imagery we used is a 3 band (RGB) aerial image of an urban
area in San Francisco, California, USA. Resolution is
approximately 0.174 meters. Using the imagery and parameter
combinations described by Holt et al. (under review), we obtained
segmentation results for two different software packages:
eCognition (http://www.definiens.com) and ASTRO
(http://berkenviro.com/berkeleyimgseg/). Both of these programs
use a region merging technique to obtain a complete spatial
partition of the input image pixels. ASTRO is developed based on
the region merging algorithms described in Benz et al. (2003).
Both software packages perform segmentation and export the
results as polygons in the ESRI shapefile format. In total, 150
parameter combinations were examined for scale, smoothness and
color according to {10, 20, 30, 40, 50}x{0.1, 0.3, 0.5, 0.7,
0.9}x{0.1, 0.3, 0.5, 0.7, 0.9}, respectively. Using the resultant
shapefile from each parameter combination, we computed the
measures in the Java environment using JTS
(http://www.vividsolutions.com/jts/jtshome.htm) and GeoTools
(http://geotools.codehaus.org/).
For training sets, we digitized 119 vehicles (cars and trucks) as
simple rectangles, 48 tree crowns, and 36 building rooftops for a
total of 203 training shapes. Relative to these training object sets
(vehicles, trees, buildings and combined), we computed
OverSegmentation and UnderSegmentation for each combination
of parameters in each software package and examined the
goodness D when averaged over the n training objects in X and
averaged over _y ; G Yj*, V ij. Resultant segmentation results
were visually examined and interpreted. The results are reported
below.
RESULTS
Figure 1 shows the overall segmentation results when
OverSegmentation and UnderSegmentation are averaged over yj
G Yj*, V ij (left) and when OverSegmentation and
UnderSegmentation are first averaged for each training object,
then averaged over all training objects (right). The behavior of
eCognition and ASTRO in response to parameter variation is
illustrated in Figure 1.