Symmetry as a Continuous Feature.
AbstractSymmetry is treated as a continuous feature and a Continuous Measure of Distance from Symmetry in shapes is defined. The Symmetry Distance (SD) of a shape is defined to be the minimum mean squared distance required to move points of the original shape in order to obtain a symmetrical shape. This general definition of a symmetry measure enables a comparison of the amount of symmetry of different shapes and the amount of different symmetries of a single shape. This measure is applicable to any type of symmetry in any dimension. The Symmetry Distance gives rise to a method of reconstructing symmetry of occluded shapes. We extend the method to deal with symmetries of noisy and fuzzy data. Finally, we consider grayscale images as 3D shapes, and use the Symmetry Distance to find the orientation of symmetric objects from their images, and to find locally symmetric regions in images.
Introduction
One of the basic features of shapes and objects is symme-
try. Symmetry is considered a pre-attentive feature which
enhances recognition and reconstruction of shapes and objects
[4]. Symmetry is also an important parameter in physical
and chemical processes and is an important criterion
in medical diagnosis.
a. b. c.
Fig. 1. Faces are not perfectly symmetrical.
a) Original image.
b) Left half of original image and its reflection.
c) Right half of original image and its reflection.
However, the exact mathematical definition of symmetry
[23], [32] is inadequate to describe and quantify the symmetries
found in the natural world nor those found in the
visual world (a classic example is that of faces - see Figure
1). Furthermore, even perfectly symmetric objects lose
their exact symmetry when projected onto the image plane
or the retina due to occlusion, perspective transformations,
digitization, etc. Thus, although symmetry is usually considered
a binary feature, (i.e. an object is either symmetric
or it is not symmetric), we view symmetry as a continuous
feature where intermediate values of symmetry denote
some intermediate "amount" of symmetry. This concept of
continuous symmetry is in accord with our perception of
symmetry as can be seen, for example, in Figure 2.
Considering symmmetry as a continuous feature, we introduce
a "Symmetry Distance" that can measure and
quantify all types of symmetries of objects. This measure
H. Zabrodsky and S. Peleg are with the Institute of Computer Sci-
ence, The Hebrew University of Jerusalem, Jerusalem, 91904 Israel.
D. Avnir is with the Department of Organic Chemistry, The Hebrew
University of Jerusalem, Jerusalem, 91904 Israel.
a. b. c. d.
Fig. 2. Perceiving continuous symmetry.
a) A shape perceived as perfectly symmetric (the oblique mirror
axis passing through the vertex). b) Shortening an arm, the
shape is perceived as "almost" symmetric. c) Further shortening
of the arm, the shape is perceived as having "less" symmetry.
e) When the arm is eliminated the shape is again perfectly symmetric
(with a mirror axis perpendicular to the existing arm).
will enable a comparison of the "amount" of symmetry of
different shapes and the "amount" of different symmetries
of a single shape. Additionally, we present a simple and
general algorithm for evaluating this measure.
In Section II we define the Symmetry Distance and in
Section III describe a method for evaluting this measure.
Following, in Sections IV-VI we describe features of the
symmetry distance including its use in dealing with occluded
objects and with noisy data. Finally in Section VII
we describe the application of the symmetry distance to
finding face orientation and to finding locally symmetric
regions in images.
A. Definitions of Symmetry
In this paper we refer to the symmetries defined be-
low, although the definitions, methods and discussions presented
in this work apply to all other symmetries in any
dimension. For further details and a review see [34].
A 2D object is mirror-symmetric if it is invariant under
a reflection about a line (the mirror-symmetry axis).
A 3D object is mirror-symmetric if it is invariant under
a reflection about a plane.
A 2D object has rotational-symmetry of order n, denoted
Cn-Symmetry, if it is invariant under rotation of
radians about the center of mass of the object.
A 3D object has rotational-symmetry of order n, denoted
Cn-Symmetry, if it is invariant under rotation of
radians about a line (the rotational symmetry axis)
passing through the center of mass of the object.
Radial symmetry is the symmetry of a 2D object having
both mirror-symmetry and Cn -symmetry (note that such
objects have n axes of mirror-symmetry). Radial symmetry
of order n is denoted Dn-Symmetry. Circular symmetry
is C1 -symmetry (see Figure 3).
d.
c.
b.
a.
Fig. 3. Examples of symmetries: a) C 8 -symmetry b) mirror-
symmetry c) D 8 -symmetry d) circular symmetry.
B. Studies of Symmetry In Computer Vision
Detection of symmetry in images has been widely stud-
ied; with respect to circular (radial) symmetries [6], [29]
and with respect to mirror symmetries [22], [26]. Transformation
of the symmetry detection problem to a pattern
matching problem introduces efficient algorithms for detection
of mirror and rotational symmetries and the location
of symmetry axes [3], [1]. These algorithms assume noise
detect symmetry, if exists, on a global scale.
As an intrinsic characteristic of objects and shapes, symmetry
has been used to describe and recognize shapes and
objects both on a global scale [17], [21] and as a local feature
Symmetrical features of images have
been exploited for better image compression [20]. Symmetrical
descriptions of shapes and the detection of symmetrical
features of objects are useful in guiding shape matching,
model-based object matching and object recognition [27],
[29]. Reconstruction of 3D objects has also been implemented
using symmetry as a constraint [31], [24]. More
recently, symmetry has been used to discriminate textures
[9] and has been used in guiding robot grasping [7].
Considerable work has been done on skewed symmetries
including detection and exploiting them in the reconstruction
of 3D structure [26], [27], [18], [14], [28].
far, symmetry has been treated as a binary feature:
either it exists or it does not exist. The approach to symmetry
as a continuous feature is novel, although several
early studies have approached the question of measuring
symmetry: In an early work, Gr-unbaum [15] reviews methods
of geometrically measuring symmetry of convex sets.
Yodogawa [33] has presented an evaluation of symmetry
(namely "Symmetropy") in single patterns which uses information
theory to evaluate the distribution of symmetries
in a pattern. Marola [22] presents a coefficient of
mirror-symmetry with respect to a given axis where global
mirror-symmetry is found by roughly estimating the axis
location and then fine tuning the location by minimizing
the symmetry coefficient. Gilat [13], Hel-Or et.al.[16] and
Avnir et.al. [5] present the idea of a Measure of Chirality
(a measure of deviation from mirror-symmetry). Similar
to Marola, Gilat's chirality measure is based on minimizing
the volume difference between the object and it's reflection
through a varying plane of reflection. Hel-Or et al. present
a measure of chirality for 2D objects based on rotational
effects of chiral bodies on the surround.
These symmetry detection and evaluation methods are
each limited to a certain type of symmetry (mirror or circular
symmetry). In this paper we introduce the notion
of continuous symmetry and present a general continuous
measure the symmetry distance for evaluating all types of
symmetries in any dimension.
II. A Continuous Symmetry Measure - Definition
We define the Symmetry Distance (SD) as a quantifier
of the minimum 'effort' required to transform a given
shape into a symmetric shape. This 'effort' is measured by
the mean of the square distances each point is moved from
its location in the original shape to its location in the symmetric
shape. Note that no a priori symmetric reference
shape is assumed.
Denote
by\Omega the space of all shapes of a given dimension,
where each shape P is represented by a sequence of n points
i=0 . We define a metric d on this space as follows:
d
This metric defines a distance function between every two
shapes in \Omega\Gamma
We define the Symmetry Transform of a shape P as
the symmetric shape -
closest to P in terms of metric d.
The Symmetry Distance (SD) of a shape P is defined
as the distance between P and it's Symmetry Transform:
The SD of a shape
i=0 is evaluated by finding the
symmetry transform -
of P and computing:
This definition of the Symmetry Distance implicitly implies
invariance to rotation and translation. Normalization
of the original shape prior to the transformation additionally
allows invariance to scale (Figure 4). We normalize by
scaling the shape so that the maximum distance between
points on the contour and the centroid is a given constant
(in this paper all examples are given following normalization
to 10). The normalization presents an upper bound on
the mean squared distance moved by points of the shape.
Thus the SD value is limited in range, where SD=0 for
perfectly symmetric shapes. The general definition of the
Symmetry Distance enables evaluation of a given shape
for different types of symmetries (mirror-symmetries, rotational
symmetries etc). Moreover, this generalization allows
comparisons between the different symmetry types,
and allows expressions such as "a shape is more mirror-symmetric
than C 2 -symmetric".P'
c.
a. b.
symmetry transform
d.
normalizeFig. 4. Calculating the Symmetry Distance of a shape:
a) Original shape fP g.
b) Normalized shape fP 0
2 g, such that maximum distance
to the center of mass is a given constant (10).
c) Applying the symmetry transform to obtain a symmetric
shape f -
P2g.
d)
An additional feature of the Symmetry Distance is that
we obtain the symmetric shape which is 'closest' to the
given one, enabling visual evaluation of the SD.CCC
Mirror
a.
b. c. d. e.
Fig. 5. Symmetry Transforms of a 2D polygon.
a) 2D polygon and its Symmetry Transform with respect to
c) C 3 -symmetry
d) C6-symmetry 2.53).
An example of a 2D polygon and it's symmetry transforms
and SD values are shown in Fig. 5. Note that the
shape in Fig. 5e is the most similar to the original shape
Fig. 5a and, indeed, its SD value is the smallest. In the
next Section we describe a geometric algorithm for deriving
the Symmetry Transform of a shape. In Section IV
we deal with the initial step of representing a shape by a
collection of points.
III. Evaluating the Symmetry Transform
In this Section we describe a geometric algorithm for
deriving the Symmetry Transform of a shape represented
by a sequence of points fP i g n\Gamma1
i=0 . In practice we find the
Symmetry Transform of the shape with respect to a given
symmetry group. For simplicity and clarity of explanation,
we describe the method by using some examples. Mathematical
proofs and derivations can be found in Appendix A.
We first present the algorithm for Cn-symmetry and later
generalize it to any finite symmetry group.
Following is a geometrical algorithm for deriving the
symmetry transform of a shape P having n points with
respect to rotational symmetry of order n (Cn -symmetry).
This method transforms P into a regular n-gon, keeping
the centroid in place.
Algorithm for finding the Cn-symmetry transform:
1. Fold the points fP i g n\Gamma1
i=0 by rotating each point P i
counterclockwise about the centroid by 2-i=n radians

Figure

6b).
2. Let -
P 0 be the average of the points f ~
ure 6c).
3. Unfold the points, obtaining the Cn -symmetric points
i=0 by duplicating -
rotating clockwise
about the centroid by 2-i=n radians (Figure 6d).
d.
a. b. c.
~
~
~
Fig. 6. The C 3 -symmetry Transform of 3 points.
a) Original 3 points fP i
into f ~
c) Average f ~
obtaining -
~
d) Unfold the average point obtaining f -
The centroid ! is marked by \Phi.
The set of points f -
i=0 is the symmetry transform of the
points
i=0 . i.e. they are the Cn -symmetric configuration
of points closest to fP i g n\Gamma1
i=0 in terms of the metric
d defined in Section II (in terms of the average distance
squared). Proof is given in Appendix A.
The common case, however, is that shapes have more
points than the order of the symmetry. For symmetry of
order n, the folding method can be extended to shapes
having a number of points which is a multiple of n. A 2D
shape P having qn points is represented as q sets fS r g q\Gamma1
of n interlaced points S
(see discussion in


Appendix

C). The Cn -symmetry transform of P (Figure 7)
is obtained by applying the above algorithm to each set of
points seperately, where the folding is performed about
the centroid of all the points
a. b.
Fig. 7. Geometric description of the C 3 -symmetry transform
for 6 points.
The centroid ! of the points is marked by \Phi.
a) The original points shown as 2 sets of 3 points:
g.
b) The obtained C 3 -symmetric configuration.
The procedure for evaluating the symmetry transform for
mirror-symmetry is similar: Given a shape having
points we divide the points into q pairs of points (see Appendix
C) and given an initial guess of the symmetry axis,
we apply the folding/unfolding method as follows (see Figure
Algorithm for finding the mirror-symmetry transform:
1. for every pair of points fP
(a) fold - by reflecting across the mirror symmetry axis
obtaining f ~
g.
(b) average - obtaining a single averaged point -
(c) unfold - by reflecting back across the mirror symmetry
axis obtaining f -
g.
2. minimize over all possible axes of mirror-symmetry.
The minimization performed in step 2 is, in practice, replaced
by an analytic solution (see Appendix B).
~
a. b.
mirror axis
c.
mirror axis
mirror axis
~
~
origin
origin
origin
Fig. 8. The mirror-symmetry transform of a single pair of points
for angle ', where the centroid of the shape is assumed to
be at the origin.
a) The two points fP are folded to obtain f ~
g.
b) Points ~
P0 and ~
are averaged to obtain -
P0 .
c) -
P1 is obtained by reflecting -
P0 about the symmetry axis.
This method extends to any finite point-symmetry
group G in any dimension, where the folding and unfolding
are performed by applying the group elements about the
centroid (see derivations in Appendix A):
Given a finite symmetry group G (having n elements)
and given a shape P represented by
the symmetry transform of the shape with respect to G-
symmetry is obtained as follows:
Algorithm for finding the G-symmetry transform:
1. The points are divided into q sets of n points.
2. For every set of n points:
(a) The points are folded by applying the elements of
the G-symmetry group.
(b) The folded points are averaged, obtaining a single
averaged point.
(c) The averaged point is unfolded by applying the inverse
of the elements of the G-symmetry group. A
G-symmetric set of n points is obtained.
3. The above procedure is performed over all possible
orientations of the symmetry axis and planes of G.
Select that orientation which minimizes the Symmetry
Distance value. As previously noted, this minimization
is analytic in 2D (derivation is given in Appendix
but requires an iterative minimization process
in 3D (except for the 3D mirror-symmetry group
where a closed form solution has been derived [35]).
Thus, the Symmetry Distance of a shape may be evaluated
with respect to any finite symmetry group. One
may consider as the 'appropriate' symmetry of a shape,
that symmetry group which minimizes the Symmetry Dis-
tance. A minimization over all symmetry groups can be
applied, however, minimization over a finite number of low
order groups usually suffices (in 2D minimization over mirror
and prime-ordered rotational symmetries is sufficient.
Since evaluation of the Symmetry Distance in 2D is ana-
lytical, this minimization is inexpensive).
IV. Point Selection for Shape Representation
As symmetry has been defined on a sequence of points,
representing a given shape by points must precede the application
of the symmetry transform. Selection of points3P
PFig. 9. When measuring symmetry of shapes inherently created
from points we represent the shape by these points.
influences the value of SD and depends on the type of object
to be measured. If a shape is inherently created from
points (such as a graph structure or cyclically connected
points creating a polygon) we can represent a shape by
these points (Figure 9). This is the case when analysing
symmetry of molecules ([37], [35]). There are several ways
to select a sequence of points to represent continuous 2D
shapes. One such method is selection at equal distances -
the points are selected along the shape's contour such that
the curve length between every pair of adjacent points is
equal

Figure

10).l
l6
l6
Fig. 10. Point selection by equal
distance: points are selected
along the contour at equal distances
in terms of curve length.
In this example six points are
distributed along the contour
spaced by 1of the full contour
length.
In many cases, however, contour length is not a meaningful
measure, as in noisy or occluded shapes. In such
cases we propose to select points on a smoothed version of
the contour and then project them back onto the original
contour. The smoothing of the continuous contour is performed
by moving each point on the continuous contour to
the centroid of its contour neighborhood. The greater the
size of the neighborhood, the greater is the smoothing (see

Figure

11). The level of smoothing can vary and for a high
level of smoothing, the resulting shape becomes almost a
circle about the centroid [25]. In this case, equal distances
on the circular contour is equivalent to equal angles about
the center. For maximum smoothing we, therefore, use
selection at equal angles (Figure 12) where points are selected
on the original contour at equal angular intervals
around the centroid. For further details on the selection of
points by smoothing see [34].
V. Symmetry of Occluded Shapes - Center of
Symmetry
As described in Section IV, a shape can be represented
by points selected at regular angular intervals about the
centroid. Angular selection of points about a point other
than the centroid will give a different symmetry distance
value. We define the center of symmetry of a shape
as that point in the 2D plane about which selection at
equal angles gives the minimum symmetry distance value
(Fig. 13). Intuitively, the center of symmetry is that point
about which rotation of the shape aligns it as close as possible
with itself (in terms of the mean squared distances).
When a symmetric shape is complete the center of symmetry
coincides with the centroid of the shape. However,
the center of symmetry of truncated or occluded objects
does not align with its centroid but is closer to the centroid
of the complete shape. Thus the center of symmetry
of a shape is robust under truncation and occlusion.
To locate the center of symmetry, we use an iterative
procedure of gradient descent that converges from the centroid
of an occluded shape to the center of symmetry. Denote
by center of selection, that point about which points
are selected using selection at equal angles. We initialize
the iterative process by setting the centroid as the cen-
c. d. e. f.
a. b.
g. h. i. j.
Fig. 11. Selection by smoothing
a) Original continuous contour.
b) Points are selected at equal distances along the contour.
c-f) The smoothed shape is obtained by averaging neighboring
points of (b). The amount of smoothing depends on the
size of the neighborhood. The smoothed shapes (c-f) are obtained
when neighborhood includes 5,10,15 and 20 percent of
the points, respectively.
g-j) The sampling of points on the original shape using the
smoothed shapes (c-f) respectively. Notice that fewer points
are selected on the "noisy" part of the contour.2p
Fig. 12. Selection at equal angles:
points are distributed along
the contour at regular angular
intervals around the centroid.
Fig. 13. An occluded shape with sampled
points selected at equal angles
about the center of symmetry
(marked by \Phi). The symmetry
distance obtained using these
points is smaller than the symmetry
distance obtained using points
selected at equal angles about the
centroid (marked by +).
a. b. c.
Fig. 14. Reconstruction of an occluded shape.
a) Original occluded shape, its centroid (+) and its center of
symmetry(\Phi).
b,c) The closest C 5 -symmetric shape using angular selection
about the centroid (b) and about the center of symmetry (c).
Selection about the centroid gives a featureless shape, while
selection about the center of symmetry yields a more meaningful
shape.
ter of selection. At each step we compare the symmetry
value obtained from points selected at equal angles about
the center of selection with the symmetry value obtained
by selection about points in the center of selection's immediate
neighborhood. That point about which selection
at equal angles gives minimum symmetry value, is set to
be the new center of selection. If the center of selection
does not change, the neighborhood size is decreased. The
process is terminated when neighborhood size reaches a
predefined minimum size. The center of selection at the
end of the process is taken as the center of symmetry.
In the case of occlusions (Figure 14), the closest symmetric
shape obtained by angular selection about the center of
symmetry is visually more similar to the original than that
obtained by angular selection about the centroid. We can
reconstruct the symmetric shape closest to the unoccluded
shape by obtaining the symmetry transform of the occluded
shape using angular selection about the center of symmetry
(see Figure 14c). In Figure 15 the center of symmetry
and the closest symmetric shapes were found for several
occluded flowers.
The process of reconstructing the occluded shape can be
improved by altering the method of evaluating the symmetry
of a set of points. As described in Section III, the
symmetry of a set of points is evaluated by folding, averaging
and unfolding about the centroid of the points. We
alter the method as follows:
1. The folding and unfolding (steps 1 and 3) will be
performed about the center of symmetry rather than
about the centroid of the points.
2. Rather than averaging the folded points (step 2), we
apply other robust clustering methods. In practice we
average over the folded points, drop the points farthest
from the average and then reaverage (see Figure 16).
Intuitively, the robust clustering causes the reconstruction
to be strongly influenced by contour points on the
unoccluded portion of the shape while eliminating the influence
of the points on the contour representing the truncated
or occluded portion of the shape.
The improvement in reconstruction of an occluded shape
is shown in Figure 17. This method improves both shape
and localization of the reconstruction. Assuming that the
original shape was symmetric, this method can reconstruct
Fig. 15. Reconstruction of Occluded objects.
a) A collection of occluded asymmetric flowers.
b) Contours of the occluded flowers were extracted manually.
c) The closest symmetric shapes and their center of symmetry.
d) The center of symmetry of the occluded flowers are marked
by '+'.
b.
a. c. d.
Fig. 16. Improving the averaging of folded points
a) An occluded shape with points selected using angular selection
about the center of symmetry (marked as \Phi).
b) A single set (orbit) of the selected points of a) is shown.
c) folding the points about the centroid (marked as +), points
are clustered sparsely.
d) folding the points about the center of symmetry, points are
clustered tightly. Eliminating the extremes (two farthest points)
and averaging results in a smaller averaging error and better re-construction

an occluded shape very accurately.
VI. Symmetry of Points with Uncertain
Locations
In most cases, sensing processes do not have absolute
accuracy and the location of each point in a sensed pattern
can be given only as a probability distribution. Given
sensed points with such uncertain locations, the following
properties are of interest:
ffl The most probable symmetric configuration represented
by the sensed points.
ffl The probability distribution of symmetry distance values
for the sensed points.
A. The Most Probable Symmetric Shape

Figure

18a shows a configuration of points whose locations
are given by a normal distribution function. The dot
represents the expected location of the point and the rectangle
represents the standard deviation marked as rectangles
having width and length proportional to the standard
deviation. In this section we briefly describe a method
of evaluating the most probable symmetric shape under
the Maximum Likelihood criterion [12] for a given set of
measured points (measurements). Detailed derivations and
proofs are given in [38]. For simplicity we describe the
method with respect to Cn -symmetry. The solution for
mirror symmetry or any other symmetry is similar (see
[38]).
Given n ordered points in 2D whose locations are given
as normal probability distributions with expected location
covariance matrix
we find the Cn -symmetric configuration
of points at locations f -
0 which is optimal under the
Maximum Likelihood criterion [12].
Denote by ! the centeroid of the most probable Cn -
symmetric set of locations -
. The point
is dependent on the location of the measurements
and on the probability distribution associated with them
is positioned at that point about which
the folding (described below) gives the tightest cluster of
points with small uncertainty (small s.t.d. We assume for
the moment that ! is given (a method for finding ! is derived
in [38]). We use a variant of the folding method which
was described in Section III for evaluating Cn -symmetry of
a set of points:
1. The n measurements are folded by
a. b. c.
Fig. 17. Improving the reconstruction
The original shape is shown as a dashed line and the reconstructed
shape as a solid line.
a) The closest symmetric shape using angular selection about
the centroid.
b) The closest symmetric shape using angular selection about
the center of symmetry.
c) The closest symmetric shape using angular selection about
the center of symmetry and robust clustering.
~
~
~ ~
a. b.
402Fig. 18. Folding measured points.
a) A configuration of 6 measuremented points . The
dot represents the expected location of the point. The rectangle
represents the standard deviation marked as rectangles having
width and length proportional to the standard deviation.
Each measurement Q i was rotated by 2-i=6 radians about
the centroid of the expected point locations (marked as '+')
obtaining measurement ~
a. b. c. d. e.
Fig. 19. The most probable symmetric shape.
a) A configuration of 6 measured points.
b-e) The most probable symmetric shapes with respect to b)
C2-symmetry.
c) C 3 -symmetry.
d) C 6 -symmetry.
mirror-symmetry.
rotating each measurement Q i by 2-i=n radians about
the point !. A new set of measurements
~
obtained (see Figure 18b).
2. The folded measurements are averaged using a
weighted average, obtaining a single point -
Averaging
is done by considering the n folded measurements
~
measurements of a single point and -
the most probable location of that point under
the Maximum Likelihood criterion.
~
~
3. The "average" point -
unfolded as described in
Section III obtaining points f -
i=0 which are perfectly
Cn -symmetric.
When we are given we find the
most probable Cn -symmetric configuration of points, similar
to the folding method of Section III. The m measurements
i=0 , are divided into q interlaced sets of n measurements
each, and the folding method as described above
is applied seperately to each set of measurements. Derivations
and proof of this case is also found in [38].
Several examples are shown in Figure 19, where for a
given set of measurements, the most probable symmetric
shapes were found. Figure 20 shows an example of varying
the probability distribution of the measurements on the
resulting symmetric shape.
a. b. c. d. e.
Fig. 20. The most probable C 3 -symmetric shape for a set
of measurements after varying the probability distribution
and expected locations of the measurements.
a-c) Changing the uncertainty (s.t.d.) of the measurements.
d-e) Changing both the uncertainty and the expected location
of the measurements.
B. The Probability Distribution of Symmetry Values

Figure

21a displays a Laue photograph [2] which is an in-
terefrence pattern created by projecting X-ray beams onto
crystals. Crystal quality is determined by evaluating the
symmetry of the pattern. In this case the interesting feature
is not the closest symmetric configuration, but the
probability distribution of the symmetry distance values.
Consider the configuration of 2D measurements given in

Figure

18a. Each measurement Q i is a normal probability
distribution We assume the centroid of
the expectation of the measurements is at the origin. The
probability distribution of the symmetry distance values
of the original measurements is equivalent to the probability
distribution of the location of the "average" point ( -
given the folded measurements as obtained in Step 1 and
Step 2 of the algorithm in Section VI-A. It is shown in
[38] that this probability distribution is a - 2 distribution
of order n \Gamma 1. However, we can approximate the distribution
by a gaussian distribution. Details of the derivation
are given in [38].
In

Figure

21 we display distributions of the symmetry
distance value as obtained for the Laue photograph given
in

Figure

21a. In this example we considered every dark
patch as a measured point with variance proportional to
the size of the patch. Thus in Figure 21b the rectangles
which are proportional in size to the corresponding dark
patches of Figure 21a, represent the standard deviation of
the locations of point measurements. Note that a different
analysis could be used in which the variance of the measurement
location is taken as inversely proportional to the
size of the dark patch.
In

Figure

22 we display distributions of the symmetry
distance value for various measurements. As expected, the
distribution of symmetry distance values becomes broader
as the uncertainties (the variance of the distribution) of the
measurements increase.
a. b.
c.
Probability
Symmetry Value
Fig. 21. Probability distribution of symmetry values
a) Interference pattern of crystals.
Probability distribution of point locations corresponding to a.
c) Probability distribution of symmetry distance values with respect
to C 10 -symmetry was evaluated as described in the text.
Expectation
c
d
a
Probability
DensityFig. 22. Probability distribution of the symmetry distance value
as a function of the variance of the measured points.
a-d) Some examples of configurations of measured points.
Probability distribution of symmetry distance values with
respect to C 6 -symmetry for the configurations a-d.
Reflection plane
Image plane
Fig. 23. Selecting points on the 3D
object (a 2D analog is shown).
For a possible reflection plane, the
plane perpendicular to it is sam-
pled. Elevations are recomputed on
the object relative to the sampling
plane.
VII. Application to Images
A. Finding Orientation of Symmetric 3D Objects
When dealing with images, we let pixel values denote
elevation, and consider an image as a 3D object on which
we can measure 3D symmetries. We applied the SD to find
orientation of symmetric 3D objects by finding their 3D
mirror-symmetry. The 3D shape is represented by a set of
3D points: for a possible reflection plane, the plane perpendicular
to it is sampled. Each sampled points is projected
onto the 3D object and its elevation is recomputed relative
to the sampling plane (Figure 23). The symmetry value for
3D mirror-symmetry is evaluated using the projected sampling
points. The final reflection plane of the 3D object
is determined by minimizing the symmetry value over all
possible reflection planes. In practice only feasible symmetry
planes were tested (i.e. planes which intersect the 3D
image) and a gradient descent algorithm was used to increase
efficiency of convergence to the minimum symmetry
value (the SD). Examples are shown in Figure 24, where a
symmetric 3D object is rotated into a frontal vertical view
after the reflection plane was found.
B. Using a Multiresolution Scheme
In many images the process of finding the reflection plane
did not converge to the correct solution, i.e. the process
converged to a local minima due to the sensitivity of the
symmetry value to noise and digitization errors. To overcome
this problem we introduced a multiresolution scheme,
where an initial estimation of the symmetry transform is
obtained at low resolution (see Figure 25) and is fine tuned
using high resolution images. The solution obtained for
the low resolution image is used as an initial guess of the
solution for the high resolution image. The low resolution
images were obtained by creating gaussian pyramids [11].
C. Finding Locally symmetric Regions
Most images cannot be assumed to have a single global
symmetry, but contain a collection of symmetric and almost
symmetric patterns (be they objects or background).
We aim to locate these local symmetries and segment the
symmetrical objects from the background. The following
three staged process is used to extract locally symmetric
regions in images.
1. The first stage locates symmetry focals - those points
about which the image is locally symmetric. Several
methods can be used to find the symmetry focals ([29],
for example). We used a variant of the multiresolution
method presented in [36] for sampling and transmitting
an image, which uses a simple model of the human
visual attention mechanism.
We used the Quad Tree [30] structure which is a hierarchical
representation of an image, based on recursive
subdivisions of the image array into quadrants. The
process of locating symmetry focals builds a sequence
of quad trees and a sequence of corresponding divisions
of the image into quadrants. The process is initialized
by setting the current quad tree to a single root node
(corresponding to the whole image). At each step all
quadrants of the image corresponding to the leaves of
the quad tree are tested for a given "interest" func-
a. b.
c. d.
Fig. 24. Applying the SD with respect to 3D mirror-symmetry
in order to find orientation of a 3D object.
a,c) original depth maps.
b,d) The symmetry reflection plane has been found and the
image rotated to a frontal vertical view.
tion. That node of the quad tree that corresponds to
the quadrant with highest "interest" value is selected.
The current quad tree is expanded by creating the son
nodes of the selected node and accordingly, subdividing
the image quadrant associated with the selected
node. Several steps of this procedure are shown in Figure
26. In our case the "interest" function was chosen
as to be a function of the Symmetry Distance value
obtained for the image quadrant. Thus the procedure
described focuses onto regions of high symmetry content
and finds symmetry focals. In practice, the "in-
terest" function also took into account the busyness of
the image quadrant, thus regions that had low busyness
values (i.e. the grey-scale values were almost con-
stant) gave low "interest" values although they were
highly symmetric (and gave low Symmetry Distance
values). In Figure 27b, a mirror-symmetry focal and
an associated reflection plane (passing through the fo-
cal) were found.
2. Given a symmetry focal and a reflection plane, a symmetry
map of the image is created as follows: the original
image is sampled at points which are pairwise symmetric
with respect to the given reflection plane. The
symmetry distance value obtained using the folding
method described in Section III for each pair of sam-
a. b.
c. d.
Fig. 25. Using multiresolution to find symmetry.
The grey-level image is treated as a depth map and 3D mirror-
symmetry is computed. The computed symmetry plane is used
to bring the image into a frontal vertical view.
a) Original image.
b) Applying the mirror-symmetry transform on (a) does not find
correct reflection plane.
c) A low resolution image obtainined by convolving (a) with a
gaussian.
d) Applying the mirror-symmetry transform on the low resolution
image (c) gives a good estimation of the reflection plane
and face orientation.
e) Using the reflection plane found in (d) as an initial guess, the
process now converges to the correct symmetry plane.
pled points is recorded and marked in the symmetry
map at the location corresponding to the coordinates
of the sampled points. Thus the symmetry map displays
the "amount" of mirror-symmetry at every point
(with respect to the given reflection plane) where low
grey values denote low SD values (i.e. high symmetry
content) and high grey values denote high SD values
(i.e. low symmetry content) (Figure 27c).
3. Starting from the symmetry focals, regions are expanded
using "active contours" [19] to include compact
symmetric regions. The expansion is guided by
the symmetry map and continues as long as the pixels
included in the locally symmetric region do not
degrade the symmetry of the region more than a pre-defined
threshold (Figure 27d).
The process can be continued to extract several locally
symmetric regions, as shown in the example of Figure 28.
VIII. Conclusion
We view symmetry as a continuous feature and define
a Symmetry Distance (SD) of shapes. The general definition
of the Symmetry Distance enables a comparison
of the "amount" of symmetry of different shapes and the
"amount" of different symmetries of a single shape. Fur-
thermore, the SD is associated with the symmetric shape
which is 'closest' to the given one, enabling visual evaluation
of the SD. Several applications were described including
reconstruction of occluded shapes, finding face orientation
and finding locally symmetric regions in images. We
also described how we deal with uncertain data, i.e. with a
configuration of measurements representing the probability
distribution of point location. The methods described
here can be easily extended to higher dimensions and to
more complex symmetry groups. Further extensions will
deal with other symmetry classes such as planar symmetry
(including translatory symmetry and fractals). Additional
work has been done on evaluating reflective symme-
Fig. 26. Several steps in the process of finding symmetry focals.
A sequence of quad trees (bottom row) and the corresponding
recursive division of the image (top row) is created. The process
is initialized by creating a quad tree with a single root node
corresponding to the whole image (left). At each step all quadrants
of the image corresponding to the leaves of the quad tree
are tested for the "interest" function. The leaf of the quad tree
that corresponds to the quadrant with highest value (marked
in grey) is expanded to create the quad tree of the next step.
Three additional steps are shown.
a. b.
c. d.
Fig. 27. Applying the Multiresolution scheme to detect a
mirror-symmetric region
a) Original image.
b) A mirror-symmetry focal was found.
c) Symmetry map of image for the symmetry focal found in b).
d) Extracted locally symmetric region.
try (and chirality) of graph structures ([35]). The methods
described here have also been extended to deal with skewed
and projected mirror symmetries [39].


Appendix


I. Mathematical Proof of the Folding Method
Given a finite point symmetry group G, we assume without
loss of generality that G is centered at the origin (i.e.
every element of G leaves the origin fixed). Given an ordering
of the n elements of the G-symmetry group fg
I and given n general points P
we find n points -
and find a rotation matrix R
and translation vector w such that the points -
translated by ! and rotated by R form an ordered orbit
under G and bring the following expression to a minimum:
Since G has a fixed point at the origin and the centroid of
the orbit formed by the rotated and translated -
P i is a fixed
point under G, we can assume without loss of generality
that the translation vector w is the centroid of points -
The points -
translated by ! and rotated by R,
form an orbit of G, thus the following must be satisfied:
a. b.
c. d.
Fig. 28. Applying the Multiresolution scheme to find multiple
mirror-symmetric regions.
a) Original image.
b) The mirror-symmetry focals found.
c) Symmetry maps for each mirror-symmetry are merged into a single
image.
d) Extracted locally symmetric regions.
Using Lagrange multipliers with Equations 1-3 we minimize
the following:
are the Lagrange multipliers.
Setting the derivatives equal to zero we obtain:
and using the last constraint (Eq 2) we obtain:
i.e. the centroid of P coincides with the centroid
of -
(in terms of the symmetry distance
defined in Section I, the centroid of a configuration and the
centroid of the closest symmetric configuration is the same
for any point symmetry group G).
Noting that R t g i R for are isometries and
distance preserving, we have from the derivatives:
Expanding using the constraints we obtain:
or
The derivation of the rotation matrix R is given in the
next section, however, given R, the geometric interpretation
of Equation 6 is the folding method, as described in
Section III, proving that the folding method results in the
G-symmetric set of points closest to the given set.
The common case, however, is that shapes have more
points than the order of the symmetry. For symmetry of order
n, the folding method can be extended to shapes having
a number of points which is a multiple of n. Given
points (i.e. q sets of n points) fP j
we follow the above derivation and obtain a result similar
to that given in Equation 6. For each set of n points, i.e.
i is the centroid of all m
points. The geometric interpretation of Equation 7 is the
folding method, as described in Section III for the case of
a shape represented by
The folding method for the cases where the number of
points is not a multiple of the number of elements in G is
not derived here. Details of this case can be found in [37].
II. Finding the Optimal Orientation in 2D
The problem of finding the minimizing orientation is irrelevant
for the Cn symmetry groups since every element g
of these groups is a rotation and R t g. In the case of
Cn -symmetry groups, R is usually taken as I (the identity
matrix). We derive here a solution for the orientation in
the case where G is a Dn symmetry group.
The 2n elements of the Dn-symmetry group can be
described as the n elements
n (where R i
n is the rotation of 2-i=n
radians about the origin) and the n elements obtained by
applying a reflection R f on each of these elements:
n .
We denote the orientation of the symmetry group as the
angle ' between the reflection axis and the y axis. Thus
sin ' cos '
and the reflection operation R f is given by:
sin ' cos '
'' cos ' sin '
sin ' cos '
sin 2' cos 2'
Without loss of generality, we assume the centroid w is at
the origin Following Appendix I.B, we minimize
Equation 1 over '. Using Equation 3 and noting that R t g i R
are distance preserving, we minimize the
following over ':
Substituting Equation 6 we minimize:
Rearranging and noting that R t g t
we minimize:
\Gamman
Denote by x the coordinates of the point g t
i\Gamman P i for Taking
the derivative of Equation 8 with respect to ' we obtain:
tan
which is an analytic solution for the case of optimal orientation
in 2D. In higher dimensions, however, no analytic
solution was found and a minimization procedure is used
(except for the mirror symmetry group in 3D where a closed
form solution is given - see [35]).
III. Dividing Points of a Shape into sets
As described in Section III, when measuring Cn -
symmetry of a shape represented by a multiple of n points,
the points must be divided into sets of n points. In gen-
eral, this problem is exponential, however when the points
are ordered along a contour, as in our case, the possible
divisions into sets are more restricted since the ordering is
preserved under the symmetry transform of a shape. For
example, points in 2D along the contour of a Cn -symmetric
shape form orbits which are interlaced. An example is
shown in Figure 29a for C 3 -symmetry, where 3 interlaced
orbits are shown marked as ffl, ffi and 2. Thus, given a
set of ordered points there is only one possible
division of the points into q sets of n points such that
the ordering is preserved in the symmetric shape - the q
sets must be interlaced (as was shown in Figure 7). In
the case of Dn-symmetry (rotational and reflective symmetry
of order n) the
orbits which are interlaced and partially inverted to account
for the reflection symmetry. An example is shown in

Figure

29b for D 4 -symmetry where instead of 3 interlaced
every other run is inverted:
ffl. Thus, given a set of
ordered points there are possible division of the
points.
a b.
Fig. 29. Dividing m selected
points into interlaced
sets: a) Cn -
ity. b) Dn-symmetry -
m=2n possibilities



--R

Congruence, similarity and symmetries of geometric objects.

On symmetry detection.
Symmetry information and memory for patterns.
Quantifying the degree of molecular shape deformation.
Recognition of local symmetries in gray value images by harmonic functions.
Grasping visual symmetry.
Shape description using weighted symmetric axis features.
Texture discrimination by local generalized symmetry.
Smoothed local symmetries and their implementation.
The Laplacian pyramid as a compact image code.
Probability and Statistics.
Chiral coefficient - a measure of the amount of structural chirality
Analyzing skewed symmetry.
Measures of symmetry for convex sets.
Characterization of right handed and left handed shapes.
Visual pattern recognition by moment invariants.
Recovery of the three-dimensional shape of an object from a single view
Snakes: active contour models.
Application of the karhunen-loeve procedure for the characterization of human faces
MIT press
On the detection of the axes of symmetry of symmetric and almost symmetric planar images.
Symmetry Groups and their Applications.

A theory of multiscale

Model based matching using skewed symmetry information.
On characterizing ribbons and finding skewed sym- metries
Robust detection of facial features by generalized symmetry.
The quadtree and related hierarchical data structures.
Symmetry seeking models and object reconstruction.
Princeton Univ.
Symmetropy, an entropy-like measure of visual symmetry
Computational Aspects of Pattern Characterization - Continuous Symmetry
Continuous symmetry measures
Attentive transmission.
Continuous symmetry measures II: Symmetry groups and the tetrahedron.
Symmetry of fuzzy data.
3D symmetry from 2D data.
--TR

--CTR
Dinggang Shen , Horace H. S. Ip , Kent K. T. Cheung , Eam Khwang Teoh, Symmetry Detection by Generalized Complex (GC) Moments: A Close-Form Solution, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.5, p.466-476, May 1999
P. J. Sanz , J. M. Iesta , A. P. Del Pobil, Planar Grasping Characterization Based on Curvature-Symmetry Fusion, Applied Intelligence, v.10 n.1, p.25-36, January 1999
Aurlien Martinet , Cyril Soler , Nicolas Holzschuch , Franois X. Sillion, Accurate detection of symmetries in 3D shapes, ACM Transactions on Graphics (TOG), v.25 n.2, p.439-464, April 2006
S. J. Tate , G. E. M. Jared , K. G. Swift, Detection of symmetry and primary axes in support of proactive design for assembly, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.151-158, June 08-11, 1999, Ann Arbor, Michigan, United States
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
M. Li , F. C. Langbein , R. R. Martin, Detecting approximate incomplete symmetries in discrete point sets, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
Kuo-Liang Chung , Jhin-Sian Lin, Faster and more robust point symmetry-based K-means algorithm, Pattern Recognition, v.40 n.2, p.410-422, February, 2007
Mu-Chun Su , Chien-Hsing Chou, A Modified Version of the K-Means Algorithm with a Distance Based on Cluster Symmetry, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.6, p.674-680, June 2001
Michael Kazhdan , Thomas Funkhouser , Szymon Rusinkiewicz, Symmetry descriptors and 3D shape matching, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
Allen Y. Yang , Kun Huang , Shankar Rao , Wei Hong , Yi Ma, Symmetry-based 3-D reconstruction from perspective images, Computer Vision and Image Understanding, v.99 n.2, p.210-240, August 2005
H. L. Zou , Y. T. Lee, Skewed mirror symmetry detection from a 2D sketch of a 3D model, Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, November 29-December 02, 2005, Dunedin, New Zealand
Alexander V. Tuzikov , Olivier Colliot , Isabelle Bloch, Evaluation of the symmetry plane in 3D MR brain images, Pattern Recognition Letters, v.24 n.14, p.2219-2233, October
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
Niloy J. Mitra , Leonidas J. Guibas , Mark Pauly, Partial and approximate symmetry detection for 3D geometry, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
David Milner , Shmuel Raz , Hagit Hel-Or , Daniel Keren , Eviatar Nevo, A new measure of symmetry and its application to classification of bifurcating structures, Pattern Recognition, v.40 n.8, p.2237-2250, August, 2007
Hanzi Wang , David Suter, Using symmetry in robust model fitting, Pattern Recognition Letters, v.24 n.16, p.2953-2966, December
Joshua Podolak , Philip Shilane , Aleksey Golovinskiy , Szymon Rusinkiewicz , Thomas Funkhouser, A planar-reflective symmetry transform for 3D shapes, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
Nahum Kiryati , Yossi Gofman, Detecting Symmetry in Grey Level Images: The Global Optimization Approach, International Journal of Computer Vision, v.29 n.1, p.29-45, Aug. 1998
Wei Hong , Allen Yang Yang , Kun Huang , Yi Ma, On Symmetry and Multiple-View Geometry: Structure, Pose, and Calibration from a Single Image, International Journal of Computer Vision, v.60 n.3, p.241-265, December 2004
Computational Model for Periodic Pattern Perception Based on Frieze and Wallpaper Groups, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.3, p.354-371, March 2004
Kenichi Kanatani, Geometric Information Criterion for Model Selection, International Journal of Computer Vision, v.26 n.3, p.171-189, Feb./March 1998
Focus-of-Attention from Local Color Symmetries, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.7, p.817-830, July 2004
Toby P. Breckon , Robert B. Fisher, Amodal volume completion: 3D visual completion, Computer Vision and Image Understanding, v.99 n.3, p.499-526, September 2005
local symmetry;fuzzy shapes;face orientation;occlusion;similarity measure;symmetry distance;symmetry