|
Given $f(x)$ and its FFT $F(u)$, I need to prove that $df/dx = F(u) * 2iu\pi /n.$ $df/dx = f'(x)$ and $n$ is the number of pixels of the one dimensional image $f$. I tried to use the convolution theorem using conv($f[1 -1]$) which is the same as $df/dx$ and in the frequency domain it's $F(u) * FFT([1 -1])$ however there sizes don't match. |
||||
|
|
This should have been a comment on the question but is too long to fit within the 500-character limit. The $f$ that is the subject of this question is a sequence or vector of $n$ numbers $$[f_0, f_1, \ldots, f_{n-1}] ~~ \text{or} ~~ \left[f[0], f[1], \ldots, f[n-1]\right] ~~ \text{or} ~~ \left[f(0), f(1), \ldots, f(n-1)\right]$$ depending on choice of notation, and its Discrete Fourier Transform (DFT) $F$ (called the FFT by the OP) is another sequence or vector of $n$ numbers. Thus, it is not clear what the derivative $\frac{\mathrm d}{\mathrm dx}f(x) = f^\prime(x)$ means since the argument of $f(\cdot)$ is an integer and not a continuous variable. One could attempt to make sense of what is intended by looking at the OP's approach to the problem via (cyclic or periodic) convolution with the sequence $[1, -1]$ (actually should have been $[1,-1,0,0,\ldots, 0]$ which results in replacing $f_i$ by $f_{i+1}-f_i$. Now, we are getting closer to the notion of differentiation since the derivative of a continuous function is obtained by looking at the limit of $\frac{f(x+h)-f(x)}{h}$ as $h \to 0$. Here we have the closest we can get since we are using $\frac{f(i+1)-f(i)}{1} = f_{i+1}-f_i$, and of course $1$ cannot "approach" $0$. Unfortunately, this does not give the desired result. The $k$-th term of the DFT of $[1,-1,0,0,\ldots, 0]$ is readily computed from the definition (no FFTs needed) as $1 - e^{-j2\pi k/n}$, and so the DFT of the "derivative" sequence $f_{i+1}-f_i$ has $k$-th term $F_k(1 - e^{-j2\pi k/n})$ which is not what the OP wants to prove. So, what does the OP want to prove? It is $\frac{\mathrm df}{\mathrm dx} \mathbf{=} F(u)*j(2\pi u/n)$. This needs clarification on two grounds. First, the left side of this equality is a function of $x$, the right side a function of $u$. So what does it mean to say the two are equal? Second, what the right side means needs clarification. Does the $*$ mean multiplication of the two complex numbers $F(u)$ and $j(2\pi u/n)$, or is the $*$ denoting complex conjugation of $F(u)$ before the multiplication, or does $*$ denote convolution so that $F(u)*j(2\pi u/n)$ means the $u$-th term of the (cyclic or periodic) convolution of the sequences $[F_0,F_1,\ldots,F_{n-1}]$ and $[1, j(2\pi/n),j(2\pi 2/n), \ldots, j(2\pi (n-1)/n)]$? The closest match occurs if we assume that $=$ is a typographical error and that what is meant is not the equality that the OP claims is needed. Instead, suppose that what was really asked for but mistranslated by the OP is that the $k$-th term of the DFT of $\frac{\mathrm df}{\mathrm dx}$ by which is meant the sequence with $i$-th term $f_{i+1}-f_i$ is $F_ke^{j2\pi k/n}$ (another typo, the missing exponential!). As noted above, this is not quite right: it should be $F_k(1 - e^{-j2\pi k/n})$. Note, incidentally, that the inverse DFT of the sequence with $k$-th term $F_ke^{j2\pi k/n}$ is a cyclic shift of the sequence $f$; see, for example, this Wikipedia entry But maybe as a non-expert in image processing I am missing something completely and so I await clarification from the OP, or perhaps a more detailed explanation from @JasonR of the method outlined in his comment on the OP's question. |
|||||||||
|
