Neighbourhood Operations

Neighbourhood operations compute an output pixel from a group of pixels in a local region, in contrast to point operations acting on a single pixel.

• The operator is a sub-image, called a filter, mask, kernel, template or window
• Each element of the mask acts on a corresponding pixel in the local neighbourhood
• The output is saved to a new image, never written back into the input

Process:

• Identify the center pixel $I(x,y)$ the operation applies to
• Align the mask center with the neighbourhood: $I(x,y) \Rightarrow M(x,y)$
• Compute the output pixel $P(x,y)$ from the mask and the selected neighbourhood
• Save $P(x,y)$ to the output image
• Repeat for every pixel in the input image

Linear spatial filtering

The output is a sum of products between the mask and the neighbourhood, equivalent to a matrix dot product.

Here:

• $M(i,j)$: mask, typically odd sized with dimensions $(2N+1) \times (2M+1)$
• $I(x,y)$: input image

Integer filter coefficients with a scaling factor $k$ reduce computational cost:

Properties:

• Translational invariance
  The computation is the same everywhere in the image, only the neighbourhood values change.
• Locality
  The output depends only on pixels within the neighbourhood.
• Linearity
  Successive linear filters combine into a single equivalent filter, saving computation.

Non-linear spatial filtering

Shares the same algorithm as linear filtering, but computes the output using a non-linear expression: thresholding, sorting, log functions.

• Locality and translational invariance still hold
• Linearity does not hold

Examples:

• $P(x,y) = 1$ if the weighted neighbourhood sum $\ge$ a threshold $t$, else $0$

Handling image boundaries

The neighbourhood doesn’t fit the mask at image boundaries.

• Omit missing pixels
  Output is smaller than the input, but requires no algorithm change.
• Change mask shape at the edge
  Requires extra conditional logic, only works for certain filters.
• Pad the image
  Add extra rows and columns with white, black or background coloured pixels.
• Replicate border pixels
• Wrap pixels around the image
  Can cause artefacts.

Convolution and correlation

Correlation:

• Denoted $M(i,j) \circ I(x,y)$
• Computed directly with the mask as given
• Used for template matching, where directionality matters

Convolution:

• Denoted $M(i,j) * I(x,y)$
• Mask is pre-rotated 180 degrees before computation
• Used for operations such as smoothing, where directionality doesn’t matter