Similarity and Symmetry Measures for Convex Shapes Using Minkowski Addition.
AbstractThis paper is devoted to similarity and symmetry measures for convex shapes whose definition is based on Minkowski addition and the Brunn-Minkowski inequality. This means, in particular, that these measures are region-based, in contrast to most of the literature, where one considers contour-based measures. All measures considered in this paper are invariant under translations; furthermore, they can be chosen to be invariant under rotations, multiplications, reflections, or the class of affine transformations. It is shown that the mixed volume of a convex polygon and a rotation of another convex polygon over an angle  is a piecewise concave function of . This and other results of a similar nature form the basis for the development of efficient algorithms for the computation of the given measures. Various results obtained in this paper are illustrated by experimental data. Although the paper deals exclusively with the two-dimensional case, many of the theoretical results carry over almost directly to higher-dimensional spaces.
Introduction
The problem of shape similarity has been extensively investigated in both machine vision
and biological vision. Although for human perception, different features such as shape,
color, reflectance, functional information play an important role while comparing objects,
in machine vision usually only geometric properties of shapes are used to introduce shape
similarity. In the literature, one finds two concepts for expressing the similarity of shapes:
distance functions measuring dissimilarity and similarity measures expressing how similar
two shapes are. In this paper we shall work with similarity measures.
In practice, similarity approaches have to be invariant under certain classes of transfor-
mations, e.g. similitudes (i.e., translations, rotations, change of scale). Affine transformations
are also of great practical value as these can approximate shape distortions arising
when an object is observed by a camera under arbitrary orientations with respect to the
image plane [1]. A well-known method to develop a similarity approach which is invariant
under a given class of transformations is to perform a shape normalization first [2], [3], [4].
In Subsection IV-C of this paper we discuss one particular method based on the ellipse of
inertia.
In the literature, one finds several different methods for comparing shapes. Among the
best known ones are matching techniques [4]. We mention here also contour matching [5],
[6], structural matching [7] (which is based on specific structural features), and point
set matching [8]. In several approaches, one uses the Hausdorff distance for point sets
to describe similarity [9]. An interesting construction of a similitude invariant distance
function for polygonal shapes is given in [5]; here one computes the L 2 -distance of the
so-called turning functions representing the boundary of the polygons. Several authors
use the concept of a scale space to develop a multiresolution similarity approach [10],
[11]. Finally, Fourier descriptors derived from contour representations have been used by
various authors to describe shape similarity and symmetry [12], [13], [14], [15]. See [16]
for a comprehensive discussion.
Similarity measures can be used to compute "how symmetric a given shape is", e.g. with
respect to reflection in a given line. For many objects, presence or absence of symmetry
is a major feature, and therefore the problem of object symmetry identification is of great
interest in image analysis and recognition, computer vision and computational geometry.
Unfortunately, in many practical cases, exact symmetry does not occur or, if it does, is
disturbed by noise. In such circumstances it is useful to define measures of symmetry
which give quantitative information about the amount of symmetry of a shape. There
exists a vast literature dealing with all kinds of symmetry of shapes and (grey-scale)
images: central symmetry [17], [18], [19], reflection symmetry [20], [21], [22], rotation
symmetry [23], [24], skew symmetry [25], [26]; see also [27], [28].
The Brunn-Minkowski theory [29] allows us to introduce a general framework for comparing
convex shapes of arbitrary dimension. In this paper we introduce and investigate a
class of similarity and symmetry measures for convex sets which are based on Minkowski
addition, the Brunn-Minkowski inequality, and the theory of mixed volumes. Although
we deal with the 2D case, most of results can be extended to higher dimensions. The
similarity measures examined in this paper are translation invariant by definition. In ad-
dition, they can be defined in such a way that they are also invariant with respect to other
transformation groups such as rotations and reflections. We propose efficient algorithms
for the computation of similarity measures for convex polygons which are invariant under
November 4, 1997
similitude transformations. These algorithms are based on the observation that the given
measures are piecewise concave functionals; thus to find their maximal values it is sufficient
to compute them only for a finite number of points. Moreover this number is bounded by
are the number of vertices of the polygons
son. We also propose efficient algorithms for the computation of affine invariant similarity
measures. In this case the calculation is preceded by a normalization of the polygonal
shapes into so-called canonical shapes. Now the computation of the affine invariant similarity
measure is reduced to the computation of the rotation invariant similarity measure
for their respective normalizations.
In this paper we investigate symmetry measures for convex shapes which are invariant
under line reflections and rotations. We introduce symmetry measures using two different
approaches. The first approach uses similarity measures, the second is a direct approach.
We propose efficient algorithms for the computation of rotation and reflection invariant
symmetry measures for convex polygons. The normalization technique makes it possible
to compute skew symmetry measures as well.
We conclude with an overview of this paper. We start with some notations and recall
some basic concepts in Section II. In Section III we give short treatment of the theory of
mixed volumes, the Brunn-Minkowski inequality, and some derived inequalities. A formal
definition of similarity measures can be found in Subsection IV-A, where we also present
some examples based on Minkowski addition. In Subsection IV-B we investigate similarity
measures for convex polygons which are invariant under rotations and multiplications, and
we present an algorithm to compute such measures efficiently. An affine invariant similarity
measure is presented in Subsection IV-C. To define it, we introduce an image normalization
(canonical form) based on the ellipse of inertia known from classical mechanics. Symmetry
measures are introduced in Section V; there we also give several examples, some of them
based on similarity measures. In Section VI we illustrate our theoretical findings with
some experimental results, and we end with some conclusions in Section VII.
In this paper, most results are given without proof. Readers interested in such proofs,
as well as some additional results, may refer to our report [30] from which this paper has
been extracted.
II. Preliminaries
In this section we present some basic notation and other prerequisites needed in the
sequel of the paper. By K(IR 2 ), or briefly K, we denote the family of all nonempty compact
subsets of IR 2 . Provided with the Hausdorff distance [29] this is a metric space. The
compact, convex subsets of IR 2 are denoted by and the convex polygons by
just P. In this paper, we are not interested in the location of a shape A '
other words, two shapes A and B are said to be equivalent if they differ only by translation.
We denote this as A j B. The Minkowski sum of two sets
It is well-known [29] that every element A of C is uniquely determined by its support
function given by:
Here ha; ui is the inner product of vectors a and u, 'sup' denotes the supremum, and S 1
denotes the unit circle. It is also known that [29]:
for C. The support set F (A; u) of A at u 2 S 1 consists of all points a 2 A for which
A polygon P ' IR 2 can be represented uniquely by specifying the position of one of its
vertices, the lengths and directions of all its edges, and the order of the edges. Below, p i
will denote the length of edge i and u i is the vector orthogonal to this edge: see Fig. 1. By
we denote the angle between the positive x-axis and u i . Since we are not interested
in the location of P , it is sufficient to give the sequence
is the number of vertices of P . We will call this sequence the perimetric
representation of P . In Fig. 1 we give an illustration.
We denote this sequence by M(P ). If the polygon is convex, then the order of
does not have to be specified in advance, since in this case the normal vectors are ordered
counter-clockwise. In this case we can think of M(P ) as a set. But we can also use the
November 4, 1997
Fig. 1. Perimetric representation of a polygon.
so-called perimetric measure M(P; \Delta) as an alternative representation [19]:
0; otherwise.
We point out that the perimetric measure is a special case of the concept of area measure
[29]. It is evident that for every convex polygon P , we have the identity
where the sum is taken over all u for which M(P; u) 6= 0. This relation expresses that the
contour of P is closed. Moreover, any discrete function that satisfies this relation is the
perimetric measure of a convex polygon.
It is well-known that the Minkowski addition of two convex polygons can be computed by
merging both perimetric representations; see e.g. [31], [32]. Mathematically, this amounts
to the following relation:
for
In the second part of this section we consider affine transformations on IR 2 . The reader
may refer to [33] for a comprehensive discussion. The group of all affine transformations
on IR 2 is denoted by G 0 . If g 2 G 0 and A 2 K, then Ag. We write
for every A 2 K. This is equivalent to saying that g \Gamma g 0 is a
translation. We denote by G the subgroup of G 0 containing all linear transformations, i.e.,
transformations g with
Lemma 1: For any two sets A; B ' IR d and for every G, we have
We introduce the following notations for subsets of G:
ffl I: isometries (distance preserving transformations);
ffl R: rotations about the origin;
multiplications with respect to the origin by a positive
ffl L: (line) reflections (lines passing through the origin);
ffl S: similitudes (rotations, reflections, multiplications).
Observe that I; R; M and S are subgroups of G. For every transformation g 2 G we
can compute its determinant 'det g' which is, in fact, the determinant of the matrix corresponding
with g. Note that this value is independent of the choice of the coordinate
system. If g is an isometry then j det the converse is not true, however. If H
is a subgroup of G, then H+ denotes the subgroup of H containing all transformations
with positive determinant. For example, I multiplications and
rotations. If H is a subgroup of G, then the set fmh j h 2 H; m 2 Mg is also a subgroup,
which will be denoted by MH.
Denote by r ' the rotation in IR 2 around the origin over an angle ' in a counter-clockwise
direction, and by ' ff the reflection in IR 2 with respect to the line passing through the origin
which makes an angle ff with the positive x-axis. The following relations hold:
In what follows, the topology on K is the one induced by the Hausdorff metric, also
called myopic topology [34]. At several instances in this paper we shall need the following
concept.
Definition 1: Let H ' G and J ' K. We say that H is J -compact if, for every A 2 J
and every sequence fh n g in H, the sequence fh n (A)g has a limit point of the form h(A),
It is easy to verify that R is K-compact. However, the subcollection fr
R is a rotation with '=- irrational, is not K-compact. The following result is
easy to prove.
Lemma 2: Assume that H is J -compact and let f : J ! IR be a continuous function.
If A 2 J and f 0 := sup h2H f(h(A)) is finite, then there exists an element h 0 2 H such
that f(h 0
III. Mixed volumes and the Brunn-Minkowski inequality
In this section we present a brief account of the theory of volumes and mixed volumes
of compact sets (also called 'mixed areas' in the 2-dimensional case). For a comprehensive
treatment the reader may consult the book of Schneider [29]. The volume (or area) of a
compact set A will be denoted by V (A). It is well-known that for every affine transformation
g the following relation holds:
The mixed volume V (A; B) of two compact, convex sets A; B ' IR 2 is implicitly defined
by the following formula for the volume of A \Phi B:
Fig. 2 for an illustration.
Fig. 2. The right figure is P \Phi Q. The sum of the volumes of the light grey regions equals 2V (P; Q), the
sum of the volumes of the dark grey regions equals V (P ).
The mixed volume has the following properties being arbitrary compact,
convex
for every affine transformation
is continuous in A and B (11)
with respect to the Hausdorff metric:
Note for example that (9) is a straightforward consequence of (3) and (4)-(5).
In this paper the following well-known inequality plays a central role. See Hadwiger [35]
or Schneider [29] for a comprehensive discussion.
Theorem 1 (Brunn-Minkowski inequality) For two arbitrary compact sets
the following inequality holds:
with equality if and only if A and B are convex and homothetic modulo translation, i.e.,
The Brunn-Minkowski inequality (12) in combination with (5) yields the following inequality
for mixed volumes:
and as before equality holds iff A and B are convex and B j -A for some - ? 0. This
latter inequality is called Minkowski's inequality.
Using the fact that for two arbitrary real numbers x; y one has
equality y, one derives from (12) that:
with equality iff A j B and both sets are convex.
The mixed volume of two convex polygons can be easily computed using support
functions and perimetric representations. Assume that the perimetric representation of Q
is given by the sequence (v Furthermore, if h(P; \Delta) is the support
function of P , then
Fig. 2 for an illustration of this formula.
Note that with this formula the additivity of V (P; Q) as stated in (10) follows immediately
from the additivity of the support function; see (1). Furthermore, (15) in combination
with (6) shows that V (P; Q) is increasing in both arguments. In fact, this observation
holds for arbitrary compact, convex sets, i.e.,
We conclude this section with a formula for the computation of the volume of a 2-
dimensional polygon (not necessarily convex) using its perimetric representation. Several
formulas for calculating volumes of polyhedra are known [36]. Let the vertices (ordered
counter-clockwise) of a polygon P be given by
Refer to [36] for some further information.
If P is a polygon with perimetric representation then the
vertices are given by (putting x
6 u j . Here P needs not be convex. Substitution into (17) gives
This is the formula which we will use in the sequel of this paper.
IV. Similarity measures
This section, which is concerned with similarity measures, falls apart into three subsec-
tions. In Subsection IV-A we give a formal definition and present some basic properties.
In the next two subsections we treat, respectively, similarity measures that are invariant
under rotations and multiplications (Subsection IV-B) and similarity measures that are
invariant under arbitrary affine transformations (Subsection IV-C).
A. Definition and basic properties
One of the goals of this paper is to find a tool which enables us to compare different
shapes, but in such a way that this comparison is invariant under a given group H of
transformations and can be computed efficiently. For example, if we take for H all rota-
tions, then our comparison should return the same outcome for A and B as for A and
r(B), where r is some rotation.
Towards this goal one could try to find a distance function (or metric) d(A; B) which
equals zero if and only if B j h(A) for some h 2 H. Many authors, however, rather
work with so-called similarity measures than with distance functions. In this paper we
will follow this convention.
Definition 2: Let H be a subgroup of G and J ' K. A function oe : J \Theta J ! [0; 1] is
called an H-invariant similarity measure on J if
1.
2.
3.
4.
5. oe is continuous in both arguments with respect to the Hausdorff metric.
When H contains only the identity mapping, then oe will be called a similarity measure.
Although not stated explicitly in the definition above, it is also required that J is invariant
under H, that is,
If oe is a similarity measure on J and H is a J -compact subgroup of G, then
defines an H-invariant similarity measure on J . Unfortunately, oe 0 is difficult to compute
in many practical situations. Below, however, we present two cases (with
which this can be done efficiently if one restricts attention to convex polygons.
Let H be a given subgroup of G, and define
and
Proposition 1: If H is a C-compact subgroup of G, then
(a) oe 1 is an H-invariant similarity measure on C;
(b) oe 2 is an MH-invariant similarity measure on C.
In [30] we present a simple example which shows that compactness is essential.
We conclude this section with the following simple but useful result. Recall that ' 0 is
the line reflection with respect to the x-axis.
Proposition 2: Let oe be a similarity measure on J , and define
(a) If oe is R-invariant, then oe 0 is an I-invariant similarity measure.
(b) If oe is G+ -invariant, then oe 0 is a G-invariant similarity measure.
To give the reader an idea of the flavour of the proof, we show, for the result in (b),
property 3 of the definition of an H-invariant similarity measure (Definition 2).
G. There are two possibilities: g 2 G+ or g 2 G n G+ . We consider the second
case. We can write
Now
which had to be demonstrated.
B. Rotations and multiplications
In this section we consider similarity measures on P which are S+ -invariant, i.e., invariant
under rotations and multiplications. We use the similarity measures defined in (20)-
In these expressions, the terms V (P \Phi r ' (Q))
and play an important role. Let the perimetric representations of the convex
November 4, 1997
polygons P and Q be given by
respectively. To compute
The support set F (P; r ' (v j )) consists of a vertex of P unless ' is a solution of r ' (v j
g. Angles ' for which this holds (i.e., r ' (v are called critical angles.
The set of all critical angles for P and Q is given by
f(
where
6 u denotes the angle of vector u with the positive x-axis. We denote the critical
angles by 0 - '
2-. It is evident that N - n P nQ . Now, fix a vertex
We have seen that the support set F (P; r ' (v j )) consists of a
vertex C of P ; see Fig. 3.
d
a
O
Fig. 3. The support set F (P; r '
(v j
consists of the vertex C.
be the angle between the line through C with normal vector r ' (v j ) and the
line through O and C. It follows that h(P; r ' (v j
Taking the second derivative with respect to ' we find
we find a similar result for ' 7!
Thus we arrive at the following result.
Proposition 3: The volume V (P \Phi r ' (Q)) and the mixed volume are functions
of ' which are piecewise concave on ('
This result is illustrated in Fig. 4.525660
Fig. 4. Left: convex polygons P and Q. Right: the function ' 7! V (P \Phi r ' (Q)) is piecewise concave.
The ffi's indicate the location of the critical angles.
Consider the S+ -invariant similarity measure obtained from (20) by choosing
Then
sup -?0; '2[0;2-)
=h
=h
=h
Thus, in order to compute oe 1 (P; Q) we have to minimize two expressions, one in - and
one in '. The first expression achieves its minimum at
2 , the second at
one of the critical angles associated with
The similarity measure oe 2 given by (21) results in
From Proposition 1 we know that oe 2 is S+ -invariant, too. As above, the maximum is
attained at one of the critical angles associated with Q, and we get
In Section III we have given some formulas for the computation of (mixed) volumes of
convex polygons. The expression in (19) uses the perimetric representation, and we use it
to get the following result.
Proposition 4: Given the perimetric representation of the convex polygons P and Q,
the time complexity of computing oe 1 and oe 2 is O(n P nQ (n P are the
number of vertices of P and Q, respectively.
If we choose
Using that '
min
where ~
To find the minimum, we need to consider the critical angles of
well as those of
Q.
C. Affine invariant similarity measure
G, then the similarity measures defined in (20) and (21), respectively, are
affine invariant (that is, invariant under arbitrary affine transformations). Unfortunately,
we do not have efficient algorithms to compute them. However, using the approach of
Hong and Tan in [2], we are able to define similarity measures which can be computed
efficiently, and which are invariant under a large group of affine transformations, namely
G+ , the collection of all linear transformations which have a determinant which is positive.
In combination with Proposition 2, this leads to similarity measures which are G-invariant.
The basic idea is to transform a set A to its so-called canonical form A ffl in such a way
that two sets A and B are equivalent modulo a transformation in G+ if and only if A ffl and
are equivalent modulo rotation. The definition of the canonical form, as discussed by
Hong and Tan [2], is based on the concept of the ellipse of inertia known from classical
mechanics [37]. Note, however, that Hong and Tan [2] use a slightly different approach;
they introduce the moment curve which is closely related to the ellipse of inertia.
Throughout this section we restrict ourselves to the family of compact sets with positive
area, in the sequel denoted by K+ . Consider an axis through the centroid of A, and denote,
for a point (x; y) 2 A, by r(x; y) its distance to this axis. The moment of inertia with
respect to the axis is given by:
Z Z
A
Here ' denotes the angle between the axis and the x-axis in some fixed coordinate system.
An easy calculation shows that
(m xx +m yy
(see also [38, p.48-53]). Here m
A xydxdy.
The point q
sin ') on the axis traces an ellipse when ' varies between
and 2-, the so-called ellipse of inertia.
ellipse of inertia
a
yy
Fig. 5. The ellipse of inertia of a shape.
This ellipse, depicted in Fig. 5, has its long axis at angle ' 0 , which is the unique solution
in [0; -) of the equations
sin
2m xy
cos
Let 2a and 2b be the lengths of these axes, respectively. One easily finds that a =
which yields that
xy
xy
A simple calculation shows thata 2
The following definition is due to Hong and Tan [2].
Definition 3: A shape is said to be in canonical form if its centroid is positioned at the
origin and its ellipse of inertia is a unit circle.
Proposition 5: Every compact set can be transformed into its canonical form by means
of a transformation in G+ , namely by a stretching along the long axis of the ellipse of
inertia by a factor b=(ab) 1=4 and along the short axis by a factor a=(ab) 1=4 .
The proof of this result is based on the observation that, under the transformation (x; y) 7!
(-x; -y), the second moments scale as follows:
Our next result shows how the canonical form of a shape is affected by affine transformations

Proposition
(a) For every A 2 K+ we have
(b) If
In [30] we use the notion of covariance matrix to prove (b); see also [3].
With this result it is easy to construct G+ -invariant similarity measures from R-invariant
ones.
Proposition 7: Let oe : K+ \Theta K+ ! [0; 1] be an R-invariant similarity measure, and define
then oe ffl is a G+ -invariant similarity measure.
As the map A 7! A ffl preserves convexity, we get the same result for shapes in
as well as for shapes in P.
To apply these results for convex polygons, there are at least two possibilities. We
can compute the canonical shape of the polygon itself or of the set given by its vertices
considered as point masses. In the latter case, which is the one considered below, the
previous findings remain valid, albeit that integrals have to be replaced by summations.
Furthermore, the stretching factors in Proposition 5 become b (along the long axis) and
a (along the short axis), respectively. Suppose we are given the perimetric representation
of a convex polygon P . The computation of M(P ffl
consists of the following steps (putting
1. Fixing the origin at the first vertex of P , we can find the coordinates of the
other vertices; see (18).
2. The centroid of P is given by
3. The second moments m are given by
4. Compute b from (23)-(24).
5. Define OE
6 in such a way that \Gamma-=2 - OE
i from
6
6
a tan OE i
a
tan
and
Example 1: Consider the rotation invariant similarity measure given by (21), i.e.,
oe ffl on P as in Proposition 7, then oe ffl is a G+ -invariant similarity measure. Using
Proposition 2(b) we obtain a G-invariant similarity measure.
V. Symmetry measures
Exact symmetry only exists in the mathematician's mind. It is never achieved in the real
world, neither in nature nor in man-made objects [39]. Thus, in order to access symmetry
of objects (convex 2-dimensional polygons in our case), we need a tool to measure the
amount of symmetry. Towards that goal Gr-unbaum [18] introduced the concept of a
symmetry measure; refer to [23], [21] for some other references. Below we give a formal
definition of this concept. But first we recall some basic terminology. We will restrict
attention to the 2-dimensional case, but most of what we say carries over immediately to
higher dimensions.
The symmetry group of a set A ' IR 2 consists of all g 2 G such that g(A) j A.
The use of the word 'group' is justified by the observation that these transformations
constitute a subgroup of G. An element g in this subgroup is called a symmetry of A
and A is said to be g-symmetric. An element g 2 G for which denoting the
identity transformation) for some finite m - 1 is called a cyclic transformation of order m.
Sometimes we to denote the dependence on g. It is evident that j det
if g is cyclic.
In this paper we are mostly interested in symmetries of a given shape which are cyclic.
However, as shown in Example 2(b), there may also exist symmetries which are not cyclic.
Example 2: (a) Not every cyclic transformation is an isometry. For example, (x; y) 7!
(2y; x=2) is cyclic of order 2, but it is not an isometry.
(b) Not every symmetry is cyclic. Let B be the unit disk in IR 2 and let A := g(B) for
some 2 G. It is obvious that gr ' g \Gamma1 is a symmetry of A for every ' 2 [0; 2-], since r ' is
a symmetry of B. In most cases, however, this symmetry is not cyclic. Let, for example,
g be the transformation (x; y) 7! (2x; y). Then A is the ellipse x 1. For every '
with '=- irrational, the transformation gr ' g \Gamma1 is a non-cyclic, non-isometric symmetry of
the ellipse.
If H is a subgroup of G, then the set of cyclic transformations in H is denoted by C(H).
It is easy to see that
In general, C(H) is not a subgroup.
Let e 2 G be a cyclic transformation of order m. We define the mapping e   : K ! K by
Here the denominator m represents a scaling with factor 1=m. It is easy to see that e   (A)
is e-symmetric, and we call this set the e-symmetrization of A. Observe that e   is not an
affine transformation. As a matter of fact, e   is defined for shapes rather than for points.
Every line reflection ' ff is a cyclic transformation of order 2. The corresponding symmetrization
of a set A, that is (A))=2, is called Blaschke symmetrization of A [29].
Proposition 8: Let A 2 C. If e is a cyclic transformation, then V (e   (A)) - V (A).
Furthermore, the following statements are equivalent:
e is a symmetry of A;
if the greatest common divisor of k and m equals 1. If e is
a cyclic transformation of order m and k / m, then e k is a cyclic transformation of order
m, and (e k )  . It is easy to see that every cyclic rotation of order m is of the form
Symmetry measures were introduced by Gr-unbaum [18] for point symmetries. Here we
will generalize this definition to arbitrary families of cyclic transformations.
Definition 4: Let E be a given collection of cyclic transformations and J ' K. A
is called an E-symmetry measure on J if, for every e 2 E, the
function -(\Delta; e) is continuous on J with respect to the Hausdorff topology, and if
Suppose that, in addition, the following property holds:
if e has order m and k / m, then -(A;
then - is called a consistent E-symmetry measure.
G be such that heh we say that - is H-invariant if
Note that in this definition we have restricted ourselves to cyclic transformations.
Example 3: It is easy to show that
defines a symmetry measure for all cyclic rotations r ' (i.e., '=- rational). This symmetry
measure is invariant under similitudes. It is not consistent, however.
The consistency condition (4) has the following intuitive interpretation. Suppose that a
shape A is (nearly) symmetric with respect to rotation over 2-=m, then it is also (nearly)
symmetric with respect to rotation over an angle 2k-=m, where 1 - k - m. Moreover, if
k / m, then the converse also holds.
There are at least two different ways to make an E-symmetry measure consistent. Our
next result, the proof of which is straightforward, shows how this can be done.
Proposition 9: If - is an E-symmetry measure, then
k/me
Y
k/me
both define a consistent E-symmetry measure. If - is H-invariant, then - min and - are
H-invariant as well.
It is easy to see that - consistent. The next result shows how one can
obtain symmetry measures from similarity measures.
Proposition 10: Let H be a subgroup of G and E ' C(H) such that
If oe is an H-invariant similarity measure, then - given by
is a consistent H-invariant E-symmetry measure.
Remarks. (a) If we do not assume the conditions in (26), the equality e   (A) j h(A)
yields that This implies that h(A) is
e-symmetric.
(b) It is tempting to replace (27) by: -(A; However, such a definition
does not allow us to consider invariance under groups H which contain e. For, oe(A;
if oe is H-invariant and e 2 H.
The following example is based on the similarity measure oe 2 given by (21).
Example 4: Let E consist of the rotations e is a positive integer.
Furthermore, let . It is clear that condition (26) in Proposition 10 holds, hence
defines an S+ -invariant E-symmetry measure.
There are other construction methods for symmetry measures besides those based on
similarity measures. Below we present several examples of symmetry measures based on
Minkowski addition.
In Proposition 8 we have seen that V (e   e is a cyclic transformation. Let
E be a collection of cyclic transformations; we define
Proposition 11 below shows that - 1 defines a consistent E-symmetry measure. There is
alternative way to define a symmetry measure using mixed volumes. It is based upon the
observation (see (13)) that
if e is a cyclic transformation. We define
Note that in Example 3 we have discussed the case where E comprises all cyclic rotations.
At first sight, it seems possible to define yet another symmetry measure by replacing
in (29). However, a simple calculation using properties
shows that V (A; e   using (7), one gets that
Therefore, such a definition would coincide with - 1 in (28).
Proposition 11: Let E be a given collection of cyclic transformations, then - 1 and - 2
given by (28) and (29), respectively, are E-symmetry measures. The measure - 1 is consistent

Suppose, furthermore, that H ' G is such that heh
and - 2 are H-invariant.
If e is a finite-order rotation or a reflection, and if P is a convex polygon whose perimetric
representation is given, then it is easy to compute the perimetric representation of e   (P )
by merging the perimetric representations of e i (P ); see Section II. This also leads to an
efficient computation of the symmetry measure - 1 .
Example 5 (Rotations) Let E consist of all cyclic rotations. Then - 1 given by (28) is a
consistent S-invariant E-symmetry measure, S being the group of similitudes. Because of
the consistency of - 1 , it suffices to consider :g. Given a polygon
P and a rotation r over the angle 2-=m, for some m - 1; the r-symmetrization r   (P ) is
a polygon which is symmetric under rotations of order m. If M(P; u) is the perimetric
measure of P , then we can use (2) to find the perimetric measure of r   (P
M(r   (P ); u) =m
=m
It is obvious that
mod 2-:
Using formula (19), we can compute - 1 directly. Table II in Section VI contains the
outcomes for a given collection of convex polygons.
Example 6 (Line reflections) In this example we restrict ourselves to convex polygons.
If E consists of all line reflections, then - 1 given by (28) defines an S-invariant E-symmetry
measure. For a line reflection ' ff we find
Like in the previous example, we can compute the perimetric measure M('
ff (P ); u) if the
perimetric measure of P is given:
and
6 u) mod 2-:
In

Table

III in Section VI we compute the symmetry measure - 1 for several convex polygons
for the angles
The symmetry measure - 2 given by (29) amounts to
Thus we get that
In most of the literature, one does not compute the symmetry measure for specific line
reflections ' ff , but rather the maximum over all lines. In our setting this leads to the
following definition. A function ' : K ! [0; 1] is called an index of reflection symmetry if '
is continuous, and only if A is reflection symmetric with respect to some
line. If - is a measure of reflection symmetry, such as - 1 in (30), then
is an index of reflection symmetry.
The computation of this index can be done efficiently because of the following observa-
tions. Since V
we conclude from Proposition 3
that ff 7! V concave on (ff
the angles 2ff
k are the critical
angles of
lying between 0 and 2-. Thus every ff
k is of the form 1(
6
where P has perimetric representation f(u g.
This yields that the minimum of ff 7! V is achieved at one of the angles ff
k .
Using the same argument as in Proposition 4, one finds that the index can be computed
in O(n 3
In Table III we also give the index as well as the angle of the reflection
axis for which the index (maximum) is attained.
Example 7 (Skew-symmetry) A shape A is said to be skew-symmetric if there exists
an affine transformation g 2 G+ such that g(A) is reflection symmetric with respect to
some line. In this example we show that one can use the notion of canonical shapes
(Subsection IV-C) to find 'how skew-symmetric' a given shape is.
Suppose that A is skew-symmetric; then g(A) is reflection symmetric for some g 2 G+ .
The symmetry line of g(A) coincides with one of the axes of inertia, and therefore it is also
a symmetry axis of (g(A)) ffl . As this latter shape is a rotation of A ffl (see Proposition 6(b)),
we conclude that A ffl is reflection symmetric, too. Conversely, if A ffl is reflection symmetric,
then A is skew-symmetric (for, A ffl is the result of two stretchings along the principal axes
of the ellipse of inertia of A). Thus we find that A is skew-symmetric if and only if A ffl is
reflection symmetric. This yields immediately that we obtain an index of skew symmetry
from any index of reflection symmetry applied to the canonical shapes; see Example 6.
VI. Experimental results
In this section the results obtained previously will be applied to some concrete examples.
We consider four, more or less regular, shapes, namely: a triangle, a square, a tetragon
with one reflection axis, and a regular octagon. These shapes, along with their canonical
forms, are depicted in Fig. 6. In this figure, we depict four other convex polygons (and
their canonical forms), namely: P , a reflection of P denoted by P refl , a distortion of P
denoted by Q (the lower three points have been shifted in the x-direction), and an affine
transformation of Q denoted by Q aff .
In

Table

I we compute the similarity measure oe 2 given by (22) which is S+ -invariant.
In the first row we compute oe 2 (Q; R), where R is one of the other polygons depicted in
Fig. 6. In the third row we compute the values oe 2 (Q aff ; R). The second row contains the
values oe ffl
2 is the G+ -invariant similarity measure obtained from Proposition
7. Observe that we do not compute oe ffl
since these values are identical to
R). Note for example that using oe 2 , which is invariant under rotations and multi-
plications, Q is more similar to the square than to the tetragon (values 0.724 and 0.692,
respectively), whereas oe ffl
2 , which is G+ -invariant, gives opposite results (values 0.907 and
0.920, respectively).
In

Table

I we also give the angle at which the maximum in expression (22) is achieved.
Often, this 'optimal angle' depends, to a large extent, on the similarity measure that is
being employed.

Table

II and Table III are concerned with symmetry measures for rotations and re-
flections, respectively. In Table II we illustrate the measure - 1 discussed in Exam-
6triangle triangle ffl square square ffl
tetragon tetragon ffl octagon octagon ffl
refl
aff
Fig. 6. Polygons used in the experiments described in this section. Note that Q ffl
aff
is a rotation of Q ffl .
ple 5 for corresponding with rotations over 360 ffi =m. Observe that
In fact, it is easy to see that both - 1 and - 2 defined in (28)
and (29), respectively, satisfy
for every shape A and every affine transformation g.

Table

II shows the rotation symmetries of the square ( 90 ffi and 180 ffi degrees) and the
degrees). The triangle is not rotation symmetric, but the
measure is maximal at an angel of 120 ffi degrees (value 0.696). Note also that P is almost
-rotation invariant (value 0.995).

Table

III shows the reflection symmetry measure of Example 6 for five different reflection
axes. Furthermore, the two bottom rows capture the maximum over all axes (i.e., the index
November 4, 1997
of reflection symmetry; see Example 6) and the angle at which this maximum is attained.

Table

III shows that the triangle and tetragon have one reflection axis ( 90 ffi ), and the
square and octagon have three reflection axes Furthermore, P is
almost reflection symmetric with respect to the axes at 0 ffi and 90 ffi (value 0.995). The
angle at which the index of reflection is attained is almost the same for P and Q
and 95:3 ffi respectively).
VII. Conclusions
The objectives of this paper are twofold: on the one hand we wanted to give a formal
definition of similarity and symmetry measures that are invariant under a given group of
transformations, and to derive some general properties of such measures; see for example
Propositions 2, 7, 9, and 10. But, on the other hand, we have introduced some new examples
of such measures based on Minkowski addition and the Brunn-Minkowski inequality.
We believe that our analysis shows that such measures can be useful in certain applica-
tions. By no means, however, do we claim that our approach can be usefully applied in
every shape analysis problem. It is clear that our restriction to convex sets is a very severe
one: we will come back to this issue below.
As our approach is based on the area of shapes, it will be difficult to compare it with
boundary-oriented approaches, such as boundary matching. Van Otterloo [16, p.143]
points out that the quality of a similarity measure is a subjective matter: "it is usually
not possible to make general statements about the quality of a similarity measure on the
basis of results in a particular application: a measure that performs well in character
recognition does not necessarily perform well in industrial inspection."
Our similarity measures do not possess the triangle inequality. Moreover, the approach
applied in the paper is limited to convex shapes. In particular this second limitation is
a major drawback. To use our approach with non-convex shapes there are at least two
options. Firstly, one might still use the perimetric measure of a nonconvex shape, even
though it characterizes only a convex shape. Alternatively, one can choose to work with
the convex hull of non-convex shapes. In both cases, one has to give up some properties
of a similarity measure as given in Definition 2, in particular 4.
Although our exposition is mainly restricted to the 2D case, the approach has a straight-forward
8extension to 3D (and higher dimensional) shapes. For example, in the case of 3D
shapes, instead of using the perimetric representation, we must use the so-called slope
diagram representation [40]. Note that from the computational point of view the 3D case
becomes much more difficult, however. We will study such problems in our future work.

Acknowledgments

A. Tuzikov is grateful to the Centrum voor Wiskunde en Informatica (CWI, Amsterdam)
for its hospitality. He also would like to thank G. Margolin and S. Sheynin for discussions
on some results in this paper.



--R


"Recognize the similarity between shapes under affine transformation,"
"Image normalization for pattern recognition,"

"An efficiently computable metric for comparing polygonal shapes,"
"Identification of partially obscured objects in two and three dimensions by matching noisy characteristic curves,"
Computer Vision
"Similarity and affine invariant distances between 2D point sets,"
"Comparing images using the Hausdorff distance,"
"A multiresolution algorithm for rotation-invariant matching of planar shapes,"
"Scale-based description and recognition of planar curves and two-dimensional shapes,"
"Elliptic Fourier features of a closed contour,"
"Classification of partial 2-D shapes using Fourier descriptors,"
"Shape discrimination using Fourier descriptors,"
"Fourier descriptors for plane closed curves,"
A Contour-Oriented Approach to Digital Shape Analysis
"A determinition of the center of an object by autoconvolution,"
"Measures of symmetry for convex sets,"
"Convexity and symmetry: Part 2,"
"On symmetry detection,"
"Measures of axial symmetry for ovals,"
"On the detection of the axes of symmetry of symmetric and almost symmetric planar images,"
"Measures of N-fold symmetry for convex sets,"
"Detection of generalized principal axes in rotationally symmetric shapes,"
"Symmetry detection through local skewed symmetries,"
"Finding axes of skewed symmetry,"
"Detection of partial symmetry using correlation with rotated- reflected images,"
"Symmetry as a continuous feature,"
The Brunn-Minkowski Theory
"Similarity and symmetry measures for convex sets based on Minkowski addition,"
"A unified computational framework for Minkowski operations,"

Metric Affine Geometry


"Computing volumes of polyhedra,"


Symmetry in Science and Art
"Mathematical morphological operations of boundary-represented geometric objects,"
--TR

--CTR
Jos B. T. M. Roerdink , Henk Bekker, Similarity measure computation of convex polyhedra revisited, Digital and image geometry: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2001
Alexander V. Tuzikov , Stanislav A. Sheynin, Symmetry Measure Computation for Convex Polyhedra, Journal of Mathematical Imaging and Vision, v.16 n.1, p.41-56, January 2002
Hamid Zouaki, Representation and geometric computation using the extended Gaussian image, Pattern Recognition Letters, v.24 n.9-10, p.1489-1501, 01 June
Antonio Chella , Marcello Frixione , Salvatore Gaglio, Conceptual Spaces for Computer Vision Representations, Artificial Intelligence Review, v.16 n.2, p.137-152, October 2001
Andrew B. Kahng, Classical floorplanning harmful?, Proceedings of the 2000 international symposium on Physical design, p.207-213, May 2000, San Diego, California, United States
Bertrand Zavidovique , Vito Di Ges, The S-kernel: A measure of symmetry of objects, Pattern Recognition, v.40 n.3, p.839-852, March, 2007
symmetry measure;minkowski addition;convex set;similarity measure;brunn-minkowski inequality