2D image processing with FFTW

Hello group,

I'm having some trouble getting my code to work correctly using C++ and
libfftw (which is, may I remark, absolutely marvellous). Basically I'm
FFTing a picture (real to complex) and then performing and IFFT (just to
see if everything works as expected). Well, it does not - I'm having
some really stupid problem with which I now spent half a day. Can't
figure out what I'm doing wrong. I guess it's best if you see for yourself:

Here is P and IFFT(FFT(P)):
http://bildrian.de/n/b/f07459f1965c011f.jpg
http://bildrian.de/n/b/ed6eadb369ed3c0d.jpg

And another example demonstrating better what the problem is:
http://bildrian.de/n/b/f8edeaeb8e33f5c5.jpg
http://bildrian.de/n/b/b81e7db06a5b17b0.jpg

So, pictures are appearently smeared somehow in vertical direction. It
seems that the circle in the second example also gets scales in vertical
direction so it's more of an ellipse. However, I just cannot figure out
what I'm doing wrong. For the IFFT I'm filling up the top half of the
picture with the values I got from the r2c transform and zero the
remaining pixels.

Although I can post the code for the IFFT I'm using
(http://www.nopaste.com/p/aR42APDpb) I have the hope that someone just
looks at the characteristic distortion seen in the pictures and knows
where I should have a look... I'd really appreciate it.

Thanks in advance,
Kind regards,
Johannes

-- 
"Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
verl�sterung von Gott, Bibel und mir und bewusster Blasphemie."
         -- Prophet und Vision�r Hans Joss aka HJP in de.sci.physik
                         <48d8bf1d$0$7510$5402220f@news.sunrise.ch>

On Feb 18, 11:12�am, Johannes Bauer wrote:

> For the IFFT I'm filling up the top half of the picture with the values
> I got from the r2c transform and zero the> remaining pixels.

Definitely wrong.  A forward 2D FFT does a 1D FFT on the rows of data
- the result is complex with some symmetry if the input was real.
Then it does a 1D FFT on the columns.  The result is also complex, and
the symmetry is slightly different (it's based on quadrants).

Also, the 2D FFT can do its 1D FFTs on rows then columns, or columns
then rows - it's a separable process.

Here's a suggestion: do a complex in/out 2D FFT and look at the
results.  Then do a 2D inverse FFT.

Kevin

kevinjmcgee@netscape.net schrieb:
> On Feb 18, 11:12 am, Johannes Bauer wrote:
> 
>> For the IFFT I'm filling up the top half of the picture with the values
>> I got from the r2c transform and zero the> remaining pixels.
> 
> Definitely wrong.  A forward 2D FFT does a 1D FFT on the rows of data
> - the result is complex with some symmetry if the input was real.
> Then it does a 1D FFT on the columns.  The result is also complex, and
> the symmetry is slightly different (it's based on quadrants).

Ah, okay, this explains something. I was aware of the symmetry
relationship as this is exactly the reason why libfftw only outputs
(roughly) half the number of complex pixels when doing a real -> complex
transformation.

However, in my first tries of reversing using complex -> complex, I
filled up the columns wrong. When I got


abcdef
ghijkl
mnopqr

I filled them up with

abcdef
ghijkl
mnopqr
ghijkl
abcdef

when I suppose I should have used

abcdef
ghijkl
mnopqr
lkjihg
fedcba

I really didn't think about that. The resulting picture was an overlay
of Mona with herself rotated about 180�. So I guess stupidly without
thinking about it anymore I just used the "zero" solution which worked
(albeit gave wrong results).

> Also, the 2D FFT can do its 1D FFTs on rows then columns, or columns
> then rows - it's a separable process.

Yes, but since I'm doing the same transformation twice (only once with
the complex conjugate), this should not have an effect.

> Here's a suggestion: do a complex in/out 2D FFT and look at the
> results.  Then do a 2D inverse FFT.

I will try this tomorrow, first thing when I have a clear head again
(after a whole day of work I'm totally drained and would not be able to
produce sane code anyways). I'll also try to use the above relation and
see if it gets me anywhere (would save me roughly half the space which
would be nice).

Thanks a lot for your suggestion... at last the penny dropped :-) I'll
report back tomorrow.

Kind regards,
Johannes

-- 
"Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
verl�sterung von Gott, Bibel und mir und bewusster Blasphemie."
         -- Prophet und Vision�r Hans Joss aka HJP in de.sci.physik
                         <48d8bf1d$0$7510$5402220f@news.sunrise.ch>

On Feb 18, 11:12&#4294967295;am, Johannes Bauer <dfnsonfsdu...@gmx.de> wrote:
> So, pictures are appearently smeared somehow in vertical direction. It
> seems that the circle in the second example also gets scales in vertical
> direction so it's more of an ellipse. However, I just cannot figure out
> what I'm doing wrong. For the IFFT I'm filling up the top half of the
> picture with the values I got from the r2c transform and zero the
> remaining pixels.

As has been noted, this is wrong.

If you are using an r2c transform to take advantage of the real inputs
for the forward FFT, you almost certainly want to use FFTW's c2r
transform for the inverse.  This takes the output of r2c as input, and
saves you both the trouble of "filling" the array with the appropriate
symmetry and also a factor of 2 in time and memory.

If you want to deal with the full (albeit half redundant) array of the
transform, will be a lot easier just to use the complex-data FFT for
both directions.  (i.e. set the real parts of the input to your image
and the imaginary parts to zero).

Regards,
Steven G. Johnson

stevenj.mit@gmail.com schrieb:
> On Feb 18, 11:12 am, Johannes Bauer <dfnsonfsdu...@gmx.de> wrote:
>> So, pictures are appearently smeared somehow in vertical direction. It
>> seems that the circle in the second example also gets scales in vertical
>> direction so it's more of an ellipse. However, I just cannot figure out
>> what I'm doing wrong. For the IFFT I'm filling up the top half of the
>> picture with the values I got from the r2c transform and zero the
>> remaining pixels.
> 
> As has been noted, this is wrong.
> 
> If you are using an r2c transform to take advantage of the real inputs
> for the forward FFT, you almost certainly want to use FFTW's c2r
> transform for the inverse.  This takes the output of r2c as input, and
> saves you both the trouble of "filling" the array with the appropriate
> symmetry and also a factor of 2 in time and memory.

Indeed, I really do - however by browsing through the documentation I
did not notice I was stuck in the "Tutorial" chapter and thus did not
notice there was a specific function for performing a c2r transform...
although I thought it would be nice if there was one :-))

Turns all needed is a little RTFM of chapter 4.3.3, which explains
exactly what I want to do.

> If you want to deal with the full (albeit half redundant) array of the
> transform, will be a lot easier just to use the complex-data FFT for
> both directions.  (i.e. set the real parts of the input to your image
> and the imaginary parts to zero).

Nope, as you noted, c2r is exactly what I want. I use it now and it
works terrific.

Let me stress this again, libfftw is a really nice, well-documented,
exemplary piece of software which you can rightfully be proud of. And it
even comes with lots of frosting (it's blazingly fast speed, that is) :-))

Thanks for your help,
Kind regards,
Johannes

-- 
"Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
verl&#4294967295;sterung von Gott, Bibel und mir und bewusster Blasphemie."
         -- Prophet und Vision&#4294967295;r Hans Joss aka HJP in de.sci.physik
                         <48d8bf1d$0$7510$5402220f@news.sunrise.ch>