A Linear Time and Space Local Point Cloud Geometry Encoder via
  Vectorized Kernel Mixture (VecKM)
Dehao Yuan Cornelia Fermüller Tahseen Rabbani Furong Huang Yiannis Aloimonos
We propose VecKM, a novel local point cloud geometry encoder that is
descriptive, efficient and robust to noise. VecKM leverages a unique approach
by vectorizing a kernel mixture to represent the local point clouds. Such
representation is descriptive and robust to noise, which is supported by two
theorems that confirm its ability to reconstruct and preserve the similarity of
the local shape. Moreover, VecKM is the first successful attempt to reduce the
computation and memory costs from $O(n^2+nKd)$ to $O(nd)$ by sacrificing a
marginal constant factor, where $n$ is the size of the point cloud and $K$ is
neighborhood size. The efficiency is primarily due to VecKM's unique
factorizable property that eliminates the need of explicitly grouping points
into neighborhoods. In the normal estimation task, VecKM demonstrates not only
100x faster inference speed but also strongest descriptiveness and robustness
compared with existing popular encoders. In classification and segmentation
tasks, integrating VecKM as a preprocessing module achieves consistently better
performance than the PointNet, PointNet++, and point transformer baselines, and
runs consistently faster by up to 10x.