Zero padding fftw

On Dec 12, 2:36&#4294967295;pm, illywhacker <illywac...@gmail.com> wrote:
...
>
> Obviously you have never heard of superresolution.

You do not seem to be qualified to judge that of which other people
have heard.
>  In any case, the
> question is: what did the OP want?
> ...

The OP asked for help in correctly performing an interpolation by fft,
zero extending in the transformed domain and ifff.

> The case you are discussing is that in
> which:
>
> 1) only one signal in the range of the antialiasing is compatible with
> the values of the given samples;
>
> 2) the resampled signal required can be derived from the antialiased
> signal alone.
>
> We can assume (1), if the initial system is well-designed. But (2)
> renders the situation trivial,

You are indeed fortunate to find 2) trivial since it is the only
sensible use case for DSP.

>  and it is hard to believe this is what
> the OP wanted (remember he or she wants to increase the resolution).
> ...

Interpolation is a common tactic used to more accurately resolve the
location of features such as a peak or a zero crossing in a sampled
signal. In English, the ability "to more accurately resolve" is
correctly referred to as "increased resolution". This definition of
resolution is consistent with the OP's question, algorithm and
vocabulary and with 1) and 2).

Dale B. Dalrymple

dbd <dbd@ieee.org> wrote:
(snip)

> The OP asked for help in correctly performing an interpolation by fft,
> zero extending in the transformed domain and ifff.
(snip)

> Interpolation is a common tactic used to more accurately resolve the
> location of features such as a peak or a zero crossing in a sampled
> signal. In English, the ability "to more accurately resolve" is
> correctly referred to as "increased resolution". This definition of
> resolution is consistent with the OP's question, algorithm and
> vocabulary and with 1) and 2).

In optics, as I understand it, resolution comes from the ability
distinguish between two objects in an image, in place of one larger
object.  The wikipedia page Optical_resolution has much of the
explanation.

If you are looking through a telescope, you would like to know
if you see two stars that are close together, or just one.
In most cases, interpolation doesn't help.  Note that the
actual image is, as seen from earth, pretty much a point source.
Diffraction broadens that into an Airy pattern, which is pretty
much the circular version of the sinc.  

High quality lenses are diffraction limited, such that diffraction
effects limit the possible resolution.  For lower quality lenses,
the lens itself limits the resolution.

Interpolation doesn't increase the resolution.  It may allow
one to see what the shape of the expected sinc or Airy disk is,
but that is all.

Linear deconvolution also doesn't do much to improve resolution.

Non-linear deconvolution uses other properties of the system
to improve resolution, but that takes more than interpolation.
For example, absorption spectra can't go below zero or
above one.  Taking those constraints into account, and accurately
knowing the transfer function of the system, allows one to do
better than one might otherwise expect.

-- glen

On Dec 13, 12:44&#4294967295;am, dbd <d...@ieee.org> wrote:
> On Dec 12, 2:36&#4294967295;pm, illywhacker <illywac...@gmail.com> wrote:

> > Obviously you have never heard of superresolution.
>
> You do not seem to be qualified to judge that of which other people
> have heard.
>
> > &#4294967295;In any case, the
> > question is: what did the OP want?
> > ...
>
> The OP asked for help in correctly performing an interpolation by fft,
> zero extending in the transformed domain and ifff.
>
> > The case you are discussing is that in
> > which:
>
> > 1) only one signal in the range of the antialiasing is compatible with
> > the values of the given samples;
>
> > 2) the resampled signal required can be derived from the antialiased
> > signal alone.
>
> > We can assume (1), if the initial system is well-designed. But (2)
> > renders the situation trivial,
>
> You are indeed fortunate to find 2) trivial since it is the only
> sensible use case for DSP.

As I said: apparently you have not heard of superresolution. You seem
convinced that your knowledge and experience is the only knowledge and
experience relevant to DSP. From what I have seen so far, I do not
agree with you.

> > &#4294967295;and it is hard to believe this is what
> > the OP wanted (remember he or she wants to increase the resolution).
> > ...
>
> Interpolation is a common tactic used to more accurately resolve the
> location of features such as a peak or a zero crossing in a sampled
> signal. In English, the ability "to more accurately resolve" is
> correctly referred to as "increased resolution". This definition of
> resolution is consistent with the OP's question, algorithm and
> vocabulary and with 1) and 2).

Perhaps we have a difference of terminology. If the anti-aliasing and
sampling are correctly designed, then the anti-aliased signal is
uniquely determined by the samples. Therefore, any feature whatsoever
of the anti-aliased signal can be recovered from the samples. This is
not interpolation: one might call it reconstruction, but really it is
just a change of basis. Whether you express this in terms of
'resampling' is a matter of nomenclature only: it certainly does not
increase the resolution in any meaningful sense. No matter how close
together you make your samples, you will not be able to resolve any
features that were not encoded in the original samples.

However, if you know something about the class of signals you are
processing, then you can do better than this. To take Glen's example:
if you know that your original signal consists of point sources, then
you may be able to reconstruct their positions from the diffracted,
sampled image.

illywhacker;

On Mon, 13 Dec 2010 05:53:36 +0000 (UTC), glen herrmannsfeldt
<gah@ugcs.caltech.edu> wrote:

>dbd <dbd@ieee.org> wrote:
>(snip)
>
>> The OP asked for help in correctly performing an interpolation by fft,
>> zero extending in the transformed domain and ifff.
>(snip)
>
>> Interpolation is a common tactic used to more accurately resolve the
>> location of features such as a peak or a zero crossing in a sampled
>> signal. In English, the ability "to more accurately resolve" is
>> correctly referred to as "increased resolution". This definition of
>> resolution is consistent with the OP's question, algorithm and
>> vocabulary and with 1) and 2).
>
>In optics, as I understand it, resolution comes from the ability
>distinguish between two objects in an image, in place of one larger
>object.  The wikipedia page Optical_resolution has much of the
>explanation.
>
>If you are looking through a telescope, you would like to know
>if you see two stars that are close together, or just one.
>In most cases, interpolation doesn't help.  Note that the
>actual image is, as seen from earth, pretty much a point source.
>Diffraction broadens that into an Airy pattern, which is pretty
>much the circular version of the sinc.  
>
>High quality lenses are diffraction limited, such that diffraction
>effects limit the possible resolution.  For lower quality lenses,
>the lens itself limits the resolution.
>
>Interpolation doesn't increase the resolution.  It may allow
>one to see what the shape of the expected sinc or Airy disk is,
>but that is all.
>
>Linear deconvolution also doesn't do much to improve resolution.
>
>Non-linear deconvolution uses other properties of the system
>to improve resolution, but that takes more than interpolation.
>For example, absorption spectra can't go below zero or
>above one.  Taking those constraints into account, and accurately
>knowing the transfer function of the system, allows one to do
>better than one might otherwise expect.
>
>-- glen

Similar definitions of "resolution" exist in signal processing.   When
I worked on radar processing systems, the ability to resolve two point
targets, similar to your optical example of resolving two stars, was
the pertinent example.   The idea there, which I've seen described
fairly consistently for other applications, was that two sinx/x point
responses had to be able to be separated to about their 3dB points in
order to detect and "resolve" them separately.

So that's one definition of "resolution" that seems to be fairly
consistently applied.   In this context, interpolating additional
points does nothing to improve the resolution, which I think is why
that's usually the case that's made.

But there are other things that can be "resolved" from a signal, and
as Darrell alluded the locations of peaks (e.g., accurately estimating
frequency in a DFT output) or zero crossings can often be more
accurately located using interpolation.

So in that sense increasing the "resolution" by interpolation is
certainly possible, but it's not the usual way the term is used.  So,
as usual, it is important to know what is meant when "resolution" is
used in a discussion.


Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

On Mon, 13 Dec 2010 06:31:45 -0800 (PST), illywhacker
<illywacker@gmail.com> wrote:

>On Dec 13, 12:44=A0am, dbd <d...@ieee.org> wrote:
>> On Dec 12, 2:36=A0pm, illywhacker <illywac...@gmail.com> wrote:
>
>> > Obviously you have never heard of superresolution.
>>
>> You do not seem to be qualified to judge that of which other people
>> have heard.
>>
>> > =A0In any case, the
>> > question is: what did the OP want?
>> > ...
>>
>> The OP asked for help in correctly performing an interpolation by fft,
>> zero extending in the transformed domain and ifff.
>>
>> > The case you are discussing is that in
>> > which:
>>
>> > 1) only one signal in the range of the antialiasing is compatible with
>> > the values of the given samples;
>>
>> > 2) the resampled signal required can be derived from the antialiased
>> > signal alone.
>>
>> > We can assume (1), if the initial system is well-designed. But (2)
>> > renders the situation trivial,
>>
>> You are indeed fortunate to find 2) trivial since it is the only
>> sensible use case for DSP.
>
>As I said: apparently you have not heard of superresolution. You seem
>convinced that your knowledge and experience is the only knowledge and
>experience relevant to DSP. From what I have seen so far, I do not
>agree with you.

You seem convinced that Darrell is incorrect or not cognizant in this
area.   I'm convinced you're wrong about that.

>> > =A0and it is hard to believe this is what
>> > the OP wanted (remember he or she wants to increase the resolution).
>> > ...
>>
>> Interpolation is a common tactic used to more accurately resolve the
>> location of features such as a peak or a zero crossing in a sampled
>> signal. In English, the ability "to more accurately resolve" is
>> correctly referred to as "increased resolution". This definition of
>> resolution is consistent with the OP's question, algorithm and
>> vocabulary and with 1) and 2).
>
>Perhaps we have a difference of terminology. If the anti-aliasing and
>sampling are correctly designed, then the anti-aliased signal is
>uniquely determined by the samples. Therefore, any feature whatsoever
>of the anti-aliased signal can be recovered from the samples. This is
>not interpolation: one might call it reconstruction, but really it is
>just a change of basis.

What is not interpolation?  Sampling?

> Whether you express this in terms of
>'resampling' is a matter of nomenclature only: it certainly does not
>increase the resolution in any meaningful sense. No matter how close
>together you make your samples, you will not be able to resolve any
>features that were not encoded in the original samples.

But you may be able to more accurately locate things like peaks and
zero crossings, as Darrell mentioned.   Improving the ability to
locate a peak is sometimes said to better "resolve" its location.
It's not the more common usage of the term, but it is used that way.

>However, if you know something about the class of signals you are
>processing, then you can do better than this. To take Glen's example:
>if you know that your original signal consists of point sources, then
>you may be able to reconstruct their positions from the diffracted,
>sampled image.
>
>illywhacker;

I'm not sure that multidimensional processing is a good example to
make a point in this case.   The context so far has been single
streams. 


Eric Jacobsen
Minister of Algorithms
Abineau Communications
http://www.abineau.com

On Dec 13, 11:06�am, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
> On Mon, 13 Dec 2010 05:53:36 +0000 (UTC), glen herrmannsfeldt
>
>
>
>
>
> <g...@ugcs.caltech.edu> wrote:
> >dbd <d...@ieee.org> wrote:
> >(snip)
>
> >> The OP asked for help in correctly performing an interpolation by fft,
> >> zero extending in the transformed domain and ifff.
> >(snip)
>
> >> Interpolation is a common tactic used to more accurately resolve the
> >> location of features such as a peak or a zero crossing in a sampled
> >> signal. In English, the ability "to more accurately resolve" is
> >> correctly referred to as "increased resolution". This definition of
> >> resolution is consistent with the OP's question, algorithm and
> >> vocabulary and with 1) and 2).
>
> >In optics, as I understand it, resolution comes from the ability
> >distinguish between two objects in an image, in place of one larger
> >object. &#4294967295;The wikipedia page Optical_resolution has much of the
> >explanation.
>
> >If you are looking through a telescope, you would like to know
> >if you see two stars that are close together, or just one.
> >In most cases, interpolation doesn't help. &#4294967295;Note that the
> >actual image is, as seen from earth, pretty much a point source.
> >Diffraction broadens that into an Airy pattern, which is pretty
> >much the circular version of the sinc. &#4294967295;
>
> >High quality lenses are diffraction limited, such that diffraction
> >effects limit the possible resolution. &#4294967295;For lower quality lenses,
> >the lens itself limits the resolution.
>
> >Interpolation doesn't increase the resolution. &#4294967295;It may allow
> >one to see what the shape of the expected sinc or Airy disk is,
> >but that is all.
>
> >Linear deconvolution also doesn't do much to improve resolution.
>
> >Non-linear deconvolution uses other properties of the system
> >to improve resolution, but that takes more than interpolation.
> >For example, absorption spectra can't go below zero or
> >above one. &#4294967295;Taking those constraints into account, and accurately
> >knowing the transfer function of the system, allows one to do
> >better than one might otherwise expect.
>
> >-- glen
>
> Similar definitions of "resolution" exist in signal processing. &#4294967295; When
> I worked on radar processing systems, the ability to resolve two point
> targets, similar to your optical example of resolving two stars, was
> the pertinent example. &#4294967295; The idea there, which I've seen described
> fairly consistently for other applications, was that two sinx/x point
> responses had to be able to be separated to about their 3dB points in
> order to detect and "resolve" them separately.
>
> So that's one definition of "resolution" that seems to be fairly
> consistently applied. &#4294967295; In this context, interpolating additional
> points does nothing to improve the resolution, which I think is why
> that's usually the case that's made.
>
> But there are other things that can be "resolved" from a signal, and
> as Darrell alluded the locations of peaks (e.g., accurately estimating
> frequency in a DFT output) or zero crossings can often be more
> accurately located using interpolation.
>
> So in that sense increasing the "resolution" by interpolation is
> certainly possible, but it's not the usual way the term is used. &#4294967295;So,
> as usual, it is important to know what is meant when "resolution" is
> used in a discussion.
>
> Eric Jacobsen
> Minister of Algorithms
> Abineau Communicationshttp://www.abineau.com- Hide quoted text -
>
> - Show quoted text -

Certainly in astro one can refer to Rayleigh's or Dawes limits, but
there are tricks for seeing a little more than what those limits
allow. In the astronomical case of stars where for almost (there are
exceptions) all practical purposes are mathematical point sources, the
common trick to resolving close stars is to use an apodization filter
placed over the telescope's aperture. This filter will push the each
star's diffraction rings around at the expense of increasing the size
of the central airey discs. But this can be useful for locating
companion stars.

So in an analogous way one can think of making a window function have
a null at a key location to reveal an item of interest but at the
expense of losing something else.

Clay

On Dec 13, 11:15�am, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
> On Mon, 13 Dec 2010 06:31:45 -0800 (PST), illywhacker
>
>
>
> <illywac...@gmail.com> wrote:
> >On Dec 13, 12:44=A0am, dbd <d...@ieee.org> wrote:
> >> On Dec 12, 2:36=A0pm, illywhacker <illywac...@gmail.com> wrote:
>
> >> > Obviously you have never heard of superresolution.
>
> >> You do not seem to be qualified to judge that of which other people
> >> have heard.
>
> >> > In any case, the question is: what did the OP want?
> >> > ...
>
> >> The OP asked for help in correctly performing an interpolation by fft,
> >> zero extending in the transformed domain and ifff.
>
> >> > The case you are discussing is that in which:
>
> >> > 1) only one signal in the range of the antialiasing is compatible with
> >> > the values of the given samples;
>
> >> > 2) the resampled signal required can be derived from the antialiased
> >> > signal alone.
>
> >> > We can assume (1), if the initial system is well-designed. But (2)
> >> > renders the situation trivial,
>
> >> You are indeed fortunate to find 2) trivial since it is the only
> >> sensible use case for DSP.
>
> >As I said: apparently you have not heard of superresolution. You seem
> >convinced that your knowledge and experience is the only knowledge and
> >experience relevant to DSP. From what I have seen so far, I do not
> >agree with you.
>
> You seem convinced that Darrell is incorrect or not cognizant in this
> area. &#4294967295; I'm convinced you're wrong about that.
>

i would agree with you completely, Eric, except i think his name is
"Dale".  or did i completely screw up regarding who we're talking
about.

r b-j

On Dec 13, 4:15�pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
> On Mon, 13 Dec 2010 06:31:45 -0800 (PST), illywhacker

> <illywac...@gmail.com> wrote:
> >On Dec 13, 12:44=A0am, dbd <d...@ieee.org> wrote:
> >> On Dec 12, 2:36=A0pm, illywhacker <illywac...@gmail.com> wrote:

> >As I said: apparently you have not heard of superresolution. You seem
> >convinced that your knowledge and experience is the only knowledge and
> >experience relevant to DSP. From what I have seen so far, I do not
> >agree with you.
>
> You seem convinced that Darrell is incorrect or not cognizant in this
> area. &#4294967295; I'm convinced you're wrong about that.

On the contrary. It is Dale that is insisting that he speaks for all
of DSP. I am quite sure he is competent. However I am also quite sure
that he, like me, is limited.

illywhacker;

On Dec 13, 4:15�pm, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
> On Mon, 13 Dec 2010 06:31:45 -0800 (PST), illywhacker
> <illywac...@gmail.com> wrote:
> >On Dec 13, 12:44=A0am, dbd <d...@ieee.org> wrote:
> >> On Dec 12, 2:36=A0pm, illywhacker <illywac...@gmail.com> wrote:
>
> >> > =A0and it is hard to believe this is what
> >> > the OP wanted (remember he or she wants to increase the resolution).
> >> > ...
>
> >> Interpolation is a common tactic used to more accurately resolve the
> >> location of features such as a peak or a zero crossing in a sampled
> >> signal. In English, the ability "to more accurately resolve" is
> >> correctly referred to as "increased resolution". This definition of
> >> resolution is consistent with the OP's question, algorithm and
> >> vocabulary and with 1) and 2).
>
> >Perhaps we have a difference of terminology. If the anti-aliasing and
> >sampling are correctly designed, then the anti-aliased signal is
> >uniquely determined by the samples. Therefore, any feature whatsoever
> >of the anti-aliased signal can be recovered from the samples. This is
> >not interpolation: one might call it reconstruction, but really it is
> >just a change of basis.
>
> What is not interpolation? &#4294967295;Sampling?

I would not call a change of basis 'interpolation', but this is just
terminology. To give an example: I can uniquely represent a periodic
signal (i.e. a function on the circle) that has an upper bound on its
frequency content using a finite set of samples at regular intervals.
Alternatively, I can represent it by its finite set of Fourier
amplitudes. In either case, I can compute the value of the function at
any point I wish. I would not say that I have interpolated in doing
this. I have merely used a different description of the same thing. It
is when I do not know how to reconstruct the signal, i.e. when there
is more than one signal that could have produced the given samples,
that it is non-trivial.

> > Whether you express this in terms of
> >'resampling' is a matter of nomenclature only: it certainly does not
> >increase the resolution in any meaningful sense. No matter how close
> >together you make your samples, you will not be able to resolve any
> >features that were not encoded in the original samples.
>
> But you may be able to more accurately locate things like peaks and
> zero crossings, as Darrell mentioned. &#4294967295;

What you saying is true, if you use a particicular *algorithm* to
locate zero crossings (or peaks): resampling the reconstructed anti-
alised signal and then eyeballing the result. This is indeed one way
to do it. Again, using such a method, you will find only the zero
crossing in the unique anti-aliased signal corresponding to the
samples. If that is what interests you, fine.

> Improving the ability to
> locate a peak is sometimes said to better "resolve" its location.
> It's not the more common usage of the term, but it is used that way.

Sure - I do not really want to argue about the word 'resolution'. My
point is that to do anything non-trivial requires a model of your
signal class.

illywhacker;

On Dec 13, 11:23&#4294967295;am, Clay <c...@claysturner.com> wrote:
> On Dec 13, 11:06&#4294967295;am, eric.jacob...@ieee.org (Eric Jacobsen) wrote:
>
>
>
> > On Mon, 13 Dec 2010 05:53:36 +0000 (UTC), glen herrmannsfeldt
>
> > <g...@ugcs.caltech.edu> wrote:
> > >dbd <d...@ieee.org> wrote:
> > >(snip)
>
> > >> The OP asked for help in correctly performing an interpolation by fft,
> > >> zero extending in the transformed domain and ifff.
> > >(snip)
>
> > >> Interpolation is a common tactic used to more accurately resolve the
> > >> location of features such as a peak or a zero crossing in a sampled
> > >> signal. In English, the ability "to more accurately resolve" is
> > >> correctly referred to as "increased resolution". This definition of
> > >> resolution is consistent with the OP's question, algorithm and
> > >> vocabulary and with 1) and 2).
>
> > >In optics, as I understand it, resolution comes from the ability
> > >distinguish between two objects in an image, in place of one larger
> > >object. &#4294967295;The wikipedia page Optical_resolution has much of the
> > >explanation.
>
> > >If you are looking through a telescope, you would like to know
> > >if you see two stars that are close together, or just one.
> > >In most cases, interpolation doesn't help. &#4294967295;Note that the
> > >actual image is, as seen from earth, pretty much a point source.
> > >Diffraction broadens that into an Airy pattern, which is pretty
> > >much the circular version of the sinc. &#4294967295;
>
> > >High quality lenses are diffraction limited, such that diffraction
> > >effects limit the possible resolution. &#4294967295;For lower quality lenses,
> > >the lens itself limits the resolution.
>
> > >Interpolation doesn't increase the resolution. &#4294967295;It may allow
> > >one to see what the shape of the expected sinc or Airy disk is,
> > >but that is all.
>
> > >Linear deconvolution also doesn't do much to improve resolution.
>
> > >Non-linear deconvolution uses other properties of the system
> > >to improve resolution, but that takes more than interpolation.
> > >For example, absorption spectra can't go below zero or
> > >above one. &#4294967295;Taking those constraints into account, and accurately
> > >knowing the transfer function of the system, allows one to do
> > >better than one might otherwise expect.
>
> > >-- glen
>
> > Similar definitions of "resolution" exist in signal processing. &#4294967295; When
> > I worked on radar processing systems, the ability to resolve two point
> > targets, similar to your optical example of resolving two stars, was
> > the pertinent example. &#4294967295; The idea there, which I've seen described
> > fairly consistently for other applications, was that two sinx/x point
> > responses had to be able to be separated to about their 3dB points in
> > order to detect and "resolve" them separately.
>
> > So that's one definition of "resolution" that seems to be fairly
> > consistently applied. &#4294967295; In this context, interpolating additional
> > points does nothing to improve the resolution, which I think is why
> > that's usually the case that's made.
>
> > But there are other things that can be "resolved" from a signal, and
> > as Darrell alluded the locations of peaks (e.g., accurately estimating
> > frequency in a DFT output) or zero crossings can often be more
> > accurately located using interpolation.
>
> > So in that sense increasing the "resolution" by interpolation is
> > certainly possible, but it's not the usual way the term is used. &#4294967295;So,
> > as usual, it is important to know what is meant when "resolution" is
> > used in a discussion.
>
> > Eric Jacobsen
> > Minister of Algorithms
> > Abineau Communicationshttp://www.abineau.com-Hide quoted text -
>
> > - Show quoted text -
>
> Certainly in astro one can refer to Rayleigh's or Dawes limits, but
> there are tricks for seeing a little more than what those limits
> allow. In the astronomical case of stars where for almost (there are
> exceptions) all practical purposes are mathematical point sources, the
> common trick to resolving close stars is to use an apodization filter
> placed over the telescope's aperture. This filter will push the each
> star's diffraction rings around at the expense of increasing the size
> of the central airey discs. But this can be useful for locating
> companion stars.
>
> So in an analogous way one can think of making a window function have
> a null at a key location to reveal an item of interest but at the
> expense of losing something else.

One simple apodizing mask is a square. It increases the effective
resolution along the diagonals of the square at the expense of
resolution along the other symmetry axes, 45 degrees away. (This is
great for spectroscopes, where resolution perpendicular to the slit is
all that matters.) Like all apodizing masks, it has to be applied at
the time of data collection. As far as I know, you can't improve an
already existing image that way.

Jerry