T-snakes: topology adaptive snakes

We present a new class of deformable contours (snakes) and apply them to the segmentation of medical images. Our snakes are defined in terms of an affine cell image decomposition (ACID). The 'snakes in ACID' framework significantly extends conventional snakes, enabling topological flexibility among other features. The resulting topology adaptive snakes, or 'T-snakes', can be used to segment some of the most complex-shaped biological structures from medical images in an efficient and highly automated manner.

Topology adaptive deformable surfaces for medical image volume segmentation

Deformable models, which include deformable contours (the popular snakes) and deformable surfaces, are a powerful model-based medical image analysis technique. We develop a new class of deformable models by formulating deformable surfaces in terms of an affine cell image decomposition (ACID). Our approach significantly extends standard deformable surfaces, while retaining their interactivity and other desirable properties. In particular, the ACID induces an efficient reparameterization mechanism that enables parametric deformable surfaces to evolve into complex geometries, even modifying their topology as necessary. We demonstrate that our new ACID-based deformable surfaces, dubbed T-surfaces, can effectively segment complex anatomic structures from medical volume images.

The computer synthesis of expressive faces

This paper presents a methodology for the computer synthesis of realistic faces capable of expressive articulations. A sophisticated three-dimensional model of the human face is developed that incorporates a physical model of facial tissue with an anatomical model of facial muscles. The tissue and muscle models are generic, in that their structures are independent of specific facial geometries. To synthesize specific faces, these models are automatically mapped onto geometrically accurate polygonal facial representations constructed by photogrammetry of stereo facial images or by non-uniform meshing of detailed facial topographies acquired by using range sensors. The methodology offers superior realism by utilizing physical modelling to emulate complex tissue deformations in response to coordinated facial muscle activity. To provide realistic muscle actions to the face model, a performance driven animation technique is developed which estimates the dynamic contractions of a performer’s facial muscles from video imagery.

Deformable models and the analysis of medical images

Deformable models are a popular and vigorously researched model-based approach to computer-assisted medical image analysis. The widely recognized efficacy of deformable models stem from their ability to segment, match and track images of anatomic structures by exploiting (bottom-up) constraints derived from the image data together with (top-down) a priori knowledge about the location, size and shape of structures of interest. Deformable models are capable of accommodating the often significant variability of biological structures over time and across different individuals. Furthermore, they support highly intuitive interaction mechanisms that allow medical scientists and practitioners to bring their expertise to bear on the model-based image interpretation task as necessary. In this paper we will review deformable models and present some recent developments in the methodology, including topologically adaptable deformable models, an approach that permits segmentation and reconstruction of topologically complex anatomical structures.

Deformable models in medical image analysis: a survey

This article surveys deformable models, a promising and vigorously researched computer-assisted medical image analysis technique. Among model-based techniques, deformable models offer a unique and powerful approach to image analysis that combines geometry, physics and approximation theory. They have proven to be effective in segmenting, matching and tracking anatomic structures by exploiting (bottom-up) constraints derived from the image data together with (top-down) a priori knowledge about the location, size and shape of these structures. Deformable models are capable of accommodating the significant variability of biological structures over time and across different individuals. Furthermore, they support highly intuitive interaction mechanisms that, when necessary, allow medical scientists and practitioners to bring their expertise to bear on the model-based image interpretation task. This article reviews the rapidly expanding body of work on the development and application of deformable models to problems of fundamental importance in medical image analysis, including segmentation, shape representation, matching and motion tracking.

A dynamic finite element surface model for segmentation and tracking in multidimensional medical images with application to cardiac 4D image analysis

This paper presents a physics-based approach to anatomical surface segmentation, reconstruction, and tracking in multidimensional medical images. The approach makes use of a dynamic "balloon" model--a spherical thin-plate under tension surface spline which deforms elastically to fit the image data. The fitting process is mediated by internal forces stemming from the elastic properties of the spline and external forces which are produced form the data. The forces interact in accordance with Lagrangian equations of motion that adjust the model's deformational degrees of freedom to fit the data. We employ the finite element method to represent the continuous surface in the form of weighted sums of local polynomial basis functions. We use a quintic triangular finite element whose nodal variables include positions as well as the first and second partial derivatives of the surface. We describe a system, implemented on a high performance graphics workstation, which applies the model fitting technique to the segmentation of the cardiac LV surface in volume (3D) CT images and LV tracking in dynamic volume (4D) CT images to estimate its nonrigid motion over the cardiac cycle. The system features a graphical user interface which minimizes error by affording specialist users interactive control over the dynamic model fitting process.

Computer-assisted registration, segmentation, and 3D reconstruction from images of neuronal tissue sections

Neuroscientists have studied the relationship between nerve cell morphology and function for over a century. To pursue these studies, they need accurate three-dimensional models of nerve cells that facilitate detailed anatomical measurement and the identification of internal structures. Although serial transmission electron microscopy has been a source of such models since the mid 1960s, model reconstruction and analysis remain very time consuming. The authors have developed a new approach to reconstructing and visualizing 3D nerve cell models from serial microscopy. An interactive system exploits recent computer graphics and computer vision techniques to significantly reduce the time required to build such models. The key ingredients of the system are a digital "blink comparator" for section registration, "snakes," or active deformable contours, for semiautomated cell segmentation, and voxel-based techniques for 3D reconstruction and visualization of complex cell volumes with internal structures.

Physically-based modeling: past, present, and future

My name is Demetri Terzopoulos and my co-chair, John Platt, and I would like to welcome you to the panel on Physically-Based Modeling -- Past, Present and Future. I'll start by introducing the panelists; the affiliations you see listed on the screen are somewhat out of date.

I'm Program Leader of modeling and simulation at the Schlumberger Laboratory for Computer Science in Austin, Texas, and I was formerly at Schlumberger Palo Alto Research. I'll speak on the subject of deformable models.

John Platt, formerly of Cal Tech, is now Principal Scientist at Synaptics in San Jose, California. He will be concentrating on constraints and control.

Alan Barr is Assistant Professor of computer science at Cal Tech. Last year he received the computer graphics achievement award. He'll speak about teleological modeling.

David Zeltzer is Associate Professor of computer graphics at the MIT Media Laboratory. He will be speaking on interactive micro worlds.

Andrew Witkin, formerly of Schlumberger Palo Alto Research, is now Associate Professor of computer science at Carnegie Mellon University. He will speak about interactive dynamics.

Last but not least, we have with us James Blinn, who of course needs no introduction. Formerly of JPL, he is now Associate Director of the Mathematics Project at Cal Tech. He says he'll have several random comments to make against physically-based modeling.

I was also asked by the SIGGRAPH organizers to remind the audience that audio and video tape recording of this panel is not permitted.

Many of you are already familiar with physically-based modeling, so I will attempt only a very simple introduction to this, in my opinion, very exciting paradigm. Physically-based techniques facilitate the creation of models capable of automatically synthesizing complex shapes and realistic motions that were, until recently, attainable only by skilled animators, if at all. Physically-based modeling adds new levels of representation to graphics objects. In addition to geometry -- forces, torques, velocities, accelerations, kinetic and potential energies, heat, and other physical quantities are used to control the creation and evolution of models. Simulated physical laws govern model behavior, and animators can guide their models using physically-based control systems. Physically-based models are responsive to one another and to the simulated physical worlds that they inhabit.

We will review some past accomplishments in physically-based modeling, look at what we are doing at present, and speculate about what may happen in the near future. The best way to get a feel for physically-based modeling is through animation, so we will be showing you lots of animation as we go along.

I would like to talk about deformable models, which are physically-based models of nonrigid objects. I have worked on deformable models for graphics applications primarily with Kurt Fleischer and also with John Platt and Andy Witkin. Deformable models are based on the continuum mechanics of flexible materials. Using deformable models, we can model the shapes of flexible objects like cloth, plasticine, and skin, as well as their motions through space under the action of forces and subject to constraints.

Please roll my Betacam tape. Here is an early example of deformable surfaces which are being dragged by invisible forces through an invisible viscous fluid. Next we see a carpet falling in gravity. It collides with two impenetrable geometric obstacles, a sphere and a cylinder, and must deform around them. The next clip shows another clastic model. It behaves like a cloth curtain that is suspended at the upper corners, then released.

Here is a simulated physical world -- a very simple world consisting of a room with walls and a floor. A spherical obstacle rests in the middle of the floor. You're seeing the collision of an elastically deformable solid with the sphere. Of course, we're also simulating gravity.

We've developed inelastic models, such as the one you see here which behaves like plasticine. When the model collides with the sphere, there's a permanent deformation. By changing a physical parameter, we obtain a fragile deformable model such as the one here. This deformable solid breaks into pieces when it hits the obstacle.

Deformable models can be computed efficiently in parallel. This massively parallel simulation of a solid shattering over a sphere was computed on a connection machine at Thinking Machines, with the help of Carl Feynman.

Here is a cloth-like mesh capable of tearing. We're applying shear forces to tear the mesh. The sound you're hearing has been generated by an audio synthesizer which was programmed by Tony Crossley so that it may be driven by the physical simulation of the deformable model. Whenever a fiber breaks, the synthesizer makes a pop. Keep watching the cloth; we get pretty vicious with it.

Deformable models are obviously useful in computer graphics, but they are also useful for doing inverse graphics; that is to say, computer vision.

For example, here we see an image of a garden variety squash. Using a deformable tube model, we can reconstruct a three dimensional model of the squash from its image, as shown. Once we have reconstructed the model from the image, we can rotate the model to view it from all sides. You can see, we have captured a fully three dimensional model from that single, monocular image. That's a basic goal of computer vision.

Kurt Fleischer, Andy Witkin, Michael Kass, and I used this deformable model based vision technique to create an animation called <i>Cooking with Kurt.</i> We wanted to mix live video and physically-based animation in this production. You see Kurt entering a kitchen carrying three vegetables. We captured deformable squash models from a single video frame of the real squashes sitting on the table -- this particular scene right here. Now the reconstructed models are being animated using physically-based techniques. The models behave like very primitive actors; they have simple control mechanisms in them that make them hop, maintain their balance, and follow choreographed paths. The collisions and other interactions that you see are computed automatically through the physical laws, and they look quite realistic. It's difficult to do this sort of thing by hand, even if you're a skilled animator.

This second tape will show you some of the physically-based modeling we're up to now at the Schlumberger Laboratory for Computer Science. Keith Waters and I are working on interactive deformable models. We're now able to compute and render deformable models in real time on our Silicon Graphics Iris 240 GTX computer. For example, here is a simulation of a nonlinear membrane constrained at the four corners and released in a gravitational field. Watch it bounce and wiggle around.

Here you're seeing a physically-based model of flesh. It's a three dimensional lattice of masses and springs with muscles running through it. Again, this is computed and displayed in real time. You can see the muscles underneath displayed as red lines. They're fixed in space at one end and attached to certain nodes of the lattice model at the other end. By contracting the muscles we can produce deformations in this slab of -- whale blubber, if you will. We did this simulation as an initial step towards animating faces using deformable models as models of facial tissue. And of course, the muscle models make good facial muscles.

The next clip will demonstrate real time, physically-based facial animation on our SGI computer. Here we see the lattice structure of the face. Let's not display all of the internal nodes so that we can see the epidermis of the lattice more clearly. There. Now we're contracting the zygomatic muscle attached to one edge of the mouth -- now both zygomatics are contracting to create a smile. The muscles inside the face model are producing forces which deform the flesh to create facial expressions.

Now the epidermis polygons are displayed with flat shading. Next we contract the brow muscles. Here the epidermis is being shaded smoothly. Finally, we relax the muscles and the face returns to normal.

An important reason for applying the physically-based modeling approach to facial animation is realism. For instance, the facial tissue model automatically produces physically realistic phenomena such as the laugh lines around the mouth and the cheek bulges that you see here.

Keith videotaped this animation off of our machine only last week. Our next step will be to develop control processes to coordinate the muscles so that the face model can create a wide range of expressions in response to simple commands. Keith's prior work on facial animation, published in SIGGRAPH 87, showed how one can go about doing this using muscle model processes. Beyond muscle control processes, we're also interested in incorporating vocoder models -- that is, physically-based speech coding and generation models, so that this face can talk to you.

The tape will end soon, so I'll release the podium to Dr. John Platt, who will talk about constraint methods and control. Thank you.

From splines to fractals

Deterministic splines and stochastic fractals are complementary techniques for generating free-form shapes. Splines are easily constrained and well suited to modeling smooth, man-made objects. Fractals, while difficult to constrain, are suitable for generating various irregular shapes found in nature. This paper develops constrained fractals , a hybrid of splines and fractals which intimately combines their complementary features. This novel shape synthesis technique stems from a formal connection between fractals and generalized energy-minimizing splines which may be derived through Fourier analysis. A physical interpretation of constrained fractal generation is to drive a spline subject to constraints with modulated white noise, letting the spline diffuse the noise into the desired fractal spectrum as it settles into equilibrium. We use constrained fractals to synthesize realistic terrain models from sparse elevation data.

Image analysis using multigrid relaxation methods

Image analysis problems, posed mathematically as variational principles or as partial differential equations, are amenable to numerical solution by relaxation algorithms that are local, iterative, and often parallel. Although they are well suited structurally for implementation on massively parallel, locally interconnected computational architectures, such distributed algorithms are seriously handi capped by an inherent inefficiency at propagating constraints between widely separated processing elements. Hence, they converge extremely slowly when confronted by the large representations of early vision. Application of multigrid methods can overcome this drawback, as we showed in previous work on 3-D surface reconstruction. In this paper, we develop multiresolution iterative algorithms for computing lightness, shape-from-shading, and optical flow, and we examine the efficiency of these algorithms using synthetic image inputs. The multigrid methodology that we describe is broadly applicable in early vision. Notably, it is an appealing strategy to use in conjunction with regularization analysis for the efficient solution of a wide range of ill-posed image analysis problems.