s. The
nity to
) as
(6)
; know
similar
image
in the
ta are
'nerate
ogram
len we
of the
'e take
n and
ture of
oÜn the
e data
means.
s are
timally
s with
bution.
of the
classes
jsts of
Is. Our
res for
(7)
(8)
(9)
) and q
ty for
ling of
pe of
e if the
| by the
les will
> nodes
e other
feature
penalty
nt than
nergy.
othness
ded by
sed on
the algorithms in Boykov et. al. (2001), Kolmogorov and Zabih
(2004), and Boykov and Kolmogorov (2004) to perform the
graph cut optimization.
5. RESULTS AND DISCUSSION
We run the algorithm first for determining the “scatter” and
“surface” points as described in the previous section. We set the
smoothness cost parameter as o — 0.8. We also apply weights
to the data cost and smoothness cost terms to control the
relative importance of conformance with the data and spatial
coherence. We set Egan (f) = 1 and Eprior(f) = 2. Figure 4
shows part of the study area with points labeled as "scatter" or
“surface”.
Figure 4. Points color labeled as “scatter” (green) or “surface”
(black) points.
Two issues may be observed regarding the effectiveness of the
method. The first issue is due to small groups of points which
appear to be not from a surface but being labeled as a surface
point. This is mostly due to the size of the object not being
large enough for identification. Second issue is related to the
points that are on the ground being labeled as scatter points.
This case mostly happens when those points are the lower parts
of areas where there are scattered points.
After labeling points as surface and scatter, we establish a
second feature vector and graph in order to segment the surface
points. The first three elements of the feature vector are the
components of the unit surface normal vector which is the
eigenvector corresponding to the smallest eigenvalue of the
covariance matrix. The last element is the surface normal
variation within the point neighborhood which is the variance
of the angle 0 between the normal vector and the vertical.
8 — arccos(n - [0 1 0]) (10)
We set the number of bins to calculate the histogram for the
watershed segmentation as 20 for each dimension of the feature
vector. This parameter is of importance since it determines the
initial clusters in the feature space. An over-segmentation is
optimized by the graph cut algorithm. However, the algorithm
doesn't have the flexibility to compensate for under-
segmentation as it is the case in a split and merge type of
algorithm. We set the smoothness cost parameter as 0 = 0.6,
and the weights determining the relative importance of the
smoothness and data costs as Eqata(f) = 4 and Eprior(f) = 1.
Figure 5 shows segmented surface points in part of the study
area.
6. CONCLUSION
In this study, we have established a methodology based on the
graph representation of point labeling problem. We have
formulated two major labeling tasks defined as an optimization
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Volume XXXIX-B3, 2012
XXII ISPRS Congress, 25 August — 01 September 2012, Melbourne, Australia
problem on graphs and employed an efficient graph cut
algorithm resulting with the determination of the structure of 3-
D lidar point cloud. First, we have identified the local
neighborhood for each point and using the cues acquired from
point neighborhood we were able to identify them as “surface”
or "scatter" points. After obtaining the “surface” points, we
have labeled them using a different set of features resulting in a
segmentation of the surface points. Performing either of these
two tasks within this framework requires prior knowledge on
the structure of the feature space. Determining the distribution
of the feature space for the classification problem requires some
effort of collecting representative samples on the user side.
However, one should note that the distribution of the features
for surface and scatter points may be predicted as well.
We believe that this framework may provide better results in
case the terms related to the shapes of objects like, corners,
ridges, boundaries, etc. are also included in the energy function.
We plan to include energy terms representing shapes and higher
levels of relationships between the points within this framework
in the future.
0
Figure 5. Color-coded point segments in part of the study area
REFERENCES
Alharthy, A. & Bethel, J. 2004. Detailed building
reconstruction from airborne laser data using a moving surface
method. In: The Int Arch Photogram, Rem Sens Spatial Inform
Sci, Vol XXXV, Part B3, pp.213-218.
Belton, D. & Lichti, D.D., 2006. Classification and
segmentation of terrestrial laserscanner point clouds using local
variance information. In: 7he Int Arch Photogram, Rem Sens
Spatial Inform Sci, Vol XXXVI, Part 5, pp.44-49.
Biosca, J. & Lerma, J., 2008. Unsupervised robust planar
segmentation of terrestrial laser scanner point clouds based on
fuzzy clustering methods. ISPRS J Photogramm, 63(1), pp.84-
98.
Boykov, Y. & Kolmogorov, V., 2004. An experimental
comparison of min-cut/max-flow algorithms for energy
minimization in vision. IEEE transactions on pattern analysis
and machine intelligence, 26(9), pp.1124-37.
Boykov, Y. & Veksler, O., 2006. Graph Cuts in Vision and
Graphics: Theories and Applications. In: N. Paragios, Y. Chen,
& O. Faugeras, eds. Handbook of Mathematical Models in
Computer Vision. New York: Springer US, pp. 79-96.
Boykov, Y., Veksler, O. & Zabih, R., 2001. Fast approximate
energy minimization via graph cuts. IEEE Transactions on
