On Sep 24, 12:37�am, kevinjmc...@netscape.net wrote:
> On Sep 23, 2:35�pm, robert bristow-johnson <r...@audioimagination.com>
> wrote:
>
>
>
>
>
> > On Sep 23, 1:10�pm, saravanan <saravananr...@gmail.com> wrote:
>
> > > Hi,
> > > Convolution in time domain is equal to multiplication in Frequency
> > > domain. I am using convolution in neural network. As many papers says
> > > that converting image and weight matrix in frequency domain, multiply
> > > and inverse the result will take less process time comparable to
> > > convolution in Time domain.
>
> > this is true for FIR filters that have a long impulse response. �if
> > the length of the two sequences that you are convolving is short
> > enough (which depends on how the fast convolution code is coded) it
> > will be more efficient to do it the old fashioned way.
>
> > > But the process time is increased instead
> > > of decreasing in my program. �I have given the detail here how I
> > > implemented the algorithm, please give me suggestion and let me know
> > > where I did mistake.
>
> > for each row and column, you are convolving a 5 sample sequence
> > against a 16 sample sequence? �i would be quite surprized if doing
> > that in the frequency domain would be faster or better for any reason.
>
> > > Comparison between FFT and Convolution
>
> > > For an example, take an image size � � �16X16
> > > Weight matrix size of � � � � � � � � � 5X5
>
> > > Output image of convolution is � � � �11X11
>
> > > One convolve takes 5X5 =25 multiplication and addition
>
> > that nearly haves to be cheaper in the time domain.
>
> > > For whole image 11X11X25 = �3025 operation
> > > ------------------------------------------------------------
>
> > > FFT
> > > I did 2D FFT in such a way that, row wise 1D FFT then column wise 1D
> > > FFT
> > > Referencehttp://local.wasp.uwa.edu.au/~pbourke/other/dft/index.html
>
> > > For each row 16X4=64 operation is required (16 log 16)
> > > 1D row wise FFT takes 16X64=1024 operation
> > > 1D Col wise FFT takes 1024 operation
> > > Totally 2048 operation is needed to convert 16X16 spatial image to
> > > frequency image
> > > We have to do this operation for weight matrix and inverse transform
> > > also
> > > So 2048 *3 =6144 operation is required along with 64 complex
> > > Multiplication
> > > So Totally �6206 operation is required in FFT
> > > ---------------------------------------------------------------
>
> > i dunno, it seems to me that you answered your own question. �i never
> > learn this lesson to read to the bottom of the post before hitting
> > reply.
>
> > r b-j- Hide quoted text -
>
> > - Show quoted text -
>
> Well, to start with, you've got an apples and oranges comparison. �The
> convolution via FFT is 16x16, but the output of your 'conventional'
> convolution is 11x11? �That's definitely not right. �And they are both
> incorrect if you're trying to do a linear convolution. With a 16x16
> image and a 5x5 kernel, you need at least a 20x20 output to get a
> linear convolution.
>
> You might want to take a look at S. Smith's book:
>
> http://www.dspguide.com/ch24/6.htm
>
> http://www.dspguide.com/ch24/7.htm
>
> Scroll down to the bottom of the second link above to see the
> comparison between conventional and FFT based convolution in terms of
> processing time.
>
> And, as r b-j has pointed out (and, as shown in the second link
> above), for very small kernels, the conventional way can in fact be
> faster than convolution via FFT. �But if the kernel is even remotely
> large, then the FFT way is definitely faster.
>
> Where the crossover occurs depends on the size of the kernel, and
> whether or not you're applying any tricks to the FFT processing.- Hide quoted text -
>
> - Show quoted text -
yes , exactly when the kerenel is small convolution is faster, if the
size increases FFT will be faster.
I agreed the same above.
Thanks
Naresh
Reply by ●September 23, 20082008-09-23
On Sep 23, 2:35�pm, robert bristow-johnson <r...@audioimagination.com>
wrote:
> On Sep 23, 1:10�pm, saravanan <saravananr...@gmail.com> wrote:
>
> > Hi,
> > Convolution in time domain is equal to multiplication in Frequency
> > domain. I am using convolution in neural network. As many papers says
> > that converting image and weight matrix in frequency domain, multiply
> > and inverse the result will take less process time comparable to
> > convolution in Time domain.
>
> this is true for FIR filters that have a long impulse response. �if
> the length of the two sequences that you are convolving is short
> enough (which depends on how the fast convolution code is coded) it
> will be more efficient to do it the old fashioned way.
>
> > But the process time is increased instead
> > of decreasing in my program. �I have given the detail here how I
> > implemented the algorithm, please give me suggestion and let me know
> > where I did mistake.
>
> for each row and column, you are convolving a 5 sample sequence
> against a 16 sample sequence? �i would be quite surprized if doing
> that in the frequency domain would be faster or better for any reason.
>
>
>
> > Comparison between FFT and Convolution
>
> > For an example, take an image size � � �16X16
> > Weight matrix size of � � � � � � � � � 5X5
>
> > Output image of convolution is � � � �11X11
>
> > One convolve takes 5X5 =25 multiplication and addition
>
> that nearly haves to be cheaper in the time domain.
>
>
>
>
>
> > For whole image 11X11X25 = �3025 operation
> > ------------------------------------------------------------
>
> > FFT
> > I did 2D FFT in such a way that, row wise 1D FFT then column wise 1D
> > FFT
> > Referencehttp://local.wasp.uwa.edu.au/~pbourke/other/dft/index.html
>
> > For each row 16X4=64 operation is required (16 log 16)
> > 1D row wise FFT takes 16X64=1024 operation
> > 1D Col wise FFT takes 1024 operation
> > Totally 2048 operation is needed to convert 16X16 spatial image to
> > frequency image
> > We have to do this operation for weight matrix and inverse transform
> > also
> > So 2048 *3 =6144 operation is required along with 64 complex
> > Multiplication
> > So Totally �6206 operation is required in FFT
> > ---------------------------------------------------------------
>
> i dunno, it seems to me that you answered your own question. �i never
> learn this lesson to read to the bottom of the post before hitting
> reply.
>
> r b-j- Hide quoted text -
>
> - Show quoted text -
Well, to start with, you've got an apples and oranges comparison. The
convolution via FFT is 16x16, but the output of your 'conventional'
convolution is 11x11? That's definitely not right. And they are both
incorrect if you're trying to do a linear convolution. With a 16x16
image and a 5x5 kernel, you need at least a 20x20 output to get a
linear convolution.
You might want to take a look at S. Smith's book:
http://www.dspguide.com/ch24/6.htmhttp://www.dspguide.com/ch24/7.htm
Scroll down to the bottom of the second link above to see the
comparison between conventional and FFT based convolution in terms of
processing time.
And, as r b-j has pointed out (and, as shown in the second link
above), for very small kernels, the conventional way can in fact be
faster than convolution via FFT. But if the kernel is even remotely
large, then the FFT way is definitely faster.
Where the crossover occurs depends on the size of the kernel, and
whether or not you're applying any tricks to the FFT processing.
Reply by robert bristow-johnson●September 23, 20082008-09-23
On Sep 23, 1:10�pm, saravanan <saravananr...@gmail.com> wrote:
> Hi,
> Convolution in time domain is equal to multiplication in Frequency
> domain. I am using convolution in neural network. As many papers says
> that converting image and weight matrix in frequency domain, multiply
> and inverse the result will take less process time comparable to
> convolution in Time domain.
this is true for FIR filters that have a long impulse response. if
the length of the two sequences that you are convolving is short
enough (which depends on how the fast convolution code is coded) it
will be more efficient to do it the old fashioned way.
> But the process time is increased instead
> of decreasing in my program. �I have given the detail here how I
> implemented the algorithm, please give me suggestion and let me know
> where I did mistake.
for each row and column, you are convolving a 5 sample sequence
against a 16 sample sequence? i would be quite surprized if doing
that in the frequency domain would be faster or better for any reason.
>
> Comparison between FFT and Convolution
>
> For an example, take an image size � � �16X16
> Weight matrix size of � � � � � � � � � 5X5
>
> Output image of convolution is � � � �11X11
>
> One convolve takes 5X5 =25 multiplication and addition
that nearly haves to be cheaper in the time domain.
> For whole image 11X11X25 = �3025 operation
> ------------------------------------------------------------
>
> FFT
> I did 2D FFT in such a way that, row wise 1D FFT then column wise 1D
> FFT
> Referencehttp://local.wasp.uwa.edu.au/~pbourke/other/dft/index.html
>
> For each row 16X4=64 operation is required (16 log 16)
> 1D row wise FFT takes 16X64=1024 operation
> 1D Col wise FFT takes 1024 operation
> Totally 2048 operation is needed to convert 16X16 spatial image to
> frequency image
> We have to do this operation for weight matrix and inverse transform
> also
> So 2048 *3 =6144 operation is required along with 64 complex
> Multiplication
> So Totally �6206 operation is required in FFT
> ---------------------------------------------------------------
>
i dunno, it seems to me that you answered your own question. i never
learn this lesson to read to the bottom of the post before hitting
reply.
r b-j
Reply by saravanan●September 23, 20082008-09-23
Hi,
Convolution in time domain is equal to multiplication in Frequency
domain. I am using convolution in neural network. As many papers says
that converting image and weight matrix in frequency domain, multiply
and inverse the result will take less process time comparable to
convolution in Time domain. But the process time is increased instead
of decreasing in my program. I have given the detail here how I
implemented the algorithm, please give me suggestion and let me know
where I did mistake.
Comparison between FFT and Convolution
For an example, take an image size 16X16
Weight matrix size of 5X5
Output image of convolution is 11X11
One convolve takes 5X5 =25 multiplication and addition
For whole image 11X11X25 = 3025 operation
------------------------------------------------------------
FFT
I did 2D FFT in such a way that, row wise 1D FFT then column wise 1D
FFT
Reference
http://local.wasp.uwa.edu.au/~pbourke/other/dft/index.html
For each row 16X4=64 operation is required (16 log 16)
1D row wise FFT takes 16X64=1024 operation
1D Col wise FFT takes 1024 operation
Totally 2048 operation is needed to convert 16X16 spatial image to
frequency image
We have to do this operation for weight matrix and inverse transform
also
So 2048 *3 =6144 operation is required along with 64 complex
Multiplication
So Totally 6206 operation is required in FFT
---------------------------------------------------------------
As I discussed above convolution in time domain takes 3025 operation
and FFT takes 6206 operations. Please let me know what is the problem.
I like to know how to improve the code
Regards
Saravanan