John Trinder
image may have several structures resembling the feature of interest (e.g., linear feature). It is therefore essential to ap-
proximately specify the structure in which the user is interested. Moreover, in order to restrict the search space of SA, we
have incorporated a windowing approach in the algorithm.
In this implementation, appropriate image processing techniques are applied initially and the energy image is computed.
Subsequently the operator determines the location of an active contour by interactively placing some points of the feature
near the image structure of interest which is taken as the initial state. B-splines are used to fit the initial user delineated
points and a rectangular window containing both the spline and the feature of interest is considered. Finally, SA is used to
provide an accurate estimate of the feature of interest by minimizing the energy of the state in the window. The superiority
of the method over the snakes model is demonstrated on a 2-D aerial image.
2 SIMULATED ANNEALING FOR FEATURE EXTRACTION
2.1 Preprocessing
Procedures to extract features from digital remotely sensed data typically involve initially the application of low level
image processing techniques. These require determination of sufficient attributes such as, edge gradients, texture, shadow,
etc., in the image to adequately define the features. Usually, some contrast and image enhancement techniques are used
to emphasize the characteristics of the image in the first stage. Moreover, noise reduction techniques are also applied to
reduce the effects of misleading information in the images. The extraction of linear features by semi-automatic methods
in this paper subsequently involves the application of edge detector algorithms (Canny 1986, Fua and Lecler 1990).
2.2 Formulation of Total Energy
Total energy in an image can be defined as sum of internal and external energies (Kass et al 1988). This may be expressed
by a parametric representation of the contour, v(s) = (x(s),y(s)), as
E = / : E(v(s))ds = A 12, (vs) + Ep(v(s)) + Ec(v(s),vo(s))]ds. (D
50
Here the intrinsic or geometric energy E, is derived from the geometric constraints of the object model. Normally E, is
based on the first derivative (v,) and the second derivative (v,,) of the function defined by F, = a|vs(s)|? + Blvss(s)[?,
where a and 5 are constants that control the influence of the geometric energy against the photometric energy. B-splines
are used to model the feature in this implementation. The advantages of the spline are that they are smooth piecewise poly-
nomial which maintain continuity between neighbouring domains. The extrinsic energy comprises photometric energy
E,, that constrains the contour to approach the feature of interest, and control energy F., which constrains the difference
between the contour v (s) and the initial curve vo(s). E,, derived from the image, depends on the type of feature to be
extracted. For a narrow linear feature, it can be the square of intensity values (/(z, y)) of the image, multiplied with a
positive or negative constant (w) for lighter or darker features respectively. ie., Ej; — w|I (x, y)|?. For a step edge, it
can be calculated as, Ej, — — |óI(z, y)|^, thus helping the contour to move towards the image points with high gradient
values while minimising the energy.
In this article, the features in the image are defined by morphological tools for narrow features and the Canny operator
(Canny 1986) for step functions as were used in (Trinder and Li 1995). The energy image is defined by a Chamfer
image, derived from the feature image, in which the pixel values relate to their closeness to any surrounding edge. Letting
Eezt = Ep + E., equation (??) becomes
$81
g- f [œ|vs(s)|? + Blvss(5)|? + Beat (Vs(s)) aJ F(s,v, vs, vss)ds (2)
$0 J 80
The computation requires the minimisation of this energy.
2.3 Energy Minimization Using Simulated Annealing
2.3.1 Basic Principle The feature of interest is first roughly delineated by the operator by control points. The B-spline
will be computed to model this feature. A rectangular window )W is defined in the image from the initial user delineation
in such a way that it includes the feature of interest. The aim of the process is to gradually update the location of the
B-spline, subsequently referred to as modified B-spline, by minimising the energy such that on termination of the process,
it will represent the correct location of the feature of interest. Note that in the SA process, the B-spline and its subsequent
modifications, are obtained by perturbing any one pixel at a time. Thus the total number of pixels in the B-spline or
modified B-spline remain constant.
906 International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000.
