R-Snakes on Polygonal Meshes

Abstract

In this research project at the Computer Graphics Group, which was supervised by Stephan Bischoff, I implemented a framework for active contours, also called snakes, on polygonal meshes. The key idea of this approach is that the snake topology is fully determined by the underlying mesh. In contrast to classical image snakes, the concept of R-Snakes is used in which the snake is a piecewise linear curve, i.e. a (closed or open) polygon. Because the polygon is embedded into the mesh plane, the vertices of the snake lie on the edges of the mesh and the edges of the snake lie in the polygons of the mesh. As in the 2D case, snakes on polygonal meshes are a physical model controlled by forces which are determined with respect to the underlying mesh and the shape of the snake itself. We believe that this approach has a variety of applications, for example in mesh texturing or in the detection of blood vessel constrictions in medicine.

The approach was presented at the Bilverarbeitung für die Medizin Workshop 2005 in Heidelberg, where it received the best poster award.

See below for the publication and a video.

What are (classic) Snakes?

Active Contour Models, also known as Snakes, are a powerful method for feature detection in images. The basic principle is a deformable spline that can move freely on an image. Several forces act on this spline and implicitly control its movement. There are image forces that attract the snake to features and internal forces of the snake that control its shape. For example, a bending force will preserve the smoothness of the snake. A particular benefit of snakes in comparison to conventional methods is their ability to interpolate incomplete features. Because of this and because of their adjustable shape properties, snakes have established themselves as a valuable tool for image segmentation.

The Computer Graphics Group at RWTH Aachen developed a variant of snakes, called R-Snakes (Paper) which have additional desirable properties and which can be generalized to the three-dimensional case.

Why Snakes on Meshes?

The motivations for implementing snakes on polygonal meshes is basically the same as for images. Snakes are a powerful tool for segmentation and feature detection. Especially the property of adjustable smoothness is interesting for mesh segmentation, because mesh texturing works best when the mesh is decomposed into patches with smooth borders. Various other applications, for example in the field of medicine, could be thought of. The above image shows a snake on the mesh of a blood vessel. The inner energy of the snake causes it to act like a rubber band, i.e. to minimize its size. So, the snake can be used to detect narrow parts of the blood vessel which could cause embolisms. Another application of snakes on meshes could be the guided selection of mesh borders. This would be the 3D-equivalent to the magic lasso tool from Gimp or Photoshop that helps to create selections that follow image borders.

How it works

An R-Snake on a mesh is a closed or open polygon that is embedded into the plane of the mesh, i.e. that lies directly on the mesh. An initial snake is drawn onto the mesh by the user and then evolves according to certain physical forces that can be freely configured and combined to suit the task.

The inner forces of the snake are for example a bending force that is used to maintain the smoothness. If the snake is a closed loop, a "balloon force" can be used to "inflate" the snake like a balloon so that the front moved towards mesh features.

The outer forces of the snake are feature forces which pull the snake in the direction of mesh features, i.e. areas of high curvature, like edges.

The ability to combine these forces is the strength of the snakes approach. It enables interpolation of noisy, blurry or incomplete features with a smooth polygon. The tradeoff between interpolation closeness and snake smoothness can be adjusted by the user in real-time. To get an impression of how the snake reacts to the forces and how well it interpolates mesh features, watch the video below.

Images

This image shows a snake (red) on a horse mesh. The color coding of the horse indicates its local curvature, where yellow stands for high curvature. The inner energy of the snake preserves its smoothness while the external enery pulls the snake into the direction of features.


Here we see a snake on the windshield of a BMW. While the windshield itself it rather smooth, the edges have a high curvature and thus the snake is attracted to these.

Material

The publication "Snakes on Triangle Meshes" can be found here.

For a presentation at the Computer Graphics Group, I made a video that demonstrates the power of R-Snakes on polygonal meshes. It can be downloaded from here.