Fundamentals of Computer Vision Lecture 3: Image Filtering and Edge Detection

Fundamentals of Computer Vision: Image Filtering

• Overview of Lecture Topics

  • Image noise.

  • Linear shift-invariant image filtering.

  • Convolution and Correlation.

  • Edge detection.

Mathematical Foundations of Convolution

• Convolution for 1D Continuous Signals

  • Filtering is defined as the convolution of an input signal $g$ and a filter $f$.

  • Definition: Output $(f * g)(x)$.

  • Mechanism: The filter is flipped before being applied.

  • Example: A 1D continuous box filter applied to a signal results in a blurred version of the input signal $g$.

• Convolution for 2D Discrete Signals

  • Definition for filtered image $h$: $h[m, n] = \sum_{k, l} f[k, l] g[m - k, n - l]$.

  • The operation involves a horizontal and vertical flip of the filter kernel.

  • If the filter $f[k, l]$ is non-zero only within the range $-N \leq k, l \leq N$, then:         $h[m, n] = \sum_{k=-N}^{N} \sum_{l=-N}^{N} f[k, l] g[m-k, n-l]$.

  • The kernel is typically represented as a $3 \times 3$ matrix (or other $N \times N$ odd-dimension matrices).

Properties of Convolution

• Linear Shift-Invariant (LSI) Properties

  • Shift Invariant: The operator behaves the same everywhere in the image. The output value depends entirely on the pattern in the image neighborhood, not the spatial position of that neighborhood.

  • Superposition: Convolution is a linear operator. $h * (f_1 + f_2) = (h * f_1) + (h * f_2)$.

• Algebraic Properties

  • Commutative: $f * g = g * f$.

  • Associative: $(f * g) * h = f * (g * h)$.

  • Distributive over Addition: $f * (g + h) = (f * g) + (f * h)$.

  • Scalars Factor Out: $k f * g = f * kg = k(f * g)$.

  • Differentiation Rule: Differentiation can be applied to either the filter or the signal.

  • Identity: Convolution with a unit impulse $e = [\dots, 0, 0, 1, 0, 0, \dots]$ results in the original signal: $f * e = f$.

Convolution vs. Correlation

• 2D Discrete Convolution: Requires flipping the filter in both dimensions (bottom to top, right to left) before applying the cross-correlation logic.

  • Notation: $F * H$.

• 2D Discrete Correlation: Does not involve a flip.

  • Definition: $\sum_{k, l} f[k, l] g[m + k, n + l]$.

• Practical Significance: For most computer vision applications, the distinction is negligible because many kernels (like Gaussian or Box filters) are symmetric. However, the flip is mathematically significant when discussing frequency-domain filtering.

Filtering an Impulse Signal

• Conceptual Exercise: Filtering an image $F$ containing a single centered pixel with value $1$ (surrounded by $0$s) with an arbitrary kernel $H = \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$.

• Result: The output is the filter kernel itself, but flipped horizontally and vertically.

  • Output pattern trace:

    • Top row: $i, h, g$

    • Middle row: $f, e, d$

    • Bottom row: $c, b, a$

Separable Filters

• Definition: A 2D filter is separable if its matrix representation can be decomposed into the product of a column vector and a row vector: $Kernel = Column \times Row$.

• Example: Box Filter:

  • A $3 \times 3$ matrix of all $1$s is the product of $\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}$ and $\begin{pmatrix} 1 & 1 & 1 \end{pmatrix}$.

  • The rank of a separable filter matrix is $1$.

• Computational Efficiency:

  • Standard 2D convolution cost for an $M \times M$ image and an $N \times N$ kernel is $M^2 \times N^2$.

  • Separable 2D convolution is equivalent to two 1D convolutions (first across all rows, then across all columns).

  • Cost of separable convolution: $2 \times N \times M^2$.

Gaussian Filtering

• Concept: Used when neighboring pixels should have more influence on the output than distant pixels. The weights fall off according to a Gaussian distribution.

• Mathematical Characteristics:

  • In theory, Gaussian support is infinite.

  • In practice, it is truncated at a finite distance, usually at $2\sigma$ to $3\sigma$.

• Key Properties:

  • Convolution of a Gaussian with another Gaussian results in a third Gaussian.

  • Scale ($\sigma$): The variance $\sigma$ determines the extent of smoothing (the width/spread of the kernel).

    • Example: $\sigma = 2$ with a $30 \times 30$ kernel vs. $\sigma = 5$ with a $30 \times 30$ kernel.

  • Kernel Size: While the Gaussian function is infinite, the discrete filter kernel size must be chosen appropriately. Truncating a $\sigma = 5$ Gaussian to a $10 \times 10$ kernel loses significant data compared to a $30 \times 30$ kernel.

• MATLAB Implementation:

  • kernelsize = 10;

  • sigma = 5;

  • h = fspecial('gaussian', kernelsize, sigma);

  • outim = imfilter(im, h); (Correlation by default).

Case Studies in Linear Filters

• Identity Filter: Kernel $[0, 0, 0; 0, 1, 0; 0, 0, 0]$ leaves the image unchanged.

• Shift Filter: Kernel $[0, 0, 0; 0, 0, 1; 0, 0, 0]$ shifts the image left by 1 pixel (using correlation).

• Box Filter: Average of pixels in the neighborhood; results in blurring.

• Sharpening Filter: Accentuates differences with the local average.

  • Strategy: Subtract a smoothed (blurred) version of the image from the original to find the "detail," then add that detail back to the original.

  • Formula: $Sharpened = Original + \alpha (Original - Smoothed)$.

  • It stresses intensity peaks and does nothing in flat areas.

Non-Linear Filtering: The Median Filter

• Mechanism: Replaces the center pixel with the median value of the pixels in the local window.

• Advantages:

  • No New Values: Does not introduce new pixel values (unlike blurring which averages).

  • Impulse Noise Removal: Extremely effective at removing "Salt and Pepper" noise (spikes).

  • Edge Preserving: Unlike Gaussian or Box blurs, the median filter maintains sharp edges.

• MATLAB: output_im = medfilt2(im, [h, w]);.

Edge Detection Theory

• Goal: Map 2D pixel arrays to a set of curves, line segments, or contours.

• Causes of Edges:

  • Depth Discontinuity: Object boundaries.

  • Surface Orientation: Changes in shape.

  • Cast Shadows.

  • Reflectance Change: Appearance and texture information.

• Mathematical Perspective: Edges correspond to "steep cliffs" or discontinuities in the image intensity function.

• Gradient Principles:

  • The gradient vector $\nabla f = \begin{pmatrix} \frac{\partial f}{\partial x} \\ \frac{\partial f}{\partial y} \end{pmatrix}$ points in the direction of the most rapid increase in intensity.

  • Edge Strength: Given by the gradient magnitude $\sqrt{(\frac{\partial f}{\partial x})^2 + (\frac{\partial f}{\partial y})^2}$.

  • Gradient Direction: $\theta = \tan^{-1}(\frac{\partial f / \partial y}{\partial f / \partial x})$.

  • Edges correspond to the extrema of the first derivative.

Finite Differences and Derivative Filters

• Discrete Derivatives:

  • Forward Difference: $f'(x) \approx \frac{f(x+h) - f(x)}{h}$.

  • Central Difference: For discrete signals, using $h=2$ results in the filter $[1, 0, -1]$.

• Derivative of Gaussian (DoG):

  • Differentiation and convolution are associative.

  • Instead of differentiating a noisy image directly, convolve the image with the derivative of a Gaussian filter.

  • This smooths the image and takes the derivative simultaneously.

Edge Detection Operators

• The Sobel Filter:

  • Approximates the derivative of a Gaussian.

  • Can be decomposed into a blurring component and a derivative component.

  • Horizontal Sobel ($S_x$):         $S_x = \begin{pmatrix} -1 & 0 & 1 \\ -2 & 0 & 2 \\ -1 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \\ 1 \end{pmatrix} * \begin{pmatrix} -1 & 0 & 1 \end{pmatrix}$

    • This detects vertical edges.

  • Vertical Sobel ($S_y$):         $S_y = \begin{pmatrix} 1 & 2 & 1 \\ 0 & 0 & 0 \\ -1 & -2 & -1 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ -1 \end{pmatrix} * \begin{pmatrix} 1 & 2 & 1 \end{pmatrix}$

    • This detects horizontal edges.

  • The $1/8$ normalization term is technically needed for correct gradient magnitude but often omitted for simple edge detection.

• Comparison of Derivative Filters:

  • Sobel: Weights the center row/column by $2$.

  • Scharr: Uses weights like $3$ and $10$ (e.g., $[3, 0, -3; 10, 0, -10; 3, 0, -3]$) for better rotational invariance.

  • Prewitt: Uses uniform weights of $1$ (e.g., $[1, 0, -1; 1, 0, -1; 1, 0, -1]$).

  • Roberts: A $2 \times 2$ operator for diagonal differences (e.g., $[0, 1; -1, 0]$ and $[1, 0; 0, -1]$).