Image Filtering Notes

Image Filtering

Let's Fix Things

Images often contain noise, which can be high-frequency variations or artifacts that degrade image quality. To reduce noise, each pixel can be replaced with a weighted average of its neighborhood. The weights are determined by a filter kernel, a matrix that specifies how each neighboring pixel's value contributes to the new value of the central pixel.

Example: A simple averaging filter with equal weights (e.g., 1/9 for a 3x3 filter). This means each pixel's new value is the average of all pixels in its 3x3 neighborhood.

1D Case

Consider a 1D signal and a 1D filter. To compute the output, the filter is convolved with the signal. This involves sliding the filter across the signal, multiplying the filter values by the corresponding signal values, and summing the result. Convolution is a fundamental operation in signal processing that combines two signals to produce a third signal.

Example:

• Signal: $[10, 12, 9, 11, 10, 11, 12]$

• Filter: $[1/3, 1/3, 1/3]$

• Output: The first output value is the average of the first three signal values: $(10 + 12 + 9) / 3 = 10.33$. Subsequent output values are computed by sliding the filter one position to the right and repeating the process. This smooths the signal by reducing sharp transitions.

Applying a Linear Filter

Applying a linear filter involves convolving a filter kernel with the input image. The output $O_{ij}$ at position $(i, j)$ is computed as a weighted sum of the input pixel values in the neighborhood of $(i, j)$, where the weights are given by the filter kernel $F$. Linear filters obey the superposition principle: the response to a sum of inputs is the sum of the responses to each input individually.

$O<em>{ij} = \sum</em>{m} \sum<em>{n} I</em>{i+m, j+n} * F_{m, n}$

Painful Details – Edge Cases

When applying filters, especially near the edges of the image, special care must be taken to handle pixels where the filter extends beyond the image boundaries. Several strategies exist to manage these edge cases:

• Full: The filter touches any part of the image, resulting in an output image larger than the input.

• Same: The output image is the same size as the input image, typically achieved by padding the input.

• Valid: Only compute the output where the filter is entirely within the image boundaries, resulting in a smaller output image.

Common padding methods include:

• Symmetric Padding: Reflect the image content across the edges. This method is good at reducing edge artifacts.

• Pad/Fill: Add a constant value (often 0) to pad the image. This can introduce a dark border if not handled carefully.

• Circular/Wrap: Wrap the image around. This is useful when the image has periodic content.

Practice with Linear Filters

Different filter kernels can achieve various effects. The design of these filters depends on the desired outcome, such as blurring, sharpening, or edge detection:

• Identity Filter: A filter with a single 1 in the center and 0s elsewhere leaves the original image unchanged. It passes the input signal without modification.

• Shift Filter: A filter with a single 1 at an offset shifts the image. Moving features in the image.

• Blur (Box Filter): A filter with equal weights (e.g., 1/9) blurs the image. It reduces sharp transitions and noise.

• Sharpen Filter: A filter that accentuates the difference from the local average. Enhancing edges and fine details.

Properties – Linear

Linearity: Applying a filter that is the sum of two filters is the same as applying each filter separately and then summing the results:

$apply(I, f1 + f2) = apply(I, f1) + apply(I, f2)$

Properties – Shift-Invariant

Shift-invariance: Shifting the input image and then applying the filter is the same as applying the filter and then shifting the output image. This means the filter's effect is consistent regardless of the object's location in the image.

$shift(apply(I, f)) = apply(shift(I), f)$

Painful Details – Signal Processing

• Convolution vs. Cross-Correlation: The operation described is technically cross-correlation. Convolution involves flipping the filter in both axes before applying it. Convolution is used to ensure that the filter behaves as expected in linear time-invariant systems.

• To perform convolution, flip the filter left/right and up/down before applying the imageFilter function. This step is crucial for certain theoretical properties to hold.

Properties of Convolution

• Commutative: $f * g = g * f$. The order of the filters does not matter.

• Associative: $(f * g) * h = f * (g * h)$. Filters can be applied in any order.

• Distributes over +: $f * (g + h) = f * g + f * h$. Convolution distributes over addition.

• Scalars factor out: $kf * g = f * kg = k (f * g)$. Scaling the filter scales the output.

• Identity: Convolution with a single one surrounded by zeros leaves the input unchanged. This is the equivalent of multiplying by one.

Smoothing With A Box

A box filter replaces each pixel with the average of its neighbors. This results in a blurred image, where sharp details are smoothed out.

Solution – Weighted Combination

Instead of equal weights, use weights according to closeness to the center. Define $(0, 0)$ to be the center pixel, then the filter weight $Filter_{ij}$ can be defined as:

$Filter_{ij} \propto exp(-\frac{x^2 + y^2}{2\sigma^2})$

This weighting function is a Gaussian. Gaussian filters give more weight to closer pixels, resulting in a smoother blur.

Recognize the Filter?

The filter is a Gaussian filter, defined as:

$Filter_{ij} = \frac{1}{2\pi\sigma^2} exp(-\frac{x^2 + y^2}{2\sigma^2})$

Smoothing With A Box & Gauss

Gaussian filters produce a smoother result compared to box filters because of their weighting. However by increasing the size of the Box filter, this will result in the same outcome, but with more computational cost.

Picking a Filter Size

A filter that is too small will not accurately approximate the Gaussian and may lead to aliasing artifacts. A good rule of thumb is to choose a filter size that is approximately $6\sigma$ to capture 99.7% of the energy. This ensures that the filter captures most of the Gaussian distribution.

Runtime Complexity

The naive implementation of image filtering has a time complexity of $O(N^2M^2)$, where $N$ is the size of the image and $M$ is the size of the filter. This can be very computationally expensive for large images and filters.

Separability

A 2D Gaussian filter can be separated into two 1D Gaussian filters (one horizontal and one vertical). This property significantly reduces computational complexity.

Separability Equations

$Filter_{ij} \propto \frac{1}{2\pi\sigma^2} exp(-\frac{x^2 + y^2}{2\sigma^2}) = \frac{1}{\sqrt{2\pi}\sigma} exp(-\frac{x^2}{2\sigma^2}) * \frac{1}{\sqrt{2\pi}\sigma} exp(-\frac{y^2}{2\sigma^2})$

Runtime Complexity for Separable Filters

Using separability reduces the time complexity to $O(N^2M)$. For a 13x13 filter, this results in significant computational savings, making real-time image processing feasible.

Why Gaussian?

Gaussian filtering removes high-frequency components from the signal, which often corresponds to noise. It provides a good balance between noise reduction and detail preservation.

Where Gaussian Fails

Gaussian filters can be distorted by outliers. Means can be arbitrarily distorted by outliers, leading to suboptimal filtering results in the presence of extreme values.

Non-linear Filters (2D)

Median filtering is a non-linear filter that replaces each pixel with the median value of its neighbors. Steps for median filtering:

1. Sort the pixel values in the neighborhood.

2. Select the median value. This is robust to outliers, as the median is not affected by extreme values.

Is Median Filtering Linear?

Median filtering is not a linear operation. It does not satisfy the superposition principle.

Filtering - Sharpening

Sharpening can be achieved by adding the "details" (difference between the original image and a smoothed version) back to the original image. This enhances edges and fine details.

Filtering - Derivatives

Filters can be used to approximate derivatives of the image. Common derivative filters include Dx and Dy. These are used for edge detection and feature extraction.

Filtering – Counting

Filters can be used for counting tasks. For example, counting how many "on" pixels have 10+ neighbors within 10 pixels. This is useful in various image analysis applications.

Filtering – Missing Data

Filters can be used to fill in missing data in images. This is common with