Spatial change detection using voxel classification by normal
distributions transform
Ukyo Katsura1 , Kohei Matsumoto1 , Akihiro Kawamura2 , Tomohide Ishigami3 ,Tsukasa Okada3 , and Ryo Kurazume2
Abstract— Detection of spatial change around a robot is
indispensable in several robotic applications, such as search andrescue, security, and surveillance. The present paper proposesa fast spatial change detection technique for a mobile robot
using an on-board RGB-D/stereo camera and a highly precise
3D map created by a 3D laser scanner. This technique first
converts point clouds in a map and measured data to grid
data (ND voxels) using normal distributions transform andclassifies the ND voxels into three categories. The voxels in
the map and the measured data are then compared according
to the category and features of the ND voxels. Overlapping
and voting techniques are also introduced in order to detect
the spatial changes more robustly. We conducted experiments
using a mobile robot equipped with real-time range sensors to
confirm the performance of the proposed real-time localizationand spatial change detection techniques in indoor and outdoor
environments.

I. INTRODUCTION
Spatial change detection is a fundamental technique forfinding the differences between two or more pieces ofgeometrical information. This technique is critical in several applications, such as topographic change detection in
airborne laser scanning [1] [2] or terrestrial laser scanning[3] [4], map maintenance in urban areas [5], preservationof cultural heritage [6], and analysis of plant growth [7].
In robotics, detection of spatial changes around a robot is
indispensable in several robotic applications, such as searchand rescue, security, and surveillance. Service robots, suchas cleaning robots or delivery robots, which are used on adaily basis, require the ability of spatial change detection inorder to safely and efficiently co-exist with humans, because
the environment can change dynamically according to humanbehavior. For these service robots, precise localization is also
required in order to perform a desired task.
Two-dimensional LiDARs, such as Hokuyo TOPURG andSick TiM51x, have commonly been used for the localizationof mobile robots due to their low cost, small size, and highprecision [8][9][10]. On the other hand, in recent years,
with the widespread use of low-cost 3D laser scanners,
such as FARO Focus 3D, and 3D range sensors, such
1 UkyoKatsura and Kohei Matsumoto are with Graduate
School of Information Science and Electrical Engineering,
KyushuUniversity,
Fukuoka
819-0395,Japan{katsura,
matsumoto}@irvs.ait.kyushu-u.ac.jp
2 Akihiro Kawamura and Ryo Kurazume are with Faculty of Information
Science and Electrical Engineering, Kyushu University, Fukuoka 819-0395,
Japan {kawamura, kurazume}@ait.kyushu-u.ac.jp
3 Tomohide Ishigami and Tsukasa Okada are with Panasonic Inc.,
3-1-1 Yagumo-naka-machi, Moriguchi City, Osaka 570-8501, Japan{ishigami.tomohide, okada.tsukasa}@jp.panasonic.com

as Kinect, Xtion, and Velodyne HDL-32e, 3D localization(or 6D localization, including attitude) is also becoming
available in robotic applications using highly accurate 3D
mapping and real-time 3D range data. However, in general,
data measured by these sensors consist of millions of 3D
points, which are referred to collectively as a point cloud.
Real-time processing of a large number of point clouds istherefore not a trivial task. For example, although iterative
closest point (ICP) [11] is a popular technique for aligningpoint clouds, ICP requires the determination of point-topoint (or mesh) correspondences, and thus the calculation
cost remains too large for real-time localization or spatialchange detection by a mobile robot using point clouds.
In order to deal with the enormous number of points
in a point cloud for robust robot localization, we haveproposed a fast localization technique using normal distributions transform (NDT)[12] and a particle filter [13]. In
the present paper, as an additional function of the proposed
localization technique [13], we propose a fast spatial change
detection technique by comparing 3D range data obtainedby an on-board RGB-D/stereo camera and a high-precision
3D map created by a 3D laser scanner. This technique first
converts point clouds in the map and measured data to grid
data (ND voxels) by NDT, and classifies the voxels into
three categories. The voxels in the map and the measured
data are then compared according to the category andfeatures of ND voxels. Overlapping and voting techniques
are also introduced in order to detect spatial changes morerobustly. We conducted the experiments using a mobile robot
equipped with real-time range sensors in order to confirm
the performance of the proposed real-time localization andspatial change detection techniques in indoor and outdoor
environments.
II. R ELATED RESEARCH
Spatial change detection is a critical problem in somerobotic applications [14] [15] [16] [17] [18], [19]. Andreasson et al. [14] proposed autonomous change detection for asecurity patrol robot. They used color and depth information
obtained from a 3D laser range finder and a camera. A
precise reference model was first created from multiple colorand depth images and was registered by 3D normal distributions transform (3D-NDT) [20] representation. Spatialchanges are detected by calculating the probabilistic valueof the current point being different from the reference modelusing the 3D-NDT representation and color information.
Saarinen et al. [21] proposed Normal Distributions Trans-form Occupancy Maps (NDT-OM), which concurrently represent the occupancy probability and the shape distributionof points (NDT) in each voxel. The occupancy probability
is calculated from a sensor model and the point distribution
in the voxel, and the similarity measure of two NDT-OMs isdefined by L2 distance function. Nùüez et al. [15] proposeda fast change detection technique using a mixture Gaussianmodel and a fast and robust matching algorithm. Pointbased comparison of an environmental model and a large
number of point cloud data measured by an on-board range
sensor requires a large calculation cost. In order to solve thisproblem, they represented the environmental model and themeasured data with a mixture Gaussian model and processed
the difference calculation using a high-speed algorithm. Fehret al. [18] presents a 3D reconstruction technique of dynamic
scenes involving movable objects using the truncated signed
distance function (TSDF). They represented the current scene
with TSDF grids and compared them with previous TSDF
grids to obtain segmented movable objects in the scene.
Luft et al. [19] proposed a stochastic approach to evaluate whether a grid is changed in time according to fullmap posteriors represented by real-valued variables. Theirtechnique enables consideration of the full-path informationof the laser measurement, as opposed to end-point based
approaches. Moreover, it considers the confidence about thecell values as opposed to occupancy maps or a most-likely
maps.
In general, spatial change detection can be classified into
three groups: point/mesh-based, height-based, and voxelbased comparisons. Point/mesh-based comparison [22] [6]is a technique that compares the distance of nearest points
or meshes in two point clouds, which is similar to the ICP
algorithm [23]. Lague et al. [4] proposed the use of the
distance along normal direction of a local surface to makethe algorithm robust to errors in 3D terrain data measured bya terrestrial laser scanner. In [3], point clouds are converted
to panoramic distance images, which are compared directly.
The problem with this technique is the degree to which theproper threshold is determined [22].
Height-based comparison is often used in geographicalanalysis in earth sciences. The digital elevation map (DEM)of difference (DoD) is a popular technique to compare
geographical data captured by airborne or terrestrial laser
scanners [5] [24] [2]. This technique also has the problem
of selecting a proper threshold.
In voxel-based comparison, a point cloud is first converted
to a voxel representation using, for example, an octree
structure. Performing the XOR of occupancy voxels is thesimplest way [25] to find spatial differences. In [26], three
metrics are compared in order to calculate the difference ofvoxels, which are the average distance, the plane orientation,and the Hausdorff distance. The Hausdorff distance is the
maximum value of the minimum distances of points in two
voxels and indicates the best performance. However, thecomputational cost of the Hausdorff distance is quite high,because closest point pairs must be determined. In spatialchange detection in 3D, not only point clouds but also asequence of camera images has been used [27], [28].
The proposed technique is a voxel-based comparison
method. However, rather than comparing the distances ofpoints or meshes or the existence of occupied voxels directly,
we used the point distribution in each voxel calculated by
3D-NDT. We classify the distribution of points in a voxel into
three categories and compare the voxels in different scansaccording to the category of voxels. Although Andreasson
et al. [14] also used 3D-NDT for spatial change detection,
their technique can be classified as a point-based comparison
because they used 3D-NDT to calculate the probability of apoint being different from the reference model.
III. FAST 3D LOCALIZATION USING NDT AND A
PARTICLE FILTER

We have proposed a fast 3D localization technique usinga large-scale 3D environmental map measured by a 3D laser
scanner and 3D range data captured by an RGB-D/stereo
camera on a mobile robot [13].
The proposed technique uses the idea of NDT [11] for
expressing a point distribution in a compact but informationrich form. Point clouds in an environmental map are first converted to the ND voxel representation. Then, in order to more
efficiently handle the characteristics of point distribution,
representative planes called eigenplanes are extracted andregistered as a new environmental map representation. Next,
when a mobile robot scans the surrounding environment
using an on-board RGB-D/stereo camera, an obtained 3D
point cloud is also converted to the ND voxel representationand eigenplanes are extracted in the same manner for theenvironmental map. In addition, seven representative points(six sigma points and a center point) are extracted andregistered as additional features. Finally, the similarities
between the environmental map and the measured data
are examined based on plane-and-plane and point-and-plane
correspondences. Using the obtained similarities, a particle
filter is used to find the optimum position, which indicatesthe maximum similarity between the environmental map andthe measured data.
IV. FAST SPATIAL CHANGE DETECTION USING NDVOXELSIn this section, we propose a fast spatial change detection
technique using ND voxels, which are generated and used
for the localization [13] mentioned in Section III. The most
simple technique for spatial change detection using voxels
is to compare the existence of occupied voxels in a same
space by XOR operation [25], in which a spatial change isconsidered to have occurred if an occupied voxel exists on
the map data but does not exist in the measured data, or viceversa. However, due to quantization errors or localizationand measurement errors, this simple technique does not work
well in many cases. For example, if the localization error islarger than the voxel size, most of the voxels are labeled as
spatial changes. In order to tackle this problem and realize
robust spatial change detection, the technique proposed inthis section adopts the following three techniques.

1) Classification of point distribution in an ND voxel2) Overlapping of voxels in map data
3) Voting of spatial change detection through sequential
measurements
A. Classification of point distributions in ND voxels
If we use the simple technique for spatial change detection
by taking XOR between the map and the measured voxels
mentioned above, it is impossible to detect spatial changes
if the voxel includes not only point clouds to be detected as
spatial change but also other stationary point clouds such asa floor or a wall. The proposed technique solves this problem
by classifying the point distribution in ND voxels into three
categories.
In the calculation of NDT during the localization [13],three eigenvalues λ1 , λ2 , λ3 (λ1 < λ2 < λ3 ) and eigenvectors of a covariance matrix of a point cloud in a voxel are
obtained. According to the following criteria, we classify the
point distribution in ND voxels into three categories, that is,“Sphere”, “Sheet”, and “Line”. In addition, if there are nomeasured points in a voxel, then we refer to the voxel as“Empty”.
Sphereλ3 ≈ λ2 ≈ λ1  0

(1)

Sheet
Line

λ3 ≈ λ2  λ1 ≈ 0
λ3  λ2 ≈ λ1 ≈ 0

(2)
(3)

Magnusson et al. [29] also proposed a loop detection
technique using the histogram of three shapes (spherical,
planar, and linear), which are classified from point clouds
according to the eigenvalues. In our case, we use theseclassifications to evaluate the difference between the map
and measured voxels.
If the voxels in the map and measured data are labeledwith different categories, then we say that there is a spatialchange in this space of the voxel. In addition, even if
both voxels have the same labels of “Sheet” or “Line”, wecompare the normal or direction vectors of the sheets and thelines, which are the eigenvectors corresponding to minimum
and maximum eigenvalues, respectively. If these vectors are
sufficiently matched, then we consider these voxels to havethe same labels and ignore their spatial change.
(nmap , nmeasured )(vmap , vmeasured )

<
<

Nt
Vt

(Sheets)(Lines)(4)(5)

where n and v are the normal and direction vectors of the
sheets and the lines which are eigenvectors corresponding to
the smallest and the largest eigenvalues, and Nt and Vt areproper thresholds. nmap and vmap are calculated beforehandfrom the environmental map (point cloud) measured by a 3D
laser scanner, and nmeasured and vmeasured are obtainedusing the measured map (point cloud) by an on-board RGBD/stereo camera. In the experiments in Section VI, we set Nt
and Vt as 0.5. Similar idea can be seen in [26], in which ”bestfitting plane orientation” was used to evaluate the spatialchanges.

B. Overlapping of voxels in map data
The proposed technique inherently involves a quantization
error because we divide the entire space into several voxel
grids and perform NDT for each voxel. Thus, the classification mentioned above is also affected by the quantization
error. For example, the boundary between a floor and a wall
is classified as “Sheet” if the majority of points in the voxel
belong to either a floor or a wall. On the other hand, theboundary is classified as “Sphere” if both planes are evenly
included.
In order to suppress the influence of quantization error,
the proposed technique uses overlapping ND voxels [12];that is, adjacent voxels overlap each other so that the centersof the voxels are displaced with half the voxel size. As aresult, every point in 3D space is involved with eight adjacentvoxels. Thus, by comparing a voxel in the measured data withup to 27 adjacent voxels in the map data, we can evaluate
the degree of coincidence of the map and the measured
data robustly with respect to the quantization error. Moreprecisely, if at least one voxel in 27 voxels in the map data issimilar enough to the voxel in the measured data, that voxel
is marked as ”no change”. In the proposed technique, theND voxels in the map overlap, and ND voxels are calculated
beforehand in order to reduce the on-line calculation cost.
C. Voting of spatial change detection through sequential
measurements
The measurement data taken from an RGB-D/stereo camera, such as Kinect or a stereo camera, are corrupted bynoise, and the measurement noise tends to be detected
as spatial change in some cases. Therefore, we adopt a
voting technique through sequential measurements in orderto suppress the effect of the measurement noise. Here, wefirst extract the voxels that are regarded as spatially changed
voxels in each measured datum. Then, by voting on theseresults for the space in a global coordinate system with thefollowing weights according to the 3D normal distribution,
the regions of spatial change can be obtained robustly.
w(p) = N (c, σ 2 )(6)where p is the center of the adjacent voxel in the map dataand c is the center of the original voxel in the measured data.
In the experiments in Section VI, we set the voxel size as
400 mm and σ as 200 mm, and voted for the information of
the spatial change to 27 adjacent voxels.
V. M OBILE ROBOT SYSTEM FOR LOCALIZATION ANDSPATIAL CHANGE DETECTION

In order to confirm the performance of the proposed
localization and spatial change detection techniques, we built
a mobile robot system equipped with an omni-directionallaser scanner (Velodyne HDL-32e) and an RGB-D camera(Kinect for Xbox One, Microsoft), as shown in Fig. 1.
For localization, point cloud data measured by the omnidirectional laser scanner are compared with a large-scale 3D
map measured by a high-precision laser scanner (Focus 3D,

FARO). However, the number of scanning lines of the omnidirectional laser scanner is 32, which is not sufficient for
detecting spatial changes in small regions. Thus, the RGB-D
camera is used to capture detailed range data in front of therobot for spatial change detection.

4
a b c

d

3
2
1

Fig. 4.

7

8

5

6

Objects placed in the pathway.

Velodyne HDL-32e
Kinect for Xbox One

Fig. 1.
Mobile robot system equipped with an omni-directional laser
scanner (Velodyne HDL-32e) and an RGB-D camera (Kinect, Microsoft).

VI. E XPERIMENTS IN INDOOR AND OUTDOORENVIRONMENTS

A. Indoor experiments
We conducted an experiment for spatial change detection
in an indoor environment (a hall) in order to confirm theperformance of the proposed technique. We first scanned thehall from eight positions using a high-precision laser scanner(Faro Focus 3D) and obtained an environmental map withdimensions of 40 m × 11 m. Figure 2 shows the obtained
3D point cloud and ND voxel representation.

laser scanner and the environmental map by the positioning
technique in Section III [13], which is based on the comparison of ND voxels and optimization using a particle filter.
The target position is determined manually, and the path tothe target position is determined by Dijkstra’s algorithm inthe navigation package in the robot operating system (ROS).
The robot moves along the desired path automatically andfuses the position information from the particle filter [13] andodometry at 1 Hz. The range data from the RGB-D camera(measured data) are transformed using the estimated position
information and compared with the environmental map using
the proposed technique. In this experiment, the voxel size for
localization and the spatial change detection is 40 cm.
Table I shows the positioning errors in cases that the voxel
size is 40 [cm] and 100 [cm]. The actual robot position ismeasured by the high-precision laser scanner (Faro Focus
3D) placed at a known position. In this experiment, thenumber of particles is fixed to 400. From this table, we cansee that the accuracy for the localization is about 10 [cm]and not so different for the cases that the voxel sizes are 40[cm] and 100 [cm].
TABLE IP OSITIONING ERRORS
Voxel size
40 [cm]100 [cm]

Fig. 2. 3D environmental map and ND voxel representation. Red, green,
and blue cubes are voxels labeled sphere, line, and sheet, respectively.

Next, we placed three objects, as shown in Fig. 4, having
a 10 cm × 10 cm × 10 cm (1 and ),5 bdimensions of 
2 and ),6 
c 30 cm × 30 cm ×20 cm × 20 cm × 20 cm (3 and ),7 and d 40 cm × 40 cm × 40 cm (4 and30 cm (8 at the positions shown in Fig. 3. The robot (Fig. 1) then)
moves along the trajectory shown in Fig. 3 and attempts tofind these objects as spatial changes.

4

3 2 1

Error
99.2 [mm]104.6 [mm]Figure 5(e) shows the detected spatial changes by the
proposed method. Though one region is misdetected asindicated by a white circle, the four kinds of objects that areplaced at eight positions later are correctly detected in thisexperiment. We run the robot from the same initial position
to the target position by taking RGB-D data ten times, andobtained the detection rate of the spatial changes as shownin Table II. Note that we considered the object is detectedin case that at least one voxel containing vertexes, edges, orplanes of the object is detected as spatially changed.

Final position
6
8

5
7

TABLE II

Initial position
5m

T HE DETECTION RATE FOR FOUR KINDS OF OBJECTS
Object (size)

Fig. 3.

Indoor environment (Hall: 40 m × 11 m).

The initial position of the robot is determined as follows.
An initial position is first roughly assigned by hand. The
accurate position is then estimated using the omni-directional

A (400 × 400 mm)
B (300 × 300 mm)
C (200 × 200 mm)
D (100 × 100 mm)

Proposed
100
100
85
50

Detection rate [%]3D-NDT[14] L2 [21]
100
95
100
95
75
50
15
0

We also compared the performance of the proposed
method with the 3D-NDT based spatial change detection

Undetected objects

Misdetected regions
Misdetected regions(a) 3D-NDT based spatial change detection [14](b) L2 distance function [21]Undetected objects

Misdetected regions
Misdetected regions(c) Taking XOR of occupancy voxels [25](d) Taking XOR of overlapped occupancy voxels

in Table III. We used the overlapped voxels in the map
and considered the voxel in the map should be detected as
spatially changed if it contains vertexes, edges, or planesof the objects. Table III shows that the proposed method,which uses classification of point distribution, overlapping
voxels, and voting techniques, gives highest precision (98.50%) and outperforms other techniques. Figure 6 shows PR
and ROC curves for each method using various parameters.
In these figures, we can say that the proposed technique
outperforms the conventional 3D-NDT [14] and L2 distancebased techniques. Note that the recalls are considerably low
in all methods. This is because all voxels including at least
one vertex, edge, or plane of the object are regarded as thecorrect voxels to be detected, and therefore, for example,
the voxels on a wall hidden by the object are considered as
missing voxels which are not correctly detected.
TABLE IIIP RECISION AND RECALL [%]Misdetected regions

Fig. 5. Detected changes by (a) 3D-NDT based spatial change detection[14], (b) L2 distance function [21], (c) taking XOR of occupancy voxels[25], (d) taking XOR of overlapped occupancy voxels, and (e) proposed
method. Misdetected regions and undetected objects are indicated by whitecircles and crosses.

by Andreasson et al. [14], L2 distance function [21], andsimple methods using XOR calculation [25]. Figure 5(a)shows the detected spatial changes by the 3D-NDT based
method [14]. In this experiment, we used the depth images
captured by the RGB-D camera only and the color images
were not used. Although the changed regions are mostly
detected, some regions are misdetected or undetected. Table
II shows the detection rate for each object by the 3D-NDT
based spatial change detection after ten trials. These results
show that the proposed method outperforms the 3D-NDT
based spatial change detection especially in case that small
objects are placed. Although it may be possible to improvethe detection rate by decreasing the threshold for evaluating
the spatial change, this induces many misdetection as shownin Fig, 5(a).
Figure 5(b) shows the detected spatial changes by L2
distance function [21]. Figures 5(c) and (d) show the detected
spatial changes by taking XOR between the map and themeasured voxels [25]. Figure 5(d) uses the overlapped voxels
in the map and we judged that the voxel is not spatiallychanged if at least one voxel among 27 map voxels adjacentto the measured voxel is occupied. In these experiments
using XOR calculation, a number of misdetected regions arefound, which are mainly caused by the positioning error of
the mobile robot. On the other hand, the proposed method(Fig. 5(e)) is robust against position error due to voxel
classification and voting technique.
Finally, we show the precision and recall of the detectionof voxels which are specially changed for each method

3D-NDT [14]L2 [21]
XOR [25]
XOR (overlapped)
Classification
Classification, overlapping
Classification, overlapping, voting (Proposed)

100
L₂

25

Proposed

Recall
4.79
1.11
3.95
1.71
2.47
26.06
7.58

Proposed

20

60
40
3D-NDT
20
0
0

Precision
61.90
81.19
17.55
69.99
22.74
61.77
98.50

30

80
Precision(e) Proposed method

RecallUndetected objects

15
10

3D-NDTL₂

5
5

10 15 20
Recall(a) PR Curve

Fig. 6.

25

30

0
0

5

10 15 20 25 30 35 40
FPR(b) ROC Curve

PR and ROC curves.

B. Processing time for localization and spatial change detection
We measured the processing time for localization andspatial change detection in this experiment. Table IV shows
the average processing time for one cycle of each stepduring the experiments (Intel Core i7, 3.40GHz). The average
processing time for spatial change detection by the proposed
technique is 21.3 millisecond including the conversion process of the depth images captured by the RGB-D camera
to the ND voxel representation. On the other hand, the processing time by the 3D-NDT based spatial change detection[14] is 563.6 millisecond and the proposed technique is 26.5
times faster than the 3D-NDT based technique. The simple
method using XOR calculation [25] is slightly faster thanthe proposed method. Note that, since these processes canbe executed independently, we run processes of localizationand spatial change detection at 1 Hz in the experiments.

TABLE IV
P ROCESSING TIME FOR EACH STEP
Localization
3D-NDT[14]L2 [21]
XOR[25]
XOR (overlapped)
Proposed

Spatial change detection

827.2 [msec]
570.0 [msec]
17.2 [msec]
17.9 [msec]
19.4 [msec]
20.4 [msec]

C. Outdoor experiments

Detected changes

Detected changes(a) XOR calculation ofoccupied voxels(b) Classification of point
distribution

Detected changes

Detected changes

In these experiments, we first scan the outdoor environment (road) from three positions using a high-precision laser
scanner (Faro Focus 3D) and obtained an environmental map
having dimensions of 30 m × 10 m. We then placed four
1 40 cm × 40 cm × 40
objects having dimensions of ,
2 40 cm × 40 cm × 80 cm; ,
3 80 cm × 15 cm ×
cm; ,
4 40 cm × 40 cm × 20 cm, and the robot
60 cm; and ,
moves 30 m along a straight line. Here, we replaced the
RGB-D camera with a conventional stereo camera systembecause acquiring range data in direct sunlight using the
RGB-D camera (Kinect for Xbox One) becomes extremely
difficult. We captured 430 range images using the stereo
camera system during the movement.
Figure 8(a) shows the detected regions (red, green, andblue cubes), which are estimated to be spatially changed
using XOR calculation of the occupied voxels [25]. Figures
8(b), 8(c), and 8(d) show the detected regions using theclassification of point distribution (Section IV-A), classification and overlapping of voxels in map data (Section IV-B),
and classification, overlapping, and voting of spatial change
detection through sequential measurements (SectionIV-C),
respectively. In Fig. 8, detected voxels classified as “Sphere”,“Sheet”, and “Line” are illustrated by red, blue, and green
cubes, respectively. Table V shows the number of voxels detected as spatial changes in these experiments. As shown Fig.
8(d), the voxels with spatial changes are detected correctly if
we apply all of the techniques proposed in Section IV, thatis, classification of point distribution, overlapping of voxels
in map data, and voting of spatial change detection.
TABLE VN UMBER OF VOXELS DETECTED AS SPATIAL CHANGESXORClassification
Classification and overlapping
Classification, overlapping, and voting (Proposed)

704
364
313
48

(c) Classification of point
distribution andoverlapping(d) Proposed method(classification,
overlapping, and voting)Fig. 8. Detected spatial changes (red, blue, and green cubes) in an outdoor
environment.

VII. CONCLUSIONSThe present paper proposed a fast spatial change detection
technique for a mobile robot using an on-board RGBD/stereo camera and a high-precision 3D map created using
a 3D laser scanner. This technique first converts point clouds
in a map and measured data to grid data (ND voxels) using
NDT and classifies the voxels into three categories. The
voxels in the map and measured data are then comparedaccording to the category and features of the ND voxels.
The proposed technique consists of the following threetechniques.
1) Classification of the point distribution2) Overlapping of voxels in map data
3) Voting of spatial change detection through sequential
measurements
We conducted experiments using a mobile robot equippedwith real-time range sensors in order to confirm the performance of the proposed real-time localization and spatialchange detection techniques in indoor and outdoor environments.
Future work includes performance evaluation of actual
scenes, such as stations or market areas, and improvement of
the performance by using other information, such as coloror laser reflectance. In particular, laser reflectance, which
is obtained as a side product of range measurement by alaser scanner, is measured stably independent of the lighting
condition, even at night. Therefore, as additional information,
evaluating the spatial change robustly is very useful.
ACKNOWLEDGMENT

3

4

2

This research is supported by JSPS KAKENHI Grant
Number JP26249029.

1

R EFERENCES
Fig. 7.

Four additional objects in an outdoor environment.

[1] M. Hebel, M. Arens, and U. Stilla, “Change detection in urban areas
by object-based analysis and on-the-fly comparison of multi-view als
data,” ISPRS Journal of Photogrammetry and Remote Sensing, vol. 86,
pp. 52–64, 2013.

[2] T. T. Vu, M. Matsuoka, and F. Yamazaki, “Lidar-based change detection of buildings in dense urban areas,” in IGARSS 2004. 2004 IEEE
International Geoscience and Remote Sensing Symposium, vol. 5,
pp. 3413–3416 vol.5, Sept 2004.
[3] R. Zeibak and S. Filin, “Change detection via terrestrial laser scanning,” International Archives of Photogrammetry and Remote Sensing,vol. 36, no. 3, pp. 430–435, 2007.
[4] D. Lague, N. Brodu, and J. Leroux, “Accurate 3d comparison ofcomplex topography with terrestrial laser scanner: Application to
the rangitikei canyon (n-z),” ISPRS Journal of Photogrammetry andRemote Sensing, vol. 82, pp. 10 – 26, 2013.
[5] B. Thomas, C. Remco, W. Zachary, and R. William, “Visual analysis
and semantic exploration of urban lidar change detection,” Computer
Graphics Forum, vol. 27, no. 3, pp. 903–910, 2008.
[6] G. Palma, M. Sabbadin, M. Corsini, and P. Cignoni, “Enhanced visualization of detected 3d geometric differences,” Computer Graphics
Forum, vol. 37, pp. 159–171, 2 2018.
[7] Y. Li, X. Fan, N. J. Mitra, D. Chamovitz, D. Cohen-Or, and B. Chen,“Analyzing growing plants from 4d point cloud data,” ACM Trans.
Graph., vol. 32, pp. 157:1–157:10, Nov. 2013.
[8] D. Filliat and J.-A. Meyer, “Map-based navigation in mobile robots::
I. a review of localization strategies,” Cognitive Systems Research,
vol. 4, no. 4, pp. 243 – 282, 2003.
[9] S. Thrun, D. Fox, W. Burgard, and F. Dellaert, “Robust monte carlo
localization for mobile robots,” Artificial Intelligence, vol. 128, no. 1,
pp. 99 – 141, 2001.
[10] S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics (Intelligent
Robotics and Autonomous Agents). The MIT Press, 2005.
[11] A. Nuchter, H. Surmann, K. Lingemann, J. Hertzberg, and S. Thrun,“6d slam with an application in autonomous mine mapping,” inRobotics and Automation, 2004. Proceedings. ICRA ’04. 2004 IEEE
International Conference on, vol. 2, pp. 1998–2003 Vol.2, April 2004.
[12] P. Biber and W. Strasser, “The normal distributions transform: a new
approach to laser scan matching,” in Proceedings 2003 IEEE/RSJ
International Conference on Intelligent Robots and Systems (IROS
2003) (Cat. No.03CH37453), vol. 3, pp. 2743–2748 vol.3, Oct 2003.
[13] S. Oishi, Y. Jeong, R. Kurazume, Y. Iwashita, and T. Hasegawa, “Ndvoxel localization using large-scale 3d environmental map and rgbd camera,” in 2013 IEEE International Conference on Robotics andBiomimetics (ROBIO), pp. pp.538–545, 2013.
[14] H. Andreasson, M. Magnusson, and A. Lilienthal, “Has somethingchanged here? autonomous difference detection for security patrolrobots,” in 2007 IEEE/RSJ International Conference on Intelligent
Robots and Systems, pp. 3429–3435, Oct 2007.
[15] P. Nùüez, P. Drews, A. Bandera, R. Rocha, M. Campos, and J. Dias,“Change detection in 3d environments based on gaussian mixture
model and robust structural matching for autonomous robotic applications,” in 2010 IEEE/RSJ International Conference on Intelligent
Robots and Systems, pp. 2633–2638, Oct 2010.
[16] J. P. Underwood, D. Gillsjö, T. Bailey, and V. Vlaskine, “Explicit
3d change detection using ray-tracing in spherical coordinates,” in2013 IEEE International Conference on Robotics and Automation,
pp. 4735–4741, May 2013.
[17] A. W. Vieira, P. L. J. Drews, and M. F. M. Campos, “Spatial
density patterns for efficient change detection in 3d environment forautonomous surveillance robots,” IEEE Transactions on Automation
Science and Engineering, vol. 11, pp. 766–774, July 2014.
[18] M. Fehr, F. Furrer, I. Dryanovski, J. Sturm, I. Gilitschenski, R. Siegwart, and C. Cadena, “Tsdf-based change detection for consistent longterm dense reconstruction and dynamic object discovery,” in 2017
IEEE International Conference on Robotics and Automation (ICRA),
pp. 5237–5244, May 2017.
[19] L. Luft, A. Schaefer, T. Schubert, and W. Burgard, “Detecting changes
in the environment based on full posterior distributions over realvalued grid maps,” IEEE Robotics and Automation Letters, vol. 3,
pp. 1299–1305, April 2018.
[20] P. Biber and W. Strasser, “The normal distributions transform: a new
approach to laser scan matching,” in Proceedings 2003 IEEE/RSJ
International Conference on Intelligent Robots and Systems (IROS
2003) (Cat. No.03CH37453), vol. 3, pp. 2743–2748 vol.3, Oct 2003.
[21] J. P. Saarinen, H. Andreasson, T. Stoyanov, and A. J. Lilienthal, “3dnormal distributions transform occupancy maps: An efficient representation for mapping in dynamic environments,” The International
Journal of Robotics Research, vol. 32, no. 14, pp. 1627–1644, 2013.

[22] P. Gianpaolo, C. Paolo, B. Tamy, and S. Roberto, “Detection ofgeometric temporal changes in point clouds,” Computer Graphics
Forum, vol. 35, no. 6, pp. 33–45, 2016.
[23] P. J. Besl and N. D. McKay, “A method for registration of 3-d shapes,”
IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 14, pp. 239–256, Feb 1992.
[24] H. Murakami, K. Nakagawa, H. Hasegawa, T. Shibata, andE. Iwanami, “Change detection of buildings using an airborne laser
scanner,” ISPRS Journal of Photogrammetry and Remote Sensing,vol. 54, no. 2, pp. 148 – 152, 1999.
[25] “Spatial change detection on unorganized point cloud data.”
http://pointclouds.org/documentation/tutorials/
octree_change.php.
[26] D. Girardeau-Montaut, M. Roux, R. Marc, and G. Thibault, “Change
detection on points cloud data acquired with a ground laser scanner,”
International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. 36, no. PART 3, pp. 30–35, 2005.
[27] T. Pollard and J. L. Mundy, “Change detection in a 3-d world,” in2007 IEEE Conference on Computer Vision and Pattern Recognition,
pp. 1–6, June 2007.
[28] A. O. Ulusoy and J. L. Mundy, “Image-based 4-d reconstruction using
3-d change detection,” in Computer Vision – ECCV 2014 (D. Fleet,
T. Pajdla, B. Schiele, and T. Tuytelaars, eds.), (Cham), pp. 31–45,
Springer International Publishing, 2014.
[29] M. Magnusson, H. Andreasson, A. Nuchter, and A. J. Lilienthal,“Appearance-based loop detection from 3d laser data using the normal
distributions transform,” in 2009 IEEE International Conference on
Robotics and Automation, pp. 23–28, May 2009.