The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Voi. XXXVII. Part B4. Beijing 2008 
building edges. In applications seeking to determine changes 
between two or more epochs of data over an urban or peri-urban 
area, where the demolition or construction of 
buildings/structures is of interest, lidar data, in contrast with 
aerial photography, is potentially able to provide a point cloud 
dataset requiring significantly less manual editing than that 
produced by conventional photogrammetric processes. 
However, while the efficiency of data capture might be 
improved, it is also necessary to improve the methodology 
relating to change detection in order to cope with this potential 
for an increase of data. Techniques operating on the point 
clouds themselves also have the advantage of being able to be 
applied to point clouds from any source, making such an 
approach more versatile. Efficient change detection 
methodologies, coupled with increasingly frequent data capture 
could lead to a merging of continuous and cyclic revision 
processes. Even without an increase in the quantity or scale of 
data it would be of interest to provide robust routines that can 
identify areas of interest automatically. 
1.2 Point cloud based change detection 
As high resolution three-dimensional samples of the real world, 
point clouds have potential for change detection at a variety of 
scales. Change detection on the point clouds themselves would 
help to increase the speed of the change detection process and 
improve the management of the datasets (both key parameters 
in determining the cost efficiency of the change detection 
process). There are, however, a number of obstacles to the 
demonstration of a robust change detection process based solely 
on a three-dimensional point cloud: 
• ‘best guess’ point correspondence must be determined, even 
though no direct point to point correspondence can be 
assumed; 
• known topology cannot be assumed as point clouds may 
originate from multiple sources; 
• occlusions during data collection may need to be considered; 
• differences between two point clouds do not imply an 
information change (e.g. the addition of a new building); 
• large datasets require memory-efficient data handling 
routines. 
The development of change detection procedures that operate 
on point cloud datasets would allow national mapping agencies 
to take advantage of improved data flow lines. As a result they 
would be able to provide change detection at a higher temporal 
and spatial scale, or simply be able to improve the economics of 
map revision. 
This paper will outline work to establish a flow line to identify 
change between two point cloud datasets, based on the 
comparison of octrees, i.e. three-dimensional data structures 
representing the point cloud. By basing any comparison on 
these octrees, it is hoped to limit the amount of pre-processing 
required (for example the building of a digital surface model). 
The paper will start with a brief introduction to octrees. It will 
then present results of using the methodology on a variety of 
datasets. This will include datasets derived from digital aerial 
photography. Finally it will provide a discussion on the 
performance of the system and outline some conclusions. 
2. METHODOLOGY 
2.1 Octrees 
An octree (Figure 1) is a recursive and regular subdivision of 
three-dimensional space originally used to optimise computer 
graphics rendering (Botsch at al., 2002). The bounding box for a 
three-dimensional geometry is divided into eight equal cubes, 
each of which are in turn divided into eight more cubes until a 
specified level of subdivision is achieved, or the cubes have less 
than a predefined number of data points within their bounds. At 
this point leaf nodes are formed. An octree representation of a 
point cloud provides an efficient represent of the spatial 
distribution of the 3D points. The tree structure assumes no 
previous knowledge of topology but allows efficient searching 
of the point cloud to determine possible correspondence. 
Figure 1 An octree generated from data used in the study 
The comparison of point clouds against 3D CAD models is 
currently undertaken using point-to-mesh and mesh-to-mesh 
processes, often using algorithms based on the iterative closest 
point solution outlined by Besl and McKay (1992). This 
requires an existing reference model to be generated before 
change detection can take place. Girardeau-Montanut et al. 
(2005) outline a point-to-point comparison framework using 
octrees to optimise the performance of the change detection 
process, removing the need for a reference model; however this 
process is based on point clouds collected from similar positions 
and orientations and does not provide a general approach to the 
problem. Nevertheless, octrees clearly have the potential for 
facilitating the change detection directly between point clouds. 
2.2 Node to node comparison 
In this study the following methodology has been applied. Two 
octrees are generated based on the two point clouds which are to 
be compared. Each of these octrees share a common central 
node (described in the same geographic coordinate system) and 
the same controlling parameters, namely the maximum number 
of points allowed in each node and the maximum number of 
subdivisions allowed in the tree. As this study only deals with 
point clouds which are defined in a common coordinate system 
(for example the mapping system in use) one octree can be 
compared with the other. If the point cloud datasets were 
identical, the structure of each octree will be the same. Thus 
differences in the structure of each octree can be termed as 
change in the intervening time between epochs. Clearly, the 
cause of this change must be taken into account as such change