Pixel Connectivity

Once an image is digitized, only a matrix of values remains. Pixel geometry is often lost.

Pixels may not be square, and capture and reproduction devices may not share the same pixel geometry
A mismatch between input and output pixel geometry causes geometric distortion
Final geometry depends on how pixels are arranged in the output device
Size, resolution and aspect ratio all need to be considered

Connectivity

Connectivity establishes the boundaries of objects, components and regions in an image.

2 pixels are connected iff they’re adjacent to each other and satisfy some similarity in grey level, given a similarity set $V$ .

4-connectivity
Adjacency restricted to the 4 pixels sharing an edge.
8-connectivity
Adjacency extended to the 4 pixels sharing only a corner.

Path

A path between 2 pixels is a sequence of adjacent pixels connecting them.

Neighborhood

A local neighborhood is a sample window selecting the pixels around a given pixel $p$ , used when an operation depends on a group of adjacent pixels.

Resampling Neighbourhoods

Image resampling finds a source position for each pixel in a new grid. A non-integer source position lies inside a $2 \times 2$ neighbourhood of source pixels.

Nearest Neighbour

Nearest-neighbour resampling copies the value of the closest source pixel. It preserves source values but creates blocky regions when enlarging an image.

The target output pixel maps backward to source coordinate $(0.75,0.25)$ between the $4$ source-pixel centres. Its distance to the centre of $30$ is $\sqrt{0.25^2 + 0.25^2}$ . Its distance to the centre of $10$ is $\sqrt{0.75^2 + 0.25^2}$ . The $30$ pixel is closest, so nearest-neighbour resampling copies $30$ to the output.

Nearest-neighbour selection from a 2 by 2 source neighbourhood.

Bilinear Interpolation

Bilinear interpolation forms a weighted sum of the $4$ surrounding pixels. Each weight decreases with distance from the source position.

The distance-based weights are $0.1875$ , $0.5625$ , $0.0625$ and $0.1875$ . Their weighted sum is $38.75$ , which rounds to output value $39$ .

Bilinear interpolation from a 2 by 2 source neighbourhood.

Distance Measures

For 2 pixels $p(x,y)$ and $q(s,t)$ :

Euclidean Distance

Straight-line distance between $p$ and $q$ .

D_e(p,q) = \sqrt{(x-s)^2 + (y-t)^2}

City-Block Distance

Also known as Manhattan distance. Straight-line distance along the grid.

D_4(p,q) = |x-s| + |y-t|

Chessboard Distance

D_8(p,q) = \max(|x-s|, |y-t|)

The same pixels are compared in each grid. Euclidean distance follows the direct line. City-block distance uses horizontal and vertical moves. The chessboard panel marks the 1-unit vertical component. Dotted guides retain the fixed horizontal offset.

Connectivity Correspondence

Each metric equals the length of the shortest path allowed by its matching connectivity.

$D_4$ matches 4-connectivity
Pixels within $D_4 \le 1$ of $p$ are $p$ and its 4 edge-sharing neighbors. A minimal $D_4$ path moves only horizontally and vertically.
$D_8$ matches 8-connectivity
Pixels within $D_8 \le 1$ of $p$ are $p$ and all 8 surrounding pixels. A minimal $D_8$ path may also move diagonally.