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

Fri Mar 13 06:20:13 EDT 2015

Anastasiia,

Concerning optimization methods.
What I am doing in my code is adding a knot between two other knots, and
then using an optimization method of scipy (gradient based) to determine
best placement of this knot and value at that knot. Constraints added on
that knot to make sure it remains between the two bounding knots.

Main problem I see is how to determine which interval is best to add an
extra knot. If there is literature that tackles this, that would be
interesting. I have not done an extensive literature search yet. You also
want to stop adding knots if their addition starts to no longer help in
reducing an error measure (Total variation increases but error does nog
significantly decrease).

My use case is not directly determining spline interpolation but instead an
indirect problem, so not directly usable for you, but I would suspect equal
approaches to knot placement for pure interpolation exist. Eg, use
levenberg-marquardt algorithm on placement of knots to reduce an error norm.

Benny

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

>  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 <http://gtwavelet.bme.gatech.edu/wp/ExpoSplines.pdf>*. If their
> implementation in SciPy is welcome, I can think about the appropriate
> proposal.
>
>  So by now I have 4 ways to go:
>
>    1.
>
>    Tensor product spline surfaces;
>    2.
>
>    Cardinal B-splines;
>    3.
>
>    Expo-rational B-splines;
>    4.
>
>    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
>>> <https://drive.google.com/file/d/0BzveGSDwNVtBanU1THpFTXNKZHc/view?usp=sharing>
>>> of my own.
>>>
>>> Recently I've made a post <http://tsplb.blogspot.com/> 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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20150313/4f053e9c/attachment.html>