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

Sat Mar 21 17:31:27 EDT 2015

Hi Evgeni!

Just in addition to the previous letter: here
<https://drive.google.com/file/d/0BzveGSDwNVtBaW02VktrZndJdnc/view?usp=sharing>
is my GSoC proposal on tensor product splines. I would be grateful if you
take a look at it!

Thanks!
Best regards,

Anastasiia

2015-03-19 12:18 GMT+02:00 Anastasiia Tsyplia <anastasiyatsyplya at gmail.com>:

> 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/20150321/df142d46/attachment.html>