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: $D_e(p,q) = \sqrt{(x-s)^2 + (y-t)^2}$
• City-block distance: $D_4(p,q) = |x-s| + |y-t|$
• Chessboard distance: $D_8(p,q) = \max(|x-s|, |y-t|)$