FPGA Central

I've browsed a bit, so hopefully I've got all my information in order.
I haven't been able to find an answer for this specific problem.

It's for image processing. I'm simplifying 2D regions by applying
low-pass filters to their contours. Specifically, I take an 8-connected
clockwise contour of (arbitrary) n points, and make two new functions,
x(i) and y(i), out of the points' coordinates. Then I do a DFT on each,
apply a Gaussian or low-pass cutoff filter, inverse DFT, and replot. It
works like a charm if I use a naive O(n^2) DFT implementation - but of
course, it's very slow.

The problem is that I'm stuck with a radix-2 FFT, for reasons best kept
to myself. Here are the features of my problem:

1. The functions are KNOWN to be periodic.
2. I need an exact spectrum, or I can't reconstruct the exact contour.
3. I can't downsample or upsample, or I can't reconstruct the exact
contour.

I've tried zero padding, padding with the average value, and padding
with a truncated copy of the function, and none of them worked.
(Obviously, windowing isn't going to help, because I need to be able to
reconstruct the exact contour. I'm picky that way.)

Is there a way I can use a radix-2 FFT on a known periodic signal of
arbitrary length?

"lord trousers" <[email protected]> wrote in message
news:[email protected] oups.com...

> Is there a way I can use a radix-2 FFT on a known periodic signal of
> arbitrary length?

From the nature of your post I think the most trouble-free
approach for you would be to use the chirp-Z algorithm, q.v.

--
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end

On 2005-11-03 01:49:18 -0400, "lord trousers" <[email protected]> said:

> I've browsed a bit, so hopefully I've got all my information in order.
> I haven't been able to find an answer for this specific problem.
>
> It's for image processing. I'm simplifying 2D regions by applying
> low-pass filters to their contours. Specifically, I take an 8-connected
> clockwise contour of (arbitrary) n points, and make two new functions,
> x(i) and y(i), out of the points' coordinates. Then I do a DFT on each,
> apply a Gaussian or low-pass cutoff filter, inverse DFT, and replot. It
> works like a charm if I use a naive O(n^2) DFT implementation - but of
> course, it's very slow.
>
> The problem is that I'm stuck with a radix-2 FFT, for reasons best kept
> to myself. Here are the features of my problem:
>
> 1. The functions are KNOWN to be periodic.
> 2. I need an exact spectrum, or I can't reconstruct the exact contour.
> 3. I can't downsample or upsample, or I can't reconstruct the exact
> contour.
>
> I've tried zero padding, padding with the average value, and padding
> with a truncated copy of the function, and none of them worked.
> (Obviously, windowing isn't going to help, because I need to be able to
> reconstruct the exact contour. I'm picky that way.)
>
> Is there a way I can use a radix-2 FFT on a known periodic signal of
> arbitrary length?

The chirp-z transform is a representation of a Fourier transform as
a convolution. Then just use your 2^k FFT to do the convolution. This
set of tricks is usually only brought out for folks who want to do FTs
of large primes but still want N log ( N ) performance. The coefficient
becomes more noticable. This representation of an FT as a convolution is
very flexible but does take more space.

There is another highly number theoretic representation of an FT as a
convolution but you only get its tighter use of space if you can match
its number theory requirements.

Now that you know what to look for try the usual places.

Gordon Sande wrote:
> On 2005-11-03 01:49:18 -0400, "lord trousers" <[email protected]> said:
>
> > I've browsed a bit, so hopefully I've got all my information in order.
> > I haven't been able to find an answer for this specific problem.
> >
> > It's for image processing. I'm simplifying 2D regions by applying
> > low-pass filters to their contours. Specifically, I take an 8-connected
> > clockwise contour of (arbitrary) n points, and make two new functions,
> > x(i) and y(i), out of the points' coordinates. Then I do a DFT on each,
> > apply a Gaussian or low-pass cutoff filter, inverse DFT, and replot. It
> > works like a charm if I use a naive O(n^2) DFT implementation - but of
> > course, it's very slow.
> >
> > The problem is that I'm stuck with a radix-2 FFT, for reasons best kept
> > to myself. Here are the features of my problem:
> >
> > 1. The functions are KNOWN to be periodic.
> > 2. I need an exact spectrum, or I can't reconstruct the exact contour.
> > 3. I can't downsample or upsample, or I can't reconstruct the exact
> > contour.
> >
> > I've tried zero padding, padding with the average value, and padding
> > with a truncated copy of the function, and none of them worked.
> > (Obviously, windowing isn't going to help, because I need to be able to
> > reconstruct the exact contour. I'm picky that way.)
> >
> > Is there a way I can use a radix-2 FFT on a known periodic signal of
> > arbitrary length?
>
> The chirp-z transform is a representation of a Fourier transform as
> a convolution. Then just use your 2^k FFT to do the convolution. This
> set of tricks is usually only brought out for folks who want to do FTs
> of large primes but still want N log ( N ) performance. The coefficient
> becomes more noticable. This representation of an FT as a convolution is
> very flexible but does take more space.
>
> There is another highly number theoretic representation of an FT as a
> convolution but you only get its tighter use of space if you can match
> its number theory requirements.
>
> Now that you know what to look for try the usual places.

Thanks! I'll go look for that.