[SciPy-Dev] GSoC 2017: BSpline support

Fri Mar 17 16:00:19 EDT 2017

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:

>
>
> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20170318/c682dea2/attachment.html>