Ph.D. thesis : Symmetry Detection and Approximation
Advisor: Prof. Dr. Helmut Alt
In this thesis, we will present algorithms to solve the following two closely related
problems:
The first problem we will consider is to detect the symmetry group of a twodimensional
object even in the case where its representation is distorted by noise.
We will derive and analyze algorithms following different approaches in order to
solve this problem.
One approach is to use the discrete Fourier transform in order to detect the symmetry
group of the object. Here we assume the object to be represented by a gray-level
image. The discrete Fourier transform is helpful in finding periodic structures in an
input since it decomposes a signal into its fundamental frequencies. We will use this
property in order to derive an algorithm which applies the discrete Fourier transform
to the gray-level image and uses the result in order to determine the symmetry group
of the represented object. The algorithm can be used for detecting finite as well as
infinite symmetry groups.
Besides we will investigate a second method based on the probabilistic approach
which is also used for solving shape matching problems. For the algorithms based
on probabilistic methods we assume the object to be represented by a set of points,
a set of polygonal curves or a set of parametrized curves.
The basic idea of these algorithms is to randomly choose two points out of the
input set representing the object and compute the transformation (rotation or reflection)
mapping the one point to the other. A vote will be generated for the computed
transformation in transformation space. This procedure is repeated sufficiently often
until dominant clusters in transformation space arise. The number of clusters with
large numbers of votes refers to the number of symmetries of the object and thus
can be used in order to compute the symmetry group of the object represented by
the input set.
Both approaches described above result in algorithms which are robust against
noise. Thus they derive the correct answers even if the symmetries of the object got
lost during the process of computing its representation by a gray-level image or a set
of geometric objects, respectively.
After detecting the symmetry group of an object represented by a point set which
might be distorted by noise another interesting problem is to find a point set which is
symmetric with respect to the symmetries in the detected symmetry group and which is
a close approximation of the input point set. The aim is to restore the symmetries
which might have got lost during the process of representing the object in such a
way that it can be processed by a computer. We assume a symmetric point set to
be a close approximation of the input point set if each point of the (non-symmetric)
input point set lies in the ε-neighborhood of a point in the symmetric point set. We
ask this correspondence to be a bijection. This problem is called the ε-Symmetry
Detection Problem(ε-SD problem).
The ε-SD problem was already studied by S. Iwanowski and he proved it to be
NP-complete in general. For some restricted versions of the ε-SD problem Iwanowski
proved the decision problem to be in P. For those we will present polynomial time
algorithms solving the corresponding optimization problems. Additionally we will
present polynomial time algorithms for some restricted versions which were not considered
until now. One possible restriction is to only allow point sets which are
well-separated. Iwanowski proved the ε-SD problem to be in P in the case where
no two points have a distance smaller than 8 ε and proved it to be NP-complete in
the case where the point set is at most ε/2-disjoint. We will improve this result by
developing polynomial time algorithms for 4(1+δ)-disjoint point sets for each &delta > 0.