#18 (11/06/2024)

Auto-correlation (Wiener-Khinchin's theorem)

The auto-correlation, R(x), of a function, f(x), represents a correlation between two points separated by x and is defined by

R(x) ≡

⌠
⌡

∞

−∞

f(y) f(y+x) dy,

(1)

i.e. comparing f at y and y+x (separated by x) and taking the average over y. Recalling that the convolution between f(x) and g(x) is defined as

f(x) ∗g(x) ≡

⌠
⌡

∞

−∞

f(x − y) g(y) dy,

(2)

it can be shown, by setting g(x) ≡ f(−x), that

R(x) = f(x) ∗f(−x).

(3)

Proof:

f(x)*f(−x)

⌠
⌡

∞

−∞

f(x−y) f(−y) d y

(Change the variable from y to z by −y ≡ z)

⌠
⌡

−∞

∞

f(x+z) f(z) d (−z)

⌠
⌡

∞

−∞

f(x+y) f(y) dy

R(x).

(4)

Wiener-Khinchin Theorem

The Fourier transform of the correlation function, R(x), is the power spectrum, P(ω), of f(x).

F(R(x)) = P(ω).

Proof:

Note that

F(f(−x))

⌠
⌡

∞

−∞

f(−x) e^{−i ωx} dx

⌠
⌡

∞

−∞

f(x) e^{i ωx} dx

F(f(x))

Therefore,

F(R(x))

F(f(x)*f(−x))

F( f(x)) F( f(−x))

F( f(x))

F(f(x))

| F( f(x))|²

P(ω).

Using the auto-correlation function to obtain the power spectrum is preferred over the direct Fourier transform as most of the signals have very narrow bandwidth.

Example:

f(x)=

⎧
⎪
⎨
⎪
⎩

|x| < 1

|x| > 1

F(ω) = 2 sin ω
ω
⇒ P(ω) = 4 sin²ω
ω²
.
R(x) = ⎧
⎪
⎨
⎪
⎩

2 +x
−2 < x < 0

2−x
0 < x < 2

0
otherwise

⇒

F(R(x)) = ⌠
⌡ 0

−2
(2+x)e^−iωx dx + ⌠
⌡ 2

0
(2−x)e^−iωx dx = 4 sin²ω
ω²
.

White noise, Pink noise, Brownian noise

If P(ω) is independent of the frequency, it is called white noise. If P(ω) is approximately proportional to 1/f ( = 1/ω), the original data is called pink noise, 1/f noise or fractal noise and if P(ω) is approximately proportional to 1/f², it is called brownian (red) noise.

White noise

Pink noise

Brownian (red) noise

Another site

Application of Fourier Transforms (Computed Tomography and Radon transforms)

Fourier Transforms in 2D

F. T.

I. F.T

F(ξ) =

⌠
⌡

∞

−∞

f(x) e^{−i ξx} dx

f(x) =

2π

⌠
⌡

∞

−∞

F(ξ)e^{i ξx} d ξ

F(ξ, η) ≡

⌠
⌡

∞

−∞

⌠
⌡

∞

−∞

f(x, y) e^{− i ( ξx + ηy)} dx dy

f(x, y) =

(2 π)²

⌠
⌡

∞

−∞

⌠
⌡

∞

−∞

F(ξ, η)e^{i (ξx + ηy)} dξdη

(5)

Radon Transforms

The Radon transform is defined as an integral of a two-dimensional density function, f(x, y), along the y′ axis as

R(x′, θ) ≡

⌠
⌡

∞

−∞

f(x, y) dy′,

(6)

where the (x′, y′) coordinate system is a rotation from the (x, y) coordinate system by θ given by

⎛
⎜
⎜
⎝

x′

y′

⎞
⎟
⎟
⎠

⎛
⎜
⎜
⎝

cos θ,

sin θ

− sin θ,

cos θ

⎞
⎟
⎟
⎠

⎛
⎜
⎜
⎝

⎞
⎟
⎟
⎠

(7)

Note that R(x′, θ) depends on x′ and θ.

The Fourier transform for a two variable function, f(x, y), is defined as

F(ξ, η) ≡

⌠
⌡

∞

−∞

⌠
⌡

∞

−∞

f(x, y) e^{− i ( ξx + ηy)} dx dy.

(8)

If the polar coordinate system, (ρ, θ), is introduced into the (ξ, η) system with

ξ = ρcos θ, η = ρsin θ,

(9)

ξx + ηy = ρ(x cos θ+ y sin θ) = ρx′.

(10)

F(ξ, η)

⌠
⌡

∞

−∞

⌠
⌡

∞

−∞

f(x, y) e^{− i ρx′} dx dy

⌠
⌡

∞

−∞

⌠
⌡

∞

−∞

f(x, y) e^{− i ρx′}

⎢
⎢

∂(x, y)

∂(x′, y′)

⎢
⎢

dx′d y′

⌠
⌡

∞

−∞

⌠
⌡

∞

−∞

f(x, y) e^{− i ρx′} dx′d y′

⌠
⌡

∞

−∞

⎛
⎝

⌠
⌡

∞

−∞

f(x, y) dy′

⎞
⎠

e^{− i ρx′} dx′

⌠
⌡

∞

−∞

R(x′, θ) e^{− i ρx′} dx′.

(11)

Thus, the Fourier transform of f(x, y) can be obtained by multiplying e^{− i ρx′} on the Radon transform of f(x, y) and integrating the result with respect to x′. The original image can be restored by the inverse Fourier transform defined as

f(x, y) =

(2 π)²

⌠
⌡

∞

−∞

⌠
⌡

∞

−∞

F(ξ, η)e^{i (ξx + ηy)} dξdη.

(12)

This is the principle of CT (computed tomography).

Trivial example

The Radon transform of the function,

f(x, y) ≡

⎧
⎪
⎨
⎪
⎩

x² + y² ≤ 1

otherwise

(13)

R(x′, θ) = 2

√

1 − x′²

(14)

Figure 1: Radon transform R(x′, θ) of f(x, y).

Therefore, the Fourier transform of f(x, y) is given by

F(ξ, η)

⌠
⌡

∞

−∞

√

1 − x′²

e^{− i ρx′} dx′

⌠
⌡

1

−1

√

1 − x′²

e^{− i ρx′} dx′

2 πJ₁(ρ)

(15)

where J₁(ρ) is the Bessel function of the first kind.

Figure 2: Fourier transform of R(x′, θ).

The inverse Fourier transform of the above is

f(x, y)

4π²

⌠
⌡

2π

0

⌠
⌡

∞

0

2 πJ₁(ρ)

e^{i (x ξ+ y η)}ρ dρ dθ

4 π²

⌠
⌡

2 π

0

⌠
⌡

∞

0

2 πJ₁(ρ)

e^{i ρ(x cos θ+ y sin θ)} ρ d ρ dθ

…

⎧
⎪
⎨
⎪
⎩

x² + y² < 1

x² + y² > 1

(16)

Figure 3: Inverse Fourier transform of F(ρ, θ).

Example:

Original image

Radon transform

Inverse Radon transform

File translated from T_EX by T_TH, version 4.03.
On 05 Nov 2024, 18:14.