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