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.