# Impact of time and note duration tokenizations on deep learning symbolic
music modeling

###### Abstract

Symbolic music is widely used in various deep learning tasks, including
generation, transcription, synthesis, and Music Information Retrieval (MIR).
It is mostly employed with discrete models like Transformers, which require
music to be tokenized, i.e., formatted into sequences of distinct elements
called tokens. Tokenization can be performed in different ways. As
Transformers can struggle at reasoning, but capture more easily explicit
information, it is important to study how the way the information is
represented for such models impact their performances. In this work, we
analyze the common tokenization methods and experiment with time and note
duration representations. We compare the performances of these two impactful
criteria on several tasks, including composer and emotion classification,
music generation, and sequence representation learning. We demonstrate that
explicit information leads to better results depending on the task.

##  1 Introduction

Most tasks involving using deep learning with symbolic music [1] are performed
with discrete models, such as Transformers [2]. To use these models, the music
must first be formatted into sequences of distinct elements, commonly called
tokens. For instance, a token can represent a note attribute or a time event.
The set of all known tokens is commonly called the vocabulary, and each token
is associated to a unique integer id. These ids are used as input and output
of models.

Compared to text, tokenizing music provides greater flexibility, as a musical
piece can be played by different instruments and composed of multiple
simultaneous notes, each having several attributes to represent. As a result,
it is necessary to serialize these elements along the time dimension. To
achieve this, researchers have developed various methods of tokenizing music
[3, 4, 5, 6].

While these works present model performance comparisons between tokenizations,
their main differences or similarities are not always clearly stated.
Moreover, they mostly focus on music generation, for which evaluations are
performed on results obtained autoregressively, which accumulates biases [7]
and is arguably difficult to evaluate [8], rather than music modeling more
broadly. Yet, Transformer models struggle at reasoning, i.e. making logical
deduction based on information points in the input data [9, 10], but perform
tasks better when fed with explicit information and instructions [11]. In the
case of symbolic music, it is thus important to study how the ways the music
information is represented impact model performances.

This paper’s primary contribution is a thorough and well-designed comparison
of common tokenization techniques. Our focus is on two critical aspects: the
representation of time and note duration. We believe that they are significant
and impactful design choices for any music tokenization approach. Through
experiments on composer classification, emotion classification, music
generation, and sequence representation, we demonstrate that these design
choices produce varying results depending on the task, model type, and
inference process. Autoregressive generation benefits from explicit note
duration and time shift tokens, while explicit note offset is more
discriminating better suited for contrastive learning approaches.

We present next the related works, followed by an analysis of music
tokenization, experimental results, and finally a conclusion. The source code
is publicly available. 111https://github.com/Natooz/music-modeling-time-
duration

##  2 Decomposing music tokenization

###  2.1 Related works

Early works using discrete models for symbolic music, such as DeepBach [12] or
FolkRNN [13], rely on specific tokenizations often tied to their training
data. Since then, researchers introduced more general representations
applicable to any kind of music. The most commonly used are Midi-Like [3] and
REMI [4]. The former tokenizes music by representing tokens as the same types
of events from the MIDI protocol, while the latter represents time with Bar
and Position tokens and note durations with explicit Duration tokens.
Additionally, REMI includes tokens with additional information such as chords
and tempo.

More recently, researchers have focused on improving the efficiency of models
with new tokenizations techniques: Compound Word [14], Octuple [5] and PopMAG
[15] merge embedding vectors before passing them to the model; 2) LakhNES [16]
and [17], SymphonyNet [18] and [19] use tokens combining several values, such
as pitch and vocabulary.

###  2.2 Music tokenization design

When analyzing the possible designs of music tokenization, we can distinguish
seven key dimensions:

  * •

Time: Type of token representing time, either TimeShift indicating time
movements, or Bar and Position indicating new bars and the positions of the
notes within them. We can also consider the unit of Time-Shift tokens, either
in beats or in seconds.222In this paper we only treat of the beat unit. The
MIDI protocol represents time in tick unit, which value is proportional to the
time division (in ticks per beat) and tempo. Hence, working with seconds would
require a conversion from ticks.

  * •

Notes duration: How notes durations are represented, with either Duration or
NoteOff tokens.

  * •

Pitch: Most works use tokens representing absolute pitch values, although
recent work shed light on the expressiveness gain of representing as intervals
instead [20];

  * •

Multitrack representation: The representation of several music tracks in a
sequence, i.e., how are the notes linked to their associated track.

  * •

Additional information: Any additional information such as chords, tempo,
rests, note density. Velocity can also falls in this category;

  * •

Downsampling: How "continuous-like" features are downsampled into discrete
sets, e.g. the 128 velocity values reduced to 16 values;

  * •

Sequence compression: Methods to reduce the sequence lengths, such as merging
tokens and embedding vectors.

| Time | Note duration
---|---|---
Tokenization | TimeShift |  Bar \+ Pos. | Duration | NoteOff
MIDI-Like [3] | $\surd$ | - | - | $\surd$
REMI [4] | - | $\surd$ | $\surd$ | -
Structured [21] | $\surd$ | - | $\surd$ | -
TSD [19] | $\surd$ | - | $\surd$ | -
Octuple [5] | - | $\surd$ | $\surd$ | -

Table 1: Time and note duration representations of common tokenizations. Pos.
stands for Position.

As time and note duration can both be represented in two different ways,
existing tokenizations can be easily classified based on these dimensions, as
shown in table 1. However, other dimensions offer a broader spectrum of
potential designs.

For instance multitrack can be represented by Program tokens333Following the
conventional programs from the MIDI protocol. preceding notes as in FIGARO
[22], distinct tracks sequences separated by Program tokens as in MMM [23],
combined note and instrument tokens as LakhNes [16] and MuseNet [17], or
merging Program embeddings with the associated note tokens (MMT [24],
MusicBert [5]). One could even infer each sequence separately and lately model
their relationships with operations aggregating their hidden states an in
ColBERT [25].

The MIDI protocol supports a set of effects and metadata that can also be
represented when tokenizing symbolic music, such as tempo, time signature,
sustain pedal or control changes. Some works also include explicit Chord
tokens, detected with rule-based methods. Nevertheless, only a few works
experimented with such additional tokens so far ([4, 26]).

Previous works have mainly compared tokenization strategies by evaluating
models with automatic and sometimes subjective (human) metrics, but often do
not proceed to comparisons between the ways to represent one of the dimensions
we introduced previously. [4] compared results for the generation task, for
the use of Bar and Position tokens versus TimeShift in seconds and beats.

To the best of our knowledge, no comprehensive work and empirical analysis
have fairly compared these possible tokenization choices. Conducting such an
assessment would require an extensive survey. In this paper, we specifically
focus on the time and note duration representations, as they are the two main
characteristics present in every tokenization.

We want to highlight the importance of the explicit information carried by the
token types, as they directly impact the performances of models. TimeShift
tokens represent explicit time movements, and especially the time distances
between successive notes. On the other hand, Bar and Position tokens bring
explicit information on the absolute positions (within bars) of the notes, but
not the onset distances between notes. One could assume that the former might
help to model melodies, and the latter rhythm and structure. For note
duration, Duration tokens intuitively express the absolute durations of the
notes, while NoteOff tokens explicitly indicates the offset times. With
NoteOff, a model would have to model note durations from the combinations of
previous time tokens.

Our experiments aim to demonstrate the impact of different combinations of
time and note duration tokens on model performance and which combinations are
suitable for different tasks. Next, we introduce our methodology.

##  3 Methodology

###  3.1 Models and trainings

For all experiments, we use the Transformer architecture [2], with the same
model dimensions: 12 layers, with dimension of 768 units, 12 attention heads
and inner feed-forward layers of 3072.

For classification and sequence representation, it is first pretrained on 100k
steps and a learning rate of $10^{-4}$, then finetuned on 50k steps and a
learning rate of $3\times 10^{-5}$, with a batch size of 48 examples. An
exception is made for the EMOPIA dataset, for which we set 30k pretraining
steps and 15k finetuning steps, as it is fairly small. These models are based
on the BERT [27] implementation of the Transformers library [28]. We use the
same pretraining than the original BERT: 1) from 15% of the input tokens, 80%
is masked with a special MASK token, and 20% is randomized; 2) half of the
inputs have 50% of their tokens (starting from the end) shuffled and separated
with a special SEP token, and the model is trained to detect if the second
part is the next of the first.

For generation, the model is based on the GPT2 implementation of the
Transformers library [28]: it uses a causal attention mask, so that for each
element in the sequence, the model can only attend to the current and previous
elements. The training is performed with teacher forcing, the cross-entropy
loss is defined as: $\ell=-\sum_{t=1}^{n}\log
p_{\theta}(x_{t}\lvert\mathbf{x}_{\leq n})$.

All trainings are performed on V100 GPUs, using automatic mixed precision
[29], the Adam optimizer [30] with $\beta_{1}=0.9$, $\beta_{2}=0.999$ and
$\epsilon=10^{-8}$, and dropout, weight decay and a gradient clip norm of
respectively $10^{-1}$, $10^{-2}$ and $3$. Learning rates follow a warm-up
schedule: they are initially set to 0, and increase to their default value
during the first 30% of training, then slowly decrease back to 0.

10% of the data is used for validation during training, and 15% to test
models. Inputs contains 384 to 512 tokens, and begin with a BOS (Beginning of
Sequence) token and end with a EOS (End of Sequence) one.

###  3.2 Tokenizations

We investigate here the four combinations of possible time and note duration
representation. In the results, we refer to them as TS (TimeShift), Pos
(Position), Dur (Duration) and NOff (NoteOff). It is worth noting that TS \+
Dur is equivalent to TSD [19] and Structured [21], TS \+ NOff is equivalent to
MIDI-Like [3], and Pos \+ Dur is equivalent to REMI (without additional tokens
for chords and tempo).

We apply different resolutions for Duration and TimeShift token values: those
up to one beat are downsampled to 8 samples per beat (spb), those from one to
two beats to 4 spb, those from two to four beats to 2 spb, and those from four
to eight beats to 1 spb. Thus, short notes are represented more precisely than
longer ones. Position tokens are downsampled to 8 spb, resulting in 32
different tokens as we only consider the 4/* time signature. This allows to
represent the $16^{th}$ note. We only consider pitches within the recommended
range for piano (program 0) specified in the General MIDI 2
specifications444Available on the MIDI Manufacturers Association website.: 21
to 108. We then deduplicate all duplicated notes. Velocities are downsampled
to 8 distinct values. No additional token (e.g., Chord, Tempo) is used.

We perform data augmentation by creating variations of the original data with
pitches increased and decreased by two octaves, and velocity by one value.
Finally, following [19], we use Byte Pair Encoding to build the vocabularies
up to 2k tokens for generation and 5k for other tasks. All these preprocessing
and tokenization steps were performed with MidiTok [6].

##  4 Generation

(a) Ts \+ Dur

(b) Ts \+ NOff

(c) Pos \+ Dur

(d) Pos \+ NOff

(e) POP909 dataset

Figure 1: Histograms of the note onset positions within bars (top-row), note
offset positions within bars (middle-row) and note durations (bottom-row) of
the generated notes. There are 32 possible positions within a bar, numerated
from 0 (beginning of bar) to 31 (last 32th note). The durations are expressed
in beats, ranging from a 32th note to 8 beats.

(a) Ts \+ Dur

(b) Ts \+ NOff

(c) Pos \+ Dur

(d) Pos \+ NOff

Figure 2: Token type succession heatmaps of the generated results. The
vertical axis is a the current token type, the horizontal axis is the next
token type following the current one. All rows are normalized.

For the generative task, we use the POP909 dataset [31]. The models start with
prompt made of between 384 to 512 tokens, then autoregressively generate 512
additional tokens. Evaluation of generated results remains an open issue [8].
Previous work often perform measures of similarity of certain features such as
pitch range or class, between prompts and generated results, alongside human
evaluations. Feature similarity is however arguably not very insightful: a
generated result could have very similar features to its prompts while being
of poor quality. Human evaluations, while being more reliable on the quality
can also induce biases. Besides, [4] already shows results on an experiment
similar to ours.

Hence we choose to evaluate results on the ratios of prediction errors: Token
Syntax Error (TSE) [19]. This metric is bias-free and directly linked to the
design choices of the tokenizations. It allows us to measure how a model
achieves to make reliable predictions based on the input context and the
knowledge it learned.

We use the categories from [19]:

  * •

$\mathbf{TSE_{type}}$: an error of type, e.g., when the model predicts a token
of an incompatible type with the previous one.

  * •

$\mathbf{TSE_{time}}$: a wrong predicted Position value, that goes back or
stay in time.

  * •

$\mathbf{TSE_{dupn}}$ (duplicated note): a note predicted whereas it was
already being played at the current time being.

  * •

$\mathbf{TSE_{nnof}}$ (no NoteOff): a NoteOn token been predicted with no
following NoteOff token to end it.

  * •

$\mathbf{TSE_{nnon}}$ (no NoteOn): NoteOff token predicted whereas this note
was not being played.

For each generated token, a rule-based function analyzes its type and value to
determine if both are valid, or which type of error was made otherwise. The
overall number of errors is normalized by the number of predicted tokens.

Tokenization |  $\mathbf{TSE_{type}}$ $\downarrow$ |  $\mathbf{TSE_{time}}$ $\downarrow$ |  $\mathbf{TSE_{dupn}}$ $\downarrow$ |  $\mathbf{TSE_{nnon}}$ $\downarrow$ |  $\mathbf{TSE_{nnof}}$ $\downarrow$
---|---|---|---|---|---
TS \+ Dur | $<10^{-3}$ | - | 0.014 | - | -
TS \+ NOff | $<10^{-3}$ | - | 0.001 | 0.109 | 0.040
Pos \+ Dur | 0.002 | 0.113 | 0.032 | - | -
Pos \+ NOff | 0.002 | 0.127 | 0.005 | 0.095 | 0.066

Table 2: Prediction error ratios when performing autoregressive generation. -
symbol stands for not concerned, and can be interpreted as 0.

The results are reported in table 2. We first observe that the type error
ratios are lower than in other categories. This is excepted since it is less
computationally demanding to model the possible next types depending solely on
the last one, rather than on the value of the predicted token, for which the
validity depends on a the whole previous context.

Position tokens bring almost no type errors, but a noticeable proportion of
time errors. When decoding tokens to notes, this means that the time may go
backward, and resulting in sections of overlapping notes.

Although Duration tokens seem to bring slightly more note duplication errors,
the use of NoteOn and NoteOff tokens results in a considerable proportion of
note prediction errors. NoteOff tokens predicted while the associated note was
not being played ($\mathbf{TSE_{nnon}}$) does not have undesirable
consequences when decoding tokens to notes, but it pointlessly extends the
sequence, reducing the efficiency of the model, and may mislead the next token
predictions. Additionaly, NoteOn tokens predicted without associated NoteOff
($\mathbf{TSE_{nnof}}$) result in notes not properly ended. This error can
only be handled by applying a maximum note duration after decoding. Explicit
Duration tokens allows to specify in advance this information, for both short
and long notes. Conversely, with NoteOff tokens, the note duration information
is implicit and inferred by the combinations of NoteOn, NoteOff and time
tokens. This can be interpreted as an extra effort for the model.
Consequently, some uncertainty on the duration accumulates over autoregressive
steps during generation. Based on these results, the best tradeoff ensuring
good predictions seems to represent time with TimeShift tokens and note
duration with Duration tokens.

In fig. 1 we observe the positions within bars and durations of the generated
notes. In all cases, onset positions are more distributed at the beginning of
the bars. This is especially the case with Bar and Position tokens, for which
we may find unexpected rests at the end of bars, when Bar tokens are predicted
during the generation before that the current bar is completed. The TS \+ Dur
combination places note onsets much more on even positions. The probability
mass of TimeShift tokens (especially for short values) seems to be much
higher. However, this is not the case for the TS \+ NOff combination, as
TimeShift tokens have to be predicted to move the time on odd positions of
note offsets. As shown in fig. 2, right after the model is likely to predict a
next note, resulting in evenly distributed onset distribution.

Finally, the use of NoteOff tokens tends to produce longer note durations,
especially when combined with Position tokens. In this last case, we can
assume that the model might "forget" the notes currently being played, and
that it struggles more to model their durations that have to be implicitly
deduced from the past Bar and Position tokens.

Tokenization | Top-20 composers $\uparrow$ | Top-100 composers $\uparrow$ | Emotion $\uparrow$
---|---|---|---
TS \+ Dur | 0.973 | 0.941 | 0.983
TS \+ NOff | 0.962 | 0.930 | 0.962
Pos \+ Dur | 0.969 | 0.927 | 0.963
Pos \+ NOff | 0.963 | 0.925 | 0.956

Table 3: Accuracy on classification tasks.

##  5 Classification

For some classification tasks, symbolic music is arguably better suited than
audio or piano roll. This is particularly true for classical music feature
classification, such as composer [32]. Mono-instrument music with complex
melodies and harmonies and no particular audio effect benefit from being
represented as discrete for classification and modeling tasks. Given this, it
felt important to us to conduct experiments on such task.

We choose to experiment with the GiantMIDI [33] dataset for composer
classification and the EMOPIA [34] dataset for emotion classification. The
results, as shown in table 3, indicate that there is very little difference
between the various tokenization methods. However, the combination of
TimeShift and Duration consistently outperforms the others by one point

The classification task involves modeling the patterns from data that are
characteristic to composers or emotions. Here, it seems that the time distance
between notes, and their explicit duration play a role in these task, more
than note offsets or onset positions. This comes with no surprise for the
composer classification task, considering that the data is largely composed of
complex music with dense melodies and harmonies, featuring mostly short
successive notes. Intuitively, patterns of note successions and chords are
more easily distinguishable with explicit durations. With implicit note
durations, the overall patterns must be deduced by the combinations of NoteOn
and NoteOff tokens while keeping track of the time.

##  6 Sequence representation

(a) Pitch +1

(b) Pitch +12

(c) Velocity +1

(d) Pitch +12 and Velocity +1

Figure 3: Density plots of cosine similarities between pairs of original and
augmented token sequences.

The last task that we wished to explore is sequence representation. It
consists in obtaining a fixed size embedding representation of an input
sequence of tokens $p_{\theta}:\mathbb{V}^{L}\mapsto\mathbb{R}^{d}$. Here
$\mathbb{V}\subset\mathbb{N}$ denotes the token ids of the vocabulary
$\mathcal{V}$, $L$ is the variable input sequence length, and $d$ the size of
embeddings. In other words, the model learns to project an input token
sequence into a embedding space, thus providing a universal representation. We
find this task interesting and well-suited to assess model performances as it
directly trains it to model the relationships between tokens within the input
sequence and between different representations themselves. While the real-
world applications of this task for symbolic music are currently limited, it
serves as a useful benchmarking technique for measuring how tokenization
impacts the learning of models.

This task has previously been addressed in natural language processing by
SentenceBERT [35] or SimCSE [36]. We adopted the approach of the latter, which
uses contrastive learning to train the model to learn sequence
representations, for which similar inputs have higher cosine similarities. The
sequence embedding is obtained by performing a pooling operation on the output
hidden states of the model. We decided to use the last hidden state of the BOS
token position, as it yielded good results with SimCSE[36]555SimCSE uses a CLS
token which is equivalent to BOS in our case.. We trained the models with the
dropout method: during training, a batch of $n$ sequences
$\mathcal{X}=\\{\mathbf{x}_{i}\\}_{i=0}^{n}$ is passed twice to the model, but
with different dropout masks, resulting in different output sequence
embeddings $\mathcal{Z}=\\{\mathbf{z}_{i}\\}_{i=0}^{N}$ and
$\bar{\mathcal{Z}}=\\{\bar{\mathbf{z}_{i}}\\}_{i=0}^{N}$. Although the dropout
altered the outputs, most of the input information is still accessible to the
model. Hence, we expect pairs of sequence embeddings
$\left(\mathbf{z}_{i},\bar{\mathbf{z}_{i}}\right)$ to be similar, so having a
high cosine similarity. To achieve this objective, we train the model with a
loss function defined by the cross-entropy for in-batch pairwise cosine
similarities ($\mathrm{sim}$):

$\ell_{i}=-\log\frac{e^{\mathrm{sim}(\mathbf{z}_{i},\bar{\mathbf{z}_{i}})/\tau}}{\sum_{j=1}^{N}e^{\mathrm{sim}(\mathbf{z}_{i},\bar{\mathbf{z}_{j}})/\tau}}$
(1)

As a result, the model will effectively learn to create similar sequence
embeddings for similar inputs, while pushing apart those with dissimilarities.
We kept a 0.1 dropout value to train the models, and used the GiantMIDI
dataset [33].

Evaluation of sequence representation is intuitively performed by measuring
the distances and similarities of pairs of similar sequences. We resort to
data augmentation by shifting the pitch and velocity of the sequences in order
to get pairs of similar music sequences. The augmented data keeps most of the
information of the original data. As such, the models are expected to produce
similar embeddings for pairs of original-augmented sequence. Ideally, the
cosine similarity should be high, yet not to be equal to 1, as this would
indicate that the model fails to capture the differences between the two
sequences. The results, presented in fig. 3, indicate that Position-based
tokenizations perform slightly better. Therefore, it appears that explicit
note onset and offset positions information facilitates models to obtains a
universal musical representation.

Unlike classification, the contrastive learning objective models the
similarities and dissimilarities between examples in the same batch. In this
context, note onset and offset positions appear to be helpful for the models
to distinguish music.

We also note the contrasting results when augmenting the velocity. Increasing
it by one unit, which would be equivalent to playing just a little bit louder,
have arguably a very small impact. As a result, the models mostly produces
embeddings that are almost identical for the original and the augmented
sequences, but also exhibits uncertainty for a notable proportion of samples.

To complement these results, we estimated the isotropy of sets of sequence
embeddings. Isotropy measures the uniformity of the variance of a set points
in a space. More intuitively, in an isotropic space, the embeddings are evenly
distributed. It has been associated with improved performances in natural
language tasks [37, 38, 39], because embeddings are more equally distant
proportionally to the density of their area, and are in turn more distinct and
distinguishable. We choose to estimate it with the intrinsic dimension of the
sets of embeddings. Intrinsic dimension is the number of dimensions required
to represent a set of points. It can be estimated by several manners [40]. We
choose Principal Component Analysis (PCA) [41], method of moments (MOM) [42],
Two Nearest Neighbors (TwoNN) [43] and FisherS [44]. The results, reported in
table 4, show that the embeddings created from the Pos \+ Dur combination tend
to occupy more space across the dimension of the model, and are potentially
better distributed.

Tokenization | lPCA $\uparrow$ | MOM $\uparrow$ | TwoNN $\uparrow$ | FisherS $\uparrow$
---|---|---|---|---
TS \+ Dur | 213 | 42.6 | 34.3 | 17.5
TS \+ NOff | 161 | 43.7 | 32.7 | 17.5
Pos \+ Dur | 146 | 39.1 | 33.1 | 17.1
Pos \+ NOff | 177 | 45.2 | 35.6 | 17.8

Table 4: Intrinsic dimension of sequence embeddings, as an estimation of
isotropy.

##  7 Conclusion

We have discussed the importance of different aspects of symbolic music
tokenization, and focused on two major ones: the time and note duration
representations. We showed that different tokenization strategies can lead to
different model performances due to the explicit information carried by
tokens, depending on the task at hand.

Explicitly representing note duration leads to better classification accuracy
as it helps the models to capture the melodies and harmonies of a music.
Modeling durations, when represented implicitly, adds an extra effort to the
model. However, the note offset position information it brings have been found
to be more discriminative and effective in our contrastive learning
experiment.

For music generation, the time representation plays a significant role, for
which the note onset and offsets distributions vary due to the successions of
token types. Implicit note durations are less suited for the autoregressive
nature of this task, from a prediction error perspective, and sometimes
"forgetting" notes being played resulting in higher durations.

We consider this work as a first step into the study of music tokenization for
music modeling. We did not experiment with the other music tokenization
dimensions, and other important tasks such as music transcription or synthesis
for which we could find different results. For transcription, input audio
frames are likely to contain the ending or beginning of notes, without being
able to identify their onset or offset notes. Explicit Duration tokens might
confuse models. Furthermore, we believe that more musical reasoning tasks,
imposing the model to perform logic deductions to retrieve implicit
information from the data, might give more insightful results. Future research
will further explore these questions.

## References

  * [1] J.-P. Briot, G. Hadjeres, and F.-D. Pachet, _Deep Learning Techniques for Music Generation_ , ser. Computational Synthesis and Creative Systems. Springer International Publishing, 2020. [Online]. Available: https://www.springer.com/gp/book/9783319701622
  * [2] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in Neural Information Processing Systems_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017\. [Online]. Available: https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf
  * [3] S. Oore, I. Simon, S. Dieleman, D. Eck, and K. Simonyan, “This time with feeling: Learning expressive musical performance,” _Neural Computing and Applications_ , vol. 32, p. 955–967, 2018. [Online]. Available: https://link.springer.com/article/10.1007/s00521-018-3758-9
  * [4] Y.-S. Huang and Y.-H. Yang, “Pop music transformer: Beat-based modeling and generation of expressive pop piano compositions,” in _Proceedings of the 28th ACM International Conference on Multimedia_ , ser. MM ’20. New York, NY, USA: Association for Computing Machinery, 2020, p. 1180–1188. [Online]. Available: https://doi.org/10.1145/3394171.3413671
  * [5] M. Zeng, X. Tan, R. Wang, Z. Ju, T. Qin, and T.-Y. Liu, “MusicBERT: Symbolic music understanding with large-scale pre-training,” in _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_. Online: Association for Computational Linguistics, 8 2021, pp. 791–800. [Online]. Available: https://aclanthology.org/2021.findings-acl.70
  * [6] N. Fradet, J.-P. Briot, F. Chhel, A. El Fallah Seghrouchni, and N. Gutowski, “MidiTok: A python package for MIDI file tokenization,” in _Extended Abstracts for the Late-Breaking Demo Session of the 22nd International Society for Music Information Retrieval Conference_ , 2021. [Online]. Available: https://github.com/Natooz/MidiTok
  * [7] A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi, “The curious case of neural text degeneration,” in _International Conference on Learning Representations_ , 2020. [Online]. Available: https://openreview.net/forum?id=rygGQyrFvH
  * [8] L.-C. Yang and A. Lerch, “On the evaluation of generative models in music,” _Neural Comput. Appl._ , vol. 32, no. 9, p. 4773–4784, 5 2020. [Online]. Available: https://doi.org/10.1007/s00521-018-3849-7
  * [9] C. Helwe, C. Clavel, and F. M. Suchanek, “Reasoning with transformer-based models: Deep learning, but shallow reasoning,” in _3rd Conference on Automated Knowledge Base Construction_ , 2021. [Online]. Available: https://openreview.net/forum?id=Ozp1WrgtF5_
  * [10] Q. Zhang, S. Chen, D. Xu, Q. Cao, X. Chen, T. Cohn, and M. Fang, “A survey for efficient open domain question answering,” in _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_. Toronto, Canada: Association for Computational Linguistics, Jul. 2023, pp. 14 447–14 465. [Online]. Available: https://aclanthology.org/2023.acl-long.808
  * [11] Y. Zhou, A. I. Muresanu, Z. Han, K. Paster, S. Pitis, H. Chan, and J. Ba, “Large language models are human-level prompt engineers,” in _The Eleventh International Conference on Learning Representations_ , 2023. [Online]. Available: https://openreview.net/forum?id=92gvk82DE-
  * [12] G. Hadjeres, F. Pachet, and F. Nielsen, “DeepBach: a steerable model for Bach chorales generation,” in _Proceedings of the 34th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, D. Precup and Y. W. Teh, Eds., vol. 70. PMLR, 8 2017, pp. 1362–1371. [Online]. Available: https://proceedings.mlr.press/v70/hadjeres17a.html
  * [13] B. L. Sturm, J. F. Santos, and I. Korshunova, “Folk music style modelling by recurrent neural networks with long short-term memory units,” in _Extended abstracts for the Late-Breaking Demo Session of the 16th International Society for Music Information Retrieval Conference_ , 2015. [Online]. Available: https://ismir2015.ismir.net/LBD/LBD13.pdf
  * [14] W.-Y. Hsiao, J.-Y. Liu, Y.-C. Yeh, and Y.-H. Yang, “Compound word transformer: Learning to compose full-song music over dynamic directed hypergraphs,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 1, pp. 178–186, 5 2021. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/16091
  * [15] Y. Ren, J. He, X. Tan, T. Qin, Z. Zhao, and T.-Y. Liu, “Popmag: Pop music accompaniment generation,” in _Proceedings of the 28th ACM International Conference on Multimedia_. Association for Computing Machinery, 2020, p. 1198–1206. [Online]. Available: https://doi.org/10.1145/3394171.3413721
  * [16] C. Donahue, H. H. Mao, Y. E. Li, G. W. Cottrell, and J. J. McAuley, “Lakhnes: Improving multi-instrumental music generation with cross-domain pre-training,” in _Proceedings of the 20th International Society for Music Information Retrieval Conference, ISMIR 2019, Delft, The Netherlands, November 4-8, 2019_ , 2019, pp. 685–692. [Online]. Available: http://archives.ismir.net/ismir2019/paper/000083.pdf
  * [17] C. Payne, “Musenet,” 2019. [Online]. Available: https://openai.com/blog/musenet
  * [18] J. Liu, Y. Dong, Z. Cheng, X. Zhang, X. Li, F. Yu, and M. Sun, “Symphony generation with permutation invariant language model,” in _Proceedings of the 23rd International Society for Music Information Retrieval Conference_. Bengalore, India: ISMIR, Dec. 2022. [Online]. Available: https://arxiv.org/abs/2205.05448
  * [19] N. Fradet, N. Gutowski, F. Chhel, and J.-P. Briot, “Byte Pair Encoding for symbolic music,” in _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_. Singapore: Association for Computational Linguistics, Dec. 2023. [Online]. Available: https://arxiv.org/abs/2301.11975
  * [20] M. Kermarec, L. Bigo, and M. Keller, “Improving tokenization expressiveness with pitch intervals,” in _Extended Abstracts for the Late-Breaking Demo Session of the 23nd International Society for Music Information Retrieval Conference_ , 2022. [Online]. Available: https://ismir2022program.ismir.net/lbd_369.html
  * [21] G. Hadjeres and L. Crestel, “The piano inpainting application,” 2021. [Online]. Available: https://arxiv.org/abs/2107.05944
  * [22] D. von Rütte, L. Biggio, Y. Kilcher, and T. Hofmann, “FIGARO: Controllable music generation using learned and expert features,” in _The Eleventh International Conference on Learning Representations_ , 2023\. [Online]. Available: https://openreview.net/forum?id=NyR8OZFHw6i
  * [23] J. Ens and P. Pasquier, “Mmm : Exploring conditional multi-track music generation with the transformer,” 2020. [Online]. Available: https://arxiv.org/abs/2008.06048
  * [24] H.-W. Dong, K. Chen, S. Dubnov, J. McAuley, and T. Berg-Kirkpatrick, “Multitrack music transformer,” in _ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2023, pp. 1–5. [Online]. Available: https://ieeexplore.ieee.org/document/10094628
  * [25] O. Khattab and M. Zaharia, “Colbert: Efficient and effective passage search via contextualized late interaction over bert,” in _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , ser. SIGIR ’20. New York, NY, USA: Association for Computing Machinery, 2020, p. 39–48. [Online]. Available: https://doi.org/10.1145/3397271.3401075
  * [26] J. Ching and y.-h. Yang, “Learning to generate piano music with sustain pedals,” in _Extended Abstracts for the Late-Breaking Demo Session of the 22nd International Society for Music Information Retrieval Conference_ , 2021\. [Online]. Available: https://archives.ismir.net/ismir2021/latebreaking/0000017.pdf
  * [27] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of deep bidirectional transformers for language understanding,” in _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_. Minneapolis, Minnesota: Association for Computational Linguistics, Jun. 2019, pp. 4171–4186. [Online]. Available: https://aclanthology.org/N19-1423
  * [28] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, J. Davison, S. Shleifer, P. von Platen, C. Ma, Y. Jernite, J. Plu, C. Xu, T. L. Scao, S. Gugger, M. Drame, Q. Lhoest, and A. M. Rush, “Transformers: State-of-the-art natural language processing,” in _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_. Online: Association for Computational Linguistics, Oct. 2020, pp. 38–45. [Online]. Available: https://www.aclweb.org/anthology/2020.emnlp-demos.6
  * [29] P. Micikevicius, S. Narang, J. Alben, G. Diamos, E. Elsen, D. Garcia, B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh, and H. Wu, “Mixed precision training,” in _International Conference on Learning Representations_ , 2018. [Online]. Available: https://openreview.net/forum?id=r1gs9JgRZ
  * [30] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015. [Online]. Available: http://arxiv.org/abs/1412.6980
  * [31] Z. Wang, K. Chen, J. Jiang, Y. Zhang, M. Xu, S. Dai, G. Bin, and G. Xia, “Pop909: A pop-song dataset for music arrangement generation,” in _Proceedings of 21st International Conference on Music Information Retrieval, ISMIR_ , 2020. [Online]. Available: https://arxiv.org/abs/2008.07142
  * [32] Q. Kong, K. Choi, and Y. Wang, “Large-scale midi-based composer classification,” 2020. [Online]. Available: https://arxiv.org/abs/2010.14805
  * [33] Q. Kong, B. Li, J. Chen, and Y. Wang, “Giantmidi-piano: A large-scale midi dataset for classical piano music,” in _Transactions of the International Society for Music Information Retrieval_ , vol. 5, 2021, pp. 87–98. [Online]. Available: https://transactions.ismir.net/articles/10.5334/tismir.80/#
  * [34] H. Hung, J. Ching, S. Doh, N. Kim, J. Nam, and Y. Yang, “EMOPIA: A multi-modal pop piano dataset for emotion recognition and emotion-based music generation,” in _Proceedings of the 22nd International Society for Music Information Retrieval Conference, ISMIR 2021, Online, November 7-12, 2021_ , J. H. Lee, A. Lerch, Z. Duan, J. Nam, P. Rao, P. van Kranenburg, and A. Srinivasamurthy, Eds., 2021, pp. 318–325. [Online]. Available: https://archives.ismir.net/ismir2021/paper/000039.pdf
  * [35] N. Reimers and I. Gurevych, “Sentence-bert: Sentence embeddings using siamese bert-networks,” in _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing_. Association for Computational Linguistics, 11 2019. [Online]. Available: https://arxiv.org/abs/1908.10084
  * [36] T. Gao, X. Yao, and D. Chen, “SimCSE: Simple contrastive learning of sentence embeddings,” in _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_. Online and Punta Cana, Dominican Republic: Association for Computational Linguistics, Nov. 2021, pp. 6894–6910. [Online]. Available: https://aclanthology.org/2021.emnlp-main.552
  * [37] T. Wang and P. Isola, “Understanding contrastive representation learning through alignment and uniformity on the hypersphere,” in _Proceedings of the 37th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, H. D. III and A. Singh, Eds., vol. 119. PMLR, Jul. 2020, pp. 9929–9939. [Online]. Available: https://proceedings.mlr.press/v119/wang20k.html
  * [38] D. Biś, M. Podkorytov, and X. Liu, “Too much in common: Shifting of embeddings in transformer language models and its implications,” in _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_. Online: Association for Computational Linguistics, Jun. 2021, pp. 5117–5130. [Online]. Available: https://aclanthology.org/2021.naacl-main.403
  * [39] Y. Liang, R. Cao, J. Zheng, J. Ren, and L. Gao, “Learning to remove: Towards isotropic pre-trained bert embedding,” in _Artificial Neural Networks and Machine Learning – ICANN 2021: 30th International Conference on Artificial Neural Networks, Bratislava, Slovakia, September 14–17, 2021, Proceedings, Part V_. Berlin, Heidelberg: Springer-Verlag, 2021, p. 448–459. [Online]. Available: https://doi.org/10.1007/978-3-030-86383-8_36
  * [40] J. Bac, E. M. Mirkes, A. N. Gorban, I. Tyukin, and A. Zinovyev, “Scikit-dimension: A python package for intrinsic dimension estimation,” _Entropy_ , vol. 23, no. 10, 2021. [Online]. Available: https://www.mdpi.com/1099-4300/23/10/1368
  * [41] K. Fukunaga and D. Olsen, “An algorithm for finding intrinsic dimensionality of data,” _IEEE Transactions on Computers_ , vol. C-20, no. 2, pp. 176–183, 1971. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/1671801
  * [42] L. Amsaleg, O. Chelly, T. Furon, S. Girard, M. E. Houle, K.-I. Kawarabayashi, and M. Nett, “Extreme-value-theoretic estimation of local intrinsic dimensionality,” _Data Mining and Knowledge Discovery_ , vol. 32, no. 6, pp. 1768–1805, 11 2018. [Online]. Available: https://hal.archives-ouvertes.fr/hal-01864580
  * [43] E. Facco, M. d’Errico, A. Rodriguez, and A. Laio, “Estimating the intrinsic dimension of datasets by a minimal neighborhood information,” _Scientific Reports_ , vol. 7, no. 1, p. 12140, 9 2017. [Online]. Available: https://doi.org/10.1038/s41598-017-11873-y
  * [44] L. Albergante, J. Bac, and A. Zinovyev, “Estimating the effective dimension of large biological datasets using fisher separability analysis,” in _International Joint Conference on Neural Networks (IJCNN)_ , 7 2019, pp. 1–8. [Online]. Available: https://arxiv.org/abs/1901.06328


# Learning Indoor Layouts from Simple Point-Clouds

Md. Tareq Mahmood  Bangladesh University of Engineering and
TechnologyDhakaBangladesh<EMAIL_ADDRESS>and  Mohammed Eunus Ali
Bangladesh University of Engineering and TechnologyDhakaBangladesh
<EMAIL_ADDRESS>
###### Abstract.

Reconstructing a layout of indoor spaces has been a crucial part of growing
indoor location based services. One of the key challenges in the proliferation
of indoor location based services is the unavailability of indoor spatial maps
due to the complex nature of capturing an indoor space model (e.g., floor
plan) of an existing building. In this paper, we propose a system to
automatically generate floor plans that can recognize rooms from the point-
clouds obtained through smartphones like Google’s Tango. In particular, we
propose two approaches - a Recurrent Neural Network based approach using
Pointer Network and a Convolutional Neural Network based approach using Mask-
RCNN to identify rooms (and thereby floor plans) from point-clouds.
Experimental results on different datasets demonstrate approximately 0.80-0.90
Intersection-over-Union scores, which show that our models can effectively
identify the rooms and regenerate the shapes of the rooms in heterogeneous
environment.

Deep Neural Network, Geometric Deep Learning, Image Segmentation, Indoor
Mapping

##  1\. Introduction

With the recent development of smartphone based technologies, indoor location
based services (Chon and Cha, 2011; Liu et al., 2012; Ran et al., 2004; Han et
al., 2014) are increasingly attracting attention from both academia and
industry in recent years due to their diversified applications. These indoor
applications include navigating inside a shopping mall or an airport,
assisting a visually challenged person to navigate on his own, enabling first
responders to track down a person in emergency inside an unknown building, and
helping tourists to navigate inside unfamiliar museums and art galleries. The
detailed spatial map (i.e., floor plans) of the indoor space is a prerequisite
for enjoying the benefits of these services. Though, indoor maps are now
available for some large installations like airports or shopping complexes,
the detailed indoor maps are not readily available for most of the small and
medium sized indoor spaces such as home and commercial office spaces. One of
the main reasons for the unavailability of the detailed maps of these indoor
spaces is the absence of cheap and ubiquitous technologies for re-creating the
indoor maps of existing buildings. In this paper, we propose a smartphone
assisted solution that exploits deep learning (LeCun et al., 2015) to
automatically generate the detailed layout of the floor plan from the point-
clouds obtained from a simple scan by a mobile phone like Google’s Tango
device.

(a) Raw Point-cloud (b) Indoor Layout Figure 1. Extracting indoor layout from
point-clouds. Left: the point-cloud collected from an indoor scene. Right:
rooms extracted from the scene.

Traditionally, re-creating floor-plans require the data-acquisition of the
indoor spaces through laser sensors (Vosselman, 2014; Jung et al., 2017),
sonar sensors (Tardós et al., 2002) or smartphone video (Pintore et al., 2014;
Pintore and Gobbetti, 2014), as the first step, and then generation of
detailed floor plans of building through human intervention. Recently, some
researchers have used expensive heavyweight equipment like LiDAR to capture
point-clouds (Vosselman, 2014; Jung et al., 2017) of an indoor space, and then
develop different algorithms to automatically identify different objects. Jung
et al. (Jung et al., 2017) propose an automatic room detection system from the
_complete_ point-clouds of the space. The key idea of their approach is to
first select floors and ceilings points, then select the points near the
ceiling and finally project those points to find a layout. The major
limitation of this approach is as follows: they require the complete point-
clouds that include floor and ceiling of the space, which is hard to capture.
Thus if a portion of ceiling or floor is missing in the point-cloud, this
approach fails to remove background clutters and thereby cannot detect rooms
in such scenarios. Similarly, Armeni et al. (Armeni et al., 2016) propose a
system that first detects the vertical planes of the walls, and then divides
the entire scene into multiple 3D spaces based on the detected vertical
planes, and finally merges adjoining 3D spaces if there is no wall between
them. The major limitation of this approach is as follows. They assume that
the walls are aligned with X and Y axis (i.e., Manhattan Assumption) and hence
fails to detect _rooms with acute or obtuse angles or curved walls_. More
recently, a neural network architecture, FloorNet (Liu et al., 2018) has been
proposed that converts an RGBD video stream of a large 3D space into floor-
plan. They have used both point clouds and RGB images to generate the floor-
plan. The major limitation of their approach is that they fail to generate
layout when the point-clouds generated from the scan is incomplete or noisy
(e.g., large gaps for windows, missing a portion of a wall, furniture, etc.),
which is the case for point-clouds generated by a simple scan using a hand-
held device like Google’s Tango.

To alleviate the above limitations, in this paper, we propose a comprehensive
deep learning based room detection and indoor layout generation technique. One
may assume that simple geometric techniques like convex hull or image
processing techniques like contour detection can be used to detect rooms and
generate layout from point-clouds. However, these have following major
challenges. (i) Though convex hull algorithm can be used to detect the
boundary of a single room, in a multi-room scenario, convex hull ends up in
detecting boundary of all the rooms combined. (ii) The contour detection works
when each room has closed boundary, whereas often point-cloud of a scene will
have gaps, and contour detection technique may merge multiple rooms into one
room.

In this paper, we propose two deep learning based techniques: the first method
is based on the concept of geometric shape learning, and the second one is
based on image segmentation network, to automatically build indoor maps
showing locations of rooms from noisy and incomplete point-clouds obtained
from the scanning of the physical space by modern smartphones. The key
intuition of our geometric learning approach comes from the proposed Pointer
Network (Vinyals et al., 2015b) that was originally proposed to learn
triangulation and convex hull from a given set of points. We adopt the Pointer
Network architecture to learn rooms in terms of sequence of connected
significant border points. On the other hand, the key motivation of exploiting
the image segmentation network, namely Mask R-CNN (He et al., 2017), to
identify rooms and layouts, comes from the recent success in object
identification from image using Mask R-CNN (He et al., 2017). One of the main
challenges in applying these deep learning techniques for our problem is the
scarcity of 3D indoor scene data. To tackle this problem, we introduce a novel
approach towards generating a synthetic indoor dataset to train deep learning
models, which shows satisfactory performance in real-world evaluation.

Our approach works in two steps: In the first step, we extract boundary
candidate points from point-clouds, which essentially depicts different walls
of the indoor space. In the next step, we build deep learning network, i.e.,
PtrNet or Mask R-CNN, to learn rooms from these candidate point sets.

To detect walls from from point-clouds, we adapt the histogram projection
based technique, which is a variant of the technique proposed by Adan et al.
(Adan and Huber, 2011). We first project horizontal coordinate of each point
onto the floor to get a 2D histogram. If there is a wall on a bin of the 2D
histogram, it usually has more points than those bins that do not have any
wall on them. We introduce a dynamic and robust threshold derived from the
data. We keep only the bins containing points greater than the threshold. This
gives us the positions of walls in the 2D histogram as an image.

As the second step, to identify rooms from the candidate point sets, we build
two neural network models to learn individual rooms from the 2D histogram of
point-clouds. The key intuition of using PtrNet to identify rooms is to learn
significant point set that determine the shape of each room from a given
sequence of point clouds. Essentially in our case, we model the PtrNet in such
a way that it takes a candidate point sets (point sets representing the walls)
as input and output fixed point set polygons representing rooms of different
shapes. This flexible model allows us to learn multiple rooms of different
shapes and sizes in an indoor space. Since the effectiveness of PtrNet largely
depends on a good spatial order of input point sets, in this paper we propose
different variants of input point sets sorting methods before we feed them
into a network. Since sorting the input candidate point sets from a random
scan is a challenging task and it can affect the performance of the model
significantly, we resort to an alternative network that can identify the
entire room as a mask, which is our second approach. The Mask R-CNN takes an
image as input and a set of binary masks as label/output. Each mask is for an
individual room and points to the area where the room is located on that
image. In our case, an input is the image showing the walls, and the
corresponding label is a set of masks for each of the rooms in that scene.

The contributions of this paper can be summarized as follows.

  * •

We develop first comprehensive deep learning based solutions to automatically
identify rooms and 2D layouts of an indoor space from a noisy point-clouds
data obtained through mobile devices.

  * •

We investigate two different paradigms of deep learning: one is geometric
learning and the other is image segmentation based learning for learning rooms
and layouts of an indoor space, and subsequently propose two methods to
identify rooms of different shapes and sizes.

  * •

Extracting rooms and layouts using deep learning is challenging mainly due to
scarcity of 3D indoor scene data. To solve this problem, we introduce a novel
approach to generate a synthetic dataset of indoor scenes.

  * •

We conduct extensive experiments on different datasets to evaluate the
performance of our proposed approached in identifying different types of rooms
that include rectangular, rectilinear, curved walls, non-right angles and also
validate performance with real-world methods.

The rest of the paper is organized as follows. We discuss related research on
indoor mapping and layout generation in Section 2. Then, we describe the
methodology in Section 3 that include two deep learning based models for room
and layout generation. After that, we discuss our dataset generation approach
for deep learning models and other experimental setup in Section 4. We present
our results both on synthetic test data and real-world test data in Section 5.
Finally, we conclude the paper with possible future directions in Section 6.

##  2\. Related Works

Indoor mapping and localization has been an interesting research area due to
its wide range of real world applications. In this section, we will review
some of the related studies in this field.

Specialized Sensors for Indoor Mapping. Vosselman et al. (Vosselman, 2014)
present an indoor mapping system based on three 2D laser scanners. Using laser
scanner data, it estimates planes of floor, ceiling and wall simultaneously.
Tardos et al. (Tardós et al., 2002) describe a technique to generate feature-
based stochastic maps using Polaroid sonar sensors. Their method extracts
environmental features, such as straight lines, corners from noisy sensor
data.

Smart-phone Based Indoor Mapping. Pintore et al. (Pintore et al., 2014;
Pintore and Gobbetti, 2014; Pintore et al., 2016, 2017) introduce several
methods to build indoor maps using smartphones. In (Pintore et al., 2014;
Pintore and Gobbetti, 2014) they present a system to reconstruct indoor scenes
using common smartphone features, such as camera and magnetometer. Although
their system struggles in curved walls and narrow spaces, this fascinatingly
simple system is able to map multi-room indoor scenes in almost all cases.
Pradhan et al. (Pradhan et al., 2018) use smartphone-based acoustic mapping
system to reconstruct indoor walls, but do not extract rooms from it.

Recent Point-clouds Based Indoor Mapping. In 2015, Google’s Project Tango
developed an application (tan, [n. d.]) for Tango enabled devices to create
rough floor plan. This application detects free spaces, furniture and walls.
Although the produced indoor maps mostly preserved their original shapes,
their outlines are noisy and fragmented. Murali et al. (Murali et al., 2017)
present a system to generate 2D indoor model from existing 3D point-cloud.
However, this method assumes all angles between walls to be right angle.
Recently, Angladon et al. (Angladon et al., 2018) present an real-time
approach to produce accurate floor plans of single rooms using Tango
Development Kit. Their approach is similar to Project Tango’s Floorplanner
application (tan, [n. d.]). Although, they have their own binary classifier to
differentiate between clutter and wall. Babacan et al. (Babacan et al., 2017)
propose a deep learning approach towards semantic segmentation of indoor
point-cloud. They divide 3D scenes into voxels and classify each voxel into
classes (e.g. walls, desks, chairs, humans etc.) using 3D Convolutional Neural
Network. None of these approaches provide any information about rooms. Jung et
al. (Jung et al., 2017) propose an automatic room detection system from point-
clouds. They estimate the height of the scene by detecting the floor and the
ceiling of the scene. Then, they avoid background clutters by selecting those
points which lie in between the plane of the ceiling and a horizontal plane
just below the ceiling. After that, they project those points onto a 2D binary
map and close any opening, such as a doorway, between two adjoining rooms.
Thus, the 2D binary map is segmented into regions, which are identified as
rooms. Armeni et al. (Armeni et al., 2016) propose a system that can
semantically segment large scale 3D point-cloud of an entire building. As a
first step, they divide point-clouds into spaces (e.g. rooms). However, both
of these approaches are performed on complete point-clouds of scenes collected
by special equipment like LiDAR or laser sensors. Moreover, if two adjoining
rooms have large gaps in the shared wall, these methods will detect both of
them as a single room. Recently, A deep learning based approach (Liu et al.,
2018) propose a neural network architecture FloorNet, which turns a RGBD video
stream covering a large 3D space into floor-plan. It uses not only point-
clouds, but also RGB images. Although FloorNet is able to generalize well from
low amount of training data, it fails to estimate layout during noisy point-
clouds, missing portions or incomplete scanning.

##  3\. Methodology

Our approach consists of two major steps: wall detection from point-clouds and
room detection from walls. We propose two deep learning strategies, one that
learns geometric borders in terms of sequence of points, and the other that
learns masks of different rooms, to identify rooms from detected walls in the
first phase. In this section, we explain these steps in detail.

###  3.1. Acquisition of Point-clouds

We acquire 3D reconstruction of indoor scenes in the form of 3D meshes or
point-clouds with the help of smart devices like Google’s Tango. Usually in 3D
meshes or point-clouds of indoor scenes, wall surfaces are occluded by
furniture like tables, chairs, beds, wardrobes, shelves etc., and also by
humans, curtains and other background clutters. This makes indoor modeling a
more challenging task. We use wall detection module to exclude all kinds of
background clutters and keep only the wall surfaces. Even after wall
extraction, we cannot fully recover shapes of the rooms. Because, often user-
generated 3D meshes or point-clouds have some missing portions due to openings
like doors and windows or due to an incomplete scan. Thus, often extracted
walls have gaps in them. Moreover, the wall detection module cannot always
remove all of the background clutters. As a result, extracted walls can often
be distorted and noisy. To handle these challenges, we use two deep learning
approaches which are trained to extract rooms even when there are gaps and
noises in extracted walls.

###  3.2. Wall Detection

The first step of our process is to identify walls of different rooms from
given point-clouds generated from mobile scan of the indoor space. Since the
3D scan may be of different formats like 3D mesh or simple point-clouds, as a
first step of the wall detection process, we first need to sample points
representing the entire indoor space and then detect walls from these point
sets.

####  3.2.1. Sampling Points

We start with the 3D reconstruction of the indoor scene of interest. Our
target is to pass a point-cloud with fixed $N$ number of points to the next
stage. If the 3D reconstruction is already captured in the point-cloud format,
we just randomly select $N$ points from it to get a sampled point-cloud. If
reconstruction is done in triangular mesh format, we do the following to get a
sampled point-cloud. A 3D triangular mesh is a collection of triangles. To
sample a single point, a triangle is randomly chosen with a weighted
probability proportional to its area. The larger the area of a triangle, the
more probability it has to get chosen. Then, a point is uniformly sampled
within the boundary of the selected triangle. We repeat this process $N$ times
to sample $N$ points.

####  3.2.2. 2D Histogram

(a) 2D histogram (b) Extracted walls

Figure 2. Wall detection by 2D histogram

We adopt a 2d histogram based technique, originally proposed by Adan et al.
(Adan and Huber, 2011), to identify only the points representing the walls
from the entire point-cloud of size $N$. We first divide the floor into
$D\times D$ bins to get a square shaped grid structure. This grid is big
enough to fit the $(x,y)$ coordinates of all points within it. Then, we
project all points to the floor and count the number of points that fall into
each bin. This gives us a 2D histogram like Figure 2(a). A bin tends to have
more points if there is a wall on it. Here, we call these bins “wall bins”.
The shape of the walls is clearly visible is Figure 2(a).

We extract wall bins by a threshold mechanism. A bin having points less than
the threshold is not considered a wall bin. Using a fixed threshold here does
not yield a desired result in our case. Hence, we find the maximum number of
points $n_{max}$ in a bin among all bins and use $n_{max}/4$ as the threshold
value by empirically evaluating from a large number of scans of real rooms.
Finally, we get a $(D,D)$ shaped image (pixels or points) showing the walls
like in Figure 2(b). Later, we use this image to extract rooms by using deep
learning techniques.

###  3.3. Room Detection using Pointer Network

In our first deep learning approach, we resort to learning the geometry of
different rooms as a sequence of points. Thus, we use the geometric learning
framework, namely Pointer Network (in short, PtrNet) to identify locations and
layouts the rooms from extracted walls of our previous step. Next, we first
give an overview of PtrNet and then explain how we adopt PtrNet in identifying
rooms as a sequence of points.

####  3.3.1. PtrNet

A Pointer Network is a seq2seq (sequence-to-sequence) architecture with
attention mechanism, where the output is a sequence of input indices of input
vectors. That means, PtrNet can select only those vectors as output that are
already present in input sequence. PtrNet supports variable-length inputs.
Mathematically, let $P=\\{P_{1},\ldots,P_{n}\\}$ be an input sequence of
vectors, $C=\\{C_{1},\ldots,C_{m}\\}$ an output sequence
$C=\\{C_{1},\ldots,C_{m}\\}$ , where $C_{i}\in\mathbb{N}$ and $1\leq C_{i}\leq
n$ for all $C_{i}\in C$. Here, $\theta$ is RNN parameters. Then the
probability of output sequence $C$ is computed as follows:

$p(C|P;\theta)=\prod_{i=1}^{m}p(C_{i}|C_{1},\ldots,C_{i-1},P;\theta).$

This model will essentially try to estimate $\theta^{\ast}$ by maximizing
probabilities, as stated below,

$\theta^{\ast}={argmax}_{\theta}\sum_{P,C}\log{p(C|P;\theta)}.$

To find $p(C_{i}|C_{1},\ldots,C_{i-1},P;\theta)$, a typical seq2seq model uses
softmax over fixed sized output dictionary. As a result, it cannot be applied
to problems where output dictionary size is equal to input length. PtrNet uses
attention mechanism to solve this problem, which can be stated as follows:

$\displaystyle u^{i}_{j}$
$\displaystyle=v^{T}\tanh(W_{1}e_{j}+W_{2}d_{i})\quad j\in(1,\ldots,n)$
$\displaystyle p(C_{i}|C_{1},\ldots,C_{i-1},P)$
$\displaystyle=\text{softmax}(u^{i})$

Softmax over vector $u^{i}$ of length $n$ is applied to produce the output
sequence. Similar to the attention mechanism, $v,W_{1},W_{2}$ are learnable
parameters in this case. PtrNet does not use encoder states $e_{j}$ to provide
information to decoder. Rather, it uses $u^{i}_{j}$ to point back to input
sequence. So, in short, PtrNet can learn a model where input is a sequence of
vectors, output is discrete and output can be constructed with input vectors.

####  3.3.2. PtrNet in Room Identification

To solve our room detection problem using PtrNet, we formulate the problem
such that it fits into the structure of PtrNet framework. After the wall
extraction phase, we have two types of pixels - those who have walls on them
and those who do not have walls on them. We take the $(row,column)$ of wall
pixels and treat them as coordinates of points. Thus, we have a point set
$S^{\prime}$. Then, we shift and scale the coordinates of points in
$S^{\prime}$ to be within a $[-1,1]\times[-1,1]$ square. Then, we sample a
fixed number of points $P_{n}$ from $S^{\prime}$ to get a new set $S$. This
point set $S$ is the input of PtrNet. Our target is to predict the borders of
rooms. For this, PtrNet selects points from input points to create new sets of
points. Each set is a polygon with fixed $b$ number of points. Each polygon
marks the border of a single room. In other words, PtrNet will only say which
input points are border points.

Figure 3 shows a toy example that illustrates the above concept. For ease of
demonstration, we consider a small set of 15 points to represent the detected
walls of a single room. The room outline is drawn with dashed line. Also, let
us suppose, each room has 4 border points. Then, point set $\langle
7,11,2,10\rangle$ creates a polygon that marks the room border, which will be
the output of our PtrNet framework.

Figure 3. Sample points representing the walls of a single room.

The PtrNet framework using this toy example is shown in Figure 4. We first
input all 15 points in encoder network. For the purpose of demonstration, RNN
cell is unrolled for each time step. Then the decoder network outputs the
indexes of border points.

Figure 4. Unrolled encoder decoder of PtrNet. For sample scenario.

We extend the above concept to identify multiple rooms. Let us assume that
output sequence $C$ consists of $K$ rooms, and each rooms have $b$ border
points. Then the length of the output sequence would be $b\times K$. Here,
‘index’ of border points of $1^{st}$ room is $\langle
C_{1},C_{2},\ldots,C_{b}\rangle$. Similarly, ‘index’ of border points of
$k^{th}$ room, where $1\leq k\leq K$, is $\langle
C_{bk-b+1},C_{bk-b+2},\ldots,C_{bk}\rangle$.

####  3.3.3. Input Ordering

PtrNet treats a input set of points $S$ as a sequence, not as a set. After we
extract walls from point-cloud, we randomly sample a fixed $P_{n}$ number of
points from it. So, after sampling, points are in random order. According to
Vinyals et al. (Vinyals et al., 2015a), order of points in input sequence has
an effect on PtrNet’s performance. So, one of the main challenges is to order
points in $S$ before we feed them to PtrNet. Here, we propose three schemes to
order the elements in $S$.

PtrNet-Random: Since we randomly pick points from walls, the input sequence to
the PtrNet can be truly random, i.e. the input set $S$ is in random order. In
this approach, we feed these random set of points (without considering any
spatial order), to PtrNet, and evaluate the performance of this PtrNet-Random
architecture in detecting rooms.

PtrNet-TrueSort: In this case, we manually sort the points in the desired
order and feed into the PtrNet architecture, namely PtrNet-TrueSort. First,
points from each room in a sample is sorted in anti-clockwise order. So, each
room has a sorted point list. These lists are appended to form input sequence.
We refer to this ordering as ‘true-sort’. This does not represent real world
situation, as we cannot know beforehand which point belongs which rooms. It
can only be done if we generate our own dataset synthetically. However, the
main purpose of PtrNet-TrueSort is to simply show how order affects the
performance of PtrNet in our problem.

PtrNet-PseudoSort: Since no known approach can do the true sort of the input
point sets, we develop a heuristic to sort the points, which approximate the
true sorting of the points. Here, first, input set $S$ is randomly picked from
the given set of points (similar to the procedure described in PtrNet-Random).
Then we order the points in $S$ based on proximity of last selected point.
Algorithm 1 shows the process of our proposed ordering. First we take an list
$L$ and insert the first element of $S$ into it. We also remove the first
element from $S$. Then, we enter into a loop. To select which point to remove,
we take the last inserted element $q$ in $L$. Then, we find the closest point
$p\in S$ to $q$. Then we remove $p$ from $S$ and insert it into $L$. We keep
selecting new $p$ until $S$ is empty. Finally, $L$ gives us the ordering. We
refer the PtrNet based on this type of ordering as PtrNet-PseudoSort.

input : Shuffled input sequence $S$

output : Ordered input sequence $L$

Function _Pseudosort_  _$S$_

$L\leftarrow\\{S_{1}\\}$

$\triangleright$ Taking the first element of $S$

$S\leftarrow S-\\{S_{1}\\}$

while  _$S\neq\\{\\}$_ do

Find point $p\in S$ that is closest to the last element in $L$

$L\leftarrow L\cup\\{p\\}$

$S\leftarrow S-\\{p\\}$

end while

return $L$

end

Algorithm 1 Pseudo-Sort Algorithm

After conducting experiments, in evaluation section (Section 5), we show how
PtrNet performance varies depending on which ordering method we choose

###  3.4. Room Detection using Mask R-CNN

As our second deep learning strategy, we adapt a deep learning framework, Mask
R-CNN, commonly used for image object segmentation, to identify locations and
layouts of the rooms from extracted walls. For this, we train an image
segmentation neural network to segment rooms from the image of extracted
walls. We first discuss the basics of Mask R-CNN and the we discuss how we use
this approach to our purpose.

####  3.4.1. Image Segmentation Network: Mask R-CNN

Mask R-CNN (He et al., 2017) is an object segmentation Convolutional Neural
Network (CNN), that can identify each pixel of an object from an image. As
explained in Section 3.2, we can obtain the image of the top view of walls
from a point-cloud. After that, we identify the rooms from the extracted
walls. As an instance of segmentation network, Mask R-CNN suits perfectly for
the task of segmenting individual rooms from that image.

A typical object detection model needs someone to annotate the objects in an
image using bounding boxes. However, for training Mask R-CNN, a sample is an
image and some binary masks. An image can have several masks, each mask marks
the pixel-wise location of an object. Mask-RCNN has two steps. First, it
produces region proposals on where an object might be. Second, a classifier
identifies the class of that object and improves on bounding box and produces
a pixel level mask of the object.

In the first step, to get a set of Regions of Interest (RoI), Mask-RCNN uses
RoI Align. RoI Align network produces multiple bounding boxes that may contain
an object. These boxes are merged and refined to one bounding box using a
regression model. In the second step, it does semantic segmentation to every
bounding box. The first step guarantees that each bounding box will have at
most one class. So, this is like a pixel level binary classifier. In the
bounding box, a pixel is 1 if it is a part of that object, 0 otherwise.

####  3.4.2. Mask R-CNN in Room Segmentation

(a) Extracted wall (b) Room mask 1

(c) Room mask 2 (d) Room mask 3

Figure 5. A sample scenario for Mask R-CNN: 3 rooms and masks for each of them

Mask R-CNN takes an image as input and a set of binary masks as label/output.
Each mask is for an individual object and points to the area where the object
is located on that image. For room segmentation task using Mask R-CNN, an
input is the image showing the walls (Figure 5(a)), and the corresponding
label is a set of masks for each of the rooms in that scene (Figure 5(b-d)).
In the training phase, we provide a dataset consisting both input images and
corresponding masks. Mask R-CNN learns from that dataset. After learning, Mask
R-CNN takes an image as input and spits out masks as output. Each predicted
mask shows the location of a room.

(a) Predicted masks

(b) Mask border

Figure 6. Extracting borders from the masks of predicted rooms

Finally for each mask, we have to extract the border of the corresponding
room. For this, we obtain the borders of the masks. Given a binary mask, we
apply _contour detection algorithm_ to find the border pixels of the masked
region. A contour is a closed curve connecting all the points along the
boundary of an object having same color. After detecting contours, we get a
set of pixels for each of the binary masks, that marks the border of the
corresponding room as shown in Figure 6.

##  4\. Experimental Setup

For detecting rooms from extracted walls like Figure 2(b), we take a learning
based approach. Any deep learning approach requires training data to learn
from. Unfortunately, there is no dataset available. We develop a novel
algorithm to generate a large number of indoor scenes with only walls. We
train PtrNet and Mask R-CNN on it and test on real indoor scenes.

###  4.1. Dataset Generation

To generate synthetic indoor layout, we first analyze a set of real indoor
layouts like Figure 7. Walls in these layouts include shapes like,
rectangular, rectilinear, curved walls and non-right angles etc. In an attempt
to make our dataset realistic, we generate these shapes.

(a)

(b)

Figure 7. Examples of real indoor layout

Two networks expect input data in two different formations - PtrNet as
sequences, Mask R-CNN as images. Generating a sample for both networks, share
some common tasks. First we explain the common portion, then we describe how
we process them differently.

Figure 8. Workflow of data generation

####  4.1.1. Rectangular Polygons

Our approach is to first generate rooms in rectangular shapes and modify them
later to create other shapes. So, first we will show how we generate a single
rectangle shaped room. Our process requires a starting point $P$ and an unit
alignment vector $\bm{v}$. The alignment vector determines the orientation of
the rectangle. We uniform randomly select length $l$ and width $w$ of the
rectangle within interval $(l_{max},l_{min})$. Then, we calculate the four
corners of the rectangle: $P_{1}=P$, $P_{2}=P_{1}+\bm{v}l$,
$P_{3}=P_{2}+\bm{v_{\perp}}w$, $P_{4}=P_{3}-\bm{v}l$, where $\bm{v_{\perp}}$
is 90∘ anticlockwise rotation of $\bm{v}$.

Figure 9. Generation of a rectangular room. Left: a point and an alignment
vector. Right: corner points.

To generate a second rectangle, we use one of the corner points of the first
rectangle as new starting point. So, the second rectangle is just beside the
first rectangle. We again randomly select length $l$ and width $w$ of the
rectangle. Similarly, to generate more rectangles, we randomly choose one of
the corner points of existing rectangles. We also make sure no new rectangle
overlaps any existing one. When we collect point-cloud of adjacent rooms, we
get two vertical planes on either side of the shared wall. To incorporate this
effect, we shrink each rectangle by a small amount (Figure 10(c)).

(a) Single rectangle (b) Multiple rectangles (c) Slightly shrunken Rectangles

Figure 10. A sample data point generation process

####  4.1.2. Other Shapes

We create 3 types shapes from rectangles as shown in Figure 11 -

  1. (1)

Shapes with right angle (rectangular and rectilinear)

  2. (2)

Shapes with non-right angle

  3. (3)

Shapes with curves (half circular and quarter circular)

Figure 11. Other shapes created from rectangle. Left to Right: rectangular,
rectilinear, two non-right angle shapes, half circular and quarter circular

Rectilinear: We randomly choose a corner, thus we get two adjacent edges
incident from that corner. We replace the corner with three other points -
midpoint of first edge, center of rectangle and midpoint of second edge.

Shapes with Non-right Angles: We again randomly choose a corner and thus we
get two adjacent edges. We replace the corner with two other points from those
two edges. We can choose a different corner and perform same procedure there.

Shapes with Curves: For a half circular shape, we randomly choose an edge and
replace it with an half circle with a radius equal to half the length of that
edge. For a quarter circular shape, we randomly choose a corner and replace it
with an quarter circle with a radius equal to half pf the length of the
shortest edge of the two incident edges there.

Now we have a set of shapes. We plot them in black on a $128\times 128$ sized
white image. After that we process differently for two different approaches.

####  4.1.3. Data Generation for PtrNet

Point-clouds collected from Google Tango Devices are usually noisy. And
extracted walls like Figure 2(b) are not smooth due to clutters. To
incorporate this effect, we shift black pixels to neighboring pixels. Then we
find the list of $(row,column)$ of black pixels. We treat each black pixels as
a point and $(row,column)$ of that black pixel as $(x,y)$ coordinates of that
point. Then we compress the points within a $[-1,1]\times[-1,1]$ square. Then,
we sample at most $P_{n}$ points from it. This introduces the effect of gaps
and incompleteness in our scans. We try four values of $P_{n}$: 100, 200, 300
and 400. We also assign $10$ border points for each shape. Finally, we have a
sequence of points and a sequence of index of border points. To evaluate the
effect of ordering on PtrNet’s performance, we further apply sorting schemes -
PtrNet-TrueSort, PtrNet-Random and PtrNet-PseudoSort. Figure 12(a) shows a
generated sample for PtrNet.

####  4.1.4. Data Generation for Mask R-CNN

We displace black pixels for this too. We also randomly remove black pixels
and turn them into white to introduce the effect of gaps and incompleteness.
We also generate separate binary masks for each shape. Finally, we have an
image and a set of masks for each shape. Figure 12(b) shows a generated sample
for Mask R-CNN.

####  4.1.5. Training Set and Validation Set

We generate $100000$ samples as training data and $10000$ samples as
validation data. There are at most $5$ rooms in each sample. Based on our
measurements in real world rooms, we vary the length of each edge of each room
within $2$ to $8$ meters.

(a) For PtrNet (b) For Mask R-CNN

Figure 12. Generated samples for both approaches. Left: Input points are
marked with blue crosses, borders are marked with red dots and lines. Right:
Rooms and corresponding masks.

###  4.2. PtrNet Architecture and Hyperparameters

Each of our PtrNet models uses a single LSTM layer with 512 hidden units,
attention size 512, Adam optimizer with 0.001 learning rate, batch size of
128, beam width of 4 and maximum gradient norm 5.0. Models are trained for
30K-60K steps depending on convergence.

###  4.3. Mask R-CNN Architecture and Hyperparameters

We train Mask R-CNN on the generated dataset. We use Resnet101 as backbone,
batch size 8, SGD momentum optimizer with momentum 0.9, learning rate 0.001,
gradient clip norm 5.0. The Resnet101 model is initialized with COCO pre-
trained weights. Then, we fine-tune the model on our dataset. The model is
trained for 60 epochs, with 100 steps per epoch. For the first 30 epochs, only
randomly initialized head layers are trained and all backbone layers are kept
frozen. Then, in the next 30 epochs, all layers are fine-tuned.

###  4.4. Performance Metric

We measure the performance of our models based on how similar the shapes of
predicted rooms and ground-truth rooms are. For similarity measurement, we use
Intersection over Union (IoU) score. It is the ratio of the common area and
the combined area of predicted room and ground-truth room. IoU values can
range from 0 to 1. Higher IoU means higher similarity between prediction and
ground-truth. We compare the performance of our different models by mean IoU
score. Mean IoU score of a model is the sum of IoU scores of all predicted
rooms divided by the total number of predicted rooms.

###  4.5. Testing on Real Environment

We test our model on $10$ indoor scenes. The 3D meshes are collected from
those scenes using Google Tango. We use Asus Zenfone AR powered by Google’s
Project Tango to collect 3D meshes. Then, we sample $3\times 10^{6}$ points
from each 3D mesh to get 3D point-clouds. The walls are extracted using
histogram approach. From the extracted walls, rooms are identified using our
trained PtrNet models and Mask R-CNN model.

##  5\. Evaluation

In this section we measure the capability of our approaches. We first evaluate
them on generated dataset. Then we evaluate them on real world point-clouds
data. We also show some example results of our models.

###  5.1. Overall Performance on Generated Dataset

First we measure performance of our models in the validation set of our
generated dataset. In Table 1 we show how the performance of PtrNet changes
with different ordering schemes and input length. We vary the length of input
sequence $P_{n}$ to 100, 200, 300 and 400. Here, the mean IoU of PtrNet-
TrueSort varies from 0.946 to 0.970. The mean IoU of PtrNet-Random varies from
0.553 to 0.840. And, the mean IoU of PtrNet-PseudoSort varies from 0.711 to
0.892. PtrNet-TrueSort outperforms every other sorting schemes. It shows that
ordering indeed has a significant effect on PtrNet’s performance. In addition,
the mean IoU of PtrNet-PseudoSort increases along with input length upto 300,
then it decreases at input length 400.

Sorting Schemes | Input Length
---|---
100 | 200 | 300 | 400
PtrNet-TrueSort | 0.970 | 0.953 | 0.945 | 0.946
PtrNet-Random | 0.553 | 0.558 | 0.602 | 0.840
PtrNet-PseudoSort | 0.711 | 0.803 | 0.892 | 0.843
Table 1. PtrNet: Mean IoU vs. input length

We also see that a simple ordering like PseudoSort has 44%-48% performance
gain from PtrNet-Random. It shows, the closer the ordering to TrueSort, the
better the performance. We select best model, PtrNet-PseudoSort with 300 input
points for real-world evaluation. We also measure how Mask R-CNN performs in
generated dataset. This is reported in Table 2. Both approaches perform almost
similarly on generated dataset.

Model | Mean IoU
---|---
PtrNet-PseudoSort (300) | 0.8921
Mask R-CNN | 0.8919
Table 2. Performance in generated data

###  5.2. Shape Based Performance on Generated Dataset

We measure how our proposed models are able to detect different shapes. For
this, we keep track of IoU scores of different shapes of rooms. This is
reported in Table 3. Mask R-CNN and PtrNet-PseudoSort perform almost similarly
in extracting all kinds of shapes in generated dataset.

Models | Shapes
---|---
Rectangular | Rectilinear
PtrNet-TrueSort | 0.927 | 0.949
PtrNet-Random | 0.650 | 0.467
PtrNet-PseudoSort | 0.862 | 0.856
Mask R-CNN | 0.910 | 0.823

Models | Shapes
---|---
Curved | Non-right Angle
PtrNet-TrueSort | 0.977 | 0.937
PtrNet-Random | 0.640 | 0.587
PtrNet-PseudoSort | 0.919 | 0.884
Mask R-CNN | 0.917 | 0.903

Table 3. Mean IoU vs. room shape

###  5.3. Performance on Real World Dataset

Finally, we take two of our best models, PtrNet-PseudoSort (300) and Mask
R-CNN to evaluate them on real world data. For this, we collect Point-cloud
from 10 indoor scenes. The indoor scenes include classrooms, households,
office spaces. To show our models can recognize rooms of different shapes, we
change the shapes of some rooms by hanging sheets vertically from ceiling to
floor. Table 4 shows, mean IoU scores of our two approaches in real dataset.

Model | Mean IoU
---|---
PtrNet-PseudoSort (300) | 0.560
Mask R-CNN | 0.850
Table 4. Performance in real world data

Table 4 shows, Mask R-CNN has an 52% performance gain from PtrNet in real
world dataset. We show some results of our proposed systems in Figure 13. In
the first example, walls are extracted almost perfectly and clutters are
completely excluded. Both PtrNet and Mask R-CNN detect rooms accurately. In
the second example, again clutters are mostly excluded by the wall detection
module. But there are visible gaps in extracted walls due to windows and
doors. Especially, there is a large gap in the lower left room due to the
existence of a large window. Both Mask R-CNN and PtrNet detect three rooms
accurately. But PtrNet over estimates the area of the top-left room. And Mask
R-CNN suffers slightly due to the large gap in the bottom-left room. In the
third example, there is a large wardrobe in the right room. The wall detection
module fails to exclude it completely. Also, there are some other clutters
still present after wall extraction. Although, Mask R-CNN is able to detect
rooms, but PtrNet performs poorly on this example. Again, in the fourth
example, there are still some background clutters. So, again PtrNet fails
completely even though Mask R-CNN detects both the rooms. So, it is evident
from these examples that Mask R-CNN can detect rooms reasonably well compared
to PtrNet.

(a) Point-cloud

(b) Extracted walls (c) PtrNet

(d) Mask R-CNN (e) Ground Truth

(f) Point-cloud

(g) Extracted walls (h) PtrNet

(i) Mask R-CNN (j) Ground Truth

(k) Point-cloud

(l) Extracted walls (m) PtrNet

(n) Mask R-CNN (o) Ground Truth

(p) Point-cloud

(q) Extracted walls (r) PtrNet

(s) Mask R-CNN (t) Ground Truth

Figure 13. Real world indoor layout results

##  6\. Conclusion

In this paper, we introduce an indoor mapping system using smart hand-held
devices. First, we capture the indoor scene in the form of a 3D mesh or a
point-cloud generated by a simple scan of modern mobile device. Then, we use
2D histogram based approach to detect positions of walls from the points-
clouds. Finally, we use two paradigms of deep learning frameworks: one from
geometric learning and the other from image segmentation, to detect rooms from
walls. Since deep learning models require huge amounts of data to train and
currently no publicly available dataset is available for this purpose, we also
develop a method to generate millions of samples for training these networks.
Though our models are trained on synthetic data, our experiments show
satisfactory results in real-world environments. This work is a promising
start towards learning based spatial object detection. In future work, we will
try to show applicability of this approach in detecting other spatial objects
e.g. doors, windows, staircase.

## References

  * (1)
  * tan ([n. d.]) [n. d.].  Tango floor plan java example.  https://github.com/googlearchive/tango-examples-java/tree/master/java_floor_plan_reconstruction_example. ([n. d.]).  Accessed: 03-10-2018.
  * Adan and Huber (2011) Antonio Adan and Daniel Huber. 2011.  3D reconstruction of interior wall surfaces under occlusion and clutter. In 2011 International Conference on 3D Imaging, Modeling, Processing, Visualization and Transmission. IEEE, 275–281.
  * Angladon et al. (2018) Vincent Angladon, Simone Gasparini, and Vincent Charvillat. 2018\.  Room Floor Plan Generation on a Project Tango Device. In International Conference on Multimedia Modeling. Springer, 226–238.
  * Armeni et al. (2016) Iro Armeni, Ozan Sener, Amir R Zamir, Helen Jiang, Ioannis Brilakis, Martin Fischer, and Silvio Savarese. 2016.  3d semantic parsing of large-scale indoor spaces. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 1534–1543.
  * Babacan et al. (2017) K Babacan, L Chen, and G Sohn. 2017.  SEMANTIC SEGMENTATION OF INDOOR POINT CLOUDS USING CONVOLUTIONAL NEURAL NETWORK.  ISPRS Annals of Photogrammetry, Remote Sensing & Spatial Information Sciences 4 (2017).
  * Chon and Cha (2011) John Chon and Hojung Cha. 2011.  Lifemap: A smartphone-based context provider for location-based services.  IEEE Pervasive Computing 10, 2 (2011), 58–67.
  * Han et al. (2014) Dongsoo Han, Sukhoon Jung, Minkyu Lee, and Giwan Yoon. 2014\.  Building a practical Wi-Fi-based indoor navigation system.  IEEE Pervasive Computing 13, 2 (2014), 72–79.
  * He et al. (2017) Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. 2017.  Mask r-cnn. In Computer Vision (ICCV), 2017 IEEE International Conference on. IEEE, 2980–2988.
  * Jung et al. (2017) Jaehoon Jung, Cyrill Stachniss, and Changjae Kim. 2017\.  Automatic Room Segmentation of 3D Laser Data Using Morphological Processing.  ISPRS International Journal of Geo-Information 6, 7 (2017), 206.
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. 2015\.  Deep learning.  nature 521, 7553 (2015), 436.
  * Liu et al. (2018) Chen Liu, Jiaye Wu, and Yasutaka Furukawa. 2018.  Floornet: A unified framework for floorplan reconstruction from 3d scans. In Proceedings of the European Conference on Computer Vision (ECCV). 201–217.
  * Liu et al. (2012) Jingbin Liu, Ruizhi Chen, Yuwei Chen, Ling Pei, and Liang Chen. 2012.  iParking: An intelligent indoor location-based smartphone parking service.  Sensors 12, 11 (2012), 14612–14629.
  * Murali et al. (2017) Srivathsan Murali, Pablo Speciale, Martin R Oswald, and Marc Pollefeys. 2017.  Indoor Scan2BIM: Building Information Models of House Interiors.  (2017).
  * Pintore et al. (2014) Giovanni Pintore, Marco Agus, and Enrico Gobbetti. 2014\.  Interactive mapping of indoor building structures through mobile devices. In 3D Vision (3DV), 2014 2nd International Conference on, Vol. 2. IEEE, 103–110.
  * Pintore et al. (2016) Giovanni Pintore, Fabio Ganovelli, Enrico Gobbetti, and Roberto Scopigno. 2016.  Mobile reconstruction and exploration of indoor structures exploiting omnidirectional images. In SIGGRAPH ASIA 2016 Mobile Graphics and Interactive Applications. ACM, 1\.
  * Pintore et al. (2017) Giovanni Pintore, Fabio Ganovelli, Enrico Gobbetti, and Roberto Scopigno. 2017.  Mobile metric capture and reconstruction in indoor environments.
  * Pintore and Gobbetti (2014) Giovanni Pintore and Enrico Gobbetti. 2014.  Effective mobile mapping of multi-room indoor structures.  The visual computer 30, 6-8 (2014), 707–716.
  * Pradhan et al. (2018) Swadhin Pradhan, Ghufran Baig, Wenguang Mao, Lili Qiu, Guohai Chen, and Bo Yang. 2018\.  Smartphone-based Acoustic Indoor Space Mapping.  Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies 2, 2 (2018), 75.
  * Ran et al. (2004) Lisa Ran, Sumi Helal, and Steve Moore. 2004.  Drishti: an integrated indoor/outdoor blind navigation system and service. In Second IEEE Annual Conference on Pervasive Computing and Communications, 2004. Proceedings of the. IEEE, 23–30.
  * Tardós et al. (2002) Juan D Tardós, José Neira, Paul M Newman, and John J Leonard. 2002.  Robust mapping and localization in indoor environments using sonar data.  The International Journal of Robotics Research 21, 4 (2002), 311–330.
  * Vinyals et al. (2015a) Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. 2015a.  Order matters: Sequence to sequence for sets.  arXiv preprint arXiv:1511.06391 (2015).
  * Vinyals et al. (2015b) Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015b.  Pointer networks. In Advances in Neural Information Processing Systems. 2692–2700.
  * Vosselman (2014) George Vosselman. 2014\.  Design of an indoor mapping system using three 2D laser scanners and 6 DOF SLAM.  ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences 2, 3 (2014), 173.