SquareNet

SquareNet is an innovative solution designed for bijective gridification of point clouds, providing a fast and scalable method to transform unstructured point cloud data into structured grids. The bijective transformation ensures that each point corresponds to one cell without overlap, allowing for full invertibility. This approach significantly optimizes spatial queries, enabling efficient tensor indexing by replacing costly methods like k-nearest neighbors (k-NN), radius searches, neighborhood graphs, kd-trees, voxelization, and rasterization.

Key Features

• Dimensional Versatility: Handles any dimensionality of data, making it flexible for various applications.
• Adaptability: Capable of processing non-convex geometries and irregular distributions.
• Scalability: Efficiently manages millions of points, achieving processing times in seconds rather than minutes.
• Framework Compatibility: Seamlessly integrates with popular machine learning frameworks such as PyTorch and JAX.
• Native Padding: Supports native padding to address mismatches between the number of grid slots and points, introduced in version 1.2.

Example of Gridification

SquareNet effectively visualizes the transformation of data from raw point clouds into a structured tensor grid. The following illustration shows the differences in organization and accessibility after the gridification process:

How It Works

Initialization of SquareNet occurs by specifying a target grid shape and subsequently calling the fit() method using the point cloud data. The underlying Cartesian sort algorithm rearranges point indices into structured grid multi-indices as shown in the following transformation:

raw points      #(N, D)       →  sn.fit(X)        →  grid  #(N1, N2, ..., ND)
flat data       #(N, *C)      →  sn.map(X)        →  structured tensor  #(N1, ..., ND, *C)
structured tensor             →  sn.invert_map(X) →  back to flat view

The mapping ensures that the process is bijective, allowing the invert_map function to retrieve the original data precisely without any loss of information.

The Cartesian Sort Algorithm

Instead of resorting to general optimal transport—which is computationally intensive at scale—SquareNet employs a rapid heuristic known as Cartesian sort. This method optimizes the gridification process by efficiently organizing data along 1D Cartesian projections, maintaining a highly vectorized approach for sorting.

Performance Benefits

• Speed: Capable of processing millions of points quickly using native tensor operations.
• Coordinate Monotonicity: Ensures that the grid reflects consistent increases along the defined axes, facilitating algorithm efficiency.
• Approximate Neighborhood Preservation: Achieves a high degree of accuracy in retrieving neighboring points in the grid, making the manipulation of spatial data more reliable. Experimental results demonstrate that:
  • In a 2D dataset, using an 11x11 square window can recover approximately 97% of the true nearest neighbors, while a 31x31 window recovers about 99.5%.
• Volume Conservation: Guarantees the conservation of volumes throughout the transformation process, enhancing the fidelity of data representation.

Usage Scenarios

SquareNet is particularly beneficial for:

• Point Cloud Processing: Enables quick spatial queries with contiguous memory lookups, enhancing vectorized processing over traditional irregular structures.
• Kernel Methods: Efficiently approximates large Gram matrices through its grid structure.
• Deep Learning Applications: Transforms flat point datasets into compatible tensors for convolutional neural networks (CNNs) or attention-based architectures.

For a detailed overview of the usage and advanced functionalities, refer to the Quick Start Guide.

SquareNet represents a critical advancement in processing complex datasets, merging speed and accuracy into a single efficient tool.