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

Mon Mar 16 08:41:44 EDT 2015

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
>