Ш 
CHANGE DETECTION FOR TOPOGRAPHIC MAPPING USING THREE- 
DIMENSIONAL DATA STRUCTURES 
D. M. Barber 3 , D. Holland* 5 , J. P. Mills 0 
a DSTL, Porton Down, Salisbury, SP4 OJQ, UK - dbarber@dstl.gov.uk 
b Ordnance Survey, Research Labs, Southampton, SO 16 4GU, UK - david.holland@ordnancesurvey.co.uk 
‘Newcastle University, School of Civil Engineering and Geosciences, Newcastle upon Tyne, NE1 7RU, UK 
j.p.mills@ncl.ac.uk 
WG IV/9 - Mapping from high resolution data 
KEYWORDS: Change Detection, Point Clouds, Lidar, Photogrammetry, Topographic Mapping 
ABSTRACT: 
Identifying significant changes to our urban areas is a prerequisite for accurate topographic mapping. This paper presents an 
approach based on octree data structures to identify change between two sets of point cloud data. The aim of the study was to 
establish if a method based on the comparison of point clouds could be used to detect simply where topographic change had occurred. 
As many of the changes that could occur are likely to result in a change of real world geometry (for example the construction or 
demolition of a building) the use of geometric data - rather than imagery alone as in other studies - is justified. Additionally, it 
means input data can be supplied directly from airborne lidar systems, or from aerial imagery using digital photogrammetric 
workstations which still remain the most commonly used apparatus for national mapping activities.Octrees are data structures that 
allow the partitioning of three-dimensional data into increasingly smaller units of space, using predefined criteria to control the level 
of subdivision (in this case a limit on the number of points in a node; and/or the total level of subdivision). Octrees have previously 
been used in applications where efficient searching and inspection of large volumes of three-dimensional data is required, such as in 
the rendering of computer graphics. By defining these structures, large data volumes of non-connected data (such as point clouds) 
can be efficiently managed and quickly compared with similar datasets collected at different epochs. In the study presented here, one 
approach compares entire octrees for differences between their structures, while a second approach compares individual data points 
to data contained in a reference octree.Two UK test areas form the basis of the study. Area 1 is the site of Heathrow Airport’s new 
Terminal Five which has seen significant development over the last five years. Area 2 is an urban/peri-urban area of Bournemouth 
consisting of both commercial and residential properties. In both cases, multi epoch data was provided by Ordnance Survey allowing 
point cloud data to be generated from imagery collected by an Intergraph DMC digital airborne sensor. High resolution 
photogrammetric processing was undertaken using BAE’s Socet Set and point cloud pre-processing using Terrasolid’s TerraScan 
suite. While it was possible to recognize significant and pre-identified areas of change using the methodology, a large number of 
false identifications were also observed, making it difficult to interpret the results without prior knowledge. The lack of success can 
partially be attributed to the quality of the input data. Slight variations in the point clouds, perhaps arising from poor image 
correlation during surface extraction, led to subtle variations in the structure of the octree and thus in the changes identified. 
1. INTRODUCTION 
1.1 Opportunities for change detection 
With the rapid expansion of our urban areas and the increasing 
desire to redevelop inner city brown field sites, ensuring that 
changes are quickly identified, and then recorded in national 
mapping databases, is increasingly important. At present within 
Ordnance Survey, Great Britain’s National Mapping Agency, 
map revision is undertaken at two levels (Ordnance Survey, 
2006). These comprise: 
• a process of continuous revision, mainly directed at urban 
developments and aiming to capture new features within six 
months of their being completed; 
• a process of cyclic revision for changes in the natural 
environment which is undertaken at intervals of between 2 
and 10 years, depending on the nature of the area and the 
expected amount of change (Holland, 2008). 
Typically, continuous revision is achieved through links to local 
planning processes and local intelligence. A surveyor may need 
to visit the site to undertake survey work. Cyclic revision, 
however, is most economically achieved through airborne 
imagery collected at fixed intervals, with this imagery being 
compared manually against the existing database and significant 
changes being specified for revision. 
The introduction of digital aerial cameras has seen a 
streamlining of data capture flow lines resulting in two possible 
outcomes relevant to map revision. The first is economic: the 
cost of capturing and processing aerial imagery could 
potentially be reduced. It is beyond the topic of this paper to 
discuss this aspect, other than to recognise that this could result 
in a second outcome. That is the option to capture imagery more 
often and/or at a larger scale. Clearly this could improve the 
chances of small, yet significant changes being identified more 
quickly than before. 
Also of relevance to map revision is the introduction of airborne 
and, for urban areas, ground based lidar systems (Barber et al., 
2008). Over the past ten years such systems have seen rapid 
development and they are now commonplace in generating 
digital surface and urban city models. They potentially offer 
datasets with a much denser set of observations, and without 
outlier measurements relating to miss-correlation between 
image points, especially along depth discontinuities such as 
1177 
•v к