Transform Techniques & Frequency Domain Analysis

TAKEAWAYS:

• Frequency domain reveals image patterns (edges, textures) as sinusoidal components, enabling selective filtering (e.g., noise removal).
• Discrete Fourier Transform (DFT) converts spatial-domain pixels into frequency-domain coefficients, where high frequencies = sharp changes (edges).
• Fast Fourier Transform (FFT) accelerates DFT computation from O(N²) to O(N log N), critical for real-time processing (e.g., video streaming).
• Wavelet transforms localize frequency information in time/space, ideal for multi-scale analysis (e.g., seismic data, speech signals).
• Hadamard transform offers faster computation than DFT for specific applications like image compression.
• Hough transform detects geometric shapes (lines, circles) by transforming edge points into parameter space.

---

1. Spatial vs. Frequency Domain

• Spatial domain: Pixels and their intensities (e.g., a grayscale image as a matrix).
• Frequency domain: Image decomposed into sine/cosine waves (frequencies).

Why switch domains?

• Filtering: Remove noise (high frequencies) or enhance edges (mid frequencies).
• Compression: Discard high-frequency components (e.g., JPEG).
• Pattern recognition: Detect periodic structures (e.g., textures, repeating patterns).

---

2. Discrete Fourier Transform (DFT)

The DFT converts a finite sequence of equally-spaced samples into components of different frequencies.

1D DFT Formula

For a signal $x[n]$ of length $N$: $$X[k]=\sum _{n=0}^{N-1}x[n]\cdot e^{-i2\pi kn/N},k=0,1,\dots ,N-1$$

• $X[k]$: Frequency-domain coefficient for frequency $k$.
• $e^{-i2\pi kn/N}$: Complex exponential (rotating vector in the complex plane).

2D DFT (for Images)

For an $M\times N$ image $f(m,n)$: $$F(u,v)=\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}f(m,n)\cdot e^{-i2\pi (um/M+vn/N)}$$

Visualization of 2D DFT Consider a 2×2 image (simplified for clarity):

1  1
1  1

Its 2D DFT (computed via formula) yields: $$F(u,v)=\left[\begin{array}{cc}4& 0\\ 0& 0\end{array}\right]$$

• Interpretation: Only the DC component (constant frequency) is non-zero; no high-frequency edges.

---

3. Fast Fourier Transform (FFT)

The FFT algorithm reduces DFT computation from O(N²) to O(N log N), enabling real-time processing.

Key Properties of FFT

Example: FFT of a 4-point sequence Given $x[n]=\{1,2,0,3\}$, compute its DFT using FFT steps:

1. Divide into even/odd:
   • Even: $x[0],x[2]=\{1,0\}$
   • Odd: $x[1],x[3]=\{2,3\}$
2. Recursively compute DFTs of even/odd sequences.
3. Combine results using twiddle factors $W_N^k$.

Output: $$X[k]=\{6,-1+1i,0,-1-1i\}$$

---

4. Hadamard Transform

A binary transform (uses ±1 instead of complex exponentials) with faster computation than DFT for certain applications.

Hadamard Matrix

For $N=4$: $$H_4=\left[\begin{array}{cccc}+1& +1& +1& +1\\ +1& -1& +1& -1\\ +1& +1& -1& -1\\ +1& -1& -1& +1\end{array}\right]$$

Hadamard Transform of $\{1,2,0,3\}$

Multiply input by $H_4$ and normalize: $$Y=\frac{1}{4}{H}_4\cdot X=\left[\begin{array}{c}2\\ -0.5\\ 1\\ 1.5\end{array}\right]$$

Advantages:

• No complex arithmetic (faster for some hardware).
• Used in image compression (e.g., Hadamard coding).

Disadvantages:

• Less accurate for smooth signals compared to DFT.

---

5. Wavelet Transform

Unlike Fourier, wavelets provide time-frequency localization, useful for multi-scale analysis.

Wavelet Decomposition

A signal is decomposed into:

• Approximation coefficients (low-frequency, smoothed version).
• Detail coefficients (high-frequency, edges/transients).

Example: Haar Wavelet For $x=\{1,2,3,4\}$:

1. First level:
   • Approximation: $\{2,3\}$ (average of pairs).
   • Detail: $\{-0.5,0.5\}$ (differences).
2. Second level:
   • Approximation: $\{2.5\}$.
   • Detail: $\{-0.25\}$.

Applications:

• Medical imaging: Localize tumors in MRI scans.
• Speech processing: Isolate phonemes in audio.

---

6. Hough Transform

Detects geometric shapes (lines, circles) by transforming edge points into parameter space.

Line Detection

For an edge point $(x,y)$, the line equation is: $$x\cos \theta +y\sin \theta =r$$

• Hough space: Accumulate votes for $(r,\theta )$ pairs where the edge lies on the line.

Example: Collinearity Check Given points $(1,1),(-2,7),(3,3)$:

1. For $(1,1)$, compute $r=x\cos \theta +y\sin \theta$ for all $\theta$.
2. Repeat for other points; check if any $(r,\theta )$ has 3 votes.

Result: All points lie on the line $y=x+2$.

---

7. Frequency Domain Filtering

Filters operate in the frequency domain to modify image properties.

Types of Filters

Example: Laplacian Filter in Frequency Domain The Laplacian kernel in spatial domain: $$\left[\begin{array}{ccc}0& -1& 0\\ -1& 4& -1\\ 0& -1& 0\end{array}\right]$$ In frequency domain, it corresponds to: $$-4(\cos 2\pi u+\cos 2\pi v)+16$$

• Effect: Amplifies high frequencies (edges).

---

In the Real World

1. eSewa/Khalti (Payment Apps)

   • Idea: Wavelet transforms compress transaction logs to detect fraud patterns (e.g., sudden spikes in payments).
   • How: Wavelets isolate anomalies in time-series data (e.g., a sudden 100x increase in transactions at 3 AM).

2. NEPSE (Stock Market)

   • Idea: Fourier analysis smooths stock price data to remove noise and identify trends.
   • How: Low-pass filtering in the frequency domain removes high-frequency volatility, revealing long-term patterns.

3. Pathao (Ride-Hailing)

   • Idea: Hough transform detects traffic bottlenecks by analyzing GPS data points.
   • How: Edge points (stagnant vehicles) are transformed into lines representing traffic jams.

Worked Example: Daraz Order Queue

• Scenario: Daraz’s warehouse uses FFT-based pattern recognition to predict order peaks.
• Steps:
  1. Collect hourly order counts as a time-series signal.
  2. Apply FFT to decompose into frequency components.
  3. Identify dominant frequencies (e.g., daily peak at 10 AM).
  4. Allocate staff dynamically to reduce delays.

---

8. Comparison Table: Transform Techniques

---

Exam Tip

1. DFT vs. FFT:

   • Always mention that FFT is an algorithm to compute DFT efficiently.
   • For 2D DFT, show the double-sum formula and emphasize symmetry (real images have conjugate symmetry).

2. Frequency Domain Filtering:

   • Link high-pass/low-pass filters to real-world examples (e.g., "A high-pass filter in medical imaging enhances bone edges").
   • For Laplacian, state it’s a second derivative in spatial domain → high-frequency emphasis in frequency domain.

3. Wavelet Transform:

   • Highlight its multi-resolution property: "Wavelets decompose an image into scales (e.g., coarse to fine details)."
   • Compare with Fourier: "Fourier tells you what frequencies are present; wavelets tell you where."

4. Hough Transform:

   • For collinearity, show the parameter space (r-θ plane) and explain how peaks indicate lines.
   • Mention circular Hough transform for detecting circles (if time permits).

5. Hadamard Transform:

   • Emphasize its binary nature: "No complex arithmetic → faster for some hardware."
   • Relate to compression: "Used in lossless coding (e.g., image files)."

6. Numerical Problems:

   • For DFT/FFT computations, show all steps (even if simplified). Use small matrices (2×2 or 4×4) to avoid errors.
   • For histogram equalization in frequency domain, assume the question implies contrast stretching via FFT-based filtering.

---

Final Visual Recap