1

I currently have a naive kernal convolution that cannot be seperable causing high load on the system at large kernal sizes. I have started looking into Fast Fourier Transform, and as far as I can tell the result of a kernal convolution is the same as the multiplication of the FFT of both the image and the kernal. Could someone please help me to learn how to implement a 2D FFT.

This is for a project for simulating lens blur.

Timbucktato
  • 117
  • 9
  • @RobertHarvey: Asking how to implement a convolution using an FFT is not a duplicate of asking how to implement an FFT. – Eric Postpischil Jan 18 '19 at 04:22
  • What specific problem are you having? Do you have an FFT implementation you can use? Do you know how, given an FFT, you can implement a kernel convolution using an FFT, or do you need to learn how to do that? Have you implemented any prototype for this, such as doing the convolution by way of FFTs in Matlab? – Eric Postpischil Jan 18 '19 at 04:24
  • Hey Eric, thanks for the question. To be entirely honest, I need to learn how to implement a 2D FFT as I am very lost in that regard. – Timbucktato Jan 19 '19 at 00:00
  • 1
    General discussion of implementing a 2D FFT is too broad for Stack Overflow. There are numerous issues—theory (including mathematics), practical concerns (such as data layouts), variants such as real-to-complex and complex-to-complex, and performance. Although implementing “an FFT” is simple, efficiency is usually a concern, and that introduces a great deal of practical knowledge about processor, cache, memory, and more. My advice would to seek existing FFT implementations (there are many). If you must write your own, doing it right requires some study. – Eric Postpischil Jan 20 '19 at 02:51
  • That makes sense, thanks for your help. – Timbucktato Jan 21 '19 at 03:05

0 Answers0