The International Archives oj the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
could be related to the accuracy of datasets (for example errors 
in geo-referencing) or errors in the collection of the data (for 
example miss-correlation of images or multi-path errors in the 
return of a lidar signal). Also, each dataset must have a common 
ground sampling resolution for a comparison of this kind to be 
valid. For the purposes of this study this approach has been 
termed a node to node comparison. 
2.3 Point to node comparison 
The second approach in which the octree is used to aid the 
comparison between point datasets is its use to improve 
searching within a reference dataset. In this study this has been 
termed a point to node comparison, where a test point cloud 
searches for its closest corresponding data point in a pre-defined 
reference octree. Points with a corresponding point a large 
distance away could be considered change between epochs. 
This approach makes use of the spatial indexing of the octree to 
improve the speed at which this searching can be completed. 
2.4 Advantages of using octrees 
A number of advantages are anticipated from the use of octree 
data structures. Firstly, the approach is generic, in that it relies 
on point clouds from any source (for example ground based 
lidar, airborne lidar or airborne photogrammetry) providing, for 
a node to node comparison, the data resolution is the same. 
Secondly, once the process is established, it could be largely 
completed automatically limiting user interaction. Finally, the 
speed of the change detection can be optimised by limiting the 
searching times required. Note that for the purposes of this 
proof of concept study the efficiency of the routines has not 
been a priority, and thus the speed of the process has not been 
evaluated. 
2.5 Test data 
Two test areas were selected for use in the study. The first was 
around the area of Bournemouth on the south coast of Great 
Britain. The second was located around the ongoing 
development of Terminal Five at Heathrow Airport, London. 
Datasets from 2005 and 2006 were made available by Ordnance 
Survey. This included image datasets collected by the Ordnance 
Survey’s Intergraph DMC. These datasets, delivered for this 
study as a pre-orientated photogrammetric dataset, were used to 
generate point cloud datasets using BAE systems Socet Set 
photogrammetric workstation. Gridded digital surface models 
were collected with a ground sample resolution of 1 m using the 
standard Socet Set surface extraction and the NGATE surface 
extraction module. If such data was being used in an actual 
change detection flow line, it would be preferable not to have to 
manually edit the collected data - clearly in a change detection 
process it is assumed that the majority of data has already been 
collected and, when not required, the generation of new data is 
clearly uneconomic. Thus, in this study the surface data was 
used without any further editing. 
Before octrees were generated, however, the extracted point 
cloud datasets were classified into ground, above ground and 
buildings using TerraSolid’s TerraScan lidar processing system. 
A common classification routine was applied to both epochs to 
identify a ground surface, vegetation (or features above the 
ground) and buildings. This was applied to point clouds 
extracted using the standard and NGATE strategies. 
Figure 2 and Figure 3 show the results of the classification on 
the Bournemouth test area. 
Figure 2 Bournemouth (2005) DSM collected by the NGATE 
Socet Set extraction module after classification with TerraScan. 
Figure 3 Bournemouth (2005) DSM collected by the standard 
Socet Set extraction module after classification with TerraScan. 
It was noticeable that data collected using the NGATE system 
was more successfully classified at this stage (for the 
Bournemouth and Heathrow datasets), with buildings in 
particular being more clearly identifiable, where not obscured 
by vegetation. This indicated improved performance of the 
surface extraction around building edges compared to the 
standard extraction routine. In the case of the Bournemouth test 
area the standard DSM (Figure 3) contained a number of outlier 
errors, which resulted in a poorly classified ground surface, and 
ultimately a failure to identify any structures. 
Following classification an octree was defined for each point 
cloud setting the maximum level of subdivision to 20 nodes and 
a maximum of 150 data points per node. These octrees were 
then used in node to node and point to node comparisons. In 
order to try and limit the number of changes identified due to 
changes in vegetation cover, an additional condition was placed 
on the comparison routine: only those points classified as 
buildings/structures in the TerraScan pre-processing should be 
considered in the comparison (except in the case of the 
Bournemouth dataset extracted using the standard Socet Set 
extraction module).