Fourier Transform and Filters

Fourier Transform and Filters

• Fourier Transform decomposes a signal into its frequency components.
• This helps understand how filters manipulate different frequency ranges, changing the original signal.

Types of Filters

• Filters affect signals based on frequency.
• There are different filter categories which include low-pass, high-pass, and band-pass filters.
• Low-pass filters pass low frequencies while attenuating high frequencies; they smooth signals and remove high-frequency noise.
• High-pass filters pass high frequencies and attenuate low frequencies; useful for edge detection and removing low-frequency hum.
• Band-pass filters pass a specific range of medium frequencies and are used in feature extraction and texture analysis.
• Filter analysis involves passing a sinusoid of known frequency through the filter.
• Attenuation observation helps determine effects on high, medium, and low frequencies.
• Each filter has a frequency response that shows how much the filter attenuates different frequencies (similar to a Fourier Transform output).

Sinusoidal Signals

• Defined as a periodic signal with a waveform like a sine wave
• Sine wave amplitude increases from 0 at 0° to a maximum of 1 at 90°, reaches -1 at 270°, and returns to 0 at 360°.
• After 360°, the sinusoidal signal repeats, with a time period of 2π (360°).

Sinusoidal Signal Parameters:

• Time period: Time taken by a periodic signal to complete one cycle.
• Amplitude (A): Maximum distance between the horizontal axis and the vertical position of any signal.
• Frequency (f): Number of times a signal oscillates in one second (reciprocal of the period).
• Phase (ɸ): Horizontal position of a waveform in one oscillation (indicated by θ).

Sinusoids for Analyzing Filters

• Sinusoids of known frequencies are passed through filters to analyze filter behavior on different frequency ranges.
• Sinusoidal signal equation: 𝑠(𝑥) = 𝑠𝑖𝑛(2𝜋𝑓𝑥 +ɸ𝑖) = 𝑠𝑖𝑛(𝜔𝑥 +ɸ𝑖), where 𝑓 is frequency, 𝜔 = 2𝜋𝑓 is angular frequency, and ϕ𝑖 is the phase.
• Convolving a sinusoidal signal 𝑠(𝑥) with a filter ℎ(𝑥) yields another sinusoid of the same frequency but different magnitude A and phase ϕ𝑜: 𝑜(𝑥) = ℎ(𝑥) ∗ 𝑠(𝑥) = 𝐴 𝑠𝑖𝑛(𝜔𝑥 +ɸ𝑜)
• Magnitude change indicates the filter's effect on the original sinusoid, large changes mean a strong effect, and minimal changes mean the filter passes the signal nearly unaffected.
• Many filters also introduce a phase shift, delaying or advancing the output sinusoid relative to the original.

Fourier Transform (FT) as a Filter Response Tool

• FT output, H(ω), is a complex number that represents the magnitude change (A) and phase shift (φ) that the filter F causes at each frequency (ω).
• Magnitude (A) indicates how much a frequency is amplified or attenuated by the filter F.
• Phase Shift (φ) reveals any delay or advancement in the timing caused by the filter F.

Discrete Fourier Transform (DFT) & Fast Fourier Transform (FFT)

• Discrete Fourier Transform (DFT) is for digital signals (sampled data).
• The DFT takes O(N2) operations
• Fast Fourier Transform (FFT) is an efficient algorithm to compute the DFT quickly.
• The FFT takes O(N log2 N) operations.
• FT is applied to continuous signals, while DFT is used for discrete sampled signals.
• Box-3 and Box-5 are smoothing filters (low-pass filters) that blur the image by averaging neighboring pixel values.
• Linear is a smoothing filter, similar to Box-3 but with weights that slightly emphasize the center pixel more than its neighbors.
• Binomial is similar to the Gaussian filter and it is used for blurring while reducing noise with a smoother transition.
• Sobel is an edge detection filter emphasizes horizontal or vertical gradients in the image.
• Corner is used to detect corners in images, highlighting areas where intensity changes in multiple directions.

Two-Dimensional Fourier Transforms

• Image is a 2D function of position (x, y).
• The 2D FT analyzes the frequency content of an image across both horizontal and vertical directions (𝜔𝑥, 𝜔𝑦).
• N and M are the width and height of the image.

Applications of Fourier Transforms

• Understanding Image Content: Provides insights into image characteristics.
• High frequencies correspond to rapid changes like sharp details and edges.
• Low frequencies represent slow, smooth variations and overall background.
• Image Enhancement:
  • Sharpening: Enhances edges and details by amplifying high-frequency components.
  • Blur Removal: Undoes blurring effects in the Fourier domain if the blur type is known.
  • Noise Removal (denoising): Reduces high frequencies to remove noise while keeping important details like edges and textures.

Evaluation of Image Denoising Algorithms

• Effectiveness is measured using:
  • PSNR (Peak Signal-to-Noise Ratio): Compares the denoised image to the original.
  • SSIM (Structural Similarity Index): Compares the denoised image to the original, reflecting human perception.
  • FLIP (Flicker Perception): Evaluates the smoothness of a video or image sequence by focusing on flicker or temporal artifacts.
  • Neural Networks: Can be used for no-reference assessment when the original image is unknown.

Image Resizing, Pyramids and Applications

• Reasons for resizing:
  • Match output device resolution.
  • Reduce file size for storage/transmission.
  • Optimize algorithm speed.
  • Find objects at different scales.
  • Enable advanced image editing like seamless blending.
• Techniques:
  • Upsampling (Interpolation) for enlarging images.
  • Downsampling (Decimation) for shrinking images.
  • Multi-Resolution Pyramids for a structured set of resized images.

Image Resizing

• Interpolation for Upsampling: Enlarging images using an interpolation kernel that is convolved with the image.
• Kernel Types:
  • Linear (Bilinear): Simple but can create jagged edges.
  • Bicubic: Common choice, smoother results.
  • Windowed Sinc: Highest quality, but can introduce ringing.
• Decimation or Downsampling Images: Reducing image resolution.
• Decimation Process:
  • Convolving the image with a low-pass filter to prevent aliasing.
  • Evaluating the convolution at every 𝑟𝑡ℎ sample to optimize computation, such that image 𝑔(𝑖,𝑗) is computed as a convolution of the original image 𝑓(𝑘,𝑙) with a filter ℎ, but only at every 𝑟𝑡ℎ sample.
• Common Filters for Decimation:
  • Commonly used r = 2 downsampling filters: Linear, Binomial, Cubic.
  • Binomial is better than linear but leaves some aliasing.
  • Cubic (a= -1) suppresses aliasing well but can introduce ringing.
  • Advanced Filters: QMF-9, JPEG2000 filters for specific tasks.
• Coefficients change based on the distance from the center pixel (∣𝑛∣), with higher values at the center (0) to give more weight to central pixels.
• The further from the center, the lower the weight, reflecting their reduced contribution in smoothing. Each filter is symmetric and designed to preserve overall image brightness while reducing aliasing.

Multi-Resolution Representations

• Multi-Resolution Analysis: Understanding signals and images at different scales of detail.
• Varying Scales: Analyzing both large-scale and fine-scale details.
• Applications:
  • Image Compression: Efficiently storing images by focusing on the most important details across scales.
  • Feature Detection: Finding key image points or regions that remain informative even when the image is resized.

Image Pyramids Overview

• Structure: Hierarchical series of images, where each level is a lower-resolution version of the previous one.
• Progressive Resolution Reduction:
  • Downsampling: Halving the size (width/height) creates a pyramid where each level has ¼ the number of pixels.
  • Filtering: Prevents aliasing during downsampling.
• Types:

Guassian Pyramid

- Created by repeated smoothing and downsampling.

Construction:

- Repeatedly blur the image with a Gaussian filter.
- Downsample by a factor of 2 to create subsequent levels.

• Binomial Filter: Offers a good balance between simplicity and quality, computationally inexpensive approximation of a Gaussian blur (efficient).
• Applications: Foundation for other pyramids, feature detection across scales.
• Laplacian Pyramid: Stores detail differences between levels, allowing reconstruction.

Storing the Detail

• Laplacian Pyramid holds the difference between the Gaussian levels.

Construction

- Upsample a lower-resolution Gaussian level.
- Subtract this from the higher-resolution level to get the Laplacian image.

• Perfect Reconstruction: Laplacian images + the smallest Gaussian level can fully reconstruct the original image.

Wavelet Pyramids

- Capture directional image detail for various applications.

Frequency Responses of Filters

• Show how filters affect different frequencies in the image.
• Sharp Cutoff vs. Aliasing:
  • Ideal filters have sharp cutoffs, but they are harder to implement.
  • Simpler filters leave more aliasing.
• Applications Dictate Choices: The best filter depends on the task's sensitivity to artifacts and its computational limitations.

Applications of Image Pyramids

• Coarse-to-Fine Search: Finding objects efficiently by starting at a coarse level and refining at finer levels.
• Multi-Resolution Blending: Seamlessly blend images of different resolutions.
• MIP-Mapping (Graphics): Fractional-level scaling without blockiness.
• Medical Whole Slide Imaging.