The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B5. Beijing 2008 
656 
Figure 5. Semi-automatic repair of a defect shown in the 
top row. The bottom row shows the result of the 
substitution. 
The process is an easy to use tool to remove defects caused by 
scanning from the facade model. While it is limited to repetitive 
structures, it can cope with any kind of shape and is not limited 
to certain geometries. One disadvantage is the need for 
interactive marking of defect areas, which prevents the 
application of the approach to mass production of building 
models. The second disadvantage is the need for a global 
template matching, since this is a very costly operation. 
However the repetitions of the elements are spread across the 
façade, so a simple localized search in the region around the 
defect area is not sufficient. We will address this issue later. 
4.1 Automated identification of defect areas 
Since most defects are caused by incomplete data, we devise a 
simple method to detect areas which have insufficient sampling. 
In other words we define a defect area as an area of the 
LASERMAP which has a point density which is considerably 
lower than the average point density. The average point density 
can be determined from the pre-planning stage of the scanning 
campaign, when the density was specified as a mission 
parameter. Another method is to estimate the average point 
spacing by computing the nearest neighbor to each scanned 
point. Obviously doing so for all points is computationally too 
expensive. But it is sufficient to sample the point density over a 
subset of points, randomly chosen from the point cloud. Figure 
6Figure 6 shows a plot of the number of samples over the 
distances to the nearest neighbor for a subset of 100000 points. 
The plot exhibits a clear peak at just under 10 mm, which gives 
the average point density. 
Figure 7 shows the result of such computation. It shows a 
LASERMAP and the corresponding error map, which marks 
areas of insufficient point density. We can see that most areas of 
incomplete data occur at windows. This is due to the laser beam 
penetrating through the glass and thus not giving a return. But 
we can also see how shadowing caused by the dominating 
oblique view from the left creates areas of incompleteness. Even 
small occlusions caused by trees are visible at the right border. 
The sensitivity of the error map can be controlled by simple 
thresholding. The regions of the error map can be used to 
replace the interactive marking of defect areas. 
The method for computing the error map integrates well with 
the computation of the LASERMAP itself, since both are based 
on the computation of planar nearest neighbors. We use an 
accelerated search structure for the computation, which has to 
be initialized only once for both computations. 
Point facing in mm 
Figure 6. Distribution of the point spacing to estimate 
average point density. 
Figure 7. A LASERMAP computed by nearest 
neighborhood interpolation and the corresponding error 
map, which marks areas of insufficient scan density. 
5. ENCODING OF REPETITIONS 
To avoid global template matching, a problem mentioned above, 
we restrict the matching to key points. We use the non 
maximum suppression on the difference-of-Gaussian to detect 
robust key points. This is in effect the same operation used to 
localize SIFT key points. However, we do not compute SIFT 
features. To detect corresponding key points within the same 
dataset, we compute the normalized correlation coefficient of 
the patches surrounding the key points. Matching key points are 
assigned to the same equivalence class. In Figure 8 the image on 
top shows the key points detected in a LASERMAP. 
We use a graph to store the relations among the key points. A 
Graph G consists of a set of vertices V and a set of edges E. The 
edges connect the vertices and thus are represented by pairs. If 
two key points kl and k2 have matching patches, we add the 
two vertices vl and v2 to the graph and add an undirected edge 
e(vl, v2). The Euclidian distance of kl and k2 is set as the 
weight of the edge e. 
A problem in the matching of key points is the selection of a 
proper threshold for the correlation coefficient. Because of this 
problem we often encounter the following situation: while key 
point kl is matched to k2 and k2 is matched to k3, kl is not 
matched to k3. Using the arrow symbol for the matching we can 
write -# k’i *2-* kS,kl **« %3. However, since we think of 
matching key points as equivalence classes, we have to generate 
the missing relation. In graph theory this is known as transitive 
closure. So if vertex v2 can be reached from vertex vl 
(k1 =» k2), we add the edge e(vl, v2) to the graph. This creates 
fully connected sub-graphs, representing equivalence classes of 
matching key points. Figure 9 shows in the upper image a 
portion of a graph after transitive closure.