Understanding Orthogonal Transform

Orthogonal Transform

• The basis polynomials/functions of a transform are orthogonal making it an orthogonal transform
• Orthogonal polynomials (OP) are a family of polynomials
• Any two different polynomials in the sequence are orthogonal to each other under some inner product
• The orthogonality condition for an OP:
  • ∑ Rₙ(x)Rₘ(x) ω(x) = ρ(η)δₙₘ, summed from x=0 to N-1
  • n, m = 0, 1, 2, ..., N – 1
  • ρ(η) is the squared norm of OP
  • ω(x) is the weight function
  • δₙₘ is the Kronecker delta
• The weighted normalized form is for calculating polynomial coefficients:
  • Rₙ(x) = Rₙ(x) * sqrt(ω(x) / ρ(η))
• The orthogonality condition can be written as:
  • Σ Rₙ(x)Rₘ(x) ω(x) = ρ(η)δₙₘ (summed from x=0 to N-1)
  • Σ Rₙ(x)Rₘ(x) = δₙₘ (summed from x=0 to N-1)
• In matrix multiplication:
  • R × R' = I
  • If the weighted normalized form of the polynomial is used to calculate the polynomial coefficients, the polynomial is orthonormal
  • The transformation is invertible and is called a unitary transform
  • R⁻¹ = R', where R' = R*ᵀ
  • • represents complex conjugate
  • T represents the transpose of a matrix

Transforming Signals

• To transform a 1-D signal from time to transform domain:
  • F(n) = Σ Rₙ(x) f(x) from x=0 to N-1
  • In matrix multiplication, F = R × f
  • f should be a column vector
• To reconstruct the signal from the transform domain using inverse transformation:
  • f(x) = Σ Rₙ(x) F(n) from n=0 to N-1
  • In matrix multiplication, f = R' × F

Transforming 2D Signals

• To transform a 2-D signal from time to transform domain:
  • F(n, m) = ΣΣ Rₙ(x, Nₓ)Rₘ(y, Nᵧ)f(x, y) summed from x=0 to Nₓ-1 and y=0 to Nᵧ-1
  • In matrix multiplication, F = Rᵧ × f × R'ₓ
• To reconstruct the signal from the transformation domain using inverse transformation:
  • f(x, y) = ΣΣ Rₙ(x, Nₓ)Rₘ(y, Nᵧ)F(n, m) summed from n=0 to Nₓ-1 and m=0 to Nᵧ-1
  • In matrix multiplication, f = R'ᵧ × F × Rₓ
• When the matrix is square (Nₓ = Nᵧ):
  • Rₓ = e^(-j2π(nx/Nₓ))
  • Rᵧ = e^(-j2π(my/Nᵧ))
  • Rₓ = Rᵧ

Fourier Transform

• Defines a traditional way of processing signals
• Introduces the basics of the Fourier transform and Fourier filtering
• High-frequency and low-frequency information in an image is explained
• The 2D Fourier transform maps an image from its spatial domain into the frequency domain (Transform Domain)
• The transform domain provides a different but mathematically equivalent representation

Fourier series

• A function f is resolved into Fourier series as a linear combination of sines and cosines
• The component frequencies of sines and cosines spread across the frequency spectrum and are represented as peaks in the frequency domain (Dirac delta functions)
• The frequency domain representation of f is the collection of peaks at the frequencies that appear in this resolution

Fourier Transform Equations

• 1D Fourier Transform:
  • F(ωₓ) = ∫ f(x) e^(-j(ωₓx)) dx integral from -∞ to ∞
• 2D Fourier Transform:
  • F(ωₓ, ωᵧ) = ∫∫ f(x, y) e^(-j(ωₓx))e^(-j(ωyy)) dx dy integral from -∞ to ∞
  • F(ωₓ, ωᵧ) = ∫∫ f(x, y) e^(-j(ωₓx + ωyy)) dx dy integral from -∞ to ∞

Discrete Fourier Transform

• 1D discrete Fourier Transform:
  • F(n) = Σ f(x) e^(-j2π(nx/Nₓ)) from x=0 to Nₓ-1
• 2D discrete Fourier Transform:
  • F(n, m) = ΣΣ f(x, y) e^(-j2π(nx/Nₓ)) e^(-j2π(my/Nᵧ)) from x=0 to Nₓ-1 and y=0 to Nᵧ-1
  • F(n, m) = ΣΣ f(x, y) e^(-j2π((nx/Nₓ) + (my/Nᵧ))) from x=0 to Nₓ-1 and y=0 to Nᵧ-1
• Euler's formula:
  • e^(jα) = cos α + j ⋅ sin α
  • j = √-1

Inverse Discrete Fourier Transform

• 1D inverse discrete Fourier Transform:
  • f(x) = (1/Nₓ) Σ F(n) e^(j2π(nx/Nₓ)) from kₓ=0 to Nₓ-1
• 2D inverse discrete Fourier Transform:
  • f(x, y) = (1/NₓNᵧ) ΣΣ F(n, m) e^(j2π(nx/Nₓ)) e^(j2π(my/Nᵧ)) from kₓ=0 to Nₓ-1 and kᵧ=0 to Nᵧ-1
  • f(x, y) = (1/NₓNᵧ) ΣΣ F(n, m) e^(j2π((nx/Nₓ) + (my/Nᵧ))) from kₓ=0 to Nₓ-1 and kᵧ=0 to Nᵧ-1

Orthogonality of DFT

• The OP for DFT is Rₙ(x) = e^(-i2π(nx/N))
• Σ Rₙ(x)Rₘ(x) = Σ e^(-i2π(nx/N)) e^(+i2π(mx/N)) = Σ e^((i2π/N)x(n-m)) summed from x=0 to N-1
• Let N = 4:
  • Σ e^((i2π/4)x(n-m)) = Σ e^((iπ/2)x(n-m)) summed from x=0 to 3
  • e⁰ + e^(-iπ/2) (n-m) + e^(-iπ(n-m)) + e^(i3π/2) (n-m)
  • 1 + cos((π/2)(n-m)) + i sin((π/2)(n-m)) + cos(π(n-m)) + i sin(π(n-m)) + cos((3π/2)(n-m)) + i sin((3π/2)(n-m))
  • 1 + 2 cos(π(n-m)) cos((π/2)(n-m)) + i2 sin(π(n-m)) cos((π/2)(n-m)) + cos(π(n-m)) + i sin(π(n-m))
  • 1 + 2 cos(π(n-m)) cos((π/2)(n-m)) + cos((π/2)(n-m))
  • 1 + cos((π/2)(n-m)) (2cos(π(n-m)) + 1)
  • 1 + cos((π/2)(n-m)) (2 cos(π(n-m)) + 1) → (-1)^(n-m)
  • 1 + cos((π/2)(n-m)) (1 + 2(-1)^(n-m))
• If n = m:
  • 1 + 1 × (2 + 1) = 4
• If n ≠ m:
  • 1 + cos((π/2)(n-m)) (1 - 2) = 0, because n + m are always odd
• The orthogonality condition in terms of matrix multiplication:
  • If N = 4, Rₙ(x) = e^(-i2π(nx/N))
  • R = a 4x4 matrix in terms of i, -i, 1, and -1
  • R' = R*ᵀ
  • R × R' = a 4x4 matrix with the diagonal as 4 and the rest of the elements at 0

Properties of Discrete Fourier Transform

• Superposition: f1 + f2 transforms to F1 + F2
• Shift: f(x - x₀) transforms to F(k)e^(-jw x₀)
• Reversal: f(-x) transforms to F*(ω)
• Convolution: f(x) * h(x) transforms to F(k)H(k)
• Correlation: f(x) ⊗ h(x) transforms to F(k)H*(k)
• Multiplication: f(x)h(x) transforms to F(k) * H(k)
• Differentiation: f'(x) transforms to jkF(k)
• Domain scaling: f(ax) transforms to 1/a F(k/a)
• Real images: f(x) = f*(x)
• Parseval Theorem: Σₓ[f(x)]² = Σₖ[F(k)]²

Example 1

• Given matrix I = [[4, 5], [2, 1]]
• F(n,m) = ΣΣ f(x,y) e^(-j2π(nx/Nₓ)) e^(-j2π(my/Nᵧ)) from x=0 to Nₓ-1 and y=0 to Nᵧ-1
• f(x, y) = [[f(0,0), f(1,0)], [f(0,1), f(1,1)]]
• Nₓ = 2, Nᵧ = 2
• F(n,m) = ΣΣ f(x,y) e^(-j2π(nx/2)) e^(-j2π(my/2)) from x=0 to 1 and y=0 to 1
• f(x, y) e^(iπnx) e^(iπmy)
• F(n,m) = [[F(0,0), F(1,0)], [F(0,1), F(1,1)]]
• F(0,0) = f(0,0) e^(iπ⋅0⋅0) e^(iπ⋅0⋅0) + f(0,1) e^(iπ⋅0⋅0) e^(iπ⋅0⋅1) + f(1,0) e^(jπ⋅0⋅1) e^(iπ⋅0⋅0) + f(1,1) e^(iπ⋅0⋅1) e^(iπ⋅0⋅1)
• F(0,1) = f(0,0) e^(iπ⋅0⋅0) e^(iπ⋅1⋅0) + f(0,1) e^(iπ⋅0⋅0) e^(↑π⋅1⋅1) + f(1,0) e^(iπ⋅0⋅1) e^(iπ⋅1⋅0) + f(1,1) e^(iπ⋅0⋅1) e^(↑π⋅1⋅1)
• F(1,0) = f(0,0) e^(iπ⋅1⋅0) e^(iπ⋅0⋅0) + f(0,1) e^(↑π⋅1⋅0) e^(iπ⋅0⋅1) + f(1,0) e^(↑π⋅1⋅1) e^(iπ⋅0⋅0) + f(1,1) e^(↑π⋅1⋅1) e^(iπ⋅0⋅1)
• F(1,1) = f(0,0) e^(iπ⋅1⋅0) e^(iπ⋅1⋅0) + f(0,1) e^(↑π⋅1⋅0) e^(↑π⋅1⋅1) + f(1,0) e^(↑π⋅1⋅1) e^(iπ⋅1⋅0) + f(1,1) e^(↑π⋅1⋅1) e^(↑π⋅1⋅1)
• F(0,0) = f(0,0) ⋅ 1 ⋅ 1 + f(0,1) ⋅ 1 ⋅ 1 + f(1,0) ⋅ 1 ⋅ 1 + f(1,1) ⋅ 1 ⋅ 1
• F(0,1) = f(0,0) ⋅ 1 ⋅ 1 + f(0,1) ⋅ 1 ⋅ (-1) + f(1,0) ⋅ 1 ⋅ 1 + f(1,1) ⋅ 1 ⋅ (-1)
• F(1,0) = f(0,0) ⋅ 1 ⋅ 1 + f(0,1) ⋅ 1 ⋅ 1 + f(1,0) ⋅ (-1) ⋅ 1 + f(1,1) ⋅ (-1) ⋅ 1
• F(1,1) = f(0,0) ⋅ 1 ⋅ 1 + f(0,1) ⋅ 1 ⋅ (-1) + f(1,0) ⋅ (-1) ⋅ 1 + f(1,1) ⋅ (-1) ⋅ (-1)
• F(0,0) = f(0,0) + f(0,1) + f(1,0) + f(1,1) = 12
• F(0,1) = f(0,0) - f(0,1) + f(1,0) - f(1,1) = 0
• F(1,0) = f(0,0) + f(0,1) - f(1,0) - f(1,1) = 6
• F(1,1) = f(0,0) - f(0,1) - f(1,0) + f(1,1) = -2
• The transformed matrix I = [[12, 0], [6, -2]]
• Magnitude matrix ||I||= [[12, 0], [6, 2]]
• Angle matrix angle(I) = [[0, 0], [0, 180]]
• Magnitude of elements √real² + img²
• Angle of elements tan⁻¹(img/real)
• If real = 0, img = ± any number, then angle = ± 90
• If real = +, img = 0, then angle = 0
• If real = -, img = 0, then angle = 180

Example 2

• Given matrix I = [[4, 5, 6, 7], [2, 1, 8, 9], [2, 5, 4, 6]]
• The tranformed matrix I = [[59, -10 - 11i, -7, -10 + 11i], [3.5 - 2.59i, -4.06 + 5.96i, 0.5 + 4.33i, 8.06 + 0.96i], [3.5 + 2.59i, 8.06 - 0.96i, 0.5 + 4.33i, -4.06 - 5.96i]]
• Magnitude matrix ||I|| = [[59, 14.86, 7, 14.87], [4.36, 7.22, 4.36, 8.12], [4.36, 8.12, 4.36, 7.22]]
• Angle matrix angle(I) = [[+000.00, -132.27, +180.00, +132.27], [-036.59, +124.56, -083.41, +006.82], [+036.59, -006.82, +083.41, -124.26]]