Point Cloud

A point cloud is a set of points in 3D space, each a sample of some surface in the scene. It is what a laser scanner returns, what a depth camera produces once its depth image is lifted into 3D, and what triangulation of many matched features yields. It records only where surfaces were measured, with no connectivity between the points, and is the usual starting point for registration, surface reconstruction, and 3D recognition.

Definition

A point cloud is a finite set of points $\{\mathbf{p}_1, \dots, \mathbf{p}_N\}$ with $\mathbf{p}_i \in \mathbb{R}^3$, expressed in some coordinate frame (the sensor’s, a camera’s, or a world frame). Each point may carry attributes: an RGB color from a camera, a return intensity from a laser scanner, a surface normal, a timestamp, a semantic label, or a confidence. The set has no inherent order and stores no adjacency between points.

Intuition

Imagine spraying a statue with paint from the front and then removing the statue: the droplets left hanging in space are a point cloud. They show the shape where they landed, nothing of the statue’s back, and nothing about which droplets were neighbors on the surface; that has to be inferred from distances.

An image, by contrast, is a regular grid in which every pixel has fixed neighbors, so convolution is trivial to define. A mesh adds explicit connectivity, triangles joining vertices, and so defines a continuous surface. A voxel grid divides space into regular cells, regaining the grid at the cost of memory and a fixed resolution. A point cloud gives up regularity and connectivity in exchange for storing exactly what was measured.

Formal Definition

Write the cloud as an $N \times 3$ matrix $P$ whose rows are the points, optionally extended with attribute columns. Because the cloud is a set, any row permutation $\Pi P$ describes the same cloud, so any function $f$ of the cloud that is meant to describe its geometry must satisfy

$$f(\Pi P) = f(P) \quad \text{for every } N \times N \text{ permutation matrix } \Pi.$$

Neighborhoods are defined by distance: the $k$-neighborhood $\mathcal{N}_k(\mathbf{p}_i)$ holds the $k$ nearest points, and the radius neighborhood the points within distance $r$,

$$\mathcal{N}_r(\mathbf{p}_i) = \{\, \mathbf{p}_j : \lVert \mathbf{p}_j - \mathbf{p}_i \rVert \le r \,\}.$$

Organized and unorganized clouds. A cloud produced from a depth image keeps the image’s layout: it is an $H \times W$ array of points, one per pixel, with invalid pixels marked. The PCD format documentation calls this an organized point cloud; it gives stereo and time-of-flight cameras as examples and notes that the known pixel adjacency makes neighbor search much cheaper. A cloud with no such layout, for example one merged from several scans, is unorganized.

A depth map becomes an organized cloud by inverting the pinhole projection: a valid pixel $\mathbf{x} = (u, v, 1)^\top$ with depth $Z$ maps to the camera-frame point $Z\,K^{-1}\mathbf{x}$, where $K$ holds the camera parameters. Here $Z$ is depth along the optical axis, not the range along the ray that a laser scanner reports; the depth map article derives the formula and the conversion between the two.

Properties

• Unordered. Storage order carries no meaning. Qi et al. (2017) list this first among the properties a network for point sets must respect: it must give the same answer for all $N!$ orderings of $N$ points.
• Irregular and non-uniform. Spacing between points varies with sensor geometry. A spinning laser scanner fires at fixed angular steps, so the spacing between neighboring points on a surface grows roughly linearly with range, and distant objects receive few points. Surfaces seen at grazing angles are sampled sparsely too.
• Incomplete. Only surfaces visible from the sensor are sampled. Occluded regions, the backs of objects, and surfaces that absorb or mirror the signal (dark, specular, or transparent materials) leave holes.
• Noisy, with outliers. Measurement noise typically grows with range for depth sensors and stereo, and spurious points appear, for example at depth discontinuities where a measurement mixes foreground and background.

Examples

Laser scanners (LiDAR). A LiDAR measures distances with laser pulses and reports each return as a 3D point, often with an intensity. In KITTI, a Velodyne HDL-64E spinning at 10 Hz recorded the scans and triggered the cameras, so each image comes with a synchronized cloud. Survey data from airborne and terrestrial scanners is commonly exchanged in the ASPRS LAS format, whose point records carry intensity, return number, classification, and GPS time alongside the coordinates.

Depth cameras. RGB-D cameras pair a depth image with a color image, so their back-projected clouds are organized and, once depth and color are registered, carry a color per point.

Stereo and multi-view reconstruction. Stereo vision produces a depth value per pixel of the reference image, which back-projects into a cloud in the same way. Structure from motion triangulates matched features across many photographs into a sparse cloud of one point per feature track, and multi-view stereo densifies it into a cloud with up to one point per pixel per image.

File formats. PLY, written at Stanford in the mid-1990s for scanned models, stores vertices with optional properties such as color and normals; a PLY file with vertices and no faces is a point cloud. PCD is the Point Cloud Library’s format, with ASCII, binary, and compressed binary encodings and WIDTH and HEIGHT header fields that record whether the cloud is organized (HEIGHT 1 means unorganized). LAS is the exchange format for LiDAR survey data maintained by ASPRS.

Basic Operations

Nearest-neighbor search. Almost every operation needs the neighbors of each point, and clouds often hold hundreds of thousands of points. A k-d tree, introduced by Bentley (1975), recursively splits space along coordinate axes; for low-dimensional data such as 3D points it typically answers a nearest-neighbor query far faster than a scan of all $N$ points. Octrees play the same role and also support multi-resolution processing.

Normal estimation. Hoppe et al. (1992) fit a plane to the $k$-neighborhood of each point by least squares. The plane passes through the neighborhood’s centroid $\bar{\mathbf{p}}$, and its normal is the eigenvector of the $3 \times 3$ covariance matrix

$$C = \sum_{\mathbf{q} \in \mathcal{N}_k(\mathbf{p}_i)} (\mathbf{q} - \bar{\mathbf{p}})(\mathbf{q} - \bar{\mathbf{p}})^\top$$

with the smallest eigenvalue, that is, the direction along which the neighbors vary least. This is principal component analysis of the neighborhood. The fit gives an axis, not a direction: $\mathbf{n}$ and $-\mathbf{n}$ fit equally well. Hoppe et al. note that choosing globally consistent signs is NP-hard in general, and orient normals approximately by propagating a sign along a minimum spanning tree of a graph linking nearby tangent planes, with edge costs that favor nearly parallel planes. When the cloud comes from a single known viewpoint, the problem is easy: the Point Cloud Library’s normal estimation, for example, flips each normal to point toward the viewpoint, a fix its documentation notes does not hold for clouds merged from several viewpoints.

Downsampling. A voxel grid filter divides space into cubes of side $s$ and replaces the points in each occupied cube by one representative. Using the points’ centroid rather than the cube’s center keeps the representative close to the sampled surface. The result has roughly uniform density, which makes later steps cheaper and their parameters easier to choose.

Outlier removal. Statistical outlier removal, as implemented in the open-source Point Cloud Library (Rusu & Cousins, 2011), computes each point’s mean distance to its $k$ nearest neighbors and discards points whose mean distance lies more than a chosen multiple of the standard deviation above the average over the cloud. Isolated points far from any surface have unusually large neighbor distances and are removed; outliers that happen to lie close to the surface are not.

The example below applies the three operations to a noisy unit sphere with uniform outliers and compares the estimated normals with the true ones.

import numpy as np
from scipy.spatial import cKDTree

rng = np.random.default_rng(0)

# 20,000 noisy samples of a unit sphere, plus 400 uniform outliers in its bounding box.
d = rng.normal(size=(20000, 3))
surface = d / np.linalg.norm(d, axis=1, keepdims=True)
surface += rng.normal(scale=0.005, size=surface.shape)
outliers = rng.uniform(-1.2, 1.2, size=(400, 3))
cloud = np.vstack([surface, outliers])
is_outlier = np.r_[np.zeros(len(surface), bool), np.ones(len(outliers), bool)]
print(f"input points:            {len(cloud)}")

# Statistical outlier removal: mean distance to k neighbours, keep points within
# mean + 1 std of the cloud-wide distribution (the PCL example uses k=50, 1.0 sigma).
tree = cKDTree(cloud)
dist, _ = tree.query(cloud, k=51)          # the first neighbour is the point itself
mean_d = dist[:, 1:].mean(axis=1)
keep = mean_d < mean_d.mean() + 1.0 * mean_d.std()
print(f"after outlier removal:   {keep.sum()}  "
      f"(outliers left: {np.sum(keep & is_outlier)} of {is_outlier.sum()}, "
      f"surface points lost: {np.sum(~keep & ~is_outlier)})")
cloud = cloud[keep]

# Voxel-grid downsampling: replace the points in each occupied voxel by their centroid.
voxel = 0.05
keys = np.floor(cloud / voxel).astype(np.int64)
_, inverse, counts = np.unique(keys, axis=0, return_inverse=True, return_counts=True)
inverse = inverse.ravel()
down = np.zeros((len(counts), 3))
np.add.at(down, inverse, cloud)
down /= counts[:, None]
print(f"after 5 cm voxel grid:   {len(down)}")

# Normal estimation by PCA (Hoppe et al. 1992): the eigenvector of the
# neighbourhood covariance with the smallest eigenvalue.
k = 15
_, idx = cKDTree(down).query(down, k=k)
nbrs = down[idx]                               # (n, k, 3)
centered = nbrs - nbrs.mean(axis=1, keepdims=True)
cov = np.einsum("nki,nkj->nij", centered, centered) / k
eigvals, eigvecs = np.linalg.eigh(cov)         # ascending eigenvalues
normals = eigvecs[:, :, 0]

true_n = down / np.linalg.norm(down, axis=1, keepdims=True)
cos = np.abs(np.sum(normals * true_n, axis=1))  # PCA normals have no sign
angle = np.degrees(np.arccos(np.clip(cos, 0, 1)))
print(f"normal error (deg):      median {np.median(angle):.2f}, "
      f"95th percentile {np.percentile(angle, 95):.2f}")
outward = np.sum(normals * true_n, axis=1) > 0
print(f"normals already pointing outward: {outward.mean():.0%}")

Output:

input points:            20400
after outlier removal:   20073  (outliers left: 73 of 400, surface points lost: 0)
after 5 cm voxel grid:   6144
normal error (deg):      median 1.48, 95th percentile 3.92
normals already pointing outward: 49%

The filter removes most outliers without touching the surface, but the 73 survivors are those that landed near the sphere, where they look like surface points. The PCA normals are accurate to a few degrees as axes, yet about half point inward: the sign is arbitrary until an orientation step fixes it.

Common Misconceptions

• “A point cloud is a surface.” It is a set of samples. Whether two points belong to the same surface, and what lies between them, is an inference that depends on density, noise, and assumptions such as smoothness.
• “An organized cloud stays organized.” Its order encodes pixel adjacency, which is lost as soon as invalid points are removed or clouds are merged; algorithms that rely on the grid must then fall back to spatial search.

Where It Is Used

• Registration. Aligning two clouds of the same scene, for example consecutive LiDAR scans or scans from several viewpoints, is the job of iterative closest point and its variants, which alternate nearest-neighbor matching with a least-squares rigid fit.
• Model fitting and segmentation. Planes, cylinders, and other primitives are fitted to clouds with RANSAC, for example to find the ground plane in a driving scene.
• Surface reconstruction. Hoppe et al. (1992) reconstructed surfaces by turning oriented tangent planes into a signed distance function and extracting its zero set. Poisson surface reconstruction (Kazhdan, Bolitho & Hoppe, 2006) treats oriented points as samples of the gradient of the shape’s indicator function and recovers that function by solving a Poisson equation. Both need oriented normals.
• Mapping and localization. LiDAR odometry and SLAM register successive scans into a map.
• 3D recognition. Detection and segmentation in driving datasets such as KITTI operate on LiDAR clouds. Earlier deep networks converted clouds to voxel grids or rendered views; PointNet (Qi et al., 2017) consumed raw points by applying the same network to each point and aggregating with max pooling, a symmetric function that makes the output invariant to point order.