# TRIX: Low-Skew Pulse Propagation for Fault-Tolerant Hardware

Ben Wiederhake Max Planck Institute for Informatics, Saarland Informatics
Campus and Saarbrücken Graduate School of Computer Science, Germany;
<EMAIL_ADDRESS>Christoph Lenzen Max Planck Institute for Informatics,
Saarland Informatics Campus<EMAIL_ADDRESS>
###### Abstract

The vast majority of hardware architectures use a carefully timed reference
signal to clock their computational logic. However, standard distribution
solutions are not fault-tolerant. In this work, we present a simple grid
structure as a more reliable clock propagation method and study it by means of
simulation experiments. Fault-tolerance is achieved by forwarding clock pulses
on arrival of the second of three incoming signals from the previous layer.

A key question is how well neighboring grid nodes are synchronized, even
without faults. Analyzing the clock skew under typical-case conditions is
highly challenging. Because the forwarding mechanism involves taking the
median, standard probabilistic tools fail, even when modeling link delays just
by unbiased coin flips.

Our statistical approach provides substantial evidence that this system
performs surprisingly well. Specifically, in an “infinitely wide” grid of
height $H$, the delay at a pre-selected node exhibits a standard deviation of
$O(H^{1/4})$ ($\approx 2.7$ link delay uncertainties for $H=2000$) and skew
between adjacent nodes of $o(\log\log H)$ ($\approx 0.77$ link delay
uncertainties for $H=2000$). We conclude that the proposed system is a very
promising clock distribution method. This leads to the open problem of a
stochastic explanation of the tight concentration of delays and skews. More
generally, we believe that understanding our very simple abstraction of the
system is of mathematical interest in its own right.

###### Keywords:

pulse propagation clock tree replacement self-stabilizing hardware fault
tolerance

##  1 Introduction

When designing high reliability systems, any critical subsystem susceptible to
failure must exhibit sufficient redundancy. Traditionally, clocking of
synchronous systems is performed by clock trees or other structures that
cannot sustain faulty components [23]. This imposes limits on scalability on
the size of clock domains; for instance, in multi-processor systems typically
no or only very loose synchronization is maintained between different
processors [6, 18]. Arguably, this suggests that fault-tolerant clocking
methods that are competitive – or even better – in terms of synchronization
quality and other parameters (ease of layouting, amount of circuitry, energy
consumption, etc.) would be instrumental in the design of larger synchronous
systems.

To the best of our knowledge, at least until 20, or perhaps even 10 years ago,
there is virtually no work on fault-tolerance of clocking schemes beyond
production from the hardware community; due to the size and degree of
miniaturization of systems at the time, clock trees and their derivatives were
simply sufficiently reliable in practice. That this has changed is best
illustrated by an upsurge of interest in single event upsets of the clocking
subsystem in the last decade [1, 3, 4, 5, 14, 16, 20, 22]. However, with ever
larger systems and smaller components in place, achieving acceptable trade-
offs between reliability, synchronization quality, and energy consumption
requires to go beyond these techniques.

On the other hand, there is a significant body of work on fault-tolerant
synchronization from the area of distributed systems. Classics are the
Srikanth-Toueg [19] and Lynch-Welch [21] algorithms, which maintain
synchronization even in face of a large minority (strictly less than one
third) of _Byzantine_ faulty nodes.111Distributed systems are typically
modeled by network graphs, where the nodes are the computational devices and
edges represent communication links. A Byzantine faulty node may deviate from
the protocol in an arbitrary fashion, i.e., it models worst-case faults and/or
malicious attacks on the system. Going beyond this already very strong fault
model, a line of works [7, 10, 11, 12, 15] additionally consider _self-
stabilization,_ the ability of a system to recover from an unbounded number of
transient faults. The goal is for the system to stabilize, i.e., recover
nominal operation, after transient faults have ceased. Note that the
combination makes for a very challenging setting and results in extremely
robust systems: even if some nodes remain faulty, the system will recover from
transient faults, which is equivalent to recover synchronization when starting
from an arbitrary state despite interference from Byzantine faulty nodes.

While these fault-tolerance properties are highly desirable, unsurprisingly
they also come at a high price. All of the aforementioned works assume a fully
connected system, i.e., direct connections between each pair of nodes. Due to
the strong requirements, it is not hard to see that this is essentially
necessary [9]: in order to ensure that each non-faulty node can synchronize to
the majority of correct nodes, its degree must exceed the number of faults, or
it might become effectively disconnected. In fact, it actually must have more
correct neighbors than faulty ones, or a faulty majority of neighbors might
falsely appear to provide the correct time. Note that emulating full
connectivity using a crossbar or some other sparser network topology defeats
the purpose, as the system then will be brought down by a much smaller number
of faults in the communication infrastructure connecting the nodes.
Accordingly, asking for such extreme robustness must result in solutions that
do not scale well.

A suitable relaxation of requirements is proposed in [8]. Instead of assuming
that Byzantine faults are also _distributed_ across the system in a worst-case
fashion, the authors of this work require that faults are “spread out.” More
specifically, they propose a grid-like network they call HEX, through which a
clock signal can be reliably distributed, so long as for each node at most one
of its four in-neighbors is faulty. Note that for the purposes of this paper,
we assume that the problem of fault-tolerant clock signal _generation_ has
already been sufficiently addressed (e.g. using [11]), but the signal still
needs to be _distributed_. Provided that nodes fail independently, this means
that the probability of failure of individual nodes that can likely be
sustained becomes roughly $1/\sqrt{n}$, where $n$ is the total number of
nodes; this is to be contrasted with a system without fault-tolerance, in
which components must fail with probability at most roughly $1/n$. The authors
also show how to make HEX self-stabilizing. Unfortunately, however, the
approach has poor synchronization performance even in face of faults obeying
the constraint of at most one fault in each in-neighborhood. While it is
guaranteed that the clock signal propagates through the grid, nodes that fail
to propagate the clock signal cause a “detour” resulting in a clock skew
between neighbors of at least one maximum end-to-end communication delay
$d$.222$d$ includes the wire delay as well as the time required for local
computations. As the grid is highly uniform and links connect close-by nodes,
the reader should expect this value to be roughly the same for all links. This
is much larger than the _uncertainty_ $u$ in the end-to-end delay: As clocking
systems can be (and are) engineered for this purpose, the end-to-end delay
will vary between $d-u$ and $d$ for some $u\ll d$. To put this into
perspective, in a typical system $u$ will be a fraction of a clock cycle,
while $d$ may easily be half of a clock cycle or more.

This is inherent to the structure of the HEX grid, see Figure 1. It seeks to
propagate the clock signal from layer to layer, where each node has two in-
neighbors on the preceding and two in-neighbors on their own layer. Because
the possibility of a fault requires nodes to wait for at least two neighbors
indicating a clock pulse before doing so themselves, a faulty node refusing to
send any signal implies that its two out-neighbors on the next layer need to
wait for at least one signal from their own layer. This adds at least one hop
to the path along which the signal is propagated, causing an additional delay
of at least roughly $d$.

#### Our Contribution

columnlayer3d3d3d3d4d4d↯4d4d5d6d6d5d Figure 1: A crashing node in a HEX grid
causes a large skew between neighbors in the same layer, even with all links
having exactly the same delay. Thick links cause nodes to pulse, dotted links
mean that the transmitted pulse was too late to be considered, and faint
dotted links do not transmit a pulse. columnlayer Figure 2: The basic topology
of TRIX. Only wires incident to the central node are shown; the same pattern
is applied at other nodes.

columnlayer$0{}d$$1{}d$$2{}d$$3{}d$$0{}d$$1{}d$$2{}d$$3{}d$$0{}d$$1{}d$$2{}d$$3{}d$$0{}d$$1{}d$$2{}d$$3{}d$↯
Figure 3: A crashing node in a TRIX grid causes no significant skew, compared
to Figure 1. In fact, in absence of uncertainty, isolated crashes can be
ignored entirely.
columnlayer$0{}d$$1{}d$$2{}d$$3{}d$$0{}d$$1{}d$$2{}d$$3{}d$$0{}\check{d}$$1{}\check{d}$$2{}\check{d}$$3{}\check{d}$$0{}\check{d}$$1{}\check{d}$$2{}\check{d}$$3{}\check{d}$
Figure 4: Worst-case assignment of wire delays causing large skew for TRIX.
Squiggly lines indicate slow wires, straight ones fast wires. The symbol
$\check{d}$ stands for $d-u$.

We propose a novel clock distribution topology that overcomes the above
shortcoming of HEX. As in our topology nodes have in- and out-degrees of $3$
and it is inspired by HEX, we refer to it as TRIX; see Figure 2 for an
illustration of the grid structure. Similar to HEX, the clock signal is
propagated through layers, but for each node, all of its three in-neighbors
are on the preceding layer. This avoids the pitfall of faulty nodes
significantly slowing down the propagation of the signal. If at most one in-
neighbor is faulty, each node still has two correct in-neighbors on the
preceding layer, as demonstrated in Figure 3. Hence, we can now focus on
fault-free executions, because single isolated faults only introduce an
additional uncertainty of at most $u\ll d$. Predictions in this model are
therefore still meaningful for systems with rare and non-malicious faults.

The TRIX topology is acyclic, which conveniently means that self-stabilization
is trivial to achieve, as any incorrect state is “flushed out” from the
system.

Despite its apparent attractiveness and even greater simplicity, we note that
this choice of topology should not be obvious. The fact that nodes do not
check in with their neighbors on the same layer implies that the worst-case
clock skew between neighbors grows as $uH$, where $H$ is the number of layers
and (for the sake of simplicity) we assume that the skew on the first layer
(which can be seen as the “clock input”) is $0$, see Figure 4. However,
reaching the skew of $d$ between neighbors on the same layer, which is
necessary to give purpose to any link between them, takes many layers, at
least $d/u\gg 1$ many. This is in contrast to HEX, where the worst-case skew
is bounded, but more easily attained. When not assuming that delays are chosen
in a worst-case manner, our statistical experiments show it to likely take
much longer before this threshold is reached. Accordingly, in TRIX there is no
need for links within the same layer for any practical number of layers,
resulting in the advantage of smaller in- and out-degrees compared to HEX.

The main focus of this work lies on statistical experiments with the goal of
estimating the performance of a TRIX grid as clock distribution method. Note
that this is largely333Skews over longer distances are relevant for long-range
communication, but have longer communication delays and respective
uncertainties. This entails larger buffers even in absence of clock skew. We
briefly show that the TRIX grid appears to behave well also in this regard.
dominated by the skew between adjacent nodes in the grid, as these will drive
circuitry that needs to communicate. While the worst-case behavior is easy to
understand, it originates from a very unlikely configuration, where one side
of the grid is entirely slow and the other is fast, see Figure 4. In contrast,
correlated but gradual changes will also result in spreading out clock skews –
and any change that affects an entire region in the same way will not affect
local timing differences at all. This motivates to study the extreme case of
independent noise on each link in the TRIX grid. Choosing a simple
abstraction, we study the random process in which each link is assigned either
delay $0$ or delay $1$ by an independent, unbiased coin flip. Moreover, we
assume “perfect” input, i.e., each node on the initial layer signals a clock
pulse at time $0$, and that the grid is infinitely wide.444Experiments with
grids of bounded width suggest that reducing width only helps, while our goal
here is to study the asymptotic behavior for large systems. By induction over
the layers, each node is then assigned the second largest value out of the
three integers obtained by adding the respective link delay to the pulse time
of each of its in-neighbors. We argue that this simplistic abstraction
captures the essence of (independent) noise on the channels.

Due to the lack of applicable concentration bounds for such processes, we
study this random process by extensive numerical experiments. Our results
provide evidence that TRIX behaves surprisingly well in several regards,
exhibiting better concentration than one might expect. First and foremost, the
skew between neighbors appears to grow extremely slowly with the number of
layers $H$. Even for $2000$ layers, we never observed larger differences than
$7$ between neighbors on the same layer. Plotting the standard deviation of
the respective distribution as a function of the layer, the experiments show a
growth that is slower than _doubly logarithmic_ , i.e. $\log\log H$. Second,
for a fixed layer, the respective skew distribution exhibits an exponential
tail falling as roughly $e^{-\lambda|x|}$ for $\lambda\approx 2.9$. Third, the
distribution of pulsing times as a function of the layer (i.e., when a node
pulses, not the difference to its neighbors) is also concentrated around its
mean (which can easily be shown to be $H/2$), where the standard deviation
grows roughly as $H^{1/4}$.

To support that these results are not simply artifacts of the simulation,
i.e., that we sampled sufficiently often, we make use of the Dvoretzky-Kiefer-
Wolfowitz (DKW) inequality [13] to show that the underlying ground truth is
very close to the observed distributions. In addition, to obtain tighter error
bounds for our asymptotic analysis of standard deviations as function of $H$,
we leverage the Chernoff bound (as stated in [17]) on individual values. We
reach a high confidence that the qualitative assertion that the TRIX
distribution exhibits surprisingly good concentration is well-founded. We
conclude that the simple mechanism underlying the proposed clock distribution
mechanism results in a fundamentally different behavior than existing clock
distribution methods or naive averaging schemes.

##  2 Preliminaries

#### Model

We model TRIX in an abstract way that is amenable to very efficient simulation
in software. In this section, we introduce this model and discuss the
assumptions and the resulting restrictions in detail.

The network topology is a grid of height $H$ and width $W$. For finite $W$,
the left- and rightmost column would be connected, resulting in a cylinder. To
simplify, we choose $W=\infty$, because we aim to focus on the behavior in
large systems. Note that a finite width will work in our favor, as it adds
additional constraints on how skews can evolve over layers; in the extreme
case of $W=3$, in absence of faults skews could never become larger than $1$.
We refer to the grid nodes by integer coordinates $(x,y)$, where
$x\in\mathbb{Z}$ and $y\in\mathbb{N}_{0}$. Layer $0\leq\ell\leq H$ consists of
the nodes $(x,\ell)$, $x\in\mathbb{Z}$.

Layer $0$ is special in that its nodes represent the clock source; they always
_pulse_ at time $0$. Again, there are implicit simplifications here. First,
synchronizing the layer $0$ nodes requires a suitable solution – ideally also
fault-tolerant – and cannot be done perfectly. However, our main goal here is
to understand the properties of the clock distribution grid, so the initial
skew is relevant only insofar as it affects the distribution. Some indicative
simulations demonstrate that the grid can counteract “bad” inputs to some
extent, but some configurations do not allow for this in a few layers, e.g.
having all nodes with negative $x$ coordinates pulse much earlier than those
with positive ones. Put simply, this would be a case of “garbage-in garbage-
out,” which is not the focus of this study. A more subtle point is the
unrealistic assumption that all layers of the grid have the same width. If the
layer $0$ nodes are to be well-synchronized, they ought to be physically
close; arranging them in a wide line is a poor choice. Accordingly, arranging
the grid in concentric rings (or a similar structure) would be more natural.
This would, however, entail that the number of grid nodes per layer should
increase at a constant rate, in order to maintain a constant density of nodes
(alongside constant link length, etc.). However, adding additional nodes
permits to distribute skews _better,_ therefore our simplification acts
against us.

All other nodes $(x,\ell)$ for $\ell>0$ are TRIX nodes. Each TRIX node
propagates the clock signal to the three nodes “above” it, i.e., the vertices
$(x-1,y+1)$, $(x,y+1)$, and $(x+1,y+1)$. In the case of the clock generators,
the signal is just the generated clock pulse; in case of the TRIX nodes, this
signal is the forwarded clock pulse. Each node (locally) triggers the pulse,
i.e., forwards the signal, when receiving the second signal from its
predecessors; this way, a single faulty in-neighbor cannot cause the node’s
pulse to happen earlier than the first correct in-neighbor’s signal arriving
or later than the last such signal.

Pulse propagation over a comparatively long distance involves delays, and our
model focuses on the uncertainty on the wires. Specifically, we model the wire
delays using i.i.d. random variables that are fair coin flips, i.e., attain
the values $0$ or $1$ with probability $1/2$ each.555This model choice is
restrictive in that it deliberately neglects correlations. A partial
justification here is the expectation that (positive) correlations are
unlikely to introduce local “spikes” in pulse times, i.e., large skews.
However, we acknowledge that this will require further study, which must be
based on realistic models of the resulting physical implementations. This
reflects that any (known expected) absolute delay does not matter, as the
number of wires is the same for any path from layer $0$ (the clock generation
layer) to layer $\ell>0$; also, this normalizes the uncertainty to 1.

Formalizing the above, for each wire from the nodes $(x+c,y)$ with
$c\in\\{-1,0,+1\\}$ to node $(x,y+1)$, we define $w_{c}$ to be the wire delay.
We further define the time
$t_{c}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=d(x+c,y)+w_{c}$
at which node $(x,y+1)$ receives the clock pulse. Then node $(x,y+1)$ fires a
clock pulse at the median time
$t\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\operatorname*{median}\\{t_{-1},t_{0},t_{+1}\\}$.
As we assume that all clock generators (i.e., nodes with $y=0$) fire, by
induction on $y$ all $d(x,y)$ are well-defined and finite.

This model may seem idealistic, especially our choice of the wire delay
distribution. However, in Appendix 0.A we argue that this is not an issue.

We concentrate on two important metrics to analyze this system: absolute delay
and relative skew. The total delay $d(x,y)$ of a node $(x,y)$ (usually with
$y=H$) is the time at which this node fires. The relative skew
$s^{\delta}(x,y)$ in horizontal distance $\delta$ is the difference in total
delay; i.e.,
$s^{\delta}(x,y)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=d(x+h,y)-d(x,y)$.
Our main interests are the random variables
$d(H)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=d(0,H)$, i.e. the
delay at the top, and
$s(H)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=s^{1}(0,H)$, i.e.
the relative skew between neighboring nodes.

#### Further Notation

We write $\mathcal{N}(\mu,\sigma^{2})$ to denote the normal distribution with
mean $\mu$ and standard deviation $\sigma$.

Given the average sample value $\bar{v}=\sum_{i=1}^{n}v_{i}/n$ over a set of
$n$ sample values $v_{i}$, we compute the _empiric_ standard deviation as
$(\sum_{i=1}^{n}(v_{i}-\bar{v})^{2}/(n-1))^{1/2}$.

We denote the cumulative distribution function of a random variable $X$ as
$C[X]$; e.g. the term $C[X](x)$ denotes the probability that $X\leq x$. We
denote the inverse function by $C^{-1}[X]$.

A quantile-quantile-plot relates two distributions $A$ and $B$. The simplest
definition is to plot the domain of $A$ against the domain of $B$, using the
function $C^{-1}[B](C[A](x))$.

We define the sample space $\Omega$ as the set of possible specific
assignments of wire delays. If we need to refer to the value of some random
variable $X$ in a sample $s\in\Omega$, we write $X[s]$.

##  3 Delay is Tightly Concentrated

###  3.1 Empiric Analysis

In this subsection, we examine $d(2000)$, which we formally defined in Section
2. Recall that $d(2000)$ is the delay at layer 2000. The results are similar
for other layers and, as we will show in Section 3.3, do change slowly with
increasing $H$.

For reference, consider a simpler system consisting of a sequence of nodes
arranged in a line topology, where each node transmits a pulse once receiving
the pulse from its predecessor. In this system, the delay at layer $H$ would
follow a binomial distribution with mean $H/2=1000$ and standard deviation
$\sqrt{H}/2=\sqrt{2000}/2\approx 22$. Recall that by the central limit
theorem, for large $H$ this distribution will be very close to a normal
distribution with the same mean and standard deviation. In particular, it will
have an exponential tail.

Figure 5 shows the estimated probability mass function of $d(2000)$. The data
was gathered using 25 million independent simulations; in Appendix 0.A we
discuss how we ensured that the simulations are correct.

Observe that the shape looks like a normal distribution, as one might expect.
However, it is concentrated much more tightly around its mean than for the
simple line topology considered above: The empiric standard deviation of this
sample is only 2.741.

Figure 5: Estimated probability mass function of $d(2000)$.

Figure 6: Quantile-quantile plot of $d(2000)$ against $N(1000,2.741^{2})$.

Figure 6 uses a quantile-quantile-plot to show that $d(2000)$ and
$\mathcal{N}(1000,2.741^{2})$ seem to be close to identical, as indicated by
the fact that the plot is close to a straight line. The extremes are an
exception, where numerical and uncertainty issues occur. Of course, they
cannot be truly identical, even if our guess $2.741$ was correct: $d(2000)$ is
discrete and has a bounded support, in contrast to
$\mathcal{N}(1000,2.741^{2})$. However, this indicates some kind of connection
we would like to understand better.

The Dvoretzky-Kiefer-Wolfowitz inequality [13] implies that the true
cumulative distribution function must be within $0.0003255$ (i.e., $8139$
evaluations) of our measurement with probability $1-\alpha=99\%$. For the
values with low frequency however, the Dvoretzky-Kiefer-Wolfowitz inequality
yields weak error bounds.

Instead, we use that Chernoff bounds can be applied to the random variable
$X_{k}$ given by sum of variables $X_{i,k}$ indicating whether the $i$-th
evaluation of the distribution attains value $k$. We then vary $p_{k}$, the
unknown probability that the underlying distribution attains value $k$, and
determine the threshold $p_{\max}$ at which Chernoff’s bound shows that
$p_{k}\geq p_{\max}$ implied that our observed sample had an a-priori
probability of at most $\alpha^{\prime}$; the same procedure is used to
determine the threshold $p_{\min}$ for which $p_{k}\leq p_{\min}$ would imply
that the observed sample has a-priori probability at most $\alpha^{\prime}$.
Note that we can also group together multiple values of $k$ into a single
bucket and apply this approach to the frequency of the overall bucket. This
can be used to address all values with frequency $0$ together. Finally, we
chose $\alpha^{\prime}$ suitably such that a union bound over all
buckets666That is, the number of non-zero values to which we do not apply
Dvoretzky-Kiefer-Wolfowitz plus one (for values of frequency $0$). yields the
desired probability bound of $1-\alpha=99\%$ that _all_ frequencies of the
underlying distribution are within the computed error bounds.

Due to our large number of samples, the resulting error bars for the
probability mass function are so small that they cannot be meaningfully
represented in Figure 5; in fact, on the interval $[990,1010]$ the error bars
are at most $8.05\%$ (multiplicative, not additive), and on the interval
$[994,1006]$ at most $0.93\%$. On the other hand, data points outside
$[990,1010]$ in Figure 6 should be taken as rough indication only.

In other words, we have run a sufficient number of simulations to conclude
that the ground truth is likely to be very close to a binomial (i.e.,
essentially normal) distribution with mean $H/2=1000$ and standard deviation
close to $2.741$; the former is easily shown, which we do next.

###  3.2 Stochastic Analysis

###### Lemma 1

$\mathbb{E}[d(H)]=H/2$.

###### Proof

Consider the bijection $f\colon\Omega\to\Omega$ on the sample space given by
$f(s)=\bar{s}$, i.e., we exchange all delays of $0$ for delays of $1$ and vice
versa. We will show that for a sample $s$ with $d(2000)[s]=\delta$ it holds
that $d(2000)[f(s)]=H-\delta$. As the wire delays are u.i.d., all points in
$\Omega$ have the same weight under the probability measure, implying that
this is sufficient to show that $\mathbb{E}[d(H)]=H/2$.

We prove by induction on $y$ that $d(x,y)[f(s)]=y-d(x,y)[s]$ for all $0\leq
y\leq H$ and $x\in\mathbb{Z}$; by the above discussion, evaluating this claim
at $(x,y)=(0,H)$ completes the proof. For the base case of $y=0$, recall that
$d(x,0)[f(s)]=d(x,0)[s]=0$ by definition.

For the step from $y$ to $y+1$, consider the node at $(x,y+1)$ for
$x\in\mathbb{Z}$. For $c\in\\{-1,0,+1\\}$, the wire delay $w_{c}$ from
$(x+c,y)$ to $(x,y+1)$ satisfies $w_{c}[f(s)]=1-w_{c}[s]$ by construction. By
the induction hypothesis, $d(x+c,y)[f(s)]=y-d(x+c,y)[s]$. Together, this
yields that $(x,y+1)$ receives the pulse from $(x+c,y)$ at time

$\displaystyle d(x+c,y)[f(s)]+w_{c}[f(s)]$
$\displaystyle=y+1-(d(x+c,y)[s]+w_{c}[s]).$

We conclude that

$\displaystyle
d(x,y+1)[f(s)]=\,\operatorname*{median}_{c\in\\{-1,0,1\\}}\\{y+1-(d(x+c,y)[s]+w_{c}[s])\\}$
$\displaystyle=\,y+1-\operatorname*{median}_{c\in\\{-1,0,1\\}}\\{d(x+c,y)[s]+w_{c}[s]\\}=y+1-d(x,y+1)[s].$

###  3.3 Asymptotics in Network Depth

As discussed earlier, forwarding the pulse signal using a line topology would
result in $d(H)$ being a binomial distribution with mean $H/2$ and standard
deviation $\sqrt{H}/2$. For $d(2000)$, we observe a standard deviation that is
smaller by about an order of magnitude.

Figure 7: Log-log plot of the empiric standard deviation of $d(H)$ as a
function of $H$.

Running simulations and computing the empiric standard deviation for various
values of $H$ resulted in the data plotted in Figure 7 as a log-log plot.
Using the technique discussed above, we can compute error bars.777 This relies
on the exponential tails demonstrated in section 3.1. Without this additional
observation, the error bars for all possible skews (including large skews like
$H/2$) would cause large uncertainty in the standard deviation. Again, the
obtained error bounds cannot be meaningfully depicted; errors are about $1\%$
(multiplicative, not additive) with probability $1-\alpha=99\%$. The largest
error margin is at 200 layers, with $1.35\%$.

Figure 7 suggests a polynomial relationship between standard deviation
$\sigma$ and grid height $H$. The slope of the line is close to $1/4$, which
suggests $\sigma\sim H^{\beta}$ with $\beta\approx 1/4$.

This is a quadratic improvement over the reference case of a line topology.

##  4 Skew is Tightly Concentrated

###  4.1 Empiric Analysis

In this subsection, we study $s(2000)$, which we formally defined in Section
2. Recall that $s(2000)$ is the skew at layer 2000 between neighboring nodes.
As we will show in Section 4.3, the behavior for other layers is very similar.
In particular, the skews increase stunningly slowly with $H$.

We gathered data from 20 million simulations888Curiously, we saw skew -7
exactly once, skew -6 never, skew +6 four times. Further investigation showed
this to be a fluke, but we want to avoid introducing bias by picking the
“nicest” sample., and see a high concentration around $0$ in Figure 9, with
roughly half of the probability mass at $0$. Note that again the error bars
cannot be represented meaningfully in Figure 9; in fact, on the interval
$[-3,+3]$ the error bars are at most $6.1\%$ (multiplicative, not additive),
and on the interval $[-2,+2]$ at most $1.4\%$.

Observe that the skew does not follow a normal distribution at all: The
probability mass seems to drop off exponentially like $e^{-\lambda|x|}$ for
$\lambda\approx 2.9$ (where $x$ is the skew), and not quadratic-exponentially
like $e^{-x^{2}/(2\sigma^{2})}$, as it would happen in the normal
distribution. The probability mass for $0$ is a notable exception, not
matching this behavior.

The Dvoretzky-Kiefer-Wolfowitz inequality [13] implies that the true
cumulative distribution function must be within $0.0005147$ (i.e., $5147$
evaluations) of our measurement with probability $1-\alpha=99\%$. In
particular, observing skew $6$ twice without observing skew $-6$ is well
within error tolerance.

Figure 8: The estimated probability mass function for $s(2000)$, with a
logarithmic y-axis. The error bounds are only visible at the fringes.

Figure 9: Empiric standard deviation of $s(H)$ as a function of $H$, as a log-
lin plot.

###  4.2 Stochastic Analysis

First, we observe that the skew is symmetric with mean $0$. This is to be
expected, as the model is symmetric. It also readily follows using the same
argument as used in the proof of Lemma 1.

###### Corollary 1

$s(H)$ is symmetric with $\mathbb{E}[s(H)]=0$.

###### Proof

Consider the bijection used in the proof of Lemma 1. As shown in the proof,
for any $(x,y)\in\mathbb{Z}\times\mathbb{N}_{0}$ and $s\in\Omega$, we have
that

$\displaystyle d(x,y)[f(s)]-d(x+1,y)[f(s)]=\,$ $\displaystyle
y-d(x,y)[s]-(y-d(x+1,y)[s])$ $\displaystyle=\,$
$\displaystyle-(d(x,y)[s]-d(x+1,y)[s]).$

Next we prove that the worst-case skew on layer $H$ is indeed $H$, c.f. Figure
4.

###### Lemma 2

There is a sample $s$ such that $s(H)[s]=H$.

###### Proof

In $s$, we simply let all wire delays $w_{i}$ of wires leading to a node with
positive $x$ be $1$, and let all wire delays $w_{j}$ of wires leading into a
node with non-positive $x$ be $0$. A simple proof by induction shows that for
positive $x$ we get $d(x,y)[s_{1}]=y$ and for non-positive $x$ we get
$d(x,y)[s_{1}]=0$. We conclude that $s(H)[s]=d(1,y)[s]-d(0,y)[s]=H$.

The constructed sample is not the only one which exhibits large skew. For
example, simultaneously changing the delay of all wires between $x=0$ and
$x=1$ does not affect times when nodes pulse. Moreover, for all
$x\notin\\{0,1\\}$, we can concurrently change the delay of any one of their
incoming wires without effect. It is not hard to see that the total
probability mass of the described samples is small. We could not find a way to
show that this is true in general; however, the experiments from Section 4.1
strongly suggests that this is the case. (Hence our question: How to approach
statistical problems like this?)

###  4.3 Asymptotics in Network Depth

Again we lack proper models to describe the asymptotic behavior, and instead
calculate the empiric standard deviation from sufficiently many simulations.

Figure 10: The data of fig. 9 in a loglog-lin plot.

Figure 11: Empiric standard deviation of $s^{\delta}(0,500)$ as a function of
horizontal distance $\delta$ in a log-log plot.

Figure 9 shows that the skew remains small even for large values of $H$.999A
standard deviation below $1$ link delay uncertainty is not unreasonable: Two
circuits clocked over independent links, hop-distance $1$ from a perfect clock
source, have $\sigma(skew)=\sqrt{\mathbb{E}[0.5^{2}]}=0.5$ uncertainties. Note
that the X-axis is logarithmic. Yet again, showing the error bars calculated
using Chernoff bounds and DKW (Dvoretzky-Kiefer-Wolfowitz) is not helpful, as
we get relative errors of about $0.6\%$ with $99\%$ confidence. The largest
error margin is at 100 layers and below, with an error about $0.95\%$.

This suggests that the standard-deviation of $s(H)$ grows strongly sub-
logarithmically, possibly even converges to a finite value. In fact, the data
indicates a growth that is significantly slower than logarithmic: in Figure
11, the x-axis is doubly logarithmic. Thus, the plot suggests that $s(H)\in
O(\log\log H)$.

Note that if we pretended that adjacent nodes exhibit independent delays, the
skew would have the same concentration as the delay. In contrast, we see that
adjacent nodes are tightly synchronized, implying strong correlation.101010For
the sake of brevity, we do not show respective plots.

###  4.4 Asymptotics in Horizontal Distance

So far, we have limited our attention to the skew between neighboring nodes.
In contrast, at horizontal distances $\delta\geq 2H$, node delays are
independent, as they do not share any wires on any path to any clock
generator. Therefore, the skew would be given by independently sampling twice
from the delay distribution and taking the difference. It remains to consider
how skews develop for smaller horizontal distances.

In Figure 11, we see that the skew grows steadily with increasing $\delta$.
These simulations were run with $H=500$ for higher precision and execution
speed. Note that the standard deviation of the skew converges to roughly
$\sqrt{2}\cdot 1.95\approx 2.75$, i.e., $\sqrt{2}$ times the standard
deviation of the delay at $H=500$, as $\delta$ approaches $2\cdot 500=1000$.
This holds because the sum of independent random variables has variance equal
to the sum of variances of the variables. As before, depicting the error bars
determined by our approach is of no use, as relative errors are about $1.6\%$.
The largest error margin is at horizontal distance 25, with $1.79\%$.

The small relative errors indicate that the log-log representation of the data
is meaningful, and suggests that the standard deviation increases roughly
proportional to $\delta^{\gamma}$ for $\gamma\approx 1/3$. It is not
surprising that the slope falls off towards larger values, as we know that the
curve must eventually flatten and become constant for $\delta\geq 2H=1000$.
Overall, we observe that the correlation of skew at a distance is stronger
than expected, specifically $\gamma\approx 1/3$ instead of the expected
$\gamma\approx 1/2$ for small $\delta$.

##  5 Conclusion

In this work, we studied the behavior of the TRIX grid under u.i.d. link
delays, using statistical tools. Our results clearly demonstrate that the TRIX
grid performs much better than one would expect from naive solutions, and thus
should be considered when selecting a fault-tolerant clock propagation
mechanism.

Concretely, our simulation experiments show that the delay as function of the
distance $H$ from the clock source layer is close to normally distributed with
a standard deviation that grows only as roughly $H^{1/4}$, a qualitative
change from e.g. a line topology that would not be achieved by averaging or
similar techniques. Moreover, the skew between neighbors in the same layer is
astonishingly small. While not normally distributed, there is strong evidence
for an exponential tail, and the standard deviation of the distribution as
function of $H$ appears to grow as $O(\log\log H)$. Checking the skew over
larger horizontal counts $d$ (within the same layer) shows a less surprising
pattern. However, still the increase as function of $d$ appears to be slightly
slower than $\sqrt{d}$.

These properties render the TRIX grid an attractive candidate for fault-
tolerant clock propagation, especially when compared to clock trees. We argue
that our results motivate further investigation, considering correlated delays
based on measurements from physical systems as well as simulation of frequency
and/or non-white phase noise. In addition, the impact of faults, physical
realization as less regular grid with a central clock source, and the
imperfection of the input provided by the clock source need to be studied.

Last but not least, we would like to draw attention to the open problem of
analyzing the stochastic process we use as an abstraction for TRIX. This is
also the reason why we lack a purely mathematical analysis. While our
simulation experiments are sufficient to demonstrate that the exhibited
behavior is highly promising, gaining an understanding of the underlying cause
would allow making qualitative and quantitative predictions beyond the
considered setting. As both the nodes’ decision rule and the topology are
extremely simple, one may hope for a general principle to emerge that can also
be applied in different domains.

##  Appendix 0.A Potential Systematic Errors

In this section we discuss possible sources of systematic errors in our
simulations and how we guarded against them.

###  0.A.1 Bugs

Since all experiments are software simulations, measurements have to be taken
to insure against bugs. In this regard, there are several arguments to be
made, some involving the Random Number Generator (RNG):

  * •

We cross-validated four different implementations: (1) A very simple Python
implementation that uses system randomness; (2) a slightly more involved
Python implementation that exhaustively enumerates all possible wire delay
combinations; (3) a straight-forward C implementation using system randomness;
and (4) an optimized C implementation with the slightly weaker RNG
“xoshiro512starstar” [2].

  * •

Even though only implementation (4) was fast enough to be used to generate the
bulk of the results, all implementations agree on the probability
distributions of delay and skew for examples they can handle. Implementation
(2) can only run up to layer 3 ($H\leq 3$), implementations (1) and (3) were
used up to around layers 100 and 1000, respectively.

  * •

Implementation (4) is short (200 lines, plus about 100 lines for the RNG [2]),
and is simple enough to be inspected manually.

  * •

Multiple machines were used, so hardware failure can be ruled out with
sufficient confidence.

###  0.A.2 Randomness and Model

  * •

Tests with a number of weak RNGs showed that TRIX seems to be robust against
this kind of deviation.

  * •

Explorative simulations and validation simulations were kept strictly
separate.

  * •

For most discussions we assumed $H=2000$, because this definitely covers all
practical applications. In fact, we expect that many applications only need
$H=200$ or even $H=20$. In this paper we use a large value for $H$ to show
that the observed behavior is not a fluke that occurs due to low $H$, but that
the growth of delay and skew as function of $H$ is indeed asymptotically slow.

  * •

Using a larger domain only scales the result linearly, as expected.

  * •

Using different wire delay models (e.g. choosing uniformly from
$\\{0,0.5,1\\}$ instead of $\\{0,1\\}$) does not significantly change the
result, and in fact improves it slightly, as expected.

  * •

We only focused on fault-free executions. Observe that single isolated faults
only introduce an additional uncertainty of at most 1 (recall the
normalization $u=1$). As faults are (supposed to be) rare and not maliciously
placed, this means that the predictions for fault-free systems have
substantial and meaningful implications also for systems with faults.

##  Appendix 0.B Raw Data

In the following, we provide the data for all graphs.

Figure 5 | Figure 6
---|---
x (delay) | y (rate) | x (delay) | y (normal)
985 | 0.00000012 | 985.5 | 985.843
986 | 0.00000040 | 986.5 | 986.615
987 | 0.00000140 | 987.5 | 987.338
988 | 0.00001076 | 988.5 | 988.457
989 | 0.00004740 | 989.5 | 989.460
990 | 0.00019060 | 990.5 | 990.462
991 | 0.00066280 | 991.5 | 991.457
992 | 0.00206788 | 992.5 | 992.464
993 | 0.00561240 | 993.5 | 993.470
994 | 0.01324480 | 994.5 | 994.472
995 | 0.02753772 | 995.5 | 995.475
996 | 0.05006436 | 996.5 | 996.479
997 | 0.08002964 | 997.5 | 997.486
998 | 0.11158960 | 998.5 | 998.492
999 | 0.13625144 | 999.5 | 999.498
1000 | 0.14553656 | 1000.5 | 1000.503
1001 | 0.13611860 | 1001.5 | 1001.508
1002 | 0.11158608 | 1002.5 | 1002.515
1003 | 0.07996644 | 1003.5 | 1003.520
1004 | 0.05016040 | 1004.5 | 1004.526
1005 | 0.02753824 | 1005.5 | 1005.531
1006 | 0.01324832 | 1006.5 | 1006.537
1007 | 0.00557100 | 1007.5 | 1007.542
1008 | 0.00205200 | 1008.5 | 1008.545
1009 | 0.00066300 | 1009.5 | 1009.545
1010 | 0.00018904 | 1010.5 | 1010.552
1011 | 0.00004660 | 1011.5 | 1011.556
1012 | 0.00001044 | 1012.5 | 1012.650
1013 | 0.00000144 | 1013.5 | 1013.385
1014 | 0.00000044 | 1014.5 | 1014.363
1015 | 0.00000008 |  |
Figure 11
---
hop dist. | empiric stddev
1 | 0.76334
2 | 0.94346
3 | 1.11873
4 | 1.26012
5 | 1.38309
6 | 1.49367
7 | 1.59118
8 | 1.67803
9 | 1.75621
10 | 1.83219
11 | 1.90233
12 | 1.96331
13 | 2.02323
14 | 2.07683
15 | 2.12580
16 | 2.17155
17 | 2.21355
18 | 2.25797
19 | 2.29356
20 | 2.32732
21 | 2.35812
22 | 2.38959
23 | 2.41912
24 | 2.44794
25 | 2.46569

| Figure 7 |  Figures 9 and 11
---|---|---
x ($H$) | y (stddev delay) | y (stddev skew)
20 | 0.9012352 | 0.74096549
50 | 1.1147817 | 0.75071102
100 | 1.3166986 | 0.75573837
200 | 1.5567596 | 0.75993333
500 | 1.9468302 | 0.76314438
1000 | 2.3115292 | 0.76499614
2000 | 2.7406959 | 0.76601516
5000 | 3.4405614 | 0.76771794

Figure 9
---
x (skew) | lowerb. rate | observed rate | upperb. rate
-7 | 0.0000000 | 0.0000001 | 0.0000010
-6 | 0.0000000 | 0.0000000 | 0.0000009
-5 | 0.0000010 | 0.0000022 | 0.0000041
-4 | 0.0000324 | 0.0000389 | 0.0000452
-3 | 0.0007020 | 0.0007322 | 0.0007578
-2 | 0.0142418 | 0.0143777 | 0.0144897
-1 | 0.2283952 | 0.2287592 | 0.2291231
0 | 0.5120736 | 0.5124375 | 0.5128015
1 | 0.2281477 | 0.2285116 | 0.2288756
2 | 0.0142291 | 0.0143650 | 0.0144769
3 | 0.0007024 | 0.0007326 | 0.0007583
4 | 0.0000343 | 0.0000410 | 0.0000475
5 | 0.0000009 | 0.0000020 | 0.0000038
6 | 0.0000000 | 0.0000002 | 0.0000013

## References

  * [1] Abouzeid, F., Clerc, S., Bottoni, C., Coeffic, B., Daveau, J.M., Croain, D., Gasiot, G., Soussan, D., Roche, P.: 28nm FD-SOI technology and design platform for sub-10pJ/cycle and SER-immune 32bits processors. In: ESSCIRC. pp. 108–111 (2015)
  * [2] Blackman, D., Vigna, S.: Scrambled linear pseudorandom number generators. CoRR abs/1805.01407 (2018), http://arxiv.org/abs/1805.01407
  * [3] Chipana, R., Kastensmidt, F.L.: SET Susceptibility Analysis of Clock Tree and Clock Mesh Topologies. In: ISVLSI. pp. 559–564 (2014)
  * [4] Chipana, R., Kastensmidt, F.L., Tonfat, J., Reis, R.: SET susceptibility estimation of clock tree networks from layout extraction. In: LATW. pp. 1–6 (2012)
  * [5] Chipana, R., Kastensmidt, F.L., Tonfat, J., Reis, R., Guthaus, M.: SET susceptibility analysis in buffered tree clock distribution networks. In: RADECS. pp. 256–261 (2011)
  * [6] Culler, D., Singh, J.P., Gupta, A.: Parallel Computer Architecture: A Hardware/Software Approach. Morgan Kaufmann Publishers Inc. (1998)
  * [7] Daliot, A., Dolev, D., Parnas, H.: Self-stabilizing Pulse Synchronization Inspired by Biological Pacemaker Networks. In: Proc. 6th International Symposium on Self-Stabilizing Systems (SSS). pp. 32–48 (2003)
  * [8] Dolev, D., Függer, M., Lenzen, C., Perner, M., Schmid, U.: HEX: Scaling honeycombs is easier than scaling clock trees. J. Comput. Syst. Sci. 82(5), 929–956 (2016). https://doi.org/10.1016/j.jcss.2016.03.001
  * [9] Dolev, D., Halpern, J.Y., Strong, H.R.: On the Possibility and Impossibility of Achieving Clock Synchronization. J. Comput. Syst. Sci. 32(2), 230–250 (1986)
  * [10] Dolev, D., Hoch, E.N.: Byzantine Self-stabilizing Pulse in a Bounded-Delay Model. In: Proc. 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems (2007). pp. 234–252 (2007)
  * [11] Dolev, D., Függer, M., Lenzen, C., Schmid, U.: Fault-tolerant Algorithms for Tick-generation in Asynchronous Logic. J. ACM 61(5), 30:1–30:74 (2014)
  * [12] Dolev, S., Welch, J.L.: Self-Stabilizing Clock Synchronization in the Presence of Byzantine Faults. Journal of the ACM 51(5), 780–799 (2004)
  * [13] Dvoretzky, A., Kiefer, J., Wolfowitz, J.: Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Math. Statist. 27(3), 642–669 (09 1956). https://doi.org/10.1214/aoms/1177728174
  * [14] Gujja, A., Chellappa, S., Ramamurthy, C., Clark, L.T.: Redundant Skewed Clocking of Pulse-Clocked Latches for Low Power Soft Error Mitigation. In: RADECS. pp. 1–7 (2015)
  * [15] Lenzen, C., Rybicki, J.: Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus. J. ACM 66(5), 32:1–32:56 (2019). https://doi.org/10.1145/3339471
  * [16] Malherbe, V., Gasiot, G., Clerc, S., Abouzeid, F., Autran, J.L., Roche, P.: Investigating the single-event-transient sensitivity of 65 nm clock trees with heavy ion irradiation and Monte-Carlo simulation. In: IRPS. pp. SE–3–1–SE–3–5 (2016)
  * [17] Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press (2005)
  * [18] Patterson, D.A., Hennessy, J.L.: Computer Architecture: A Quantitative Approach. Morgan Kaufmann Publishers Inc. (1990)
  * [19] Srikanth, T.K., Toueg, S.: Optimal Clock Synchronization. J. ACM 34(3), 626–645 (1987)
  * [20] Wang, H.B., Mahatme, N., Chen, L., Newton, M., Li, Y.Q., Liu, R., Chen, M., Bhuva, B.L., Lilja, K., Wen, S.J., Wong, R., Fung, R., Baeg, S.: Single-Event Transient Sensitivity Evaluation of Clock Networks at 28-nm CMOS Technology. IEEE Trans. Nucl. Sci. 63(1), 385–391 (2016)
  * [21] Welch, J.L., Lynch, N.A.: A New Fault-Tolerant Algorithm for Clock Synchronization. Information and Computation 77(1), 1–36 (1988)
  * [22] Wissel, L., Heidel, D.F., Gordon, M.S., Rodbell, K.P., Stawiasz, K., Cannon, E.H.: Flip-Flop Upsets From Single-Event-Transients in 65 nm Clock Circuits. IEEE Trans. Nucl. Sci. 56(6), 3145–3151 (2009)
  * [23] Xanthopoulos, T. (ed.): Clocking in Modern VLSI Systems. Springer (2009)


# From Semi-supervised to Omni-supervised
Room Layout Estimation Using Point Clouds

Huan-ang Gao1,2, Beiwen Tian1,2, Pengfei Li1,2, Xiaoxue Chen1,2
Hao Zhao3,4, Guyue Zhou2, Yurong Chen4 and Hongbin Zha3 1Department of
Computer Science and Technology, Tsinghua University, China, {gha20,tbw18,li-
<EMAIL_ADDRESS>for AI Industry Research
(AIR), Tsinghua University, China<EMAIL_ADDRESS>University, China<EMAIL_ADDRESS><EMAIL_ADDRESS>Labs, China,
<EMAIL_ADDRESS>
###### Abstract

Room layout estimation is a long-existing robotic vision task that benefits
both environment sensing and motion planning. However, layout estimation using
point clouds (PCs) still suffers from data scarcity due to annotation
difficulty. As such, we address the semi-supervised setting of this task based
upon the idea of model exponential moving averaging. But adapting this scheme
to the state-of-the-art (SOTA) solution for PC-based layout estimation is not
straightforward. To this end, we define a quad set matching strategy and
several consistency losses based upon metrics tailored for layout quads.
Besides, we propose a new online pseudo-label harvesting algorithm that
decomposes the distribution of a hybrid distance measure between quads and PC
into two components. This technique does not need manual threshold selection
and intuitively encourages quads to align with reliable layout points.
Surprisingly, this framework also works for the fully-supervised setting,
achieving a new SOTA on the ScanNet benchmark. Last but not least, we also
push the semi-supervised setting to the realistic omni-supervised setting,
demonstrating significantly promoted performance on a newly annotated
ARKitScenes testing set. Our codes, data and models are made publicly
available***https://github.com/AIR-DISCOVER/Omni-PQ.

##  I Introduction

Over the past decade, room layout estimation has drawn a lot of attention from
the robotics community [1, 2, 3, 4, 5, 6] since it marks a crucial step
towards understanding indoor scenes and might help robot agents make better
decisions in challenging environments [7, 8, 9, 10]. However, the majority of
earlier efforts exploit perspective or panoramic RGB images as input [11, 12,
13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28], whereas the
promising paradigm of layout estimation using point clouds (PCs) [29] still
suffers from the lack of annotated data. It is due to the difficulty of
annotating the boundaries of 3D indoor scenes manually, particularly rooms
containing non-cuboid shapes and many corners.

We envision an omni-supervised setting [30] where intelligent robots all over
the world can exploit enormous unannotated raw point clouds to continuously
improve the collective intelligence (i.e., layout estimation accuracy in this
study). To this end, we start from the semi-supervised setting in which we
assume a large portion of ScanNet [31] annotations is not available and push
it finally to the omni-supervised setting using the recent ARKitScenes [32]
dataset.

Actually, semi-supervised room layout estimation has already been studied in a
recent work SSLayout360 [33]. However, it still relies upon hand-crafted post-
processing and only exploits the model exponential moving averaging (EMA)
technique to learn representations from many unannotated panoramic images.
Note that this paradigm does not apply to the state-of-the-art (SOTA) PC-based
layout estimator [29], which directly predicts quads end-to-end.

Figure 1: (a) The input is a 3D point cloud whose colors are only for
visualization. (b) We train the former SOTA method PQ-Transformer with only
20$\%$ labeled data of ScanNet training set and use it as the baseline. (c) We
adopt our method on the whole ScanNet training set with only 20$\%$
annotations, resulting in a more accurate layout prediction.

To this end, we propose the first semi-supervised room layout estimation
method using point cloud inputs. Our method builds upon the SOTA counterpart
PQ-Transformer [29], which takes the 3D point cloud of a scene as input (see
Fig. 1(a)) and predicts a set of quadrilateral (referred to as _quads_)
equations representing layout elements (wall, floor and ceiling). As observed
in Fig. 1(b), it performs poorly on unseen scenes if only $20\%$ annotations
are used for training. By contrast, our model is able to predict a more
accurate layout by making use of the unlabeled data (see Fig. 1(c)).

Specifically, the success of our method is credited to two techniques. The
first is a consistency based training framework inspired by the Mean Teacher
[34] method. We design a quad matching strategy and three consistency
regularization losses that are tailored for the layout estimation problem. We
also identify a simple but effective add-on that capitalizes on the confidence
of the teacher model. The second is a pseudo label generation module that
decomposes the distribution of a new hybrid metric into two components, based
upon gamma mixture. It intuitively aligns quad predictions to reliable layout
point clouds. Through ablation experiments, both techniques are proven
effective, and combining them brings larger improvements.

Experimental results highlight four notable messages: (1) our solution with
different percentages (e.g., $5\%$ to $40\%$) of annotations available
consistently and greatly outperforms supervised baselines on the ScanNet
dataset. (2) with only 40$\%$ of labeled data we are able to surpass prior
fully-supervised SOTA. (3) in the fully-supervised setting, our method can
also improve strong baselines by +4.11$\%$. (4) we further extend the method
into a more realistic omni-supervised [30] setting, where we leverage all
ScanNet training data and unlabeled ARKitScenes [32] training data. On a newly
crowd-sourced ARKitScenes testing set, a significant performance gain is
achieved, with F1-score going from 10.66$\%$ to 25.85$\%$. Our contributions
are as follows:

  * $\bullet$

We propose the first semi-supervised framework for room layout estimation
using point clouds, with tailored designs including a quad set matching
strategy and three confidence-guided consistency losses.

  * $\bullet$

We propose a threshold-free pseudo-label harvesting technique based upon a
newly-proposed hybrid distance metric and gamma mixture decomposition.

  * $\bullet$

We achieve significant results in semi-supervised, fully-supervised and omni-
supervised settings. We contribute a new crowd-sourced testing set and release
our codes.

##  II Related Works

Recently, semi-supervised and weakly-supervised learning are hot topics in the
robotics community, with many methods proposed for various tasks including
point cloud semantic parsing [35, 36, 37, 38] and representation learning
[39], 3D object detection [40][41], articulation understanding [42], single-
view reconstruction [43] and intrinsic decomposition [44]. This line of
research envisions an exciting future scheme that robots all over the world
exploit unlimited unlabeled data to continuously improve the collective
intelligence. [45, 46, 47, 48] Our study is the first semi-supervised
framework for room layout estimation from point clouds, which contributes to
this robotic vision trend.

From the perspective of methodology, we briefly review two kinds of semi-
supervised learning (SSL) paradigms.

The consistency based SSL methods rely on the assumption that near samples
from the low-dimensional input data manifold result in near outputs in the
feature space [49][50]. Thus, they enforce the model to stay in agreement with
itself despite perturbations. Under this scope, multiple perturbation
strategies are explored. The $\Pi$ model [51][52] penalizes the difference of
hidden features of the same input with different data transformations and
dropout. Temporal Ensembling training [52] regularizes consistency on current
and former predictions. The Mean Teacher method [34] uses exponential moving
average of student network parameters.

The pseudo-label based SSL methods, on the other hand, are more general as
they don’t require domain-specific data transformations. By equipping them
with a few necessary designs, they can be as proficient as consistency based
ones. For example, in 3D object detection task, [53] proposes two post-
processing modules to improve the recall rate and the precision rate of the
pseudo labels. In image classification task, [54] sets a constant confidence
threshold $\tau$ for determining whether to discard a pseudo-label, and [55]
upgrades that constant to a set of per-class learnable variables. In 2D object
detection task, Noisy Pseudo-box Learning strategy is proposed by [56], which
only considers $N$ proposals of top-quality as pseudo labels and the rest ones
as false positives.

Figure 2: Method Overview. In each training iteration, we sample
$(\mathbf{X}^{L},\mathbf{Y}^{L})$ from labeled dataset and $\mathbf{X}^{U}$
from unlabeled dataset to form a batch. The input batch is first
stochastically transformed then fed into the student model to produce
predictions $\tilde{\mathbf{Y}}^{L}_{S}$ and $\tilde{\mathbf{Y}}^{U}_{S}$.
Meanwhile, the input batch is also fed into the teacher model then transformed
to produce predictions $\tilde{\mathbf{Y}}^{L}_{T}$ and
$\tilde{\mathbf{Y}}^{U}_{T}$. In the two adopted transformations, FPS sampling
uses different seeds whereas rotation, flipping and scaling are identical. We
impose three losses in total: (1) a supervised loss between the transformed
label and predictions of student model. (2) a consistency loss that minimizes
the difference between student predictions and teacher predictions. (3) a
pseudo-label loss that encourages quads to align with reliable layout points.
The student parameters are updated by gradient descent according to the sum of
three losses, whereas the teacher parameters are updated by exponential moving
average (EMA) of student parameters.

##  III Method

We aim to develop a learning framework that allows robot agents to leverage
enormous unlabeled data to infer room layouts $\mathbf{Y}$ from indoor scene
point clouds $\mathbf{X}$. Following [29], we denote a layout wall
(represented by a quad)
$\mathbf{y}=\\{\mathbf{c},\mathbf{n},\mathbf{s},p\\}\in\mathbf{Y}$ by its
center coordinate $\mathbf{c}$, unit normal vector $\mathbf{n}$, size
$\mathbf{s}=(w,h)$, and predicted quadness score $p$. The quadness scores of
ground truths are fixed to $1.0$.

To start with, we formally describe three training settings. Suppose we have a
3D point cloud (PC) dataset $\mathcal{D}_{L}$ with layout annotations in
conjunction with a much larger unlabeled PC dataset $\mathcal{D}_{U}$. In the
fully-supervised setting, $\mathcal{D}_{L}$ is the whole training set of
ScanNet with quad annotations whereas $\mathcal{D}_{U}$ is a null set. In the
semi-supervised setting, $\mathcal{D}_{L}$ is part of the ScanNet training set
along with quad annotations whereas $\mathcal{D}_{U}$ is the complementary set
whose annotations are assumed unknown. In the omni-supervised setting [30]
which is a real-world generalization of the semi-supervised setting,
$\mathcal{D}_{L}$ is the whole training set of ScanNet with annotations
whereas $\mathcal{D}_{U}$ is the ARKitScenes training set without annotations.

We introduce our method in the three settings using unified notations
$\mathcal{D}_{L}$ and $\mathcal{D}_{U}$. As depicted in Fig. 2, we adapt the
Mean Teacher [34] training framework (see Sec. III-A) to end-to-end room
layout estimation with a tailored quad matching strategy and three consistency
losses. We also integrate a novel pseudo-label refinement module (Sec. III-B)
for quads, which is based upon gamma mixture decomposition. In Sec. III-C, we
describe the loss terms to optimize.

###  III-A Quad Mean Teacher (QMT)

Mean Teacher [34] is a successful framework for semi-supervised learning with
a student model and a teacher model of the same architecture. The general idea
is to feed two models with the same input samples transformed differently and
enforce the predictions of the two models to be consistent. The student model
is updated by gradient descent while the teacher model is updated by
exponential moving average (EMA) of the weights of the student model.

Inspired by the idea of Mean Teacher, we first sample $\mathbf{X}^{U}$ from
$\mathcal{D}_{U}$ and $(\mathbf{X}^{L},\mathbf{Y}^{L})$ from $\mathcal{D}_{L}$
to form a batch $\mathbf{X}=\\{\mathbf{X}^{L},\mathbf{X}^{U}\\}$. $\mathbf{X}$
is transformed with stochastic transformation $T$ before feeding into the
student model to yield
$\tilde{\mathbf{Y}}_{S}=\\{\tilde{\mathbf{Y}}_{S}^{L},\tilde{\mathbf{Y}}_{S}^{U}\\}$.
$\mathbf{Y}^{L}$ is transformed into $\tilde{\mathbf{Y}}^{L}$ with the same
transformation. Meanwhile, $\mathbf{X}$ is also fed into the teacher model and
then applied the same transformation $T$ to yield
$\tilde{\mathbf{Y}}_{T}=\\{\tilde{\mathbf{Y}}_{T}^{L},\tilde{\mathbf{Y}}_{T}^{U}\\}$.
Following the same loss design in [29], we impose a supervised loss
$\mathcal{L}_{\text{sup}}$ between $\tilde{\mathbf{Y}}_{S}^{L}$ and
$\tilde{\mathbf{Y}}^{L}$.

The success of Mean Teacher based methods relies on domain-specific data
transformation and carefully designed consistency losses between two sets of
predictions, without which the method could suffer from degeneration. Based
upon this observation, we design the transformation domain and consistency
losses for room layout estimation as follows.

Data transformation We adopt four kinds of transformations: Farthest Point
Sampling (FPS) [57], flipping along horizontal axes, rotating along vertical
axes and coordinates scaling. FPS [57] downsamples the point cloud by
repeatedly choosing the point farthest from the chosen ones, discarding only
redundant points. Also, flipping, rotating and scaling in constrained ways
mimic the natural viewpoint changes of humans. Among them, layout annotations
are invariant to FPS [57] as subsampling does not change the layout geometries
and equivariant to the other three transformations with which the geometries
should be transformed accordingly. Hence, when applying the same
transformation, for invariant transformation (i.e., FPS [57]) we use different
seeds and for the other three we apply the same transformation before the
student model and after the teacher model.

Quad Set Matching To encourage consistency between the predicted quad sets of
two models, the difference between two quads should be defined first. Given
two quad predictions,
$\tilde{\mathbf{y}}_{1}=\\{\tilde{\mathbf{c}}_{1},\tilde{\mathbf{n}}_{1},\tilde{\mathbf{s}}_{1},p_{1}\\}$
and
$\tilde{\mathbf{y}}_{2}=\\{\tilde{\mathbf{c}}_{2},\tilde{\mathbf{n}}_{2},\tilde{\mathbf{s}}_{2},p_{2}\\}$,
the differences of three geometrical characteristics (quad center location
$\tilde{\mathbf{c}}$, quad normal $\tilde{\mathbf{n}}$, quad size
$\tilde{\mathbf{s}}$) should all be considered. Thus, as illustrated in Fig.
3(b), we define the distance between two quads as: ($|\\!|\cdot|\\!|_{k}$
denotes $k$-norm)

$\displaystyle
d(\tilde{\mathbf{y}}_{1},\tilde{\mathbf{y}}_{2})={|\\!|\tilde{\mathbf{c}}_{1}-\tilde{\mathbf{c}}_{2}|\\!|_{2}}+{|1-\tilde{\mathbf{n}}_{1}\cdot\tilde{\mathbf{n}}_{2}|}+{|\\!|\tilde{\mathbf{s}}_{1}-\tilde{\mathbf{s}}_{2}|\\!|_{2}^{2}}$
(1)

Based on the distance metric between quads, we calculate the difference of two
predicted quad sets by first finding the correspondences between the two quad
sets and then summing up the distances between corresponding quads. To
establish the correspondences, we find the nearest student-predicted quad
$\tilde{\mathbf{y}}_{S}=\\{\tilde{\mathbf{c}}_{S},\tilde{\mathbf{n}}_{S},\tilde{\mathbf{s}}_{S},p_{S}\\}$
for each teacher-predicted quad
$\tilde{\mathbf{y}}_{T}=\\{\tilde{\mathbf{c}}_{T},\tilde{\mathbf{n}}_{T},\tilde{\mathbf{s}}_{T},p_{T}\\}$:

$\displaystyle\mathcal{P}_{\tilde{\mathbf{Y}}_{S}}(\tilde{\mathbf{y}}_{T})=\operatorname*{argmin}_{\tilde{\mathbf{y}}_{S}\in\tilde{\mathbf{Y}}_{S}}|\\!|\tilde{\mathbf{c}}_{S}-\tilde{\mathbf{c}}_{T}|\\!|_{2}$
(2)

We use $\mathcal{P}(\cdot)$ to represent this injective mapping from the
teacher model prediction to the student model prediction.

Consistency Loss Design Although the quad geometries (i.e.,
$\tilde{\mathbf{c}},\tilde{\mathbf{n}},\tilde{\mathbf{s}}$) predicted by
teacher are not adequately precise, the predicted quadness score $p$ could
measure the correctness of the predictions. Considering that the teacher-
predicted quads are generally more reliable than the student-predicted quads,
we use teacher-predicted quadness scores $p_{T}$ as the confidence and define
the consistency loss $\mathcal{L}_{\text{QMT}}$ as:

$\displaystyle\mathcal{L}_{\text{QMT}}=\dfrac{1}{|\tilde{\mathbf{Y}}_{T}|}\sum_{\tilde{\mathbf{y}}_{T}\in\mathbf{Y}_{T}}$
$\displaystyle
d(\mathcal{P}_{\tilde{\mathbf{Y}}_{S}}(\tilde{\mathbf{y}}_{T}),\tilde{\mathbf{y}}_{T})\cdot
p_{T}$ (3)

Remark A similar idea to evaluate the closeness of two sets is the Chamfer
Distance, which establishes two injective mappings from each of the two sets
to its counterpart. On the contrary, our method only establishes a one-way
mapping from the teacher model predictions to the student model predictions
since the latter is less reliable than the former. As depicted in Fig. 3(a),
finding the nearest teacher prediction around $S$ and penalizing the quad
distance in between would wrongly push $S$ to the unreliable prediction
$T_{1}$. By contrast, as $S$ is the nearest student prediction around
unreliable $T_{1}$ and reliable $T_{2}$, optimizing the weighted quad distance
sum would push $S$ to the reliable prediction $T_{2}$.

Figure 3: Illustration on Teacher Student Alignment. (a) For every teacher-
predicted quad, we find the nearest student-predicted quad. Although teacher
predictions are noisy, the quadness scores demonstrate how accurate the
predictions are. (b) These three figure illustrate the three components of the
defined distance between two quads.

###  III-B Gamma Mixture Filtering (GMF)

In this stage, we introduce the Gamma Mixture Filtering module which makes
further use of the unlabeled data and re-estimates a more accurate quad
prediction $\tilde{\mathbf{y}}_{TR}$ from the noisy prediction
$\tilde{\mathbf{y}}_{T}$. A naive approach to do this is to select points
whose perpendicular distance to the quad is below a manually chosen distance
threshold $\epsilon_{D}$ and use these points to estimate a more accurate
quad. However, it is inevitable to manually tune the hyper-parameter
$\epsilon_{D}$, which is time-consuming and ineffective as a fixed threshold
is usually not applicable to all scenes. Besides, using perpendicular distance
solely as the metric may erroneously select points in the room corners which
belong to other quads.

To address these issues, we introduce 1) hybrid distance between point and
quad as an improved metric and 2) the gamma mixture decomposition filtering
strategy to automatically select the threshold for filtering.

Hybrid Point-Quad Metric We propose a hybrid metric to measure the distance
between a point and a quad. Instead of using the perpendicular distance alone,
we also leverage normals and quad sizes. Consider a point $\mathbf{p}$ with
coordinate $\mathbf{c}_{p}$ and normal $\mathbf{n}_{p}$ estimated with
adjacent points in the PC, and a quad $\tilde{\mathbf{y}}_{T}$ whose plane
equation is
$\tilde{\mathbf{n}}_{T}\cdot(\mathbf{c}-\tilde{\mathbf{c}}_{T})=0$,
$\mathbf{c}\in\mathbb{R}^{3}$. Then the perpendicular distance can be written
as:

$\displaystyle\mathcal{M}_{\text{p}}(\mathbf{p},\tilde{\mathbf{y}}_{T})={|(\mathbf{c}_{p}-\tilde{\mathbf{c}}_{T})\cdot\tilde{\mathbf{n}}_{T}|}$
(4)

Note that $\tilde{\mathbf{n}}_{T}$ is of unit length. In some corner cases
where points are close but differ greatly in normals (e.g. in wall corners),
using this measure solely would erroneously include points on other quads.
Therefore, we also define a cosine similarity metric for the normals:

$\displaystyle\mathcal{M}_{\text{o}}(\mathbf{p},\tilde{\mathbf{y}}_{T})=|1-{\mathbf{n}_{p}\cdot\tilde{\mathbf{n}}_{T}}|$
(5)

Furthermore, as the size of quads is not considered in the proposed two
measures, we consider the extent to which the projections of points lay
outside the quad. Since the vertical edges of predicted quads are parallel to
$\hat{\mathbf{z}}=(0,0,1)^{T}$, the horizontal edges should be parallel to
$\hat{\mathbf{x}}=\dfrac{\tilde{\mathbf{n}}_{T}\times\hat{\mathbf{z}}}{|\\!|\tilde{\mathbf{n}}_{T}\times\hat{\mathbf{z}}|\\!|_{2}}$
($\times$ denotes cross product). The horizontal and vertical distances
between the quad center and the projection of $\mathbf{p}$ on the quad are
then given by
$w_{p}=|(\mathbf{c}_{p}-\tilde{\mathbf{c}}_{T})\cdot\hat{\mathbf{x}}|$ and
$h_{p}=|(\mathbf{c}_{p}-\tilde{\mathbf{c}}_{T})\cdot\hat{\mathbf{z}}|$,
respectively. Thus, we define the out-of-quad metric as:

$\displaystyle\mathcal{M}_{\text{s}}(\mathbf{p},\tilde{\mathbf{y}}_{T})=|\\!|\text{ReLU}((w_{p},h_{p})^{T}-\tilde{\mathbf{s}}_{T})|\\!|_{1}$
(6)

Finally, the hybrid point-quad distance is defined as:

$\displaystyle\mathcal{M}=\mathcal{M}_{p}+\mathcal{M}_{o}+\mathcal{M}_{s}$ (7)

In Fig. 4(b) we illustrate the three proposed metrics between the highlighted
quad and points.

Figure 4: Illustration on Gamma Mixture Filtering. We calculate the proposed
hybrid metrics between points and quads in (b), where warmer colors indicate
shorter distances. Then we decompose the distribution of metrics into two
components, corresponding to points that belong to the quad and those don’t,
respectively. We filter out redundant points using the mixture distribution
model (depicted in (c)), and re-estimate quads with higher accuracy for the
student model to learn.

Mixture Decomposition Filtering In this stage we use the hybrid metric
$x=\mathcal{M}(\cdot,\cdot)$ to select points from the PC for each quad. We
first collect the metrics between the quad and all points, and then use the
metrics to fit a probabilistic mixture model. The possibility density function
(PDF) of the probability model is defined as

$\displaystyle
P(x|\theta_{0},\theta_{1})=w_{0}P(x|\theta_{0})+w_{1}P(x|\theta_{1})$ (8)

where $P(x|\theta_{0})$ and $P(x|\theta_{1})$ are PDFs of individual
components and $w_{0},w_{1}$ denote weights of them, with $w_{0}+w_{1}=1$.

The two individual components correspond to points that belong to the quad and
those don’t, respectively. We empirically choose gamma distribution for the
two components:

$\displaystyle
P(x|\theta_{i})=\dfrac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}x^{a-1}(1-x)^{b-1},\theta_{i}=\\{a,b\\}$
(9)

To fit this mixture distribution, we follow [58] to decide the parameters
$\theta_{0},\theta_{1},w_{0}$ and $w_{1}$. By using the expectation
maximization (EM) algorithm, we take the parameters when $\sum_{p\in P}\log
P(x_{p}|\theta_{0},\theta_{1})$ is maximized. The fitting result is
illustrated in Fig. 4(c), where the blue curve represents $P(x|\theta_{0})$
and the red curve represents $P(x|\theta_{1})$.

Finally, with this mixture model, we examine the probabilities that an
unlabeled point belongs and not belongs to the quad. When the former is larger
than the latter, we keep this point during filtering. In other words, for each
quad $\mathbf{y}_{T}$ we keep points $\mathbf{p}_{i}$ that satisfy $\
w_{0}P(x_{i}|\theta_{0})\leq w_{1}P(x_{i}|\theta_{1})$ where
$x_{i}=\mathcal{M}(\mathbf{p}_{i},\mathbf{y}_{T})$, as shown in Fig. 4(d). It
is unnecessary to manually tune a threshold, as the intersection point of the
two component PDFs works as a per-quad threshold obtained by statistics of the
unlabeled points around that quad.

Quad estimation With the set of selected points $P^{\prime}$, we reconstruct a
more accurate quad $\tilde{\mathbf{y}}_{TR}$ for each predicted quad
$\tilde{\mathbf{y}}_{T}$. We refine the quad center and quad normal to
$\mathbf{c}^{\prime}=\frac{1}{|P^{\prime}|}\sum_{p\in
P^{\prime}}\mathbf{c}_{p}$ and $\mathbf{n}^{\prime}={\sum_{p\in
P^{\prime}}\mathbf{n}_{p}}\ /\ {|\\!|\sum_{p\in
P^{\prime}}\mathbf{n}_{p}|\\!|_{2}}$. To estimate the quad size, we randomly
take $K_{s}$ samples $\\{\tau_{i}\\}_{i=1}^{K_{s}}$ from $[0,1]$. Under the
assumption that the point collection $P^{\prime}$ is uniformly sampled from
the refined quad, we refine the quad size to
$\mathbf{s}^{\prime}=\frac{1}{K_{s}}\sum_{i=1}^{K_{s}}\frac{1}{\tau_{i}}\cdot\rm{quantile}(\tau_{i})$.
Here ${\text{quantile}}(\tau_{i})$ is defined as $\tau_{i}$-th quantiles of
$\\{\mathbf{s}_{p}|p\in P^{\prime}\\}$ computed on $\hat{\mathbf{x}}$ axis and
$\hat{\mathbf{z}}$ axis, respectively.

In each scene of each training step, due to tractability concerns, we choose
one of all teacher predicted quads to refine, as illustrated in Fig. 2. Based
on the refined quad
$\tilde{\mathbf{y}}_{TR}=\\{\mathbf{c}^{\prime},\mathbf{n}^{\prime},\mathbf{s}^{\prime},1.0\\}$,
we propose the pseudo-label loss:

$\displaystyle\mathcal{L}_{\text{GMF}}=d(\mathcal{P}(\tilde{\mathbf{y}}_{T}),\tilde{\mathbf{y}}_{TR})$
(10)

###  III-C Loss

The loss term we aim to optimize during training is:

$\displaystyle\mathcal{L}=\mathcal{L}_{\text{sup}}+\lambda_{\text{QMT}}\mathcal{L}_{\text{QMT}}+\lambda_{\text{GMF}}\mathcal{L}_{\text{GMF}}$
(11)

where $\lambda_{\text{QMT}}$ and $\lambda_{\text{GMF}}$ are loss weights.

##  IV Experiment

###  IV-A Datasets and Implementation Details

Datasets In the semi-supervised setting, our methods are evaluated on the
ScanNet dataset. ScanNet [31] is a large-scale RGB-D video dataset with 3D
reconstructions of indoor scenes, including 1513 scans reconstructed from
around 2.5 million views. On top of the ScanNet, SceneCAD [59] provides scene
layout annotations containing 8.4K polygons. In our experiments, we use the 3D
reconstructions from ScanNet [31] as the input point clouds and use the scene
layouts from SceneCAD [59] as the ground truth labels.

Furthermore, we extend our methods to the omni-supervised setting and employ
ARKitScenes dataset [32]. ARKitScenes is another large-scale RGB-D dataset
containing 4493 training scans and 549 validation scans. In our experiments,
the training scans are leveraged as the unlabeled input. The validation scans
are used for testing, whose ground-truth layouts are annotated by crowd-
sourcing.

Implementation Details In the transformation stage, the point cloud is first
downsampled to 40,000 points with FPS and rotated along the z-axis by
$\theta=\theta_{1}+\theta_{2}$, with $\theta_{1}$ randomly chosen from
$\\{0,\frac{\pi}{2},\pi,\frac{3\pi}{2}\\}$ and $\theta_{2}$ uniformly sampled
from $[-5^{\circ},5^{\circ}]$. Next, the point cloud is flipped along the
x-axis and the y-axis with the probability of 0.5 and scaled by a ratio
uniformly sampled from $[0.85,1.15]$.

We implement the teacher and student models in the proposed Quad Mean Teacher
framework with PQ-Transformer [29], while the framework also works with other
layout estimators. The preprocessing of quad annotations and the evaluation
metrics are the same as [29]. The consistency loss weight is set to
$\lambda_{\text{QMT}}=0.05$, using the same warm-up strategy as [60]. The
pseudo-label loss weight is set as $\lambda_{\text{GMF}}=5\times 10^{-4}$. Our
experiments run on a single NVIDIA RTX A4000 GPU with batch size of 6. Half of
the samples in a batch have quad annotations.

###  IV-B Results

To the best of our knowledge, our methods are the first to perform the PC-
based layout estimation task in the semi-supervised and the omni-supervised
setting. Hence we compare our method with fully-supervised methods including
SceneCAD [59] and PQ-Transformer [29].

TABLE I: Layout Estimation F1-scores on ScanNet

Method |  5$\%$ |  10$\%$ |  20$\%$ |  30$\%$ |  40$\%$ |  100$\%$
---|---|---|---|---|---|---
SceneCAD [59] |  - |  - |  - |  - |  - |  37.90
PQ-Transformer [29] |  22.43 |  29.26 |  39.60 |  46.02 |  48.08 |  56.64
Ours (QMT only) |  26.83 |  34.76 |  44.42 |  49.30 |  51.84 |  58.80
Ours (GMF only) |  26.65 |  35.17 |  45.25 |  51.69 |  52.69 |  60.54
Ours (QMT & GMF) |  29.08 |  36.85 |  48.68 |  54.35 |  56.92 |  60.75
Margin |  +6.65 |  +7.59 |  +9.08 |  +8.33 |  +8.84 |  +4.11
Relative Improv. ($\%$) |  29.65$\uparrow$ |  25.94$\uparrow$ |  22.93$\uparrow$ |  18.10$\uparrow$ |  18.37$\uparrow$ |  7.26$\uparrow$

We evaluate our method and the baselines in various semi-supervised settings
on ScanNet validation set and report the F1-scores of the predicted layouts in
Tab. I. The size of labeled set $\mathcal{D}_{L}$ sampled from the ScanNet
training split, or the amount of ground truth annotations in use, is denoted
by percentages in the first row. And $\mathcal{D}_{U}$ is the complementary
set whose annotations are assumed unknown.

It can be seen that either QMT or GMF can result in performance boost. And by
combining these two techniques together, we see further improvement in
performance. In all semi-supervised settings, the performances of our methods
are better than baselines by large margins. With only 40$\%$ quad annotations
available, our method achieves similar performance to that of the state-of-
the-art method trained in fully supervised settings. Surprisingly, our method
also performs better in fully supervised settings than former arts. We
attribute the outperformance to the consistency regularization mechanism
promoting the model’s robustness to perturbations and the pseudo-label
refinement module providing guidance on the geometrical information of
layouts.

We further demonstrate the robustness of our method in the omni-supervised
setting [30]. To be more specific, we train our method and the baselines with
the whole labeled training split of ScanNet $\mathcal{D}_{L}$ and then
evaluate the performance on the validation split of the ARKitScenes dataset
with crowd-sourced layout annotations. Besides, in our method, the unlabeled
training split of ARKitScenes serves as the unlabeled dataset
$\mathcal{D}_{U}$. As shown in Tab. II, our method achieves a significant
margin over former arts, showing the ability to generalize to more realistic
omni-supervised settings.

In addition, we provide visualization of the quad predictions of our method on
ScanNet and ARKitScenes in Fig. 5 and Fig. 6. These qualitative results show
that exterior quads as well as the interior quads are predicted by our method
accurately, compensating for the ineffectiveness of PQ-Transformer [29] w.r.t.
interior wall quads.

TABLE II: Layout Estimation F1-scores on ARKitScenes

Method | Recall (%) | Precision (%) | F1-score (%)
---|---|---|---
PQ-Transformer [29] | 6.72 | 25.81 | 10.66
Ours (QMT & GMF) | 23.00 | 29.50 |  25.85 (+15.19)

Figure 5: Qualitative results on ScanNet. The ratio represents the proportion
of annotated data in use.

###  IV-C Ablation Study

Data Transformation Strategies We run the 10$\%$-supervised experiment on
ScanNet with different data transformations. As shown in Tab. III, data
transformation is crucial to our proposed method, as any of the
transformations improves the performance, and in extreme cases without
transformations the F1-score decreases by 6.31%.

Among the four transformations, rotation has the largest influence on the
performances. One possible reason is that rotation brings the most changes to
the coordinates of points whilst keeping the holistic layouts of the scenes
unchanged.

TABLE III: Ablations on Data Transformation Strategies

Downsample | Flipping | Rotation | Scaling | F1-score (%)
---|---|---|---|---
$\times$ | $\times$ | $\times$ | $\times$ | 30.54
✓ | $\times$ | $\times$ | $\times$ | 31.59
$\times$ | ✓ | $\times$ | $\times$ | 32.47
$\times$ | $\times$ | ✓ | $\times$ | 32.95
$\times$ | $\times$ | $\times$ | ✓ | 30.70
$\times$ | ✓ | ✓ | ✓ | 35.61
✓ | $\times$ | ✓ | ✓ | 34.53
✓ | ✓ | $\times$ | ✓ | 33.42
✓ | ✓ | ✓ | $\times$ | 33.96
✓ | ✓ | ✓ | ✓ | 36.85

Quad Mean Teacher We compare Quad Mean Teacher and the basic Mean Teacher (MT)
method in the 10%-supervised settings and report their performances on ScanNet
in Tab. IV. MT assumes that all teacher predictions are equally reliable.
Results show that the QMT achieves a large margin over MT on the precision of
prediction. We believe this is because the confidence of predictions by the
teacher model is exploited and erratic or incorrect predictions are neglected
accordingly.

Figure 6: Qualitative results on ARKitScenes. Ground truth layouts are
annotated by crowd-sourcing. TABLE IV: Ablations on Quad Mean Teacher

Method | Recall (%) | Precision (%) | F1-score (%)
---|---|---|---
Mean Teacher | 26.39 | 39.61 | 31.67
Ours (QMT) | 27.73 | 46.54 | 34.76

Gamma Mixture Filtering In the 10%-supervised settings, we compare our method
using only pseudo-label loss with the naive $\epsilon_{D}$ approach introduced
in Sec. III-B. We set the fixed threshold $\epsilon_{D}=0.2\text{m}$. More
specifically, in the alternative method, a point stays after filtering if its
perpendicular distance to the plane is less than $\epsilon_{D}$. Compared to
ours, the alternative method achieves significantly lower performance, since
no supervision is applied on the quad normals and sizes.

TABLE V: Ablations on Gamma Mixture Filtering Method | Recall (%) | Precision (%) | F1-score (%)
---|---|---|---
Simple $\epsilon_{D}$ Filtering | 25.29 | 40.51 | 31.14
Ours (GMF) | 29.75 | 43.01 | 35.17

##  V Conclusion

Our research makes the first step towards omni-supervised layout estimation
merely using point clouds, which has promising implications in robotics. Our
training framework combines Quad Mean Teacher and Gamma Mixture Filtering to
better exploit the unlabeled data. Experimental results demonstrate our
method’s effectiveness in semi-supervised, fully-supervised and omni-
supervised settings.

Despite the effectiveness of our method, limitations still exist. The
predictions of our method are unsatisfactory in incomplete scenes, in which
insufficient points fail to form a layout wall. In the future, we will
consider possible rectifications including ensembling online inference
results, thanks to the quasi-real-time speed brought by the PQ-Transformer
[29] implementation.

## References

  * [1] L. Ma, C. Kerl, J. Stückler, and D. Cremers, “Cpa-slam: Consistent plane-model alignment for direct rgb-d slam,” in _2016 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2016, pp. 1285–1291.
  * [2] M. Hsiao, E. Westman, G. Zhang, and M. Kaess, “Keyframe-based dense planar slam,” in _2017 IEEE International Conference on Robotics and Automation (ICRA)_. Ieee, 2017, pp. 5110–5117.
  * [3] M. Kaess, “Simultaneous localization and mapping with infinite planes,” in _2015 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2015, pp. 4605–4611.
  * [4] S. Yang, Y. Song, M. Kaess, and S. Scherer, “Pop-up slam: Semantic monocular plane slam for low-texture environments,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2016, pp. 1222–1229.
  * [5] S. Yang and S. Scherer, “Monocular object and plane slam in structured environments,” _IEEE Robotics and Automation Letters_ , vol. 4, no. 4, pp. 3145–3152, 2019.
  * [6] H. Zhao, R. Ranftl, Y. Chen, and H. Zha, “Transferable end-to-end room layout estimation via implicit encoding,” _arXiv preprint arXiv:2112.11340_ , 2021\.
  * [7] Y. M. Chung, H. Youssef, and M. Roidl, “Distributed timed elastic band (dteb) planner: Trajectory sharing and collision prediction for multi-robot systems,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 10 702–10 708.
  * [8] B. Jin, B. Tian, H. Zhao, and G. Zhou, “Language-guided semantic style transfer of 3d indoor scenes,” in _Proceedings of the 1st Workshop on Photorealistic Image and Environment Synthesis for Multimedia Experiments_ , ser. PIES-ME ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 11–17.
  * [9] C. Pérez-D’Arpino, C. Liu, P. Goebel, R. Martín-Martín, and S. Savarese, “Robot navigation in constrained pedestrian environments using reinforcement learning,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2021, pp. 1140–1146.
  * [10] L. Yuan, X. Gao, Z. Zheng, M. Edmonds, Y. N. Wu, F. Rossano, H. Lu, Y. Zhu, and S.-C. Zhu, “In situ bidirectional human-robot value alignment,” _Science robotics_ , vol. 7, no. 68, p. eabm4183, 2022.
  * [11] S. Yang, D. Maturana, and S. Scherer, “Real-time 3d scene layout from a single image using convolutional neural networks,” in _2016 IEEE international conference on robotics and automation (ICRA)_. IEEE, 2016, pp. 2183–2189.
  * [12] V. Hedau, D. Hoiem, and D. Forsyth, “Recovering the spatial layout of cluttered rooms,” in _2009 IEEE 12th international conference on computer vision_. IEEE, 2009, pp. 1849–1856.
  * [13] M. Hosseinzadeh, Y. Latif, T. Pham, N. Suenderhauf, and I. Reid, “Structure aware slam using quadrics and planes,” in _Asian Conference on Computer Vision_. Springer, 2018, pp. 410–426.
  * [14] G. Pintore, M. Agus, and E. Gobbetti, “Atlantanet: Inferring the 3d indoor layout from a single 360∘ image beyond the manhattan world assumption,” in _European Conference on Computer Vision_. Springer, 2020, pp. 432–448.
  * [15] C. Yan, B. Shao, H. Zhao, R. Ning, Y. Zhang, and F. Xu, “3d room layout estimation from a single rgb image,” _IEEE Transactions on Multimedia_ , vol. 22, no. 11, pp. 3014–3024, 2020.
  * [16] H. Zhao, M. Lu, A. Yao, Y. Guo, Y. Chen, and L. Zhang, “Physics inspired optimization on semantic transfer features: An alternative method for room layout estimation,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 10–18.
  * [17] C. Zou, J.-W. Su, C.-H. Peng, A. Colburn, Q. Shan, P. Wonka, H.-K. Chu, and D. Hoiem, “Manhattan room layout reconstruction from a single 360∘ image: A comparative study of state-of-the-art methods,” _International Journal of Computer Vision_ , vol. 129, no. 5, pp. 1410–1431, 2021.
  * [18] A. G. Schwing and R. Urtasun, “Efficient exact inference for 3d indoor scene understanding,” in _European conference on computer vision_. Springer, 2012, pp. 299–313.
  * [19] C. Liu, A. G. Schwing, K. Kundu, R. Urtasun, and S. Fidler, “Rent3d: Floor-plan priors for monocular layout estimation,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 3413–3421.
  * [20] W. Zhang, Y. Zhang, R. Song, Y. Liu, and W. Zhang, “3d layout estimation via weakly supervised learning of plane parameters from 2d segmentation,” _IEEE Transactions on Image Processing_ , vol. 31, pp. 868–879, 2021.
  * [21] S. Huang, S. Qi, Y. Zhu, Y. Xiao, Y. Xu, and S.-C. Zhu, “Holistic 3d scene parsing and reconstruction from a single rgb image,” in _Proceedings of the European conference on computer vision (ECCV)_ , 2018, pp. 187–203.
  * [22] M. Hirzer, V. Lepetit, and P. ROTH, “Smart hypothesis generation for efficient and robust room layout estimation,” in _Proceedings of the IEEE/CVF winter conference on applications of computer vision_ , 2020, pp. 2912–2920.
  * [23] W. Zhang, W. Zhang, and Y. Zhang, “Geolayout: Geometry driven room layout estimation based on depth maps of planes,” in _European Conference on Computer Vision_. Springer, 2020, pp. 632–648.
  * [24] H. J. Lin and S.-H. Lai, “Deeproom: 3d room layout and pose estimation from a single image,” in _Asian Conference on Pattern Recognition_. Springer, 2019, pp. 719–733.
  * [25] Y. Zhao and S.-C. Zhu, “Scene parsing by integrating function, geometry and appearance models,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2013, pp. 3119–3126.
  * [26] C. Fernandez-Labrador, J. M. Facil, A. Perez-Yus, C. Demonceaux, J. Civera, and J. J. Guerrero, “Corners for layout: End-to-end layout recovery from 360 images,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 1255–1262, 2020.
  * [27] B. Solarte, Y.-C. Liu, C.-H. Wu, Y.-H. Tsai, and M. Sun, “360-dfpe: Leveraging monocular 360-layouts for direct floor plan estimation,” _IEEE Robotics and Automation Letters_ , 2022.
  * [28] C. Fernandez-Labrador, A. Perez-Yus, G. Lopez-Nicolas, and J. J. Guerrero, “Layouts from panoramic images with geometry and deep learning,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 4, pp. 3153–3160, 2018.
  * [29] X. Chen, H. Zhao, G. Zhou, and Y.-Q. Zhang, “Pq-transformer: Jointly parsing 3d objects and layouts from point clouds,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 2519–2526, 2022.
  * [30] I. Radosavovic, P. Dollár, R. Girshick, G. Gkioxari, and K. He, “Data distillation: Towards omni-supervised learning,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 4119–4128.
  * [31] A. Dai, A. X. Chang, M. Savva, M. Halber, T. Funkhouser, and M. Nießner, “Scannet: Richly-annotated 3d reconstructions of indoor scenes,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 5828–5839.
  * [32] A. Dehghan, G. Baruch, Z. Chen, Y. Feigin, P. Fu, T. Gebauer, D. Kurz, T. Dimry, B. Joffe, A. Schwartz _et al._ , “Arkitscenes: A diverse real-world dataset for 3d indoor scene understanding using mobile rgb-d data.” in _NeurIPS Datasets and Benchmarks_ , 2021.
  * [33] P. V. Tran, “Sslayout360: Semi-supervised indoor layout estimation from 360deg panorama,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 15 353–15 362.
  * [34] A. Tarvainen and H. Valpola, “Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results,” _Advances in neural information processing systems_ , vol. 30, 2017\.
  * [35] K. Liu, Y. Zhao, Z. Gao, and B. M. Chen, “Weaklabel3d-net: A complete framework for real-scene lidar point clouds weakly supervised multi-tasks understanding,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 5108–5115.
  * [36] S. Deng, Q. Dong, B. Liu, and Z. Hu, “Superpoint-guided semi-supervised semantic segmentation of 3d point clouds,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 9214–9220.
  * [37] B. Tian, L. Luo, H. Zhao, and G. Zhou, “Vibus: Data-efficient 3d scene parsing with viewpoint bottleneck and uncertainty-spectrum modeling,” _ISPRS Journal of Photogrammetry and Remote Sensing_ , vol. 194, pp. 302–318, 2022.
  * [38] L. Yi, B. Gong, and T. Funkhouser, “Complete & label: A domain adaptation approach to semantic segmentation of lidar point clouds,” in _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2021, pp. 15 363–15 373.
  * [39] S. Huang, Y. Xie, S.-C. Zhu, and Y. Zhu, “Spatio-temporal self-supervised representation learning for 3d point clouds,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 6535–6545.
  * [40] G. Ding, M. Zhang, E. Li, and Q. Hao, “Jst: Joint self-training for unsupervised domain adaptation on 2d&3d object detection,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 477–483.
  * [41] Z. Zhang, Y. Ji, W. Cui, Y. Wang, H. Li, X. Zhao, D. Li, S. Tang, M. Yang, W. Tan _et al._ , “Atf-3d: Semi-supervised 3d object detection with adaptive thresholds filtering based on confidence and distance,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 10 573–10 580, 2022.
  * [42] J. Lv, Q. Yu, L. Shao, W. Liu, W. Xu, and C. Lu, “Sagci-system: Towards sample-efficient, generalizable, compositional, and incremental robot learning,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 98–105.
  * [43] P. Li and H. Zhao, “Monocular 3d detection with geometric constraint embedding and semi-supervised training,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 3, pp. 5565–5572, 2021.
  * [44] K. Wang and S. Shen, “Semi-supervised learning: Structure, reflectance and lighting estimation from a night image pair,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 976–983, 2021.
  * [45] T. Zhao, N. Zhang, X. Ning, H. Wang, L. Yi, and Y. Wang, “Codedvtr: Codebook-based sparse voxel transformer with geometric guidance,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 1435–1444.
  * [46] Q. Li, Y. Wang, Y. Wang, and H. Zhao, “Hdmapnet: An online hd map construction and evaluation framework,” in _2022 International Conference on Robotics and Automation (ICRA)_. IEEE, 2022, pp. 4628–4634.
  * [47] T. Zhang, X. Chen, Y. Wang, Y. Wang, and H. Zhao, “Mutr3d: A multi-camera tracking framework via 3d-to-2d queries,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 4537–4546.
  * [48] Y. Liu, Y. Liu, C. Jiang, K. Lyu, W. Wan, H. Shen, B. Liang, Z. Fu, H. Wang, and L. Yi, “Hoi4d: A 4d egocentric dataset for category-level human-object interaction,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 21 013–21 022.
  * [49] A. Ghosh and A. H. Thiery, “On data-augmentation and consistency-based semi-supervised learning,” in _International Conference on Learning Representations_ , 2020.
  * [50] J. E. Van Engelen and H. H. Hoos, “A survey on semi-supervised learning,” _Machine Learning_ , vol. 109, no. 2, pp. 373–440, 2020.
  * [51] A. Rasmus, M. Berglund, M. Honkala, H. Valpola, and T. Raiko, “Semi-supervised learning with ladder networks,” _Advances in neural information processing systems_ , vol. 28, 2015.
  * [52] S. Laine and T. Aila, “Temporal ensembling for semi-supervised learning,” in _International Conference on Learning Representations_ , 2017.
  * [53] J. Yin, J. Fang, D. Zhou, L. Zhang, C.-Z. Xu, J. Shen, and W. Wang, “Semi-supervised 3d object detection with proficient teachers,” _arXiv preprint arXiv:2207.12655_ , 2022.
  * [54] K. Sohn, D. Berthelot, N. Carlini, Z. Zhang, H. Zhang, C. A. Raffel, E. D. Cubuk, A. Kurakin, and C.-L. Li, “Fixmatch: Simplifying semi-supervised learning with consistency and confidence,” _Advances in neural information processing systems_ , vol. 33, pp. 596–608, 2020.
  * [55] B. Zhang, Y. Wang, W. Hou, H. Wu, J. Wang, M. Okumura, and T. Shinozaki, “Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 18 408–18 419, 2021.
  * [56] G. Li, X. Li, Y. Wang, S. Zhang, Y. Wu, and D. Liang, “Pseco: Pseudo labeling and consistency training for semi-supervised object detection,” _arXiv preprint arXiv:2203.16317_ , 2022.
  * [57] C. R. Qi, L. Yi, H. Su, and L. J. Guibas, “Pointnet++: Deep hierarchical feature learning on point sets in a metric space,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [58] H. Zhao, M. Lu, A. Yao, Y. Guo, Y. Chen, and L. Zhang, “Pointly-supervised scene parsing with uncertainty mixture,” _Computer Vision and Image Understanding_ , vol. 200, p. 103040, 2020.
  * [59] A. Avetisyan, T. Khanova, C. Choy, D. Dash, A. Dai, and M. Nießner, “Scenecad: Predicting object alignments and layouts in rgb-d scans,” in _European Conference on Computer Vision_. Springer, 2020, pp. 596–612.
  * [60] N. Zhao, T.-S. Chua, and G. H. Lee, “Sess: Self-ensembling semi-supervised 3d object detection,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 11 079–11 087.