Mixing
The mathematics behind Fourier Transform for Image Processing
$begingroup$
I am following http://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm . I understand the application of Fourier Transform behind Image Processing, but right now, I am curious about the mathematics behind it, and it is giving me a bit of a hard time.
For example:
In this formula, where do all these equations come from? Could somebody please elaborate the mathematics behind the scene in layman's term?
fourier-analysis image-processing
asked Aug 28 '12 at 9:00
KarlKarl
420718
$endgroup$
add a comment |
$begingroup$
I am following http://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm . I understand the application of Fourier Transform behind Image Processing, but right now, I am curious about the mathematics behind it, and it is giving me a bit of a hard time.
For example:
In this formula, where do all these equations come from? Could somebody please elaborate the mathematics behind the scene in layman's term?
fourier-analysis image-processing
asked Aug 28 '12 at 9:00
KarlKarl
420718
$endgroup$
2
$begingroup$
Did you check en.wikipedia.org/wiki/Discrete_Fourier_transform ?
$endgroup$
– Zeta.Investigator
Aug 28 '12 at 9:08
$begingroup$
Yes, I did, but my head spins even further.
$endgroup$
– Karl
Aug 28 '12 at 9:24
$begingroup$
Explain the Fourier transform in layman's terms you say?
$endgroup$
– Rahul
Aug 28 '12 at 9:39
2
$begingroup$
An interesting explanation, to be sure... but I think I prefer to think about it in terms of orthogonal bases in inner product spaces.
$endgroup$
– Zhen Lin
Aug 28 '12 at 9:40
add a comment |
$begingroup$
I am following http://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm . I understand the application of Fourier Transform behind Image Processing, but right now, I am curious about the mathematics behind it, and it is giving me a bit of a hard time.
For example:
In this formula, where do all these equations come from? Could somebody please elaborate the mathematics behind the scene in layman's term?
fourier-analysis image-processing
asked Aug 28 '12 at 9:00
KarlKarl
420718
$endgroup$
I am following http://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm . I understand the application of Fourier Transform behind Image Processing, but right now, I am curious about the mathematics behind it, and it is giving me a bit of a hard time.
For example:
In this formula, where do all these equations come from? Could somebody please elaborate the mathematics behind the scene in layman's term?
fourier-analysis image-processing
fourier-analysis image-processing
asked Aug 28 '12 at 9:00
KarlKarl
420718
asked Aug 28 '12 at 9:00
KarlKarl
420718
asked Aug 28 '12 at 9:00
KarlKarl
420718
asked Aug 28 '12 at 9:00
KarlKarl
420718
asked Aug 28 '12 at 9:00
KarlKarl
420718
420718
2
$begingroup$
Did you check en.wikipedia.org/wiki/Discrete_Fourier_transform ?
$endgroup$
– Zeta.Investigator
Aug 28 '12 at 9:08
$begingroup$
Yes, I did, but my head spins even further.
$endgroup$
– Karl
Aug 28 '12 at 9:24
$begingroup$
Explain the Fourier transform in layman's terms you say?
$endgroup$
– Rahul
Aug 28 '12 at 9:39
2
$begingroup$
An interesting explanation, to be sure... but I think I prefer to think about it in terms of orthogonal bases in inner product spaces.
$endgroup$
– Zhen Lin
Aug 28 '12 at 9:40
add a comment |
2
$begingroup$
Did you check en.wikipedia.org/wiki/Discrete_Fourier_transform ?
$endgroup$
– Zeta.Investigator
Aug 28 '12 at 9:08
$begingroup$
Yes, I did, but my head spins even further.
$endgroup$
– Karl
Aug 28 '12 at 9:24
$begingroup$
Explain the Fourier transform in layman's terms you say?
$endgroup$
– Rahul
Aug 28 '12 at 9:39
2
$begingroup$
An interesting explanation, to be sure... but I think I prefer to think about it in terms of orthogonal bases in inner product spaces.
$endgroup$
– Zhen Lin
Aug 28 '12 at 9:40
2
2
$begingroup$
Did you check en.wikipedia.org/wiki/Discrete_Fourier_transform ?
$endgroup$
– Zeta.Investigator
Aug 28 '12 at 9:08
$begingroup$
Did you check en.wikipedia.org/wiki/Discrete_Fourier_transform ?
$endgroup$
– Zeta.Investigator
Aug 28 '12 at 9:08
$begingroup$
Yes, I did, but my head spins even further.
$endgroup$
– Karl
Aug 28 '12 at 9:24
$begingroup$
Yes, I did, but my head spins even further.
$endgroup$
– Karl
Aug 28 '12 at 9:24
$begingroup$
Explain the Fourier transform in layman's terms you say?
$endgroup$
– Rahul
Aug 28 '12 at 9:39
$begingroup$
Explain the Fourier transform in layman's terms you say?
$endgroup$
– Rahul
Aug 28 '12 at 9:39
2
2
$begingroup$
An interesting explanation, to be sure... but I think I prefer to think about it in terms of orthogonal bases in inner product spaces.
$endgroup$
– Zhen Lin
Aug 28 '12 at 9:40
$begingroup$
An interesting explanation, to be sure... but I think I prefer to think about it in terms of orthogonal bases in inner product spaces.
$endgroup$
– Zhen Lin
Aug 28 '12 at 9:40
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
The discrete Fourier transform (which is a function from $mathbb C^N$ to $mathbb C^N$) simply changes basis, to a special basis known as the discrete Fourier basis.
And what's so special about this basis? It's a basis of eigenvectors for the shift operator $S$, which maps $begin{bmatrix} x_0 & x_1 & x_2 &ldots & x_{N-1} end{bmatrix}^T$ to $begin{bmatrix} x_{N-1} & x_0 & x_1& ldots & x_{N-2} end{bmatrix}^T$.
Each basis vector is constructed by taking an $N$th root of unity $omega$ and forming the vector $v = begin{bmatrix} 1 & omega & omega^2 & ldots & omega^{N-1} end{bmatrix}^T$. It's easy to check that $v$ is an eigenvector of $S$:
begin{align*}
S(v) &= begin{bmatrix} omega^{N-1} & 1 & omega & ldots & omega^{N-2} end{bmatrix}^T \
&= omega^{-1} v.
end{align*}
We have one discrete Fourier basis vector for each $N$th root of unity.
Because $S$ is unitary (it clearly preserves norms), we have that $S$ is normal, so there is an orthonormal basis of eigenvectors for $S$. This explains why the discrete Fourier basis (once normalized) is orthonormal and why the discrete Fourier transform preserves norms.
Any convolution operator on $mathbb C^N$ can be expressed as a linear combination of powers of $S$. This explains why the discrete Fourier basis diagonalizes any convolution operator on $mathbb C^N$.
The 2D discrete Fourier transform is analogous. We have two shift operators on $mathbb C^{M times N}$, $S_1$ (which shifts each row to the right) and $S_2$ (which shifts each column down). $S_1$ and $S_2$ are normal operators and they commute, so there is an orthonormal basis of eigenvectors that simultaneously diagonalizes $S_1$ and $S_2$. This gives us the 2D discrete Fourier basis.
answered Aug 3 '13 at 8:10
littleOlittleO
29.6k646109
$endgroup$
add a comment |
$begingroup$
In my opinion it is quite okay to understand Fourier transform as orthogonal basis matrices to evaluate the certain frequencies for a given image. However I have the following link which will be helpful for you to further understand:
http://sharp.bu.edu/~slehar/fourier/fourier.html#harmonics (dead link)
The working one
Good luck.
answered Aug 28 '12 at 9:54
Seyhmus GüngörenSeyhmus Güngören
5,57131736
$endgroup$
$begingroup$
alright. edited. thx.
$endgroup$
– Seyhmus Güngören
Jan 7 at 15:49
add a comment |
$begingroup$
I think the easiest way of understanding the math, Is understanding what it means. It's also easier to start in 1D and only then move on to higher dimensions.
To see what the sum you mentioned is, try inserting a wave with constant frequency. You see that the summation only gives a peak at the "correct" frequency. If you have a super-position of waves, the sum will give you a number of peaks each corresponding to a different part of the super-position.
Thus, the sum gives you the spectrum of frequencies in the wave or image.
answered Aug 28 '12 at 9:59
nbubisnbubis
27.1k552108
$endgroup$
add a comment |
$begingroup$
In layman's terms:
First lets start with the Fourier series.
This comes from a paper Fourier wrote on modelling heat diffusion. The idea being that one could approximate any continuous function by adding up lots of sin an cos functions. The more terms you can use, the more accurate you can make the result.
ie:
$f(x) = a_0cosfrac{pi y}{2}+a_1cos 3frac{pi y}{2}+a_2cos5frac{pi y}{2}+cdots + b_0sinfrac{pi y}{2}+b_1sin 3frac{pi y}{2}+b_2sin5frac{pi y}{2}+cdots$
In order to find the coefficients (the a's) to do this, the following trick was used:
$a_n = frac{1}{pi}int_{-pi}^pi f(x) cos(nx), dx$
The same would be similarly done for sine functions.
$b_n = frac{1}{pi}int_{-pi}^pi f(x) sin(nx), dx$
These are known as the Fourier sine and cosine transforms.
Euler's formula
$e^{itheta} = cos(theta) + i sin(theta)$ shows an relationship between exponential functions and cos and sin. This is why you seen an exponential (e) in the Fourier transform instead of cos and sin. This is merely the Fourier cosine and Fourier Sine transforms being combined into one transform.
This is where $hat{f}(xi) = int_{-infty}^{infty} f(x) e^{- 2pi i x xi},dx$ comes from.
Now in image processing we are typically working with 2 dimensional images. So the Fourier transform has been done twice on both dimensions.
$F(u,v)=int int_{-infty}^{infty} f(x,y) e^{-j2pi(ux+vy)} dx dy $
Since images actually come in discrete pixels rather than continuous (like analogue vs digital) functions. (Images are "digital"). This function has been discretised.
Which is why you see the summation instead of the integrals.
answered Aug 3 '13 at 5:10
savsav
934411
$endgroup$
add a comment |
$begingroup$
I have given a similar explanation of Fourier series here and here.
The Fourier series of a function $f : mathbb R / mathbb Z to mathbb C$ is a sum $sum_{k = -infty}^infty hat{f}(e^{2 pi i k x}) e^{2 pi i k x}$. Here, $e^{2 pi i k x} = chi_k (x)$ denotes the $k$-th character of the topological group $mathbb R / mathbb Z $ and $hat{f} : widehat{mathbb R / mathbb Z} to mathbb C$ denotes the Fourier transform of $f$.
The setting is: You have a topological group $G$, then you consider a space of functions $G to mathbb C$ on it, say for example $L^2(G)$. This is a Hilbert space and comes with an inner product $langle cdot , cdot rangle$ which lets you define orthogonality of functions in the space, and characters in particular. Those characters form an orthonormal basis for your functions which means that you can approximate every function in $L^2(G)$ as $| f - sum_{k = -N}^N hat{f}(chi_k) chi_k (x) |_2 xrightarrow{N to infty} 0$.
edited Apr 13 '17 at 12:20
Community♦
1
answered Aug 28 '12 at 9:43
Rudy the ReindeerRudy the Reindeer
26.4k1792240
$endgroup$
$begingroup$
I don't think it's possible to explain it using less definitions.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 9:43
$begingroup$
That's not much of a layman's term, is it?
$endgroup$
– Karl
Aug 28 '12 at 12:24
$begingroup$
@Karl Indeed that's why I wrote that I don't think it's possible to explain this with less definitions. I don't see how to understand what Fourier transform does with less background that this.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 12:33
1
$begingroup$
@MattN. - sorry, but one can definitely explain the intuition behind a Fourier series without knowing what the "k-th character of the topological group" is.
$endgroup$
– nbubis
Aug 3 '13 at 5:20
2
$begingroup$
An inability to express an everyday concept such as a Fourier representation of an image in terms that an engineer can use signals a lack of practical understanding of the subject matter, no matter how sophisticated the mathematics may be behind your description. What is a frequency? Why use complex exponentials in the first place? How are they manipulated? This is the proper level of description here.
$endgroup$
– Ron Gordon
Aug 3 '13 at 7:23
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f187806%2fthe-mathematics-behind-fourier-transform-for-image-processing%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The discrete Fourier transform (which is a function from $mathbb C^N$ to $mathbb C^N$) simply changes basis, to a special basis known as the discrete Fourier basis.
And what's so special about this basis? It's a basis of eigenvectors for the shift operator $S$, which maps $begin{bmatrix} x_0 & x_1 & x_2 &ldots & x_{N-1} end{bmatrix}^T$ to $begin{bmatrix} x_{N-1} & x_0 & x_1& ldots & x_{N-2} end{bmatrix}^T$.
Each basis vector is constructed by taking an $N$th root of unity $omega$ and forming the vector $v = begin{bmatrix} 1 & omega & omega^2 & ldots & omega^{N-1} end{bmatrix}^T$. It's easy to check that $v$ is an eigenvector of $S$:
begin{align*}
S(v) &= begin{bmatrix} omega^{N-1} & 1 & omega & ldots & omega^{N-2} end{bmatrix}^T \
&= omega^{-1} v.
end{align*}
We have one discrete Fourier basis vector for each $N$th root of unity.
Because $S$ is unitary (it clearly preserves norms), we have that $S$ is normal, so there is an orthonormal basis of eigenvectors for $S$. This explains why the discrete Fourier basis (once normalized) is orthonormal and why the discrete Fourier transform preserves norms.
Any convolution operator on $mathbb C^N$ can be expressed as a linear combination of powers of $S$. This explains why the discrete Fourier basis diagonalizes any convolution operator on $mathbb C^N$.
The 2D discrete Fourier transform is analogous. We have two shift operators on $mathbb C^{M times N}$, $S_1$ (which shifts each row to the right) and $S_2$ (which shifts each column down). $S_1$ and $S_2$ are normal operators and they commute, so there is an orthonormal basis of eigenvectors that simultaneously diagonalizes $S_1$ and $S_2$. This gives us the 2D discrete Fourier basis.
answered Aug 3 '13 at 8:10
littleOlittleO
29.6k646109
$endgroup$
add a comment |
$begingroup$
The discrete Fourier transform (which is a function from $mathbb C^N$ to $mathbb C^N$) simply changes basis, to a special basis known as the discrete Fourier basis.
And what's so special about this basis? It's a basis of eigenvectors for the shift operator $S$, which maps $begin{bmatrix} x_0 & x_1 & x_2 &ldots & x_{N-1} end{bmatrix}^T$ to $begin{bmatrix} x_{N-1} & x_0 & x_1& ldots & x_{N-2} end{bmatrix}^T$.
Each basis vector is constructed by taking an $N$th root of unity $omega$ and forming the vector $v = begin{bmatrix} 1 & omega & omega^2 & ldots & omega^{N-1} end{bmatrix}^T$. It's easy to check that $v$ is an eigenvector of $S$:
begin{align*}
S(v) &= begin{bmatrix} omega^{N-1} & 1 & omega & ldots & omega^{N-2} end{bmatrix}^T \
&= omega^{-1} v.
end{align*}
We have one discrete Fourier basis vector for each $N$th root of unity.
Because $S$ is unitary (it clearly preserves norms), we have that $S$ is normal, so there is an orthonormal basis of eigenvectors for $S$. This explains why the discrete Fourier basis (once normalized) is orthonormal and why the discrete Fourier transform preserves norms.
Any convolution operator on $mathbb C^N$ can be expressed as a linear combination of powers of $S$. This explains why the discrete Fourier basis diagonalizes any convolution operator on $mathbb C^N$.
The 2D discrete Fourier transform is analogous. We have two shift operators on $mathbb C^{M times N}$, $S_1$ (which shifts each row to the right) and $S_2$ (which shifts each column down). $S_1$ and $S_2$ are normal operators and they commute, so there is an orthonormal basis of eigenvectors that simultaneously diagonalizes $S_1$ and $S_2$. This gives us the 2D discrete Fourier basis.
answered Aug 3 '13 at 8:10
littleOlittleO
29.6k646109
$endgroup$
add a comment |
$begingroup$
The discrete Fourier transform (which is a function from $mathbb C^N$ to $mathbb C^N$) simply changes basis, to a special basis known as the discrete Fourier basis.
And what's so special about this basis? It's a basis of eigenvectors for the shift operator $S$, which maps $begin{bmatrix} x_0 & x_1 & x_2 &ldots & x_{N-1} end{bmatrix}^T$ to $begin{bmatrix} x_{N-1} & x_0 & x_1& ldots & x_{N-2} end{bmatrix}^T$.
Each basis vector is constructed by taking an $N$th root of unity $omega$ and forming the vector $v = begin{bmatrix} 1 & omega & omega^2 & ldots & omega^{N-1} end{bmatrix}^T$. It's easy to check that $v$ is an eigenvector of $S$:
begin{align*}
S(v) &= begin{bmatrix} omega^{N-1} & 1 & omega & ldots & omega^{N-2} end{bmatrix}^T \
&= omega^{-1} v.
end{align*}
We have one discrete Fourier basis vector for each $N$th root of unity.
Because $S$ is unitary (it clearly preserves norms), we have that $S$ is normal, so there is an orthonormal basis of eigenvectors for $S$. This explains why the discrete Fourier basis (once normalized) is orthonormal and why the discrete Fourier transform preserves norms.
Any convolution operator on $mathbb C^N$ can be expressed as a linear combination of powers of $S$. This explains why the discrete Fourier basis diagonalizes any convolution operator on $mathbb C^N$.
The 2D discrete Fourier transform is analogous. We have two shift operators on $mathbb C^{M times N}$, $S_1$ (which shifts each row to the right) and $S_2$ (which shifts each column down). $S_1$ and $S_2$ are normal operators and they commute, so there is an orthonormal basis of eigenvectors that simultaneously diagonalizes $S_1$ and $S_2$. This gives us the 2D discrete Fourier basis.
answered Aug 3 '13 at 8:10
littleOlittleO
29.6k646109
$endgroup$
The discrete Fourier transform (which is a function from $mathbb C^N$ to $mathbb C^N$) simply changes basis, to a special basis known as the discrete Fourier basis.
And what's so special about this basis? It's a basis of eigenvectors for the shift operator $S$, which maps $begin{bmatrix} x_0 & x_1 & x_2 &ldots & x_{N-1} end{bmatrix}^T$ to $begin{bmatrix} x_{N-1} & x_0 & x_1& ldots & x_{N-2} end{bmatrix}^T$.
Each basis vector is constructed by taking an $N$th root of unity $omega$ and forming the vector $v = begin{bmatrix} 1 & omega & omega^2 & ldots & omega^{N-1} end{bmatrix}^T$. It's easy to check that $v$ is an eigenvector of $S$:
begin{align*}
S(v) &= begin{bmatrix} omega^{N-1} & 1 & omega & ldots & omega^{N-2} end{bmatrix}^T \
&= omega^{-1} v.
end{align*}
We have one discrete Fourier basis vector for each $N$th root of unity.
Because $S$ is unitary (it clearly preserves norms), we have that $S$ is normal, so there is an orthonormal basis of eigenvectors for $S$. This explains why the discrete Fourier basis (once normalized) is orthonormal and why the discrete Fourier transform preserves norms.
Any convolution operator on $mathbb C^N$ can be expressed as a linear combination of powers of $S$. This explains why the discrete Fourier basis diagonalizes any convolution operator on $mathbb C^N$.
The 2D discrete Fourier transform is analogous. We have two shift operators on $mathbb C^{M times N}$, $S_1$ (which shifts each row to the right) and $S_2$ (which shifts each column down). $S_1$ and $S_2$ are normal operators and they commute, so there is an orthonormal basis of eigenvectors that simultaneously diagonalizes $S_1$ and $S_2$. This gives us the 2D discrete Fourier basis.
answered Aug 3 '13 at 8:10
littleOlittleO
29.6k646109
edited Aug 3 '13 at 8:18
answered Aug 3 '13 at 8:10
littleOlittleO
29.6k646109
answered Aug 3 '13 at 8:10
littleOlittleO
29.6k646109
answered Aug 3 '13 at 8:10
littleOlittleO
29.6k646109
29.6k646109
add a comment |
add a comment |
$begingroup$
In my opinion it is quite okay to understand Fourier transform as orthogonal basis matrices to evaluate the certain frequencies for a given image. However I have the following link which will be helpful for you to further understand:
http://sharp.bu.edu/~slehar/fourier/fourier.html#harmonics (dead link)
The working one
Good luck.
answered Aug 28 '12 at 9:54
Seyhmus GüngörenSeyhmus Güngören
5,57131736
$endgroup$
$begingroup$
alright. edited. thx.
$endgroup$
– Seyhmus Güngören
Jan 7 at 15:49
add a comment |
$begingroup$
In my opinion it is quite okay to understand Fourier transform as orthogonal basis matrices to evaluate the certain frequencies for a given image. However I have the following link which will be helpful for you to further understand:
http://sharp.bu.edu/~slehar/fourier/fourier.html#harmonics (dead link)
The working one
Good luck.
answered Aug 28 '12 at 9:54
Seyhmus GüngörenSeyhmus Güngören
5,57131736
$endgroup$
$begingroup$
alright. edited. thx.
$endgroup$
– Seyhmus Güngören
Jan 7 at 15:49
add a comment |
$begingroup$
In my opinion it is quite okay to understand Fourier transform as orthogonal basis matrices to evaluate the certain frequencies for a given image. However I have the following link which will be helpful for you to further understand:
http://sharp.bu.edu/~slehar/fourier/fourier.html#harmonics (dead link)
The working one
Good luck.
answered Aug 28 '12 at 9:54
Seyhmus GüngörenSeyhmus Güngören
5,57131736
$endgroup$
In my opinion it is quite okay to understand Fourier transform as orthogonal basis matrices to evaluate the certain frequencies for a given image. However I have the following link which will be helpful for you to further understand:
http://sharp.bu.edu/~slehar/fourier/fourier.html#harmonics (dead link)
The working one
Good luck.
answered Aug 28 '12 at 9:54
Seyhmus GüngörenSeyhmus Güngören
5,57131736
edited Jan 7 at 15:49
answered Aug 28 '12 at 9:54
Seyhmus GüngörenSeyhmus Güngören
5,57131736
answered Aug 28 '12 at 9:54
Seyhmus GüngörenSeyhmus Güngören
5,57131736
answered Aug 28 '12 at 9:54
Seyhmus GüngörenSeyhmus Güngören
5,57131736
5,57131736
$begingroup$
alright. edited. thx.
$endgroup$
– Seyhmus Güngören
Jan 7 at 15:49
add a comment |
$begingroup$
alright. edited. thx.
$endgroup$
– Seyhmus Güngören
Jan 7 at 15:49
$begingroup$
alright. edited. thx.
$endgroup$
– Seyhmus Güngören
Jan 7 at 15:49
$begingroup$
alright. edited. thx.
$endgroup$
– Seyhmus Güngören
Jan 7 at 15:49
add a comment |
$begingroup$
I think the easiest way of understanding the math, Is understanding what it means. It's also easier to start in 1D and only then move on to higher dimensions.
To see what the sum you mentioned is, try inserting a wave with constant frequency. You see that the summation only gives a peak at the "correct" frequency. If you have a super-position of waves, the sum will give you a number of peaks each corresponding to a different part of the super-position.
Thus, the sum gives you the spectrum of frequencies in the wave or image.
answered Aug 28 '12 at 9:59
nbubisnbubis
27.1k552108
$endgroup$
add a comment |
$begingroup$
I think the easiest way of understanding the math, Is understanding what it means. It's also easier to start in 1D and only then move on to higher dimensions.
To see what the sum you mentioned is, try inserting a wave with constant frequency. You see that the summation only gives a peak at the "correct" frequency. If you have a super-position of waves, the sum will give you a number of peaks each corresponding to a different part of the super-position.
Thus, the sum gives you the spectrum of frequencies in the wave or image.
answered Aug 28 '12 at 9:59
nbubisnbubis
27.1k552108
$endgroup$
add a comment |
$begingroup$
I think the easiest way of understanding the math, Is understanding what it means. It's also easier to start in 1D and only then move on to higher dimensions.
To see what the sum you mentioned is, try inserting a wave with constant frequency. You see that the summation only gives a peak at the "correct" frequency. If you have a super-position of waves, the sum will give you a number of peaks each corresponding to a different part of the super-position.
Thus, the sum gives you the spectrum of frequencies in the wave or image.
answered Aug 28 '12 at 9:59
nbubisnbubis
27.1k552108
$endgroup$
I think the easiest way of understanding the math, Is understanding what it means. It's also easier to start in 1D and only then move on to higher dimensions.
To see what the sum you mentioned is, try inserting a wave with constant frequency. You see that the summation only gives a peak at the "correct" frequency. If you have a super-position of waves, the sum will give you a number of peaks each corresponding to a different part of the super-position.
Thus, the sum gives you the spectrum of frequencies in the wave or image.
answered Aug 28 '12 at 9:59
nbubisnbubis
27.1k552108
answered Aug 28 '12 at 9:59
nbubisnbubis
27.1k552108
answered Aug 28 '12 at 9:59
nbubisnbubis
27.1k552108
answered Aug 28 '12 at 9:59
nbubisnbubis
27.1k552108
27.1k552108
add a comment |
add a comment |
$begingroup$
In layman's terms:
First lets start with the Fourier series.
This comes from a paper Fourier wrote on modelling heat diffusion. The idea being that one could approximate any continuous function by adding up lots of sin an cos functions. The more terms you can use, the more accurate you can make the result.
ie:
$f(x) = a_0cosfrac{pi y}{2}+a_1cos 3frac{pi y}{2}+a_2cos5frac{pi y}{2}+cdots + b_0sinfrac{pi y}{2}+b_1sin 3frac{pi y}{2}+b_2sin5frac{pi y}{2}+cdots$
In order to find the coefficients (the a's) to do this, the following trick was used:
$a_n = frac{1}{pi}int_{-pi}^pi f(x) cos(nx), dx$
The same would be similarly done for sine functions.
$b_n = frac{1}{pi}int_{-pi}^pi f(x) sin(nx), dx$
These are known as the Fourier sine and cosine transforms.
Euler's formula
$e^{itheta} = cos(theta) + i sin(theta)$ shows an relationship between exponential functions and cos and sin. This is why you seen an exponential (e) in the Fourier transform instead of cos and sin. This is merely the Fourier cosine and Fourier Sine transforms being combined into one transform.
This is where $hat{f}(xi) = int_{-infty}^{infty} f(x) e^{- 2pi i x xi},dx$ comes from.
Now in image processing we are typically working with 2 dimensional images. So the Fourier transform has been done twice on both dimensions.
$F(u,v)=int int_{-infty}^{infty} f(x,y) e^{-j2pi(ux+vy)} dx dy $
Since images actually come in discrete pixels rather than continuous (like analogue vs digital) functions. (Images are "digital"). This function has been discretised.
Which is why you see the summation instead of the integrals.
answered Aug 3 '13 at 5:10
savsav
934411
$endgroup$
add a comment |
$begingroup$
In layman's terms:
First lets start with the Fourier series.
This comes from a paper Fourier wrote on modelling heat diffusion. The idea being that one could approximate any continuous function by adding up lots of sin an cos functions. The more terms you can use, the more accurate you can make the result.
ie:
$f(x) = a_0cosfrac{pi y}{2}+a_1cos 3frac{pi y}{2}+a_2cos5frac{pi y}{2}+cdots + b_0sinfrac{pi y}{2}+b_1sin 3frac{pi y}{2}+b_2sin5frac{pi y}{2}+cdots$
In order to find the coefficients (the a's) to do this, the following trick was used:
$a_n = frac{1}{pi}int_{-pi}^pi f(x) cos(nx), dx$
The same would be similarly done for sine functions.
$b_n = frac{1}{pi}int_{-pi}^pi f(x) sin(nx), dx$
These are known as the Fourier sine and cosine transforms.
Euler's formula
$e^{itheta} = cos(theta) + i sin(theta)$ shows an relationship between exponential functions and cos and sin. This is why you seen an exponential (e) in the Fourier transform instead of cos and sin. This is merely the Fourier cosine and Fourier Sine transforms being combined into one transform.
This is where $hat{f}(xi) = int_{-infty}^{infty} f(x) e^{- 2pi i x xi},dx$ comes from.
Now in image processing we are typically working with 2 dimensional images. So the Fourier transform has been done twice on both dimensions.
$F(u,v)=int int_{-infty}^{infty} f(x,y) e^{-j2pi(ux+vy)} dx dy $
Since images actually come in discrete pixels rather than continuous (like analogue vs digital) functions. (Images are "digital"). This function has been discretised.
Which is why you see the summation instead of the integrals.
answered Aug 3 '13 at 5:10
savsav
934411
$endgroup$
add a comment |
$begingroup$
In layman's terms:
First lets start with the Fourier series.
This comes from a paper Fourier wrote on modelling heat diffusion. The idea being that one could approximate any continuous function by adding up lots of sin an cos functions. The more terms you can use, the more accurate you can make the result.
ie:
$f(x) = a_0cosfrac{pi y}{2}+a_1cos 3frac{pi y}{2}+a_2cos5frac{pi y}{2}+cdots + b_0sinfrac{pi y}{2}+b_1sin 3frac{pi y}{2}+b_2sin5frac{pi y}{2}+cdots$
In order to find the coefficients (the a's) to do this, the following trick was used:
$a_n = frac{1}{pi}int_{-pi}^pi f(x) cos(nx), dx$
The same would be similarly done for sine functions.
$b_n = frac{1}{pi}int_{-pi}^pi f(x) sin(nx), dx$
These are known as the Fourier sine and cosine transforms.
Euler's formula
$e^{itheta} = cos(theta) + i sin(theta)$ shows an relationship between exponential functions and cos and sin. This is why you seen an exponential (e) in the Fourier transform instead of cos and sin. This is merely the Fourier cosine and Fourier Sine transforms being combined into one transform.
This is where $hat{f}(xi) = int_{-infty}^{infty} f(x) e^{- 2pi i x xi},dx$ comes from.
Now in image processing we are typically working with 2 dimensional images. So the Fourier transform has been done twice on both dimensions.
$F(u,v)=int int_{-infty}^{infty} f(x,y) e^{-j2pi(ux+vy)} dx dy $
Since images actually come in discrete pixels rather than continuous (like analogue vs digital) functions. (Images are "digital"). This function has been discretised.
Which is why you see the summation instead of the integrals.
answered Aug 3 '13 at 5:10
savsav
934411
$endgroup$
In layman's terms:
First lets start with the Fourier series.
This comes from a paper Fourier wrote on modelling heat diffusion. The idea being that one could approximate any continuous function by adding up lots of sin an cos functions. The more terms you can use, the more accurate you can make the result.
ie:
$f(x) = a_0cosfrac{pi y}{2}+a_1cos 3frac{pi y}{2}+a_2cos5frac{pi y}{2}+cdots + b_0sinfrac{pi y}{2}+b_1sin 3frac{pi y}{2}+b_2sin5frac{pi y}{2}+cdots$
In order to find the coefficients (the a's) to do this, the following trick was used:
$a_n = frac{1}{pi}int_{-pi}^pi f(x) cos(nx), dx$
The same would be similarly done for sine functions.
$b_n = frac{1}{pi}int_{-pi}^pi f(x) sin(nx), dx$
These are known as the Fourier sine and cosine transforms.
Euler's formula
$e^{itheta} = cos(theta) + i sin(theta)$ shows an relationship between exponential functions and cos and sin. This is why you seen an exponential (e) in the Fourier transform instead of cos and sin. This is merely the Fourier cosine and Fourier Sine transforms being combined into one transform.
This is where $hat{f}(xi) = int_{-infty}^{infty} f(x) e^{- 2pi i x xi},dx$ comes from.
Now in image processing we are typically working with 2 dimensional images. So the Fourier transform has been done twice on both dimensions.
$F(u,v)=int int_{-infty}^{infty} f(x,y) e^{-j2pi(ux+vy)} dx dy $
Since images actually come in discrete pixels rather than continuous (like analogue vs digital) functions. (Images are "digital"). This function has been discretised.
Which is why you see the summation instead of the integrals.
answered Aug 3 '13 at 5:10
savsav
934411
edited Aug 3 '13 at 5:20
answered Aug 3 '13 at 5:10
savsav
934411
answered Aug 3 '13 at 5:10
savsav
934411
answered Aug 3 '13 at 5:10
savsav
934411
934411
add a comment |
add a comment |
$begingroup$
I have given a similar explanation of Fourier series here and here.
The Fourier series of a function $f : mathbb R / mathbb Z to mathbb C$ is a sum $sum_{k = -infty}^infty hat{f}(e^{2 pi i k x}) e^{2 pi i k x}$. Here, $e^{2 pi i k x} = chi_k (x)$ denotes the $k$-th character of the topological group $mathbb R / mathbb Z $ and $hat{f} : widehat{mathbb R / mathbb Z} to mathbb C$ denotes the Fourier transform of $f$.
The setting is: You have a topological group $G$, then you consider a space of functions $G to mathbb C$ on it, say for example $L^2(G)$. This is a Hilbert space and comes with an inner product $langle cdot , cdot rangle$ which lets you define orthogonality of functions in the space, and characters in particular. Those characters form an orthonormal basis for your functions which means that you can approximate every function in $L^2(G)$ as $| f - sum_{k = -N}^N hat{f}(chi_k) chi_k (x) |_2 xrightarrow{N to infty} 0$.
edited Apr 13 '17 at 12:20
Community♦
1
answered Aug 28 '12 at 9:43
Rudy the ReindeerRudy the Reindeer
26.4k1792240
$endgroup$
$begingroup$
I don't think it's possible to explain it using less definitions.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 9:43
$begingroup$
That's not much of a layman's term, is it?
$endgroup$
– Karl
Aug 28 '12 at 12:24
$begingroup$
@Karl Indeed that's why I wrote that I don't think it's possible to explain this with less definitions. I don't see how to understand what Fourier transform does with less background that this.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 12:33
1
$begingroup$
@MattN. - sorry, but one can definitely explain the intuition behind a Fourier series without knowing what the "k-th character of the topological group" is.
$endgroup$
– nbubis
Aug 3 '13 at 5:20
2
$begingroup$
An inability to express an everyday concept such as a Fourier representation of an image in terms that an engineer can use signals a lack of practical understanding of the subject matter, no matter how sophisticated the mathematics may be behind your description. What is a frequency? Why use complex exponentials in the first place? How are they manipulated? This is the proper level of description here.
$endgroup$
– Ron Gordon
Aug 3 '13 at 7:23
add a comment |
$begingroup$
I have given a similar explanation of Fourier series here and here.
The Fourier series of a function $f : mathbb R / mathbb Z to mathbb C$ is a sum $sum_{k = -infty}^infty hat{f}(e^{2 pi i k x}) e^{2 pi i k x}$. Here, $e^{2 pi i k x} = chi_k (x)$ denotes the $k$-th character of the topological group $mathbb R / mathbb Z $ and $hat{f} : widehat{mathbb R / mathbb Z} to mathbb C$ denotes the Fourier transform of $f$.
The setting is: You have a topological group $G$, then you consider a space of functions $G to mathbb C$ on it, say for example $L^2(G)$. This is a Hilbert space and comes with an inner product $langle cdot , cdot rangle$ which lets you define orthogonality of functions in the space, and characters in particular. Those characters form an orthonormal basis for your functions which means that you can approximate every function in $L^2(G)$ as $| f - sum_{k = -N}^N hat{f}(chi_k) chi_k (x) |_2 xrightarrow{N to infty} 0$.
edited Apr 13 '17 at 12:20
Community♦
1
answered Aug 28 '12 at 9:43
Rudy the ReindeerRudy the Reindeer
26.4k1792240
$endgroup$
$begingroup$
I don't think it's possible to explain it using less definitions.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 9:43
$begingroup$
That's not much of a layman's term, is it?
$endgroup$
– Karl
Aug 28 '12 at 12:24
$begingroup$
@Karl Indeed that's why I wrote that I don't think it's possible to explain this with less definitions. I don't see how to understand what Fourier transform does with less background that this.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 12:33
1
$begingroup$
@MattN. - sorry, but one can definitely explain the intuition behind a Fourier series without knowing what the "k-th character of the topological group" is.
$endgroup$
– nbubis
Aug 3 '13 at 5:20
2
$begingroup$
An inability to express an everyday concept such as a Fourier representation of an image in terms that an engineer can use signals a lack of practical understanding of the subject matter, no matter how sophisticated the mathematics may be behind your description. What is a frequency? Why use complex exponentials in the first place? How are they manipulated? This is the proper level of description here.
$endgroup$
– Ron Gordon
Aug 3 '13 at 7:23
add a comment |
$begingroup$
I have given a similar explanation of Fourier series here and here.
The Fourier series of a function $f : mathbb R / mathbb Z to mathbb C$ is a sum $sum_{k = -infty}^infty hat{f}(e^{2 pi i k x}) e^{2 pi i k x}$. Here, $e^{2 pi i k x} = chi_k (x)$ denotes the $k$-th character of the topological group $mathbb R / mathbb Z $ and $hat{f} : widehat{mathbb R / mathbb Z} to mathbb C$ denotes the Fourier transform of $f$.
The setting is: You have a topological group $G$, then you consider a space of functions $G to mathbb C$ on it, say for example $L^2(G)$. This is a Hilbert space and comes with an inner product $langle cdot , cdot rangle$ which lets you define orthogonality of functions in the space, and characters in particular. Those characters form an orthonormal basis for your functions which means that you can approximate every function in $L^2(G)$ as $| f - sum_{k = -N}^N hat{f}(chi_k) chi_k (x) |_2 xrightarrow{N to infty} 0$.
edited Apr 13 '17 at 12:20
Community♦
1
answered Aug 28 '12 at 9:43
Rudy the ReindeerRudy the Reindeer
26.4k1792240
$endgroup$
I have given a similar explanation of Fourier series here and here.
The Fourier series of a function $f : mathbb R / mathbb Z to mathbb C$ is a sum $sum_{k = -infty}^infty hat{f}(e^{2 pi i k x}) e^{2 pi i k x}$. Here, $e^{2 pi i k x} = chi_k (x)$ denotes the $k$-th character of the topological group $mathbb R / mathbb Z $ and $hat{f} : widehat{mathbb R / mathbb Z} to mathbb C$ denotes the Fourier transform of $f$.
The setting is: You have a topological group $G$, then you consider a space of functions $G to mathbb C$ on it, say for example $L^2(G)$. This is a Hilbert space and comes with an inner product $langle cdot , cdot rangle$ which lets you define orthogonality of functions in the space, and characters in particular. Those characters form an orthonormal basis for your functions which means that you can approximate every function in $L^2(G)$ as $| f - sum_{k = -N}^N hat{f}(chi_k) chi_k (x) |_2 xrightarrow{N to infty} 0$.
edited Apr 13 '17 at 12:20
Community♦
1
answered Aug 28 '12 at 9:43
Rudy the ReindeerRudy the Reindeer
26.4k1792240
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Aug 28 '12 at 9:43
Rudy the ReindeerRudy the Reindeer
26.4k1792240
answered Aug 28 '12 at 9:43
Rudy the ReindeerRudy the Reindeer
26.4k1792240
answered Aug 28 '12 at 9:43
Rudy the ReindeerRudy the Reindeer
26.4k1792240
26.4k1792240
$begingroup$
I don't think it's possible to explain it using less definitions.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 9:43
$begingroup$
That's not much of a layman's term, is it?
$endgroup$
– Karl
Aug 28 '12 at 12:24
$begingroup$
@Karl Indeed that's why I wrote that I don't think it's possible to explain this with less definitions. I don't see how to understand what Fourier transform does with less background that this.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 12:33
1
$begingroup$
@MattN. - sorry, but one can definitely explain the intuition behind a Fourier series without knowing what the "k-th character of the topological group" is.
$endgroup$
– nbubis
Aug 3 '13 at 5:20
2
$begingroup$
An inability to express an everyday concept such as a Fourier representation of an image in terms that an engineer can use signals a lack of practical understanding of the subject matter, no matter how sophisticated the mathematics may be behind your description. What is a frequency? Why use complex exponentials in the first place? How are they manipulated? This is the proper level of description here.
$endgroup$
– Ron Gordon
Aug 3 '13 at 7:23
add a comment |
$begingroup$
I don't think it's possible to explain it using less definitions.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 9:43
$begingroup$
That's not much of a layman's term, is it?
$endgroup$
– Karl
Aug 28 '12 at 12:24
$begingroup$
@Karl Indeed that's why I wrote that I don't think it's possible to explain this with less definitions. I don't see how to understand what Fourier transform does with less background that this.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 12:33
1
$begingroup$
@MattN. - sorry, but one can definitely explain the intuition behind a Fourier series without knowing what the "k-th character of the topological group" is.
$endgroup$
– nbubis
Aug 3 '13 at 5:20
2
$begingroup$
An inability to express an everyday concept such as a Fourier representation of an image in terms that an engineer can use signals a lack of practical understanding of the subject matter, no matter how sophisticated the mathematics may be behind your description. What is a frequency? Why use complex exponentials in the first place? How are they manipulated? This is the proper level of description here.
$endgroup$
– Ron Gordon
Aug 3 '13 at 7:23
$begingroup$
I don't think it's possible to explain it using less definitions.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 9:43
$begingroup$
I don't think it's possible to explain it using less definitions.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 9:43
$begingroup$
That's not much of a layman's term, is it?
$endgroup$
– Karl
Aug 28 '12 at 12:24
$begingroup$
That's not much of a layman's term, is it?
$endgroup$
– Karl
Aug 28 '12 at 12:24
$begingroup$
@Karl Indeed that's why I wrote that I don't think it's possible to explain this with less definitions. I don't see how to understand what Fourier transform does with less background that this.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 12:33
$begingroup$
@Karl Indeed that's why I wrote that I don't think it's possible to explain this with less definitions. I don't see how to understand what Fourier transform does with less background that this.
$endgroup$
– Rudy the Reindeer
Aug 28 '12 at 12:33
1
1
$begingroup$
@MattN. - sorry, but one can definitely explain the intuition behind a Fourier series without knowing what the "k-th character of the topological group" is.
$endgroup$
– nbubis
Aug 3 '13 at 5:20
$begingroup$
@MattN. - sorry, but one can definitely explain the intuition behind a Fourier series without knowing what the "k-th character of the topological group" is.
$endgroup$
– nbubis
Aug 3 '13 at 5:20
2
2
$begingroup$
An inability to express an everyday concept such as a Fourier representation of an image in terms that an engineer can use signals a lack of practical understanding of the subject matter, no matter how sophisticated the mathematics may be behind your description. What is a frequency? Why use complex exponentials in the first place? How are they manipulated? This is the proper level of description here.
$endgroup$
– Ron Gordon
Aug 3 '13 at 7:23
$begingroup$
An inability to express an everyday concept such as a Fourier representation of an image in terms that an engineer can use signals a lack of practical understanding of the subject matter, no matter how sophisticated the mathematics may be behind your description. What is a frequency? Why use complex exponentials in the first place? How are they manipulated? This is the proper level of description here.
$endgroup$
– Ron Gordon
Aug 3 '13 at 7:23
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f187806%2fthe-mathematics-behind-fourier-transform-for-image-processing%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
Did you check en.wikipedia.org/wiki/Discrete_Fourier_transform ?
$endgroup$
– Zeta.Investigator
Aug 28 '12 at 9:08
$begingroup$
Yes, I did, but my head spins even further.
$endgroup$
– Karl
Aug 28 '12 at 9:24
$begingroup$
Explain the Fourier transform in layman's terms you say?
$endgroup$
– Rahul
Aug 28 '12 at 9:39
2
$begingroup$
An interesting explanation, to be sure... but I think I prefer to think about it in terms of orthogonal bases in inner product spaces.
$endgroup$
– Zhen Lin
Aug 28 '12 at 9:40