[SciPy-Dev] GSoC'15 Idea: Approximation with Parametric Splines
Ralf Gommers
ralf.gommers at gmail.com
Sat Apr 4 04:11:05 EDT 2015
On Sat, Mar 28, 2015 at 12:23 PM, Anastasiia Tsyplia <
anastasiyatsyplya at gmail.com> wrote:
> Hi all!
>
>
> Thanks everyone for support during the registration period! It has been
> a brainstorming couple of weeks but I hope this is only the beginning :)
>
> I submitted two proposals to GSoC'15: “FITPACK alternative... “ and
> “Tensor product splines...”. Recently I was asked to edit their titles so
> they start with SciPy. But it seems I'm no longer able to make any changes.
> Melange says that I can send a comment to the organization so they allow me
> to make changes. If this tuning is crucial, please, let me do it.
>
Hi Anastasiia, it's not critical to us (Scipy mentors) but apparently
important for some of the admins. You should be able to change the title on
your proposals now. Please let me know once you've done that, then I'll
disable editing again.
Cheers,
Ralf
> Andreas, thanks for the comment. I'll take into account your suggestions.
>
>
> Best regards,
>
> Anastasiia
>
> 2015-03-25 21:19 GMT+02:00 Andreas Hilboll <lists at hilboll.de>:
>
>> Hi Anastasiia, Eveni, ...
>>
>> I'd very much appreciate if tensor product splines would make it into
>> scipy =) One wish I have would be to enable periodicity, possibly via a
>> periodic kwarg, where the use would be able to provide, for any
>> dimensions, an interval in which the coordinates are considered
>> periodic. This is probably too specific to make it into the
>> implementation, but I'd like to raise the issue early on ...
>>
>> Cheers,
>> Andreas.
>>
>>
>> On 21.03.2015 22:31, Anastasiia Tsyplia wrote:
>> > 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 <mailto: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… LSo 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 <mailto: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
>> > <mailto: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 <mailto:ralf.gommers at gmail.com>>:
>> > >>
>> > >> Hi Anastasiia, welcome!
>> > >>
>> > >>
>> > >> On Sun, Mar 8, 2015 at 10:25 AM, Anastasiia Tsyplia
>> > >> <anastasiyatsyplya at gmail.com
>> > <mailto: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
>> > <http://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 <mailto:SciPy-Dev at scipy.org>
>> > >> http://mail.scipy.org/mailman/listinfo/scipy-dev
>> > >>
>> > >
>> > >
>> > > _______________________________________________
>> > > SciPy-Dev mailing list
>> > > SciPy-Dev at scipy.org <mailto:SciPy-Dev at scipy.org>
>> > > http://mail.scipy.org/mailman/listinfo/scipy-dev
>> > >
>> > _______________________________________________
>> > SciPy-Dev mailing list
>> > SciPy-Dev at scipy.org <mailto: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
>> >
>>
>>
>> --
>> -- Andreas.
>> _______________________________________________
>> 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/20150404/48f7c775/attachment.html>
More information about the SciPy-Dev
mailing list