Convolution of Arrays

[Gregory James]

Dear ImageJ community,

I would like to convolve two functions together. My data are in two 1-D arrays. I was very excited with the recent introduction of the 'Array.fourier' function. Thank you to the ImageJ administrators for this.

The problem I'm having is that I can perform the multiplication in Fourier space to do the convolution but then I can not transform the result back into real space. Are there any plans to introduce an inverse function to 'Array.fourier'?

I've also tried representing my 1-D arrays as images then using the FFT functionality, but this doesn't seem to be working.

Does anyone have any bright ideas as to how I can convolve two functions together?

Thank you very much,

Greg.

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Michael Schmid]

Hi Greg,

hmm, having the full FFT/FD math functionality for 1D arrays would be quite a bit of work.

Why not do the convolution without the FFT, point by point?
  http://en.wikipedia.org/wiki/Convolution#Discrete_convolution

Typically, 1D arrays don't have millions of points, so the computing time is not as much an issue as for 2D images.
Also, when doing it directly without FFT, you have more choices for how to treat the boundaries; having periodic repetition or not, dividing by the length of the overlap in case of no periodic boundary conditions, using windowing functions for the overlap area, etc. If desired, you can easily have periodic boundary conditions with an array length that is not a power of 2. Just a lot of flexibility that you will never get from the FFT approach.

Michael
________________________________________________________________
On Nov 11, 2014, at 11:59, Gregory James wrote:

> Dear ImageJ community,
>
> I would like to convolve two functions together. My data are in two 1-D arrays. I was very excited with the recent introduction of the 'Array.fourier' function. Thank you to the ImageJ administrators for this.
>
> The problem I'm having is that I can perform the multiplication in Fourier space to do the convolution but then I can not transform the result back into real space. Are there any plans to introduce an inverse function to 'Array.fourier'?
>
> I've also tried representing my 1-D arrays as images then using the FFT functionality, but this doesn't seem to be working.
>
> Does anyone have any bright ideas as to how I can convolve two functions together?
>
> Thank you very much,
>
> Greg.
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[ctrueden]

Hi Greg,

> Does anyone have any bright ideas as to how I can convolve two
> functions together?

You might also find the ImgLib2 library useful. See the ImgLib2 Tutorials
for relevant examples.

http://imagej.net/ImgLib2_Examples
http://imagej.net/ImgLib2_Examples#Example_6b_-_Convolution_in_Fourier_space

Regards,
Curtis

On Tue, Nov 11, 2014 at 5:10 AM, Michael Schmid <[hidden email]>
wrote:

> Hi Greg,
>
> hmm, having the full FFT/FD math functionality for 1D arrays would be
> quite a bit of work.
>
> Why not do the convolution without the FFT, point by point?
>   http://en.wikipedia.org/wiki/Convolution#Discrete_convolution
>
> Typically, 1D arrays don't have millions of points, so the computing time
> is not as much an issue as for 2D images.
> Also, when doing it directly without FFT, you have more choices for how to
> treat the boundaries; having periodic repetition or not, dividing by the
> length of the overlap in case of no periodic boundary conditions, using
> windowing functions for the overlap area, etc. If desired, you can easily
> have periodic boundary conditions with an array length that is not a power
> of 2. Just a lot of flexibility that you will never get from the FFT
> approach.
>
> Michael
> ________________________________________________________________
> On Nov 11, 2014, at 11:59, Gregory James wrote:
>
> > Dear ImageJ community,
> >
> > I would like to convolve two functions together. My data are in two 1-D
> arrays. I was very excited with the recent introduction of the
> 'Array.fourier' function. Thank you to the ImageJ administrators for this.
> >
> > The problem I'm having is that I can perform the multiplication in
> Fourier space to do the convolution but then I can not transform the result
> back into real space. Are there any plans to introduce an inverse function
> to 'Array.fourier'?
> >
> > I've also tried representing my 1-D arrays as images then using the FFT
> functionality, but this doesn't seem to be working.
> >
> > Does anyone have any bright ideas as to how I can convolve two functions
> together?
> >
> > Thank you very much,
> >
> > Greg.
> >
> > --
> > ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[bnorthan]

Hi Greg,

To follow up on Curtis's suggestion below is a Fiji beanshell script that
wraps 1D float arrays to the imglib2 Img format and uses Imglib2 to
convolve them.

If you copy into Fiji's script editor and save as 'bsh' (or choose
beanshell as the language) it should run.

Brian

----------------------------------------------------------------------------------------------------------------
import net.imglib2.FinalDimensions;
import net.imglib2.img.array.ArrayImgs;
import net.imglib2.algorithm.fft2.FFTConvolution;

size=20;

input = new float[size];
kernel = new float[size];
output = new float[size];

// place a couple of impulses in the array
input[size / 4] = 50;
input[size / 2] = 100;

// make the kernel a pulse
kernel[size/2-1]=0.33f;
kernel[size/2]=0.33f;
kernel[size/2+1]=0.33f;

// wrap arrays as imglib2 Imgs

// first we need to wrap the size as a long array
dimensions = new long[] { size };

// then wrap the float arrays as ArrayImgs
arrayInput=ArrayImgs.floats(input, dimensions);
arrayKernel= ArrayImgs.floats(kernel, dimensions);
arrayOutput = ArrayImgs.floats(output, dimensions);

// now call the convolution
new FFTConvolution( arrayInput, arrayKernel, arrayOutput  ).run();

// and finally, print input and output
for (int i=0;i<size;i++)
print(input[i]+" :        "+output[i]);

On Mon, Nov 17, 2014 at 6:12 PM, Curtis Rueden <[hidden email]> wrote:

> Hi Greg,
>
> > Does anyone have any bright ideas as to how I can convolve two
> > functions together?
>
> You might also find the ImgLib2 library useful. See the ImgLib2 Tutorials
> for relevant examples.
>
> http://imagej.net/ImgLib2_Examples
>
> http://imagej.net/ImgLib2_Examples#Example_6b_-_Convolution_in_Fourier_space
>
> Regards,
> Curtis
>
> On Tue, Nov 11, 2014 at 5:10 AM, Michael Schmid <[hidden email]>
> wrote:
>
> > Hi Greg,
> >
> > hmm, having the full FFT/FD math functionality for 1D arrays would be
> > quite a bit of work.
> >
> > Why not do the convolution without the FFT, point by point?
> >   http://en.wikipedia.org/wiki/Convolution#Discrete_convolution
> >
> > Typically, 1D arrays don't have millions of points, so the computing time
> > is not as much an issue as for 2D images.
> > Also, when doing it directly without FFT, you have more choices for how
> to
> > treat the boundaries; having periodic repetition or not, dividing by the
> > length of the overlap in case of no periodic boundary conditions, using
> > windowing functions for the overlap area, etc. If desired, you can easily
> > have periodic boundary conditions with an array length that is not a
> power
> > of 2. Just a lot of flexibility that you will never get from the FFT
> > approach.
> >
> > Michael
> > ________________________________________________________________
> > On Nov 11, 2014, at 11:59, Gregory James wrote:
> >
> > > Dear ImageJ community,
> > >
> > > I would like to convolve two functions together. My data are in two 1-D
> > arrays. I was very excited with the recent introduction of the
> > 'Array.fourier' function. Thank you to the ImageJ administrators for
> this.
> > >
> > > The problem I'm having is that I can perform the multiplication in
> > Fourier space to do the convolution but then I can not transform the
> result
> > back into real space. Are there any plans to introduce an inverse
> function
> > to 'Array.fourier'?
> > >
> > > I've also tried representing my 1-D arrays as images then using the FFT
> > functionality, but this doesn't seem to be working.
> > >
> > > Does anyone have any bright ideas as to how I can convolve two
> functions
> > together?
> > >
> > > Thank you very much,
> > >
> > > Greg.
> > >
> > > --
> > > ImageJ mailing list: http://imagej.nih.gov/ij/list.html
> >
> > --
> > ImageJ mailing list: http://imagej.nih.gov/ij/list.html
> >
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html

[Stephan Preibisch]

Just a note, also the FFT Convolution supports any outofbounds strategy … the image is simply extended by half the kernel size using the desired outofboundsstrategy before computing the FFT based convolution.

Cheers,
Stephan

> On Nov 17, 2014, at 18:12 , Curtis Rueden <[hidden email]> wrote:
>
> Hi Greg,
>
>> Does anyone have any bright ideas as to how I can convolve two
>> functions together?
>
> You might also find the ImgLib2 library useful. See the ImgLib2 Tutorials
> for relevant examples.
>
> http://imagej.net/ImgLib2_Examples
> http://imagej.net/ImgLib2_Examples#Example_6b_-_Convolution_in_Fourier_space
>
> Regards,
> Curtis
>
> On Tue, Nov 11, 2014 at 5:10 AM, Michael Schmid <[hidden email]>
> wrote:
>
>> Hi Greg,
>>
>> hmm, having the full FFT/FD math functionality for 1D arrays would be
>> quite a bit of work.
>>
>> Why not do the convolution without the FFT, point by point?
>>  http://en.wikipedia.org/wiki/Convolution#Discrete_convolution
>>
>> Typically, 1D arrays don't have millions of points, so the computing time
>> is not as much an issue as for 2D images.
>> Also, when doing it directly without FFT, you have more choices for how to
>> treat the boundaries; having periodic repetition or not, dividing by the
>> length of the overlap in case of no periodic boundary conditions, using
>> windowing functions for the overlap area, etc. If desired, you can easily
>> have periodic boundary conditions with an array length that is not a power
>> of 2. Just a lot of flexibility that you will never get from the FFT
>> approach.
>>
>> Michael
>> ________________________________________________________________
>> On Nov 11, 2014, at 11:59, Gregory James wrote:
>>
>>> Dear ImageJ community,
>>>
>>> I would like to convolve two functions together. My data are in two 1-D
>> arrays. I was very excited with the recent introduction of the
>> 'Array.fourier' function. Thank you to the ImageJ administrators for this.
>>>
>>> The problem I'm having is that I can perform the multiplication in
>> Fourier space to do the convolution but then I can not transform the result
>> back into real space. Are there any plans to introduce an inverse function
>> to 'Array.fourier'?
>>>
>>> I've also tried representing my 1-D arrays as images then using the FFT
>> functionality, but this doesn't seem to be working.
>>>
>>> Does anyone have any bright ideas as to how I can convolve two functions
>> together?
>>>
>>> Thank you very much,
>>>
>>> Greg.
>>>
>>> --
>>> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>>
>> --
>> ImageJ mailing list: http://imagej.nih.gov/ij/list.html
>>
>
> --
> ImageJ mailing list: http://imagej.nih.gov/ij/list.html

--
ImageJ mailing list: http://imagej.nih.gov/ij/list.html