#### Ph.D. thesis : Symmetry Detection and Approximation

Claudia Dieckmann

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.