[Boost.GIL] GSoC 2020 - FFT implementation
Hi, I am a third year undergrad from IIT Bombay. I am interested in PROJECT 1: Image Processing Algorithms for BOOST.GIL . I have gone through the Getting started with Boost, Modular Boost Overview and Contributing page(on git repository for boost.gil) to get a fair idea of how Boost works. I went over the boost Gil library looking for an implementation of FFT(Fast Fourier transform) but could not find one . Since it is listed as a suggested project topic for the GSoC 2020 , I was hoping to implement it as part of my GSoC competency test. I have a few questions though:- a. Should I try and implement 1D-DFT(using FFT) independent from 2D-DFT (which is the more popular among image processing algorithms) ? b. Should I submit the above mentioned algorithms as separate PRs or as a single one? I am choosing FFT over other topics since it is an essential part of many image processing algorithms like Wiener filters, tomographic reconstructions etc. I have worked with image processing algorithms before on college projects and I think that I will be able to pull it off as a GSoC competency test. Thank You. Debabrata Mandal CSE undergrad, IIT Bombay -- Sent from: http://boost.2283326.n4.nabble.com/Boost-Dev-f2600599.html
Hello Debabrata, thank you for your interest into Boost.GIL ! While I think it would be great for Boost.GIL users to be able to perform Fourier transforms on their images, I'm not convinced the best way to support that would be by adding our own FFT implementations to Boost.GIL. Given the amount of work (and expertise !) that goes into existing third-party FFT libraries (such as FFTW: http://fftw.org/), I think it's far more useful to make sure Boost.GIL can readily use (or be used with) such libraries. As far as Boost.GIL competency tests are concerned, I would much rather see you demonstrate your ability to write modern C++(11 and beyond) code, and use the existing Boost.GIL APIs, rather than focus on algorithms, though of course knowledge of algorithms and the ability to implement them is an important skill, too. Finally, don't under-estimate the work needed to write (reasonably well-performing) FFTs. It seems to me that this would be beyond the scope of any test assignment (even a full GSoC project, I would argue). Keep up your enthusiasm ! Good luck, Stefan -- ...ich hab' noch einen Koffer in Berlin...
On Tue, Feb 4, 2020 at 3:18 PM stefan via Boost <boost@lists.boost.org> wrote:
Boost.GIL. Given the amount of work (and expertise !) that goes into existing third-party FFT libraries (such as FFTW: http://fftw.org/), I think it's far more useful to make sure Boost.GIL can readily use (or be used with) such libraries.
One thing that bothered me when I used FFTW years ago in a C++ program, is they don't care much about types as long as they have the same memory layout. The fftw_complex type changes its definition in fftw3.h depending on whether complex.h is included before fftw3.h or not. This seems to be asking for trouble with strict aliasing rules and the C++ one definition rule.
On Tue, 4 Feb 2020 at 16:11, deb via Boost <boost@lists.boost.org> wrote:
Hi, I am a third year undergrad from IIT Bombay. I am interested in PROJECT 1: Image Processing Algorithms for BOOST.GIL .
Welcome!
I have gone through the Getting started with Boost, Modular Boost Overview and Contributing page(on git repository for boost.gil) to get a fair idea of how Boost works.
Yup, great, that's what you need to get you going.
I went over the boost Gil library looking for an implementation of FFT(Fast Fourier transform) but could not find one.
Since it is listed as a suggested project topic for the GSoC 2020, I was hoping to implement it as part of my GSoC competency test.
Well, speaking as one of GIL development team members together with Stefan, I agree with explanation posted by Stefan in https://lists.boost.org/Archives/boost/2020/02/248147.php As a result of that consensus, I have just removed the FFT from suggestions of the GSoC projects. As Stefan explained, we would rather prefer to adapt third-party implementations FFT for GIL which, presumably, would be hosted as GIL extensions. Although I have not given the FFT for GIL much consideration yet myself, I, personally, think there is room in GIL for an extension with a classic and not necessarily high-performance/optimal implementation of FFT that would several purposes as: - a proof of concept - educational examples - test stub exercising interface adapting an FFT implementation The FFT adapter interface itself has never been discussed, AFAIK, so any input is welcome here or on https://lists.boost.org/boost-gil/ However, such discussions and contribution of implementation is likely beyond the scope of a GSoC project.
I have a few questions though:-
a. Should I try and implement 1D-DFT(using FFT) independent from 2D-DFT (which is the more popular among image processing algorithms) ?
I think this is answered by Stefan and myself above .
b. Should I submit the above mentioned algorithms as separate PRs or as a single one?
Generally, it's a good idea to submit one PR per one functional feature.
I am choosing FFT over other topics since it is an essential part of many image processing algorithms like Wiener filters, tomographic reconstructions etc. I have worked with image processing algorithms before on college projects and I think that I will be able to pull it off as a GSoC competency test.
The aim of the test is to show minimum required fluency in C++ and the subject Boost library, while a complete implementation of an algorithm takes much more and is not what the GSoC competency test is asking for. As I have already mentioned to one of the other students keen in GIL, see https://github.com/boostorg/gil/pull/430#issuecomment-581576130, a complete feature takes more than 100 lines of C++ code of an algorithm implementation. It requires tests and docs. BTW, during last year GSoC we did not quite succeeded as I planned w.r.t. the docs especially and the tests could cover more too. So, I'd expect we are going to raise the bar a bit higher this year :-) Please, don't feel discouraged, just take it as a warning to avoid overestimation of the work capacity required, as Stefan mentioned. It's better to aim for less, a simpler task, but deliver it with a complete excellent solution on time. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net
Thanks, Stefan and Mateusz Loskot for your quick reply and useful suggestions . I was myself not quite sure of the idea of having a textbook implementation of FFT being useful for Boost. I will right away pick up a simpler topic from the project proposal page on Github (probably smoothing/blurring) and spend time getting more familiar with the Boost.gil API . And as suggested by Mateusz Loskot , I will also try to add docs and tests to the implementation before I submit a pull request. Again thanks for replying so quick. Debabrata Mandal -- Sent from: http://boost.2283326.n4.nabble.com/Boost-Dev-f2600599.html
On Wed, 5 Feb 2020 at 17:40, deb via Boost <boost@lists.boost.org> wrote:
I was myself not quite sure of the idea of having a textbook implementation of FFT being useful for Boost.
As I explained, a classic implementation of FFT will be useful, but it is not yet really. First, we need to get (discuss, design and implement) the FFT adaptation support. If you are dying hard to submit such FFT to GIL soon, then it could be accepted as as an example (.hpp & .cpp files similar to the interleaved_ptr.hpp|cpp) or as an extension in boost/gil/extension (with tests and docs!). That, however, still does not qualify for a GSoC project.
I will right away pick up a simpler topic from the project proposal page on Github (probably smoothing/blurring) and spend time getting more familiar with the Boost.gil API. And as suggested by Mateusz Loskot , I will also try to add docs and tests to the implementation before I submit a pull request.
Sounds good, just please keep in mind that for competency we do not ask you to deliver fully-featured, tested and documented implementation of an algorithm. Leave some work for the actual GSoC :-) Best regards, -- Mateusz Loskot, http://mateusz.loskot.net
Mateusz Loskot via Boost said: (by the date of Wed, 5 Feb 2020 00:49:45 +0100)
https://lists.boost.org/Archives/boost/2020/02/248147.php As a result of that consensus, I have just removed the FFT from suggestions of the GSoC projects.
FFT was added to that list due to feature requests to boost.math, see: https://github.com/boostorg/math/issues/303 I agree that writing FFT which supports all multiprecision types is a tremendous task. But if it's not in GSoC it has a really hard chance of being completed, ever. So maybe the right approach is to split this task into several smaller sub-tasks? Maybe first make a GSoC project for 1D FFT which works with math and all multiprecision and has speed comparable with libfftw when using double type (and is correctly templatized and designed, etc ;) Bjorn Reese via Boost said: (by the date of Wed, 5 Feb 2020 20:53:10 +0100)
FYI, Boost.Math already uses FFTW for Chesbyshev polynomials.
and uses boost.math code to jump-start. -- # Janek Kozicki http://janek.kozicki.pl/
On 2020-02-06 5:28 p.m., Janek Kozicki via Boost wrote:
I agree that writing FFT which supports all multiprecision types is a tremendous task. But if it's not in GSoC it has a really hard chance of being completed, ever. So maybe the right approach is to split this task into several smaller sub-tasks?
The point is not that it's a lot of work. It's that the idea to re-implement FFT from scratch inside Boost is foolish, given the availability and quality of existing FFT libraries. That being said, if you think you can come up with a better API (using modern C++), I think there *might* be value in providing (very thin) wrappers around those existing libs. But reimplementing them from scratch, and hope to get to a similar level of quality with a reasonable amount of effort, that's extremely naive. Stefan -- ...ich hab' noch einen Koffer in Berlin...
stefan via Boost said: (by the date of Thu, 6 Feb 2020 17:36:01 -0500)
On 2020-02-06 5:28 p.m., Janek Kozicki via Boost wrote:
I agree that writing FFT which supports all multiprecision types is a tremendous task. But if it's not in GSoC it has a really hard chance of being completed, ever. So maybe the right approach is to split this task into several smaller sub-tasks?
The point is not that it's a lot of work. It's that the idea to re-implement FFT from scratch inside Boost is foolish, given the availability and quality of existing FFT libraries.
I did not find a library which works with these types: * boost::multiprecision::mpfr * boost::multiprecision::cpp_bin_float * boost::multiprecision::quad_double, in the works: https://github.com/boostorg/multiprecision/pull/190 https://github.com/boostorg/multiprecision/issues/184 hence a generic approach to FFT which works with any multiprecision type is desirable. Not a single other library can provide that. Notwithstanding of course the boost implementation could fallback to existing libraries for types where FFT implementation is available, for example in libfftw: * double * long double * boost::multiprecision::float128
That being said, if you think you can come up with a better API (using modern C++), I think there *might* be value in providing (very thin) wrappers around those existing libs. But reimplementing them from scratch, and hope to get to a similar level of quality with a reasonable amount of effort, that's extremely naive.
Not all hope is lost, then ;) Depending on how badly I will need FFT for quad_double I could consider doing this. -- # Janek Kozicki http://janek.kozicki.pl/
On Thu, 6 Feb 2020, 23:28 Janek Kozicki, <janek.listy.mailowe@gmail.com> wrote:
Mateusz Loskot via Boost said: (by the date of Wed, 5 Feb 2020 00:49:45 +0100)
https://lists.boost.org/Archives/boost/2020/02/248147.php As a result of that consensus, I have just removed the FFT from suggestions of the GSoC projects.
FFT was added to that list due to feature requests to boost.math, see: https://github.com/boostorg/math/issues/303
I should have said, I removed FFT from items of Image Processing project of GIL. I agree that writing FFT which supports all multiprecision types is a
tremendous task. But if it's not in GSoC it has a really hard chance of being completed, ever. So maybe the right approach is to split this task into several smaller sub-tasks?
That's generally a recommend approach for any GSoC project, especially if a student tends to be overzealous :) Maybe first make a GSoC project for 1D FFT which works with math and
all multiprecision and has speed comparable with libfftw when using double type (and is correctly templatized and designed, etc ;)
Maybe. If there's a mentor with minimum experience of FFT implementation(s) under her sleeve, and a student... I expect the design part will be a challenge, esp. for someone new to GIL. Mateusz Loskot, mateusz@loskot.net (Sent from mobile, may suffer from top-posting)
On 2020-02-04 21:18, stefan via Boost wrote:
While I think it would be great for Boost.GIL users to be able to perform Fourier transforms on their images, I'm not convinced the best way to support that would be by adding our own FFT implementations to Boost.GIL. Given the amount of work (and expertise !) that goes into existing third-party FFT libraries (such as FFTW: http://fftw.org/), I think it's far more useful to make sure Boost.GIL can readily use (or be used with) such libraries.
FYI, Boost.Math already uses FFTW for Chesbyshev polynomials.
On 2020-02-05 2:53 p.m., Bjorn Reese via Boost wrote:
On 2020-02-04 21:18, stefan via Boost wrote:
While I think it would be great for Boost.GIL users to be able to perform Fourier transforms on their images, I'm not convinced the best way to support that would be by adding our own FFT implementations to Boost.GIL. Given the amount of work (and expertise !) that goes into existing third-party FFT libraries (such as FFTW: http://fftw.org/), I think it's far more useful to make sure Boost.GIL can readily use (or be used with) such libraries.
FYI, Boost.Math already uses FFTW for Chesbyshev polynomials.
Great to see ! Debabrata, perhaps you could look into the above and see whether Boost.GIL could use a similar technique to use FFTW as a backend. Regards, Stefan -- ...ich hab' noch einen Koffer in Berlin...
participants (6)
-
Bjorn Reese -
deb -
Frank Mori Hess -
Janek Kozicki -
Mateusz Loskot -
stefan