Convolutional Neural Networks on Non-uniform Geometrical Signals Using Euclidean Spectral Transformation

Chiyu Max Jiang, Dequan Wang, Jingwei Huang, Philip Marcus, Matthias Nießner

TL;DR

This paper introduces a novel method to apply standard, powerful Convolutional Neural Networks (CNNs) to irregular 3D data—such as point clouds and meshes—without the typical information loss. By utilizing an analytical Euclidean Spectral Transformation, the authors map non-uniform geometric signals into a spectral domain. This allows the data to be processed by state-of-the-art "grid-based" CNNs with zero initial sampling error.

Overview of the NUFT pipeline for various simplices and downstream tasks.

The Problem with 3D Data

Deep learning has mastered "grid" data like 2D images and 3D voxels, but the real world is rarely so tidy. 3D data usually exists in non-uniform formats like point clouds, wireframes, or triangular meshes. To use a standard CNN, researchers typically "voxelize" this data, essentially turning it into a 3D grid of pixels.

This approach has two major flaws:

  1. Aliasing and Information Loss: Voxelization is a lossy process. If a thin surface falls between grid points, it gets blurred or disappears entirely.
  2. Topological Rigidity: It is difficult to create a single neural network architecture that can simultaneously handle a point cloud (0-dimensional points) and a surface mesh (2-dimensional triangles).

Current alternatives, like Graph CNNs, often struggle to generalize across different shapes because they rely on the specific "connectivity" of the graph rather than the underlying Euclidean space.

Methodology: Non-Uniform Fourier Transforms (NUFT)

The authors propose using Non-Uniform Fourier Transforms (NUFT). Instead of approximating a shape on a grid, they use mathematical formulas to analytically integrate the geometry directly into the spectral (frequency) domain.

  • Simplex Formulations: They developed specific mathematical expressions for different "simplices"—points (0-simplex), lines (1-simplex), triangles (2-simplex), and tetrahedra (3-simplex). This allows them to treat any geometric object as a sum of these basic parts.
  • The "AuxNode" Trick: To handle complex solid shapes (polytopes), they introduced an "Auxiliary Node Method." This allows them to compute the transform of a solid volume just by looking at its boundary surface, significantly speeding up computation.
  • Euclidean Spectral Space: Unlike Graph CNNs, which operate on a graph-specific spectrum, this method transforms data into a standard Euclidean spectral space. The resulting representation is translation-invariant and can be converted back into a uniform grid using an Inverse Fast Fourier Transform (IFFT).
  • Standard Backbones: Because the output of their transform is a uniform grid (in either spectral or physical space), they can use "off-the-shelf" high-performance architectures like DLA (Deep Layer Aggregation) and U-Net.

Datasets and Evaluation

The researchers evaluated their method across three distinct tasks:

  1. MNIST Polygons: A "toy" dataset where standard MNIST digits were converted into vector polygons to test 2D shape representation.
  2. SHREC17 (ShapeNet55 Core): A large-scale benchmark for 3D shape retrieval and classification.
  3. ShapeNet55 (Surface Reconstruction): A subset of categories (cars, sofas, bottles) used to test the ability to reconstruct a smooth surface from a raw point cloud.
MNIST Polygons experiment comparing standard rasterization to the NUFT physical representation.

Key Insights and Results

  • Sub-grid Accuracy: Because the transform is analytical, the network can "see" details smaller than a single voxel. The paper demonstrates that their representation is significantly more accurate than binary voxels or Signed Distance Functions (SDF) at the same resolution.
  • Unified Topology: This is one of the few frameworks that can seamlessly "mix" data types. You could theoretically feed a network a point cloud with a few known surface patches, and the math remains consistent.
  • Efficiency through Frequency: By focusing on the spectral domain, the authors show they can capture complex shapes using fewer "modes" (data points) than a high-resolution voxel grid would require. They report a 58x efficiency gain over binary voxels for a specific error threshold.
  • State-of-the-Art Reconstruction: The model achieved a new state-of-the-art in point-cloud-to-surface reconstruction, outperforming established methods like Poisson Surface Reconstruction (PSR) and Deep Marching Cubes (DMC).
  • Robustness: The method proved highly robust to noise. In the surface reconstruction task, adding Gaussian noise to the input point cloud resulted in only a negligible drop in accuracy.
  • Competitive Retrieval: On the SHREC17 benchmark, the NUFT-based model performed on par with state-of-the-art models pre-trained on massive 2D image datasets (like ImageNet), despite the NUFT model being trained entirely from scratch.

Limitations and Future Work

While highly effective, the approach has a few constraints:

  • Computational Overhead: The initial analytical Fourier transform can be computationally intensive for extremely dense meshes (millions of faces). The authors suggest using Breadth-First Search (BFS) and caching to mitigate this.
  • Quadrature Resolution: At very high resolutions, the error estimates for their volume transforms become less accurate due to limitations in numerical integration (quadrature resolution).
  • Memory Constraints: Like all 3D grid-based methods, they are eventually limited by GPU memory when trying to reach ultra-high resolutions. Future work might involve combining this spectral approach with space-partitioning structures like Octrees.

Summary updated

Abstract

Convolutional Neural Networks (CNN) have been successful in processing data signals that are uniformly sampled in the spatial domain (e.g., images). However, most data signals do not natively exist on a grid, and in the process of being sampled onto a uniform physical grid suffer significant aliasing error and information loss. Moreover, signals can exist in different topological structures as, for example, points, lines, surfaces and volumes. It has been challenging to analyze signals with mixed topologies (for example, point cloud with surface mesh). To this end, we develop mathematical formulations for Non-Uniform Fourier Transforms (NUFT) to directly, and optimally, sample nonuniform data signals of different topologies defined on a simplex mesh into the spectral domain with no spatial sampling error. The spectral transform is performed in the Euclidean space, which removes the translation ambiguity from works on the graph spectrum. Our representation has four distinct advantages: (1) the process causes no spatial sampling error during the initial sampling, (2) the generality of this approach provides a unified framework for using CNNs to analyze signals of mixed topologies, (3) it allows us to leverage state-of-the-art backbone CNN architectures for effective learning without having to design a particular architecture for a particular data structure in an ad-hoc fashion, and (4) the representation allows weighted meshes where each element has a different weight (i.e., texture) indicating local properties. We achieve results on par with the state-of-the-art for the 3D shape retrieval task, and a new state-of-the-art for the point cloud to surface reconstruction task.
BibTeX
@inproceedings{jiang2019convolutional,
  author = {Chiyu Max Jiang and Dequan Wang and Jingwei Huang and Philip Marcus and Matthias Nießner},
  title = {{Convolutional Neural Networks on Non-uniform Geometrical Signals Using Euclidean Spectral Transformation}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
}
Figure