# Repeated Angles in the Plane for Angles with Algebraic Tangents

Max Aires
Department of Mathematics, Rutgers University, New Brunswick, NJ
<EMAIL_ADDRESS>
###### Abstract

We construct a set of points with $\Omega(n^{2}\log n)$ triples determining an
angle $\theta$ whenever $\tan(\theta)$ is algebraic over $\mathbb{Q}$,
matching the upper bound of Pach and Sharir. This improves upon the original
construction, which was optimal only for $\tan(\theta)=a\sqrt{m}/b$ with
$a,b,m$ positive integers.

##  1 Introduction

Pach and Sharir [4] proved that, for all $0<\theta<\pi$, any set of $n$ points
in the Euclidean plane contains at most $O(n^{2}\log n)$ triples which
determine an angle with measure $\theta$. They also showed that, for
$\tan(\theta)=\frac{a\sqrt{m}}{b}$ with $a,b,m$ positive integers, this upper
bound is tight, and that there exists a configuration of $n$ points in the
plane with $\Omega_{\theta}(n^{2}\log n)$ triples determining angle $\theta$.
However, for other $\theta$, it remains open whether the upper bound is
asymptotically tight (see problem 6, Chapter 6.2 in [1]).

We shall construct a configuration of $n$ points with
$\Omega_{\theta}(n^{2}\log n)$ triples determining angle $\theta$ for any
$0<\theta<\pi$ where $\tan(\theta)$ is algebraic over $\mathbb{Q}$. This class
contains many angles of geometric interest; in particular, this gives a
construction with $\Omega(n^{2}\log n)$ triples if $\theta$ is any rational
multiple of $\pi$, as well as for any constructible angle $\theta$.

The question remains open in the case that $\tan(\theta)$ is transcendental.
We note the similar problem of determining the maximum number of subsets
similar to a desired set $S$; Laczkovich and Ruzsa [3] showed that there exist
configurations with $\Omega(n^{2})$ copies, matching the trivial upper bound,
if and only if the cross-ratio of every quadruple in $S$ is algebraic. Their
construction builds upon that of Elekes and Erdős [2], which finds similar
copies within “pseudo-grids,” which are grid-like configurations of points
made from generalized arithemetic progressions. Our construction makes use of
a similar idea, generalizing the original approach of Pach and Sharir [4] from
rectangle lattice grids to similar grid-like sets.

##  2 Proof

######  Theorem 2.1.

If $\tan(\theta)$ is algebraic over $\mathbb{Q}$, then for $n\geq 3$, there
exist arrangements of $n$ points in the Euclidean plane with
$\Omega_{\theta}(n^{2}\ln n)$ triples determining angle $\theta$.

###### Proof.

Let $\tan(\theta)$ be a algebraic. Then we can write
$\tan(\theta)=\frac{\alpha}{b}$, where $b\in\mathbb{Z}$ and $\alpha$ is a
positive real algebraic integer. Then we can write $\alpha$ as the root of a
monic, irreducible polynomial of degree $d$ in $\mathbb{Z}[x]$. So
$\mathbb{Z}[\alpha]$ is a $\mathbb{Z}$-module with basis
$1,\alpha,\dots,\alpha^{d-1}$.

We shall represent the Euclidean plane as $\mathbb{C}$. Note that $b+i\alpha$
will have argument $\theta$, so we seek triples of the form
$z,z+\lambda_{1}v,z+(b+i\alpha)\lambda_{2}v$, with $z,v\in\mathbb{C}$ and
$\lambda_{1},\lambda_{2}\in\mathbb{R}$. Fix some positive integer $t$ (to be
determined later), and define $\mathcal{K}_{t}$ and $\mathcal{G}_{t}$ as

$\mathcal{K}_{t}:=\left\\{\sum_{k=0}^{d-1}a_{k}\alpha^{k}:a_{k}\in\mathbb{Z},|a_{k}|\leq
t\right\\}$
$\mathcal{G}_{t}:=\mathcal{K}_{t}+i\mathcal{K}_{t}=\\{u_{1}+iu_{2}:u_{1},u_{2}\in\mathcal{K}_{t}\\}$

Note that $\mathcal{G}_{t}$ is the cartesian product of two real generalized
arithmetic progression, while the pseduo-grids of Elekes and Erdős [2] are one
complex generalized arithmetic progression. Clearly,
$|\mathcal{K}_{t}|=(2t+1)^{d}$ and $|\mathcal{G}_{t}|=(2t+1)^{2d}$.

First, suppose $\mu\in\mathcal{K}_{s}$ and $\lambda\in\mathcal{K}_{t}$;
clearly, $\mu+\lambda\in\mathcal{K}_{s+t}$. We shall now consider
$\mu\lambda$. Since $\alpha$ is an algebraic integer with minimal polynomial
of degree $d$, we can write
$\alpha^{d}=c_{0}+c_{1}\alpha+\dots+c_{d-1}\alpha^{d-1}$ for
$c_{i}\in\mathbb{Z}$; let $C_{1}=1+\max(|c_{0}|,|c_{1}|,\dots,|c_{d-1}|)$. By
writing $\lambda=a_{0}+a_{1}\alpha+\dots+a_{d-1}\alpha^{d-1}$ with
$a_{i}\in\mathbb{Z}$, $|a_{i}|\leq t$, we see that
$\alpha\lambda=(a_{0}\alpha+\dots+a_{d-2}\alpha^{d-1})+a_{d-1}(c_{0}+\dots+c_{d-1}\alpha^{d-1})\in\mathcal{K}_{C_{1}t}$.
Applying this observation repeatedly, we see that
$\alpha^{k}\lambda\in\mathcal{K}_{C_{1}^{k}t}$. Hence, if we write
$\mu=b_{0}+b_{1}\alpha+\dots+b_{d-1}\alpha^{d-1}$, we see that
$\mu\lambda=b_{0}\lambda+b_{1}\alpha\lambda+\dots+b_{d-1}\alpha^{d-1}\lambda\in\mathcal{K}_{dC_{1}^{d-1}st}$.

Now suppose $u=(u_{1}+iu_{2})\in\mathcal{G}_{s}$ and
$v=(v_{1}+iv_{2})\in\mathcal{G}_{t}$. Then
$u+v=(u_{1}+u_{2})+i(v_{1}+v_{2})\in\mathcal{G}_{s+t}$, and
$uv=(u_{1}+iu_{2})(v_{1}+iv_{2})=(u_{1}v_{1}-u_{2}v_{2})+i(u_{1}v_{2}+u_{2}v_{1})\in\mathcal{G}_{2dC_{1}^{d-1}st}$.
Letting $C_{2}=2dC_{1}^{d-1}$, we have that $uv\in\mathcal{G}_{C_{2}st}$.

Ungar [5] proved that a set of $N$ points forms has at least $N-1$ pairs of
points each forming a distinct direction. By applying this to the set
$\mathcal{G}_{t}$, we see that $\mathcal{G}_{t}$ contains at least
$(2t+1)^{2d}-1\geq(2t)^{2d}$ pairs giving distinct directions. Since
$\mathcal{G}_{t}-\mathcal{G}_{t}\subseteq\mathcal{G}_{2t}$, this means that
the nonzero elements of $\mathcal{G}_{2t}$ determine at least $(2t)^{2d}$
distinct arguments (directions) from $[0,\pi)$.

Now, for each $1\leq k\leq t$, pick $T_{k}$ as
$(2k)^{2d}-(2(k-1))^{2d}\geq(2k)^{2d-1}$ elements from $\mathcal{G}_{2k}$
whose angles are all distinct from each other and those of
$T_{1},\dots,T_{k-1}$.

For each choice of $v\in\bigcup_{k=1}^{t}T_{k}$ and each
$0<\lambda\in\mathcal{K}_{\left\lfloor t/k\right\rfloor}$, the element
$\lambda v$ is distinct, since each $v\in T_{k}$ has a distinct angle and each
$\lambda$ is a unique positive real number. Moreover, if $v\in
T_{k}\subseteq\mathcal{G}_{2k}$ and $\lambda\in\mathcal{K}_{\left\lfloor
t/k\right\rfloor}$, $\lambda v\in\mathcal{G}_{C_{2}(2k)\left\lfloor
t/k\right\rfloor}\subseteq\mathcal{G}_{2C_{2}t}$. Therefore, for any choice of
$1\leq k\leq t$ and any $z\in\mathcal{G}_{t}$, $v\in
T_{k}\subseteq\mathcal{G}_{2k}$, and
$\lambda_{1},\lambda_{2}\in\mathcal{K}_{\left\lfloor t/k\right\rfloor}$ with
$\lambda_{1},\lambda_{2}>0$, the triple

$(z,z+\lambda_{1}v,z+(b+i\alpha)\lambda_{2}v)$

is a unique triple determining angle $\theta$. Observe that
$z+\lambda_{1}v\in\mathcal{G}_{t+2C_{2}t}$ and (since
$b+i\alpha\in\mathcal{G}_{|b|}$) $z+(b+\alpha
i)\lambda_{2}v\in\mathcal{G}_{t+C_{2}|b|(2C_{2}t)}=\mathcal{G}_{(1+2|b|C_{2}^{2})t}$,
so for all choices of $z,v,\lambda_{1},\lambda_{2}$, we have
$z,z+\lambda_{1}v,z+(b+i\alpha)v\in\mathcal{G}_{(1+2|b|C_{2}^{2})t}$. Since
the elements of $\mathcal{K}_{\left\lfloor t/k\right\rfloor}$ are equally
distributed between positive and negative, with one element $0$, the number of
choices for $\lambda_{1}$ and $\lambda_{2}$ is
$\left(\frac{|\mathcal{K}_{\left\lfloor
t/k\right\rfloor}|-1}{2}\right)=\frac{(2\left\lfloor\frac{t}{k}\right\rfloor+1)^{2d}-1}{2}\geq\left\lfloor\frac{t}{k}\right\rfloor^{2d}$.
Hence the total number of triples chosen in this way is

$\displaystyle|\mathcal{G}_{t}|\sum_{k=1}^{t}|T_{k}|\left\lfloor\frac{t}{k}\right\rfloor^{2d}$
$\displaystyle\geq(2t+1)^{2d}\sum_{k=1}^{t}(2k)^{d-1}\left(\frac{t}{2k}\right)^{2d}$
$\displaystyle\geq t^{2d}\sum_{k=1}^{t}k^{2d-1}\left(\frac{t}{k}\right)^{2d}$
$\displaystyle=t^{4d}\sum_{k=1}^{t}\frac{1}{k}$ $\displaystyle\geq t^{4d}\ln
t$

Hence, there are at least $t^{4d}\ln t$ triples which determine angle $\theta$
with elements chosen from $\mathcal{G}_{(1+2|b|C_{2}^{2})t}$. This set
contains $(2(1+2|b|C_{2}^{2})t+1)^{2d}\leq(4|b|C_{2}^{2}+3)^{2d}t^{2d}$, so if
we let $C_{3}=(4|b|C_{2}^{2}+3)^{2d}$, we have a set of at most $C_{3}t^{2d}$
points whose elements form at least $t^{4d}\ln t$ triples.

Now, for an arbitrary $n$, pick $t$ so that $C_{3}t^{2d}<n\leq
C_{3}(t+1)^{2d}$. If $n\geq C_{3}$, then we have a set with $C_{3}t^{2d}\leq
n$ points. Moreover, if $t\geq 1$, then $n\leq C_{3}(2t)^{2d}$, so
$t\geq\frac{(n/C_{3})^{1/2d}}{2}$, so the number of triples determining angle
$\theta$ is at least $t^{4d}\ln
t\geq\frac{(n/C_{3})^{2}}{2^{4d}}\ln\left(\frac{(n/C_{3})^{1/2d}}{2}\right)=\frac{n^{2}}{2dC_{3}^{2}2^{4d}}\ln\left(\frac{n}{2^{2d}C_{3}}\right)$.
Since $d$ and $C_{3}$ depend only on our angle $\theta$ and not on $n$, we
have a construction of at most $n$ points with $\Omega_{\theta}(n^{2}\log n)$
triples determining angle $\theta$, as desired. ∎

## References

  * [1] P. Brass, W. Moser, and J. Pach.  Research problems in discrete geometry.  2005\.
  * [2] G. Elekes and P. Erdős.  Similar configurations and pseudo grids.  Intuitive geometry (Colloquia mathematica Societatis János Bolyai), pages 85–104, 1991.
  * [3] M. Laczkovich and I. Z. Ruzsa.  The number of homothetic subsets.  The Mathematics of Paul Erdős II, pages 294–302, 1997.
  * [4] J. Pach and M. Sharir.  Repeated angles in the plane and related problems.  Journal of Combinatorial Theory, Ser. A, 59:12–22, 1992.
  * [5] P. Ungar.  $2N$ noncollinear points determine at least $2N$ directions.  Journal of Combinatorial Theory, Ser. A, 33:343–347, 1982.


# The Devils in the Point Clouds: Studying the Robustness of Point Cloud
Convolutions

Xingyi Li, Wenxuan Wu, Xiaoli Z. Fern, and Li Fuxin
Oregon State University
{lixin, wuwen, xfern<EMAIL_ADDRESS>
###### Abstract

Recently, there has been a significant interest in performing convolution over
irregularly sampled point clouds. Since point clouds are very different from
regular raster images, it is imperative to study the generalization of the
convolution networks more closely, especially their robustness under
variations in scale and rotations of the input data. This paper investigates
different variants of PointConv, a convolution network on point clouds, to
examine their robustness to input scale and rotation changes. Of the variants
we explored, two are novel and generated significant improvements. The first
is replacing the multilayer perceptron based weight function with much simpler
third degree polynomials, together with a Sobolev norm regularization.
Secondly, for 3D datasets, we derive a novel viewpoint-invariant descriptor by
utilizing 3D geometric properties as the input to PointConv, in addition to
the regular 3D coordinates. We have also explored choices of activation
functions, neighborhood, and subsampling methods. Experiments are conducted on
the 2D MNIST & CIFAR-10 datasets as well as the 3D SemanticKITTI & ScanNet
datasets. Results reveal that on 2D, using third degree polynomials greatly
improves PointConv’s robustness to scale changes and rotations, even
surpassing traditional 2D CNNs for the MNIST dataset. On 3D datasets, the
novel viewpoint-invariant descriptor significantly improves the performance as
well as robustness of PointConv. We achieve the state-of-the-art semantic
segmentation performance on the SemanticKITTI dataset, as well as comparable
performance with the current highest framework on the ScanNet dataset among
point-based approaches.

##  1 Introduction

Convolution is one of the most fundamental concepts in deep learning.
Convolutional neural networks (CNNs) have redefined the state-of-the-art for
almost every task in computer vision. In order to transfer such successes from
2D images to the 3D world, there is a significant body of work aiming to
develop the convolution operation on 3D point clouds. This is essential to
many applications such as autonomous driving and virtual/augmented reality.

PointConv [60] seems to be one of the promising efforts. Similar to earlier
work [43, 18, 59, 14, 58, 64], PointConv utilizes a multi-layer perceptron
(MLP) to learn the convolution weights on each point implicitly as a nonlinear
transformation from the point coordinates, basically a Monte Carlo
discretization of the continuous convolution operator on irregular point
clouds, but with the efficient version of PointConv it now can scale to modern
deep networks with dozens of layers. PointConv is permutation-invariant and
translation-invariant, and to our best knowledge is the only approach that
achieved equivalent performance to 2D CNNs on images as well as having one of
the highest performances on 3D benchmarks.

Figure 1: Examples of learned weight functions from PointConv: (a) MLP-based
PointConv trained on MNIST; (b) MLP-based PointConv trained with Faster R-CNN;
(c) Sobolev-regularized cubic polynomial (Best Viewed in Color)

Networks based on point clouds introduce a new complication on the
neighborhoods used in convolution. In 2D images, we are accustomed to having
fixed-size neighborhoods such as $3\times 3$ or $5\times 5$. PointConv and
other point-based networks instead adopt k-nearest neighbors (kNN), which may
potentially make it harder for point cloud networks to generalize from
training locations to testing locations, as sufficiently smooth weight
functions need to be learned. Usually, point cloud networks augment the data
by randomly jittering point locations, but such jittering only provides local
generalization. We attempted to plot one of the typical learnt weight function
on MNIST and on a faster-RCNN detector as shown in Fig. 1 (a-b). As one can
see, due to the nonlinearity in the weight functions, PointConv could
potentially generalize poorly if the testing neighborhoods are substantially
different from those of the training. Indeed, even in 2D images we rely on re-
scaling of all the images to the same scale to avoid this generalization
issue. Such a simple shortcut is, however, unlikely to suffice for point
clouds as each kNN neighborhood may be significantly different from others in
terms of scale.

In this paper we study empirically the generalization of PointConv under scale
changes (resulting in different sampling densities) and rotations, which would
induce very different neighborhoods between training and testing. The basic
methodology is to train the network with a certain set of scales and
rotations, and test it on out-of-sample scales/rotations that are
significantly different from the training ones. Experiments are done both on
the 2D MNIST [25] & CIFAR-10 [22] datasets, and the 3D SemanticKITTI [2] &
ScanNet v2 [8] datasets. Multiple design choices are tested, including
different neighborhood selection methods, activation functions, input feature
transformations and regularization methods to examine their impact on
generalization under scale changes and rotations.

From the experiments, we identify two strategies that have not been applied to
point cloud networks to be the most effective. In 2D images, we propose to
utilize cubic polynomials as the weight functions, with a Sobolev norm
regularization similar to thin-plate splines. This restricts the flexibility
of the weight functions (Fig. 1) and improves generalization. We additionally
find that using an $\epsilon$-ball neighborhood is more robust than kNN in 2D.
With these improvements, we have found PointConv to be more robust than
traditional raster CNNs on scale changes and rotations, which suggests a
potential of applying PointConv on 2D images for the sake of robustness in
future work.

For 3D point clouds, we introduce a novel viewpoint-invariant (VI) feature
transformation to the 3D coordinates. The results show that our novel feature
transformation is not only rotation-invariant, but also robust to neighborhood
size changes and achieves significantly better generalization results than
simply using 3D coordinates as input. VI enables coordinates to generalize to
neighborhood of different sizes, hence we have found that $\epsilon$-ball
neighborhoods become no longer necessary on top of VI. This is welcome news
since $\epsilon$-ball neighborhoods (e.g. utilized commonly in KPConv [49])
are more expensive to compute than kNN neighborhoods.

##  2 Related Work

Volumetric and Projection-based Approaches A direct extension from convolution
in 2D raster images to 3D is to compute convolution on volumetric grids [61,
33, 39, 57]. In densely sampled point clouds, sparse volumetric convolutions
such as MinkowskiNet [5] and Submanifold sparse convolution [10] currently
obtain the best performance. However, they depend heavily on being able to
locate enough points in a local volumetric neighborhood of each point, hence
are difficult to apply to cases where the sampling density of point clouds is
low or especially uneven (e.g. LIDAR). Some other approaches that project
point clouds onto multi-view 2D images [46, 36, 30] or lattice space [45] may
suffer from the same issue.

Point-based Approaches [35] first attempted to directly work on point clouds,
and PointNet++ [37] improved it by adding a hierarchical structure. Following
PointNet++, some other studies also attempted to utilize hierarchical
architectures to aggregate information from neighbor points with MLPs [26,
31]. PointCNN [27] utilized a learned $X$-transformation to weight the local
features and reorder them simultaneously. FeaStNet [52] utilize a soft-
assignment matrix to generalize traditional convolution on point clouds. Flex-
convolution [11] introduced a convolution layer for arbitrary metric spaces,
along with an efficient GPU implementation. A-CNN [21] proposed a annular
convolution that assigned kernel weights for neighbour points based on their
distances to the center point. PointWeb [68] considered every pair of points
within the neighborhood for extracting contextual features. A-SCN [62] adopt
the dot-product self-attention mechanism from [51] to propagate features.
PointASNL [65] proposed an adaptive sampling strategy to avoid outliers before
extracting local and global features from each point cloud.

Generally, convolutional approaches on point clouds performed better than the
approaches listed above. [43, 18, 59, 14, 58, 64] proposed to learn
discretizations of continuous convolutional filters. [18] utilized a side
network to generate weights for 2D convolutional kernels. [43] generalized it
to 3D point clouds, and [58] further extends it to segmentation tasks [58],
along with an efficient version. However, the efficient version in [58] only
achieves depthwise convolution rather than full convolution. EdgeConv [59]
encodes pairwise features between a neighbor point and the center point
through MLPs. [14] takes densities into account. Pointwise CNN [16] located
kernel weights for predefined voxel bins, so it was not flexible. SpiderCNN
[64] proposed a polynomial weight function, which we experiment with in this
paper. However, they did not utilize regularization to control the smoothness.
The formulation of PointConv [60] is mathematically similar to [14], and it
encompasses [43, 59] and [58], since those can be viewed as special cases of
PointConv, removing some of the components (e.g. density, full convolution).
The main contribution in PointConv [60] is an efficient variant that does not
explicitly generate weight functions, but implicitly so by directly computing
the convolution results between the weights and the input features. Such a
variant removed the memory requirement to store the weights and networks,
allowing for scaling up to the “modern” deep network size, e.g. dozens of
layers with hundreds of filters per layer. It is also the only paper showing
results on CIFAR-10 matching those of a 2D CNN of the same structure.

The main competitive point-based convolutional approach to PointConv is KPConv
[49]. In KPConv, convolution weights are generated as kernel functions between
each point and anchor points, points in the 3D space that are pre-specified as
parameters for each layer separately. KPConv enjoys nice performance due to
the smooth and well-regularized kernel formulation, but it introduces
significantly more parameters in the specification of anchor points and their
$\epsilon$-ball neighborhoods are computationally costly. Similar to KPConv,
PCNN [1] also assign anchor points with kernel weights, but it does not take
neighbor points into account for convolution.

Scale and rotation invariance in convolution We did not find significant
amount of related work in studying scale and rotation robustness on point
clouds. [56, 66] build a spatial transformer side network (STN) to learn
global transformations on input point clouds. The main difference comparing
with our work is that we aim to improve the robustness against transformations
through directly working on the network itself, instead of designing
additional structures to accommodate them.

A significant amount of work have been published in 2D CNNs on scale and
rotation invariance. A standard approach has been data augmentation [44, 12,
50, 24, 4, 13], where the training set is augmented by including objects with
random rescaling or rotations. A group of studies attempted to integrate deep
CNNs with side-networks [29, 69, 55, 63, 67, 19] or attention modules [54,
42]. [70] convolved the input with several rotated versions of the same CNN
filter before feeding to the pooling layer. Some techniques proposed to learn
transformations directly [17, 28] on the input or intermediate outputs from
convolutional layers in a deep network [9, 40]. There has also been interest
in combining group concepts with CNNs to encode scale and rotate
transformations [6, 3, 7].

Non-deep Approaches [41] encodes relations between local 3D surface patches as
well as global patches in a viewpoint invariant manner, which is a good hint
for this work.

##  3 Methodology

The main goal of this work is to investigate how to best enable the learned
weight function to generalize from known local locations to unseen ones, to
make PointConv [60] based networks more robust against unseen scales and
rotations of objects. Toward this, we attempted three methods. First, we
replace kNN with $\epsilon$-ball based neighbor search to unify the receptive
field for each PointConv layer. Next, we introduce a much simpler hypothesis
space of third degree polynomials to replace MLP for weight functions to avoid
overfitting. To further enforce the smoothness of this hypothesis space, we
utilize the Sobolev norm for thin-plate splines as a regularizer. Finally, for
3D point clouds, we introduce a viewpoint-invariant (VI) descriptor for the
MLP that utilizes geometric properties of the data to be less sensitive to
local scale and rotation changes.

Below we will first introduce PointConv [60], followed by the description of
$\epsilon$-ball based neighbor search, third degree polynomials, and the VI
descriptor for the weight function, respectively.

Figure 2: (a) We perform robustness experiments of PointConv on 2D images
where the training kNN neighborhood is significantly different from the
testing; (b) For a given local center point $p_{\mu}$ and $p_{\alpha}\in
N_{\epsilon}(p_{\mu})$ for a pair of points, a set of viewpoint-agnostic basis
$(\vec{r},\vec{w},\vec{v})$ can be generated from $\vec{r}_{\mu}^{\alpha}$ and
$n_{\mu}$ with the Gram-Schmidt process, and viewpoint-invariant features such
as the angles between $\vec{n_{\mu}}$ and $\vec{v}$ can be extracted from them

###  3.1 Background: PointConv

A point cloud can be denoted as a set of $3D$ points
$P=\\{p_{1},p_{2},...,p_{n}\\}$, where each point $p_{i}$ contains a position
vector $(x,y,z)\in R^{3}$ as well as a feature vector (RGB color, surface
normal, etc.). A line of work including PointConv generalizes the convolution
operation to point clouds based on discretizations of continuous 3D
convolutions [43, 14, 59, 60]. For a center point $p_{xyz}=(x,y,z)$, its
PointConv is defined by:

$\small\begin{multlined}PointConv(S,W,F)_{xyz}=\\\
\sum_{(\delta_{x},\delta_{y},\delta_{z})\in
G}S(\delta_{x},\delta_{y},\delta_{z})W(\delta_{x},\delta_{y},\delta_{z})F(x+\delta_{x},y+\delta_{y},z+\delta_{z})\end{multlined}PointConv(S,W,F)_{xyz}=\\\
\sum_{(\delta_{x},\delta_{y},\delta_{z})\in
G}S(\delta_{x},\delta_{y},\delta_{z})W(\delta_{x},\delta_{y},\delta_{z})F(x+\delta_{x},y+\delta_{y},z+\delta_{z})$
(1)

where $(\delta_{x},\delta_{y},\delta_{z})$ denote the coordinate offsets for a
point in $p_{xyz}$’s local neighborhood $G$, usually located by kNN.
$F(x+\delta_{x},y+\delta_{y},z+\delta_{z})$ represents the feature of the
point, and $W(\delta_{x},\delta_{y},\delta_{z})$ is the convolution kernel
generating the weights for convolution and is approximated by an MLP, called
WeightNet in [60]. Finally, $S(\delta_{x},\delta_{y},\delta_{z})$ represents
the inverse local density to balance the impact of non-uniform sampling of the
point clouds.

PointConv uses an efficient approach to avoid the computation of the function
values of $W$ at each point, which is extremely memory-intensive. The
computation approach does not change the final output of eq. (1), hence we
omit it. A deep network can be built from PointConv layers similar to 2D
convolutions. For stride-2 convolution/pooling, one can just subsample the
point clouds [37]. [60] also provides a deconvolution/upsampling approach to
increase the resolution of point clouds. Hence, classification and semantic
segmentation tasks can be solved with PointConv networks. It is also
straightforward to incorporate other commonly used 2D convolution operations,
e.g. residual connections. Dilated convolution can be approximated by first
sampling a larger kNN neighborhood, and then subsampling from the
neighborhood.

###  3.2 $\epsilon$-ball neighbor search and activations

The neighborhood $G$ in PointConv is usually defined by kNN. Fig. 2 (a)
illustrates the robustness issue for K-nearest neighbors search. Namely, the
equivalent receptive field for a sparse point cloud is much larger than the
one for a densely distributed point cloud. If trained only on dense (high
resolution) point clouds, the learned weight function may not generalize well
to much larger (unseen) receptive fields when dealing with sparse point clouds
during testing.

An $\epsilon$-ball based neighborhood (e.g. commonly used in KPConv [49]) on
the other hand would be robust to different sampling rates. For a point
$p_{i}$, denote $N_{\epsilon}(p_{i})=\\{p_{j}\in P|d(p_{i},p_{j})<\epsilon\\}$
as its $\epsilon$-ball neighborhood. To ease the computation burden, we
(randomly) select at most $K$ neighbors from $N_{\epsilon}(p_{i})$. The actual
chosen neighbors from $N_{\epsilon}(p_{i})$ are denoted as
$C_{\epsilon}(p_{i},K)$. Compared with kNN, $\epsilon$-ball neighborhood
retains the maximal distance of the neighbors w.r.t. the center point. Since
different $\epsilon$-balls may contain different number of neighbors, we
replace the normalizer $S(\delta_{x},\delta_{y},\delta_{z})$ in equation 1
with $\frac{1}{|C_{\epsilon}(p_{i},K)|}$. Note that the flexibility of the
PointConv framework allows for variable number of neighbors in each
neighborhood.

We also investigate the robustness over several different activations in the
MLP-based WeightNet, such as ReLU [34], SeLU [20], Leaky ReLU [32], and Sine
$(\sin(x))$. Sine is included because its connections to random Fourier
features [38]. In [38], it was proved that a basis of
$\cos(\mathbf{Wx}+\mathbf{b})$ with random $\mathbf{W}$ and $\mathbf{b}$ could
be a universal function approximator. Hence we thought learned $\mathbf{W}$
and $\mathbf{b}$s could improve over the pure random one. Empirically we have
found that using sine worked better than cosine, maybe due to the fact that
$sin(0)=0$ hence it does not introduce additional constants.

###  3.3 Convolutional Kernels as Cubic Polynomials

The set of functions MLPs can represent is very large, which may introduce
overfitting to the training point locations. Hence, we experiment with much
simpler weight functions $W(\delta_{x},\delta_{y},\delta_{z})$ in the form of
cubic polynomials of $(x,y,z)$. This was investigated in [64], however with
some arbitrary additional functions multiplied that actually reduced the
performance on 2D [60]. We utilize a plain version, with proper weights to
regularize for smoothness. In 2D, this results in a feature space:

$\small\phi(x,y)=[x^{3},y^{3},\sqrt{3}x^{2}y,\sqrt{3}xy^{2},\sqrt{3}x^{2},\sqrt{3}y^{2},\sqrt{6}xy,x,y,1]$
(2)

and in 3D:

$\begin{split}\phi(x,y,z)=[x^{3},y^{3},z^{3},\sqrt{3}x^{2}y,\sqrt{3}x^{2}z,\sqrt{3}xy^{2},\sqrt{3}y^{2}z,\\\
\sqrt{3}xz^{2},\sqrt{3}yz^{2},\sqrt{3}x^{2},\sqrt{3}y^{2},\sqrt{3}z^{2},\sqrt{6}xyz,\sqrt{6}xy,\\\
\sqrt{6}xz,\sqrt{6}yz,\sqrt{3}x,\sqrt{3}y,\sqrt{3}z,1]\end{split}$

The coefficients of each term ensures that an $L_{2}$ regularization on the
feature descriptors (excluding linear and constant terms) correspond to
regularizing with the Sobolev $S_{2}$ norm:

$||f||_{s_{2}}^{2}=\lambda\int\int[(\frac{\partial^{2}f}{\partial
x^{2}})^{2}+2(\frac{\partial^{2}f}{\partial x\partial
y})^{2}+(\frac{\partial^{2}f}{\partial y^{2}})^{2}]dxdy$ (3)

in 2D, where $\lambda$ is a parameter. The 3D form can be written similarly.
Sobolev-norm regularizations are commonly used in thin-plate splines [53] but
to our knowledge they have not been used in point cloud networks in the past.
Note that the choice of a third degree polynomial is common in the smoothing
splines community. Quadratic functions have undesirable symmetries and fourth-
order polynomials introduce too many terms, e.g. $35$ terms for a 3D space.

###  3.4 A Viewpoint-Invariant Input Descriptor

PointConv relies on the $(x,y,z)$ coordinates to compute the weights, which is
sensitive to the rotation of the object as well as the sampling rate of the
point clouds. We hypothesize that by using viewpoint-invariant descriptors for
the weight function, we can achieve better generalization.

We develop a viewpoint-invariant (VI) descriptor for each point $p_{\alpha}$
in a local neighborhood as an $8$-dimensional vector utilizing its geometric
relationship with the center point $p_{\mu}$. Denote the surface normal of
$p_{\mu}$ as $\hat{n}_{\mu}$ and its difference with $p_{\alpha}$ as
$\vec{r}_{\mu}^{\alpha}=p_{\alpha}-p_{\mu}$. When the scene is rotated, the
angle between $\hat{n}_{\mu}$ and $\vec{r}_{\mu}^{\alpha}$ remains the same.
To discriminate between different directions, we generate an orthonormal basis
from $\\{\hat{n}_{\mu},\vec{r}_{\mu}^{\alpha}\\}$ and compute the angles
between $\hat{n}_{\mu}$, $\vec{r}_{\mu}^{\alpha}$ and $\hat{n}_{\alpha}$ as
well as the projection lengths of $\hat{n}_{\alpha}$ and $\hat{n}_{\mu}$ onto
the orthonormal basis. With a global rotation of the scene, the basis and
normal vectors are identically rotated. Hence, our descriptor is rotation
invariant and provides a complete characterization of the vectors
$\hat{n}_{\mu}$, $\vec{r}_{\mu}^{\alpha}$ and $\hat{n}_{\alpha}$.

Formally, we utilize the Gram-Schmidt process on
$\\{\vec{r}_{\mu}^{\alpha},\hat{n}_{\mu}\\}$ to generate a 3D basis
$\\{\hat{r},\hat{v},\hat{w}\\}$ where
$\hat{r}=\frac{\vec{r}_{\mu}^{\alpha}}{||\vec{r}_{\mu}^{\alpha}||}$,
$\hat{v}=\frac{\hat{n}_{\mu}-(\hat{r}^{\top}\hat{n}_{\mu})\hat{r}}{\sqrt{1-(\hat{r}^{\top}\hat{n}_{\mu})^{2}}}$
is orthonormal to $\hat{r}$, and $\hat{w}$ is derived by
$\hat{r}\times\hat{v}$, the outer product of $\hat{r}$ and $\hat{v}$, as
illustrated in Fig. 2. Note that this basis is seldom degenerate, because it
is unlikely for $\hat{n}_{\mu}$ and $\vec{r}_{\mu}^{\alpha}$ to be collinear
in 3D surface point clouds.

With the basis defined, for each point $p_{\alpha}$ in the neighborhood of
$p_{\mu}$, we extract the following viewpoint invariant feature vector:

$\begin{split}\beta_{\mu}^{\alpha}=[\hat{n}_{\alpha}\cdot\hat{n}_{\mu},\frac{\vec{r}_{\mu}^{\alpha}\cdot\hat{n}_{\mu}}{\|\vec{r}_{\mu}^{\alpha}\|},\frac{\vec{r}_{\mu}^{\alpha}\cdot\hat{n}_{\alpha}}{\|\vec{r}_{\mu}^{\alpha}\|},\hat{n}_{\alpha}\cdot\hat{v},\hat{n}_{\alpha}\cdot\hat{w},\\\
\vec{r}_{\mu}^{\alpha}\cdot\hat{n}_{\mu},\vec{r}_{\mu}^{\alpha}\cdot(\hat{n}_{\alpha}\times\hat{n}_{\mu}),||\vec{r}_{\mu}^{\alpha}||]\end{split}$
(4)

where $\times$ represents the cross product. The first $5$ features are both
scale and rotation invariant, and the last $3$ features are rotation invariant
only. We believe that a weight function with this input will be invariant to
rotation and more robust against scale changes. We also anticipate this to
alleviate the need for rotation-based data augmentation.

##  4 Experiments

###  4.1 MNIST

MNIST contains $60,000$ handwritten digits in the training set and $10,000$
digits in the test set from 10 distinct classes. The original resolution of
each image is $28\times 28$. We trained a 4-layer network. Table 1 illustrate
the general architecture for our proposed framework and all other baselines.
They only differ in the structures for convolutional layers. The $\epsilon$ is
fixed to $\frac{1}{10}$ for Conv1 in Table 1, $\frac{1}{5}$ for Conv2, and
$\frac{1}{2}$ for Conv3 as well as Conv4. The numbers of output points from
FPS for Subsampling1 Subsampling2 layer in Table 1 are $196$ and $49$
respectively. The coefficient of the Sobolev norm regularization is set to
$10^{-6}$ or $10^{-5}$ for our proposed approach. For other ablation variants,
it was tuned to the optimal one. We utilize cross entropy as the loss
function. The batch size is $60$ and the optimizer is Adam with learning rate
$0.001$. For traditional 2D CNN baselines, we adopt max pooling with $2\times
2$ stride for the sub-sampling layer. Global average pooling is used in the
last layer to account for different input resolutions. For point cloud sub-
sampling, we attempt two different methods. The first one is named as PC-2D
subsampling, which achieves the equivalent number of sampled points as 2D max-
pooling with stride $2\times 2$, but in point cloud formats. The next one is
Farthest Point Sampling (FPS), a commonly used sampling approach in point
cloud networks [37, 60].

Layer name | Layer description
---|---
Conv1 |  $3\times 3$ conv. (or PointConv) 64 w/ ReLU
Subsampling1 |  max-pooling with stride $2\times 2$ (or farthest point sampling)
Conv2 |  $3\times 3$ conv. (or PointConv) 128 w/ ReLU
Subsampling2 |  max-pooling with stride $2\times 2$ (or farthest point sampling)
Conv3 |  $3\times 3$ conv. (or PointConv) 128 w/ ReLU
Conv4 |  $3\times 3$ conv. (or PointConv) 128 w/ ReLU
Pooling | global average pooling
FC-10 | fully connected layer
Softmax layer
Table 1: The general network architecture for MNIST experiments. Every
convolutional layer is followed by a ReLU layer.

To convert a 2D raster image with the resolution of $m\times n$ to a point
cloud, we generate a point for each pixel with normalized coordinates
$p_{i}(x,y)=(\frac{m_{i}}{m},\frac{n_{i}}{n})\in R^{2}$ as its spatial
location. Normalization constrains the input range of each coordinate for the
weight function to $[0,1]$. Thus, images of different scales are converted to
point clouds with different sampling densities. The original RGB feature is
also normalized to $[0,1]$.

Three 2D CNN baselines are considered. The first one is exactly the same
structure as the PointConv network. The other two utilize the Deformable CNN
[9], and CapsNet [40] respectively. Both claimed to be robust to
scale/rotation changes. Every baseline is tuned to the optimal performance
based on the validation accuracy.

Robustness to Scaling The first experiment we conduct is to train with images
of limited known scales and test on larger/smaller objects outside of the
known scales. To construct the training set, all MNIST images are rescaled to
$20\times 20$, $28\times 28$, and $36\times 36$, respectively. The validation
set is built by rescaling the original test images to $24\times 24$ and
$32\times 32$. We trained all baseline models on this new MNIST dataset, and
tuned parameters on the validation set. Test accuracies are measured on images
with $34\times 34$, $38\times 38$, $44\times 44$, $56\times 56$, $72\times
72$, $18\times 18$, $14\times 14$, and $10\times 10$ resolutions, which
creates a discrepancy with training.

Results are shown in Table 2 and 3. PC-2D sampling is generally inferior to
the furthest point subsampling. We note several takeaways:

  * •

Naive kNN-based PointConv is less robust to scale changes than conventional
CNN. On most out-of-sample scales it does not generalize as well as the 2D
CNNs.

  * •

Cubic polynomials with Sobolev regularization outperforms MLP with any
activation at most scales. Sobolev regularization improves robustness
especially at small scales.

  * •

$\epsilon$-ball neighborhood is generally more robust than kNN neighborhood,
especially at scales significantly different from the training.

  * •

With appropriate design e.g. cubic polynomial WeightNet and $\epsilon$-ball
neighborhood, PointConv is significantly more robust to scale changes than
traditional 2D CNN.

This builds a case to use PointConv in 2D spaces with an $\epsilon$-ball
neighborhood, and a cubic polynomial WeightNet with Sobolev regularizations.
Especially, the significantly improved robustness w.r.t. 2D CNNs may justify
the use of PointConv even for 2D raster images, if robustness is of concern.

# NBR | Neighborhood | WeightNet architecture | $34\times 34$ | $38\times 38$ | $44\times 44$ | $56\times 56$ | $72\times 72$ | $18\times 18$ | $14\times 14$ | $10\times 10$
---|---|---|---|---|---|---|---|---|---|---
$16$ |  $\epsilon$-ball | cubic P + Sobolev Reg. | $95.37\%$ | $94.35\%$ | $\mathbf{94.56}\%$ | $\mathbf{94.01}\%$ | $\mathbf{93.23}\%$ | $\mathbf{95.82}\%$ | $\mathbf{96.15}\%$ | $47.4\%$
$9$ |  $\epsilon$-ball | cubic P + Sobolev Reg. | $91.96\%$ | $93.31\%$ | $91.00\%$ | $92.20\%$ | $91.04\%$ | $95.51\%$ | $95.27\%$ | $\mathbf{68.83}\%$
$9$ | kNN | cubic P + Sobolev Reg. | $93.78\%$ | $93.84\%$ | $90.21\%$ | $88.45\%$ | $69.41\%$ | $92.79\%$ | $84.56\%$ | $54.67\%$
$9$ | kNN | cubic P | $90.31\%$ | $94.35\%$ | $89.77\%$ | $90.42\%$ | $68.46\%$ | $91.37\%$ | $81.73\%$ | $24.02\%$
$9$ | kNN | MLP w/ Sine | $91.35\%$ | $92.91\%$ | $84.69\%$ | $79.45\%$ | $66.29\%$ | $86.06\%$ | $74.61\%$ | $31.6\%$
$9$ | kNN | MLP w/ SeLU | $91.77\%$ | $90.52\%$ | $87.5\%$ | $82.66\%$ | $69.5\%$ | $91.74\%$ | $82.9\%$ | $38.18\%$
$9$ | kNN | MLP w/ Leaky ReLU | $95.57\%$ | $88.89\%$ | $80.69\%$ | $49.8\%$ | $37.89\%$ | $94.61\%$ | $81.22\%$ | $26.85\%$
$9$ | kNN | MLP w/ ReLU | $71.38\%$ | $75.04\%$ | $75.41\%$ | $51.33\%$ | $18.85\%$ | $69.23\%$ | $59.54\%$ | $29.88\%$
CNN | $96.30\%$ | $95.68\%$ | $89.19\%$ | $51.23\%$ | $25.77\%$ | $75.6\%$ | $24.25\%$ | $11.2\%$
Deformable CNN | $91.31\%$ | $16.05\%$ | $17.99\%$ | $11.56\%$ | $11.35\%$ | $74.40\%$ | $28.18\%$ | $14.74\%$
CapsNet | $\mathbf{98.53}\%$ | $\mathbf{97.52}\%$ | $93.28\%$ | $43.25\%$ | $16.50\%$ | $80.07\%$ | $21.41\%$ | $8.65\%$
Table 2: MNIST performance comparison across different scales under the setting of farthest subsampling. P is short for polynomials, and NBR is short for neighbor. The first row indicates the resolution of test images. # NBR | Neighborhood | WeightNet architecture | $34\times 34$ | $38\times 38$ | $44\times 44$ | $56\times 56$ | $72\times 72$ | $18\times 18$ | $14\times 14$ | $10\times 10$
---|---|---|---|---|---|---|---|---|---|---
$16$ |  $\epsilon$-ball | cubic P + Sobolev Reg. | $95.83\%$ | $96.21\%$ | $\mathbf{97.84}\%$ | $\mathbf{97.92}\%$ | $\mathbf{98.23}\%$ | $90.8\%$ | $64.47\%$ | $21.78\%$
$9$ |  $\epsilon$-ball | cubic P + Sobolev Reg. | $94.76\%$ | $95.58\%$ | $96.56\%$ | $96.89\%$ | $97.27\%$ | $\mathbf{93.51}\%$ | $\mathbf{88.20}\%$ | $\mathbf{23.59}\%$
$9$ | kNN | cubic P + Sobolev Reg. | $97.64\%$ | $96.83\%$ | $95.92\%$ | $54.06\%$ | $23.99\%$ | $53.84\%$ | $17.98\%$ | $10.11\%$
$9$ | kNN | cubic P | $97.85\%$ | $97.31\%$ | $95.38\%$ | $42.71\%$ | $13.77\%$ | $14.77\%$ | $12.02\%$ | $7.28\%$
$9$ | kNN | MLP w/ Sine | $95.76\%$ | $94.35\%$ | $94.47\%$ | $47.26\%$ | $19.02\%$ | $76.5\%$ | $30.01\%$ | $10.86\%$
$9$ | kNN | MLP w/ SeLU | $92.03\%$ | $82.49\%$ | $56.90\%$ | $17.09\%$ | $6.01\%$ | $33.78\%$ | $10.51\%$ | $11.59\%$
$9$ | kNN | MLP w/ Leaky ReLU | $66.27\%$ | $24.39\%$ | $13.69\%$ | $10.11\%$ | $10.1\%$ | $65.66\%$ | $16.50\%$ | $8.11\%$
$9$ | kNN | MLP w/ ReLU | $16.54\%$ | $16.66\%$ | $11.35\%$ | $11.35\%$ | $11.35\%$ | $10.63\%$ | $7.83\%$ | $6.43\%$
CNN | $96.30\%$ | $95.68\%$ | $89.19\%$ | $51.23\%$ | $25.77\%$ | $75.6\%$ | $24.25\%$ | $11.2\%$
Deformable CNN | $91.31\%$ | $16.05\%$ | $17.99\%$ | $11.56\%$ | $11.35\%$ | $74.40\%$ | $28.18\%$ | $14.74\%$
CapsNet | $\mathbf{98.53}\%$ | $\mathbf{97.52}\%$ | $93.28\%$ | $43.25\%$ | $16.50\%$ | $80.07\%$ | $21.41\%$ | $8.65\%$
Table 3: MNIST performance comparison across different scales under the setting of PC-2D subsampling. P is short for polynomials, and NBR is short for neighbor. The first row indicates the resolution of test images. # NBR | Neighborhood | WeightNet architecture | $+10\degree$ | $-10\degree$ | $+20\degree$ | $-20\degree$ | $+40\degree$ | $-40\degree$
---|---|---|---|---|---|---|---|---
$12$ |  $\epsilon$-ball | cubic P + Sobolev Reg. | $96.93\%$ | $96.63\%$ | $96.2\%$ | $95.86\%$ | $85.27\%$ | $\mathbf{85.51}\%$
$9$ |  $\epsilon$-ball | cubic P + Sobolev Reg. | $95.52\%$ | $95.58\%$ | $94.63\%$ | $94.55\%$ | $81.27\%$ | $84.27\%$
$9$ | kNN | cubic P + Sobolev Reg. | $98.11\%$ | $97.68\%$ | $95.96\%$ | $97.2\%$ | $64.79\%$ | $63.71\%$
$9$ | kNN | cubic P | $98.50\%$ | $98.37\%$ | $95.52\%$ | $97.45\%$ | $56.23\%$ | $61.75\%$
$9$ | kNN | MLP w/ Sine | $98.11\%$ | $97.65\%$ | $93.84\%$ | $93.95\%$ | $20.21\%$ | $29.27\%$
$9$ | kNN | MLP w/ SeLU | $97.75\%$ | $97.56\%$ | $43.27\%$ | $94.66\%$ | $10.44\%$ | $11.62\%$
$9$ | kNN | MLP w/ Leaky ReLU | $98.09\%$ | $97.56\%$ | $92.34\%$ | $95.71\%$ | $36.16\%$ | $35.49\%$
$9$ | kNN | MLP w/ ReLU | $98.03\%$ | $97.62\%$ | $92.65\%$ | $95.53\%$ | $37.03\%$ | $34.39\%$
CNN | $96.47\%$ | $96.9\%$ | $95.06\%$ | $95.51\%$ | $75.71\%$ | $74.28\%$
Deformable CNN | $98.21\%$ | $98.60\%$ | $96.59\%$ | $97.60\%$ | $80.82\%$ | $81.01\%$
CapsNet | $\mathbf{99.8}\%$ | $\mathbf{99.9}\%$ | $\mathbf{99.6}\%$ | $\mathbf{99.5}\%$ | $\mathbf{92.5}\%$ | $83.8\%$
Table 4: MNIST performance comparison with different rotations under the
setting of farthest subsampling. P stands for polynomials, and NBR stands for
neighbor. The first row indicates the rotation angles of test images.

Robustness to Rotations The next experiment we conduct is to train with
objects of limited known rotations and test on objects with various rotated
angles. We define counter clockwise as the positive rotation direction. The
training set is constructed through rotating the original $28\times 28$
training images (or point clouds) by $-15^{\circ}$, $0^{\circ}$, and
$+15^{\circ}$ around the center. We rotate the original testing images (or
point clouds) by $-15^{\circ}$ and $+15^{\circ}$ to create the validation set.
All parameters are tuned on the validation dataset. Test accuracies are
measured on the rotation angles of $\pm 10^{\circ}$, $\pm 20^{\circ}$, and
$\pm 40^{\circ}$.

Trends on results shown in Table 4 are similar to those mentioned in the
previous subsection, e.g. $\epsilon$-ball and cubic polynomials outperform kNN
and MLPs. However, here the regular ReLU seems to show the most robustness
among the activation functions, although cubic polynomials still outperform
all the MLP-based WeightNets. With $\epsilon$-ball and cubic polynomials,
PointConv is again significantly more robust than regular CNNs. Interestingly
CapsNet is able to show better rotation robustness than PointConv. Given that
CapsNet is orthogonal to PointConv, it maybe possible to combine them in
future work.

Layer name | Layer description
---|---
Conv1 |  $3\times 3$ conv. (or PointConv) 64 w/ BN & ReLU
Subsampling1 |  max-pooling with stride $2\times 2$ (or farthest point sampling)
Conv2 |  $3\times 3$ conv. (or PointConv) 128 w/ BN & ReLU
Conv3 |  $3\times 3$ conv. (or PointConv) 128 w/ BN & ReLU
Subsampling2 |  max-pooling with stride $2\times 2$ (or farthest point sampling)
Conv4 |  $3\times 3$ conv. (or PointConv) 256 w/ BN & ReLU
Conv5 |  $3\times 3$ conv. (or PointConv) 256 w/ BN & ReLU
Subsampling3 |  max-pooling with stride $2\times 2$ (or farthest point sampling)
Conv6 |  $3\times 3$ conv. (or PointConv) 512 w/ BN & ReLU
Conv7 |  $3\times 3$ conv. (or PointConv) 512 w/ BN & ReLU
Pooling | global average pooling
FC-10 | fully connected layer
Softmax layer
Table 5: The general network architecture for CIFAR-10 experiments. BN stands
for batch normalization. Every BN layer is followed by a ReLU layer.

###  4.2 CIFAR-10

In CIFAR-10 [22], there are $60,000$ RGB images in $10$ classes in the
training set, and $10,000$ images in the test set. The original size of each
image is $32\times 32$. The general architecture of all baselines are shown in
Table 5. We adopt the same hyperparameters and preprocessing procedures as
detailed in section 4.1, besides the Sobolev norm regularizer. The $\epsilon$
is fixed to $0.05$ for Conv1 in Table 5, $0.1$ for Conv2 and Conv3, $0.2$ for
Conv4 and Conv5, and $0.5$ for Conv6 as well as Conv7. The numbers of output
points from FPS for Subsampling1, Subsampling2, and Subsampling3 layer in
Table 5 are $256$, $64$, and $16$, respectively. The coefficient of the
Sobolev norm regularization is set to one of $\\{10^{-6},10^{-5},10^{-4}\\}$
for our proposed approach. We does not adopt PC-2D subsampling since it is
experimentally proven not robust in 4.1.

Two 2D CNN baselines are considered. The first one is the traditional CNN as
shown in Table 5, and the other one is Deformable CNN [9] which has the exact
architecture except for that the last four convolutional layer are
deformable.We did not including CapsNet [40] in this experiment, since it has
no pooling layers and performs poorly on this dataset.

Robustness to Scaling The first experiment tests robustness with respect to
scaling. The original training set is augmented to three different
resolutions, which are $24\times 24$, $32\times 32$, and $40\times 40$,
respectively. The validation resolutions are $28\times 28$, and $36\times 36$.
We trained all baseline models on this new CIFAR-10 dataset, and tuned
hyperparameters on the validation set.

Results are shown in Table 6. We note several takeaways:

  * •

Naive kNN-based PointConv is less robust to scale changes than conventional
CNN. On most out-of-sample scales it does not generalize as well as the 2D
CNNs. Even for the resolution $32\times 32$, the generalization is less well
than traditional CNNs. This is interesting since we have verified that with
the same architecture PointConv is able to match CNN performance if trained
only under a single resolution, which might show that further work is needed
for PointConv to be robust to mixing resolutions in training.

  * •

Cubic polynomials outperform MLP with any activation at most scales. Sobolev
regularization does not universally improves the robustness against scaling on
this dataset.

  * •

$\epsilon$-ball neighborhood is generally significantly more robust than kNN
neighborhood when testing scales are significantly different from the
training.

  * •

With appropriate design e.g. cubic polynomial WeightNet and an $\epsilon$-ball
neighborhood, PointConv is significantly more robust than traditional 2D CNN
when the testings scales that are significantly larger/smaller than training
scales.

# NBR | Neighborhood | WeightNet architecture | $32\times 32$ | $48\times 48$ | $60\times 60$ | $76\times 76$ | $88\times 88$ | $22\times 22$ | $18\times 18$ | $16\times 16$
---|---|---|---|---|---|---|---|---|---|---
$16$ |  $\epsilon$-ball | cubic P + Sobolev Reg. | $73.43\%$ | $70.24\%$ | $\mathbf{68.56}\%$ | $\mathbf{65.7}\%$ | $\mathbf{65.78}\%$ | $66.15\%$ | $\mathbf{67.12}\%$ | $\mathbf{71.89}\%$
$9$ |  $\epsilon$-ball | cubic P + Sobolev Reg. | $70.56\%$ | $68.00\%$ | $67.15\%$ | $64.41\%$ | $65.31\%$ | $59.89\%$ | $63.36\%$ | $66.41\%$
$9$ | kNN | cubic P + Sobolev Reg. | $78.59\%$ | $61.67\%$ | $46.32\%$ | $32.48\%$ | $24.91\%$ | $64.67\%$ | $52.50\%$ | $59.65\%$
$9$ | kNN | cubic P | $78.09\%$ | $61.87\%$ | $47.12\%$ | $30.91\%$ | $27.63\%$ | $63.17\%$ | $54.48\%$ | $59.65\%$
$9$ | kNN | MLP w/ Sine | $71.29\%$ | $39.62\%$ | $30.58\%$ | $26.69\%$ | $25.17\%$ | $46.68\%$ | $21.99\%$ | $23.81\%$
$9$ | kNN | MLP w/ SeLU | $72.04\%$ | $47.27\%$ | $37.48\%$ | $34.81\%$ | $34.54\%$ | $35.21\%$ | $18.51\%$ | $23.80\%$
$9$ | kNN | MLP w/ Leaky ReLU | $76.06\%$ | $16.85\%$ | $9.85\%$ | $11.37\%$ | $11.21\%$ | $41.56\%$ | $30.11\%$ | $27.47\%$
$9$ | kNN | MLP w/ ReLU | $69.58\%$ | $20.81\%$ | $15.00\%$ | $12.01\%$ | $12.36\%$ | $38.89\%$ | $27.17\%$ | $25.32\%$
CNN | $\mathbf{88.47}\%$ | $\mathbf{79.21}\%$ | $59.21\%$ | $38.43\%$ | $27.13\%$ | $\mathbf{69.11}\%$ | $44.99\%$ | $39.80\%$
Deformable CNN | $82.82\%$ | $72.03\%$ | $52.07\%$ | $31.91\%$ | $25.68\%$ | $60.20\%$ | $51.20\%$ | $45.67\%$
Table 6: CIFAR-10 performance comparison across different scales under the setting of farthest subsampling. P is short for polynomials, and NBR is short for neighbor. The first row indicates the resolution of test images. # NBR | Neighborhood | WeightNet architecture | $0\degree$ | $+10\degree$ | $-10\degree$ | $+20\degree$ | $-20\degree$ | $+40\degree$ | $-40\degree$
---|---|---|---|---|---|---|---|---|---
$12$ |  $\epsilon$-ball | cubic P + Sobolev Reg. | $71.26\%$ | $67.63\%$ | $67.55\%$ | $64.58\%$ | $65.36\%$ | $40.13\%$ | $42.64\%$
$9$ |  $\epsilon$-ball | cubic P + Sobolev Reg. | $69.72\%$ | $66.24\%$ | $66.56\%$ | $63.13\%$ | $63.71\%$ | $39.42\%$ | $39.42\%$
$9$ | kNN | cubic P + Sobolev Reg. | $75.57\%$ | $62.95\%$ | $60.12\%$ | $59.96\%$ | $54.35\%$ | $42.94\%$ | $39.13\%$
$9$ | kNN | cubic P | $75.94\%$ | $62.27\%$ | $59.12\%$ | $57.18\%$ | $54.68\%$ | $38.85\%$ | $37.61\%$
$9$ | kNN | MLP w/ Sine | $68.32\%$ | $45.11\%$ | $44.11\%$ | $35.92\%$ | $35.52\%$ | $15.35\%$ | $16.34\%$
$9$ | kNN | MLP w/ SeLU | $69.04\%$ | $43.81\%$ | $41.26\%$ | $40.83\%$ | $37.97\%$ | $21.53\%$ | $18.28\%$
$9$ | kNN | MLP w/ Leaky ReLU | $78.01\%$ | $65.68\%$ | $64.84\%$ | $59.22\%$ | $57.85\%$ | $34.67\%$ | $34.14\%$
$9$ | kNN | MLP w/ ReLU | $76.79\%$ | $64.57\%$ | $62.25\%$ | $57.43\%$ | $55.21\%$ | $31.07\%$ | $33.98\%$
CNN | $\mathbf{86.61}\%$ | $83.72\%$ | $\mathbf{84.48}\%$ | $\mathbf{78.03}\%$ | $78.25\%$ | $45.71\%$ | $46.14\%$
Deformable CNN | $86.53\%$ | $\mathbf{83.74}\%$ | $83.96\%$ | $77.69\%$ | $\mathbf{78.31}\%$ | $\mathbf{47.21}\%$ | $\mathbf{47.72}\%$
Table 7: CIFAR-10 performance comparison with different rotations under the
setting of farthest subsampling. P stands for polynomials, and NBR stands for
neighbor. The first row indicates the rotation angles of test images.

Robustness to Rotations The next experiment we conduct is to train baselines
with images with a few predefined rotations, and test them on images with
various rotated angles. The counter clockwise direction is defined as the
positive direction. To construct the training set, we rotate the original
$32\times 32$ training images (or point clouds) by $-15^{\circ}$, $0^{\circ}$,
and $+15^{\circ}$ around the center. The validation set is created through
rotating the original testing images (or point clouds) by $-15^{\circ}$ and
$+15^{\circ}$. All parameters are tuned on the validation dataset. Test
accuracies are measured on the rotation angles of $\pm 10^{\circ}$, $\pm
20^{\circ}$, and $\pm 40^{\circ}$.

The corresponding results are shown in Table 7. We observe that
$\epsilon$-ball still outperforms kNN in all nonzero rotations but
underperform it at no rotation. However, Leaky ReLU is overall comparable with
cubic polynomial with Sobolev regularization as the best approach, and SeLU
performed significantly worse. Besides, PointConv is generally significantly
less robust as regular or deformable CNNs in this case, showing that more work
needs to be done in terms of robustness to rotations in 2D in more complex
datasets.

# layers | MLP input | activation | NBR setting |  rotation augmentation | $100k$ | $60k$ | $40k$ | $20k$ | $10k$
---|---|---|---|---|---|---|---|---|---
16 |  VI + $(x,y,z)$ | ReLU | KNN | Y | $\mathbf{68.2}$ | $\mathbf{64.4}$ | $\mathbf{63.0}$ | $\mathbf{57.6}$ | $45.4$
16 | VI | ReLU | KNN | Y | $63.3$ | $60.7$ | $59.7$ | ${55.0}$ | $44.7$
16 | VI | SeLU | KNN | Y | ${63.7}$ | ${61.5}$ | $57.7$ | $53.1$ | $40.2$
16 | VI | Cubic First Block | KNN | Y | $63.5$ | $61.4$ | ${60.2}$ | $54.0$ | $42.0$
|  | \+ ReLU in others |  |  |  |  |  |  |
16 | $(x,y,z)$ | ReLU | KNN | Y | $61.7$ | $58.7$ | $53.4$ | $34.6$ | $17.8$
16 | VI | ReLU | KNN | N | $60.4$ | $58.6$ | $57.8$ | $54.2$ | $46.3$
16 | $(x,y,z)$ | ReLU | KNN | N | $56.4$ | $54.0$ | $51.2$ | $40.6$ | $27.4$
16 | VI | ReLU |  $\epsilon$-ball | Y | $61.61$ | $58.6$ | $58.0$ | $52.3$ | $40.6$
16 | $(x,y,z)$ | ReLU |  $\epsilon$-ball | Y | $48.9$ | $43.3$ | $39.7$ | $30.6$ | $20.7$
16 | surface normal | ReLU | KNN | Y | $60.2$ | $57.5$ | $56.8$ | $54.8$ | $50.9$
|  \+ $(x,y,z)$ |  |  |  |  |  |  |  |
16 | surface normal | ReLU | KNN | Y | $53.1$ | $50.6$ | $50.2$ | $47.6$ | $43.3$
4 |  VI + $(x,y,z)$ | ReLU | KNN | Y | $64.5$ | $61.3$ | $60.6$ | $57.3$ | $\mathbf{51.2}$
4 | VI | ReLU | KNN | Y | $61.0$ | $58.8$ | $57.5$ | $50.8$ | $39.4$
4 | $(x,y,z)$ | ReLU | KNN | Y | $55.3$ | $53.3$ | $47.0$ | $30.7$ | $16.1$
4 | VI | ReLU |  $\epsilon$-ball | Y | $59.2$ | $57.5$ | $55.12$ | $44.8$ | $31.1$
Table 8: Performance results (mIoU,%) for the ScanNet dataset. The first
column shows the configurations of the approach, and the top row contains the
number of subsampled points. The default number of neighbors is $8$, and the
default activation for weight functions is ReLU.

###  4.3 ScanNet

We conduct 3D semantic scene segmentation on the ScanNet v2 [8] dataset. We
use the official split with $1,201$ scenes for training and $312$ for
validation.

We implemented 2 PointConv architectures. One is the 4-layer network in [60],
the second one is the 16-layer PointConv network that achieved $66.6\%$ on the
ScanNet testing set. Network architectures are provided by the authors. Our
main results are reported on the ScanNet validation set as the benchmark
organizers do not allow ablation studies on the testing set.

We adopt regular subsampling [48] for feature encoding layers with grid sizes
$0.05$, $0.1$, $0.2$, and $0.4$ (in meter). $\epsilon$ is set to be
$\frac{1}{1.3}$ of the grid size for the corresponding subsampling layer. We
enumerated $\epsilon$ in
$\\{\frac{1}{1.0},\frac{1}{1.1},\frac{1}{1.2},\frac{1}{1.3},\frac{1}{1.4},\frac{1}{1.5}\\}$,
and it turned out the network is not sensitive to those choices (see
supplementary for experiments). The surface normal for a subsampled point is
computed through averaging all surface normals of its corresponding grid.
During training, we randomly subsample $100,000$ points from each point cloud
for both the training and validation sets, and the mini-batch size is set to
be $3$. The learning rate is set to $10^{-3}$, with a decay multiplier of
$\frac{1}{2}$ every $40$ epochs. Moreover, the rotation augmentation is
applied by randomly rotating every mini-batch with an arbitrary angle in
$[0,2\pi)$, as in [60].

To study the robustness to scales for all baselines, we re-subsample each
validation point cloud to less than $100k$ — $\\{60k,40k,20,10k\\}$. This is
equivalent to downsampling the image in the 2D space as it increases the size
of KNN neighborhoods with a fixed $K$. Also, each sub-sampled point cloud is
further rotated with $4$ different predefined angles around $z$-axis —
$\\{0\degree,90\degree,180\degree,270\degree\\}$. Such operations could
significantly change both local scales and rotations. We also evaluate the
performance when the rotation augmentation is not applied during training. We
found performance variation between different rotation angles to be less than
$1\%$ (see supplementary), hence the mIoUs averaged from all angles are
reported. Experiments are performed with the proposed VI descriptor, as well
as configurations that are promising from 2D experiments: $\epsilon$-ball,
cubic polynomial WeightNet, and SeLU activation.

Results are shown in Table 8, which shows that the proposed VI descriptor
significantly improved the performance as well as robustness under every
setting. Especially, it is significantly more robust to input downsampling
than the $(x,y,z)$ coordinates as input. For example, at $10k$ testing points
(reflecting $10x$ downsampling from the training), the VI descriptors still
maintain a $44.7\%$ accuracy while the $(x,y,z)$ coordinates version has its
performance dropped to $17.8\%$, marking an improvement of $251\%$. Besides,
with VI descriptor, the need to use rotation augmentation reduced
significantly. Interestingly, rotation augmentation still improved performance
by $2\%$. We believe the main reason is that the input feature of our
framework consists of both $(x,y,z)$ coordinates and RGB colors, and thus
rotation augmentation creates more $(x,y,z)$ coordinates variations for the
training, and hence improved performance. We further conduct ablation studies
by replacing VI descriptors with surface normals. The mIoU drops by
$8\%-10\%$, which indicates that VI is a better representation of local
geometry than the commonly used surface normal.

Finally, when we combined the VI features with $(x,y,z)$ inputs, it generated
the best performance of all – $68.2\%$ on the original validation set, and
better on almost all subsampled scenarios. This shows that a combination of
scale-invariant, rotation-invariant and non-invariant features is beneficial,
potentially letting the network choose the invariance it requires.
Furthermore, on the test set, we achieved comparable mIoU with KPConv [49],
which is the current state-of-the-art among point-based approaches (Table 9).
Note that PointConv [60] has significantly less parameters than KPConv [49],
and KNN used in PointConv is significantly more efficient than the
$\epsilon$-ball in KPConv.

Otherwise, none of the other tested choices were helpful, including
$\epsilon$-ball, SeLU or cubic polynomial. Our takeaway is that the proposed
VI descriptor is very powerful and improved robustness significantly w.r.t.
neighborhood sizes, hence, none of the other improvements is needed.

From our experience, it is very difficult to find a good set of parameters for
$\epsilon$-ball in $3D$. It also slows down the algorithm because the non-
uniform neighborhood size is not easily amenable for tensor computation. Hence
not needing to use it is a significant bonus. Nevertheless, $\epsilon$-ball
neighborhoods are still very useful in $2D$ settings, where locating them is
much easier and the VI descriptor is not applicable.

Method | mIoU(%)
---|---
PointNet++ [37] | $33.9$
SPLATNet [45] | $39.3$
TangentConv [47] | $40.9$
PointCNN [27] | $45.8$
PointASNL [65] | $63.0$
PointConv [60] | $66.6$
KPConv [49] | $\mathbf{68.4}$
VI-PointConv (ours) | $67.6$
Table 9: Semantic Scene Segmentation results for point-based approaches on the ScanNet test set Method |  mIoUs(%) |  road |  sidewalk |  parking |  other-ground |  building |  car |  truck |  bicycle |  motorcycle |  other-vehicle |  vegetation |  trunk |  terrain |  person |  bicyclist |  motorcyclist |  fence |  pole |  traffic-sign
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
PointNet[35] | $14.6$ | $61.6$ | $35.7$ | $15.8$ | $1.4$ | $41.4$ | $46.3$ | $0.1$ | $1.3$ | $0.3$ | $0.8$ | $31.0$ | $4.6$ | $17.6$ | $0.2$ | $0.2$ | $0.0$ | $12.9$ | $2.4$ | $3.7$
SPG[23] | $17.4$ | $45.0$ | $28.5$ | $0.6$ | $0.6$ | $64.3$ | $49.3$ | $0.1$ | $0.2$ | $0.2$ | $0.8$ | $48.9$ | $27.2$ | $24.6$ | $0.3$ | $2.7$ | $0.1$ | $20.8$ | $15.9$ | $0.8$
SPLATNet[45] | $18.4$ | $64.6$ | $39.1$ | $0.4$ | $0.0$ | $58.3$ | $58.2$ | $0.0$ | $0.0$ | $0.0$ | $0.0$ | $71.1$ | $9.9$ | $19.3$ | $0.0$ | $0.0$ | $0.0$ | $23.1$ | $5.6$ | $0.0$
PointNet++[37] | $20.1$ | $72.0$ | $41.8$ | $18.7$ | $5.6$ | $62.3$ | $53.7$ | $0.9$ | $1.9$ | $0.2$ | $0.2$ | $46.5$ | $13.8$ | $30.0$ | $0.9$ | $1.0$ | $0.0$ | $16.9$ | $6.0$ | $8.9$
TangentConv[47] | $40.9$ | $83.9$ | $63.9$ | $33.4$ | $15.4$ | $83.4$ | $90.8$ | $15.2$ | $2.7$ | $16.5$ | $12.1$ | $79.5$ | $49.3$ | $58.1$ | $23.0$ | $28.4$ | $8.1$ | $49.0$ | $35.8$ | $28.5$
PointConv[60] | $53.0$ | $86.2$ | $68.6$ | $57.7$ | $16.0$ | $89.9$ | $94.2$ | $30.2$ | $29.5$ | $33.9$ | $30.5$ | $78.9$ | $60.8$ | $63.7$ | $48.8$ | $45.7$ | $20.4$ | $59.9$ | $53.4$ | $38.6$
RandLA-Net[15] | $53.9$ | $\mathbf{90.7}$ | $\mathbf{73.7}$ | $60.3$ | $20.4$ | $86.9$ | $94.2$ | $40.1$ | $26.0$ | $25.8$ | $38.9$ | $81.4$ | $61.3$ | $66.8$ | $49.2$ | $48.2$ | $7.2$ | $56.3$ | $49.2$ | $47.7$
KPConv[49] | $58.8$ | $88.8$ | $72.7$ | $61.3$ | $31.6$ | $90.5$ | $\mathbf{96.0}$ | $33.4$ | $30.2$ | $\mathbf{42.5}$ | $44.3$ | $\mathbf{84.8}$ | $\mathbf{69.2}$ | $\mathbf{69.1}$ | $\mathbf{61.5}$ | $\mathbf{61.6}$ | $11.8$ | $64.2$ | $56.5$ | $47.4$
VI-PConv(ours) | $\mathbf{59.6}$ | $88.8$ | $72.5$ | $\mathbf{63.5}$ | $\mathbf{32.7}$ | $\mathbf{91.4}$ | $95.9$ | $\mathbf{41.8}$ | $\mathbf{38.6}$ | $35.0$ | $\mathbf{45.7}$ | $83.9$ | $68.0$ | $66.9$ | $51.2$ | $50.1$ | $\mathbf{27.6}$ | $\mathbf{66.6}$ | $\mathbf{57.4}$ | $\mathbf{54.8}$
Table 10: Semantic Scene Segmentation results for point-based approaches on
the SemanticKITTI test set

###  4.4 SemanticKITTI

We also evaluate the semantic segmentation performance on SemanticKITTI [2]
(single scan), which consists of $43,552$ point clouds sampled from $22$
sequences in driving scenes. Each point cloud contains $10-13k$ points,
collected by a single Velodyne HDL-64E laser scanner, spanning up to
$160\times 160\times 20$ meters in 3D space. The officially training set
includes $19,130$ scans (sequences $00-07$ and $09-10$), and there are $4,071$
scans (sequence $08$) for validation. For each 3D point, only $(x,y,z)$
coordinate is given without any color information. It is a challenging dataset
because faraway points are sparser in LIDAR scans.

We adopt the exact same $16$-layer architecture as showed at the first row of
Table 8, together with the mini-batch size of 16. The initial learning rate is
$10^{-3}$, and it is decayed by half every $6$ epochs. We do not integrate
with any subsampling preprocessing. As reported in Table 10, we achieve the
state-of-the-art semantic segmentation performance among point-based
baselines, improving by $0.8\%$ over KPConv and $6.6\%$ over standard
PointConv, which demonstrate the effectiveness of VI descriptor for PointConv
[60].

##  5 Conclusion

This paper empirically studies several strategies to improve the robustness
for point cloud convolution with PointConv [60]. We have found two
combinations to be effective. In 2D images, using an $\epsilon$-ball
neighborhood with cubic polynomial weight functions achieved the highest
robustness, and outperformed 2D CNNs for MNIST dataset. In 3D images, our
novel viewpoint-invariant descriptor, when used instead of, or in combination
with the 3D coordinates, significantly improved the performance and robustness
of PointConv networks and achieved state-of-the-art. Our results show that kNN
is still a viable neighborhood choice if the input location features are
robust to neighborhood sizes.

## References

  * [1] Matan Atzmon, Haggai Maron, and Yaron Lipman.  Point convolutional neural networks by extension operators.  international conference on computer graphics and interactive techniques, 2018.
  * [2] J. Behley, M. Garbade, A. Milioto, J. Quenzel, S. Behnke, C. Stachniss, and J. Gall.  SemanticKITTI: A Dataset for Semantic Scene Understanding of LiDAR Sequences.  In Proc. of the IEEE/CVF International Conf. on Computer Vision (ICCV), 2019.
  * [3] Arunkumar Byravan and Dieter Fox.  Se3-nets: Learning rigid body motion using deep neural networks.  In International Conference on Robot and Automation, 2017.
  * [4] Gong Cheng, Peicheng Zhou, and Junwei Han.  Rifd-cnn: Rotation-invariant and fisher discriminative convolutional neural networks for object detection.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
  * [5] Christopher Choy, JunYoung Gwak, and Silvio Savarese.  4d spatio-temporal convnets: Minkowski convolutional neural networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3075–3084, 2019.
  * [6] Taco Cohen and Max Welling.  Group equivariant convolutional networks.  In International Conference on Machine Learning, pages 2990–2999, 2016.
  * [7] Taco S Cohen and Max Welling.  Steerable cnns.  In ICLR, 2017.
  * [8] Angela Dai, Angel X. Chang, Manolis Savva, Maciej Halber, Thomas Funkhouser, and Matthias Nießner.  Scannet: Richly-annotated 3d reconstructions of indoor scenes.  In Proc. Computer Vision and Pattern Recognition (CVPR), IEEE, 2017\.
  * [9] Jifeng Dai, Haozhi Qi, Yuwen Xiong, Yi Li, Guodong Zhang, Han Hu, and Yichen Wei.  Deformable convolutional networks.  In ICCV, 2017.
  * [10] Benjamin Graham, Martin Engelcke, and Laurens van der Maaten.  3d semantic segmentation with submanifold sparse convolutional networks.  CVPR, 2018.
  * [11] Fabian Groh, Patrick Wieschollek, and Hendrik P. A. Lensch.  Flex-convolution (million-scale point-cloud learning beyond grid-worlds).  In Asian Conference on Computer Vision (ACCV), Dezember 2018.
  * [12] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Spatial pyramid pooling in deep convolutional networks for visual recognition.  In ECCV. 2014.
  * [13] João F. Henriques and Andrea Vedaldi.  Warped convolutions: Efficient invariance to spatial transformations.  In Proceedings of the International Conference on Machine Learning (ICML), 2017.
  * [14] P. Hermosilla, T. Ritschel, P-P Vazquez, A. Vinacua, and T. Ropinski.  Monte carlo convolution for learning on non-uniformly sampled point clouds.  ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2018), 37(6), 2018.
  * [15] Qingyong Hu, Bo Yang, Linhai Xie, Stefano Rosa, Yulan Guo, Zhihua Wang, Niki Trigoni, and Andrew Markham.  Randla-net: Efficient semantic segmentation of large-scale point clouds.  Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2020.
  * [16] Binh-Son Hua, Minh-Khoi Tran, and Sai-Kit Yeung.  Pointwise convolutional neural networks.  In Computer Vision and Pattern Recognition (CVPR), 2018.
  * [17] Max Jaderberg, Karen Simonyan, Andrew Zisserman, et al.  Spatial transformer networks.  In NIPS, pages 2017–2025, 2015.
  * [18] Xu Jia, Bert De Brabandere, Tinne Tuytelaars, and Luc V Gool.  Dynamic filter networks.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 667–675. Curran Associates, Inc., 2016.
  * [19] Yonghyun Kim, Bong-Nam Kang, and Daijin Kim.  San: Learning relationship between convolutional features for multi-scale object detection.  In ECCV, 2018.
  * [20] Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter.  Self-normalizing neural networks.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 971–980. Curran Associates, Inc., 2017.
  * [21] Artem Komarichev, Zichun Zhong, and Jing Hua.  A-cnn: Annularly convolutional neural networks on point clouds.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
  * [22] A. Krizhevsky.  Learning multiple layers of features from tiny images.  In Tech Report, 2009.
  * [23] L. Landrieu and M. Simonovsky.  Large-scale point cloud semantic segmentation with superpoint graphs.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4558–4567, 2018.
  * [24] Dmitry Laptev, Nikolay Savinov, Joachim M Buhmann, and Marc Pollefeys.  Ti-pooling: transformation-invariant pooling for feature learning in convolutional neural networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 289–297, 2016.
  * [25] Yann LeCun, Corinna Cortes, and Christopher J.C. Burges.  The mnist database of handwritten digits.  1998\.
  * [26] Jiaxin Li, Ben M. Chen, and Gim Hee Lee.  So-net: Self-organizing network for point cloud analysis.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [27] Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen.  Pointcnn: Convolution on x-transformed points.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 820–830. Curran Associates, Inc., 2018.
  * [28] Chen-Hsuan Lin and Simon Lucey.  Inverse compositional spatial transformer networks.  In IEEE Conf. Comput. Vis. Pattern Recog., 2017.
  * [29] Tsung-Yi Lin, Piotr Dollar, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In CVPR, 2017.
  * [30] Yiqun Lin, Zizheng Yan, Haibin Huang, Dong Du, Ligang Liu, Shuguang Cui, and Xiaoguang Han.  Fpconv: Learning local flattening for point convolution.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [31] Xinhai Liu, Zhizhong Han, Yu-Shen Liu, and Matthias Zwicker.  Point2sequence: Learning the shape representation of 3d point clouds with an attention-based sequence to sequence network.  In Thirty-Third AAAI Conference on Artificial Intelligence, 2019\.
  * [32] Andrew L. Maas, Awni Y. Hannun, and Andrew Y. Ng.  Rectifier nonlinearities improve neural network acoustic models.  In in ICML Workshop on Deep Learning for Audio, Speech and Language Processing, 2013.
  * [33] Daniel Maturana and Sebastian Scherer.  Voxnet: A 3d convolutional neural network for real-time object recognition.  In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 922–928. IEEE, 2015.
  * [34] Vinod Nair and Geoffrey E. Hinton.  Rectified linear units improve restricted boltzmann machines.  In Johannes Fürnkranz and Thorsten Joachims, editors, ICML, pages 807–814. Omnipress, 2010.
  * [35] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  arXiv preprint arXiv:1612.00593, 2016.
  * [36] Charles Ruizhongtai Qi, Hao Su, Matthias Nießner, Angela Dai, Mengyuan Yan, and Leonidas Guibas.  Volumetric and multi-view cnns for object classification on 3d data.  In Proc. Computer Vision and Pattern Recognition (CVPR), IEEE, 2016\.
  * [37] Charles R Qi, Li Yi, Hao Su, and Leonidas J Guibas.  Pointnet++: Deep hierarchical feature learning on point sets in a metric space.  arXiv preprint arXiv:1706.02413, 2017.
  * [38] Ali Rahimi and Benjamin Recht.  Random features for large-scale kernel machines.  In Advances in neural information processing systems, pages 1177–1184, 2008.
  * [39] Gernot Riegler, Ali Osman Ulusoy, and Andreas Geiger.  Octnet: Learning deep 3d representations at high resolutions.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017.
  * [40] Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton.  Dynamic routing between capsules.  In NIPS. 2017.
  * [41] Rahul Sawhney, Fuxin Li, Henrik I. Christensen, and Charles L. Isbell Jr.  Purely geometric scene association and retrieval - A case for macro scale 3d geometry.  CoRR, abs/1808.01343, 2018.
  * [42] Shikhar Sharma, Ryan Kiros, and Ruslan Salakhutdinov.  Action recognition using visual attention.  In NIPS Time Series Workshop. 2015.
  * [43] M. Simonovsky and N. Komodakis.  Dynamic edge-conditioned filters in convolutional neural networks on graphs.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 29–38, 2017.
  * [44] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In ICLR, 2015.
  * [45] Hang Su, Varun Jampani, Deqing Sun, Subhransu Maji, Evangelos Kalogerakis, Ming-Hsuan Yang, and Jan Kautz.  SPLATNet: Sparse lattice networks for point cloud processing.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2530–2539, 2018.
  * [46] Hang Su, Subhransu Maji, Evangelos Kalogerakis, and Erik G. Learned-Miller.  Multi-view convolutional neural networks for 3d shape recognition.  In Proc. ICCV, 2015.
  * [47] Maxim Tatarchenko*, Jaesik Park*, Vladlen Koltun, and Qian-Yi Zhou.  Tangent convolutions for dense prediction in 3D.  CVPR, 2018.
  * [48] H. Thomas, F. Goulette, J. Deschaud, B. Marcotegui, and Y. LeGall.  Semantic classification of 3d point clouds with multiscale spherical neighborhoods.  In 2018 International Conference on 3D Vision (3DV), pages 390–398, 2018.
  * [49] Hugues Thomas, Charles R. Qi, Jean-Emmanuel Deschaud, Beatriz Marcotegui, François Goulette, and Leonidas J. Guibas.  Kpconv: Flexible and deformable convolution for point clouds.  Proceedings of the IEEE International Conference on Computer Vision, 2019.
  * [50] David A van Dyk and Xiao-Li Meng.  The art of data augmentation.  Journal of Computational and Graphical Statistics, 10(1):1–50, 2001\.
  * [51] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 5998–6008. Curran Associates, Inc., 2017.
  * [52] Nitika Verma, Edmond Boyer, and Jakob Verbeek.  FeaStNet: Feature-Steered Graph Convolutions for 3D Shape Analysis.  In CVPR - IEEE Conference on Computer Vision & Pattern Recognition, pages 2598–2606, Salt Lake City, United States, June 2018. IEEE.
  * [53] G. Wahba.  Spline Models for Observational Data.  Society for Industrial and Applied Mathematics, Philadelphia, 1990.
  * [54] Fei Wang, Mengqing Jiang, Chen Qian, Shuo Yang, Cheng Li, Honggang Zhang, Xiaogang Wang, and Xiaoou Tang.  Residual attention network for image classification.  In CVPR, 2017.
  * [55] Hao Wang, Qilong Wang, Mingqi Gao, Peihua Li, and Wangmeng Zuo.  Multi-scale location-aware kernel representation for object detection.  In CVPR, 2018.
  * [56] Jiayun Wang, Rudrasis Chakraborty, and Stella X. Yu.  Spatial transformer for 3d points.  CoRR, abs/1906.10887, 2019.
  * [57] Peng-Shuai Wang, Yang Liu, Yu-Xiao Guo, Chun-Yu Sun, and Xin Tong.  O-CNN: Octree-based Convolutional Neural Networks for 3D Shape Analysis.  ACM Transactions on Graphics (SIGGRAPH), 36(4), 2017.
  * [58] Shenlong Wang, Simon Suo, Wei-Chiu Ma, Andrei Pokrovsky, and Raquel Urtasun.  Deep parametric continuous convolutional neural networks.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [59] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon.  Dynamic graph cnn for learning on point clouds.  ACM Transactions on Graphics (TOG), 2019.
  * [60] Wenxuan Wu, Zhongang Qi, and Li Fuxin.  Pointconv: Deep convolutional networks on 3d point clouds.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [61] Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao.  3d shapenets: A deep representation for volumetric shapes.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1912–1920, 2015.
  * [62] Saining Xie, Sainan Liu, Zeyu Chen, and Zhuowen Tu.  Attentional shapecontextnet for point cloud recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018.
  * [63] Hongyu Xu, Xutao Lv, Xiaoyu Wang, Zhou Ren, Navaneeth Bodla, and Rama Chellappa.  Deep regionlets for object detection.  In ECCV, 2018.
  * [64] Yifan Xu, Tianqi Fan, Mingye Xu, Long Zeng, and Yu Qiao.  Spidercnn: Deep learning on point sets with parameterized convolutional filters.  In The European Conference on Computer Vision (ECCV), September 2018\.
  * [65] Xu Yan, Chaoda Zheng, Zhen Li, Sheng Wang, and Shuguang Cui.  Pointasnl: Robust point clouds processing using nonlocal neural networks with adaptive sampling.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [66] Wentao Yuan, David Held, Christoph Mertz, and Martial Hebert.  Iterative transformer network for 3d point cloud.  arXiv preprint arXiv:1811.11209, 2018.
  * [67] Rui Zhang, Sheng Tang, Yongdong Zhang, Jintao Li, and Shuicheng Yan.  Scale-adaptive convolutions for scene parsing.  ICCV, 2017.
  * [68] Hengshuang Zhao, Li Jiang, Chi-Wing Fu, and Jiaya Jia.  PointWeb: Enhancing local neighborhood features for point cloud processing.  In CVPR, 2019.
  * [69] Peng Zhou, Bingbing Ni, Cong Geng, Jianguo Hu, and Yi Xu.  Scale-transferrable object detection.  In CVPR, June 2018.
  * [70] Yanzhao Zhou, Qixiang Ye, Qiang Qiu, and Jianbin Jiao.  Oriented response networks.  In CVPR, 2017.