Non-Local Networks Link Distant Pixels

Non-local blocks let each pixel borrow features from far away pixels, weighted by similarity, so context crosses the whole image in one step.

Scores 2, 1, and 0 become weights 0.665, 0.245, and 0.090 that blend far pixels into each output

Why Does This Exist?

A $3 \times 3$ convolution sees neighbors only. A small ball in a wide field needs net texture from meters away, but stacking layers to reach it wastes depth.

Non-local fixes it in one block. It extends convolutional layers, generalizes spatial attention, and helps object detection on large scenes.

Think of It Like This

A group chat polling every member

You decide where to eat by polling all friends at once, weighting replies by how much you trust each person on food. One far friend who knows ramen outweighs three nearby friends who do not.

Pixels are friends, similarity is trust, and the blend is dinner. Where it stops: polling everyone each time costs attention, just as non-local costs compute.

How It Actually Works

For position $i$ with feature $x_i$ , output $y_i$ blends all positions $j$ :

y_i = \frac{1}{C(x)} \sum_j f(x_i, x_j) g(x_j)

$f$ measures similarity and $g$ transforms features. Embedded Gaussian uses $f(x_i,x_j) = e^{\theta(x_i)^T \phi(x_j)}$ , where $\theta$ and $\phi$ are learned $1 \times 1$ projections, and $C(x) = \sum_j f(x_i,x_j)$ normalizes. Add $y_i$ back with $z_i = x_i + W y_i$ .

Worked example

Query pixel compares to three spots with dot scores $s = [2, 1, 0]$ . Exponentiate to $[7.39, 2.72, 1.00]$ , sum $11.11$ , weights $[0.665, 0.245, 0.090]$ . Values $g$ are $[1,0]$ , $[0,1]$ , $[0,0]$ . Blend is $0.665 \times [1,0] + 0.245 \times [0,1] = [0.665, 0.245]$ . Far spot two still gives a quarter vote, which convolution cannot do in one step.

Watch Out For

Paying quadratic cost on full resolution

Non-local on $64 \times 64$ maps builds a $4096 \times 4096$ affinity, blowing memory. Symptom: out of memory on first epoch. Fix: insert after downsampling or subsample $j$ with pooling before affinity.

The Quick Version

Non-local output blends all positions weighted by learned similarity in one step.
Scores $[2, 1, 0]$ give weights $[0.665, 0.245, 0.090]$ summing to 1.
Fixture output $[0.665, 0.245]$ keeps far context convolution misses.
Cost is quadratic in pixels, so place after downsampling.
It generalizes spatial attention from local gates to full-image blends.