Claudia Dieckmann:
Symmetry Detection and Approximation
Kurzbeschreibung
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 two-dimensional 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 epsilon-neighborhood of a point in the symmetric point set. We ask this correspondence to be a bijection. This problem is called the epsilon-Symmetry Detection Problem (epsilon-SD problem).
The epsilon-SD problem was already studied by S. Iwanowski and he proved it to be NP-complete in general. For some restricted versions of the epsilon-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 epsilon-SD problem to be in P in the case where no two points have a distance smaller than 8*epsilon and proved it to be NP-complete in the case where the point set is at most epsilon/2-disjoint. We will improve this result by developing polynomial time algorithms for 4(1+delta)epsilon-disjoint point sets for each delta>0.