An Incremental Scheme for Dictionary-based Compressive SLAM
Nagasaka Tomomi

Tanaka Kanji

Abstract— Obtaining a compact representation of a largesize pointset map built by mapper robots is a critical issue for recent SLAM applications. This “map compression”
problem is explored from a novel perspective of dictionarybased map compression in the paper. The primary contribution of the paper is proposal of an incremental scheme
for simultaneous mapping and map-compression applications.
An incremental map compressor is presented by employing
a modified RANSAC map-matching scheme as well as thecompact projection visual search. Experiments show promising
results in terms of compression speed, compactness of data andstructure, as well as an application to the compression distance.

I. I NTRODUCTION
Obtaining a compact representation of a large-size pointset
map built by mapper robots is a critical issue for recent
SLAM applications. This “map compression” problem has
been approached from a novel perspective of dictionarybased data compression in our study [1] [2]. Applications ofa map compressor range from memory-intensive large-size
map building [3]- [5] to lightweight information sharing in arobotic sensor network [6]- [8]. Another line of applications
is Kolmogorov complexity, as a universal similarity metric(e.g. compression distance [9]) between any two maps [2], inthe context of information retrieval [10], semantic labeling[11], as well as similarity clustering [12]. In the current
paper, an incremental scheme for the dictionary-based map
compression is presented in order to facilitate the incremental
mapping (SLAM) applications.
In the field of data compression, dictionary-based compression is one of standard approaches. Its basic idea isto replace patterns appearing in the data with reference topatterns in a dictionary. For instance, text compression isa process of replacing repetitive patterns (words) with reference to words in a given dictionary. In general, the dictionaryof repetitive patterns is given in advance for general purpose
compressor or learned on-the-fly from a given training data
(patterns). Given such a dictionary, patterns in the input data
are replaced by the reference to the corresponding patterns in
the dictionary. Dictionary learning and pattern matching are
two essential tasks for dictionary-based data compression.
In [2], the problem of batch map compression has been
approached from the viewpoint of dictionary-based datacompression [13]. The dictionary learning is formulated as arecursive process of finding repetitive patterns appearing inThis work was partially supported by MECSST Grant in-Aid for Young
Scientists (B) (23700229), by KURATA grants and by TATEISI Science
And Technology Foundation.
T. Nagasaka and K. Tanaka are with Faculty of Engineering, Universityof Fukui, Japan. tnkknj@u-fukui.ac.jp

Fig. 1.
Incremental map compression. The input is a sequence ofsubmaps built by mapper robots during a SLAM task (top figure, 24
submaps, each is distinguished by different colors). A set of datapoints arecompactly represented in the form of compression trajectory, a sequence oftransformed datapoints (middle figure, random 100 examples of compression
trajectories). The incremental map compression is a process of updating a setof compression trajectories by incorporating latest submap (bottom figures,
respectively corresponding to the 1st, 2nd, ..., 24th update).

input maps by employing modified RANSAC map-matchingalgorithms [1]. The main focus of the study was on speedof map compression algorithms as well as compactnessof compressed representations. On the other hand, a main
limitation of the previous approach is the batch assumption
it relies on. It was assumed that the mapping task has
been completed prior to the map-compression task. Such anassumption is violated in the case of SLAM applications,where the map should be incrementally compressed evenduring the map building task. The problem of incremental
compression (while simultaneously building the map) ischallenging due to two requirements: (1) incrementality of
map compressor’s structure and data, and (2) space/time
efficiency of map compression algorithm.
Based on the consideration, this paper focuses on the
problem of incremental map compression. Let us simply
model a map as a sequence of submaps, each is a 2D
pointset map built by a mapper robot during a SLAM
task [14]. Let us consider a parallel setting, splitting the
SLAM and the map-compression (the map-matching) processed in parallel [15]. Our incremental map compression
task is formulated as the problem of finding a compact
representation C(Ot ) of latest submap Ot at time t, givena sequence of compressed submaps C(O1 ), · · ·, C(Ot−1 )obtained so far (Fig.1). Let Size(·) denote the datasize [Byte]of a representation. Compactness is evaluated in terms ofcompression ratio Size(C(O1 , · · · , Ot ))/Size(O1 , · · · , Ot ), theratio of datasize between before and after the compression.
Our incremental map compressor C(·) is composed of two
independent building blocks. One is an incremental scheme
for data structure and algorithm employing RANSAC mapmatching. Another key building block is a visual searchwhich has now become a standard tool for accelerating a
SLAM module [4], i.e. saves data and structure by reusing
such an existing module. We employ the recently developed,
compact projection technique [16] with hashing structure as
an incremental and compact method for visual search, aswell as a compact binary landmark representation [17]. Asa central contribution, we focus on• speed of compression algorithm• compactness of data and structure
in order to facilitate the advanced SLAM applications. Effectiveness of the techniques are evaluated in experiments using
radish dataset [18]. An application of the map compressor
to incremental estimation of the compression distance [9] isalso demonstrated. Improving the compression performanceof a map compressor gives more accurate estimate of thecompression distance.
A. Relation to Other Work
Map matching techniques have now become a key building block for mobile robot applications, including robotic
mapping [19] and robot self-localization [20]. The goal ofmap matching is given a pair of input maps, to find a“best” transformation (rotation, translation) by which one
map maximally overlaps with the other map. RANSAC is astandard approach to the map matching problem [20]. In [15],an “incremental” extension of the RANSAC map matching
was developed to address practical applications of simultaneous mapping and map matching. In [21], the approach was
speeded up by employing visual search techniques.
The basic idea of dictionary-based compression approachis to exploit repetitive patterns, inherent in natural scenes
as well as in man-made environments [22]- [26], in order
to compactly model a scene and recover the missing data.
The approach is motivated by recent progresses in computer
vision techniques, including image recognition [22], compression [23], completion [24], segmentation [12], dating

(a)

(b)

(c)

Fig. 2. Overview. (a) Batch map compression task addressed in [1] [2].
Patterns in the dictionary are recursively explained by smaller patterns. It
was assumed that compression of pattern dictionary is performed after finding repetitive patterns has been finished. (b) Incremental map compression
task addressed in the current paper. It is required that compression has
to be performed while simultaneously finding repetitive patterns. (c) The
incremental map compressor.

[25], as well as super-resolution [26]. Our novel application,
pointset map is one of standard map formats in mobile
robotics. Due to recent progress in robotic mapping, methods
for building pointset maps (e.g. openslam [27]) as well as
datasets (e.g. radish [18]) are publicly available.
In the field of computer graphics, point clouds haverecently become a popular alternative to polygonal meshes
for three-dimensional geometric models. Although the current implementation is described only in 2D, the proposed
approach could generalize to 3D as well.
In network robotics, acquiring dense 3D point clouds byvision sensors, and storing or transmitting them via ratelimited communication channels attract much interest in
recent years. In such a context, compactly modeling the scene
is essential for efficient operations, especially when it comesto high-resolution 3D maps (e.g. point cloud library [28]).
The dictionary-based map compression approach is orthogonal to other potential techniques for map compression,
since the output data is in the same format as the input, i.e.
pointset maps. There exist many such orthogonal techniques,
including point cloud, geometry, time series and light fieldcompression, as well as other coding schemes such as runlength, Huffman, predictive, fractal, etc.
II. M AP C OMPRESSION A PPROACH
This section explains the map compression approach (Fig.
2). II-A reviews the batch map compression task addressedin [1] [2]. II-B presents the incremental scheme. II-C develops an incremental compressor employing the modified
RANSAC map-matching scheme and the compact projection
visual search.

A. Dictionary-based Map Compression [1] [2]As aforementioned, map matching is a basic building
block of a dictionary-based map compressor. A map matching process aims to take a pair of pointset maps L, R as input
and search a “best” transformation (rotation, translation) T
by which L maximally overlaps with R. The overlapping
part A ⊂ L (or B ⊂ R) is viewed as a repetitive pattern. The
input maps L, R are represented by the overlapping parts A, B
as well as the remainder, non-overlapping (difference) parts
L′ , R′ , where
L′ = L \ A, R′ = R \ B.
(1)More formally, for each 2D point PiA in A, there exists
a counterpart point PjB in B that satisfies |PjB − PiA T |2 < ε ,where ε is a preset threshold. For clarity, homogeneous
matrix expression is used for datapoints PiA , PjB and transformation T . Datapoints in A (or B) are not distinguished fromone another, and in such a case, there is no need to memorize
the identifier i (or j) of each datapoint. The threshold ε iscalled spatial resolution of a map-matcher and impacts thespatial accuracy of a map compressor. In implementation,
ε = 0.1m.
Based on the above terminology, ⟨B, L′ , R′ ⟩ is viewed as acompressed representation of the input ⟨L, R⟩ given T . First,
the datasize is smaller in former than in latter:
Size(⟨B, L′ , R′ ⟩) ≤ Size(⟨L′ , R′ ⟩) + 2Size(B) = Size(⟨L, R⟩).
(2)
Second, each point PiA in A can be recovered from a point
PjB in B given T :PiA ≃ PjB T −1 .
(3)
The mappair L, R input to a map matching process canbe either two different maps or two identical maps. In thelatter case, trivial transformations with nearly zero rotationand zero translation are not considered as candidates of thebest transformation.
The batch map compression task (Fig.2a) begins by initializing a set of patterns called “pattern dictionary” D using theoriginal map O as an element pattern, then repeats the mapmatching process until the computation time is exhausted.
Each k-th map matching process takes maps L, R from thedictionary D as input and searches the transformation Tk as
well as patterns B′ , L′ , R′ , then inserts the patterns B′ , L′ , R′ tothe dictionary D. The dictionary D given the transformations
Y can be viewed as a compressed representation of theoriginal map O.
B. Incremental Scheme
Now, we turn to how to implement the above compressor
using incremental data and structure. Given a transformation
Tk output by a map matching process, each corresponding
point pair PiA , PjB gives an approximation
PiA = PjB Tk−1 .

(4)

Given a sequence of transformations T1 · · · Tk , we obtain alength k sequence of approximated datapoints
P(Tk )−1 , P(Tk−1 Tk )−1 , · · · , P(T1 · · · Tk )−1 .

(5)Fig. 3. Compression trajectory. A compression trajectory represents asequence of transformed datapoints. Each point on the trajectory is anapproximation of an original datapoint. The approximation error is smaller
than ε and free from error accumulation.

Exploiting this, we can represent a length k + 1 sequence of
datapoints in a compact form (S P), using a base point P anda length k symbol sequence called compression trajectory
S = “T1 · · · Tk ”

(6)given a set of transformations
Y = (T1 , · · · , Tk ).

(7)

Fig.3 explains compression trajectory. For a raw submap thathas not been compressed yet, S is a null sequence.
A pattern M(∈ D) is represented by a common compression trajectory SM and a set of base points {PM }. Let l M
denote number of the base points of a pattern M, and kM
denote length of the compression trajectory. A set of l M kM
datapoints in a pattern M is represented in a compressed
form:
 M

S
P1M
 .

..
M
M
M
M =  ..
(8)
 , S = “T1 · · · TkM ”.
.
SM

PlMM

It is straightforward to implement the above expression by
employing an incremental data structure. In implementation,a list structure is employed.
Also, the pointset in an original input map O is represented
in an incremental compressed form: ⟨ S1 P1
T1 ⟩..  ,  ..  .
Z = ⟨X, Y ⟩ =  ...
(9).   . 
Sl Pl
Tk
The expressions X,Y can be further compressed by a general purpose compressor exploiting redundancy. In current
implementation, gzip compressor is used.
Since each pattern M in the dictionary represents l M kM
datapoints, there is a relationship:|O| = ∑ l M kM .

(10)

M∈D

According to the relationship, high compression ratio is expected when l M , kM per pattern are large. The characteristics
will be taken into consideration for the map compressor.

C. Incremental Map Compressor
This subsection presents an incremental map compressor(Fig.2). The incremental compressor begins by initializingtimestamps t = 1, k = 1, and initializing the variable Z with
an empty pointset X = 0/ and an empty transformation set
Y = 0.
/ Every time a new submap Ot arrives, the compressor
inserts the corresponding pattern Mt to X
X ← X ∪ Mt

(11)

and repeats the following k-th step until the computation timeis exhausted:
1) Perform map-matching using two identical maps X, X
as input and a transformation Tk as output.
2) Search a set of correspondence ⟨PjB , PiA ⟩ and a transformation Tk , as shown in eqn. (4).
3) Insert Tk to the transformation set Y .
4) For each corresponding point-pair ⟨PjB , PiA ⟩, update thecompression trajectory (S P) of PiA in X byP ←S ← S + “Tk ”
PiA Tk ,

(12)
(13)

then remove the datapoint PjB from X.
In (13), ’+’ is an operation of appending two symbol sequences. The update (12) guarantees the approximation error
being free from error accumulation. The procedure for above
k-th step is summarized in the following.
Algorithm 1: DictionaryBasedCompressiveSLAM
input : Zk = ⟨Xk ,Yk ⟩.
output: Zk+1 = ⟨Xk+1 ,Yk+1 ⟩.
T ⇐ MapMatching (X).
U ⇐ SearchCorrespondences (X, T ).
Y ⇐ InsertSet (Y, T ).
foreach ⟨PjB , PiA ⟩ ∈ U do
PiA .P ⇐ MultiplyMatrix (PiA .P, T ).
PiA .S ⇐ AppendString (PiA .S, “T ”).
X ⇐ DeleteSet (X, PjB ).
end
Speeding up the map-matching process is a key requirement for efficient map compression. In the following, twostrategies for map-matching, RANSAC map matching andthe compact projection visual search are explained.
1) RANSAC map-matching: Map-matching process aims
to take a pair of maps as input and search a best transformation (rotation, translation) by which one map maximallyoverlaps with the other map. RANSAC map matching repeats
the following steps (generation and evaluation of hypotheses)
until the computation time is exhausted [20]:1) Randomly sample a small subset X ′ ⊂ X and generatea hypothesis Tm of the transformation.
2) Compute the score o = ∑Pn ∈X ω (Tm , Pn ) by counting
the number of overlapped datapoints between mappair.
When the process finishes, the hypothesis with highest scorevalue is output as the best transformation. In implementation,

the score function ω (T, P) returns 1 iff there exists a matching counterpart P′ in X which satisfies a matching condition|PT − P′ | < ε or 0 otherwise.
To speed up the RANSAC map-matching, preemption
scheme [29] is also introduced. The preemption scheme(preemptive RANSAC) aims at better allocation of resources
for each point-hypothesis pair (T, P), taking into accountthe tradeoff between diversification and intensification in
the search. We employ so-called preemptive breadth-firstrule which has been successful in robotic mapping andlocalization applications [1] [30] [31]. This strategy employsa decreasing preemption function ρ (n). At the initialization
stage, it randomly permutes the input datapoints 1, · · · , ξ andhypotheses 1, · · · , η , and initializes the score of each m-th
hypothesis om = 0 (1 ≤ m ≤ η ). Then, it iterates the following
n-th step (1 ≤ n ≤ ξ ) until there remains only one active
hypothesis:
1) For each hypothesis m(1 ≤ m ≤ ρ (n)), compute thescore om ← om + ω (Tm , Pn ).
2) Reorder the hypothesis ids so that the range 1, · · · , ρ (n)contains the best ρ (n) active hypotheses according to
the accumulated score om .
The preemption function is in the form:

ρ (n) = ⌊η 2−⌊n/β ⌋ ⌋,(14)

where ⌊·⌋ denotes downward truncation and β is a preset
constant called “block size”. Since the size of hypothesis
set reduces to the half every β -th iteration, the algorithm isapproximately O(β η ) time cost.
2) Visual Search: The visual search aims at searching
repetitive patterns using the local feature descriptor (signature) as a cue. Incrementality and compactness of visual
search are two basic requirements for the simultaneous mapping and map-compression applications. Incrementality is arequirement that insertion or deletion of a database element
incorporating latest measurement should be performed at
a constant cost. We are based on a hash table as a basisof the database structure. Unlike other structures such as
trees, a hash table is essentially an incremental structure.
For instance, locality sensitive hashing (LSH) which exploits
the distance preserving properties of random projections was
successful in SLAM applications, as demonstrated in ourprevious studies [30]. Compactness is a requirement thatthe indexing structure should be compact. The current paper
employs the compact projection (CP) technique with binary
signatures. Compared with LSH which consumes significant
amount of memory, CP achieves 2-3 orders of magnitude
lower space cost [16].
Indexing and query of the compact projection database isa fully incremental process. Let {xi } denote a size n set ofd-dim signature vectors. R denote a k × d random projection
matrix. Each element of R is an independent sample from astandard normal distribution. The compact projection maps
a k-dim signature vector xi to a d-bit compact binary code:
yi = σ (Rxi ),

(15)

0.8

1

decompressed
original

0.8
compression ratio

0.6
datasize [MByte]

20

compressed
original

0.7

0.5
0.4
0.3
0.2

15
0.6

10

0.4

0.2

5

0.1
0

0
0

5

10

15

20

25

0

5

10

update

15

20

25

0

updateFig. 4. An example of compression result. Left: datasize of compressedand original data. Right: compression ratio.
3500

-5

100000

3000

-10

10000

#patterns#patterns

2500
2000
1500

1000

-15
100

1000

-20
980

10
500
0

985

0

200

400

600
800
size [pts]

1000

1200

1400

0

2

4
6
length [pts]

8

995

1000

1005

1010

1000

1002

1004

0.1

0.12

0.14

1015

1020

10
4

Fig. 5. Statistics of repetitive patterns. Left: size of patterns, a cumulative histogram of number of datapoints in each pattern. Right: length ofcompression trajectories, a frequency histogram.
0.85

X
Y
X+Y

0.5
datasize [MByte]

0.75

2

0.6

naive
P
CP
P+CP

0.8
compression ratio

990

1

0.7
0.65
0.6
0.55

0

0.4
0.3

-2

0.2
0.1

0.5

-4

0.45

0
1

10
100
#hypotheses per update

1000

1

10
100
#hypotheses per update

1000

996

Fig. 6. Compression performance. Left: compression ratio of the final
map (i.e. after 24th update) vs. resource (#hypotheses) per update, for four
different map matching strategies “naive”, “P”, “CP” and “P+CP”. Right:
datasize [MByte] of X and Y (for the strategy “P+CP”).

998

1
0.9
0.8
0.7
0.6
0.5
0.4

III. E XPERIMENTS
The proposed approach is evaluated in terms of compression speed, compression ratio, parameter sensitivity, performance comparison with batch scheme [2], as well as thecompression distance application [33]. A length 24 sequence

0.3
0

0.02

0.04

0.06

0.08

0.16

0.18

0.2

Fig. 7. A decompression result. Top: the decompressed map superimposedon the original map. Bottom: accumulative frequency of spatial error [m].
0.85

0.85

without CP
1
2
4
8
16

0.75
0.7
0.65

without CP
1
2
4
8
16

0.8
compression ratio

0.8
compression ratio

where the function σ (v)(∈ {0, 1}) quantizes the projections
according to their signs, - or +. The indexing process maps
a signature to a binary code by (15) and inserts the signature
to a hash table using the binary code as index. The query
process also maps a query signature xQ to a binary code yQ
and then selects from the hash table a set of signatures whose
codes have smallest Hamming distance from yQ .
In implementation, we use shape context descriptor which
has been used for SLAM applications [30]- [31]. In detail,a polar grid with a radius χ with 16 rings and 16 wedges
centered at a given interest point is imposed and 16x16=256
dim histogram is computed by counting the number ofdatapoints falling into each grid cell, and then the histogramis L1 normalized and output as a 256 dim signature vector.
The map-matcher performs one query for every hypothesis generation. In detail, one is randomly sampled fromsignatures within a radius α -bit Hamming ball output by
the compact projection database, and is used as a basis
for hypothesis generation. The projection matrix of CP isgenerated employing a pseudo random number generator,
and its random seed (i.e. O(1) space cost) can be viewed
as a compressed representation of the database structure.

0.6
0.55
0.5

0.75
0.7
0.65
0.6
0.55
0.5

0.45

0.45
1

10
100
#hypotheses per update

P+CP

Fig. 8.

1000

1

10
100
#hypotheses per update

1000

CP

Results for various feature size χ [m] for the CP visual search.

of submaps are generated from 7 datasets “albert”, “fr101”,“fr079”, “kwing1”, “claxton2”, “abuilding” and “run1”, eachis a sequence of ego-motion and laser range measurements.
In detail, each dataset is divided into a set of length γ =1000 measurements and the rest. The result is a 24 small
datasets. Then, each of the 24 small datasets is scan matched
into a pointset map. The result is a length 24 sequenceof submaps and is used as input to the incremental map
compressor. To evaluate compression performance (datasize,
compression ratio), a gzip compressor is employed as atool to estimate datasize of an original map as well as its
compressed representation. The origins of the 7 maps arelocated far apart from each other, although in Fig.1 the maps

0

5

10
15
update2025

η = 10

0

5

10
15
update2025

η = 100

7
6
5

naive
P
CP
CP+P

4
3
2
1
0

5

10
15
update

20

20
15

naive
P
CP
CP+P

10
5
0
0

25

5

10
15
update

20

20
15
10

25

η = 10η = 1000

Fig. 9. Comparison between map-matching strategies, “naive”, “P”, “CP”
and “P+CP”. The vertical axis: average computation time [sec] per update(i.e. per 100 map-matching). The horizontal axis: timestamp t (update ID).

naive
P
CP
CP+P

5
0
0

5

10
15
update

30
20
10
0

5
0

25

0

0.8
0.75
0.7
0.65
0.6

incremental
batch

0.75
0.7
0.65
0.6

0.5
0

10 20 30 40 50 60 70 80 90
total time [sec]03065002

4

6

hypothesis ID

Fig. 10. Comparison between a strategy with CP (“P+CP”) and a strategy
without CP (“P”). The strategy “P+CP” is investigated for several different
settings of the parameters χ and α (0bit, 1bit or 2bit). For clarity, hypotheses
are aligned in the ascending order of their scores. The right figure is a
closeup of the left figure.

0.8
incremental
batch

0.75
0.7
0.65
0.6
0.55

A. Snapshots
Shown in Fig.1 is an example of incremental map compression task. A set of compression trajectories is incrementally built as the mapping task goes on. Global and local
repetitive patterns are found both in the same environment
and in different environments. Overall, the incremental compression result is stable, as shown in Fig.4. Fig.5 shows somestatistics of patterns in terms of size of pointset as well as
length of compression trajectory.
B. Compression PerformanceFig.6 shows the compression performance of the incremental map compressor for four different map-matchingstrategies, naive RANSAC map-matching (“naive”), preemptive RANSAC map-matching (“P”), compact projection(“CP”), and the combination (“P+CP”), for 10 different sizesof hypothesis set η . One can see that two strategies using thecompact projection visual search (“CP”, “P+CP”) outperformthe other two. They reach compression ratio around 0.5 whenη (the number of hypotheses per update) is set larger than
20. The performance gain of the two strategies (over “P”,
“naive”) becomes small when large amount of resources (i.e.
η ) is spent.
The current implementation is not optimized in terms ofcompression ratio. Although it successfully explains the input
point cloud by a smaller point cloud X, the compression of X
is currently not optimized (i.e. a gzip compressor is simply
employed). X could be further compressed by employing

incremental
batch

0.75
0.7
0.65
0.6
0.55

0.5

0.5

0.45

0.45
0

are placed close to each other for the sake of visualization.
The number of iterations of the map-matching process per
update is set 100. The parameters α = 0, χ = 1[m] in default.
All experiments are performed on 2.4GHz Intel CPU and
2GB of RAM.

8 10 12 14 16 18 20
total time [sec]P

0.8

307000compression ratio

0306000

25

0.55

0.5

compression ratio

300000

20

0.8

naive
100000200000hypothesis ID

10
15
updateη = 1000

0.85

0.55

5

0

5

0.9

incremental
batch

compression ratio

score

score

4m,1bit8m,1bit
16m,1bit
1m,2bit2m,2bit
4m,2bit8m,2bit
16m,2bitcompression ratio

4m,1bit8m,1bit
16m,1bit
1m,2bit2m,2bit
4m,2bit8m,2bit
16m,2bitwithout CP
1m,0bit2m,0bit
4m,0bit20
8m,0bit
16m,0bit15
1m,1bit2m,1bit1025

10

η = 100

0.9

100
90without CP
1m,0bit80
2m,0bit
4m,0bit70
8m,0bit60 16m,0bit
50
1m,1bit2m,1bit
40

20

naive
P
CP
CP+P

15

Fig. 11. Map compression cost [sec]. The vertical axis: average computation time [sec] per update (100 map-matching). The horizontal axis:
timestamp t (update ID).
0.85

30

20

computation time [sec]

naive
P
CP
CP+P

computation time [sec]

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1

computation time [sec]

naive
P
CP
CP+P

computation time [sec]computation time [sec]computation time [sec]

0.1
0.09
0.08
0.07
0.06
0.05
0.04
0.03

10 20 30 40 50 60 70 80 90

0total time [sec]

CP

2

4

6

8 10 12 14 16 18 20 22
total time [sec]P+CP

Fig. 12. Incremental vs. batch. Either scheme is investigated for several
different settings of number of hypotheses η . The horizontal axis: computation time [sec] spent. The vertical axis: compression ratio of the final map(i.e. after 24th update).

a general purpose point cloud compressor. Similarly, thecompression of symbols S is not optimized.
Fig.7 reports spatial accuracy of the decompressed map.
The decompressed map is reasonably accurate and the spatial
error is less than the preset spatial resolution, 0.1m.
C. Local Feature Size
In general, local feature size impacts retrieval performanceof the visual search as well as overall performance of the map
compressor. In our case, the size is controlled by the radius
χ [m] of the polar grid. Fig.8 summarizes the compression
performance for P+CP and for CP using 5 different radius χof polar grid. One can see that the performance is maximized
when χ is 8. Overall, better performance is observed when
CP is used than when it is not.
D. Effect of RANSAC map-matchingFig.9 summarizes the time efficiency for RANSAC mapmatching. As also demonstrated in [30], the time cost for
RANSAC map-matching is approximately linear to the number of point hypothesis pairs. Overall, the time cost is lower
when preemption RANSAC is used than when it is not.
E. Effect of compact projection
Fig.10 investigates the effect of the compact projection
visual search. The compact projection aims at improving
quality of hypotheses generated at the hypothesis generation
stage. In Fig.10, we evaluate the quality of each hypothesis interms of the map-matching score assigned by the RANSAC

x0

x1

x3

x2

x4

(a)
3

1.5

relative change

2
NCD

100

abuildingclaxton2
fr079
fr101
kwing1
run1

2.5

1

abuildingclaxton2
fr079
fr101
kwing1
run1

10

1

0.5
0

0.1
0

1

2
update

3

4

(b)

0

1

2
update34(c)Fig. 13.
Incremental estimation of NCD. NCD between mappairs isincrementally estimated while simultaneously building the map. The map
xt (t = 0, 1, 2, 3, 4) is incrementally built by incorporating the five submaps
from “albert”, as shown in Fig.a. The estimate NCD(xt , y) of NCD between
latest map xt and each database map y (“abuilding”, “claxton2”, “fr079”,“fr101”, “kwing1”, “run1”) is incrementally updated at each time t, as shownin Fig.b. Fig.c visualizes relative change in NCD: NCD(xt , y)/NCD(xt−1 , y).
One can see that the NCD score converges even at the early stages of themap building task, e.g. t = 1, 2.

map-matcher. One can see that the quality is clearly improved
when CP is used than when it is not.
F. Map Compression Cost
Fig.11 reports the time cost for incremental map compression tasks. In general, the map compression cost at eachtime t is linear to the number of datapoints in latest X.
An advantage of an incremental scheme is the ability ofamortizing the computational cost over the period of map
building task.
G. Incremental vs. Batch
Fig.12 reports a comparison between the incremental
scheme and a batch scheme presented in [2]. For fair comparison, total of the amortized costs [sec] for the incremental
scheme is compared against the total cost for the batch
scheme. One can see that compression performance of the
proposed fully incremental scheme is comparable to thebatch one.
H. Incremental Estimation of NCD
Application to normalized compression distance (NCD)
is also demonstrated. As described in [2], NCD between
mappair ⟨x, y⟩ is obtained by
NCD(x, y) =Size(Kxy ) − min{Size(Kx ), Size(Ky )}.
max{Size(Kx ), Size(Ky )}(16)

Here, ’xy’ denote concatenation of a mappair, an operation of
merging the two pointsets ⟨x, y⟩ locating one’s origin far apartfrom the other’s. Kz denote the compressed representation ofa given map z. With the incremental compressor, incremental
estimation of NCD is successful as illustrated in Fig.13.
IV. C ONCLUSIONS & F UTURE D IRECTIONS
The primary contribution of this paper is proposal of an incremental scheme for the dictionary-based map compression
approach. An incremental map compressor is developed by
employing the modified RANSAC map-matching and the CP
visual search. Experiments show promising results in termsof incrementality, compression ratio and speed, comparison
against batch scheme as well as an application to the compression distance. The core of the scheme (Algorithm 1) iseasy to implement, in tens of lines of C code, if existing module for map matching (as well as visual search) is reused. The
proposed dictionary-based approach is orthogonal to otherpotential techniques for map compression, since the output
data is in the same format as the input, i.e. pointset maps.
Combining the orthogonal approaches would further improvethe compression performance of the presented approach.
One can image several further extensions and improvements to the dictionary-based compressive SLAM approach.
Important three of them are discussed in the following.
A. Distributed SLAM
Currently, we rely on an assumption that the scenes(submaps) are already perfectly rendered locally. In the
distributed SLAM context, there are paradigms that havenot been addressed in the paper: sub-mapping based on
filtering and sub-mapping based on non-linear optimization.
Robots can share information of their relative submaps inorder to update and improve the current solution. For both,
filtering and non-linear optimization, matrices representing
covariance or factorizations respectively has to be transmitted
if no approximations are applied. It would affect the qualityof the final patterns obtained. Dealing with such more
complex information through networks of transmission withlimited band as well as the inverse process to recover data
would be a direction of future research.
B. Semantic Scene Compression
The compression ratio of a dictionary-based compressor
depends on the type of environment as well as on the
robot’s trajectory. For instance, high compression ratio is
expected in highly structured environments, such as “Manhattan world”-like environments, where points belonging to
the dominant orthogonal planes could be viewed as repetitive
patterns. On the other hand, wilderness scenes are muchless structured. Introducing prior knowledge (such as “lowresolutional map”, “previously visited scenes”, etc) within
the dictionary-based map compression will be presented in
our future paper.
C. Data Association Reuse
An advantage of the map-matching approach is its abilityof reusing the results of data association (e.g. map-matching,visual search) which have been obtained during a SLAM
task. In modern SLAM approaches, submapping methods
perform data association during the process. In most of
the cases, it uses robust matching algorithms able to deal
with different noise levels and spurious. How to reuse that
information into the compression module in order to avoid
part of the map matching process leads to an interesting
research topic.

R EFERENCES[1] Nagasaka Tomoni and Tanaka Kanji. Dictionary-based map compression using modified ransac map-matching. Proc. IEEE Int. Conf.
Robotics and Biomimetics (ROBIO), 2011.
[2] Nagasaka Tomoni and Tanaka Kanji. Dictionary-based map compression for sparse feature maps. Proc. IEEE Int. Conf. Robotics andAutomation (ICRA), 2011.
[3] Juan Nieto, Tim Bailey, and Eduardo Nebot. Recursive scan-matchingslam. Robotics and Autonomous Systems, 55:39–49, 2007.
[4] Mark Cummins and Paul Newman. Accelerated appearance-only
SLAM. Proc. IEEE ICRA, 2008.
[5] Viorela Ila Kai Ni Frank Dellaert, Justin Carlson and Charles E.
Thorpe. Subgraph-preconditioned conjugate gradients for large scaleslam. Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems(IROS), 2010.
[6] Lars A. A. Andersson and Jonas Nygards. C-sam: Multi-robot slamusing square root information smoothing. Proc. IEEE ICRA, pages
2798–2805, 2008.
[7] Emanuele Menegatti, Andrea Zanella, Stefano Zilli, Francesco Zorzi,
and Enrico Pagello. Range-only slam with a mobile robot and awireless sensor networks. Proc. IEEE ICRA, pages 1699–1705, 2009.
[8] Arthur Martens Rene Iser and Friedrich M. Wahl. Localization ofmobile robots using incremental local maps. Proc. IEEE ICRA, 2010.
[9] Manuel Cebrián, Manuel Alfonseca, and Alfonso Ortega. The normalized compression distance is resistant to noise. IEEE Trans.
Information Theory, 53(5):1895–1900, 2007.
[10] Sivic J. and Zisserman A. Video google: a text retrieval approach toobject matching in videos. Proc. IEEE Int. Conf. Computer Vision(ICCV), pages 1470–1477, 2003.
[11] Cyrill Stachniss, Oscar Martinez Mozos, Axel Rottmann, and Wolfram
Burgard. Semantic labeling of places. 2005.
[12] Minsu Cho et al. Unsupervised detection and segmentation ofidentical objects. Proc. IEEE Int. Conf. Computer Vision and Pattern
Recognition (CVPR), 2010.
[13] Willis Lang et al. Dictionary-based compression for long time-series
similarity. IEEE Trans. Knowl. Data Eng., 22(11), 2010.
[14] Shoudong Huang, Zhan Wang, and Gamini Dissanayake. Sparse local
submap joining filter for building large-scale maps. IEEE Transactions
on Robotics, 24(5):1121–1130, 2008.
[15] Tanaka Kanji and Kondo Eiji. Incremental ransac for online vehicle
relocation in large dynamic environments. Proc. IEEE ICRA, 2006.
[16] Kerui Min, Linjun Yang, John Wright, Lei Wu, Xian-Sheng Hua, andYi Ma. Compact projection: Simple and efficient near neighbor searchwith practical memory requirements. Proc. IEEE Int. Conf. CVPR,
pages 3477–3484, 2010.
[17] Ikeda Kouichirou and Tanaka Kanji. Visual robot localization using
compact binary landmarks. Proc. IEEE ICRA, 2010.
[18] Andrew Howard and Nicholas Roy. The robotics data set repository(radish). 2003.
[19] Shoudong Huang, Zhan Wang, Gamini Dissanayake, and Udo Frese.
Iterated slsjf: A sparse local submap joining algorithm with improved
consistency. IEEE Trans. Robotics, Visual SLAM, 2008.
[20] Neira J., Tardos J.D., and Castellanos J.A. Linear time vehicle
relocation in slam. Proc. IEEE ICRA, 1:427– 433, 2003.
[21] Saeki Kennichi, Tanaka Kanji, and Ueda Takeshi. Lsh-ransac: An
incremental scheme for scalable localization. Proc. IEEE ICRA, pages
3523–3530, 2009.
[22] Grant Schindler et al. Detecting and matching repeated patterns forautomatic geo-tagging in urban environments. Proc. IEEE Int. Conf.
CVPR, 2008.
[23] Wee Meng Woon et al. Achieving high data compression of selfsimilar satellite images using fractal. Proc. Geoscience and Remote
Sensing Symposium, 2000.
[24] James Hays and Alexei A Efros. Scene completion using millions ofphotographs. Proc. ACM Trans. Graphics, 26(3), 2007.
[25] Grant Schindler and Frank Dellaert. Probabilistic temporal inference
on reconstructed 3d scenes. Proc. IEEE Int. Conf. Computer Vision
and Pattern Recognition, 2010.
[26] Daniel Glasner, Shai Bagon, and Michal Irani. Super-resolution froma single image. Proc. IEEE ICCV, 2009.
[27] http://www.openslam.org/.
[28] Radu Bogdan Rusu and Steve Cousins. 3D is here: Point Cloud Library(PCL). Proc. IEEE ICRA, 2011.
[29] David Nistér. Preemptive ransac for live structure and motion estimation. Proc. IEEE ICCV, pages 199–206, 2003.

[30] Kenichi Saeki, Kanji Tanaka, and Takeshi Ueda. Lsh-ransac: An
incremental scheme for scalable localization. Proc. IEEE ICRA, pages
3523–3530, 2009.
[31] Ueda Takeshi and Tanaka Kanji. On the scalability of robot localization using high-dimensional features. Proc. IAPR Int. Conf. Pattern
Recognition, 2008.
[32] K. Tanaka and E. Kondo. A scalable algorithm for monte carlo
localization using an incremental e2lsh-database of high dimensionalfeatures. Proc. IEEE ICRA, pages 2784–2791, 2008.
[33] R. Cilibrasi. Statistical Inference Through Data Compression. PhD
thesis, University of Amsterdam, 2007.