Thin plates for a 3D deformation field
Hi, I wondered if someone knew of a package that allows the interpolation of a 3D deformation field with thin plates (or in fact with anything) based on a list of points and their associated deformation field. If only 2D deformation field is supported by a package, I'll go for it too ;) -- French PhD student Website : http://miles.developpez.com/ Blogs : http://matt.eifelle.com and http://blog.developpez.com/?blog=92
Hello Matthieu, I don't know of any fast multipole solver or anything fancy like that for dealing with evaluating the splines rapidly, but for simple purposes, the rbf module in scipy.sandbox should do just fine. Set the function to 'thin-plate', and you will get a thin-plate spline interpolator that can interpolate values of arbitrary dimension in spaces of arbitrary dimension. So it should naturally be able to interpolate a 3D deformation field in three dimensions, or any other combination you might want. I haven't used the RBF module exclusively (I wrote my own thin-plate spline interpolator before it existed -- it's a very small amount of code), but I think that that module should be just right. One note: this sort of interpolation can be very slow if you're going to be interpolating the deformations over a fine grid -- for, say, using the deformation field for image warping. This is where one might start wanting a fast multipole solver. I find that in most cases, I can get away with interpolating the deformations on a relatively coarse grid, and then using linear interpolation to fill in the gaps. (The resizing methods in ndimage come in useful here -- just scale up the x, y, and z components of the deformation separately.) Zach Pincus On Oct 26, 2007, at 4:35 AM, Matthieu Brucher wrote:
Hi,
I wondered if someone knew of a package that allows the interpolation of a 3D deformation field with thin plates (or in fact with anything) based on a list of points and their associated deformation field. If only 2D deformation field is supported by a package, I'll go for it too ;)
-- French PhD student Website : http://miles.developpez.com/ Blogs : http://matt.eifelle.com and http://blog.developpez.com/? blog=92 _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
Matthieu Brucher wrote:
Hi,
I wondered if someone knew of a package that allows the interpolation of a 3D deformation field with thin plates (or in fact with anything) based on a list of points and their associated deformation field. If only 2D deformation field is supported by a package, I'll go for it too ;)
Another alternative is to use the natural-neighbor interpolation that I coded up. I've moved it to its own scikit for easier installation. http://svn.scipy.org/svn/scikits/trunk/delaunay/ At the moment, I only support doing one dimension at a time, but that can be easily worked around. Let's say you have your deformation field separated into 3 shape-(n,) arrays dx, dy, and dz and you have spatial coordinates in shape-(n,) arrays x and y. from scikits.delaunay import Triangulation t = Triangulation(x, y) dxinterp = t.nn_interpolator(dx) dyinterp = t.nn_interpolator(dy) dzinterp = t.nn_interpolator(dz) # Use nn_extrapolator if you want to find values outside of the convex hull of # the input points. If your interpolating points are on a grid, the easiest way to get the interpolated values is by "fake" slicing along the lines of numpy.mgrid. dx2 = dxinterp[0:1:101j, 0:2:201j] ... That interpolates the dx deformation across a grid going from 0 to 2 (inclusive) at a step of 0.01 in the X direction and 0 to 1 (inclusive) at a step of 0.01 in the Y direction (yes, the Y coordinate comes first; I'm not much happy with that either, but it seemed the most consistent with the way indexing "looks"). That should be reasonably fast; I've optimized grid-structured interpolating point sets. Let me know if you try this and anything you think can or should be improved about it. -- Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth." -- Umberto Eco
Thank you Zachary and Robert. In fact, I've decided to implement my own version (I'll make it available on the net, as it can be recurrent) based on the Bookstein article on the subject. I could use the rbf module, but I've decided that the dependence on scipy was not necessary (the function is needed at two places, not more, and the real trick was to compute the coefficients for the thin plates and then interpoling the field with it). Matthieu 2007/10/26, Matthieu Brucher <matthieu.brucher@gmail.com>:
Hi,
I wondered if someone knew of a package that allows the interpolation of a 3D deformation field with thin plates (or in fact with anything) based on a list of points and their associated deformation field. If only 2D deformation field is supported by a package, I'll go for it too ;)
-- French PhD student Website : http://miles.developpez.com/ Blogs : http://matt.eifelle.com and http://blog.developpez.com/?blog=92
-- French PhD student Website : http://miles.developpez.com/ Blogs : http://matt.eifelle.com and http://blog.developpez.com/?blog=92
Hi Matthieu, See attached my (GPL, but ask if you want in a different license) code for thin-plate image warping in 2D. It's straight out of Bookstein, but has some simple changes to make it tolerably fast in python/numpy. It still depends on ndimage for the image coordinate mapping (so that one can use the fancier interpolators available), but that's easy to remove. The basic code should work fine in 3D; I think only the interpolation of the coarse deformation grid to a finer grid (a hack anyway) is 2D specific. Anyhow, it should give you somewhere to start, and a hint at various caveats (like needing to set the log of very small values to zero to keep the thin plate function from exploding at times). Also, note that if you do choose to use the RBF module from scipy, you can just grab that file and put it into your code (modulo license restrictions) -- it doesn't depend on much else. Similarly, you could just grab Robert's delaunay scikit and incorporate that into your code so as not to have any dependencies. Zach On Oct 28, 2007, at 11:12 AM, Matthieu Brucher wrote:
Thank you Zachary and Robert. In fact, I've decided to implement my own version (I'll make it available on the net, as it can be recurrent) based on the Bookstein article on the subject. I could use the rbf module, but I've decided that the dependence on scipy was not necessary (the function is needed at two places, not more, and the real trick was to compute the coefficients for the thin plates and then interpoling the field with it).
Matthieu
2007/10/26, Matthieu Brucher <matthieu.brucher@gmail.com>: Hi,
I wondered if someone knew of a package that allows the interpolation of a 3D deformation field with thin plates (or in fact with anything) based on a list of points and their associated deformation field. If only 2D deformation field is supported by a package, I'll go for it too ;)
-- French PhD student Website : http://miles.developpez.com/ Blogs : http://matt.eifelle.com and http://blog.developpez.com/? blog=92
-- French PhD student Website : http://miles.developpez.com/ Blogs : http://matt.eifelle.com and http://blog.developpez.com/? blog=92 _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
Hi, I see that you compute directly the new image ;) For the tool we are developping in my lab, we prefer to split everything (one function to compute a deformation field and one function for applying the deformation field), as some times we only want to work on the field, sometimes on the image, ... I didn't use the same approach than you, I tried to maximize the use of Numpy too (so to compute the distances, I used Bill Baxter's function he proposed some time ago, the computation of the sum in the smooth continuous field is done by a matrix multiplication, ...), which means that my approach may use more memory than yours. I've only one thing that I have to modifiy, it is the computation of r²log r² when r is too small, I saw that you took care of it. For those who are interested in the future, they have now two solutions : http://matt.eifelle.com/item/4 Matthieu 2007/10/28, Zachary Pincus <zpincus@stanford.edu>:
Hi Matthieu,
See attached my (GPL, but ask if you want in a different license) code for thin-plate image warping in 2D. It's straight out of Bookstein, but has some simple changes to make it tolerably fast in python/numpy.
It still depends on ndimage for the image coordinate mapping (so that one can use the fancier interpolators available), but that's easy to remove. The basic code should work fine in 3D; I think only the interpolation of the coarse deformation grid to a finer grid (a hack anyway) is 2D specific.
Anyhow, it should give you somewhere to start, and a hint at various caveats (like needing to set the log of very small values to zero to keep the thin plate function from exploding at times).
Also, note that if you do choose to use the RBF module from scipy, you can just grab that file and put it into your code (modulo license restrictions) -- it doesn't depend on much else. Similarly, you could just grab Robert's delaunay scikit and incorporate that into your code so as not to have any dependencies.
Zach
-- French PhD student Website : http://miles.developpez.com/ Blogs : http://matt.eifelle.com and http://blog.developpez.com/?blog=92
participants (3)
-
Matthieu Brucher
-
Robert Kern
-
Zachary Pincus