[Boost.GIL] GSoC 2020 - FFT implementation

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

[Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
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...
     


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Tue, 4 Feb 2020 at 16:11, deb via Boost <[hidden email]> 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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
On Wed, 5 Feb 2020 at 17:40, deb via Boost <[hidden email]> 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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list

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...
     


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Tue, Feb 4, 2020 at 3:18 PM stefan via Boost <[hidden email]> 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.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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/

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
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...
     


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
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/

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost.GIL] GSoC 2020 - FFT implementation

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Thu, 6 Feb 2020, 23:28 Janek Kozicki, <[hidden email]>
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, [hidden email]
(Sent from mobile, may suffer from top-posting)

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost