Page 1 of 1

multiplication in the fourier domain

Posted: 2012-12-06T19:10:23-07:00
by toasty
I am experimenting with the FFT and implementing convolution through it as detailed on this page:
http://www.imagemagick.org/Usage/fourier/fft_math/

The kernel I'm using is a circle generated using IM. This code snippet, modified from the above URL. This is what it's trying to do:
Line 1: creates the circle, saves it to circle.png, then fft's it into magnitude/phase
Line 2: finds the mean (DC) of the circle image and divides by that mean. This is most probably because the FFT is unnormalized and will multiply by a constant, so this operation is set to undo that
Line 3: Pulls in the image I want to convolve and crops the top left 128x128 of it, then fft's it
Line 4: performs the multiplication of the magnitudes
Line 5: performs the addition of phases. I'm not too sure why it is adding gray50 and what the -flatten is for.
Line 6: removes the unnecessary layers, ift's and saves.

Code: Select all

convert \( -size 128x128 xc:black -fill white -draw "circle 64,64 70,64" -write circle.png -roll -64-64 -fft \)\
 \( -clone 0 -crop 1x1+64+64 +repage -scale 128x128 -clone 0 -compose divide -composite \) -swap 0 +delete \
 \( image.jpg -crop 128x128+0+0 -fft \) \
 \( -clone 0,2 -compose multiply -composite \) \
 \( -clone 1,3 -compose add -background gray50 -flatten \) \
 -delete 0-3 -ift -compress none image_convolved1.png
The above code doesn't work for me, it produces a dark output. The left is the original image, and the right is output
Image

However if I do this:

Code: Select all

convert circle.png -roll -64-64 -fft\
  \( -clone 0 -crop 1x1+64+64 +repage -scale 128x128 -clone 0 -compose divide -composite \) -swap 0 +delete \
  \( image.jpg -crop 128x128+0+0 -fft \) \
  \( -clone 0,2 -compose multiply -composite \) \
  \( -clone 1,3 -compose add -background gray50 -flatten \) \
  -delete 0-3 -ift  image_convolved2.png
It works:
Image

The only difference is that it uses the circle saved in the above operation from the file, rather than being created by IM directly.

Can someone explain why the first one fails, but the second works?

Thanks.

Re: multiplication in the fourier domain

Posted: 2012-12-06T19:33:15-07:00
by el_supremo
I can't try that command right now but try replacing the first line with this:

Code: Select all

convert \( circle.png -roll -64-64 -fft \) \
Pete

Re: multiplication in the fourier domain

Posted: 2012-12-06T20:20:59-07:00
by fmw42
try disabling the alpha channel created by -draw in your first line also try using +write to prevent the png format from affecting the subsequent commands

convert \( -size 128x128 xc:black -fill white -draw "circle 64,64 70,64" -alpha off +write circle.png -roll -64-64 -fft \)\

Since one is not using HDRI mode, the following combines the phase images taking into account that the phase has been scaled from the range -pi to +pi to the range 0 to pi (and combing by addition is modulo pi) and then to the range 0 to 1, so is now modulo 1. IM in non-hdri cannot handle negative value, so the phase is scaled between full black and full white (0 to quantumrange or normalized to 0 to 1)

\( -clone 1,3 -compose add -background gray50 -flatten \) \

This is represented in math at http://www.imagemagick.org/Usage/fourie ... /#multiply

Re: multiplication in the fourier domain

Posted: 2012-12-07T12:06:20-07:00
by fmw42
Comment from Anthony:

"add" composition is modulo. and a 50% gray is also modulo added to the result.
see http://www.imagemagick.org/Usage/compose/#modulus_add (which is the newer form of add, which appears to be deprecated)

If value1 and value2 are the actual values (without bias), then the modulo addition using flatten becomes... modulo( value1 + 50% + value2 + 50% + 50%) or just (value1 + value2 + 50%bias). Whci his what we want.

However, in later versions of IM gray50% is non-linear and gray(50%) is linear. So the command may need to be changed to

\( -clone 1,3 -compose add -background "gray(50%) -flatten \) \

Re: multiplication in the fourier domain

Posted: 2012-12-07T18:24:58-07:00
by toasty
Thanks fmw42.

-alpha off gets the convolution to work and thanks also for the tip on using +write instead of -write and the info on the phase and adding the gray.

Re: multiplication in the fourier domain

Posted: 2012-12-07T18:49:12-07:00
by fmw42
Another reference for FFT is my tutorial at http://www.fmwconcepts.com/imagemagick/ ... urier.html. This is in addition to Anthony's version at http://www.imagemagick.org/Usage/fourier/.

Both may? need some updating due to the colorspace and grayscale changes referenced at viewtopic.php?f=4&t=21269

Re: multiplication in the fourier domain

Posted: 2012-12-07T19:11:38-07:00
by toasty
Thanks for the link fmw, I've already been using a lot of the info from your page.

I'm wanting to FFT a lot images and convolve with a lot of kernels. So I'm trying to FFT my images (both the image and the kernel) and save the FFT'd version to a miff: file. I pre-divide by the mean in the kernels before saving so later I only need to worry about the point-wise multiplications of the kernel I choose with the image I choose.

This is what I do to save the image:

Code: Select all

convert 016217.jpg -fft miff:016217_FFT.mif
This is what I do to create and save the kernel:

Code: Select all

convert -size 1200x1200 xc:black -fill white -draw "circle 99,99,109,99" -alpha off  +write circle_010.png -roll -99-99 -fft \( -clone 0 -crop 1x1+600+600 +repage -scale 1200x1200 -clone 0 -compose divide -composite -swap 0 +delete \) miff:circle_FFT_010.mif
Then this is what I do to point-wise multiply and IFT:

Code: Select all

convert -alpha off 016217_FFT.mif -alpha off circle_FFT_010.mif -alpha off   \( -clone 0,2 -compose multiply -composite \) \( -clone 1,3 -compose add -background gray50 -flatten \) -delete 0-3 -ift -crop 1200x900+0+0 016217_r010.png
I wasn't sure whether I needed the -alpha off in the last line, and where it should go if it's needed, so I put it around all the images loaded from the mif files. However I am getting dark images again.

Any idea what I'm doing wrong?

Re: multiplication in the fourier domain

Posted: 2012-12-07T20:08:20-07:00
by fmw42
Best to put your parenthesis properly and use line continuations to make it more readable. You should not need to preface with MIFF: (though it should not hurt). Should not need all the -alpha off; only after the -draw. So try (though untested)

convert 016217.jpg -fft 016217_FFT.mif

convert -size 1200x1200 xc:black -fill white -draw "circle 99,99,109,99" -alpha off +write circle_010.png -roll -99-99 -fft \
\( -clone 0 -crop 1x1+600+600 +repage -scale 1200x1200 \) \
\( -clone 2 -clone 0 -compose divide -composite \) \
-delete 2 +swap \
circle_FFT_010.mif


convert 016217_FFT.mif circle_FFT_010.mif \
\( -clone 0,2 -compose multiply -composite \) \
\( -clone 1,3 -compose add -background gray50 -flatten \) \
-delete 0-3 -ift -crop 1200x900+0+0 +repage 016217_r010.png

If that does not work, then try substituting "gray(50%)" for gray50 ---- note include the quotes.

If this does not work, then provide a link to just the input image, so we can test with it.

Re: multiplication in the fourier domain

Posted: 2012-12-08T09:21:05-07:00
by toasty
Hi fmw42,

I'm not sure why, but in my version of IM, I need to preface with miff: It doesn't create a proper .mif file without it. I'm using a version which I compiled myself with HDRI, if that makes a difference.

After tinkering, I've managed to get it to work. For anyone else who might be interested, this is what worked for me:
1) Turn the jpg image into miff format:

Code: Select all

convert image.jpg -fft miff:image.mif
2) Create the kernel and save it to circle_FFT_010.mif:

Code: Select all

convert -size 1200x1200 xc:black -fill white -draw "circle 99,99,109,99" -alpha off +write circle_010.png -roll -99-99 -fft \
\( -clone 0 -crop 1x1+600+600 +repage -scale 1200x1200 -clone 0 -compose divide -composite \) \
-swap 0 +delete miff:circle_FFT_010.mif
This is what I had to modify to get it to work, I'll briefly describe what it's doing.
Line 1: First it draws a circle at center 99,99 of radius 10 pixels. It then rolls the center up to 0,0 which the fourier transform takes as its origin, then it performs the fourier transform
Line 2: The purpose of this line is to find the mean (DC value) of the image which is located at the center of the fft image (600,600 in this case) and divide the entire image by this value
Line 3: shifts this scaled down version to layer 0, and deletes the old layer 0, then saves the new modified fft to circle_FFT_010.mif
I'm not sure why, but when I wrote it the way you proposed, it didn't work.

3) load the two .mif files, pointwise multiply in the freq domain, ift them back to the time-domain:

Code: Select all

convert circle_FFT_010.mif image.mif \
 \( -clone 0,2 -compose multiply -composite \) \
 \( -clone 1,3 -compose add -background gray50 -flatten \) \
 -delete 0-3 -ift -crop 1200x900+0+0 +repage image_r010.png
Thanks, fmw for all your suggestions and help

Re: multiplication in the fourier domain

Posted: 2012-12-08T11:24:56-07:00
by fmw42
When using -fft and -ift, you do not have to use HDRI.

Re: multiplication in the fourier domain

Posted: 2012-12-18T18:04:54-07:00
by anthony
Also it is ".miff" not ".mif"

With the way you are doing it... The miff: on the front overrides the unknwon bad suffix, while magick file handling (special label at the start of the file contents) take care of the reading, whcih is why it is working for you.