On 3D vision

This is part #15 of my notes on CS231n. The course is openly available, including the video lectures and assignments.

These notes are based on lecture 15: 3D Vision by Jiajun Wu, with the original papers linked below.

In diffusion models, the output was an image. We knew how to store it: a grid of pixels.

What if we want to move around the object, or change its shape? We need an output that describes it in 3D.

Let's start with what we can store, then build networks that read and produce those representations.

How do we represent a shape?

A point cloud stores positions $\mathbf{p}_i=(x_i,y_i,z_i)$. We can attach colour or a surface normal, a direction perpendicular to the surface. This is close to what a scanner gives us: samples of the surface, often with gaps and noise.

The points do not say which ones connect. Two nearby points might belong to one smooth surface, or to opposite sides of a thin gap.

Connect the points with triangles and we get a triangle mesh. We store vertices and a list of faces, each referring to three vertices. Now we can render the triangles or move the vertices to deform the surface. The connections tell us which neighbours to use when smoothing it. We still need to avoid holes and crossed faces.

We can also generate surface points from two coordinates:

$$\mathbf{p}=g(u,v)$$

Pick $u$ and $v$, evaluate $g$, and get a position in 3D. This is a parametric surface. Bézier patches and NURBS use control points to shape the mapping. Subdivision surfaces instead repeatedly refine a control mesh. In both cases, we can describe a smooth surface without listing every point on it.

These representations give us positions on the shape. We call them explicit. Let's reverse the operation: give a position in space and ask whether it is on the shape. This gives us an implicit representation.

A sphere in two forms

For a sphere of radius $r$, centred at the origin, a parametric description is:

$$g(u,v)=r\begin{bmatrix} \sin u\cos v\\ \sin u\sin v\\ \cos u \end{bmatrix}$$

Here $0\leq u\leq\pi$ and $0\leq v<2\pi$. Pick two angles and we get a point on the surface. This is convenient for sampling, although uniform steps in the angles do not give uniformly spaced surface points.

Its signed distance function, or SDF, is:

$$d(\mathbf{p})=\|\mathbf{p}\|_2-r$$

Here the sign is negative inside, zero on the surface, and positive outside. For $r=2$, the origin has distance $-2$, $(2,0,0)$ has distance 0, and $(3,0,0)$ has distance 1.

Notice the difference. The parametric function gives us a point on the sphere. The SDF tells us where a query point is relative to it. To get the surface back from the SDF, find where its value is zero.

If we only need the inside/outside answer, store 1 or 0 with an occupancy function. To sample a field, divide space into cells and store a value in each cell. This is a voxel grid; its values can be occupancy, distance, or learned features. A level set selects the locations where the field has one chosen value, such as the SDF's zero surface.

What an image leaves out

In a simple perspective camera, a point in camera coordinates projects to:

$$\begin{aligned} u&=f_x\frac{X}{Z}+c_x\\ v&=f_y\frac{Y}{Z}+c_y \end{aligned}$$

Here $Z>0$ is depth, $f_x,f_y$ are focal lengths in pixels, and $(c_x,c_y)$ is the image's principal point. These are camera intrinsics. The camera's position and orientation, its pose, transform world coordinates into camera coordinates first.

Scale $(X,Y,Z)$ by the same positive number and the pixel stays the same. With focal length 400 and principal point at zero, $(1,0,2)$ and $(2,0,4)$ both project to $(200,0)$.

So one pixel gives us a ray of possible 3D positions. It does not tell us which depth to choose, or what is behind the visible surface. We need more views, depth measurements, or a learned guess about the object's shape. A plausible guess can still disagree with the actual object.

Learning to recognize 3D objects

Suppose we have a shape and want to classify it. We already know how to classify images, so render the shape from several camera positions. Run the same CNN on each view, pool their features, then predict the class from that combined vector. This is a multi-view CNN.

We get to reuse 2D convolutions, although the chosen views determine which surfaces the network sees. This also assumes we have a shape to render; a partial scan may leave large parts out.

Alternatively, put the shape into a voxel grid and slide a 3D convolution through it. A $3\times3\times3$ filter mixes features from 27 cells instead of the nine pixels in a $3\times3$ image filter. We share the same weights at every position, just as before.

Resolution gets expensive

Suppose one dense feature volume has $n^3$ cells, 32 channels, and four bytes per channel value:

$$\text{bytes}=n^3\cdot32\cdot4$$

Here 1 MiB is $2^{20}$ bytes. This is one volume for one example, before gradients, other layers, or a batch. Doubling resolution along each axis multiplies the storage by eight.

Much of that volume may be empty. Keep large cells there, and split cells into eight children where we need more detail. Repeating this gives us an octree. OctNet uses this structure to reduce storage and computation. We save space, but our convolutions now have to work with cells of different sizes.

Learning directly from points

Why convert points to a grid at all?

A point cloud has no order. We can put the same points in different rows of an array, and we still want the same object class.

PointNet starts by running each point through the same MLP. Now we have one learned feature vector per point. Take the maximum over points, independently for each channel, to get one vector for the whole object:

In math notation:

$$\mathbf{f}_i=h_\theta(\mathbf{p}_i),\qquad z_k=\max_i f_{i,k}$$

$h_\theta$ is the MLP with shared parameters $\theta$. $i$ indexes points and $k$ indexes feature channels. Pass the pooled vector $\mathbf{z}$ through another MLP to get the class scores.

Suppose three points produce these two-channel features:

$$\mathbf{f}_1=(2,1),\quad \mathbf{f}_2=(0,4),\quad \mathbf{f}_3=(3,2)$$

Take the largest entry in each channel and we get $(3,4)$. Change the order to $\mathbf{f}_3,\mathbf{f}_1,\mathbf{f}_2$: still $(3,4)$. Notice that the two maxima come from different points. The MLP learns which features to compute before we select them with pooling.

For part segmentation, send the global vector back to every point. Concatenate it with that point's local feature and predict a label. Each prediction can now use both local and whole-object information. If we reorder the input points, their labels reorder with them. This is permutation equivariance; for classification, where the answer stays unchanged, it is permutation invariance.

Changing point order leaves the maxima unchanged. Rotating the points can change their features, and removing a point can remove a maximum. The original PointNet also learns transformations to align the input and feature spaces, but pooling alone only handles the order.

The shared MLP still processes each point independently. To learn local geometry first, PointNet++ groups nearby points and repeats this operation at increasing spatial scales. Or make the points nodes in a graph, connect neighbours, and pass features along the edges. Both let nearby points interact before we pool the whole object.

Predicting a shape

Now reverse the task. Given an image or a partial scan, we want to predict the shape.

Encode the observation into a shape code $\mathbf{z}$, then decode it into points, voxels, a mesh, or a field. Training across shapes lets the network learn recurring patterns and use them to fill gaps. We call this learned knowledge a shape prior. To supervise the missing parts directly, we need complete target shapes; a partial scan only tells us about the parts it measured.

With 3D targets, compare the geometry directly. With images alone, render the prediction and compare the rendered image or silhouette with the observation. A differentiable renderer lets us backpropagate that error to the shape parameters. The loss can correct the outline, although it cannot recover a dent that never changes the observed silhouette.

One way to decode a mesh is to start with a template and predict vertex movements. Pixel2Mesh uses graph convolutions and image features to do this. We keep the connections, so the output is already a surface. But that also keeps the topology: a sphere cannot acquire a proper handle just by stretching it.

AtlasNet instead learns to bend several surface patches:

$$\mathbf{p}=g_{\theta,k}(\mathbf{z},u,v)$$

$k$ selects a patch. Sample $(u,v)$ from a square and the network maps it to the object's surface. More samples give us more points. If we triangulate the square, we can carry those connections over to get mesh faces. Joining the patches is a separate problem; the mappings can leave gaps or overlaps.

How do we compare unordered outputs?

If the decoder outputs points, point 17 need not correspond to point 17 in the target. A loss between rows would punish a correct shape just because the point order changed.

For each predicted point, find its nearest target point and measure the squared distance. Average those distances, then repeat in the other direction. This gives us Chamfer distance, used in the point-set reconstruction paper. Here I use a mean for each direction:

$$L_{P\to Q}=\frac{1}{|P|} \sum_{\mathbf{p}\in P}\min_{\mathbf{q}\in Q} \|\mathbf{p}-\mathbf{q}\|_2^2$$ $$L_{\mathrm{CD}}=L_{P\to Q}+L_{Q\to P}$$

$P$ is the prediction and $Q$ the target. $|P|$ is the number of predicted points. The first direction penalizes predicted points far from the target; the reverse direction penalizes target regions the prediction misses.

Take points on a line, embedded in 3D with the other coordinates zero: $P=\{0,2\}$ and $Q=\{0,3\}$. In each direction the squared nearest distances are 0 and 1. Each mean is $1/2$, so the loss is 1.

If we only predict $P=\{0\}$, the first term is zero. But the reverse term is $(0+9)/2=4.5$. That is why we need both directions.

Several predicted points can choose the same nearest neighbour. To force a one-to-one match between equally sized, equally weighted sets, use Earth Mover's Distance and solve a minimum-cost assignment. That is more expensive. Neither point loss checks mesh connectivity, and a low average Chamfer error can hide a missing thin part.

Learning the implicit function

Let's make the decoder answer queries instead of producing a fixed list of points.

An occupancy network predicts:

$$o_\theta(\mathbf{p},\mathbf{z})\in[0,1]$$

Given the shape code $\mathbf{z}$ and position $\mathbf{p}$, it predicts the probability that the position is inside. Sample query points with inside/outside labels and train with binary cross-entropy. To recover the surface, find where the output crosses a threshold, commonly 0.5. We have turned surface prediction into a classifier's decision boundary in 3D.

DeepSDF predicts signed distance instead:

$$s_\theta(\mathbf{p},\mathbf{z})\in\mathbb{R}$$

Train it with signed distances, clamping the loss's distances to focus on the region near the surface. DeepSDF learns a code for each training shape together with one shared decoder. For a new shape, freeze the decoder and optimize a new code to fit the measurements. We do not need an encoder to predict that code in one pass. We do need the measurements in the same coordinate frame as the training shapes, or we must estimate pose too.

We can query this continuous function at any position, but it only learns detail supported by its capacity and training data. Near-surface samples help locate the boundary; farther samples teach it which regions are inside or outside.

To get a mesh, evaluate the field on a grid. Find cells that cross the surface threshold and extract triangles with Marching Cubes. We can refine the grid only near those crossings. The decoder saves us from storing a dense output grid during training, although mesh extraction still needs enough queries to resolve small details.

From geometry to rendered views

An SDF tells us where a surface is. It does not by itself tell us the colour of a pixel looking through the scene.

NeRF makes the network return density and colour. First pass an encoded position $\mathbf{x}$ through an MLP. It produces nonnegative volume density $\sigma$ and a feature vector. Combine that feature with the encoded viewing direction $\mathbf{d}$ to predict RGB colour $\mathbf{c}$.

The direction enters only the colour branch. The density at a position stays the same as we move the camera, while the colour can change to show a moving highlight.

Density controls how quickly a ray loses visibility as it passes through a region. Its units and role differ from the occupancy probability or signed distance we predicted earlier.

For a camera ray:

$$\mathbf{r}(t)=\mathbf{o}+t\mathbf{d}$$

$\mathbf{o}$ is the camera centre, $\mathbf{d}$ a unit direction, and $t$ distance along the ray. Sample positions from near to far and query the same network at each one. We now have densities and colours to combine into a pixel.

Turning density into a pixel

Assume density is constant over a short segment of length $\Delta_i$. Its opacity is:

$$\alpha_i=1-e^{-\sigma_i\Delta_i}$$

To find how much we can see of sample $i$, multiply the fractions that passed through all earlier segments. This is transmittance:

$$T_i=\prod_{j<i}(1-\alpha_j)$$

The first segment has $T_1=1$. Each segment contributes $T_i\alpha_i\mathbf{c}_i$. Add the $N$ contributions and whatever background colour $\mathbf{c}_{\mathrm{bg}}$ is still visible:

$$\begin{aligned} \hat{\mathbf{C}}={}& \sum_{i=1}^{N}T_i\alpha_i\mathbf{c}_i\\ &+T_{N+1}\mathbf{c}_{\mathrm{bg}} \end{aligned}$$

This is the discrete volume-rendering rule. A large density over a tiny distance can still have low opacity; the product $\sigma_i\Delta_i$ matters.

For example, let the first segment have $\alpha_1=0.2$ and the second $\alpha_2=0.75$. The first contributes 20% of its colour. We can still see 80% past it, so the second contributes $0.8\cdot0.75=60\%$. The remaining $0.8\cdot0.25=20\%$ comes from the background.

The weights sum to one. If we put the second segment first, it contributes 75%, the other contributes 5%, and the background still contributes 20%. Depth order changes the pixel.

To train the original NeRF, take photographs of one static scene with known camera intrinsics and poses. Render their rays, compare the predicted colours with the photographs, and backpropagate through the blend to the MLP weights. The positional encoding helps represent fine variation. A coarse pass also tells us where to place more samples for the fine pass.

After fitting, move the camera and render its new rays through the same field. This gives us novel-view synthesis. We trained on pixel colours, so poorly observed geometry may still be wrong even when the rendered views look right.

Gaussian splatting

Querying an MLP many times per pixel takes work. 3D Gaussian Splatting stores explicit Gaussian elements with positions, shapes, opacities, and direction-dependent colour.

Project the Gaussians into soft ellipses on the image, sort them by depth within screen tiles, then blend them. During training, adjust their parameters and add or remove Gaussians where needed. We can render these stored elements without evaluating an MLP at every ray sample.

I went through the splatting operation in more detail in these notes. Both approaches learn to reproduce a scene across views. To identify its parts or simulate their motion, we still need more structure.

A chair is more than a surface

Suppose we want to make a chair taller. If we only have surface points, which ones should move? How do we keep the legs attached to the seat?

Separate the seat, back, and legs into parts. Now we can select a leg or move the seat as a unit. We still need to describe how they connect.

Make each part a node in a graph, then add edges for contact, symmetry, or attachment. Group parts into a hierarchy: an arm belongs to an assembly, which belongs to the chair. StructureNet combines part geometry with these hierarchical relationship graphs. We can also describe repeated parts with a program, so one parameter changes all four leg lengths.

The network now has to learn the parts and their relationships as well as the coordinates. But those outputs let us express an edit such as “lengthen the legs and raise the seat” instead of moving thousands of unrelated surface points.

This is what I find interesting about the representation itself. Changing what we store changes what we can ask the model to do with the object.

Next are vision and language, where we connect visual representations to words.