Neighbourhood Operations

Neighbourhood operations compute an output pixel from a group of pixels in a local region.

Kernel

Aka. filter, mask, template or window. Operator of a neighbourhood operation.

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.

The mask cells are addressed by offset from the mask center, which is $(0,0)$. An odd sized mask has one such center cell. $M(i,j)$ is the mask value at offset $(i,j)$.

Process

• Identify the center pixel $I(x,y)$ the operation applies to
• Place the mask so its center cell $M(0,0)$ sits on $I(x,y)$. Each other cell $M(i,j)$ then sits on $I(x+i, y+j)$, since the offset that addresses the cell is the offset added to $(x,y)$ to find the pixel under it
• 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

Spatial Filtering

A neighbourhood operation that computes each output pixel directly from the intensities in the input image’s spatial domain, by sliding a mask over it.

Correlation and convolution are the two ways to combine the mask with a neighbourhood, both by a sum of products equivalent to a matrix dot product. They differ only in whether the mask is flipped first.

In both sums:

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

Correlation

The mask is applied as given: each cell $M(i,j)$ multiplies the pixel at the matching offset $(x+i, y+j)$, and the products are summed. Denoted $M \circ I$.

Used for template matching: the response peaks where the neighbourhood looks most like the mask, so the mask must keep its orientation.

Convolution

The mask is first rotated 180 degrees, so cell $M(i,j)$ multiplies the pixel at the opposite offset $(x-i, y-j)$. Denoted $M * I$.

The flip makes the operation associative and commutative, so a chain of convolution filters can be merged into one equivalent mask. Used for smoothing and similar operations, where the mask is often symmetric and orientation doesn’t matter.

Frequency Domain Filtering

A filtering method that transforms the image to the frequency domain via the Fourier transform, multiplies it by a filter function there, then inverse-transforms back to the spatial domain.

By the convolution theorem, multiplication in the frequency domain is equivalent to convolution in the spatial domain, so any spatial filter has a frequency domain counterpart.

• Low-pass filter
  Keeps low frequencies, removing high-frequency detail and noise. Smooths the image.
• High-pass filter
  Keeps high frequencies, removing low-frequency content. Sharpens edges.

Linearity of Filters

Linear Filter

Output pixel is a correlation or convolution of the mask with the neighbourhood. 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 Filter

Output pixel comes from a non-linear expression applied to the neighbourhood: 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.