comp.lang.idl-pvwave archive: archive » computation time for convolution

Home » Public Forums » archive » computation time for convolution

Show: Today's Messages :: Show Polls :: Message Navigator
E-mail to friend

Re: computation time for convolution [message #88996 is a reply to message #88995]

Thu, 10 July 2014 19:17

wlandsman
Messages: 743
Registered: June 2000

Senior Member

Here's an interesting post addressing the question -- for what size kernel is the Fourier transform more efficient that direct convolution?

http://programmers.stackexchange.com/questions/171757/comput ational-complexity-of-correlation-in-time-vs-multiplication- in-frequency-s

Given a kernel of width K and an image of width W, the Fourier transform method is more efficient than direct convolution when

K > sqrt(8*alog(W)/alog(2))

The author makes a lot of approximations. F0r example, I do think that David Stern was able to be more efficient than (K^2)*(W^2)in his implementation of direct convolution. For a 1024 x 1024 image the above formula says that Fourier transforms are preferred when K > 9, whereas my simple experiments suggest that K ~ 64 is more appropriate for IDL. --Wayne

Report message to a moderator

[Message index]

		computation time for convolution By: fra on Wed, 09 July 2014 01:12
		Re: computation time for convolution By: wlandsman on Wed, 09 July 2014 09:48
		Re: computation time for convolution By: chris_torrence@NOSPAM on Wed, 09 July 2014 17:59
		Re: computation time for convolution By: Lajos Foldy on Thu, 10 July 2014 01:47
		Re: computation time for convolution By: wlandsman on Thu, 10 July 2014 05:16
		Re: computation time for convolution By: fra on Thu, 10 July 2014 14:19
		Re: computation time for convolution By: wlandsman on Thu, 10 July 2014 19:17

Previous Topic:	No Raster Image via Imagemagick
Next Topic:	Source Control IDL 8.1

-=] Back to Top [=-

[ Syndicate this forum (XML) ] [

] [

]

Current Time: Wed Oct 08 20:04:35 PDT 2025

Total time taken to generate the page: 0.00401 seconds