waclicense

# WAAW Csound

Steven Yi Victor Lazzarini Ed Costello  Rochester, USA<EMAIL_ADDRESS>Music Department
Maynooth University, Ireland<EMAIL_ADDRESS>Music Department
Maynooth University, Ireland<EMAIL_ADDRESS>
(2018)

###### Abstract

This paper describes Web Assembly Audio Worklet (WAAW) Csound, one of the
implementations of WebAudio Csound. We begin by introducing the background to
this current implementation, stemming from the two first ports of Csound to
the web platform using Native Clients and asm.js. The technology of Web
Assembly is then introduced and discussed in its more relevant aspects. The
AudioWorklet interface of Web Audio API is explored, together with its use in
WAAW Csound. We complement this discussion by considering the overarching
question of support for multiple platforms, which implement different versions
of Web Audio. Some initial examples of the system are presented to illustrate
various potential applications. Finally, we complement the paper by discussing
current issues that are fundamental for this project and others that rely on
the development of a robust support for WASM-based audio computing.

††conference: Web Audio Conference WAC-2018, September 19–21, 2018, Berlin,
Germany.

##  1 Introduction

The Csound sound and music computing system [8] runs ubiquitously in a variety
of platforms from supercomputers to embedded hardware. Since 2013, it has also
been ported to Web browsers [6, 7], originally in two versions: one using an
asm.js codebase and another as a portable Native Client (PNaCl) [12, 10, 4]
module The first of these two implementations took advantage of two
technologies, the Emscripten [13] compiler, and Web Audio. The second version
employed an ahead-of-time compiled bytecode module that was loaded by the
browser as a plugin, and relied on the Pepper API as provided by the PNaCl SDK
to implement audio input and output.

The pure JavaScript (JS) port of Csound could be deployed in any Web Audio-
enabled browser, whereas PNaCl Csound depended on the support for that
technology, which was limited to Chrome and Chromium-based browsers. However,
it was clear that the PNaCl approach was much superior from an audio
programming perspective. Not only it run very closely to native speeds, but
also, since Pepper provided a standard callback audio output interface, it was
capable of much better latencies (down to a 128-frame buffer size). Also, very
importantly, it ran audio processing on a separate thread, which was very
robust and resilient to processing interruptions that might have caused drop-
outs. As far as audio programming on the Web was concerned, PNaCl still
represents a standard against which we can compare other solutions, including
the one discussed in this paper.

With the Emscripten-compiled version, processing was of an order of magnitude
slower than PNaCl. Since it depended on Web Audio for output, it had to run on
its ScriptProcessorNode (SPN), which was neither designed for efficient
processing, nor for low latency. Furthermore, the SPN has a fundamental flaw
in that it runs on the browser main thread, and therefore it is prone to be
interrupted by any graphics that is a little demanding. The only advantage of
this version was its wide support, which allowed code to run on a variety of
browsers and devices (including mobile).

This was the situation until PNaCl was deprecated and its support
discontinued, following which the Csound project also stopped development of
its PNaCl-based port and frontend. More or less simultaneously, support for
another compiler technology began to be introduced. This was Web Assembly
(WASM) [5], which, from the perspective of Csound came as an alternative to
its pure-JS port, using the same SPN infrastructure, but possibly offering
better computing performance.

More recently, after a long wait, the specification for the AudioWorklet (AW)
was finalised in the WebAudio API, and support for it came on stream in the
Chrome browser. This offers an asynchronous alternative to the SPN, which is
supposed to resolve the issues of sharing a thread with graphics/text display.
This paper discusses Web Assembly-based Audio Worklet (WAAW) Csound: an
implementation of the system for the browser platform, which takes advantage
of these two technologies.

The paper is organised as follows: we first detail WASM and its use in the
implementation of CsoundObj.js, the fundamental API used to run Csound in a
browser. We also discuss the porting of csound.js, which is a frontend
originally designed for PNaCl Csound, which has been made to work with
CsoundObj.js and WASM to provide some compatibility with code written for
PNaCl. We then move to introduce AWs within the Csound context. We also tackle
the issue of multiple platforms, given the sketchy support currently enjoyed
by this component of the Web Audio API. The paper concludes with some examples
and a discussion of some up-to-date issues in Web Audio development vis-a-vis
the technologies discussed here.

##  2 Web Assembly

WASM is a solution for the need of a low-level safe, fast, portable, and
compact code for the Web. It addresses the gap left by the presence of JS as
the sole natively supported programming language in this platform. It has been
developed as a collaboration between the major browser vendors and the online
development community seeking a solution for high-performance solutions. Among
these, the case of audio computing is listed as one of the prime targets for
WASM.

In the context of the Web, WASM is embedded in the JS virtual machine. This
takes the static representation of a program, the WASM binary, and
instantiates it for execution. This may begin by invoking an exported function
from the binary instance.

WASM is both a bytecode format and a language with a well-defined (and
compact) abstract syntax [5]. This is structured around a _Module_ , which is
the WASM binary containing definitions for _functions_ , _globals_ , _tables_
, and _memories_. WASM executes as a _stack machine_ , where code for
functions is a a sequence of instructions that operate on an operand stack.

Functions can be invoked through direct or indirect calls. In the latter case,
emulation of function pointers is possible, and calls perform dynamic type
checking. The indirect call mechanism enables simpler support for dynamic
linking. Functions can also be exported or imported from/to a module, through
which a foreign function interface is implemented to provide a communication
with the external (embedding) environment.

The WASM syntax includes the definition for four basic types: two sizes of
integer and IEEE 754 floating-point numbers each, with no distinction between
signed and unsigned integers. It allows for the declaration of local and
global variables of these types.

Memory is provided by a linear array of bytes, which is defined module-wise
and can be grown dynamically. WASM memory is defined to have little-endian
byte order. For security, it is completely disjoint from code space, as well
as the execution stack, so that exploits or bugs have only a limited effect on
an running program.

Finally, an important feature of the WASM language is its representation of
control flow, based on the concept of _structured control flow_. Instead of
allowing simple jumps, which may be unstructured and irreducible, WASM
provides structured blocks where branching occurs as breaks, which can only
take place within a given scope given by the nesting of blocks. This has a
number of benefits, including single-pass validation and compilation.

In practical terms, WASM code can be generated by a C/C++ compiling
environment, for embedding in a JS virtual machine. This bytecode is loaded,
compiled, and invoked via a JS API in three steps:

  1. 1.

A binary module is acquired from a source (disk, network);

  2. 2.

Instantiated;

  3. 3.

Exported functions can then be invoked.

Implementations in JS engines take advantage of a combination of ahead-of-time
and just-in-time compilation to translate bytecode efficiently. The API also
provides means of asynchronous loading and compilation of WASM modules,
through a promise mechanism.

Performance-wise, WASM has been shown to perform in many cases within 10% of
native code and in general, within 50% [5]. It provides a significant
improvement over asm.js, in load time, performance, and executable size. It is
also on average 85.3% of the size of a native x86_64 binary. It appears to
fill the necessary requirements for high-performance applications such as
realtime audio processing, which would make it comparable to PNaCl (as far as
computation is concerned). Provided that support for lower-latency audio IO is
present in realtime-safe conditions, WASM appears to be an excellent solution
for sound and music computing on the web platform.

###  2.1 WASM Csound

WASM Csound is a port of the Csound library built with the Emscripten cross-
compilation tools. The core code has only one dependency, libsndfile, which is
also built for WASM and linked to Csound. Together with the core library, WASM
Csound also includes the code for the CsoundObj, which mediates access to the
underlying Csound API. This is used in CsoundObj.js, where we interface with
the Web Audio API for audio IO, as discussed in [7].

The WASM build is made up of two components,

  1. 1.

The WASM binary module (libcsound.wasm), which is a static build of the Csound
library, libsndfile, and includes CsoundObj (as well as a couple of file
listing utility functions).

  2. 2.

Its JS interface (libcsound.js), generated at link time.

The JS file contains the code that loads the WASM code in the form of a Module
object. Loading can be synchronous or asynchronous and needs to be determined
at link time, when the JS interface is generated. Depending on how we intend
to use the code, we might need to chose one or the other loading method.

At the moment, the Csound API is exclusively accessed through the exported
functions in CsoundObj.c, which wraps the relevant parts of the API. In the
future, it might be a consideration to provide access to the underlying API,
but this has to be considered more carefully. The CsoundObj.js file provides
the access to the exported functions and connects to Web Audio for audio IO,
as mentioned above. In the cases where AW is not available, this uses SPN as
we had done before with asm.js [7] (see Sec. 4 for details).

###  2.2 csound.js

With the demise of PNaCl, Csound support for that technology has also been
retired. In order to maintain compatibility with JS code that used PNaCl
Csound, a port of its frontend, csound.js, has been developed. Built on top of
the CsoundObj API, it provides means to run a single Csound engine per web
page, send Csound code for compilation, access to its software bus channels,
and MIDI input. It also includes support for accessing the sandboxed
filesystem used by Csound, for the loading of source, audio, MIDI, and other
binary files. It provides an alternative to the direct use of CsoundObj,
simplifying the code for a number of use cases. Depending on their
requirements, user applications can be written using the functionality
provided by csound.js or by CsoundObj.js

##  3 Audio Worklets

Audio Worklet (AW) is a new interface provided by the Web Audio API [11] for
the developers to provide scripts establishing custom audio nodes, which will
be executed by a worker thread, rather than the main thread (as in the case of
ScriptProcessor nodes). The potential for this new interface, if implemented
correctly, is to provide a more robust realtime audio support for systems such
as Csound, which employ Web Audio mostly for audio IO, or as an extension of
the built-in unit generators provided by that API.

For an AW to be set up, a pair of objects must be defined, namely an
AudioWorkletNode (AWN) and an AudioWorkletProcessor (AWP). The latter contains
the implementation of the audio processing code, and the former provides an
interface for the main global scope, as a custom AudioNode. Communication with
the global scope is implemented via asynchronous message passing, and audio
processing is synchronous with the rest of the audio graph defined in an
application (Fig. 1).

Figure 1: AudioWorkletNode and AudioWorkletProcessor

###  3.1 CsoundObj.js integration

In order to integrate this new AW functionality, the CsoundObj API has been
redesigned to have a 1:1 relationship with a WASM-backed Node implementation,
either AWN or SPN, as detailed in Sec. 4. The choice of backend defaults to
the best performing option at runtime (AW if available, otherwise fall back to
SPN) though may be overridden if a specific implementation is required.

Developers may work with CsoundObj without understanding the WebAudio API to
create music applications. In this case, CsoundObj will manage the audio graph
of nodes for the developer. Using CsoundObj in this manner follows usage of
other CsoundObj API implementations found in Java on Android and in
Objective-C and Swift on iOS.

Developers may also access the Csound Node (either AudioNode or SPN) that is
backing the current CsoundObj instance. In this scenario, developers use
CsoundObj simply as a Node factory, and take the responsibility for assembling
and maintaining the audio graph themselves.

These two approaches to CsoundObj API usage allow for covering a wide range of
use cases. We hope this encourages Csound users to explore making web
applications with their Csound knowledge, and Web Audio API users to explore
extending their systems with Csound-backed Nodes.

###  3.2 Setting up and registering the AWP

The addModule() method of the audioWorklet object in the AudioContext is used
to set up the AWP in three primary steps into the AudioWorkletGlobalScope:

  1. 1.

Load the WASM binary data

  2. 2.

Load the libcsound.js WASM module loading script. This is generated using
Emscripten (see Sec. 2.1) with the MODULARIZE=1 option.

  3. 3.

Load the CsoundProcessor.js. This is the JS code that loads the WASM module
from the WASM binary, reads native functions to call from JS using cwrap(),
then defines and registers the Csound AWP.

For WASM-backed AWs, there has been difficulty in trying to find ways to get
the WASM binary data to the AWP thread. Following the work done for
WebAudioModules and Faust and in contact with their authors, we have explored
two primary ways to achieve this: encode binary data as JS code that
instantiates a Uint8Array that is passed directly to the module loader; encode
binary data as base64-encoded string embedded in JS code that is decoded to
binary at runtime before being passed to the module loader.

Table 1 shows a comparison of various properties between the two encoding
methods.111The generated WASM was compiled using Emscripten SDK 1.37.37. The
speeds were reported using Chrome 66 on Windows 10, Surface Pro 4, Core
i7-6650U CPU @ 2.20 GHz. While on-disk size was significantly larger for the
Uint8Array encoding, the compressed size delivered over network was only 100
kB difference. The load time222Measured using new Date().getTime() at start
and end of JS files, as this method was available both on the main thread and
AWP thread. shows an order of magnitude difference due to the runtime decoding
of base64 back to binary. Factoring in that the cost for decoding base64 was
required every load, but downloading the JS was likely to be a one time cost
due to caching, we settled on using the Uint8Array implementation (see Sec.
6.2 for further details).

Table 1: Comparison of base64 and Uint8Array encoded WASM Properties Property | base64 | Uint8Array
---|---|---
File Size | 3.9 mb | 8.3 mb
Network Size | 1.5 mb | 1.6 mb
Load Time | 73 ms | 6 ms

###  3.3 Instantiating the AWN/AWP

When a CsoundNode is created on the main thread, the corresponding AWP
(CsoundProcessor) is also created. When the AWPś constructor is executed, a
new native Csound instance is created and ready for use. At this point, the
AWP is ready for processing and the AWN is ready for connection in an audio
graph. If the native Csound instance is not in a running state, the AWP
process() method is a non-op. When Csound is in a running state, the process()
method transfers AWP input to Csound, executes Csound by calling the
CsoundPerformKsmps() API function, then transfers audio output from Csound to
the output buffer channels (Listing 1).

Listing 1: CsoundProcessor process() method

⬇

process(inputs, outputs, parameters) {

if(this.csoundOutputBuffer == null ||

this.running == false) { return true;}

let input = inputs[0];

let output = outputs[0];

let bufferLen = output[0].length;

let csOut = this.csoundOutputBuffer;

let csIn = this.csoundInputBuffer;

let ksmps = this.ksmps;

let zerodBFS = this.zerodBFS;

let cnt = this.cnt;

let nchnls = this.nchnls;

let status = this.status;

for(let i = 0; i < bufferLen; i++, cnt++) {

if(cnt == ksmps && status == 0) {

status = Csound.performKsmps(this.csObj);

cnt = 0;

}

for(let channel = 0;

channel < input.length; channel++) {

let inputChannel = input[channel];

csIn[cnt*nchnls + channel] =

inputChannel[i] * zerodBFS

}

for(let channel = 0;

channel < output.length; channel++) {

let outputChannel = output[channel];

if(status == 0)

outputChannel[i] =

csOut[cnt*nchnls + channel]/zerodBFS;

else

outputChannel[i] = 0;

}

}

this.cnt = cnt;

this.status = status;

return true;

}>>>

###  3.4 Using Csound through the AWN/AWP

As explained in Sec. 3.1, developers may employ the CsoundObj interface to
work with Csound. This involves operations such as setting Csound engine
options, compiling Csound code, starting the Csound engine, and sending
control data and events to a running Csound instance. Methods for these
operations delegate to the AWN, which in turn communicates asynchronously with
the AWP, where they are executed. Alternatively, a CsoundNode may be created
with the static method CsoundObj.createNode() and used as another audio node
in the system.

##  4 Multiple Platforms

Prior to the introduction of AW, WebAudio Csound was released in two
implementations. The original one packaged the CsoundObj API that used SPN and
a native C libcsound compiled into asm.js. The second form, WASM Csound, as
discussed in Sec 2.1, used an identical API but was backed by a WASM libcsound
module. Developers could download one or the other release depending upon the
technology they wanted to support. Developers could also write code to, at
runtime, choose which implementation to load. However, it was the
responsibility of the developer to write their own loading mechanism if they
wanted to have runtime implementation switching.

With the arrival of AW and the ubiquitous availability of WASM, the WebAudio
Csound release has dropped the asm.js form and now includes the two supported
forms: the WASM-backed SPN (aka WASP Csound) or WASM-backed AW (aka WAAW
Csound). The CsoundObj API also now includes all code to detect the platform
and capabilities at runtime and choose to which implementation to use.

We have tested web applications using the current WebAudio Csound on various
desktop and mobile platforms. The AW version is properly loaded in
applications served over HTTPS to browsers that support AW (tested with Chrome
Stable 66 and Chrome Canary 68 on Windows 10 and MacOS; Chrome Beta 66 on
Android). The SPN version is properly loaded when the web application is
served over HTTP or when the browser does not support AW (tested Firefox on
Windows, Linux, MacOS, and Android; MS Edge on Windows 10)333WebAudio Csound
does not properly run on iOS at this time though the authors have found many
other WebAudio applications do not currently function on this platform. We
consider it an ongoing problem to solve..

##  5 Examples

A set of examples demonstrating WAAW Csound have been provided as straight
ports of original WASM and PNaCl Csound pages, which use csound.js and a plain
HTML 5 interface. These demonstrate basic interaction and synthesis, range
from simple sound tests, to interactive synthesis examples, as well as MIDI
and CSD file players. They can be found at

https://waaw.csound.com

As discussed in Sec. 4, these examples will use AW if available (WAAW),
falling back to SPN (WASP) if not, hence they can be used for some head-to-
head comparisons between the two implementations.

###  5.1 Glowing Orbs

“Glowing Orbs”444https://kunstmusik.github.io/csound-p5js is an example web
application project that demonstrates building a generative multimedia program
using Csound for audio and p5.js555http://p5js.org for animation. It is an
example program designed to function as a template for users to download,
customise, and use to create their own interactive, multimedia web programs.

Originally developed with WASM Csound using SPN, the program ran fairly well
but suffered from two primary issues due to both audio and animation (via
p5.js) being rendered in the main thread. Firstly, the audio could break up if
the animation took up too much time. This was evident during development and
facilitated changes to reduce the number of orbs to use on the screen to
ensure there was enough rendering time for the audio to avoid breakups.
Secondly, the video frame rate could slow down if the audio took up too much
time. This was clearly seen on more resource-constrained platforms, such as
Android.

Switching to WAAW Csound, we found that using the AW path successfully
provided the expected benefits to render audio separately from the main
thread. Audio rendered well and video animation was much smoother compared to
the original implementation. We have observed a similar improvement in other
examples that used moderate amounts of graphics rendering, such as for
instance in the display of console messages from Csound.

###  5.2 live.csound.com

The live.csound.com666https://live.csound.com website is a Progressive Web
Application (PWA)777https://developers.google.com/web/progressive-web-apps/
that provides a full Csound livecoding environment in the browser. Users can
program in Csound code using the included livecode.orc
framework888https://github.io/kunstmusik/csound-live-code as well as employing
any other standard Csound programming practices. The web application may be
installed to users’ devices, such as Android phones, and run offline.

Using the application with WAAW Csound, we found that we no longer had to
worry about interactions with the text editor interfering with sound
processing. This matched our expectations for the benefits of AW design over
SPN as well as matched the behaviour we enjoyed previously with PNaCl Csound.
We also verified that the AW implementation worked equally well when running
offline. Our initial experiences with integrating WAAW Csound with
live.csound.com have been positive and we look forward to exploring the area
of PWA music applications further using Csound.

##  6 Current Issues with AW

As noted in Sec. 3, AW is a very recent addition to the Web Audio API. As
such, at the time of writing, they have only been implemented by the Chromium
project and deployed for the first time in Chrome 66. This first
implementation has a number of teething issues, which have been the subject of
discussion between a group of early adopters of the technology (which includes
these authors) and Chromium project developers. The major issues can be
classed into two categories: (a) audio computing, and (b) WASM integration.

###  6.1 Audio Computing

Early adopters of AW have noticed intermittent drop-outs in the audio stream.
Since the promise of the technology was exactly to provide a robust and
resilient environment for JS (and now WASM)-generated audio, this is clearly a
significant issue. Two related difficulties seem to have been identified:

  1. 1.

Thread priority.

  2. 2.

Garbage collection.

In the V8 engine provided by the Chromium project, there are four levels of
priority: BACKGROUND, NORMAL, DISPLAY, and REALTIME_AUDIO. The thread in which
an AW runs is scheduled with DISPLAY priority, whereas native nodes run at
REALTIME_AUDIO priority. This has been identified as less than ideal, and a
proposal to move AW to REALTIME_AUDIO has been put forward. There is
resistance to this, arising from security concerns, so it is not clear at the
time of writing whether the proposal will be accepted.

Running at DISPLAY priority might still be a reasonable proposition if it were
not for the fact that the JS engine garbage collector (called Oilpan in V8)
seems to be getting in the way of audio computing. As it stands, the AW thread
appears to invoke garbage collection on a regular basis; moreover, this needs
to be synchronised with garbage collection in other threads. A programmatic
example that places garbage collection pressure on the main thread, prepared
by these authors, has demonstrated clear break-ups in the audio stream when
computing a simple sine wave in WAAW Csound.

It is reported that audio buffers are allocated at every audio cycle [2].
Allocation is from a memory pool, so in itself might not be too problematic
but it means that garbage collection is involved in the process. From the
point of view of realtime time audio [1], this is really unsatisfactory, but
from the perspective of implementors, nothing in the specification explicitly
prohibits it.

The major question to be asked is whether the Web Audio design for AW should
have included more stringent specifications for realtime operation. In fact,
we should have expected a level of realtime safety that is comparable to
native node implementation. We would for instance like to have a lock-free AW
thread, which given the level of difficulties involved seems at the moment to
be unachievable.

In the end, it is accepted that the Web platform, as implemented by a JS
engine, is not designed as a realtime system [3]. All we can do is mitigate
the issues that arise from a general-purpose computing environment where audio
is not anywhere the main concern.

The regrettable aspect of this situation is that five years ago we already had
an audio computing environment for browsers that offered realtime safe
operation, in the form of PNaCl modules using the Pepper audio API. At the
first Web Audio Conference in 2014, these and other authors demonstrated
systems that took advantage of that technology to provide robust audio
computing solutions. At that time, AW (more specifically, its design
predecessor AudioWorkerNode) was a near-future promise that would
prospectively solve many of the existing problems for non-builtin audio
processing in Web Audio. More than four years later, this goal has not yet
been fulfilled, and an alternative has been discontinued. Such issues with the
Web Audio API development have been already noted elsewhere [9]. However, it
remains the only means of audio IO provided in the web platform for
foreseeable future, therefore we are committed to contributing to the search
for workable solutions.

###  6.2 WASM support

Using WASM with AW is straightforward, once the binary module has been
instantiated and available to use within the AWP thread. However, loading and
compiling the WASM binary is more complicated than we would have liked.

Ideally, we would deploy a single WASM binary and loader script that could be
used for both AW and SPN versions of Csound. The idea is that we might
initiate loading, compilation, and instantiation of the WASM module from the
binary either in the main thread for SPN or AWP thread for AW.

However, this is not currently possible as we found two conflicting
requirements. Firstly, compiling WASM within the AWP thread requires that
Module compilation be done synchronously. Secondly, compiling WASM for use
with SPN requires it be done asynchronously (e.g., Firefox 59.0.2 on Android
throws an error if synchronous WASM compilation is attempted from the main
thread). As a result, until all of the major browsers support AW, we will need
to package two WASM binaries and JS loader scripts to make our WebAudio
Csound-based applications operate as widely as possible.

Next, because code within the AWP thread cannot use standard JS loading
methods like fetch()999See https://github.com/WebAudio/web-audio-
api/issues/1439 for more information about the reasons for this., we had to
consider how to get the binary data to the AWP thread for it to compile and
instantiate the WASM Module object. Following the work of the community, we
went with a method to encode the WASM binary into Javascript code that creates
a Uint8Array. The generated JS file is then used with the addModule() method
of the audioWorklet object to have that loaded in the AWP thread. The
resulting variable is then used with the WASM loader script for libcsound that
results in synchronously compiling and instantiating the Module from the
binary data.

Other loading methods have been proposed. One method is to first instantiate
an AWN/AWP and then transfer WASM binary data or compiled module to the node
through its MessagePort. This might work but complicates the
loading/instantiation as one has to split construction of the AWN/AWP into two
phases: one phase when the constructor is called and another phase after the
node has received WASM data. This is not a solution we found attractive.

Another solution is to pass WASM data to the AWP constructor through the AWN
processorData constructor argument. This is reported to be
working101010https://bugs.chromium.org/p/chromium/issues/detail?id=808848 in
Chrome Canary (an unreleased, development version of Chrome) but requires a
special flag to allow it to work. At this time, we are monitoring the status
of this change and its presence in upcoming release versions of Chrome.

For the short term, we have settled on using the Uint8Array JS solution. This
solution works well in desktop Chrome 66 browsers, Android Chrome 66, and in
Chrome OS 66. The process to encode the WASM into JS is, in our opinion, a
hack to deal with an awkward situation, but we will continue to use it until a
better solution becomes commonly available.

##  7 Conclusions

This paper described the implementation of Csound under WASM and AW. Building
on five years of previous work, we have been able to provide a generally
stable and usable implementation, which we will hope will be improved as some
of the key hurdles in AW implementation get overcome. Despite the difficulties
encountered with the early implementation of the interface in the Chrome
project, we found that there is good potential for development. Taking
PNaCl+Pepper as a standard for audio programming support on the Web Platform,
we have found that AW is going in the right direction, providing a much
improved environment when compared to the original SPN. In particular, we have
found that the combination of audio and graphics has had significant gains in
performance.

Finally, we would like to note that Csound is free software, and the source
code, plus all building scripts, is available publicly at

https://csound.com

The WebAudio Csound implementation as described in this paper has been first
introduced in version 6.11.

##  8 Acknowledgments

The authors would like to thank Jari Kleimola, Oli Larkin, and Stéphane Letz,
early adopters of the WASM+AW technology, for the useful discussions and
sharing of experiences. We would also like to note the support of Hong Chan
from the Chromium project, and his patience in listening to our requests and
suggestions. Finally, we would also like to thank Henri Manson who contributed
to the WASM Csound port effort.

## References

  * [1] R. Bencina.  Real-time audio programming 101: time waits for nothing.  http://www.rossbencina.com/code/real-time-audio-programming-101-time-waits-for-nothing.  Accessed 25.04.2018.
  * [2] H. Chan.  Comment 23 on Chromium issue 836306.  https://bugs.chromium.org/p/chromium/issues/detail?id=836306#c23.  Accessed 28.04.2018.
  * [3] H. Chan.  Comment 32 on Chromium issue 836306.  https://bugs.chromium.org/p/chromium/issues/detail?id=836306#c32.  Accessed 28.04.2018.
  * [4] A. Donovan, R. Muth, B. Chen, and D. Sehr.  PNaCl: Portable Native Client Executables.  Google White Paper, 2010.
  * [5] A. Haas, A. Rossberg, D. L. Schuff, B. L. Titzer, M. Holman, D. Gohman, L. Wagner, A. Zakai, and J. Bastien.  Bringing the Web up to Speed with WebAssembly.  SIGPLAN Not., 52(6):185–200, June 2017.
  * [6] V. Lazzarini, E. Costello, S. Yi, and J. ffitch.  Csound on the Web.  In Linux Audio Conference, pages 77–84, Karlsruhe, Germany, May 2014.
  * [7] V. Lazzarini, E. Costello, S. Yi, and J. ffitch.  Extending Csound to the Web.  In 1st Web Audio Conference, IRCAM, Paris, 2015.
  * [8] V. Lazzarini, J. ffitch, S. Yi, Ø. Brandtsegg, J. Heintz, and I. McCurdy.  Csound: A Sound and Music Programming System.  Springer, Berlin, 2016.
  * [9] V. Lazzarini, S. Yi, and J. Timoney.  Web Audio: Some critical considerations.  In Proceedings of the VI Ubiquitous Music Workshop, Växjö, Sweden, 2015.
  * [10] D. Sehr, R. Muth, C. Biffle, V. Khimenko, E. Pasko, K. Schimpf, B. Yee, and B. Chen.  Adapting Software Fault Isolation to Contemporary CPU Architectures.  In 19th USENIX Security Symposium, 2010.
  * [11] W3C.  Web Audio API Editor’s Draft, 19 April 2018.  https://webaudio.github.io/web-audio-api.  Accessed 25.04.2018.
  * [12] B. Yee, D. Sehr, G. Dardyk, J. B. Chen, R. Muth, T. Ormandy, S. Okasaka, N. Narula, and N. Fullagar.  Native Client: A Sandbox for Portable, Untrusted x86 Native Code.  In 2009 IEEE Symposium on Security and Privacy, 2009.
  * [13] A. Zakai.  Emscripten: An LLVM-to-JavaScript Compiler.  In Proceedings of the ACM International Conference Companion on Object Oriented Programming Systems Languages and Applications Companion, OOPSLA ’11, pages 301–312, New York, NY, USA, 2011. ACM.


# PSE-Match: A Viewpoint-free Place Recognition
Method with Parallel Semantic Embedding

Peng Yin1, Graduate Student Member, IEEE, Lingyun Xu1∗, Ziyue Feng3,
Anton Egorov2 and Bing Li3, Member, IEEE Manuscript received July, 2020;
revised February, 2021; accepted August, 2021.
This work was supported in part by the U.S. Department of Transportation
(grant 69A3551747117) through University Transportation Center - Center for
Connected Multimodal Mobility (C2M2) at Clemson University.
Peng Yin and Lingyun Xu are with the Robotics Institute, Carnegie Mellon
University, Pittsburgh, PA 15213<EMAIL_ADDRESS>hitmaxtom@gmail.com). Anton Egorov is with the Skolkovo Institute of Science
and Technology, Moscow, 121205, Russia. (Anton.Egorov@skoltech.ru). Ziyue Feng
and Bing Li are with the Department of Automotive Engineering, Clemson
University International Center for Automotive Research (CU-ICAR), Greenville,
SC 29607 USA. (e-mails: zfeng, bli4@clemson.edu).
* Lingyun Xu is the corresponding author (hitmaxtom@gmail.com).

###### Abstract

Accurate localization on the autonomous driving cars is essential for autonomy
and driving safety, especially for complex urban streets and search-and-rescue
subterranean environments where high-accurate GPS is not available. However
current odometry estimation may introduce the drifting problems in long-term
navigation without robust global localization. The main challenges involve
scene divergence under the interference of dynamic environments and effective
perception of observation and object layout variance from different
viewpoints. To tackle these challenges, we present PSE-Match, a viewpoint-free
place recognition method based on parallel semantic analysis of isolated
semantic attributes from 3D point-cloud models. Compared with the original
point cloud, the observed variance of semantic attributes is smaller. PSE-
Match incorporates a divergence place learning network to capture different
semantic attributes parallelly through the spherical harmonics domain. Using
both existing benchmark datasets and two in-field collected datasets, our
experiments show that the proposed method achieves above 70% average recall
with top one retrieval and above 95% average recall with top ten retrieval
cases. And PSE-Match has also demonstrated an obvious generalization ability
with limited training dataset.

###### Index Terms:

3D Place Recognition, Semantic Embedding, Divergence Learning, Global
Localization, Place Feature Learning

##  I Introduction

Mapping and localization are fundamental functionalities for autonomous
driving, and have been well explored over the past decade [1]. The autonomous
driving system usually includes localization module [2], perception module
[3], planning and control modules [4]. As one of the core module of
simultaneously localization and mapping (SLAM), robust place recognition
ability can increase the localization accuracy by reducing odometry drift via
providing re-localization within a given prior map (a.k.a robot kidnapped
problem). However, place recognition is still a challenging task due to the
scene variation caused by dynamic environments, appearance and layout changes
from different viewpoints. In the above extreme scenarios, robust re-
localization is one of the main bottlenecks for autonomous driving.

Figure 1: 3D place recognition under variant viewpoints and dynamic
environments is a challenging problem. PSE-match can achieve viewpoint-free
place recognition by leveraging different static 3D semantic attributes
through a parallel semantic embedding network. We further introduce a
divergence-metric learning module to explore various perspectives through
different semantic embedding networks.

Visual localization and place recognition have been significantly explored in
the computer vision community. Many existing researches adopt local keypoints
and global appearance by overcoming the differences of perspective in place
recognition. FAB-MAP [5] and ORB-SLAM [6] utilize Bag-of-visual-Words (BoVW)
[7] as place recognition module to encode each keyframe into an order-
invariant vocabulary tree for local features [8, 9]. Appearance-based methods,
such as NetVLAD [10] and SeqSLAM [11], compress single or continuous frame
images into a global scene identifier to improve the robustness under
perspective variations. However, there are vast differences between keypoint-
based local features in perspective transformation. On the other hand, the
state-of-the-art appearance-based methods can only deal with limited
perspective differences with regarding to translation or orientation. Compared
with visual camera features, 3D Light-Detection-and-Ranging (LiDAR) sensing
data are more consistent for environmental changes and viewpoints differences.
SegMap [12] mainly consider extract different 3D segments for place
recognition, but the limitation for this method is that they need rich 3D
geometry structures for segment extraction, which cannot be always satisfied.
With the advanced 3D deep learning (e.g. PointNet [13, 14]), many recent
researches [15, 16, 17] employ place descriptors from PointNet-based feature
extraction and achieve top scene recognition performance results in open
datasets. Since the original PointNetVLAD [15] method and its variants are
mainly designed to handle the interference of translation movement for scene
recognition, the aforementioned point-based methods are often unable to
overcome the interference from both translation and orientation changes at the
same time.

Therefore, we propose PSE-Match, a viewpoint free 3D scene recognition method.
Our proposed method can handle both locally translation-(XY-plane) and
orientation-(heading) differences simultaneously through the spherical
convolution. Besides, since the accuracy and stability of place recognition
model are profoundly affected by robot’s trajectory, we also design a dynamic
octree mapping method to generate stable local map for inferencing. Our method
utilizes a parallel semantic embedding network to encode different semantic
attributes into independent place descriptors. The detected semantic
attributes enable robust features extraction, thus more reliable consistency
for feature matching using only the static information. In addition, it allows
our feature extraction model to learn different semantic factors
independently. As shown in Fig. 1, we extract four semantic attributes for the
point-cloud, including roads, buildings, static objects, and dynamic objects
(e.g., cars and pedestrians). We only choose non-dynamic ones for feature
extraction to avoid the disturbance from dynamic environments. Thus, the
extracted feature descriptors can take advantage of semantic attributes by
avoiding dynamic disturbance and improving semantic constraints. The main
contributions of this paper include the following:

  * •

A viewpoint-free 3D place recognition pipeline that simultaneously leverage
the viewpoint-invariant place features from different semantic attributes.

  * •

A parallel semantic embedding network that encode semantic attributes into
place descriptors through a spherical convolution network, which can extract
orientation-invariant descriptors from spherical projections.

  * •

A divergence learning metric to enhance the extracted place descriptors
invariant to locally translation viewpoints difference, where individual
attributes are more consistent than entire scenarios in translation variants.

  * •

Demonstration of the limitation of the state-of-the-art LiDAR-based place
recognition approaches that are either focusing on orientation- or
translation-invariance, while real large-scale place recognition tasks are
with both changes.

We conducted a comprehensive recognition performance analysis on two public
datasets, and two in-field collected datasets under orientation-translation
difference. The proposed method achieves higher precision-recall than existing
LiDAR-based place recognition methods. The remaining of the paper is
structured as follows. In Section II, we conduct a survey for 3D place
recognition approaches and semantic-enhanced place recognition methods.
Section III introduces the overall of the proposed method, and elaborates the
details of PSE-Match design. Experimental setup and performance analysis on
different datasets are presented in Section IV, and quantitative analysis and
comparison are conducted between PSE-Match and current state-of-the-art place
recognition methods. Section V concludes the results and discusses the future
works.

##  II Related Work

A holistic review for 3D-based place recognition methods is presented in this
section. For general 3D place recognition using geometric information,
handcrafted and statistic-based features have been broadly explored, and
learning-based features were also introduced to improve the feature
robustness. More recently, 3D semantic-enhanced place recognition shows the
potential of higher accuracy by enhancing the feature descriptor retrieving
and matching.

Unlike SIFT [18] and SURF [19] in image fields, hand-crafted features for the
3D point-cloud did not achieve such great success. Keypoint based feature
Spin-image [20], distance and angle based feature ESF [21], structure based
Scan Context[22], and histogram-based feature SHOT [23] are both focused on
local areas and not suitable for extracting global descriptors. Fast Histogram
[24] uses a histogram to represent the entire point-cloud distribution, M2DP
[25] projects all points to several planes, they are designed to obtain a
global descriptor, however, requires high density and complete data, and
sensitive to noises. Recently, learning-based point-cloud descriptors have
shown outstanding performance and gradually replacing handcraft features. With
the breakthrough of the convolutional neural networks, NetVLAD [10] provides a
successful learning-based paradigm to aggregate local features to form a
global descriptor. Since the NetVLAD [10] only accepts 2D image inputs, to
leverage the illumination invariant advantage of the LiDAR sensor,
PointNetVLAD [15] incorporates the iconic point-cloud processing network
PointNet [13] to achieve an end to end learning-based point-cloud global
feature extractor. To further improve the performance of the PointNetVLAD
[15], PCAN[16] adds a context-aware attention module to give different weights
to different contributing contexts, LPD-Net[17] uses the PointNet++[14] to
introduce more multi-scale feature extracting ability.

These PointNet [13] and PointNet++ [14] based methods are translation-
invariant, but sensitive to orientation changes. LocNet [26] uses a handcraft
rotation-invariant intermediate representation as input, but it lost too much
information from the original point-cloud. SphereCNN [27] introduced a
spherical convolution to efficiently obtain orientation-equivariant features.
Inspired by it, we project the point-cloud with semantic information to a
sphere space to get the orientation-equivariant features from spherical
harmonics, then use a feature clustering operation to convert it to
orientation-invariant global descriptors.

Most of the existing place recognition methods are based on pure geometric or
appearance information, which can’t provide conceptual knowledge to support
high-level complex tasks, and sensitive to illumination, season, and view
point changes. With the vigorous development and satisfactory performance of
the deep learning based 2D [28] and 3D [29] semantic segmentation
technologies, incorporating semantic information to achieve robust and
accurate place recognition becomes possible. Semantic information is much more
robust than appearance information. Johannes’s work [30] proves that semantic
features from 2D images can achieve successful localization under extreme
appearance changes, which is challenging for appearance-based features. There
are many works use semantic information to enhance feature descriptors. Garg’s
work [31] concatenates the appearance-based descriptor and the semantics-based
descriptor, then normalize it to get the final global descriptor.

In our work, we extract the 3D segmentation via SqueezeSeg [32] and project
the semantic segmentation result along with geometry to the sphere space to
extract orientation-invariant global feature descriptor, which enhances place
features robustness by focusing on different types of semantics.

##  III The Proposed Method

###  III-A Overview

As depicted in Fig. 2, the framework of PSE-Match is mainly composed of three
modules: Dynamic Octree mapping (DOM), Parallel Semantic Embedding (PSE), and
Divergence enhanced Feature Learning (DFL). Because of the sparsity of a
single LiDAR scan, we implement a dynamic octree mapping mechanism to generate
dense local maps. By applying a modified LiDAR Odometry method [33] to
estimate the transformation information for sequences of LiDAR inputs, and we
generate a dense local map for each place by accumulating LiDAR scans via an
octree mapping procedure [34]. In Parallel Semantic Embedding networks, we
collect semantic attributes from a pre-trained 3D segmentation network [32]
and parallelly extract semantic-independent descriptors by designing a
spherical convolution network.

Finally, the learned descriptors are further enhanced by a divergence learning
metric, which can explore the different semantic attributes in viewpoint-free
place feature learning.

Figure 2: The framework pipeline of PSE-Match. The framework mainly includes
three modules: a dynamic octree-based mapping method for dense map generation
(dashed-blue block), a parallel semantic embedding module for place descriptor
extraction (dashed-green block), and a divergence metric-based viewpoint-free
feature learning module to incorporate different aspects learned from the
parallel semantic embedding (dashed-red block).

###  III-B Dynamic Octree Mapping

The single scan of LiDAR input is too sparse to extract valid appearance
feature, here we utilize a dynamic octree data structure to incrementally
generate the dense local map from continuous frame scans. An octree is a tree
type data structure, where the sub-children of a parent node divide the space
into eight equal ones until the size of a leaf node reaches a given
granularity. DOM models the local map around the robot coordinate by fixing
the map scale and updating the map based on the odometry estimation. Odometry
error between maps $M_{t-1}$ and $M_{t}$ may introduce additional uncertainty
for each leaf node’s occupancy, which leads to mapping blurring problem. This
problem can be alleviated using our dynamic octree mapping mechanism by taking
into account of odometry uncertainty for the map updating. We first describe
the map measurement updating step in static octree updating by accumulating
LiDAR inputs, then introduce dynamic octree updating method with the
additional motion updating step.

####  III-B1 Measurement Updating

In traditional octree mapping method [34], the occupancy beliefs of leaf nodes
are updated by the log-odds method described in [35]. For the leaf node $n$
with given sequential measurements $z_{1:t}$, the occupancy estimation
$P(n|z_{1:t})$ can be calculated by

$\displaystyle P(n|z_{1:t})=$
$\displaystyle[1+\frac{1-P(n|z_{t})}{P(n|z_{t})}\cdot\frac{1-P(n|z_{1:t-1})}{P(n|z_{1:t-1})}\cdot\frac{P(n)}{1-P(n)}]^{-1}$
(1)

where $P(n)$ is the prior occupancy probability for the leaf node $n$, and
$P(n|z_{t})$ is the occupancy belief based on the current observation. The
log-odds function $L(x)$ over a probability distribution $P(x)$ is defined by

$\displaystyle L(x)=\log[\frac{P(x)}{1-P(x)}]$ (2)

Without loss of generality, we can assume the initial occupancy $P(n)$ is
$0.5$, we can combine Eq. 1 and Eq. 2 into

$\displaystyle L(n|z_{1:t})=L(n|z_{1:t-1})+L(n|z_{t})$ (3)

Then, the original occupancy updating problem is now transformed into a linear
accumulation operation. This mechanism guides us in map center updating, where
we need to modify the occupancy of each voxel based on the odometry
estimation.

Figure 3:  Map updating in the Dynamic Octree Mapping (DOM). Except the
measurement updating step in traditional octree mapping method, DOM contains
an additional motion updating step. The first row shows 3D voxel changes
during these two steps, the second row shows inner changes of octree
structure, and the third row shows the changes of occupancy probability of
occupied leaf nodes under different motion error and measurement error. In the
additional motion updating step, the occupancy of octree maps are further
modified according to the covariance of estimated robot position according to
Eq. 4.  Figure 4: The network structure of PSE-Match. The training procedure
of method includes the parallel semantic embedding step and a divergence
learning step. In the parallel semantic embedding step, we only embed the
static objects (i.e., ground, building and man-made structures) for
orientation-invariant place feature learning. In the divergence learning step,
we introduce two learning metrics: a viewpoint-free metric learning which
shorten distances of features with only orientation- or locally translation-
differences, and a regularization loss metric to capture different semantic
aspects of original 3D point-cloud.

####  III-B2 Motion Updating

We cope with the motion updating error by modifying the log-odds updating in
the occupancy updating step in Eq. 3. In the motion updating step, the
occupancy of each leaf node from map $M_{t-t_{p}}$ to map $M_{t}$, is updated
with a motion error model $\mathcal{N}_{M}(0,\sigma_{t_{p}})$. The covariance
$\sigma_{t_{p}}$ can be evaluated based on the LiDAR odometry estimation
results [36], and the more aggressive the motion, the larger the covariance
value. A high confidence map can be obtained when vehicles travel in flat
areas smoothly and vice versa. Then we can update the original log-odds
${L}(n|z_{1:t})$ by incorporating additional motion error

$\displaystyle\hat{L}(n|z_{1:t})=L(n|z_{1:t})\cdot\mathcal{N}_{M}(0,\sigma_{t_{p}})$
(4)

Referring to the new log-odds $\hat{L}(n|z_{1:t})$, the new occupancy
$\hat{P}(n|z_{1:t})$ can be updated with Eq. 4,

$\displaystyle\hat{P}(n|z_{1:t})=\frac{\exp(\hat{L}(n|z_{1:t}))}{\exp(\hat{L}(n|z_{1:t}))+1}$
(5)

Since $\|\hat{L}(n|z_{1:t})\|\leq\|L(n|z_{1:t})\|$, by comparing the original
$P(n|z_{1:t})$ with updated probability $\hat{P}(n|z_{1:t})$, we have,

$\displaystyle P(n|z_{1:t})>0.5\Rightarrow
P(n|z_{1:t})>\hat{P}(n|z_{1:t})>0.5$ (6) $\displaystyle
P(n|z_{1:t})<0.5\Rightarrow P(n|z_{1:t})<\hat{P}(n|z_{1:t})<0.5$

Therefore, based on Eq. 5 and Eq. III-B2, the new updated probability
$\hat{P}(n|z_{1:t})$ reduces the occupancy beliefs for both occupied and
unoccupied leaf nodes, i.e., the motion error model
$\mathcal{N}_{M}(0,\sigma_{t_{p}})$ introduce uncertainty in the motion
updating step. Therefore, in the case of low odometry confidence, the map
updating can be alleviated through this step.

###  III-C Parallel Semantic Embedding

In this section, we will describe the three modules for parallel semantic
embedding: semantic spherical projection, spherical feature extraction and
place feature aggregation. The conventional spherical projection for all the
point-clouds will loss geometry information of the original 3D point-cloud
data [27]. In stead, we propose a novel approach of constructing a multi-layer
spherical projections from different semantic attributes. It allows
independent semantic attribute feature extraction, while maintaining the
synergy of all attributes in the divergency learning as shown in section
III-D.

####  III-C1 Semantic Spherical Projection

In our PSE-Match, we project the 3D point-cloud on spherical perspectives for
viewpoint-free feature extraction. The attributes are extracted by a pre-
trained 3D semantic segmentation network [32], and have high consistence to
environmental changes. As we can see the first module in Fig. 4, we extract
semantic elements, e.g., ground, structures and man-made objects as static
objects; on the other hand, dynamic objects, such as cars and pedestrians etc,
are ignored at the early stage of PSE-Match. We generate a two-channel
spherical representation for each static semantic attribute. We define
spherical image $S^{2}$ as the set of points $x\in\mathbb{R}^{3}$ in the unit
sphere. We can parameters $S^{2}$ by spherical coordinates $\theta\in[0,2\pi]$
and $\phi\in[0,\pi]$. Given a resolution $n$, we divide the flattened sphere
plane into $n\times n$ equiangular spherical grids indexed by
$(\theta_{i},\phi_{j})$. Here $\theta_{i}=2\pi{i}/n,\phi_{j}=\pi{j}/n$,
$0\leq{i,j}\leq{n-1}$. We take $d_{ij}$ which is the distance from center to
the closest point in spherical grid $(\theta_{i},\phi_{j})$ as the first
channel. Using sine value of the angle $\alpha_{i,j}$ between ray towards the
closest point and normal direction in spherical grid $(\theta_{i},\phi_{j})$,
we get the second channel. Formally, the two-channel spherical representation
$z_{A_{l}}$ of the semantic attribute $A_{l}$ can be written as:
$z_{A_{l}}(\theta_{i},\phi_{j})=[d_{ij},\sin{\alpha_{ij}}],0\leq{i,j}\leq{n-1}$.

Figure 5: The spherical convolution module. With the given spherical feature
$f$ and a kernel signal $h$, we first transform them into the harmonic domain
($H_{f}$, $H_{h}$)with the Fast Fourier transform (FFT) and Discrete Fourier
Transform (DFT) respectively. In spherical convolution, the convolution
operation is equal to the point-wise product of harmonic coefficients, and the
shperical feature outputs can be formulated by Inverse Fast Fourier Transform
(IFFT) operation.

####  III-C2 Spherical Feature Extraction

Representing data in the spherical domain can be quite natural and effective
in analyzing 3D point-cloud; however, it is difficult to adopt traditional
planner convolution network in such manifolds, because the spaces between
adjacent points in the spherical domain are not uniform. Instead of planner
convolution, we apply the spherical convolution on the spherical
representations for orientation-invariant feature extraction. Spherical
convolution avoids space-varying distortions in the Euclidean space by
convolving spherical signals in the harmonic domain. The mathematical model of
spherical convolution into the harmonic domain shows its orientation-
equivalent. Here we firstly define the required mathematical concepts in the
spherical convolution. We model spherical images and filters as functions:
$f:S^{2}\rightarrow\mathbb{R}^{K}$, where $S^{2}$ is defined as the set of
points $x\in\mathbb{R}^{3}$ in the unit sphere, and $K$ is the number of
channels. The set of rotations in $\mathbb{R}^{3}$ is called $SO(3)$, the
”special orthogonal group”. Each rotation can be represented by a $3\times 3$
matrix that preserves distance (i.e. $\left\|R\circ
x\right\|=\left\|x\right\|,x\in\mathbb{R}^{3}$), where $\circ$ denotes acting
rotation $R$ on $x$. Based on the work in [37], we can introduce the rotation
operator $L_{R}$ which acts on spherical signals (i.e. functions)
$f:S^{2}\rightarrow\mathbb{R}^{K}$ for $R\in SO(3)$ as: $[L_{R}\circ
f](x)=f(R^{-1}\circ x)$. Thus the spherical convolution of signals $f$ and $h$
in the rotation group $SO(3)$ are defined as:

$\displaystyle[f\star_{SO(3)}h](\mathbf{R})=$
$\displaystyle\int_{SO(3)}f(\mathbf{R}^{-1}\mathbf{Q})h(\mathbf{Q})d\mathbf{Q}.$
(7)

where $\mathbf{R,Q}\in SO(3)$. As the proof in [38], spherical convolution is
shown to be orientation-equivariant:

$\displaystyle[f\star_{SO(3)}[L_{Q}h](\mathbf{R})=$
$\displaystyle[L_{\mathbf{Q}}[f\star_{SO(3)}h]](\mathbf{R}).$ (8)

where $L_{\mathbf{Q}}(\mathbf{Q}\in SO(3))$ is a rotation operator for
spherical signals. As depicted in Fig. 5, the convolution of two spherical
signals $f$ and $h$ in the harmonica domain are computed by three steps. We
first expand $f$ and $h$ to their spherical harmonic basis $H_{f}$ and
$H_{h}$, then compute the point-wise product of harmonic coefficients, and
finally invert the spherical harmonic expansion. For more details, we suggest
the reader refers to the original work in [37].

####  III-C3 Place Feature Aggregation

We leverage a feature clustering operation to convert the output of spherical
convolution into an orientation-invariant place descriptor. Intuitively, there
exists spatial similarity in output local descriptors of spherical
convolution. Therefore, we cluster the local descriptors and take a sum of
residuals (difference vector between descriptor and its corresponding cluster
center) as a global place descriptor. Formally, given $N$ $D$-dimensional
local descriptors $\\{\mathbf{x}_{i}\\}$ as input, and $K$ cluster centers
(“visual words”) ${\mathbf{c}_{k}}$ as VLAD parameters, the $(j,k)$ element of
output global descriptor $\mathbf{V}$:

$\displaystyle\mathbf{V}(j,k)=\sum_{i=1}^{N}\overline{a}_{k}(\mathbf{x}_{i})(x_{i}(j)-c_{k}(j)),$
(9)

where $x_{i}(j)$ and $c_{k}(j)$ are the $j$-th dimension of the $i$-th
descriptor and $k$-th cluster center, respectively. Here
$\overline{a}_{k}(\mathbf{x}_{i})$ has the following definition:

$\displaystyle\overline{a}_{k}(\mathbf{x}_{i})=\frac{e^{\mathbf{w}_{k}^{T}}\mathbf{x}_{i}+b_{k}}{\sum_{k}e^{\mathbf{w}_{k}^{T}\mathbf{x}_{i}+b_{k}}},$
(10)

where vector $\mathbf{w}_{k}$ and scalar $b_{k}$ are two learnable parameters.
The clustered place features satisfy the permutation invariance of input local
descriptors (order of $\\{\mathbf{x}_{i}\\}$), which makes the place
descriptors invariant to orientation difference and locally translation
difference. For the detailed analysis of VLAD please refer to the original
paper [39]

###  III-D Divergence Metric-based Feature Learning

To incorporate different aspects learned from the parallel semantic embedding
network, we introduce a viewpoint-free divergence loss metric for place
feature learning. This divergence loss includes two loss metric parts: a
“Viewpoint-free” loss to enhance feature robustness to orientation- and local
translation- variants, and a regularizing term to force the network to learn
from different semantic attributes.

For convenience of illustrating the loss functions, some necessary definitions
are first described in following. Each training tuple in our training datasets
consists of four components:
$\mathcal{S}=[S_{a},\\{S_{rot}\\},\\{S_{pos}\\},\\{S_{neg}\\}]$, where $S_{a}$
is the spherical representation of a local 3D scan, $\\{S_{rot}\\}$ is a set
of spherical representations of 3D scans rotated with different angles
($[$$,$$,...$$]$). $\\{S_{pos}\\}$ denotes a set of spherical representations
of 3D scans (“positive”) which are structurally similar to $\\{S_{a}\\}$, and
$\\{S_{neg}\\}$ denotes a set of 3D scans (“negative”) which are structurally
different to $\\{S_{a}\\}$. Ideally, the model can minimize two distances:
$\delta_{pos}^{j}=d(f(S_{a}),f(S_{pos}^{j}))$ and
$\delta_{pos_{i}}^{rot_{j}}=d(f(S_{rot}^{j}),f(S_{pos}^{i}))$, while
maximizing: $\delta_{neg}^{j}=d(f(S_{a}),f(S_{neg}^{j}))$ and
$\delta_{neg_{i}}^{rot_{j}}=d(f(S_{rot}^{j}),f(S_{neg}^{i}))$. Here $f(.)$ is
the function that encodes spherical representations into a global descriptors
by PSE-Match, and $d(\cdot)$ denoted the squared Euclidean distance.

Figure 6: The Viewpoint-free loss metric. We provide the current query frame,
rotated frames (same places with different orientations), positive frames
(places with local translation differences) and negative frames (places with
translation difference beyond certain distance) for viewpoint-free feature
learning. The “Viewpoint-free” metric can pull or push features of rotated,
positive and negative frames towards the query frame based on the margin
settings.

The “Viewpoint-free” loss metric contains a “LazyRot” loss for orientation-
invariant feature learning and a “LazyTrip” loss for the locally translation-
invariant. “LazyRot” loss is designed to maximize the feature distance between
$f(S_{rot})$ and $f(S_{neg})$, while reduce feature difference between
$f(S_{rot})$ and $f(S_{pos})$. Formally, the “Lazy Rotation“ loss is denoted
as:

$\displaystyle
L_{LazyRot}(\mathcal{T})=\max_{i,j,k}([\ell+\delta_{pos_{i}}^{rot_{j}}-\delta_{neg_{k}}^{rot_{j}}]_{+}),$
(11)

where $[.]_{+}$ denotes the hinge loss and $\ell$ is a constant parameter to
mark corresponding margin. With this soft loss constraints, PSE-Match can
further reduce the feature similarity within local boundaries even under
variant orientation differences. We apply a “Lazy Triplet” loss to maximize
the feature distance between the local scan feature $f(S_{rot})$ and its
corresponding “negative” features $f(S_{neg})$, which is represented as:

$\displaystyle
L_{LazyTrip}(\mathcal{T})=\max_{j}([\alpha+\delta_{pos}-\delta_{neg_{j}}]_{+}),$
(12)

here $\alpha$ is constant threshold to control the margin. We employ the
simultaneous supervision of “Lazy Rotation” loss and “Lazy Triplet” loss to
learn the “viewpoint-free” descriptors for the semantic attribute $A_{l}$ by:

$\displaystyle L_{free}^{A_{l}}=L_{LazyRot}^{A_{l}}+L_{LazyTrip}^{A_{l}}.$
(13)

The final divergence loss metric is based on the each semantic attribute loss
$L_{free}^{A_{l}}$ and an additional regularization term,

$\displaystyle
L_{Divergence}=\sum_{l}L_{free}^{A_{l}}+\lambda\sum_{a,b}[m-D_{ia,ib}^{2}]_{+},$
(14)

where $D_{ia,ib}$ represents a distance measurement between place descriptors
learned by different semantic embedding branches, $m$ is the margin between
two different leaners $a$ and $b$, and $\lambda$ is the weighting parameter to
control the regularization strength.

Figure 7: The in-field datasets which contains a campus area and city-scale
area. All the datasets are collected by a data-recording platform with a
Velodyne-VLP 16 LiDAR device, a front view camera, an IMU device, and a Global
Navigation Satellite Systems (GNSS) system for ground truth positions. Campus
datasets includes $11$ trajectories around the campus of Carnage Mellon
University (CMU). The city-scale datasets contains $12$ trajectories outside
the CMU campus in the city of Pittsburgh. The data are recorded incrementally
on different parts, different environment conditions and different tracks.
Figure 8: Place retrievals on two public available datasets and two in-field
collected datasets. The first column shows the original reference maps on
different datasets, and the following columns present the top one matched maps
retrieved on testing frames by different methods. Both ScanContext and M2DP
achieve similiar performances.

##  IV Experiments

This section compares the proposed method with both non-learning/learning-
based 3D place recognition methods on two public datasets, and two in-field
collected datasets. To generate our datasets, we designed a data-collecting
platform, which contains a LiDAR device (Velodyne-VLP 16), an inertial
measurement unit (Xsense MTi $30$, $0.5^{\circ}$ error in roll/pitch,
$1^{\circ}$ error in yaw, $550m$W), a Global Navigation Satellite Systems
(GNSS) ($10$Hz outputs), a mini PC (Intel NUC i7, $3.5$ GHz, $28$W) and an
embedded GPU device (Nvidia Xavier, $8$G memory). We trained our network model
on a GPU server with a Ubuntu 18.04 system with a single Nvidia 1080Ti GPU and
$64$G RAM. In the rest of this section, we first introduce the datasets, the
comparison of non-learning/learning-based methods, and evaluate manners and
metrics. Then, we demonstrate the quantitative and qualitative comparison
analysis of different methods under variant viewpoint configurations on
different datasets. Finally, both resource requirements and computation
efficiency are further evaluated for each methods.

Datasets. The training and evaluation data includes two public available
datasets and two in-filed collected datasets:

  * •

KITTI [40] odometry datasets, which consists of 21 trajectories generated with
Velodyne-64 LiDAR scanner, around the mid-size city of Karlsruhe. We use
trajectory $\\{1\sim 8\\}$ for network training, and $\\{9,10\\}$ for
evaluation.

  * •

NCLT [41] datasets, which consists of 103 trajectories generated with
Velodyne-32 LiDAR scanner, around the mid-size city of Karlsruhe. We use
trajectory $\\{1\sim 8\\}$ for network training, and $\\{9,10\\}$ for
evaluation.

  * •

CMU dataset, we created a Campus dataset with 11 trajectories by driving our
data capturing mobile platform to traverse a $2km$ outdoor route around the
campus of our university. We use trajectories $\\{1\sim 9\\}$ for network
training, and $\\{10,11\\}$ for evaluation.

  * •

Pittsburgh dataset, we created a City-scale dataset by mounting our data
capturing system on the top of a car and incrementally traversing $12km$
trajectories in the city of Pittsburgh. We collected 12 trajectories, and we
use trajectories $\\{1\sim 10\\}$ for network training, and $\\{11,12\\}$ for
evaluation.

TABLE I: Dataset frames splitting in training/evaluation. | KITTI | NCLT | CMU | CITY
---|---|---|---|---
Train | $13,070$ | $15,971$ | $13,830$ | $10,972$
Evaluation | $3,268$ | $3,993$ | $3,458$ | $2,744$

The relationship between the two in-field dataset are shown in Fig. 7. Table.
LABEL:table:dataset shows the data splitting in the training and evaluation
procedure on the four different datasets. We generate the reference and
testing sequence from the same trajectory in the evaluation step for each
dataset under different orientation and translation differences. And to
evaluate the generalization ability of different learning-based methods, we
introduce a refine mode to train the network: we select every first two
trajectories within four datasets for network training, and use the same
testing data in Table LABEL:table:dataset for evaluation.

Evaluation Methods. To evaluate our approach’s performance, we firstly
compared it with the state-of-the-art learning-based place recognition
approaches: PointNetVLAD (PN-
VLAD)111https://github.com/mikacuy/pointnetvlad[15],
LPDNet222https://github.com/Suoivy/LPD-net[17] and
PCAN333https://github.com/XLechter/PCAN[16]. For non-learning based
approaches, we also compare the frame-level descriptors ScanContext
[22]444https://github.com/irapkaist/scancontext, M2DP
[25]555https://github.com/LiHeUA/M2DP, and 3D keypoint-based approaches SHOT
and Fast Histogram from PCL [23]666https://github.com/PointCloudLibrary/pcl
libaray. For all the above approaches, we provide the dense local maps
generated by our dynamic octree mapping step, as shown in Section III-B, and
extract the global place descriptors based on the different procedures of the
above approaches. For the fair comparison, the inputs for all the above
methods are processed with out dynamic octree mapping module. And we also
analysis the place recognition of our PSE-Match with and without the dynamic
octree mapping module to investigate their differences.

Figure 9: Average recall at top $1\%$ under variant viewpoint differences. For
each sub-graph, x-axis represents the translation differences between the
testing and reference trajectories, y-axis represents the relative orientation
differences. z-axis shows the relative average recall.

We evaluate the place recognition accuracy under two different matching
methods: single-scan and sequential-scan based place recognition. The first
method retrieves corresponding places by evaluating feature similarity with
K-nearest neighbor search. The second method defines a temporal window to
capture more stable place features, and use brute-force searching to locate
the best matches [11].

Evaluation Metrics. In both evaluation methods, similar to PN-VLAD [15], we
use the Average Recall at top one, ten and $1\%$ retrievals, the Precision-
Recall Curve and Average Precision Score (AP score) under different viewpoints
to assess the place recognition accuracy between the relative reference and
testing sequence trajectories.

###  IV-A Place Recognition Results

####  IV-A1 Orientation- and Translation- Invariant Analysis

Fig. 8 demonstrate the top one place retrievals of different methods with a
given reference map, we can see that PSE-Match can retrieve the correct sub-
maps under both orientation and translation differences. Fig. 9 gives a more
detailed recognition performance, where each sub-figure represents the place
recognition analysis with a fixed viewpoint difference. The x-axis represents
the translation difference (from $0\sim 10$m), y-axis represents the
orientation difference (from $0\sim 180^{\circ}$), and z-axis represents the
average recall at top $1\%$ retrieves. For all the non-learning based
approaches, we can note that: these methods are robust to orientation
differences, but weak to locally translation differences. Among the non-
learning methods, both ScanContext and M2DP show robuster place recognition
ability under variant orientation differences; however, this method is
sensitive to the locally translation differences in the XY-plane. This
performance of the non-learning based methods is slightly different from the
other work [26, 22], because the viewpoint didn’t includes variant orientation
differences. Among all the other non-learning methods, ScanContext shows the
best performance, but it has a higher time-consumption as we analyzed in
Section. IV-B.

(a)

(b)

Figure 10: Precision-recall curves of single/sequential-scan matching on the
NCLT dataset.

(a)

(b)

Figure 11: Average precision score (AP score) of single/sequential-scan matching on the NCLT dataset. TABLE II: The average recall of at top one on four datasets with translation differences range from $0\sim 8$m and orientation changes range from $0\sim 135^{\circ}$. Method | NCLT | KITTI | City | CMU
---|---|---|---|---
ScanContext [22] | $63.19\%$ | $61.27\%$ | $60.81\%$ | $64.19\%$
M2DP [25] | $59.23\%$ | $58.99\%$ | $57.03\%$ | $64.32\%$
SHOT [23] | $33.33\%$ | $30.33\%$ | $48.98\%$ | $44.47\%$
Fast-Histogram [42] | $14.23\%$ | $18.83\%$ | $12.32\%$ | $15.19\%$
PN-VLAD [15] | $13.85\%$ | $7.39\%$ | $14.97\%$ | $13.98\%$
LPDNet [17] | $13.10\%$ | $12.92\%$ | $18.63\%$ | $17.26\%$
PCAN [16] | $13.02\%$ | $9.80\%$ | $13.02\%$ | $15.47\%$
PSE-Match (no DOM) | $67.21\%$ | $64.98\%$ | $70.71\%$ | $67.13\%$
PSE-Match | $\mathbf{82.78\%}$ | $\mathbf{72.19\%}$ | $\mathbf{78.06\%}$ | $\mathbf{75.95\%}$
PN-VLAD (refine) | $12.67\%$ | $7.33\%$ | $13.54\%$ | $14.97\%$
LPDNet (refine) | $12.07\%$ | $8.18\%$ | $12.01\%$ | $13.41\%$
PCAN (refine) | $11.89\%$ | $9.89\%$ | $14.25\%$ | $16.08\%$
PSE-Match (refine) | $72.33\%$ | $69.12\%$ | $70.91\%$ | $70.61\%$

On the other hand, for the current learning-based place recognition methods,
they shows a better robustness to locally translation differences than the
non-learning ones. However, as we can see in Fig. 9, all PointNet-based place
features are not aimed at dealing with orientation-invariance, thus they are
also very sensitive to the orientation differences. Table. LABEL:table:ar_1p
and Table. LABEL:table:ar_10p give the detailed average recall at top one and
ten respectively, and please note the recalls are averaged all the viewpoint
differences (i.e., translation differences range from $0\sim 8$m and
orientation changes range from $0\sim 135^{\circ}$). As we can note that, both
LPDNet [17] and PCAN [16] show better place recognition ability than the
original PN-VLAD [15] under orientation differences. However, they cannot
handle significant perspective changes in both translation and orientation
simultaneously.

TABLE III: The average recall of at top ten on four datasets with translation differences range from $0\sim 8$m and orientation changes range from $0\sim 135^{\circ}$. Method | KITTI | NCLT | PITTS | CMU
---|---|---|---|---
ScanContext [22] | $85.21\%$ | $90.15\%$ | $85.88\%$ | $88.49\%$
M2DP [25] | $83.39\%$ | $83.53\%$ | $80.68\%$ | $85.82\%$
SHOT [23] | $55.87\%$ | $53.26\%$ | $74.73\%$ | $68.55\%$
Fast-Histogram [42] | $31.31\%$ | $21.43\%$ | $28.07\%$ | $30.98\%$
PN-VLAD [15] | $36.42\%$ | $13.21\%$ | $33.90\%$ | $32.24\%$
LPDNet [17] | $34.18\%$ | $29.05\%$ | $37.05\%$ | $35.13\%$
PCAN [16] | $38.85\%$ | $23.36\%$ | $32.70\%$ | $38.45\%$
PSE-Match (no DOM) | $88.32\%$ | $89.09\%$ | $93.21\%$ | $91.31\%$
PSE-Match | $\mathbf{99.89\%}$ | $\mathbf{96.28\%}$ | $\mathbf{99.16\%}$ | $\mathbf{99.50\%}$
PN-VLAD (refine) | $30.77\%$ | $10.70\%$ | $27.73\%$ | $29.15\%$
LPDNet (refine) | $30.09\%$ | $14.98\%$ | $23.42\%$ | $28.20\%$
PCAN (refine) | $34.47\%$ | $21.13\%$ | $34.69\%$ | $38.45\%$
PSE-Match (refine) | $97.16\%$ | $94.72\%$ | $96.40\%$ | $97.17\%$

In contrast, PSE-Match shows better performance in place recognition under
variant viewpoint differences. On all the four datasets, the average recalls
at top one are above $70\%$; and in the refine mode, PSE-Match also shows
better generalization ability than both non-learning/learning based methods.
In the top ten retrieval case, PSE-Match can reach above $95\%$ on all
datasets. We also analysis the place recognition performance of our dynamic
octree mapping (DOM) module. The PSE-Match (no DOM) in Table.
LABEL:table:ar_1p and Table. LABEL:table:ar_10p indicate the local mapping
using accumulated point clouds, without the measurement and motion updating in
the DOM module. In both the recalls of top one and ten retrievals, PSE-Match
can provide more reliable place recognition with DOM module.

Figure 12: Sequence matching performance of different methods on KITTI
datasets. The first row shows the cosine feature difference between testing
and reference trajectory, and the relative translation and orientation
difference between two trajectories is $4m$ and $135^{\circ}$ respectively.
The second row shows the enhanced difference matrix by apply local
normalization same to the original SeqSLAM [11]. The last row shows the
estimated sequential matching results.

####  IV-A2 Single and Sequential Matching Results

In this subsection, we further investigate the place recognition performance
under single-scan and sequential-scan matching mode. Fig. 10 and Fig. 11 shows
the precision-recall curve and average precision score of different methods on
the NCLT dataset. In the cases of lower translation and orientation cases, all
methods can achieve robust place recognition ability. And both ScanContext and
M2DP show the invariant property to orientation and perform well under smaller
translation and orientation. However, for significant translational or
rotational cases, both transitional methods or PointNet-based method cannot
guarantee accurate place retrieval. Especially, the PointNet based methods are
very sensitive to the orientation differences.

Obviously, the sequence-matching manner can improve the matching performances.
The performance of both ScanContext and M2DP are significantly improved.
However, PointNet-based methods still fail to find the matches in the cases
with big orientation differences. For PSE-Match method, it can achieve even
better recognition performance with the sequential matching manner. Fig. 12
shows the feature difference matrix, enhancement matrix and matched indexes in
the sequential-matching [11] procedure. We can see the reference/testing
features difference matrix has a stronger contrast than other methods, which
provides stable sequential matches.

###  IV-B Time and Storage Analysis

In Table. IV, we analysis the time and memory usage comparison of our PSE-
Match and other non-learning/learning based place recognition methods. Both
ScanContext and M2DP is time consuming in feature extraction. Compared with
ScanContext, M2DP and other learning-based methods, PSE-Match consumes less
GPU memory in the training procedure. In the inference step, we running the
dynamic octree mapping module to generate dense local map, which takes $10$ms
in application. The semantic inference and PSE-Match feature extraction for
each sub-map will take $15ms$ ($250MB$ GPU) and $13.24ms$ ($37Mb$ GPU)
respectively. It is feasible to run PSE-Match in the Nvidia embedded system
(Nvidia Jetson TX2, or Xavier), and suitable for low-cost robot systems in
long-term SLAM and navigation.

TABLE IV: Comparison result of time and memory requirements of different methods. Method | GPU (M) | Time (ms) | Feature Size
---|---|---|---
ScanContext | $-$ | $258.29$ | 192
M2DP | $-$ | $164.05$ | 192
SHOT | $-$ | $14.74$ | 352
Fast Histogram | $-$ | $2.53$ | 192
PN-VLAD [15] | $2887$ | $11.31$ | 256
LPDNet [17] | $4679$ | $41.23$ | 256
PCAN [16] | $8525$ | $21.53$ | 256
PSE-Match | $2459$ | $10+15+13.24$ | 256

##  V Conclusions

In this paper, we propose PSE-Match, a 3D place recognition and global
localization method. Compared with the current 3D place recognition methods,
PSE-Match can learn robust and viewpoint-free 3D feature descriptors from
different independent semantic attributes, which can provide stable
consistence in complex 3D environment and avoid the disturbance from the
dynamic objects. Particularly, we introduce a parallel semantic embedding
network to learn viewpoint-free feature descriptor on the spherical
projections with assistance of a divergence learning metric. Validating on
both single and sequential matching data, experiments results show that our
method has significant accuracy improvement than other state-of-the-arts peers
under variant viewpoint differences. The less computation resource
requirements and efficient inference make our method more practical for real-
time applications.

In the future work, we will extend the large-scale loop closure detection and
mapping based on the PSE-Match. Leveraging the native properties of semantic
embedding, we will pursue embedding objective-level information for accurate
localization for autonomous navigation.

## References

  * [1] J. Fuentes-Pacheco, J. Ruiz-Ascencio, and J. M. Rendón-Mancha, “Visual simultaneous localization and mapping: a survey,” _Artificial intelligence review_ , vol. 43, no. 1, pp. 55–81, 2015.
  * [2] E. Larson, A. Ianuzzi, R. Oliva, D. Lowrance _et al._ , “Autonomous underwater survey apparatus and system,” May 2 2019, uS Patent App. 16/173,567.
  * [3] F. Rosique, P. J. Navarro, C. FernÃ¡ndez, and A. Padilla, “A systematic review of perception system and simulators for autonomous vehicles research,” _Sensors_ , vol. 19, no. 3, 2019. [Online]. Available: https://www.mdpi.com/1424-8220/19/3/648
  * [4] W. Lim, S. Lee, M. Sunwoo, and K. Jo, “Hierarchical trajectory planning of an autonomous car based on the integration of a sampling and an optimization method,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 19, DOI 10.1109/TITS.2017.2756099, no. 2, pp. 613–626, 2018.
  * [5] M. Nowakowski, C. Joly, S. Dalibard, N. Garcia, and F. Moutarde, “Topological localization using wi-fi and vision merged into fabmap framework,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 3339–3344, 2017.
  * [6] W. Zong, L. Chen, C. Zhang, Z. Wang, and Q. Chen, “Vehicle model based visual-tag monocular ORB-SLAM,” in _IEEE International Conference on Systems, Man, and Cybernetics (SMC)_ , DOI 10.1109/SMC.2017.8122816, pp. 1441–1446, Oct. 2017.
  * [7] H. JÃ©gou, F. Perronnin, M. Douze, J. SÃ¡nchez, P. PÃ©rez, and C. Schmid, “Aggregating local image descriptors into compact codes,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 34, no. 9, pp. 1704–1716, 2012.
  * [8] E. Rublee, V. Rabaud, K. Konolige, and G. Bradski, “ORB: An efficient alternative to SIFT or SURF,” in _International Conference on Computer Vision_ , DOI 10.1109/ICCV.2011.6126544, pp. 2564–2571, Nov. 2011.
  * [9] Z. Zhang, Y. Huang, C. Li, and Y. Kang, “Monocular vision simultaneous localization and mapping using SURF,” in _7th World Congress on Intelligent Control and Automation_ , DOI 10.1109/WCICA.2008.4593166, pp. 1651–1656, Jun. 2008.
  * [10] R. Arandjelovic, P. Gronat, A. Torii, T. Pajdla, and J. Sivic, “Netvlad: Cnn architecture for weakly supervised place recognition,” in _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , DOI 10.1109/CVPR.2016.572, pp. 5297–5307, Jun. 2016.
  * [11] M. J. Milford and G. F. Wyeth, “SeqSLAM: Visual route-based navigation for sunny summer days and stormy winter nights,” in _IEEE International Conference on Robotics and Automation_ , DOI 10.1109/ICRA.2012.6224623, pp. 1643–1649, May. 2012.
  * [12] R. DubÃ©, A. Cramariuc, D. Dugas, H. Sommer, M. Dymczyk, J. Nieto, R. Siegwart, and C. Cadena, “Segmap: Segment-based mapping and localization using data-driven descriptors,” _The International Journal of Robotics Research_ , vol. 39, DOI 10.1177/0278364919863090, no. 2-3, pp. 339–355, 2020.
  * [13] C. R. Qi, H. Su, K. Mo, and L. J. Guibas, “Pointnet: Deep learning on point sets for 3d classification and segmentation,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 652–660, 2017\.
  * [14] C. R. Qi, L. Yi, H. Su, and L. J. Guibas, “Pointnet++: Deep hierarchical feature learning on point sets in a metric space,” in _Advances in neural information processing systems_ , pp. 5099–5108, 2017.
  * [15] M. Angelina Uy and G. Hee Lee, “Pointnetvlad: Deep point cloud based retrieval for large-scale place recognition,” in _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , Jun. 2018.
  * [16] W. Zhang and C. Xiao, “Pcan: 3d attention map learning using contextual information for point cloud based retrieval,” in _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pp. 12 428–12 437, 2019.
  * [17] Z. Liu, S. Zhou, C. Suo, P. Yin, W. Chen, H. Wang, H. Li, and Y.-H. Liu, “Lpd-net: 3d point cloud learning for large-scale place recognition and environment analysis,” in _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 2831–2840, 2019.
  * [18] D. G. Lowe, “Object recognition from local scale-invariant features,” in _Proceedings of the seventh IEEE international conference on computer vision_ , vol. 2, pp. 1150–1157. Ieee, 1999\.
  * [19] H. Bay, T. Tuytelaars, and L. Van Gool, “Surf: Speeded up robust features,” in _Computer Vision – ECCV 2006_ , A. Leonardis, H. Bischof, and A. Pinz, Eds., pp. 404–417. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006.
  * [20] Y. Mei and Y. He, “A new spin-image based 3d map registration algorithm using low-dimensional feature space,” in _IEEE International Conference on Information and Automation (ICIA)_ , DOI 10.1109/ICInfA.2013.6720358, pp. 545–551, Aug. 2013.
  * [21] W. Wohlkinger and M. Vincze, “Ensemble of shape functions for 3d object classification,” in _2011 IEEE international conference on robotics and biomimetics_ , pp. 2987–2992. IEEE, 2011\.
  * [22] G. Kim and A. Kim, “Scan context: Egocentric spatial descriptor for place recognition within 3d point cloud map,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 4802–4809. IEEE, 2018.
  * [23] F. Tombari, S. Salti, and L. Di Stefano, “Unique signatures of histograms for local surface description,” in _Computer Vision – ECCV 2010_ , K. Daniilidis, P. Maragos, and N. Paragios, Eds., pp. 356–369. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010\.
  * [24] T. Röhling, J. Mack, and D. Schulz, “A fast histogram-based similarity measure for detecting loop closures in 3-d lidar data,” in _2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 736–741. IEEE, 2015.
  * [25] L. He, X. Wang, and H. Zhang, “M2dp: A novel 3d point cloud descriptor and its application in loop closure detection,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pp. 231–237. IEEE, 2016.
  * [26] H. Yin, Y. Wang, X. Ding, L. Tang, S. Huang, and R. Xiong, “3d lidar-based global localization using siamese neural network,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 4, pp. 1380–1392, 2019.
  * [27] C. Esteves, C. Allen-Blanchette, A. Makadia, and K. Daniilidis, “Learning so (3) equivariant representations with spherical cnns,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , pp. 52–68, 2018.
  * [28] K. He, G. Gkioxari, P. Dollár, and R. Girshick, “Mask r-cnn,” in _Proceedings of the IEEE international conference on computer vision_ , pp. 2961–2969, 2017.
  * [29] C. Choy, J. Gwak, and S. Savarese, “4d spatio-temporal convnets: Minkowski convolutional neural networks,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 3075–3084, 2019.
  * [30] J. L. Schönberger, M. Pollefeys, A. Geiger, and T. Sattler, “Semantic visual localization,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 6896–6906, 2018.
  * [31] S. Garg, N. Suenderhauf, and M. Milford, “Semantic geometric visual place recognition: a new perspective for reconciling opposing views,” _The International Journal of Robotics Research_ , vol. 0, DOI 10.1177/0278364919839761, no. 0, p. 0278364919839761, 0. [Online]. Available: https://doi.org/10.1177/0278364919839761
  * [32] B. Wu, A. Wan, X. Yue, and K. Keutzer, “Squeezeseg: Convolutional neural nets with recurrent crf for real-time road-object segmentation from 3d lidar point cloud,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , DOI 10.1109/ICRA.2018.8462926, pp. 1887–1893, May. 2018.
  * [33] T. Shan and B. Englot, “Lego-loam: Lightweight and ground-optimized lidar odometry and mapping on variable terrain,” in _2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , DOI 10.1109/IROS.2018.8594299, pp. 4758–4765, Oct. 2018.
  * [34] E. Rho and S. Jo, “Octomap-based semi-autonomous quadcopter navigation with biosignal classification,” in _6th International Conference on Brain-Computer Interface (BCI)_ , DOI 10.1109/IWW-BCI.2018.8311533, pp. 1–4, Jan. 2018.
  * [35] S. Thrun, “Probabilistic robotics,” _Communications of the ACM_ , vol. 45, no. 3, pp. 52–57, 2002.
  * [36] J. Zhang and S. Singh, “Loam: Lidar odometry and mapping in real-time.” in _Robotics: Science and Systems_ , vol. 2, p. 9, 2014.
  * [37] M. Kazhdan, T. Funkhouser, and S. Rusinkiewicz, “Rotation invariant spherical harmonic representation of 3 d shape descriptors,” in _Symposium on geometry processing_ , vol. 6, pp. 156–164, 2003.
  * [38] T. S. Cohen, M. Geiger, J. Köhler, and M. Welling, “Spherical cnns,” in _International Conference on Learning Representations_ , 2018.
  * [39] R. Arandjelovic and A. Zisserman, “All about vlad,” in _2013 IEEE Conference on Computer Vision and Pattern Recognition_ , DOI 10.1109/CVPR.2013.207, pp. 1578–1585, Jun. 2013.
  * [40] A. Geiger, P. Lenz, C. Stiller, and R. Urtasun, “Vision meets robotics: The KITTI dataset,” _INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH_ , vol. 32, DOI 10.1177/0278364913491297, no. 11, pp. 1231–1237, SEP 2013.
  * [41] N. Carlevaris-Bianco, A. K. Ushani, and R. M. Eustice, “University of michigan north campus long-term vision and lidar dataset,” _The International Journal of Robotics Research_ , vol. 35, no. 9, pp. 1023–1035, 2016.
  * [42] R. B. Rusu, N. Blodow, and M. Beetz, “Fast point feature histograms (fpfh) for 3d registration,” in _2009 IEEE International Conference on Robotics and Automation_ , pp. 3212–3217. IEEE, 2009\.