RSS News Feed

Images in the frequency domain

Message-ID:<6767a886-1755-401f-b47e-0dd55e97fcae@35g2000pry.googlegroups.com>
Subject:

Images in the frequency domain..

Date:Fri, 30 Jan 2009 02:47:49 +0100


Hi,

I've been trying to understand more on frequency plots of images.

1. Assuming a 1d example of just a strip of an image; in the frequency
map there are 'same' no. of frequencies as there are pixels. What is
the reason for this? Does this have something to do with the Nyquist
theorom.

2. What you see in the frequency domain is just a plot of all the
spatial frequencies and thier amplitude corresponds to the coefficient
of that frequency? Is this correct?

3. Now if in the 1d example, i see a one recurring pattern...
	 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1

How would this map to the frequency domain? So for example, i see the
sequence '0 0 0 1' 4 times. What can i make out of this?

4. In 2d all the points near the center are the lower frequencies and
away from the center are higher frequencies. What can be said about
the image if we get

higher amplitudes in the lower freqencies as compared to the higher
frequencies. What does this mean? Can we say that simpler (or more
complicated) images will not peak at the center like this? [PS:- i do
know that lower frequencies capture the general aspects of the image
whereas the higher frequencies capture the more 'detailed' aspects
(e.g. edges)]

Thanks
Neville

Message-ID:<25010407-0e57-4133-bcfe-8a0d6bc1c663@b16g2000yqb.googlegroups.com>
Subject:

Re: Images in the frequency domain..

Date:Sat, 31 Jan 2009 05:06:13 +0100

On Jan 29, 8:47=A0pm, ndesk  wrote:
> Hi,
>
> I've been trying to understand more on frequency plots of images.
>
> 1. Assuming a 1d example of just a strip of an image; in the frequency
> map there are 'same' no. of frequencies as there are pixels. What is
> the reason for this? Does this have something to do with the Nyquist
> theorom.
>
> 2. What you see in the frequency domain is just a plot of all the
> spatial frequencies and thier amplitude corresponds to the coefficient
> of that frequency? Is this correct?
>
> 3. Now if in the 1d example, i see a one recurring pattern...
> =A0 =A0 =A0 =A0 =A00 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
>
> How would this map to the frequency domain? So for example, i see the
> sequence '0 0 0 1' 4 times. What can i make out of this?
>
> 4. In 2d all the points near the center are the lower frequencies and
> away from the center are higher frequencies. What can be said about
> the image if we get
>
> higher amplitudes in the lower freqencies as compared to the higher
> frequencies. What does this mean? Can we say that simpler (or more
> complicated) images will not peak at the center like this? [PS:- i do
> know that lower frequencies capture the general aspects of the image
> whereas the higher frequencies capture the more 'detailed' aspects
> (e.g. edges)]
>
> Thanks
> Neville

--------------------------------------------
Neville:
Here is my take on your questions:
1.  No.  It has nothing to do with Nyquist frequency but everything to
do with the FFT, which is a special way to do the FT that has been
optimized for the quantized way computers deal with numbers.
Basically, it's just an artifact of the way the FFT works.  If you did
it a different way, you wouldn't have to have the same number of
elements in the frequency space as the image space.  They don't even
have the same units or spatial calibrations after all.

2. Yeah, basically.  Sometimes you see the spectrum displayed as the
magnitude squared and with a gamma or some kind of log lookup table
mapping to make it easier to see the high frequencies, which normally
have a much, much lower amplitude than the lower spatial frequencies.
You can also have real and imaginary parts of the FFT, but let's not
get too complicated for now.

3. You've described a comb function (assuming it recurs infinitely).
The Fourier Transform of a comb function in image space is also a comb
function in frequency space.  See http://en.wikipedia.org/wiki/Dirac_comb
It is a very special case.  There are a handful of very special cases
like that - cases which have very interesting, unique, or useful
properties.

4.  Your image would be either very periodic or have negative values.
Most regular images have a spike at the origin in frequency space
(because the image has a non-zero mean meaning you have some DC
energy), and they fall off as you go to higher frequencies.
Occasionally you can see spikes in a periodic array in the frequency
space and this is usually due to some periodic nature of your spatial
image, for example the spatial image is of a rectangular grid or
honeycomb pattern.  Remember periodic in one space means spikes in the
other space, and vice versa.  You will only get zero at the origin in
FT space if the mean of your image is zero (meaning it must have
positive and negative values and thus not a natural, real-world
luminance image, but one you created somehow).
Regards,
ImageAnalyst

Message-ID:
Subject:

Re: Images in the frequency domain..

Date:Mon, 2 Feb 2009 11:39:46 +0100

On Jan 30, 2:47=A0am, ndesk  wrote:

> 1. Assuming a 1d example of just a strip of an image; in the frequency
> map there are 'same' no. of frequencies as there are pixels. What is
> the reason for this? Does this have something to do with the Nyquist
> theorom.

As Image Analyst says, this has nothing to do with the Nyquist
theorem, which is about the highest frequency present in the signal
before it was sampled to produce the pixels. However, what Image
Analyst says about the number of frequencies is, in my opinion,
misleading. Here is why.

How many numbers do you need to describe an image with N pixels? N, of
course: the image values at each pixel. Here is an analogy: how many
numbers do you need to describe a point on a table? Two, x and y,
because the surface of the table is two dimensional. But we could make
another choice, e.g. polar coordinates. But whatever choice we make,
there are always two numbers. Similarly, we can choose a different set
of coordinates to describe our images. We can choose the Fourier
coefficients of the image. (There are many other possibilities; you
may have heard of wavelets, to give one example.) But whatever system
we choose, the number of numbers will remain N, as this is the
dimension of the space of images with N pixels.

Now of course, you can compute more numbers than this, let's say M >
N, but they will be redundant. That is, (M - N) of them will be
computable in terms of the N others. On the other hand, you could
choose to compute less than N numbers. But then you would not be able
to go backwards: there would be many possible images corresponding to
your set of numbers, and you would have no way of knowing which one
was your original image. It would be like throwing away some of the
pixel values.

> 2. What you see in the frequency domain is just a plot of all the
> spatial frequencies and thier amplitude corresponds to the coefficient
> of that frequency? Is this correct?

Yes. Each coefficient is a complex number. It has a magnitude (the
amount of that frequency that is present), and a phase (the position
of that frequency wave - where it 'starts from'). Note that in fact,
this way you have 2N numbers, the real and imaginary part of each
coefficient. This is because the FFT can represent an arbitrary
complex signal with N pixels, which needs 2N numbers of describe it.
The fact that an image is real places a constraint on these 2 N
numbers: one half of them is determined in terms of the other half.

> 3. Now if in the 1d example, i see a one recurring pattern...
> =A0 =A0 =A0 =A0 =A00 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
>
> How would this map to the frequency domain? So for example, i see the
> sequence '0 0 0 1' 4 times. What can i make out of this?

A signal of the form

f(n) =3D a sin(k n) + b cos(k n) ,

where k is a number of the form 2 pi m / N, where m is an integer from
0 to (N - 1), has just two peaks in the FFT, one at point k, and one
at point N - k. The numbers at these  two points are complex
conjugates of each other if a and b are real: this is the constraint I
mentioned earlier.

Any other other signal can be represented as a sum of signals of this
form, one for each value of k, with different values of a and b.

> 4. In 2d all the points near the center are the lower frequencies and
> away from the center are higher frequencies. What can be said about
> the image if we get
>
> higher amplitudes in the lower freqencies as compared to the higher
> frequencies. What does this mean? Can we say that simpler (or more
> complicated) images will not peak at the center like this? [PS:- i do
> know that lower frequencies capture the general aspects of the image
> whereas the higher frequencies capture the more 'detailed' aspects
> (e.g. edges)]

I would not use the words 'simpler' and 'complicated' as these are not
very precise. Signals with less high frequencies are smoother, closer
to being constant: they change more slowly with time or position.
Signals with more high frequencies are more jagged, and change more
rapidly. Edges are very fast changes, hence require high frequencies
to represent them.

illywhacker;

Message-ID:
Subject:

Re: Images in the frequency domain..

Date:Mon, 2 Feb 2009 19:03:14 +0100




ndesk schrieb:
> Hi,
>
> I've been trying to understand more on frequency plots of images.
>
> 1. Assuming a 1d example of just a strip of an image; in the frequency
> map there are 'same' no. of frequencies as there are pixels. What is
> the reason for this? Does this have something to do with the Nyquist
> theorom.
>
> 2. What you see in the frequency domain is just a plot of all the
> spatial frequencies and thier amplitude corresponds to the coefficient
> of that frequency? Is this correct?
>
> 3. Now if in the 1d example, i see a one recurring pattern...
> 	 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
>
> How would this map to the frequency domain? So for example, i see the
> sequence '0 0 0 1' 4 times. What can i make out of this?
>
> 4. In 2d all the points near the center are the lower frequencies and
> away from the center are higher frequencies. What can be said about
> the image if we get
>
> higher amplitudes in the lower freqencies as compared to the higher
> frequencies. What does this mean? Can we say that simpler (or more
> complicated) images will not peak at the center like this? [PS:- i do
> know that lower frequencies capture the general aspects of the image
> whereas the higher frequencies capture the more 'detailed' aspects
> (e.g. edges)]
>
> Thanks
> Neville

Perhaps this helps a little:
http://www.fho-emden.de/~hoffmann/fft31052003.pdf

Best regards --Gernot Hoffmann

Message-ID:<1Pyil.1430$1r4.439@newsfe04.iad>
Subject:

Re: Images in the frequency domain..

Date:Thu, 5 Feb 2009 11:02:40 +0100

ndesk wrote:
> Hi,
> 
> I've been trying to understand more on frequency plots of images.
> 
> 1. Assuming a 1d example of just a strip of an image; in the frequency
> map there are 'same' no. of frequencies as there are pixels. What is
> the reason for this? Does this have something to do with the Nyquist
> theorom.

I am going to disagree with the others very slightly. If you consider 
the 1d strip as a time series then the Nyquist theorem says that to 
preserve all the information contained in it you have to sample up to 
and including the alternating frequency component.

BTW If you use naive unpacked FFTs then there are actually N+1 frequency 
components for an image of length N. But two components, the DC and 
alternating component are pure reals (imaginary part is identically zero 
and need not be stored). So clever FFTs (especially high dimensional 
ones) usually pack them with the AC component stored in the DC imaginary 
slot.

Most image are pure real data and transforms also exploit the inherent 
symmetry in frequency space to avoid storing the complex conjugate (with 
an implicit 2x for all the frequency components)

The FFT is effectively a rotation of the spatial data into frequency 
space using an orthogonal transform. So that usually

  FFT^-1(FFT(x)) = Nx

> 
> 2. What you see in the frequency domain is just a plot of all the
> spatial frequencies and thier amplitude corresponds to the coefficient
> of that frequency? Is this correct?

Yes although conventions vary about where to place the DC component.
> 
> 3. Now if in the 1d example, i see a one recurring pattern...
> 	 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
> 
> How would this map to the frequency domain? So for example, i see the
> sequence '0 0 0 1' 4 times. What can i make out of this?

FFT of a comb is another comb. The motif 0 0 0 1 is simple enough that 
the 4 radix FFT kernel is pure reals. Namely M

DC	1   1   1   1
Cosx	1   0  -1   0
Sinx	0   1   0  -1
Cos2x	1  -1   1  -1

So that the FFT of your motif under a 4x4 real to complex FFT is

k = 1 0 -2 -1

And if you compute k.M you will get your vector back scaled by the 
length of the tranform.

> 4. In 2d all the points near the center are the lower frequencies and
> away from the center are higher frequencies. What can be said about
> the image if we get
> 
> higher amplitudes in the lower freqencies as compared to the higher
> frequencies. What does this mean? Can we say that simpler (or more
> complicated) images will not peak at the center like this? [PS:- i do
> know that lower frequencies capture the general aspects of the image
> whereas the higher frequencies capture the more 'detailed' aspects
> (e.g. edges)]

In a real image the DC component will always be the largest one since 
every value in the image is summed with no phase factor.

If your data had zero mean and was mostly high frequency noise then the 
DC component would be insignificant, but the time series would contain 
negative values. Knowing that real images do not contain negative values 
allows data measured in frequency space to be processed to produce 
better quality images than the simple linear inverse can manage.

Regards,
Martin Brown

Message-ID:<98c25c7b-6f00-47e6-abe5-26b43c7dec35@u14g2000yqg.googlegroups.com>
Subject:

Re: Images in the frequency domain..

Date:Thu, 5 Feb 2009 12:48:33 +0100

On Feb 5, 11:02=A0am, Martin Brown <|||newspam...@nezumi.demon.co.uk>
wrote:
> ndesk wrote:
> > Hi,
>
> > I've been trying to understand more on frequency plots of images.
>
> > 1. Assuming a 1d example of just a strip of an image; in the frequency
> > map there are 'same' no. of frequencies as there are pixels. What is
> > the reason for this? Does this have something to do with the Nyquist
> > theorom.
>
> I am going to disagree with the others very slightly. If you consider
> the 1d strip as a time series then the Nyquist theorem says that to
> preserve all the information contained in it you have to sample up to
> and including the alternating frequency component.

Yes, but for discrete signals, this simply corresponds to counting the
dimensionality, i.e. not much of a theorem. The point is that for an
infinite continuous signal (i.e. an uncountable number of values in
both real space and frequency space) that has an upper frequency
bound, a countable set of samples suffices to represent it. Now, this
idea, i.e. the Nyquist-Shannon sampling theorem, is really pretty
simple, despite its status as a great truth of signal processing, and
indeed it is wrong, since real sampling bears little relation to it,
but it is not quite as simple as dimension counting.

illywhacker;

Message-ID:<1Pyil.1430$1r4.439@newsfe04.iad>
Subject:

Re: Images in the frequency domain..

Date:Thu, 5 Feb 2009 11:02:40 +0100

ndesk wrote:
> Hi,
> 
> I've been trying to understand more on frequency plots of images.
> 
> 1. Assuming a 1d example of just a strip of an image; in the frequency
> map there are 'same' no. of frequencies as there are pixels. What is
> the reason for this? Does this have something to do with the Nyquist
> theorom.

I am going to disagree with the others very slightly. If you consider 
the 1d strip as a time series then the Nyquist theorem says that to 
preserve all the information contained in it you have to sample up to 
and including the alternating frequency component.

BTW If you use naive unpacked FFTs then there are actually N+1 frequency 
components for an image of length N. But two components, the DC and 
alternating component are pure reals (imaginary part is identically zero 
and need not be stored). So clever FFTs (especially high dimensional 
ones) usually pack them with the AC component stored in the DC imaginary 
slot.

Most image are pure real data and transforms also exploit the inherent 
symmetry in frequency space to avoid storing the complex conjugate (with 
an implicit 2x for all the frequency components)

The FFT is effectively a rotation of the spatial data into frequency 
space using an orthogonal transform. So that usually

  FFT^-1(FFT(x)) = Nx

> 
> 2. What you see in the frequency domain is just a plot of all the
> spatial frequencies and thier amplitude corresponds to the coefficient
> of that frequency? Is this correct?

Yes although conventions vary about where to place the DC component.
> 
> 3. Now if in the 1d example, i see a one recurring pattern...
> 	 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
> 
> How would this map to the frequency domain? So for example, i see the
> sequence '0 0 0 1' 4 times. What can i make out of this?

FFT of a comb is another comb. The motif 0 0 0 1 is simple enough that 
the 4 radix FFT kernel is pure reals. Namely M

DC	1   1   1   1
Cosx	1   0  -1   0
Sinx	0   1   0  -1
Cos2x	1  -1   1  -1

So that the FFT of your motif under a 4x4 real to complex FFT is

k = 1 0 -2 -1

And if you compute k.M you will get your vector back scaled by the 
length of the tranform.

> 4. In 2d all the points near the center are the lower frequencies and
> away from the center are higher frequencies. What can be said about
> the image if we get
> 
> higher amplitudes in the lower freqencies as compared to the higher
> frequencies. What does this mean? Can we say that simpler (or more
> complicated) images will not peak at the center like this? [PS:- i do
> know that lower frequencies capture the general aspects of the image
> whereas the higher frequencies capture the more 'detailed' aspects
> (e.g. edges)]

In a real image the DC component will always be the largest one since 
every value in the image is summed with no phase factor.

If your data had zero mean and was mostly high frequency noise then the 
DC component would be insignificant, but the time series would contain 
negative values. Knowing that real images do not contain negative values 
allows data measured in frequency space to be processed to produce 
better quality images than the simple linear inverse can manage.

Regards,
Martin Brown

Message-ID:<98c25c7b-6f00-47e6-abe5-26b43c7dec35@u14g2000yqg.googlegroups.com>
Subject:

Re: Images in the frequency domain..

Date:Thu, 5 Feb 2009 12:48:33 +0100

On Feb 5, 11:02=A0am, Martin Brown <|||newspam...@nezumi.demon.co.uk>
wrote:
> ndesk wrote:
> > Hi,
>
> > I've been trying to understand more on frequency plots of images.
>
> > 1. Assuming a 1d example of just a strip of an image; in the frequency
> > map there are 'same' no. of frequencies as there are pixels. What is
> > the reason for this? Does this have something to do with the Nyquist
> > theorom.
>
> I am going to disagree with the others very slightly. If you consider
> the 1d strip as a time series then the Nyquist theorem says that to
> preserve all the information contained in it you have to sample up to
> and including the alternating frequency component.

Yes, but for discrete signals, this simply corresponds to counting the
dimensionality, i.e. not much of a theorem. The point is that for an
infinite continuous signal (i.e. an uncountable number of values in
both real space and frequency space) that has an upper frequency
bound, a countable set of samples suffices to represent it. Now, this
idea, i.e. the Nyquist-Shannon sampling theorem, is really pretty
simple, despite its status as a great truth of signal processing, and
indeed it is wrong, since real sampling bears little relation to it,
but it is not quite as simple as dimension counting.

illywhacker;