B-spline Snakes and a JAVA interface:

An Intuitive Tool for General Contour Outlining

Patrick Brigger’ and Robert Engel Michael Unser

ImageMinds Biomedical Imaging Group
Imaging and Internet Technologies Swiss Federal Institute of Technology (EPFL)
Greenwich, CT, USA CH-101.5 Lausanne, Switzerland

and specific to a particular problem, usually requiring

Abstract important computational resources and not allowing a
We present a novel formulation for B-spline snakes manual intervention.
that can be used as a tool for fast and intuitive contour The snake as an energy minimizing “spline” has found
outlining. The theory is implemented in a platform wide acceptance and has proven extremely useful in
independent JAVA interface, which allows real time applications for medical analysis [ 11, feature tracking in
computation of the snake curve. In this paper, our main video sequences [ 2 ] , 3D object recognition[3], stereo
focus is on two points. First, we propose a novel B-spline matching [4, 51. The original snake by Kass et. al. [5] is
snake formulation, where the intrinsic scale of the spline the solution of a functional minimization problem of Euler
model is adjusted a priori. It leads to a reduction of the equations. The snake gives an elegant method to simulate
number of parameters to be optimized and eliminates the an elastic material, which can dynamically conform to
need for internal energies. The approach solves the two local image features. It is guided by external and internal
main drawbacks of traditional snakes (slow convergence forces. The former are given as a user supplied function,
speed and diJ5cult to adjust weighting factors for internal while the latter is determined by the shape of the curve in
energy terms). Second, we comment on our experience terms of first and second order derivatives. While it
using JAVA for the implementation of the snake and for provides an elegant mathematical solution, it has two
the design of the graphical user interface. Our technique main drawbacks: 1) a large number of control points
provides a very intuitive, user-friendly, and plalform subject to optimization, 2) an explicit formulation of the
independent tool for contour outlining, generally smoothness constraint, which requires the knowledge of
applicable to a vast range of images. Several biomedical difficult to determine a priori weighting factors. The
examples of applications are included to illustrate the associated problems of slow convergence speed and
versatility of the method. difficult user-interaction have been addressed in a number
of publications [6,7, 81.
The recent introduction of B-snakes provides an
1. Introduction alternative approach to snakes, which also circumvents
many of the inherent problems [4, 9, 101. The B-snake is
Many applications require the extraction of salient mainly characterized by the following points: 1) few
image features such as edges, lines, subjective differences parameters, and 2) smoothness implicitly built into the
in gray-level. Often, users are interested in computer model. In addition, the B-snake approach naturally
assisted devices that help to detect and outline an image permits the local control of the curve by controlling
contour, but which still permit input of personal individual control points.
knowledge and experience. Such an approach is The motivation for our work is to extend the basic
especially desirable in medical imaging, for the detection concept of B-spline snakes in order to improve their
of specific organs or other medical features of interest. efficiency, speed, and to provide a means for intuitive
Often, two types of problems subsist: a) contour outlining interaction. Our main contributions are as follows: First,
is either too elementary and subjective (manual outlining we introduce a scale parameter for the B-splines, which
using a pencil tool) or b) contour outlining is automatic,

’ This work was mainly performed while employed with the Bioengineering and Physical Science Program, BEPUORS,
National Institutes of Health (NIH), Bethesda, MD, USA.

277
0-8186-8821-1/98 $10.00 0 1998 IEEE
allows us to control the smoothness of the snake final curve. In the discrete case, we only render the curve
implicitly. Second, the proposed formulation eliminates for t integer, in which case we associate M = t,, + 1 .
the need for curve-internal energies, making the snake Clearly, if we specify N (i.e. the number of snake control
more convenient to handle because no internal energy points) and M,the curve resolution, then the knot spacing
weight terms need to be determined. Third, we discuss is h = M IN and therefore the smoothness constraint for
object-oriented implementation issues, and the adequacy the curve is defined. The freedom of the curve has been
of JAVA as programming language. reduced by the same amount, resulting in a smoothing and
In the next section, the B-spline snake will be formally stiffening of the curve. Increasing the number N of control
derived. Section 3 discusses some implementation issues, points will reduce the knot spacing, and consequently it
and in Section 4, a number of examples are presented. will reduce the smoothing effect of the curve. The energy
term may now be formulated in the following way:
2. B-spline snakes:
Parametric formulation t(c(k)) = c
M

i=O
s y (9)
g(s, (4, (3)
In this section, the goal is to introduce our parametric
where g(x, y) = L [ f ( x ,y)] . L is an image processing
B-spline snake formulation, which is characterized by a
scale parameter for the splines. A two-dimensional B- operator (for example, gradient magnitude) that enhances
spline curve is defined by its control points as: the contours of interest in the imagef(x,y). The operator
may include a smoothing component to reduce the
s(t>= (s,(t>,s,(t>> = C c ( k ) . P " ( t - k ) likelihood of the snake getting trapped in a local
keZ (1) minimum. Optimization of (3) is carried out using a
(OStSt,, =N-1) conjugate gradient algorithm [ 1 11. With this algorithm,
the direction of search for each independent variable is in
where s,(t) and s,(t) are the x and y spline
an A-orthogonal direction with respect to the other
components, respectively, both parameterized by the variables. In the case of a quadratic potential function, the
curvilinear variable t. N denotes the number of control procedure leads to a scheme where exactly one step is
points, which corresponds to the number of primary B- done in every search direction. In other words, the
spline coefficients, denoted by c ( k ) = (c, ( k ) ,c y ( k ) ) . AS principal idea is that once a parameter is optimized, the
the sum needs to be carried out over the domain of all remaining parameters are moved in directions conjugate
integers, the remaining coefficients are found through to the previously optimized parameters, such that those
appropriate boundary conditions. Based on ( l ) , B-snake are not modified any more. An iterative scheme is used
formulations have been proposed, which minimize an for non-quadratic potential function.
energy functional that consists of an external, user In Fig. 1, we demonstrate the similar optimization
supplied term, and an internal, curve specific term [4, 9, performances of the proposed B-spline snake formulation
101. While the formulation allows a continuous without internal energies, versus the traditional snake
representation of the curve, it still is subject to some of formulation [5] with internal energies. The comparison is
the same limitations as in the traditional approach. The based on a binary test image consisting of a vertical line,
idea presented here is to eliminate the term corresponding of which a small part has been displaced to the left (see
to the internal energy and to introduce a variable knot Fig. 1, initial contour). In order to obtain a smooth force
spacing between the spline knot points. An increased knot function, the binary image is smoothed by a two
spacing will essentially have the same smoothing effect on dimensional Gaussian, with a = 5 . Optimization is
the solution. Thus, we consider a B-spline curve with a formulated as a minimization problem, and hence the
coarser knot spacing h > 1 : optimal snake position is on the line. Eleven control
points that have been set manually at unequal length
t intervals characterize the initial snake curve. Depending
Sh (0 = ( k ) . p" (-h - k ) ,
keZ on the smoothness requirements of the final curve, two
(OItIt,, =hN-1) different results can be anticipated from the optimization.
a) The resulting curve is vertically centered on the longer
The new smoothness parameter is thus h. Typically, line, being unaffected by the small displaced part. Such an
we will take h to be an integer m, which will reduce the outcome corresponds to an important smoothing
number of degrees of freedom (B-spline coefficients) in constraint. b) The resulting curve has a "bump" and is
the same proportion. The end of the curve is given at attracted towards the small displacement on the left. This
t = t,, , which is dictated by the desired resolution of the outcome reflects a less severe smoothness requirement.

278
 First, the traditional snake is computed with various
weights for the internal energies. Each discrete curve
point is independently optimized and attracted to the
closest minimum by setting weights for the stretching and
bending energy to zero (Fig. la). A weight of
(x,tretch = 0.1 and Bstretch= 0.1 tends to pull the “bump”
towards the right (Fig. lb), however, does not produce a
straight curve yet. A weight of (xStre& =0.2
and bstretch = 0.2 produces an almost flat curve (Fig. IC). b) h i 2 d h-4

c>
This type of snake proves to be very flexible in that the Figure 2: B-spline snake: Initial contour and optimization with
user can choose among a large number of smoothness different knot spacings.
requirements by adjusting ffstretch and Bstretch. The
feature may also represent a drawback for certain representations. The optimized result with h=2 is shown
applications, because of the associated difficulties in in Fig. 2b. Note that there is one interpolated point
choosing the correct weighting factors, by either empirical between two control points. The point helps attracting the
of automatic means. curve towards the longer line. An increased knot-spacing
with h=3 uses two interpolated values between two
The B-spline snake incorporates smoothness through control points for computation of energy (Fig. 2c). In this
different knot spacings. The knot spacing, h = M I N , configuration, these points manage to fully attract the
where M is the number of interpolated points and N is the curve towards the longer line, and the “bump” disappears.
number of control points, can be changed by either The experiment demonstrates the similar effect of a
varying M or N. For this example, we have decided to variable knot spacing and of internal energies on the
employ the same number of control points as for the smoothness of the final snake curve.
traditional snake, and hence h is changed by changing the
number of interpolated points M. A knot spacing of h=I 3. Object-orientedimplementation using
signifies that no points are interpolated between control The JAVA programming language
points. A B-spline of degree one corresponds exactly to
the above experiment with zero weights, and the result is Java was born three years ago. Every since, it has
identical (Fig. 2a). Using a B-spline of higher degree, attracted programmers’ attention, mainly because of its
control points are no longer completely independent. For ability to run through web browsers, providing
all remaining experiments, we have used a B-spline of sophisticated and animated web pages. The power of
degree three, because it leads to visually pleasant curve Java, however, goes much further than that. It is a
language that naturally supports an object-oriented
implementation approach, being more convenient and less
error prone than C++, for example. Furthermore, its
0 ability to run on different computer platforms makes it
attractive to stand-alone applications as well. For image
processing, it has not been widely used so far, because of
the slow performance capabilities of the interpreter. New
improved just-in-time compilers and native compilers,
a,,,e,ch =oo o.,,#,c*= 0 1 =02
hltwl m M l r
abmd=OO abmd=O1
she,rh
nbad=O2
however, have increased execution speeds. We have
a) b) C) successfully implemented the B-spline snake in a Java
Figure 1: Traditional snake: Initial contour and optimization framework, with real-time curve rendering speeds. Curve
with different internal energies. optimization requires less than 10 sec. on a 166MHz
Pentium I1 Processor for a snake curve with 4 control
points.
The B-spline snake algorithm design is object-
oriented. In other words, the basic algorithm is designed
to optimize an object of type Function with some given
boundary conditions of type Boundary. Given such a
framework, it is then possible to define an object
Functionspline derived from Function, as well as

279
different boundary objects (BoundaryPeriodic, optimization, as well as 3D surface rendering of the
BoundaryMirror, etc.) derived from Boundary. Such a segmentation result. Various bio-medical examples have
design is very general and allows the introduction of new illustrated the versatility of the method.
functions and boundary conditions at any time, without
having to change the main program. From our experience,
the Java language lends itself extremely well for such an
implementation, and usually allows a development in a
shorter time than C++, for instance.

4. Application results
Typically, it is routine medical practice for a
technician to outline the boundaries of the liver, spleen,
ludneys, etc. in CT scans. Often, the standard imaging
tools consist of an interface that allows manual border
tracing using the computer mouse. Technicians face
several problems related to that task. First, the hand drawn
boundary is subject to small, uncontrollable hand
movements that result in a noisy boundary. Second, often
the technician does not have the possibility to pause in the
outlining process. Also, a curve that is not considered
satisfactory often has to be redrawn in its entirety.
We have asked an experienced technician to roughly
outline the boundaries of the corpus callosum using the B-
spline snake concept (Fig. 3a). The initial curve is then b)
optimized and the final segmentation result is shown in
Fig. 3b. Figure. 3: Outlining of the corpus callosum: a) initial curve and
b) automatically optimized curve.
Another example is given in Fig. 3. The goal here is to
detect the endothelial walI in an intravascular ultrasound
image sequence that has been obtained by constant pull
back of the ultrasound device. The initial contour is
placed manually in the first frame (Fig. 4a). The snake is
optimized and attracted to the endothelial wall (Fig. 4b).
The result is then automatically propagated to the next
frame, where it is again optimized. This process is iterated
through the entire image sequence, and yields a 3D
segmentation of the coronary wall. The segmentation
result can be displayed as a 3D body using surface
rendering techniques. The visualization program is also
implemented in Java, and is shown in Fig. 5.

5. Conclusions
We have presented a novel implementation of the B-
spline snake, which is characterized by a variable knot
spacing. The approach eliminates the need for internal
energies. Hence, this type of snake gives an intuitive way
of user-interaction, because it does not require adjustment
of weighting factors. Also, it features fast convergence
speeds, because of the reduced number of control points.
We have discussed the possibility of an implementation
using Java. Our experiments show that the language is fast
enough for real-time computation of the curve, fast

280
 Understanding Workshop, pp. 720-726, Darpa,
September, 1990.
M. Kass, A. Witkin and D. Terzopoulos, "Snakes: Active
contour models", Internat. J. of Computer Vision, pp.
321-331, 1988.
A. Amini, T. Weymouth and R. Jain, "Using dynamic
programming for solving variational problems in vision",
IEEE Trans. on Pattern Analysis and Machine
Intelligence, vol. 12, no. 9, pp. 855-867, September, 1990.
K. Lam and H. Yan, "Fast greedy algorithm for active
contours", Electronics Letters, vol. 30, no. 1, pp. 21-23,
1994.
G. Xu, E. Segawa and S. Tsuji, "Robust active contours
with insensitive parameters", Pattern Recognition, vol. 27,
no. 7, pp. 879-884, 1994.
M. Flickner, H. Sawhney, D. Pryor and J. Lotspiech,
"Intelligent interactive image outlining using spline
snakes", in 28th Asilomar Conference on Signals,
Figure 4: Example of an ultrasound sequence of the coronary Systems, and Computers, vol. 1, pp. 731-735, 1994.
artery. a) initial, manually placed contour, b) automatically M. Wang, J. Evans, L. Hassebrook and C. Knapp, "A
optimized contour. For this example, only four control points multistage, optimal active contour model", IEEE Trans.
were necessary. on Image Processing, vol. 5, no. 11, pp. 1586-1591,
November, 1996.
E. Polak, Computational methods in optimization. New
York: Academic Press, 1971.

Figure 5: 3D representation of a segment of the coronary artery.

References:

A. Klein, T.K. Egglin, J.S. Pollak, F. Lee and A. Amini,

"Identifying vascular features with orientation specific
filters and B-spline snakes", Computers in Cardiology, pp.
113-116,1994.
M. Hoch and P. Litwinowicz, "A semi-automatic system
for edge tracking with snakes", The Visual Computer, vol.
12, pp. 75-83, 1996.
J. Wang and F. Cohen, "Part 11: 3-D object recognition
and shape estimation from image contours using B-
splines, shape invariant matching, and neural networks",
IEEE Trans. on Pattern Analysis and Machine
Intelligence, vol. 16, no. 1, pp. 13-23, January, 1994.
S. Menet, P. Saint-Marc and G. Medioni, "B-snakes:
Implementation and application to stereo", in Image

281