Image design and interaction technology based on Fourier inverse transform

Fourier transform (FT) is a very complicated analysis theory, but it plays an important role in image design and interactive technology. Especially for the discrete Fourier transform (DFT), since the image is a two-dimensional discrete data matrix based on the grey level (RGB), the implementation of FT on it belongs to the DFT. First, the image data is defined as x = 0, 1, ..., M − 1; y = 0, 1, ..., N − 1; then its DFT can be defined as F(u,v)=1MN∑x=0M−1∑y=0N−1f(x,y)exp[−i2π(uxM+vyN)] F\left( {u,v} \right) = {1 \over {MN}}\sum\limits_{x = 0}^{M - 1} \sum\limits_{y = 0}^{N - 1} f\left( {x,y} \right)\exp \left[ { - i2\pi \left( {{{ux} \over M} + {{vy} \over N}} \right)} \right]

One of them, one of the formulas u = 0, 1,..., M − 1;v = 0, 1,...,N − 1

The corresponding inverse transformation is: f(x,y)=1MN∑x=0M−1∑y=0N−1F(u,v)exp[−i2π(uxM+vyN)] f\left( {x,y} \right) = {1 \over {MN}}\sum\limits_{x = 0}^{M - 1} \sum\limits_{y = 0}^{N - 1} F\left( {u,v} \right)\exp \left[ { - i2\pi \left( {{{ux} \over M} + {{vy} \over N}} \right)} \right] One of them, one of the formulas x = 0, 1,...,M − 1, y = 0, 1,...,N − 1

During image processing, it is common to select square data, i.e. M = N. The amplitude spectrum or Fourier spectrum of the image f (x, y) is: |F(u,v)|=R2(u,v)+I2(u,v) \left| {F\left( {u,v} \right)} \right| = \sqrt {{R^2}\left( {u,v} \right) + {I^2}\left( {u,v} \right)} The phase spectrum is: ϕ(u,v)=arctg[I(u,v)/R(u,v)] \phi \left( {u,v} \right) = arctg\left[ {I\left( {u,v} \right)/R\left( {u,v} \right)} \right] The energy spectrum is: E(u,v)=F(u,v)|2=R2(u,v)+I2(u,v) E\left( {u,v} \right) = F\left( {u,v} \right)\left| {^2} \right. = {R^2}\left( {u,v} \right) + {I^2}\left( {u,v} \right)

In the case of a fast Fourier transform (FFT), the advantage of separability is that the two-dimensional FT or the inverse FT is implemented using two continuous one-dimensional FTs. For an image f (x, y), the one-dimensional FT can be calculated for each column, and then the one-dimensional transform can be performed for each row:

The forward transformation is: F(u,v)=1NN∑x=0N−1∑y=0N−1f(x,y)exp[−i2π(ux+vyN)]=1N∑x=0N−1f(x,y)exp[−i2π(uxN)]×1N∑y=0N−1f(x,y)exp[−i2π(vyN)] \matrix{ {F\left( {u,v} \right) = {1 \over {NN}}\sum\limits_{x = 0}^{N - 1} \sum\limits_{y = 0}^{N - 1} f\left( {x,y} \right)\exp \left[ { - i2\pi \left( {{{ux + vy} \over N}} \right)} \right] = } \hfill \cr {{1 \over N}\sum\limits_{x = 0}^{N - 1} f\left( {x,y} \right)\exp \left[ { - i2\pi \left( {{{ux} \over N}} \right)} \right] \times {1 \over N}\sum\limits_{y = 0}^{N - 1} f\left( {x,y} \right)\exp \left[ { - i2\pi \left( {{{vy} \over N}} \right)} \right]} \hfill \cr }

The inverse transformation is: F(u,v)=1NN∑u=0N−1∑v=0N−1f(u,v)exp[i2π(ux+vyN)]=1N∑u=0N−1f(u,v)exp[i2π(uxN)]×1N∑v=0N−1f(u,v)exp[i2π(vyN)] \matrix{ {F\left( {u,v} \right) = {1 \over {NN}}\sum\limits_{u = 0}^{N - 1} \sum\limits_{v = 0}^{N - 1} f\left( {u,v} \right)\exp \left[ {i2\pi \left( {{{ux + vy} \over N}} \right)} \right] = } \hfill \cr {{1 \over N}\sum\limits_{u = 0}^{N - 1} f\left( {u,v} \right)\exp \left[ {i2\pi \left( {{{ux} \over N}} \right)} \right] \times {1 \over N}\sum\limits_{v = 0}^{N - 1} f\left( {u,v} \right)\exp \left[ {i2\pi \left( {{{vy} \over N}} \right)} \right]} \hfill \cr }

Because of the separability of the two-dimensional FT, only the one-dimensional FFT is analysed, where the forward transform is [1]: F(u)=1N∑x=0N−1f(x)exp[−i2πuxN] F\left( u \right) = {1 \over N}\sum\limits_{x = 0}^{N - 1} f\left( x \right)\exp \left[ {{{ - i2\pi ux} \over N}} \right] The inverse transformation is: f(x)=1N∑u=0N−1F(u)exp[i2πuxN] f\left( x \right) = {1 \over N}\sum\limits_{u = 0}^{N - 1} F\left( u \right)\exp \left[ {{{i2\pi ux} \over N}} \right]

Since the running time of the computer will be affected by the number of multiplications, the one-dimensional discrete will undergo a FT from the spatial domain to the frequency domain according to the above formula, in which case all N of the N values of F (u) will undergo N operations, and the relationship between time and N2 is directly proportional [2, 3].

In the mid-1960s, Kuri Tuckey proposed an algorithm to reduce the operation to the order of Nlog 2N. In other words, N can be decomposed into the product of a large number of small integers. Therefore, when N is a power of 2 and P is an integer, the actual operation is the most efficient; moreover, the actual operation is also easier to implement. The actual operation is given by the FFT.

Since both u and v have 0,1 . . ., N−1, N possible value ranges, so f (x, y) contains N2 frequency components, and when (x, y) obtains all possible values, that is, in the case of x = 0, 1,...,N − 1;y = 0,1,...,N −1, a basic image corresponding to the special value (u, v) can be obtained, as shown below: fu,v=1N2{exp[j2π(0u+0vN)]exp[j2π(0u+1vN)]...exp[j2π(0u+(N−1)vN)]exp•••[j2π(1u+0vN)]exp[j2π(1u+1vN)]...•••exp[j2π(1u+(N−1)vN)]•••exp[j2π((N−1)u+0vN)]exp[j2π((N−1)u+1vN)]...exp[j2π((N−1)u+(N−1)vN)] {f_{u,v}} = {1 \over {{N^2}}}\left\{ {\matrix{ {\exp \left[ {j2\pi \left( {{{0u + 0v} \over N}} \right)} \right]\exp \left[ {j2\pi \left( {{{0u + 1v} \over N}} \right)} \right]...\exp \left[ {j2\pi \left( {{{0u + \left( {N - 1} \right)v} \over N}} \right)} \right]} \hfill \cr {ex\mathop p\limits_{ \bullet \matrix{ {} \cr { \bullet \matrix{ {} \cr \bullet \cr } } \cr } } \left[ {j2\pi \left( {{{1u + 0v} \over N}} \right)} \right]ex\mathop {p\left[ {j2\pi \left( {{{1u + 1v} \over N}} \right)} \right]...}\limits_{ \bullet \matrix{ {} \cr { \bullet \matrix{ {} \cr \bullet \cr } } \cr } } ex\mathop {p\left[ {j2\pi \left( {{{1u + \left( {N - 1} \right)v} \over N}} \right)} \right]}\limits_{ \bullet \matrix{ {} \cr { \bullet \matrix{ {} \cr \bullet \cr } } \cr } } } \hfill \cr {\exp \left[ {j2\pi \left( {{{\left( {N - 1} \right)u + 0v} \over N}} \right)} \right]\exp \left[ {j2\pi \left( {{{\left( {N - 1} \right)u + 1v} \over N}} \right)} \right]...\exp \left[ {j2\pi \left( {{{\left( {N - 1} \right)u + \left( {N - 1} \right)v} \over N}} \right)} \right]} \hfill \cr } } \right.

It can be seen that the average grey value of an image can be calculated by using the value of the DFT at the origin position:

First, we discuss symmetries about M/2, N/2. Assuming that F (x, y) is an image with a size of M × N, then according to the periodic formula analysis of the DFT, we can get: F(u,v)=F(u+mM,v+nN)|F(u,v)|=|F(u+M,v+N)| \matrix{ {F\left( {u,v} \right) = F\left( {u + mM,v + nN} \right)} \hfill \cr {\left| {F\left( {u,v} \right)} \right| = \left| {F\left( {u + M,v + N} \right)} \right|} \hfill \cr } At the same time, combined with the DFT of the conjugate symmetry formula analysis: |F(u,v)|=|F(−u,−v)| \left| {F\left( {u,v} \right)} \right| = \left| {F\left( { - u, - v} \right)} \right| Then we can get: |F(u,v)|=|F(M−u,N−v)| \left| {F\left( {u,v} \right)} \right| = \left| {F\left( {M - u,N - v} \right)} \right|

Then, under the condition of u=0, if n=0, then we can get: |F (0,0)| = |F (M,N)|

If v = 1, then we can get: |F (0,1)| = |F (M,N − 1)|

Similarly, under the condition of v = 0, if u = 0, then we can get: |F(0,0)| = |F(M,N)|

If u = 1, then we can get: |F (1,0)| = |F (M − 1,N)|

Combined with the analysis of the above two situations, the results as shown in Figures 1 and 2 below can be obtained:

In Figures 1 and 2, Block A, Block D, and Block B, Block C represent symmetric results of coordinates (M/2, N/2). Thus it can be proved that the relationship between periodicity and conjugate symmetry conforms to the following formula: F(u,v)=F(u+mM,v+Nn)F(u,v)=F(−u,−v) F\left( {u,v} \right) = F\left( {u + mM,v + Nn} \right)F\left( {u,v} \right) = F\left( { - u, - v} \right) At the same time, we can get: F(u+mN,v+nN)=1NN∑x=0N−1∑y=0N−1f(x,y)•exp[−i2π((u+mN)x+(v+nN)yN)]=1NN∑x=0N−1∑y=0N−1f(x,y)•exp[−i2π(ux+vyN)]•exp[−i2π(mx+ny)] \matrix{ {F\left( {u + mN,v + nN} \right) = {1 \over {NN}}\sum\limits_{x = 0}^{N - 1} \sum\limits_{y = 0}^{N - 1} f\left( {x,y} \right) \bullet } \hfill \cr {\exp \left[ { - i2\pi \left( {{{\left( {u + mN} \right)x + \left( {v + nN} \right)y} \over N}} \right)} \right]} \hfill \cr { = {1 \over {NN}}\sum\limits_{x = 0}^{N - 1} \sum\limits_{y = 0}^{N - 1} f\left( {x,y} \right) \bullet } \hfill \cr {\exp \left[ { - i2\pi \left( {{{ux + vy} \over N}} \right)} \right] \bullet } \hfill \cr {\exp \left[ { - i2\pi \left( {mx + ny} \right)} \right]} \hfill \cr } Where, since exp[−i2π (mx + ny)] represents the unit value, we can get: f(x,y)⋅(−1)(x+y)⇔F(u−M/2,v−N/2) f\left( {x,y} \right) \cdot {\left( { - 1} \right)^{\left( {x + y} \right)}} \Leftrightarrow F\left( {u - M/2,v - N/2} \right)