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.

Neighborhoods and Paths

• A path between 2 pixels is a sequence of adjacent pixels connecting them
• 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

Distance Measures

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

Euclidean Distance

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

City-Block Distance

Aka. Manhattan distance. Straight-line distance along the grid.

Chessboard Distance

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.

$D_e$ has no such grid correspondence, since its unit disc is not aligned to the pixel lattice.