[SciPy-Dev] GSoC'15 Idea: Approximation with Parametric Splines

Thu Mar 19 06:18:53 EDT 2015

Hi!

Great thanks for useful tips to everyone!

Benny, thanks for the advice, I hope it will be useful to me during the
spring/summer J.

Evgeni, once again thanks for the detailed answer!

As far as I can judge, all current issues with the scipy.interpolate are
somehow related with the usage of FITPACK library. Such conclusion can also
be made by counting FITPACK word in our mailing history J. And of course it
is mentioned on the SciPy’s ideas page.

So now it becomes clear to me that reimplementig FITPACK routines is one of
the fundamental issues for scipy.interpolate module, at least in the area
of splines.

That’s why I've made my mid to revise my original proposal totally.

Here
<https://drive.google.com/file/d/0BzveGSDwNVtBVDZiUlgybGNpcFk/view?usp=sharing>
is my new GSoC’15 draft proposal on making the alternative to Dierckx’s
FITPACK library. I understand the difficulties and the huge scope of the
work to do. I think my proposal can be thought of not as a proposal to
reimplement FITPACK totally, but to make a basic alternative so it can be
complemented by new features in future.

Currently I’m thinking of making a draft for the second proposal on tensor
product splines.

The docstring fix I wanted to make appeared to be already fixed before me… L
So I think I’ll do fix something else on the weekend.

Please let me know what you are thinking of my new proposal so I can revise
it before the registration deadline.

Best regards,

Anastasiia

2015-03-16 14:41 GMT+02:00 Evgeni Burovski <evgeny.burovskiy at gmail.com>:

> Anastasiia,
>
> For interpolation with derivatives you can use BPoly.from_derivatives.
> This constructs an interpolating polynomial in the Bernstein basis
> though, so you get a Bezier curve. Converting it to b-spline basis is
> possible, you just need to be a bit careful with continuity at
> breakpoints. This latter part is not implemented in scipy, but the
> construction of the interpolating polynomial is.
> BPoly.from_derivatives should also work for specifying the end derivatives.
>
> It is certainly possible to implement this sort of functionality
> directly in the b-spline basis, but I'm not sure it's in scope --- an
> add-on for CAD could be a better fit maybe.  Unless there is a set of
> applications where using the existing functionality + conversion from
> a Bernstein basis to B-spline basis is not sufficient [which might
> very well be, an input from a domain expert would be welcome here.]
>
> Regarding fitpack2: yes, BivariateSplines are tensor products. The
> main issue with these, as well as UnivariateSpline are that they are
> black boxes which tightly couple manipulation of the b-spline objects
> themselves with fitting. Notice that in your blog post you had to use
> a `_from_tck` method, which is, strictly speaking, private (as
> indicated by the leading underscore).  With either functional or
> object-oriented wrappers around FITPACK there is no easy way of
> * constructing the spline object from knots and coefficients (you have
> to use semi-private methods)
> * influencing the way the fitting works. (for instance, here is one
> enhancement request: https://github.com/scipy/scipy/issues/2579)
>
> Regarding expo-rational splines I have no opinion :-). My gut feeling
> from quickly glancing over the link you provided is that it falls into
> a fancy side of things, while scipy.interpolate I think needs more
> basic functionality at present.  Again, an input from a domain expert
> would be welcome.
>
> Regarding an issue with LSQBivariateSpline --- please open an issue on
> github for this. Best open a pull request with a fix :-). For the GSoC
> requirements I think you need a PR anyway :-).
>
> Regarding the automatic fitting/interpolation with non-uniform knots.
> The main issue here is how to construct a good knot vector (and what
> is "good"). One problem of FITPACK is that it does what it does and
> it's quite hard to extend/improve on what it does when it performs
> sub-optimally. There is quite a literature on this topic, de Boor's
> book is one option. [Quoting Chuck Harris, "de Boor is not an easiest
> read" though.] An alternative way can, in principle, be inferred from
> FITPACK source code, from the Dierckx's book and/or other references
> in the FITPACK source code. Looking at MARS algorithms might be useful
> as well (py-earth is one implementation), maybe one can try
> implementing generalized cross validation.
>
> As far as specific GSoC-sized tasks are concerned: it depends on you
> really. Coming up with a specific proposal for spline fitting would
> require quite a bit of work with the literature and experimenting: any
> new algorithm should be competitive with what is already there in
> FITPACK.
> Implementing basic tensor product splines is a definitely a smaller
> project, also definitely less research-y.
> Implementing cardinal b-splines would involve studing what's in
> ndimage and signal. The latter are likely best deprecated, but the
> former contain a lot of fine-tuning and offer very good performance.
> One reasonably well-defined task could be to implement periodic
> splines in the framework of gh-3174. A challenge is to have a
> numerically stable algorithm while still keeping linear algebra
> banded.
>
> All I say above is just my perspective on things :-).
>
>
> Evgeni
>
>
>
>
>
> On Thu, Mar 12, 2015 at 6:47 PM, Anastasiia Tsyplia
> <anastasiyatsyplya at gmail.com> wrote:
> > Hello!
> >
> > Thanks for expanded and kind reply!
> >
> > Especially thanks for the link to bezierbuilder! It opened my eyes on
> what
> > can be done with the matplotlib. I guess now I’ll abandon my efforts to
> make
> > the implementation with Qt and will start again with only the matplotlib.
> > Anyway, this can wait for some time, and when it's done I'll definitely
> > share the link to repo with you.
> >
> > Regarding to the optimization I wrote about before:
> >
> > Initially I was thinking about the precise positioning of control points
> > while dragging them on the screen in order to get best fit. It is
> obvious,
> > that manual positioning of control points can give a good visual result.
> > Following automatic variation in some boundaries can provide strict
> control
> > points positions and numerically best fitting result.
> >
> > By now I’m thinking about the possibility to implement the request for
> some
> > additional parameters from the user for approximating spline functions.
> > Actually, this can be user-provided n-order derivatives in some points
> (for
> > example endpoints to get good extrapolation results). Maybe this will
> > require implementation of a new class like DerivativeControlledSpline or
> > something familiar.
> >
> > Another issue of optimization is the construction of non-uniform knot
> > vectors. Just as an example, I think in some cases non-uniform knot
> vector
> > can be constructed using information about the data points’ density
> along x
> > and y axes. If these thoughts make any sense please, let me know and I’ll
> > try to expand them to some proposal-like state.
> >
> > Regarding to alternative tasks:
> >
> > The list of your alternative tasks pushed me to reread the 7th chapter of
> > the book on spline methods, what made me feel excited about tensor
> product
> > spline surfaces. Current module fitpack2 has a big set of classes
> > representing bivariate splines. Aren’t they tensor product splines? Or
> the
> > idea is to move away from FITPACK wrapping? Anyway I feel some interest
> to
> > the issue and I would be grateful if you describe the problem more
> specific
> > so I can estimate the effort and the milestones.
> >
> > Implementation of Cardinal B-splines seems to be of the less effort, but
> not
> > less interest :)
> >
> > In addition, I would like to know what you are thinking about
> expo-rational
> > B-splines. If their implementation in SciPy is welcome, I can think about
> > the appropriate proposal.
> >
> > So by now I have 4 ways to go:
> >
> > Tensor product spline surfaces;
> >
> > Cardinal B-splines;
> >
> > Expo-rational B-splines;
> >
> > Optimization methods for spline functions.
> >
> > If it is possible, please provide the information on their importance to
> the
> > SciPy project so I can choose 1 or 2 of them to make the GSoC
> proposal(s).
> >
> > Thanks a lot and best regards,
> >
> > Anastasiia
> >
> >
> > PS
> >
> > While discovering fitpack2 module I guess I found some copy-paste bug in
> > docstring on LSQBivariateSpline. It seems that the class doesn’t require
> > smoothing parameter on initialization but the docstring about it somehow
> > migrated from another class. Should I write about it on IRC channel or
> > somewhere else, or maybe do it by myself?
> >
> >
> >
> >
> > 2015-03-09 23:48 GMT+02:00 Ralf Gommers <ralf.gommers at gmail.com>:
> >>
> >> Hi Anastasiia, welcome!
> >>
> >>
> >> On Sun, Mar 8, 2015 at 10:25 AM, Anastasiia Tsyplia
> >> <anastasiyatsyplya at gmail.com> wrote:
> >>>
> >>> Hello,
> >>>
> >>> My name is Anastasiia Tsyplia. I am a 5th-yaer student of National
> Mining
> >>> University of Ukraine.
> >>>
> >>> I am keen on interpolation/approximation with splines and it was a nice
> >>> surprise to find out that there is a demand in interpolation
> improvements
> >>> amongst the Scipy's ideas for GSoC'15. However, I've spend some time on
> >>> working out the idea of my own.
> >>>
> >>> Recently I've made a post dedicated to description of the parametric
> >>> spline curves construction process and approaches to approximate
> engineering
> >>> data by spline functions and parametric spline curves with SciPy.
> >>
> >>
> >> Nice blog post!
> >> I'll leave the commenting on technical details you have in your draft
> >> proposal to Evgeni and others, just want to say you've made a pretty
> good
> >> start so far.
> >>>
> >>> It seems that using parametric spline curves in approximation can be
> >>> extremely useful and time-saving approach. That's why I would like to
> share
> >>> my project idea and hope to hear some feedback as I am about to make a
> >>> proposal for the Google Summer of Code.
> >>>
> >>> I have a 2-year experience in programming with Python, PyOpengl, PyQt,
> >>> Matplotlib, Numpy & SciPy. Some time I spent to dive into ctypes and
> >>> scratched the surface of C. Now my priority is Cython. I've read the
> book on
> >>> the spline methods recommended on SciPy's idea page, so I feel myself
> >>> competent in spline methods. I feel free with recursions: the last
> challenge
> >>> I faced was implementation of binary space partitioning algorithm in
> python
> >>> as I was writing my own ray-tracer.
> >>>
> >>> I would like to contribute to SciPy by any means, so I'm ready to
> receive
> >>> instructions on my next move. And, certainly I'm looking forward to
> start
> >>> dealing with B-Splines in Cython as it is also a part of my project
> idea.
> >>
> >>
> >> What I recommend to all newcomers is to start by reading
> >> https://github.com/scipy/scipy/blob/master/HACKING.rst.txt and then
> first
> >> tackly an issue labeled "easy-fix", just to get a feel for the
> >> development/PR process.
> >>
> >> I've checked open issues for Cyhon code, there aren't that many at the
> >> moment. Maybe something fun could be to take some code now using
> np.ndarray
> >> and change it to use memoryviews (suggestion by @jakevdp that in
> >> scipy.sparse.csgraph this could help). And include a benchmark to show
> that
> >> it does speed things up
> >> (seehttps://github.com/scipy/scipy/tree/master/benchmarks for details).
> >>
> >> Regarding B-splines there's https://github.com/scipy/scipy/issues/3423,
> >> but I don't recommend tackling that now - that'll be a significant
> amount of
> >> work + discussion.
> >>
> >> Cheers,
> >> Ralf
> >>
> >>
> >> _______________________________________________
> >> SciPy-Dev mailing list
> >> SciPy-Dev at scipy.org
> >> http://mail.scipy.org/mailman/listinfo/scipy-dev
> >>
> >
> >
> > _______________________________________________
> > SciPy-Dev mailing list
> > SciPy-Dev at scipy.org
> > http://mail.scipy.org/mailman/listinfo/scipy-dev
> >
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20150319/1129b424/attachment.html>