[SciPy-Dev] GSoC 2017: BSpline support

Thu Mar 23 10:31:32 EDT 2017

Hello,
I need some help with *"**Convert a CubicSpline/PPoly object to a BSpline".
*I am unable to find suitable literature for it, or maybe I am overlooking
something. I would be really grateful if you could guide me to some reading
material or code samples.

Thank You

On 20 March 2017 at 03:38, Nikolay Mayorov <nikolay.mayorov at zoho.com> wrote:

> For future I suggest to put your proposal in markdown format somewhere on
> github (scipy wiki is a good place).
>
> I don't know what is the correct and productive way to review such
> proposal, so these are some thoughts on some of your points.
>
> *> Rework the tutorial for scipy.interpolate:* The 1D interpolation
> section prominently recommends interp1d. We likely want              to
> tone it down and recommend instead CubicSpline, Akima1DInterpolator,
> BSpline etc.
>    This can be done after reading some basics about these algorithms and
> making the changes as required.
>
>
> Honestly I don't think it is that easy, you definitely need to have a
> certain taste and interest to rewrite this tutorial. My guess is that you
> will be able to do it better after you finished the main algorithmic and
> coding work.
>
> *> Come up with better names for make_interp_spline/make_lsq_spline
> routines.*
>    This too can be handled after some discussion.
>
>
> I don't think it is necessary to put things like that in the proposal,
> you'll figure it out (with Evgeni) as the work progresses.
>
> *> Add string aliases to the bc_type keyword of make_interp_spline* to
> match what CubicSpline allows. I.e.
> bc_type="natural" should be equivalent to bc_type=((2, 0), (2, 0))
>  This requires mainly imitating whats there in CubicSpline so wont be very
> difficult.
>
>
> This can be indeed your first small objective. The documentation for
> bc_type in make_interp_spline reads
>
> "Each of these must be an *iterable* of pairs (order, value) which gives
> the values of derivatives of specified orders at the given edge of the
> interpolation interval."
>
> So BSpline is quite general and allows specifying conditions for several
> derivatives at one end (as opposed to CubicSpline). Maybe it will need some
> special considerations, just something I noticed.
>
>
>         *> Convert a CubicSpline object to a BSpline*
>  This could be done by assigning the __class__ attribute to the instance.
> However, since this is not preferred, we may
> construct a new method which will create a new BSpline object using a
> CubicSpline object by assigning the corresponding               attribute
> values. (I need your suggestion, which approach to follow?)
>
>
> I believe ideally there should be a factory method like
> `BSpline.from_ppoly(...)`, as a compromise something like
> `BSpline.from_cubic_spline`, but I'm not sure whether it will be that
> valuable in that form. The problem might be not that simple, do some
> research on now to make conversion between polynomial and B-spline basis.
>
> *> Knot insertion:* BSpline class should grow a method insert_knot (or
> insert_knots). This can either wrap fitpack.insert
>  directly, or reuse parts of it (e.g. retain the buffer swapping plumbing
> from _fitpack and reimplement the Fortran routine
>  fitpack/fpinst.f in C or Cython).
>    Since fitpack.insert is already implemented for BSplines, wrapping
> around it would be the simplest solution as I perceive.
>
>
> As I see there is already a public function insert (implemented in
> fitpack.py). So just moving it in as a method pretty much does the job.
> However is the final aim is to move away from FITPACK, then reimplementing
> insertion algorithm in Cython is useful. Additionally it can be an entry
> into more serious problems to follow and doing things in Cython. (Btw, I'm
> not sure what Evgeni meant by "e.g. retain the buffer swapping plumbing".)
>
> *> Root-finding:* At a minimum, sproot should be wrapped into a method of
> BSpline class. Better still, it should be generalized            to allow
> non-cubic splines. The interface should mirror PPoly.solve and PPoly.roots.
>    This too can be done by imitating PPoly.roots and PPoly.solve.
>
>
> Writing a new implementation for arbitrary spline orders looks like an
> interesting and challenging problem. Consider doing it instead of just
> minimal wrapper.
>
> All in all the two previous problems, if done in full capacity, don't seem
> easy and can occupy you for the good part of the GSoC.
>
> *BSpline Variations:-*
> *> Cardinal BSplines (BSplines with equidistant knots).* We need
> representation, evaluation and construction. scipy.signal              has
> some. The task here is to have an interface which is both compatible with
> regular b-splines and piecewise polynomials              and is useful for
> the signal processing folks.
>    For implementing this feature I will have to read some material to get
> a good understanding of Cardinal BSplines and its
>  implementation
>    These are two of the places (for now) I would start my study from. The
> implementation in scipy.signal can be of help.
>            https://en.wikipedia.org/wiki/B-spline#Cardinal_B-spline
>    http://dx.doi.org/10.1016/j.aml.2010.06.029
>    This task could take a long time, maybe 3 weeks or more.
>
> *> Spline fitting to data.* ATM there's only FITPACK, and we want a more
> controllable alternative. A first exploratory shot could            be
> to implement de Boors's newknot routine and see how it behaves in real life.
>    This too requires reading of some literature to understand the math and
> also looking at the FITPACK code for guidance.
>    The following literature can be helpful.
>    https://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/
> spline/B-spline/de-Boor.html
>    https://en.wikipedia.org/wiki/De_Boor%27s_algorithm
>
>  Both these tasks would take over a month for complete implementation.
>
>
> Generally I suggest to pick (at least for now) one subject most
> interesting to you and think it through in more details. Now it's unclear
> what exactly you want to program (which classes, functions, etc.) and time
> estimates don't look reliable. For "Spline fitting to data" I'm somewhat
> confused, because make_lsq_spline and make_interp_spline seem to already
> solve fitting problems without relying on FITPACK. Evgeni, what is the
> situation here?
>
> For now that's all from me. To sum up: focus on fewer things with more
> details, you don't necessary need to go into the most advanced things. If
> I'm not mistaken, the whole project can be organized as "get rid of some
> things from fitpack" and it can be good.
>
> I think Evgeni will clarify/comment on things.
>
>
> Nikolay.
>
>
> After looking at the issue tracker #6730
> <https://github.com/scipy/scipy/issues/6730> I have made my first
> proposal for the GSoC project "Improve support for B-splines". This is in
> continuation with my first mail regarding the same matter.
>
> This is a long list of what I think could be done as part of the project.
> I don't have much knowledge of Splines or B-Splines hence the work plan is
> not very detailed. Please have a look.
>
> *Minor changes:-*
> ::: Documentation:
> *> Rework the tutorial for scipy.interpolate:* The 1D interpolation
> section prominently recommends interp1d. We likely want              to
> tone it down and recommend instead CubicSpline, Akima1DInterpolator,
> BSpline etc.
>    This can be done after reading some basics about these algorithms and
> making the changes as required.
>
> *> Come up with better names for make_interp_spline/make_lsq_spline
> routines.*
>    This too can be handled after some discussion.
>
> Both these documentation changes can be done within a few days time, 3 to
> 4 days should be enough.
>
> ::: Enhancements:
> *> Add string aliases to the bc_type keyword of make_interp_spline* to
> match what CubicSpline allows. I.e.
> bc_type="natural" should be equivalent to bc_type=((2, 0), (2, 0))
>  This requires mainly imitating whats there in CubicSpline so wont be very
> difficult.
>
>         *> Convert a CubicSpline object to a BSpline*
>  This could be done by assigning the __class__ attribute to the instance.
> However, since this is not preferred, we may
> construct a new method which will create a new BSpline object using a
> CubicSpline object by assigning the corresponding               attribute
> values. (I need your suggestion, which approach to follow?)
>
>  Both these tasks should not take more than 6 to 7 days, including all the
> documentation and unit tests.
>
>
> *Major Enhancements:-*
> *> Knot insertion:* BSpline class should grow a method insert_knot (or
> insert_knots). This can either wrap fitpack.insert
>  directly, or reuse parts of it (e.g. retain the buffer swapping plumbing
> from _fitpack and reimplement the Fortran routine
>  fitpack/fpinst.f in C or Cython).
>    Since fitpack.insert is already implemented for BSplines, wrapping
> around it would be the simplest solution as I perceive.
>
> *> Root-finding:* At a minimum, sproot should be wrapped into a method of
> BSpline class. Better still, it should be generalized            to allow
> non-cubic splines. The interface should mirror PPoly.solve and PPoly.roots.
>    This too can be done by imitating PPoly.roots and PPoly.solve.
>
>  Both these tasks can be completed within 10 days time including all the
> documentation and tests.
>
> *BSpline Variations:-*
> *> Cardinal BSplines (BSplines with equidistant knots).* We need
> representation, evaluation and construction. scipy.signal              has
> some. The task here is to have an interface which is both compatible with
> regular b-splines and piecewise polynomials              and is useful for
> the signal processing folks.
>    For implementing this feature I will have to read some material to get
> a good understanding of Cardinal BSplines and its
>  implementation
>    These are two of the places (for now) I would start my study from. The
> implementation in scipy.signal can be of help.
>            https://en.wikipedia.org/wiki/B-spline#Cardinal_B-spline
>    http://dx.doi.org/10.1016/j.aml.2010.06.029
>    This task could take a long time, maybe 3 weeks or more.
>
> *> Spline fitting to data.* ATM there's only FITPACK, and we want a more
> controllable alternative. A first exploratory shot could            be
> to implement de Boors's newknot routine and see how it behaves in real life.
>    This too requires reading of some literature to understand the math and
> also looking at the FITPACK code for guidance.
>    The following literature can be helpful.
>    https://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/
> spline/B-spline/de-Boor.html
>    https://en.wikipedia.org/wiki/De_Boor%27s_algorithm
>
>  Both these tasks would take over a month for complete implementation.
>
> *optional:*
> I am not sure about the scope of these additions. Also, if we decide to
> implement these, I am not quite sure they can be
> completed within the span of GSoC. Probably, we can just take up one of
> these tasks.
>
> *> PSpline:* The term P-spline stands for "penalized B-spline". It refers
> to using the B-spline representation where the
>  coefficients are determined partly by the data to be fitted, and partly by
> an additional penalty function that aims to impose
>  smoothness to avoid overfitting.
>    Adequate literature can be found here,
>  https://projecteuclid.org/download/pdf_1/euclid.ss/1038425655
> <https://projecteuclid.org/download/pdf_1/euclid.ss/1038425655>
>  SAS have already implemented it,
>  https://support.sas.com/documentation/cdl/en/statug/
> 63033/HTML/default/viewer.htm#statug_transreg_sect020.htm
> <https://support.sas.com/documentation/cdl/en/statug/63033/HTML/default/viewer.htm#statug_transreg_sect020.htm>
>  This feature could take up a lot of time, including
> documentation,tests,examples etc.
>
> *> Non-Uniform Rational B-splines (NURBS):*  Unlike simple B-splines, the
> control points each have a weight.
>  The following literature can be helpful,
>  https://en.wikipedia.org/wiki/Non-uniform_rational_B-spline
>  https://www.rhino3d.com/nurbs
>  The following articles can help with the implementation.
>  https://www.codeproject.com/Articles/996281/NURBS-curve-made-easy
>  http://www.nar-associates.com/nurbs/c_code.html#chapter4
>  This feature too can take up lots of time for full completion.
>
> *> Constructing periodic splines*. Fitpack does it. With full matrices
> it's straightforward, a naive implementation with banded
>  matrices has issues with numerical stability.
>    We can definitely look into the banded matrix issue if time permits. I
> am not sure what we may find so cant say anything                    about
> the time required.
>
> Final Assessment:-
> After these tasks have been completed. All the new features,methods would
> undergo rigorous tests and doctests. Benchmark tests could also be added
> wherever necessary. Features having scope for work could be reported on
> GitHub.
>
> I plan on reading as much as I can related to Cardinal BSplines,De Boor's
> newknot routine,Penalized BSplines,NURBS etc. before the start of GSoC.
> This will help me in saving time finding literature related to all these
> new additions.
>
> Looking forward to feedback and corrections.
>
>
> On 16 March 2017 at 20:03, Evgeni Burovski <evgeny.burovskiy at gmail.com>
> wrote:
>
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> https://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
>
> On Thu, Mar 16, 2017 at 11:06 AM, Aman Pratik <amanpratik10 at gmail.com>
> wrote:
>
>
> Hello Developers,
>
> This is Aman Pratik. I am currently pursuing my B.Tech from Indian
> Institute of Technology, Varanasi. I am a keen software developer and not
> very new to the open source community. I am interested in your project
> "Improve support for B-splines" for GSoC 2017.
>
> I have been working in Python for the past 2 years and have good idea
> about Mathematical Methods and Techniques. I am quite familiar with scipy
> mainly as a user and also as a developer. I also have some experience with
> Cython.
>
> These are the PRs I have worked/working on for the past month.
>
> ENH: Add evaluation of periodic splines #6730
> <https://github.com/scipy/scipy/pull/7185>
>
> DOC: Bad documentation of k in sparse.linalg.eigs See #6990 (Merged)
> <https://github.com/scipy/scipy/pull/6995>
>
> ENH: scipy.linalg.eigsh cannot get all eigenvalues #7004
> <https://github.com/scipy/scipy/pull/7004>
>
> My GitHub Profile: https://www.github.com/amanp10
>
> I am interested in Mathematical models and functions and therefore willing
> to work on splines. Also, I am familiar with Benchmark tests, Unit tests
> and other technical knowledge I would require for this project. I have
> started my study for the subject and am looking forward to guidance from
> the potential mentors or other developers.
>
> Thank You
>
>
>
> Hi Aman, and welcome!
>
> I see that you already started with https://github.com/scipy/
> scipy/pull/7185, great!
>
> We'll also need a proposal. Since writing a good proposal typically takes
> several iterations, I encourage you to start working on it, too. When you
> have a draft, please send it to the list.
>
> All the best,
>
> Evgeni
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> https://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
>
>
>
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> https://mail.scipy.org/mailman/listinfo/scipy-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20170323/2e500afb/attachment.html>