Image Subsampling Redux

It's even more interesting to ponder this:

Start with a set of sinusoidally weighted gray stripes going from peak black
to peak white.  This is a pure sinusoid plus a constant in one dimension.

If we align the stripes either in X or in Y then we can have all these
discussions about sampling and filtering as if it were all in 1-D.

What happens if the stripes are rotated in XY by 45 degrees (or some other
rotation)?  Then, it's reasonable to ask:
What is the Nyquist sampling interval necessary
*in X and Y*   [NB!]
in order to deal with the rotated regular frequency?

     A=1.0 . . . . . . . . . . . . . . . . . C   sqrt(2)_45
     |\                                      .
     | \\                                    .
     |   \\                                  .
     |     \                                 .
     |      \\                 \             .
     |        \\                \\           .
     |          \                /\D  1.0_45 .
     |           \\            //  \\        .
     |             \\         /      \       .
     |               \      //               .
     |                \ E //                 .
     |                  \\  [1/sqrt(2)]_45   .
     |                 // \\                 .
     |               //     \                .
     |             //        \\              .
     |            /            \\            .
     |          //               \           .
     |        //                  \\         .
     |       /                      \\       .
     |     //                         \      .
     |   //                            \\    .
     | //                                \\  .
     |/                                    \ .
    -X---------------------------------------B=1.0


One analysis seems to say that the sampling interval needs to reduce by
sqrt(2) so that the sample point shown at "C" is now at "D".
I've heard another to suggest it needs to reduce by 2 so that the sample
shown at "C" is now at "E" - which I rather doubt.
I believe there are other arguments having to do with the fact that the
sampling is 2-D, not simply 1-D, and the "adjacent" samples at "A" and "B"
make up for the lack of a sample at "D" or "E" - leaving the sample at "C"
to be adequate.

Is there a good reference to sampling rate limits for 2-D that deals with
this question?

Fred

So, no clue or ....?

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<7POdnc5K-qKe4PLdRVn-uw@centurytel.net>...
> So, no clue or ....?

2D sampling is somewhat trickier.
In your example, rotation alters bandwidths in X and Y directions.
If strips are aligned to X or Y directions, only one axis has max
bandwidths while the other axis has only DC components.
So when you rotate it, say by 45 degree, both bandwidths become 
identical. One is reduced by 1/sqrt(2) and the other increased to the
same bandwith. However, the number of samples required does not
change. You need to satisfy Nyquist sampling density regardless
of rotation. 

Suppose in your example, which is basically a 1-D signal rotated by 45
degree,
requires N number of samples before rotation.
If you maintained the sampling structure along with the signal, then
you would end up with a diagonal sampling pattern after the rotation
with N samples within the resulting 2-D signal. It's clear that
you can restore the signal from those N samples since nothing has been
changed in terms of sample values and the signal except that you know
sampling line has been rotated 45 degree.

Now your sampling structure need not be restricted to a line in the 
2-D space. You need N samples within the support of the signal
(Nyquist sampling density). However, there are restrictions on how
these sampling points can be distrubuted in a 2-D space 
depending on X and Y bandwidths. 

This boils down to a singularity issue of a
matrix which gives frequency domain samples (2D DFT)
from non-uniform spatial domain samples.

REF:
S.P. Kim, N.K. Bose," Reconstruction of 2-D Discrete (spectrum)
Signals from Nonuniformly 	Spaced Samples,", IEE Proceedings - F,
Radar and Signal Processing, Vol. 137, Pt F, No.3, pp, 197-204, June
1990.

Hope it helps.

Seung

Seung wrote:
> 
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message news:<7POdnc5K-qKe4PLdRVn-uw@centurytel.net>...
> > So, no clue or ....?
> 
> 2D sampling is somewhat trickier.
> In your example, rotation alters bandwidths in X and Y directions.
> If strips are aligned to X or Y directions, only one axis has max
> bandwidths while the other axis has only DC components.
> So when you rotate it, say by 45 degree, both bandwidths become
> identical. One is reduced by 1/sqrt(2) and the other increased to the
> same bandwith. However, the number of samples required does not
> change. You need to satisfy Nyquist sampling density regardless
> of rotation.

If you *know* that the signal is rotated 45 degrees and is 1
dimensional you:

a) don't need to sample 2d - just sampling in X or Y will
suffice.
b) can increase the sample spacing by sqrt(2).

This will satisfy Nyquist. However, you will need to increase
the dynamic range of your measurements to achieve the same SNR.

I guess all that hinges on what is meant by "know".

-jim

> 
> Suppose in your example, which is basically a 1-D signal rotated by 45
> degree,
> requires N number of samples before rotation.
> If you maintained the sampling structure along with the signal, then
> you would end up with a diagonal sampling pattern after the rotation
> with N samples within the resulting 2-D signal. It's clear that
> you can restore the signal from those N samples since nothing has been
> changed in terms of sample values and the signal except that you know
> sampling line has been rotated 45 degree.
> 
> Now your sampling structure need not be restricted to a line in the
> 2-D space. You need N samples within the support of the signal
> (Nyquist sampling density). However, there are restrictions on how
> these sampling points can be distrubuted in a 2-D space
> depending on X and Y bandwidths.
> 
> This boils down to a singularity issue of a
> matrix which gives frequency domain samples (2D DFT)
> from non-uniform spatial domain samples.
> 
> REF:
> S.P. Kim, N.K. Bose," Reconstruction of 2-D Discrete (spectrum)
> Signals from Nonuniformly       Spaced Samples,", IEE Proceedings - F,
> Radar and Signal Processing, Vol. 137, Pt F, No.3, pp, 197-204, June
> 1990.
> 
> Hope it helps.
> 
> Seung


-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 100,000 Newsgroups - 19 Different Servers! =-----

"jim" <"N0sp"@m.sjedging@mwt.net> wrote in message
news:40716557_4@corp.newsgroups.com...
>
>
> Seung wrote:
> >
> > "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:<7POdnc5K-qKe4PLdRVn-uw@centurytel.net>...
> > > So, no clue or ....?
> >
> > 2D sampling is somewhat trickier.
> > In your example, rotation alters bandwidths in X and Y directions.
> > If strips are aligned to X or Y directions, only one axis has max
> > bandwidths while the other axis has only DC components.
> > So when you rotate it, say by 45 degree, both bandwidths become
> > identical. One is reduced by 1/sqrt(2) and the other increased to the
> > same bandwith. However, the number of samples required does not
> > change. You need to satisfy Nyquist sampling density regardless
> > of rotation.
>
> If you *know* that the signal is rotated 45 degrees and is 1
> dimensional you:
>
> a) don't need to sample 2d - just sampling in X or Y will
> suffice.
> b) can increase the sample spacing by sqrt(2).
>
> This will satisfy Nyquist. However, you will need to increase
> the dynamic range of your measurements to achieve the same SNR.
>
> I guess all that hinges on what is meant by "know".

Jim,

I'm talking about sampling and reconstruction ala Nyquist.  I'm not talking
about reconstructing a "known polynomial" from discrete values of that
polynomial.  So, there would be no way to know that the signal were rotated
45 degrees.  That's a "simple test pattern", if you will, to pose the
question.

Here is the essential difference:
- to reconstruct a sine wave's phase if I know the frequency and amplitude I
only need two samples of high signal to noise ratio and accurate temporal
registration.  I don't know of any real world  signal processing problems
that ask for this and so I don't find it very interesting.  That doesn't
mean such applications don't exist!
- to reconstruct a general sine wave of unknown amplitude and unknown
frequency, Nyquist says we have to sample it higher than 2x the frequency
for infinite time.  We don't like infinite time so we allow errors and add
some guard band below 2x the frequency.  That is the essence of my question.
"What is the X and Y Nyquist frequency if we are going to consider the type
of test signal I posed?"

So, one says "what if it's rotated by "phi"? and recognizes that 45 degrees
is the worst case in some sense.  But 45 degrees isn't "known" when one is
selecting a sample rate.

If you want to assert that increasing the sample spacing by sqrt(2) in x and
in y is necessary, then tell us why.  It seems overkill.  And, that was the
essence of my question.  I certainly grant you that in a practical situation
that can afford it, that might actually be a good approach.

Fred

"Seung" <kim.seung@sbcglobal.net> wrote in message
news:fdf92243.0404042231.1d752e99@posting.google.com...
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:<7POdnc5K-qKe4PLdRVn-uw@centurytel.net>...
> > So, no clue or ....?
>
> 2D sampling is somewhat trickier.
> In your example, rotation alters bandwidths in X and Y directions.
> If strips are aligned to X or Y directions, only one axis has max
> bandwidths while the other axis has only DC components.
> So when you rotate it, say by 45 degree, both bandwidths become
> identical. One is reduced by 1/sqrt(2) and the other increased to the
> same bandwith. However, the number of samples required does not
> change. You need to satisfy Nyquist sampling density regardless
> of rotation.
>
> Suppose in your example, which is basically a 1-D signal rotated by 45
> degree,
> requires N number of samples before rotation.
> If you maintained the sampling structure along with the signal, then
> you would end up with a diagonal sampling pattern after the rotation
> with N samples within the resulting 2-D signal. It's clear that
> you can restore the signal from those N samples since nothing has been
> changed in terms of sample values and the signal except that you know
> sampling line has been rotated 45 degree.
>
> Now your sampling structure need not be restricted to a line in the
> 2-D space. You need N samples within the support of the signal
> (Nyquist sampling density). However, there are restrictions on how
> these sampling points can be distrubuted in a 2-D space
> depending on X and Y bandwidths.
>
> This boils down to a singularity issue of a
> matrix which gives frequency domain samples (2D DFT)
> from non-uniform spatial domain samples.

I think you're saying something like this:

If we lowpass the 2-D data with a brick wall cylinder filter then the
Fourier Transform is a Mexican Hat kind of "sinc" of rotation.  We need to
sample at the zero crossings of the sinc same as in 1-D.  So, we can
construct a sample rate in X and Y on that basis I suppose.  So there will
be a peak of this "hat" at each sample point and no reconstruction result
from one sample will overlap any other sample point - making the
reconstruction simple to envision.  Except it isn't so easy to envision in
2-D.

Instead of saying there have to be so many samples per unit time, now we're
saying there have to be so many samples per unit area.  Is that right?

So, uniform sampling in X and Y that will satisfy the "test signal" of a
sine surface oriented 0 degrees or 90 degrees (the two simple cases) will
continue to satisfy the sampling criterion *exactly*? if the test image is
rotated to somewhere in between?  Is that right?

If so, it suggests that the "adjacent" samples do come into the picture.  We
aren't stuck with using 1-D analysis on a slice where the sample interval at
45 degrees is worst case larger than the X or Y interval by a factor of
sqrt(2).
This says that the frequency limit at 45 degrees is the same as the
frequency limit in X or in Y for a given X and Y sampling interval.
This says that if the rotation is arbitrary - as real images will be - then
analyzing for spatial frequency bandwidth in 1-D is adequate and no concern
regarding rotation is necessary.  Is that right?

Fred

Fred Marshall wrote:
>
> 
> So, one says "what if it's rotated by "phi"? and recognizes that 45 degrees
> is the worst case in some sense.  But 45 degrees isn't "known" when one is
> selecting a sample rate.

No it's not the worst case. Its the opposite. Examine what the 1
dimensional signal you describe 'looks like' to the x and y
axis. The x will see a frequency that is sqrt(2) lower in
frequency than it does if the wave form is directed along the x
axis.  

> 
> If you want to assert that increasing the sample spacing by sqrt(2) in x and
> in y is necessary, then tell us why.  It seems overkill.  And, that was the
> essence of my question.  I certainly grant you that in a practical situation
> that can afford it, that might actually be a good approach.

I didn't say it was necessary I said you *could* sample it at a
lower frequency and still satisfy Nyquist so there will be no
problem at the same frequency.
	If you define the frequency content of 2d as orthogonal 1D
signals then there is no problem. A more interesting question is
what is the frequency content of a 2d signal emanating from a
point. If you take a sinusoid and revolve it around a point so
that the cross-section is the same in every direction, then what
is the minimum uniform sampling needed to accurately reconstruct
the shape from the samples.

-jim


-jim


-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 100,000 Newsgroups - 19 Different Servers! =-----

"jim" <"N0sp"@m.sjedging@mwt.net> wrote in message
news:4071ae23_1@corp.newsgroups.com...
>
>
> Fred Marshall wrote:
> >
> >
> > So, one says "what if it's rotated by "phi"? and recognizes that 45
degrees
> > is the worst case in some sense.  But 45 degrees isn't "known" when one
is
> > selecting a sample rate.
>
> No it's not the worst case. Its the opposite. Examine what the 1
> dimensional signal you describe 'looks like' to the x and y
> axis. The x will see a frequency that is sqrt(2) lower in
> frequency than it does if the wave form is directed along the x
> axis.

Jim,

I seem to not have described the situtation / question very well.  We seem
to be hung up on the definition of the problem.

I understand perfectly about the apparent frequencies in X and Y and the
sample rates in those directions.  I meant to say that it appears to have
the worst case, i.e. lowest, sample rate when the test image is rotated 45
degrees - IF you look at the sample rate along a line of highest frequency.
Then, if the X and Y intervals are 1.0, the interval at 45 degrees is
sqrt(2).  Any other angle gets closer to X or to Y and the sample interval
approaches 1.0.

So, the question was / is: if the test image is rotated such that the sine
peaks and troughs are parallel to a line at 135 degrees <> 315 degrees then
the maximum frequency is in the direction of 45 degrees <> 225 degrees.  In
that latter direction the distance between samples along any 45 degree line
is sqrt(2).  Is this adequate sampling for this test image with this
rotation?

Some have argued that it is not and I just don't know - so I'm asking.

Fred

Fred Marshall wrote:
>
> 
> I understand perfectly about the apparent frequencies in X and Y and the
> sample rates in those directions.  I meant to say that it appears to have
> the worst case, i.e. lowest, sample rate when the test image is rotated 45
> degrees - IF you look at the sample rate along a line of highest frequency.
> Then, if the X and Y intervals are 1.0, the interval at 45 degrees is
> sqrt(2).  Any other angle gets closer to X or to Y and the sample interval
> approaches 1.0.
> 
> So, the question was / is: if the test image is rotated such that the sine
> peaks and troughs are parallel to a line at 135 degrees <> 315 degrees then
> the maximum frequency is in the direction of 45 degrees <> 225 degrees.  In
> that latter direction the distance between samples along any 45 degree line
> is sqrt(2).  Is this adequate sampling for this test image with this
> rotation?
> 

You haven't made it clear, but I think you are saying that your
sampling matrix is composed of rows in the x direction and
columns in the y direction. So the 'apparent' frequencies in x
and y are all you have. And as I said before if your waveform
will always be rotated and 1D as you describe you could increase
the frequency past Nyquist and reconstruct the signal perfectly
from the samples in any given row or column.

	But maybe your saying that you are viewing the matrix as
rotated so that you have rows and columns running in what we
would normally view as the diagonal. It would then appear to be
that the waveform is not sufficiently sampled to meet the
Nyquist criteria. But when you do this you are only looking at
half the samples. That is to say, when you define the rows and
columns at a diagonal there are 2 such matrices that are
interleaved. Either one taken in isolation would not have the
bandwidth to sample your signal, but the combination of the two
do.

-jim 


> Some have argued that it is not and I just don't know - so I'm asking.
> 
> Fred


-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 100,000 Newsgroups - 19 Different Servers! =-----

"jim" <"N0sp"@m.sjedging@mwt.net> wrote in message
news:4072ac29_3@corp.newsgroups.com...
>
>
> Fred Marshall wrote:
> >
> >
> > I understand perfectly about the apparent frequencies in X and Y and the
> > sample rates in those directions.  I meant to say that it appears to
have
> > the worst case, i.e. lowest, sample rate when the test image is rotated
45
> > degrees - IF you look at the sample rate along a line of highest
frequency.
> > Then, if the X and Y intervals are 1.0, the interval at 45 degrees is
> > sqrt(2).  Any other angle gets closer to X or to Y and the sample
interval
> > approaches 1.0.
> >
> > So, the question was / is: if the test image is rotated such that the
sine
> > peaks and troughs are parallel to a line at 135 degrees <> 315 degrees
then
> > the maximum frequency is in the direction of 45 degrees <> 225 degrees.
In
> > that latter direction the distance between samples along any 45 degree
line
> > is sqrt(2).  Is this adequate sampling for this test image with this
> > rotation?
> >
>
> You haven't made it clear, but I think you are saying that your
> sampling matrix is composed of rows in the x direction and
> columns in the y direction. So the 'apparent' frequencies in x
> and y are all you have. And as I said before if your waveform
> will always be rotated and 1D as you describe you could increase
> the frequency past Nyquist and reconstruct the signal perfectly
> from the samples in any given row or column.
>
> But maybe your saying that you are viewing the matrix as
> rotated so that you have rows and columns running in what we
> would normally view as the diagonal. It would then appear to be
> that the waveform is not sufficiently sampled to meet the
> Nyquist criteria. But when you do this you are only looking at
> half the samples. That is to say, when you define the rows and
> columns at a diagonal there are 2 such matrices that are
> interleaved. Either one taken in isolation would not have the
> bandwidth to sample your signal, but the combination of the two
> do.

Jim,

The question is not about what is sufficient, it's about what is necessary.
So, sure, one could increase the sample rate a whole lot in order to make
sure that a marginal situation was made to be certainly not marginal.  But
this is not a question about what might be done that would surely work.
It's a question about theoretical limits.  Just like Nyquist in 1-D.

There's not really a "matrix" until the sampling is done.  Before the
sampling is done is a set of coordinates for samples to be taken.  Those
coordinates I'm using are:
....
.... (-2,-2) (-2,-1) (-2,0) (-2,1) (-2,2) ...
.... (-1,-2) (-1,-1) (-1,0) (-1,1) (-1,2) ...
.... (0,-2)  (0,-1)  (0,0)  (0,1)  (0,2) ...
.... (1,-2)  (1,-1)  (1,0)  (1,1)  (1,2) ...
.... (2,-2)  (2,-1)  (2,0)  (2,1)  (2,2) ...
....

Once the samples are taken, the matrix has to be described subject to those
underlying coordinates.

The distance from (0,0) to (0,1) and from (0,0) to (1,0) is 1.0
The distance from (0,0) to (1,1) and from (1,0) to (2,1) is sqrt(2)
If a sinusoidal image is aligned with the latter, what is the necessary
sampling interval in X and Y?  are 1 and 1 still adequate or is some smaller
interval necessary?  How is the correct one of these assertions justified?

We have one paper cited that deals with irregular sampling of images.
What if the sampling intervals are regular and equal?
What is the fundamental analysis that determines the maximum allowable
sampling interval in X and Y?

I hope this expression of the situation and the queston is clearer.

Fred