The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B5. Beijing 2008
569
connected points in the graph. Desirably, the strength of the
edges connecting points in the bricks and the points in the
mortar should be weak. Conversely the strength of brick-brick
edges and mortar-mortar edges should be strong. Some possible
schemes for determining the edge strength, Es, of an edge with
end points Vi and Vj, are:
- Es = Vi A + Vj A : the sum of the end point attributes,
- Es = Vi A - Vj A : the difference of the end point attributes,
- Es = Vi A * Vj A : the product of the end point attributes,
Vi A and Vj A are the attributes of end points Vi and Vj.
4.5 Segmentation - connected components
The graph G is filtered to remove the weak edges, i.e., edges
whose strength is below a user defined threshold. The result of
the filtering is a graph Gf. Filtering the weak edges leaves edges
that connect brick-brick points and mortar-mortar points, see
Figure 2(c) and (d). Therefore, all points in the same brick
should be interconnected by at least one edge. A connected
components analysis of Gf yields components (sub graphs) that
represent the bricks, see Figure 2(e).
4.6 Component counting
The connected components analysis will yield components of
varying sizes. Some of these components are invalid. Invalid
components are typically small and are to be rejected. The
definition of an invalid component is user defined. A count of
the number of valid components is kept. This count is used in
the next step to seek the optimum segmentation parameters for
a wall.
(d) Filtered mesh of the wall (e) Connected components
Figure 2 Real examples of typical results at key steps in the
algorithm. In this example the wall is over segmented. The
reason for this over segmentation is explained in the discussion
on the results for wall 3 (section 5).
4.7 Mode seeking
The segmentation and connected components is run several
times with different thresholds on the edge strengths. At each
segmentation the number of valid components is counted. The
component counts are graphed against the edge strengths,
Figure 3.
Number of components vs. Edge strength threshold
900
800 ,
| 700 * % • •
! 600 I v V
| 500 ' \
■S 400 ‘ * *
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
Edge strength threshold
Figure 3 The distribution of the edge strength threshold against
the number of components generated with a point count less
than a specified number. The solid curve shows valid
components with a point count of 20 or more points and the
solid curve shows valid components with a point count of 40 or
more points. It can be seen from the solid curve that the number
of components drops sharply as fewer invalid components are
counted. Notable about the graph are the two peaks. The data
set for this result has two walls at different distances from a
scanner. The two peaks represent the optimum edge strength
threshold for each wall.
The graph in Figure 3 is used to select the optimum edge
strength threshold for the final segmentation. A very large edge
threshold will lead to the removal of many edges and hence an
over segmentation. Many of the components obtained at this
large edge threshold will be small and will therefore be invalid.
Therefore, a small component count will be obtained.
Conversely a very small edge threshold leads to an under
segmentation as fewer edges are removed. Therefore, the
component count at very small edge thresholds will also be
small. The edge count should peak when there is an optimum
segmentation. If a point cloud contains walls at different
distances (depths) from the scanner, then several peaks will be
obtained. The number of peaks will be equal to the number of
depths in the scan. The critical part of this step is selecting a
suitable point count for invalid edges.
5. EXPERIMENTS
The point clouds used in the tests are from two different walls
at the University of Cape Town. Wall 1 is a typical face brick
wall. Wall 2 is a masonry wall with fairly large and irregularly
stone bricks. Walll and wall 2 are scanned at a resolution of
about 3 mm and 5 mm respectively.
Wall 1 Wall 2
Figure 4 Walls used in the tests.