Optimal Local Weighted Averaging Methods in Contour Smoothing.
AbstractIn several applications where binary contours are used to represent and classify patterns, smoothing must be performed to attenuate noise and quantization error. This is often implemented with local weighted averaging of contour point coordinates, because of the simplicity, low-cost and effectiveness of such methods. Invoking the "optimality" of the Gaussian filter, many authors will use Gaussian-derived weights. But generally these filters are not optimal, and there has been little theoretical investigation of local weighted averaging methods per se. This paper focuses on the direct derivation of optimal local weighted averaging methods tailored towards specific computational goals such as the accurate estimation of contour point positions, tangent slopes, or deviation angles. A new and simple digitization noise model is proposed to derive the best set of weights for different window sizes, for each computational task. Estimates of the fraction of the noise actually removed by these optimum weights are also obtained. Finally, the applicability of these findings for arbitrary curvature is verified, by numerically investigating equivalent problems for digital circles of various radii.
Introduction
There are numerous applications involving the processing of 2-D images, and 2-D views
of 3-D images, where binary contours are used to represent and classify patterns of inter-
est. Measurements are then made using the contour information (e.g. perimeter, area,
moments, slopes, curvature, deviation angles etc. To obtain reliable estimates of these
quantities, one must take into account the noisy nature of binary contours due to discrete
sampling, binarization, and possibly the inherent fuzziness of the boundaries themselves 1 .
In some cases, this can be done explicitly and exhaustively (see Worring & Smeulders [1]
on curvature estimation). But more frequently it is done implicitly by smoothing. Following
this operation, the measurements of interest can be obtained directly from the
smoothed contour points, as in this paper, or from a curve fitted to these points. For a
recent example of this last approach, see Tsai & Chen [2].
The smoothing of binary contours or curves for local feature extraction directly from
1 For example, the "borders" of strokes in handwriting.
the discrete data is the focus of this article. More precisely, we will investigate optimum
local weighted averaging methods for particular measurement purposes such as estimating
point positions, derivatives (slopes of tangents), and deviation angles from point to point
(see Fig. 2).
In this article, the following definitions will be used. Let
be the sequence of N points (4- or 8-connected) around the closed contour. Since the
contour is cyclic,
be the counter-clockwise elevation angle between v i and the horizontal x-axis. We have
4 where c i is the Freeman [3] chain code (see Fig. 1). For 4-connectivity, the
values of c i are limited to even values. We also define d i , the differential chain code, as
\Gamma'@
@
@
@I
oe
\Gamma\Psi
@
@
@

Figure

1: Freeman chain code
\Gamma\Psit

Figure

2: Deviation angle at p i
The deviation angle at point p i will be denoted OE i . It is the angle between the small
vectors v i and v i+1 (See Fig. 2). Of course we have OE
4 .
Finally, the local weighted averaging method investigated in sections II, III, and IV is
defined as:
j=\Gamman
i is the contour point i after k smoothing steps (p (0)
The window size is
A. Variety of Approaches Used in Applications
Due to limited computing power, early methods were quite simple and found justification
in their "good results". Thus we find schemes removing/filling one-pixel wide
protrusions/intrusions based on templates, or replacing certain pairs in the chain code
sequence by other pairs or by singletons ([4]). However, from early on, local weighted averaging
methods are the most frequently used. They are applied to differential chain codes
([5], [6], [7]), possibly with compensation for the anisotropy of the square grid ([8]); they
are applied to cartesian coordinates ([9]), possibly with weights depending on neighboring
pixel configuration ([10]) or varying with successive iterations ([11]); they are applied to
deviation angles ([12]).
With advances in computing power and insight into the smoothing problem, more complex
methods were developed with more solid theoretical foundations. In this process,
"Gaussian smoothing" has become very popular. One approach consists of applying local
weighted averaging with Gaussian weights. Dill et al. [13] use normalized Gaussian-
smoothed differential chain codes with fixed oe and window size. In Ansari & Huang [14],
the weights and window size may vary from point to point based on
e
region of support. See also Pei
Variable amounts of smoothing can be applied to the entire curve, taking the overall
behaviour of the smoothed curve across scale as its complete description. Witkin [17]
convolves a signal f(x) with Gaussian masks over a continuum of sizes:
2-oe
F (x; oe) is called the scale-space image of f(x) and it is analyzed in terms of its inflection
points. This concept of scale-space was also originally explored by Koenderink [18].
Asada & Brady [19] analyze the convolution of simple shape primitives with the first
and second derivatives of G(x; oe) and then use the knowledge gained to extract these
shape primitives from the contours of objects. Mokhtarian & Mackworth [20] compute
November 20, 1997
the Gaussian-smoothed curvature using
Y (t; oe) -
where X(t; oe) and Y (t; oe) are the coordinates (x(t),y(t)) convolved with a Gaussian filter
G(t; oe). The locus of points where -(t; is called the generalized scale-space image
of the curve which they use for image matching purposes. Wuescher & Boyer [21] also use
Gaussian-smoothed curvature but with a single oe to extract regions of constant curvature
from contours.
Multiscale shape representations are not necessarily associated with Gaussian smoothing.
Saint-Marc et al. [22] propose scale-space representations based on adaptive smoothing,
which is a local weighted averaging method where the smoothed signal S (k+1) (x) after
smoothing steps is obtained as:
\Gamma(x)X
Several multiscale shape representations based on non-linear filters have also been used
successfully. Maragos [23] investigated morphological opening/closing filters depending
on a structuring element and a scale parameter; using successive applications of these
operators and removing some redundancy, a collection of skeleton components (Reduced
Skeleton Transform) can be generated which represents the original shape at various scales
more compactly than multiscale filtered versions. See also Chen & Yan [24].
Recently Bangham et al. [25] used scale-space representations based on M - and N -
sieves. For any 1D discrete signal f denoting as C r the set of all intervals of r
consecutive integers, they define:
Using the N-sieves of f are the sequence: f
1. The M-sieves of f are defined similarly, using M. Applying sieves horizontally and
vertically to 2D images appears to preserve edges and reject impulsive noise better than
Gaussian smoothing.
B. Theoretical Foundations
Regularization theory and the study of scale-space kernels are the two main areas which
have provided insight into the special qualities of the Gaussian kernel for smoothing pur-
poses. As will be seen, they do not warrant unqualified statements about the 'optimality'
of Gaussian smoothing.
Consider a one-dimensional function g(x), corrupted by noise j(x). The observed signal
is then Assume that the information available is a sampling of this
signal obtained for One approach to
estimating g(x) is to find f(x) which minimizesn
Z xn
where - is the regularization parameter. The solution is a smoothing spline of order 2m
(see [26], [27]).
For equally spaced data and et al. [28] have shown that the cubic spline
solution is very similar to a Gaussian. Canny's paper on edge detection[29] is also cited to
support the optimality of Gaussian filtering. But the Gaussian is only an approximation
to his theoretically obtained optimal filter.
Babaud et al. [30] have considered the class of infinitely differentiable kernels g(x; y)
vanishing at infinity faster than any inverse of polynomial, and one-dimensional signals
f(x) that are continuous linear functionals on the space of these kernels. In this class,
they have shown that only the Gaussian g(x;
can guarantee that all
first-order maxima (or minima) of the convolution
will increase (or decrease) monotonically as y increases.
Yuille & Poggio [31] extended the previous result by showing that, in any dimension,
the Gaussian is the only linear filter that does not create generic zero crossings of the
Laplacian as the scale increases. In the literature, such demonstrations are often designated
as the scaling theorem. Mackworth & Mokhtarian [32] derived a similar result concerning
their curvature scale-space representation. Wu & Xie [33] developed an elementary proof
of the scaling theorem based on calculus, assuming signals represented by polynomials.
Very recently, Anh et al. [34] provided another proof applicable to the broader class of
band-limited signals and to a larger class of filtering kernels, by relaxing the smoothness
constraint.
This property of the Gaussian filter was established for continuous signals. Lindeberg [35]
has studied the similar problem for discrete signals. He postulated that scale-space should
be generated by convolution with a one-parameter family of kernels and that the number
of local extrema in the convolved signal K   f should not exceed the number of local
extrema in the original signal. Imposing a semigroup requirement, he found the unique
one-parameter family of scale-space kernels T (n; t) with a continuous scale parameter t;
as t increases, it becomes less and less distinguishable from the discretized Gaussian.
Recently, Pauwels et al. [36] demonstrated that imposing recursivity and scale-invariance
on linear, isotropic, convolution filters narrows down the class of scale-space kernels to a
one-parameter family of filters but is not restrictive enough to single out the Gaussian. The
latter results for a parameter value of 2; for higher values, the kernel has zero crossings.
Pauwels et al. also derive Lindeberg's results as special cases of theirs.
Finally, Bangham et al. [25] showed that discrete 1D M-sieves and N-sieves do not
introduce new edges or create new extrema as the scale increases. In addition, Bangham
et al. [37] have proven that when differences are taken between sieving operations applied
recursively with increasing scale on 1D discrete signals, a set of granule functions are
obtained which map back to the original signal. Furthermore, the amplitudes of the
granules are, to a certain extent, independent of one another.
C. Practical Considerations
For practical applications, regardless of the smoothing method one decides to use, some
concrete questions must eventually be answered. For the regularization approach, what
November 20, 1997
value should be used for -? For Gaussian smoothing, what value of oe and what finite
window size? When scale-space representation is used, if we say that significant features
are those which survive over "a wide range of scale", we must eventually put some actual
figures on this 'wide' range. These decisions can be entirely data-driven or based on
prior experience, knowledge of particular applications etc. In the end, they may play a
significant role in both the performance of the selected method and its implementation
cost. We now briefly present some of these aspects.
In [38] [39], Shahraray & Anderson consider the regularization problem of equation 8,
4, and they argue that finding the best value of - is critical. For this purpose,
they propose a technique based on minimizing the cross-validation mean square error
(g [k]
where g [k]
n;- is the smoothing spline constructed using all samples except y k , and is then
used to estimate y k . The method is said to provide a very good estimate of the best -,
for equally-spaced periodic data assuming only a global minimum. Otherwise, a so-called
generalized cross-validation function must be used.
The presence of discontinuities to be preserved in the contours of interest brings more
complexity into the optimal smoothing problem. One possible solution was already men-
tioned: the adaptive smoothing of Saint-Marc et al. [22]. For one-dimensional regularization
which preserves discontinuities, see Lee & Pavlidis [40]. For two-dimensional regularization
which preserves discontinuities, see Chen & Chin [41]. For Gaussian smoothing
which preserves discontinuities, see the methods of Ansari & Huang [14] and of Brady et
al. [42].
Another problem is that repeated convolution of a closed curve with a kernel may not
yield a closed contour or may cause shrinkage. For simple, convex, closed curves, Horn &
Weldon [43] propose a new curve representation which guarantees closed curves. Mackworth
Mokhtarian [32] offer a different solution involving the reparametrization of the
Gaussian-smoothed curve by its normalized arc length parameter. Lowe [44] attenuates
shrinking by adding a correction to the Gaussian-smoothed curve. Oliensis [45] applies
FFT to the signal and resets amplitudes to 0 only for frequencies larger than some thresh-
9old. Recently, Wheeler & Ikeuchi [46] present a new low-pass filter based on the idea
of iteratively adding smoothed residuals to the smoothed signals. Results are said to be
comparable to Oliensis' and somewhat better than Lowe's.
possible solution to the high computation and storage
requirements of generating "continuous" scale-space. They show that an optimal L 1 approximation
of the Gaussian can be obtained with a finite number of basis Gaussian filters:
from which scale-space can be constructed efficiently.
The above discussion exemplifies the potential complexity involved in implementing
methods. Clearly, in practice, one should not lose track of the cost of these
operations and how much smoothing is really required by the application of interest. It
is not always necessary to attain the ultimate precision in every measurement. In many
situations, simple and fast methods such as local weighted averaging with fixed weights
and a small window size, will provide a very satisfactory solution in only 2 or 3 iterations
(see [11], [5], [12]). Moreover, there is often little difference in the results obtained via
different methods. Thus, Dill et al. [13] report similar results when a Gaussian filter and
a triangular (Gallus-Neurath) filter of the same width are applied to differential chain
codes; in Kasvand & Otsu [48], rectangular, triangular, and Gaussian kernels, with the
same standard deviation, yield comparable outcomes (especially the latter two) for the
smooth reconstruction of planar curves from piecewise linear approximations.
D. Present Work
Our interest in contour smoothing stems from practical work in handwriting recognition.
In this and other applications, the discrimination of meaningful information from 'noise'
is a complex problem which often plays a critical role in the overall success of the system.
This filtering process can be handled across several stages (preprocessing, feature extrac-
tion, even classification), with different methods. In the preprocessing stage of one of our
recognition schemes [49], a triangular filter with first applied to contours of
characters before deviation angles OE i were computed. Satisfactory results were obtained.
Nevertheless, we were curious about the optimality of our choice of local weights.
Initial review revealed that, in many practical applications, the smoothing operation
is still performed by some local weighted averaging schemes 2 because they are simple,
fast, and effective (see for example [14], [50], [51], [52], [21]). However, little theoretical
investigation of these methods per se has been conducted. Some authors rapidly invoke the
'optimality' of Gaussian filtering and use Gaussian-derived weights. Their results may be
satisfactory as the Gaussian may be a good approximation to the 'optimum' filter, but its
discretization and truncation may cause it to further depart from 'optimum' behaviour.
In this paper, we assume local weighted averaging with constant weights as a starting
point and we investigate how these smoothing methods handle small random noise. To
this end, we propose a simple model of a noisy horizontal border. The simplicity of
the model allows a very pointed analysis of these smoothing methods. More precisely,
for specific computational goals such as estimating contour point positions, derivatives
(slopes of tangents), or deviation angles from the pixels of binary contours, we answer the
following questions: what are the optimum fixed weights for a given window size? and
what fraction of the noise is actually removed by these optimum weights?
After deriving these results, we offer experimental evidence that their validity is not
restricted to the limited case of noisy horizontal borders. This is done by considering digital
circles. For each particular computational task, we find very close agreement between the
optimum weights derived from our simple model and the ones derived numerically for
circles over a wide range of radii.
An important side-result concerns the great caution which should be exercised in speaking
of 'optimal' smoothing. Even for our simple idealized model, we find that the smoothing
coefficients which best restore the original noise-free pixel positions are not the same
which best restore the original local slope, or the original local deviation angles; further-
more, the best smoothing coefficients even depend on the specific difference method used
to numerically estimate the slope. Hence, in choosing smoothing methods, researchers
should probably first consider what it is they intend to measure after smoothing and in
what manner.
In relation to this, we point out the work of Worring & Smeulders [1]. They analyze
2 Once the Gaussian is discretized and truncated, it also simply amounts to a local weighted averaging method
with particular weight values.
noise-free digitized circular arcs and exhaustively characterize all centers and radii which
yield a given digitization pattern; by averaging over all these, an optimum measure of
radius or curvature can be obtained. If radius or curvature is the measurement of interest
and if utmost precision is required (with the associated computing cost to be paid), then
their approach is most suitable.
Our work in contrast is not oriented towards measuring a single attribute. We focus
on measurements such as position, slope and deviation angles because they are often of
interest. But our model and approach can be used to investigate other quantities or other
numerical estimates of the same quantities. The methods may be less accurate but they
will be much less costly, and optimum in the category of local weighted averaging methods.
The requirements of specific applications should dictate what is the best trade-off.
The rest of the article is organized as follows. The next section briefly describes the
methods investigated and provides a geometric interpretation for them. In section III, the
simple model of a noisy horizontal border is used to derive optimal values of the smoothing
parameters, in view of the above-mentioned computational goals. Finally, the applicability
of our findings for varying curvature is explored experimentally in section IV.
II. Local Weighted Averaging
We begin our study of local weighted averaging, as defined by Eq. 1, with window size
course, the smoothed contour points p (k)
smoothing iterations,
can be obtained directly from the original points p i as
j=\Gamman 0
corresponding to a window size w 1, and the fi's are
functions of the ff's and of k. The form of Eq. 1 is often computationnally more convenient.
However, as long as k and n are finite, the study of local weighted averaging need only
consider the case of a single iteration with finite width filters. When this is done, we will
use the simpler notation p 0
i instead of p (1)
We now impose a simple requirement to this large family of methods. Since our goal
is to smooth the small 'wiggles' along boundaries of binary images, it seems reasonable
to require that when p i and its neighbouring contour pixels are perfectly aligned, the
November 20, 1997
smoothing operation should leave p i unchanged. In particular, consider the x-coordinates
of consecutive horizontally-aligned pixels from p i\Gamman to p i+n . For
Our requirement that x 0
j=\Gamman
j=\Gamman
For this to hold whatever the value of x i , we must have
j=\Gamman
Thus our requirement is equivalent to a normalization condition and a symmetry constraint
on the ff's.
A. Geometric Interpretation
It is a simple matter to find a geometric interpretation for local weighted averaging.
Using the above conditions, Eq. 1 can be rewritten as:
Fig. 3. Geometric interpretation for
For a single iteration of the simplest method 1), the last Eq. reduces to
The points p are generally not aligned and the situation is illustrated in
Fig. 3, where m is the middle of the base of the triangle. Eq.
implies that the smoothed point
i is always on the median of the triangle from point p i .
Furthermore, the effect of the unique coefficient ff is clear since jp i p 0
As
ff varies continuously from 0 to 0.5, p 0
i 'slides' from p i to m i1 .
Similarly, in the more general situation, the vectors [ p (k\Gamma1)
are the medians
from p (k\Gamma1)
i of the triangles \Deltap (k\Gamma1)
i+j . Eq. 15 indicates that the smoothed
point
i is obtained by adding to p (k\Gamma1)
i a weighted sum of the medians of these triangles,
using 2ff j as weights. Thus, in a geometric sense, local weighted averaging as a contour
smoothing method could be renamed median smoothing.
III. Optimum Results from a Simple Digitization Noise Model
This section addresses the question "If local weighted averaging is considered, what
constant coefficients ff j should be used for smoothing binary contours in view of specific
computational goals?". We develop an answer to this question, based on a simple model:
an infinite horizontal border with random 1-pixel noise.
Why use this model? Of course, we do not consider the horizontal line to be a very
general object. Nor do we think that noise on any particular binary contour is a random
phenomenom. We have noticed in our work that binary contours often bear small noise,
commonly "1-pixel wiggles". Our goal is to perform an analytical study of the ability of
local weighted averaging smoothing methods to remove such noise. Since the filters are
meant to be used with arbitrary binary contours, it seems reasonable to consider that over
a large set of images noise can be considered random.
Furthermore, we do not make the very frequent implicit assumption that a smoothing
filter can be optimal independently of the specific attributes one intends to measure or
even the specific numerical estimation method used. For specific measurements and computation
methods, we would like to find the best choice of smoothing coefficients for a
given window size and an estimate of how much noise these coefficients remove; if the window
size is increased 3 , what are then the best coefficients and how much more is gained
compared to the smaller window size?
These questions are very pointed and we have no workable expression for small random
3 assuming the feature structure scale allows this.
noise on an arbitrary binary contour which would allow to derive answers analytically. Thus
we choose to look at an ideal object for which we can easily model random 1-pixel noise
and our study can be carried out. Similar approaches are often followed. For example,
in studying optimal edge detectors, Canny [29] considers the ideal step edge. There is
no implication that this is a common object to detect in practice; simply it makes the
analytical investigation easier and can still allow to gain insight into the edge detection
problem more generally. The practicality of our own findings concerning optimal local
weighted averaging will be verified in section IV. We now give a definition for our simple
model.
The infinite horizontal border with random 1-pixel noise consists of all points
Z, satisfying
with probability
with probability p
An example of such a simple noisy boundary is shown in Fig. 4.
y
Fig. 4. Noisy Horizontal Border
With this model, x It then follows from Eq. 15 that the
smoothing operation will not change the x-coordinates and the local weighted averaging
will only affect the y-coordinates. The best fitting straight line through this initial data is
easy to obtain since it must be of the form y. It is obtained by minimizing the mean
square distance
with respect to ~
y. The best fitting line is simply We will consider this to be
the Eq. of the ideal border which has been corrupted by the digitization process, yielding
the situation of Eq. 18.
We now examine the problem of applying "optimal" local weighted averaging to the
data of our simple model. Our aim is to eliminate the 'wiggles' along the noisy horizontal
border as much as possible. An alternate formulation is that we would want the border,
after smoothing, to be "as straight as possible" and as close as possible to
Several criteria can be used to assess the straightness of the border and optimize the
smoothing process:
ffl Minimize the mean square distance to the best fitting line after the data has been
smoothed.
ffl Minimize the mean square slope along the smoothed data points (ideally, the border
is straight and its slope should be 0 everywhere).
ffl Minimize the mean square deviation angle OE i (see Fig. 2) along the smoothed data
(ideally, OE i should also be 0 everywhere).
Each of the above criteria is sound and none can be said to be the best without considering
the particular situation further. The first criterion is the most commonly used in the curve
fitting literature. In this paper however, we want to derive optimal smoothing methods
tailored for specific computational tasks; hence, we will consider each of the above criteria
in turn. If our interest is simply to obtain numerical estimates of the slopes at contour
points, the optimal ff j 's derived based on the second criterion should be preferred. And
for estimating deviation angles OE i , the optimal coefficients derived from the third criterion
would be better.
For the first criterion, we will use d rms , the root mean square (r.m.s.) distance to the
best fitting line, as our measure of noise before and after the smoothing step; for the
second criterion, m rms , the r.m.s. slope along the border; with the third criterion, OE rms ,
the r.m.s. deviation angle along the border. For the original unsmoothed data, these noise
measures can be computed using the probabilities of the possible configurations of 2 or 3
consecutive pixels. Thus for the original, unsmoothed data we have:
r
using
Based on our simple model, we now derive the best smoothing parameters for each of
the three criteria mentioned above. Once obtained, we will compute the corresponding
noise measures for the smoothed data which we will denote by [w] d 0
rms
rms ; and [w] OE 0
rms
respectively. In this notation the 'prime' indicates a single smoothing step and w is the
window size used.
A. Best Parameters to Minimize d 0
rms
The unsmoothed y-coordinate of our border points is a discrete random variable following
a simple Bernouilli distribution for which the expected value is y and the variance
is Obviously, the best fitting line is simply the expected value and d rms in Eq.
20 is the standard deviation of y i . After smoothing, the expected value of y 0
(finite) window size w. Denoting the expected value by E, we have from
elementary probability theory:
E(y 0
E(
j=\Gamman
j=\Gamman
j=\Gamman
Now we find the best choice of smoothing parameters and the corresponding noise measure
rms . Denoting variance by oe 2 (), we have:
j=\Gamman
Each ff j y i+j is a discrete random variable (with two possible values) and its variance is
. Thus
j=\Gamman
We must now minimize
j=\Gamman
subject to the constraint ff
problem is typically solved using the Lagrange multipliers method (see [53], page 182).
from which we obtain the simple result ff for each k. All coefficients are equal,
hence of value 1=(2n+1) 4 . Substituting this value into Eq. 25, we obtain the corresponding
4 As expected, straight averaging reduces the variance of a collection of random variables faster than any other
weighted average.
2 . Our findings can be summarized as follows:
ffl For a single smoothing iteration with arbitrary window size w, for any value of p, the
best choice of parameters to minimize the mean square distance is to set all ff j 's to
1=w, resulting in [w] d 0
s
The fraction of the noise which is removed by the smoothing operation is
sw
Hence, for the noise is reduced by 42:3%; for by 55:3%; for
62:2%. Finally, contrary to what one might expect, we note that the optimum 5-point
smoothing operation is not to apply the optimum 3-point operation twice. The latter is
equivalent to a 5-point window with ff which gives d 0
This would remove approximately 51.6% of the noise.
B. Best Parameters to Minimize m 0
rms
In this section, we apply our second criterion for straightness and minimize the root mean
square value of the slope after smoothing. We consider two different ways of computing
the slope from contour points.
B.1 Based on m 0
The simplest numerical estimate of the slope is given by the forward difference formula
i . This gives
j=\Gamman
\Gamman y i\Gamman
ff \Gamman
Expanding the last squared summation and taking the mean, we obtain the following
\Gamman ff n y i+1+n y i\Gamman
\Gamman y 2
i\Gamman
November 20, 1997
ff \Gamman
\Gamman+1
For any s; t 2 Z; y s y
Substituting these
results, Eq. 27 can be further simplified by making use of Eq. 14. We obtain:
j=\Gamman
Using Eq. 14 again, some algebraic manipulation leads to an expression for
involving
only the n independent parameters ff
Our task now is to minimize the mean squared slope. Differentiating this with respect to
a system of n linear equations as shown below.B
ff 6
ff
Solutions are given in Table I for 1 - n - 6. The column before last gives the fraction of
the noise which is removed by the optimum smoothing method. For comparison purposes,
the last column provides the equivalent result when all weights are set equal to 1
w . Finally
we note that for window size 5, the triangular filter using ff results in
a noise reduction of 80.8%, slightly better than the equal-weights method.
fraction of noise removed
B.2 Based on m 0
A more accurate 5 estimate of the slope is given by m 0
Expanding it
in terms of the original coordinates and following the same approach as in the preceding
section, we arrive at:
j=\Gamman
When expressed in terms of the n independent ff's, this becomes:
Minimizing with respect to ff k , for 1 - k - n, we obtain another set of n linear equations
for which the solutions are listed in Table II for 1 - n - 6.
Note that the distribution of coefficients from ff \Gamman to ff n is no longer unimodal. Fur-
thermore, values of n. Finally we note that for window size w = 5, the
5 Provided the data resolution is fine enough.
and fraction of noise removed
triangular filter using ff results in a noise reduction of 66.7%, notably less
than the equal-weights method.
Parameters to Minimize Deviation Angles
In this section, we examine the smoothing problem based on minimizing the deviation
angles OE 0
. Here the problem is more complex and we will not obtain general expressions of
the optimum smoothing parameters which are independant of the probability p involved
in our model. We restrict our study to the cases 5.
Our definitions of section I imply that OE 0
. From trigonometry, we have
tan OE 0
Now tan ' 0
. Thus we can obtain tan OE 0
i from the
smoothed coordinates and then OE 0
i from the value of the tangent.
C.1 For
For
i at p 0
will depend on the original contour points in a 5-point neighbourhood
around p i . For our model of Eq. 18, there are 2 possible configurations for such
a neighbourhood, which must be examined for their corresponding OE 0
. Of course, these
November 20, 1997
computations need not be performed manually; they can be carried out using a language
for symbolic mathematical calculation.
Adding together the contributions from the 32 possible configurations, weighted by
the respective probabilities of these configurations, results in the following expression for
For simplicity we have dropped the subscript on the unique parameter ff 1 . Numerical
optimization was performed to find the value of ff which minimizes Eq. 34. No single
value of ff will minimize tan 2 OE 0
i for all values of p. The results are shown in Fig. 5(a).
The best value of ff is now a smooth function of p. However we note that the domain of
variation is very little.
We cannot compare the results obtained minimizing the mean squared tangent of OE 0
to the situation without smoothing, since tan 2 OE i is infinite. By taking the arc tangent
function of Eq. 33, we can obtain the values of the angles OE 0
themselves and we can derive
an expression for OE 0
2 in the same manner. Numerical optimization of this expression yields
the results shown in Fig. 5(b). As can be seen, they are almost the same as those of Fig.
5(a). In a similar fashion, we can generate expressions for j tan OE 0
i j, for which the
best smoothing parameters are shown in Fig. 5(c) and 5(d) respectively. Here there seems
to be one predominant best parameter over a wide range of values for p.
All the results shown in Fig. 5 were obtained numerically, for values of p ranging from
to 0.995, in steps of 0.005. As expected, all these curves are symmetric about
so we will limit our discussion to p ! 0:5. In Fig. 5(c), the best value of ff for
0:495), the best value is
Between these two intervals, p increases almost linearly. In Fig. 5(d), the same values of
ff are found: 0:25 is the best choice for 0:2857 is the best
choice for p 2 (0:150; 0:495).
In Fig. 5(a) and 5(b), the best value of ff is a smoothly varying function of p. But we
notice that 0:2857 is an intermediate value of ff in the narrow range of best values.
In fact, choosing all values of p, the value of tan 2 OE 0
i is always within 0.2%
of the minimum possible.
Despite the differences in the actual curves of Fig. 5, the corresponding ranges of best
ff's are always quite narrow and very similar, independently of the exact criterion chosen.
From now on, to maintain uniformity with the treatment of sections III-A and III-B, we
will restrict ourselves to minimizing the mean squared angle.
Eq. 22 provided a measure of the noise before smoothing: OE rms = -q
. The
fraction of this noise (1 \Gamma OE 0
rms =OE rms ) which is removed by a simple smoothing operation
with computed for different values of ff. The results are displayed in Fig. 6.
The solid line represents the best case and we see that approximately 73% of the r.m.s.
noise is removed. The dashed line, representing the case where ff = 0:2857 is used for all
values of p, is not distinguishable from the best case at this scale. The dash-dotted and the
dotted lines represent the fraction of noise removed for
In this last case, this fraction is a constant equal to 0.6655.
C.2 For
For possible configurations of a 7-point neighbourhood centered on p 0
must be considered to obtain the values of OE 0
after smoothing. In Eq. 34, there were 9
distinct terms involving p and ff. Now the computation of tan 2 OE 0
results in 35 distinct
terms in p, ff 1 , and ff 2 . We will not reproduce this lengthy expression here.
Fig. 7(a) presents the best choice of parameters to minimize OE 0
2 . We notice that there is
very little variation in their values over the range of values of p. The optimum parameters
are approximately ff These values are close to 2
9 and 1
9 , the
values for the triangular 5-point filter. Fig. 7(b) shows the fraction of OE rms removed by the
smoothing operation. The solid line represents the case where the optimum parameters are
used for each value of p. In this situation, approximately 88:75% of the noise is removed.
The dashed line represents the case ff
9 and ff
9 , for which 86% of the noise is
removed approximately. We see that these results are close to the ideal situation.
IV. Verifying Results for Varying Curvature
In the preceding section, we have studied optimum local weighted averaging extensively,
based on a model of a horizontal border with random 1-pixel noise. Particular solutions
were derived based on error criteria chosen in light of specific computational tasks to be
performed after the smoothing operation. But can these results be relied upon to handle
digitization noise along arbitrary contours?
Our results were obtained for a straight, horizontal border, i.e. a line of curvature 0.
But for arbitrary contours, curvature may vary from point to point. Should optimum
smoothing parameters vary with curvature and, if so, in what manner? For a given
window size, can a fixed set of smoothing parameters be found which will give optimum
(or near optimum) results across a wide range of curvature values? If so, how does this
set of parameters compare with the one we have derived using our simple model?
In this section, we try to answer these above questions by performing some experiments
with digital circles. It should be clear that our interest is not with digital circles per se
but rather, as explained above, with the variation of optimum smoothing parameters with
curvature. The approach will be to examine, for digital circles of various radii, situations
which are equivalent to the ones studied for the horizontal straight border in sections III-A,
III-B, and III-C. Using numerical optimization, we will find the best choice of smoothing
parameters for each situation, over a wide range of curvature values, and compare them
with the values obtained previously. An example of a digital circle is shown in Fig. 8 for
a radius R = 7.
A. Minimizing Error on Distances to Center
In this section, we consider the distances d i from the center to each pixel P i as approximations
to the radius R. See Fig. 9(a). After smoothing, pixel P i is replaced by pixel P 0
which is at a distance d 0
i from the center of the circle. Our aim is to find the values of the
smoothing parameters, for
these parameters might vary depending on the radius of the circles.
For reasons of symmetry, it is only necessary to consider one quadrant; with special
attention to the main diagonal, we can restrict our attention to the first octant of each
November 20, 1997
circle. Let N 1=8 be the number of pixels which are strictly within the first octant. The
mean value of (R \Gamma d 0
obtained by adding twice the sum of (R \Gamma d 0
points, plus the value for the pixel at coordinates (R; 0), plus the value for the pixel on
the main diagonal (if present). This sum is then divided by 2N 1=8
there is a pixel on the main diagonal).
We now give a simple example, for 3. First we consider the situation
before any smoothing is applied. For the point on the x-axis, the value of (R \Gamma d 0 ) 2 is
always 0. For the next point (4; 1), (R \Gamma d 1
. For the next point (3; 2),
(R
. Finally, for the point on the main diagonal (3; 3), (R \Gamma d 3
. The contributions for points (4; 1) and (3; 2) are counted twice and added to
the contributions for the diagonal point (3; 3). This sum is then divided by 6. Taking the
square root of the result, we obtain (R
After smoothing with the smallest window size, we have the following values for
(R
(R
(R
(R
and we must minimize the expression 1i
. Thus the
best smoothing parameter for is found to be
In the numerical computations it is possible to take advantage of the fact that, for small
window sizes, the smoothing rarely affects the y-coordinates in the first octant; exceptions
occur occasionally for the last pixel in the first octant (not on the diagonal) and for the
pixel on the diagonal when the preceding pixel has the same x-coordinate. This last
condition is found only for radii values of 1, 4, 11, 134, 373, 4552 etc. (see Kulpa [54]).
The coordinates of the pixels for the first octant of the digital circles were generated
using the simple procedure presented in Horn [55], with a small correction pointed out by
Kulpa [56] (see also Doros [57]). The best smoothing parameters were obtained for integer
values ranging from 2 pixels to 99 pixels, in steps of 1. The results are presented in
November 20, 1997
Fig. 9(b) for 5. For comparison, the values derived in section
III-A from our model of a noisy horizontal edge are shown with dashed lines.
For we see that for radii values larger than 20 pixels the best ff \Sigma1 oscillates around3
, as derived from our model. Similarly, for 5, the best values of ff \Sigma1 and ff \Sigma2 are
close to the predicted value of 0:2. For small radii values however, the optimum ff \Sigma2 -values
are much lower than this value and the optimum ff \Sigma1 -values are correspondingly higher.
This is easily understood since a 5-pixel neighbourhood covers a relatively large portion
of the circumference in these cases (as much as one eighth of the total circumference for a
radius of 6 pixels, one fourth for a radius of 3 pixels). In fact, for radii values of 2, 3, 4,
6, and 8 pixels, it is best to use ff using only the nearest neighbour.
Fig. 9(d) compares the r.m.s. values of the errors on the radii without smoothing (solid
line) to the best values possible after smoothing with window sizes of (dashed line)
and (dotted line) respectively.
For each value of the radius, we have also compared the noise reduction achieved using
the optimum parameters to that achieved with the constant values 1and 1. The results
are presented in Fig. 10(a) and 10(b), for respectively. For the
2 curves are indistinguishable for R ? pixels, and they are very close for R - 10. For
smoothing with ff actually
worse than no smoothing at all. But, for R ? 18, the best curve and that obtained with
these fixed values are very close.
Finally, for compares the
mean noise reduction of 3 methods: the optimum method, corresponding to the variable
parameters of Fig. 9(b) and Fig. 9(c); the fixed parameter method derived from our model
of section III; and the best fixed parameter method obtained from numerical estimates.
We see that the results are very close and that the method derived from our simple noise
model compares very well with the numerically determined best fixed parameter method.
B. Minimizing Error on Tangent Directions
In this section, we compare the direction of the tangent to a circle at a given point
to the numerical estimate of that direction, obtained for digital circles. The situation is
November 20, 1997
Window Method ff \Sigma1 ff \Sigma2 Mean noise reduction
optimum variable 0.484317
best fixed 0.3329 0.482673
optimum variable variable 0.6184
best fixed 0.2148 0.1703 0.6117


III
Mean noise reduction for
illustrated in Fig. 11(a).
Since the slope of the tangent is infinite at pixel (R; 0) of the digital circle, we will
consider instead the angle which the tangent line makes with the x-axis. The radius
from the center of the circle to pixel P i makes an angle ' i with the positive x-axis. Now
consider the point where this radius intersects the continuous circle. Theoretically, the
angle between the tangent to the circle at that point and the x-axis is -
On the
other hand, the numerical estimate of this angle is given by -
is the angle
between the horizontal axis and the perpendicular bisector of the segment from P i\Gamma1 to
Fig. 11(a)). The difference between these angles, (' is the error on the
elevation of the tangent to the circle at the point of interest. Our goal is to minimize the
r.m.s. value of (' 0
primes refer to the quantities after smoothing.
The values of ' i and ' i are readily computed in terms of the original coordinates of the
digital circle as follows:
The values of ' 0
are obtained similarly, in terms of the coordinates after smoothing.
Once again, the r.m.s. error for the entire circle can be computed by considering only
the first octant; and the best smoothing parameters were obtained for integer radii values
ranging from 4 pixels to 99 pixels, in steps of 1. The results are presented respectively in
Fig. 11(b) for 5.
In section III-B.2, for the optimum value derived for ff
5, the
optimum values derived for ff \Sigma1 and ff \Sigma2 were 1and 3respectively. These values are shown
with horizontal dashed lines in Fig. 11(b) and 11(c). The best smoothing parameters vary
with the values of R. However, when we compute their means for 4 - R - 99, the results
obtained are very close to the predicted values. Thus, for (compared
to 0.4); for (compared to 0.1429) and ff (compared to
0.2143).
Fig. 11(d) compares the r.m.s. values of the errors on the elevation of the tangents to
a circle without smoothing (solid line) to the best values possible after smoothing with
window sizes (dashed line) and (dotted line).
The noise reduction produced by smoothing is equal to 1:0 \Gamma (' 0
. For each
value of the radius, we have compared the noise reduction achieved using the optimum
parameters to that achieved with the constant values ff
5 , for 5. The results are presented in Fig. 12(a) and 12(b) respectively.
As can be seen, the constant values predicted by our simple model yield noise reduction
results which are very close to optimum.
Finally, for 4 - R - 99 and window sizes
the mean noise reduction of 3 methods as explained previously. The best smoothing
parameters derived from our simple noise model and the numerically determined best
fixed parameters are almost the same and their performance is nearly optimal.
C. Minimizing Error on Deviation Angles
In this section, we compare the deviation angles along the circumference of a circle to
the numerical estimates obtained for digital circles. The situation is illustrated in Fig.
13(a).
Consider 3 consecutive pixels P on the circumference of a digital circle.
The deviation angle at P i is denoted by OE i . Now the line segments from the center of the
circle to these 3 pixels (partly represented by dashed lines in the figure) have elevation
angles of ' respectively. The intersection of these line segments with the
circle are the true circle points Q elevations. Connecting these
November 20, 1997
Window Method ff \Sigma1 ff \Sigma2 Mean noise reduction
optimum variable 0.58084
best fixed 0.4026 0.57478
optimum variable variable 0.7658
14 0.7572
best fixed 0.1445 0.2088 0.7576


IV
Mean noise reduction for 4 - R - 99
points by line segments defines a deviation angle ffi i at Q i , for which OE i is a numerical
estimate.
The difference between ffi i and OE i is the error on the deviation angle at the point of
interest. Our goal in this section is to find the optimum parameters which will minimize
the r.m.s. value of this error, after smoothing.
In terms of the pixel coordinates deviation angle OE i is equal to
To compute ffi i , we first obtain the elevation angles as ' then the
coordinates of the circle points Q i as
Finally, ffi i is computed as in Eq. 37, using (~x; ~
y) instead of (x; y).
The best smoothing parameters were obtained for integer radii ranging from 4 pixels to
pixels, in steps of 1. The results are presented in Fig. 13(b) for
5.
In section III-C, for the optimum value derived for ff \Sigma1 was 0.2857; for 5, the
optimum values derived for ff \Sigma1 and ff \Sigma2 were 0.2381 and 0.1189 respectively. These values
are shown with dashed lines in Fig. 13(b) and 13(c). Again, the best smoothing parameters
vary with the values of R. However, when we compute their means for 4 - R - 99, the
November 20, 1997
results obtained are very close to the predicted values. Thus, for
Fig. 13(d) compares the r.m.s. values of the errors on the deviation angles without
smoothing (solid line) to the best values possible after smoothing with window sizes
(dashed line) and (dotted line).
The noise reduction produced by smoothing is equal to 1:0 \Gamma (ffi 0
. For each
value of the radius, we have compared the noise reduction achieved using the optimum
parameters to that achieved with the constant values ff
5. The results are presented in Fig. 14(a) and 14(b)
respectively.
As can be seen, the constant values predicted by our simple model yield noise reduction
results which are very close to optimum.
For 4 - R - 99 and window sizes compares the mean noise
reduction of 3 methods as explained previously. The best smoothing parameters derived
from our simple noise model and the numerically determined best fixed parameters are
even closer than in the 2 previous cases and their performance is very nearly optimal.
Window Method ff \Sigma1 ff \Sigma2 Mean noise reduction
optimum variable 0.770903
best fixed 0.2865 0.765732
optimum variable variable 0.910833
best fixed 0.2386 0.1190 0.906917


Mean noise reduction for 4 - R - 99
Finally, for one prefers to use ff 1(computationnally
convenient for deviation angle measurements), the mean error reduction level is 0.8832.
This is very good but not quite as effective as the optimum methods previously discussed.
A comparison of the error reduction with the best possible solution, for every value of R,
appears in Fig. 15.
V. Conclusion
This paper has presented a different avenue to solve the problem of optimum smoothing
of 2-D binary contours. Several approaches were reviewed with particular emphasis on
their theoretical merits and implementation difficulties. It was argued that most methods
are eventually implemented as a local weighted average with particular weight values.
Hence we adopted this scheme as the starting point of our investigation into optimum
methods.
Furthermore, there are many applications where smoothing is performed to improve the
precision of specific measurements to be computed from the contour points. In such cases,
the smoothing parameters should be chosen based on the nature of the computations
intended, instead of relying on a single, general 'optimality' criterion. Thus our work was
focused on optimum local weighted averaging methods tailored for specific computational
goals. In the present article, we have considered three such goals: obtaining reliable
estimates of point positions, of slopes, and of deviation angles along the contours.
To study the problem, a simple model was defined to represent 1-pixel random noise
along a straight horizontal border. Based on this simple model, an in-depth analytical
investigation of the problem was carried out, from which precise answers were derived for
the 3 chosen criteria.
Despite its simplicity, this model captures well the kind of perturbations which digitization
noise causes in the numerical estimation of various quantities along 2-D binary
contours even with arbitrary curvature. This was indeed verified, for window sizes of
and by finding the best smoothing parameters, using equivalent criteria, for digital
circles over a wide range of radii.
In this general case, the best smoothing parameters were found to vary according to
the length of the radius. Thus, in order to take full advantage of these optimum filters,
it would be necessary to compute local estimates of the radius of curvature for groups of
consecutive pixels along the contour, and then apply the best parameters found for these
radii. This would significantly reduce the efficiency of the smoothing operation. However,
it is not really necessary to go to that extent since the performance of these varying-weight
optimum filters can be very nearly approached by methods with a fixed set of parameters.
The latter were derived by numerical computation, for a wide range of radii. And it turned
out that their values were very close to those predicted using our simple digitization noise
model.
These numerical computations with varying radius of curvature validate our proposed
model and confer added confidence to the results obtained from it. Researchers requiring
simple and effective local weighted averaging filters before making numerical estimates of
specific quantities can thus rely on this model to derive optimum methods tailored to their
particular needs.
VI.

Acknowledgements

The authors would like to thank Dr. Louisa Lam for helpful comments and suggestions
made on an earlier draft of this paper.
This work was supported by the National Networks of Centres of Excellence research
program of Canada, as well as research grants awarded by the Natural Sciences and Engineering
Research Council of Canada and by an FCAR team research grant awarded by
the Ministry of Education of Quebec.


--R

"Digitized circular arcs: Characterization and parameter estimation,"
"Curve fitting approach for tangent angle and curvature measurements,"
"On the encoding of arbitrary geometric configurations,"
"Extraction of invariant picture sub-structures by computer,"
"Analysis of the digitized boundaries of planar objects,"
"On the digital computer classification of geometric line patterns,"
"Improved computer chromosome analysis incorporating preprocessing and boundary analysis,"
"Computer recognition of partial views of curved objects,"
"The medial axis of a coarse binary image using boundary smoothing,"
"Performances of polar coding for visual localisation of planar objects,"
"Curve smoothing for improved feature extraction from digitized pictures,"
"Measurements of the lengths of digitized curved lines,"
"Multiple resolution skeletons,"
"Non-parametric dominant point detection,"
"On the detection of dominant points on digital curves,"
"Fitting digital curve using circular arcs,"
"Scale-space filtering,"
"The structure of images,"
"The curvature primal sketch,"
"Scale-based description and recognition of planar curves and two-dimensional shapes,"
"Robust contour decomposition using a constant curvature criterion,"
"Adaptive smoothing: A general tool for early vision,"
"Pattern spectrum and multiscale shape representation,"
"A multiscale approach based upon morphological filtering,"
"Scale-space from nonlinear filters,"
"Smoothing by spline functions,"
"Spline functions and the problem of graduation,"
"A regularized solution to edge detection,"
"A computational approach to edge detection,"
"Uniqueness of the gaussian kernel for scale-space filtering,"
"Scaling theorems for zero crossings,"
"The renormalized curvature scale space and the evolution properties of planar curves,"
"Scaling theorems for zero-crossings,"
"Scaling theorems for zero crossings of bandlimited signals,"
"Scale-space for discrete signals,"
"An extended class of scale-invariant and recursive scale space filters,"
"Multiscale nonlinear decomposition: The sieve decomposition theorem,"
"Optimal estimation of contour properties by cross-validated regularization,"
"Optimal smoothing of digitized contours,"
"One-dimensional regularization with discontinuities,"
"Partial smoothing splines for noisy boundaries with corners,"
"Describing
"Filtering closed curves,"
"Organization of smooth image curves at multiple scales,"
"Local reproducible smoothing without shrinkage,"
"Iterative smoothed residuals: A low-pass filter for smoothing with controlled shrinkage,"
"Optimal L1 approximation of the gaussian kernel with application to scale-space construction,"
"Regularization of digitized plane curves for shape analysis and recognition,"
"Refining curvature feature extraction to improve handwriting recognition,"
"Multistage digital filtering utilizing several criteria,"
"Computer recognition of unconstrained hand-written numerals,"
"Speed, accuracy, flexibility trade-offs in on-line character recognition,"
John Wiley
"On the properties of discrete circles, rings, and disks,"
"Circle generators for display devices,"
"A note on the paper by
"Algorithms for generation of discrete circles, rings, and disks,"
--TR

--CTR
Ke Chen, Adaptive Smoothing via Contextual and Local Discontinuities, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.10, p.1552-1567, October 2005
Helena Cristina da Gama Leito , Jorge Stolfi, A Multiscale Method for the Reassembly of Two-Dimensional Fragmented Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1239-1251, September 2002
optimal local weighted averaging;contour smoothing;gaussian smoothing;digitization noise modeling