Curve Morphing

A python module for morphing curves and creating 3D meshes.

Download
Blender plugins
How it works
Screenshots
Work for developers to do
Acknowledgements
References

Download the CurveMorphing module

Installation instructions included with the files.

I would very much appreciate if you can contribute a Windows Visual Studio compilation.

PLEASE NOTE: this release is fully stable in the systems tested and for the purposes tested, but may not be for your particular setup. USE AT YOUR OWN RISK, the General Public License (GPL) applies, and if you come across any problems please report back with a ready test case to reproduce it.

Blender python plugins that use the module

Load .shapes from ImageJ's 3D editing plugin.
Enables the loading of user-drawn Bézier, brush and wand curves, and also pipes and balls, as stored in a .shapes file generated by the 3D Editing ImageJ's plugin. The main application is for the creation of 3D models of biological data, particularly designed to work best with confocal stacks of images, i.e. seriated images in which an XY section of the object to model shows in each.
Bezier curve skin maker.
Draw several multi-point Bézier curves in the XY plane, stacked along the Z axis, select them all, and run the plugin to generate a mesh (a 3D skin) that wraps them. It works independently of the number of control points of each Bézier curve. Do not rotate the Bézier curves in Object Mode, because the plugin does not read the object rotation. This is because I failed miserably at figuring out how the point coordinates are translated. If you happen to know how, of if you know of any documentation on the subject please let me know.
This plugin is extremely barebones because the Blender Curve Python API is broken in 2.37a, and therefore I can't really apply the desired functionality, i.e. to have the curves dynamically alter a mesh defined by them and contained within. This will have to wait until Blender 2.40 becomes stable.

Screenshots

This head below was generated by outlining the skull in an MRI scan of a human head. The Bézier curves were drawn over a stack of 50 slices using the 3D Editing plugin for ImageJ, and then imported using the load_shapes_v1.4.3.py and the CurveMorphing module with 1 interpolated curve between any two Z consecutive pair of curves, scale 0.1, and depth 5.5 (this is the distance in pixels that separates any two slices). The Bézier curves drawn had many different number of points each. The face is slightly deformed because this is the outline of the bones, the ears and the eyes, not the flesh. It took about 23 seconds to generate in my FreeBSD 5.3 Intel 2.8GHz 1GB DDR RAM. This is as it comes out, no smoothing, no nothing. From here, using standard Blender tools, one can generate and render a perfectly looking model of the head.

head generated with ImageJ's 3D editing plugin, the CurveMorphing module and the load_shapes_1.4.3.py.

head generated with ImageJ's 3D editing plugin, the CurveMorphing module and the load_shapes_1.4.3.py.

Here is the display highlighting the vertices. I have pushed "smooth" once, so some vertices are not perfectly aligned in the XY plane:
vertices of the head generated with ImageJ's 3D editing plugin, the CurveMorphing module and the load_shapes_1.4.3.py.

vertices of the head generated with ImageJ's 3D editing plugin, the CurveMorphing module and the load_shapes_1.4.3.py.

The images below illustrate the sort of problem solved by this C Python module. In commercially available programs such as Amira(TM), a volume is made from any set of consecutive outlines by thickening each outline and merging them all, creating what I call a "stack of pizzas", which is far less than optimal. There are two really undesirable consequences of this pizza stacking: 1) holes are created when one of the curves has an invagination so deep that it crosses the other side of the curve, and 2) curves that don't overlap at all in the Z axis are reconstructed as independent floating pizzas. Furthermore, if the user didn't outline a structure for a particular section, the final object will be sliced in two at that section. All these problems are addressed by the program presented here.

The program provided here creates smooth interpolated curves between any two consecutive curves, thus avoiding the creation of holes in the object, and also avoiding the representation of two non-overlapping outlines as separate floating pizzas. Since the program attempts to match any two Z-consecutive outlines, if the outline of any section is missing, an interpolated one will be created for it. The automatic interpolation of outlines saves the user lots of drawing when the outline of an object doesn't change match from section to section; i.e. the user only has draw every other or one every three, four, etc. sections and still obtain a very good model of the object of interest. Finally, since the outline is subsampled, the accuracy of the curve representation is user-defineable. The automated subsampling chosen by the program is simply the average of the point interdistance of all curves that represent the outlines of an object. The default value for subsampling already results in the number of triangles and quad faces used being much, much lower than that of Amira's created objects, without affecting at all the quality of the rendered surface, and resulting in much smaller files.

Some screenshots, showing a mesh made of 3 Bézier curves with different number of control points:

blender screenshot, the curves

How it works

From the Jiang et al. 2002 paper: "Shape morphing, also known as metamorphosis, shape interpolation, shape blending, and shape evolving, is to compute a continuous transformation from one shape (the source) to another (the target). The curve morphing problem is formulated as that of computing a weigthed mean of two strings, which is then solved by [Wagner and Fischer's algorythm]."

This implementation of the method described in Jiang et al. 2002 paper proceeds through several steps:

Generate the interpolated points for a given pair of Bézier curves to match, hereafter referred to as the 'perimeter'. Note any curve will work as well, not just Béezier curves.
Subsample the perimeter so that the average point interdistance is even.
Generate a string (a list) of vectors in the plane, that go from one point to the next, so that if the first point is provided, the whole perimeter can be reconstructed.
Compute the minimum edit distance between the two strings of vectors (the Levenshtein string distance), using edit operations as described in lots of detail in the Wagner and Fischer 1974 paper. In the case of closed perimeters, for every pair of strings to match the Levenshtein distance is calculated as many times as vectors the second string has. Every point in the second perimeter is used as starting point to match the first perimeter. The pair that result in the smallest Levenshtein distance will define the starting point in the second perimeter from which to start the matching with the first perimeter (starting from which the edit sequence is extracted). This step alone is a fundamental breakthrough in curve matching.
Determine the optimal edit path, i.e. the optimal list of mutation, insertion and deletion operations that lead to the morphing of one curve to another.
Apply the editions in a weighted manner to both strings of vectors, so that any desired number of morphed curves can be generated between the original curves. this was the idea explained in both the Jiang et al and Bunke et al paper, where they morphed fish shapes one to another -quite impressively.
Make a skin by crawling over any two Z-consecutive curves and applying several proximity and perpendicularity tests to define the optimal triangles and quad faces. This could be done as well (and as closest to perfection as it is possible) using the sequence of editions, but then if the curves are not perfectly one over the other -which is rarely the case in our biological data- the faces would have very diagonal edges, resulting in undesired shades and angles in the skin.

References

X. Jiang, H. Bunke, K. Abegglen, A. Kandel. 2002. "Curve Morphing by Weighted Mean of Strings." In Proceedings of the Sixteenth Conference on PAttern Recognition (ICPR 2002), volume 4, pages 192-195. IEEE Press, 2002. abstract (html)
H. Bunke, X. Jiang, K. Abegglen, A. Kandel. 2002. "On he weighted mean of a pair of strings." Pattern Analysis & Applications, 5:23-50. paper (PDF), abstract (html)
R.A. Wagner and M.J. Fischer. "The String-to-String Correction Problem." 1974. J. ACM. paper (PDF)

Work for developers to do

This 1.0 release is by no means final, but fully working and stable for the purpose intended. Despite, I am a flexible programmer and, precisely because of that, my knowledge of any given language has huge gaps. If you can identify bottle necks, memory leaks, or suggest optimizations, please do! If the module crashes on you, please report back with a test case to reproduce the problem.

Further, the curve morphing method is by no means restricted to 2D, but could be implemented for three-dimensional curves as well. I can lead you through the code if you'd like to go for such an implementation. I will not implement it myself because, to put it plainly, we already have what we need to do 3D models of biological data. And time is gold!

Acknowledgements

This C Python module would not have been possible without:

Python itself, a fantastic language which enabled me to make a fully functional prototype in one single day. Indeed I intended to leave it as a python script, but speed issues demanded a C module. The Python API resulted very useful and straighforward.
The GNU Project Debugger (GDB) and the Data Display Debugger (DDD), two fantastic tools to trace and identify the many ways that the programming language C enables to shoot oneself in the foot.
The #C channel at freenode, whose inhabitants provided many insights into the devious ways of malloc/realloc.
The fantastic 'screen' application and the text editor ViM, without which writting code can be simply a pain.
And last but not least, the Hartenstein's lab at UCLA for their interest in the project, the fantastic postdoc on Drosophila brain development, and for funding me, of course.