Fundamentals of Computer Vision Lecture 5: Noise, Edges, and Fourier Theory of Fourier, and Pyramids

Review of Convolution and Correlation

  • Convolution Defined: An integral that expresses the amount of overlap of one function as it is shifted over another function. It is primarily considered a filtering operation.

  • Cross-Correlation Defined: A comparison of the similarity between two sets of data. It computes a measure of similarity of two input signals as they are shifted by one another.

    • The result reaches a maximum value at the moment when the two signals match best.

    • Correlation is a measure of the relatedness of two signals.

  • 2D Convolution Examples:

    • Smoothing/Blurring: Filtering with a kernel where elements sum to 1 (e.g., a 3×33 \times 3 box filter of all ones) results in a smoothed image. Blurring removes high-frequency "details" from the image.

    • Sharpening: Accomplished by subtracting a smoothed version of the image from the original or using a sharpening filter to accentuate differences with the local average.

    • Sharpening Filter Formula: Original+(Original−Smoothed)=Sharpened\text{Original} + (\text{Original} - \text{Smoothed}) = \text{Sharpened}. This can be represented as a single filter: [0,0,0;0,2,0;0,0,0]−[1,1,1;1,1,1;1,1,1]×19[0, 0, 0; 0, 2, 0; 0, 0, 0] - [1, 1, 1; 1, 1, 1; 1, 1, 1] \times \frac{1}{9}.

Image Support and Border Handling

  • The Edge Effect Problem: Computers convolve finite support signals. At the edges of an image, the filter kernel does not completely overlap the image pixels. Decisions must be made regarding the values used for pixels that are "off the image."

  • Common Border Handling Methods:

    • Zero-Padding: Values outside the image boundaries are assumed to be 0. This is often the default method.

    • Replication (Clamp): Each off-image pixel is replaced with the value from the nearest pixel within the image. Example: If the border is 9, the padding remains 9.

    • Reflection (Mirror): Pixel values are reflected at the border as if a mirror were present. Example sequence $1, 2, 3$ becoming $3, 2, 1$ across the boundary.

    • Wraparound (Torus): When going off the right border, the signal reappears on the left; leaving the bottom leads back to the top. The image is treated as a torus.

Mathematical Foundations of 1D and 2D Gradients

  • 1D Gradient Example: Consider the function f(x)=100−0.5×x2f(x) = 100 - 0.5 \times x^2.

    • The gradient is df(x)dx=−x\frac{df(x)}{dx} = -x.

    • Geometric Interpretation: The gradient at a point $x_0$ is the slope of the tangent line to the curve at that point (slope=ΔyΔxslope = \frac{\Delta y}{\Delta x}).

    • Sign and Direction:

      • A positive gradient indicates the direction to travel "uphill."

      • A negative gradient indicates traveling "downhill" toward lower values.

    • Magnitude: The magnitude of the gradient indicates the steepness of the slope.

  • 2D Gradient: For a function f(x,y)=100−0.5×x2−0.5×y2f(x, y) = 100 - 0.5 \times x^2 - 0.5 \times y^2, the gradient vector is:

    • Gradient=[∂f(x,y)∂x,∂f(x,y)∂y]=[−x,−y]\text{Gradient} = [\frac{\partial f(x, y)}{\partial x}, \frac{\partial f(x, y)}{\partial y}] = [-x, -y].

    • Let $g = [g_x, g_y]$ be the gradient vector at $(x_0, y_0)$.

    • $g$ points in the direction of steepest ascent.

    • $-g$ points in the direction of steepest descent.

    • The vector $[g_y, -g_x]$ is perpendicular to the gradient and denotes the direction of constant elevation (tangent to the contour line).

Edge Detection and the Impact of Noise

  • Discrete Derivative Filters: Derivatives can be implemented as 1D convolutions:

    • Backward filter: $[0, 1, -1]$

    • Forward filter: $[-1, 1, 0]$

    • Central filter: $[1, 0, -1]$

  • 3x3 Image Gradient Filters (Prewitt/Sobel style): Used to calculate horizontal and vertical gradients.

  • The Problem of Noise: Finite difference filters respond strongly to noise because noise creates sharp local differences between neighbors. As noise increases, the filter response strengthens, making it difficult to distinguish edges.

  • The Solution: Smoothing: Smoothing forces noise pixels to look more like their neighbors. To find edges in noisy images, one should smooth first and then apply the derivative.

  • Derivative of Gaussian (DoG) Filter: Based on the derivative theorem of convolution:

    • ∂∂x(h⋆f)=(∂h∂x)⋆f\frac{\partial}{\partial x}(h \star f) = (\frac{\partial h}{\partial x}) \star f

    • Instead of smoothing then differentiating, we can differentiate the Gaussian kernel itself and convolve the image with that derivative of Gaussian filter in one step.

Laplacian and Scale Space

  • Laplace Filter: A second-order finite difference filter $[1, -2, 1]$. In 2D, the Laplacian operator ∇2\nabla^2 is used.

  • Laplacian of Gaussian (LoG): Combines Laplacian filtering with Gaussian smoothing.

    • Edges are detected by looking for "zero crossings" in the LoG output.

    • Zero crossings are more accurate at localizing edges than first-derivative peaks, though they are less convenient to work with.

  • Approximating LoG: The LoG can be approximated by the Difference of two Gaussians (DoG) at different scales σ1\sigma_1 and σ2\sigma_2. A common ratio for approximation is σ1σ2≈1.6\frac{\sigma_1}{\sigma_2} \approx 1.6.

  • The Effect of Scale (σ\sigma):

    • The parameter σ\sigma is the width/spread of the Gaussian kernel.

    • Small σ\sigma: Finer features and smaller-scale edges are detected.

    • Large σ\sigma: Larger-scale structures are detected; noise is heavily suppressed, but edges become blurred.

The Fourier Series and Frequency Domain

  • Jean Baptiste Joseph Fourier (1768-1830): Proposed that any univariate periodic function can be rewritten as a weighted sum of sines and cosines of different frequencies.

    • Historical Context: The committee examining his 1807 paper (including Malus, Lagrange, Legendre, and Laplace) was skeptical due to a lack of rigorous proofs.

    • Amusing Aside: For 200 years, a portrait of Louis Legendre was misidentified as the mathematician Adrien-Marie Legendre; the only known portrait of the mathematician is a 1820 caricature by Julien-Leopold Boilly alongside Fourier.

  • Basic Building Block of Fourier Series: The sinusoid, defined by amplitude, angular frequency, and phase.

    • Square Wave Example: A square wave is an infinite sum of sine waves of increasing odd frequencies.

  • Visualizing the Frequency Spectrum: A plot of magnitude vs. frequency. In 1D, this looks like discrete bars for periodic signals. In 2D, frequency components correspond to spatial variations in $x$ and $y$ directions.

Fourier Transform and Filtering Properties

  • Complex Numbers Basics:

    • Rectangular: $a + bi$

    • Polar: (r,θ)(r, \theta)

    • Euler's Formula: eix=cos⁡(x)+isin⁡(x)e^{ix} = \cos(x) + i\sin(x)

  • The Fourier Transform Equations:

    • Continuous: F(ω)=∫−∞∞f(x)e−iωxdxF(\omega) = \int_{-\infty}^{\infty} f(x) e^{-i\omega x} dx

    • Inverse: f(x)=12π∫−∞∞F(ω)eiωxdωf(x) = \frac{1}{2\pi} \int_{-\infty}^{\infty} F(\omega) e^{i\omega x} d\omega

  • The Convolution Theorem: Convolution in the spatial domain is equivalent to multiplication in the frequency domain.

    • f⋆g  ⟺  F×Gf \star g \iff F \times G

  • Implementation: In practice, the Discrete Fourier Transform (DFT) is implemented using the Fast Fourier Transform (FFT) algorithm.

  • Natural Images: Image phase matters significantly more than amplitude for human perception of structure (as demonstrated by swapping cheetah phase with zebra amplitude).

  • Example Filters in Frequency Domain:

    • Low-Pass: Keeps low frequencies (center of the spectrum); results in blurring.

    • High-Pass: Keeps high frequencies; results in edge detection/sharpening.

    • Band-Pass: Keeps a specific range of frequencies.

Sampling, Aliasing, and the Nyquist Limit

  • Image Downsampling: Creating a smaller version of an image.

  • Sub-sampling: Throwing away rows and columns (e.g., delete every even row/column).

  • Aliasing: Undersampling can disguise a high-frequency signal as one of a lower frequency.

    • Temporal Aliasing: The "Wagon Wheel Effect" where a wheel rotating clockwise appears to rotate slowly counter-clockwise when captured at a low frame rate.

  • Anti-Aliasing Strategies:

    • Oversampling: Take more samples.

    • Smoothing (Pre-filtering): Apply a Gaussian low-pass filter before subsampling to remove frequencies that would cause aliasing.

  • Nyquist-Shannon Sampling Theorem: A continuous signal can be perfectly reconstructed if the sampling frequency is at least twice the highest frequency present in the signal.

    • Nyquist Frequency: fs=2×fmaxf_s = 2 \times f_{max}.

Gaussian and Laplacian Image Pyramids

  • Concept: A multi-resolution representation of an image.

  • Gaussian Pyramid:

    • Synthesis: Repeatedly smooth the image with a Gaussian and then downsample.

    • Association: Blurring decreases the Nyquist frequency to avoid aliasing artifacts during subsampling.

    • Cost: Dominated by convolution at the highest resolution levels.

  • Laplacian Pyramid: Represents the "details" lost at each level of the Gaussian pyramid.

    • Formula: Li=Gi−expand(Gi+1)L_i = G_i - \text{expand}(G_{i+1}).

    • Reconstruction: Gi=Li+expand(Gi+1)G_i = L_i + \text{expand}(G_{i+1}).

  • Human Sensitivity: The Campbell-Robson contrast sensitivity curve shows that human eyes are most sensitive to mid-range frequencies, which dominate perception.

Questions & Discussion

  • Question: Why does the Gaussian give a nice smooth image, but the square (box) filter give edgy artifacts?

  • Answer: In the frequency domain, the Fourier transform of a box filter is a sinc function, which has significant high-frequency components (side lobes) that cause ringing/edgy artifacts. The Fourier transform of a Gaussian is another Gaussian, which is smooth in both domains.

  • Question: How would you deal with aliasing?

  • Answer: Either oversample the signal or smooth the signal before subsampling to remove the detail effects that cause aliasing.