Symmetry detection and approximation

Abstract

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.

In dieser Arbeit werden zwei eng miteinander verwandte Probleme betrachtet. Zum Einen wird untersucht, wie die Symmetriegruppe eines zweidimensionalen Objektes bestimmt werden kann. Wird ein Objekt so dargestellt, dass es mit Hilfe eines Computerprogramms untersucht werden kann, so kann es passieren, dass die Symmetrien des ursprünglichen Objekts in der Darstellung des Objekts nicht mehr vorhanden sind. Die Algorithmen, die in dieser Arbeit entwickelt werden, bestimmen die Symmetriegruppe eines Objektes auch dann, wenn die Darstellung des Objektes selber nicht mehr symmetrisch ist. Abhängig von der Darstellung des Objekts werden verschiedene Algorithmen vorgestellt und untersucht. Eine Möglichkeit ist, das Objekt mit Hilfe eines Graustufenbilds (z.B. als .jpg oder .png Datei) darzustellen. In diesem Fall wird das Bild mit Hilfe der diskreten Fourier-Transformation analysiert und so die Symmetriegruppe ermittelt. Die Fourier-Transformation zerlegt ein Signal in seine Grundschwingungen und kann daher verwendet werden, um periodische Strukturen zu erfassen. Diese Eigenschaft wird genutzt, indem die diskrete Fourier-Transformation auf das Graustufenbild angewendet und mit Hilfe der entdeckten periodischen Struktur in diesem Bild die Symmetriegruppe des dargestellten Objekts ermittelt wird. Der so entwickelte Algorithmus kann verwendet werden, um sowohl endliche als auch unendliche Symmetriegruppen zu ermitteln. Des Weiteren wird ein probabilistischer Ansatz verwendet, um die Symmetriegruppe eines Objekts zu ermitteln, wobei hier von der Repräsentation des Objekts als Punktemenge, Menge von Polygonzügen oder als Menge von parametrisierten Kurven ausgegangen wird. Die Grundidee dieses Algorithmus' ist, zwei Punkte zufällig aus der Punktmenge, die das Objekt repräsentiert, auszuwählen und dann die Transformation (Rotation oder Spiegelung) zu berechnen, die den einen Punkt auf den anderen abbildet. Im Raum der Transformationen wird dann eine Stimme für die ermittelte Transformation erzeugt. Dieses Vorgehen wird ausreichend oft wiederholt, so dass sich Cluster im Transformationsraum bilden. Die Anzahl der Cluster mit einer großen Anzahl von Stimmen entspricht der Anzahl der Symmetrien des Objekts und kann daher verwendet werden, um die Symmetriegruppe des dargestellten Objekts zu bestimmen. Mit Hilfe der beiden beschriebenen Ansätze werden jeweils Algorithmen entwickelt, die die Symmetriegruppe eines zweidimensionalen Objekts ermitteln, auch wenn die ursprünglichen Symmetrien des Objekts durch die Darstellung als Graustufenbild oder als Menge von geometrischen Objekten verloren gegangen sind, da beide Algorithmen robust gegenüber Störungen sind. Nachdem die ursprüngliche Symmetriegruppe eines Objekts, das durch eine Punktmenge repräsentiert wird, ermittelt wurde, ist die Konstruktion einer Punktmenge mit der ermittelten Symmetriegruppe ein weiteres interessantes Problem. Ist die so erzeugte symmetrische Menge eine gute Approximation der Menge, die das Objekt darstellt, so ist sie eine symmetrische Darstellung des ursprünglichen Objekts. Wir betrachten eine symmetrische Punktmenge als gute Approximation einer Eingabemenge, falls jeder Punkt dieser Menge in der epsilon-Umgebung eines Punktes der symmetrischen Punktmenge liegt, wobei diese Zuordnung bijektiv sein muss. Dieses Problem wurde von S.Iwanowski untersucht und als Epsilon-Symmetry Detection Problem (Epsilon-SD Problem) bezeichnet, wobei er das Problem als Entscheidungsproblem formuliert. Iwanowski zeigte in seiner Arbeit, dass das Epsilon-SD Problem im Allgemeinen NP-vollständig ist und für eingeschränkte Varianten in P liegt. Für einige dieser eingeschränkten Varianten werden in dieser Arbeit Polynomialzeitalgorithmen angegeben, die das zugehörige Optimisierungsproblem lösen. Ausserdem werden bisher noch nicht untersuchte eingeschränkte Varianten betrachtet und es werden Polynomialzeitalgorithmen entwickelt, die diese entscheiden. Das Epsilon-SD Problem kann dadurch eingeschränkt werden, dass nur Punktmengen als Eingabe erlaubt werden, deren Punkte weit auseinander liegen. Iwanowski zeigte in seiner Arbeit, dass das Epsolin-SD Problem in P ist, falls keine zwei Punkte der Menge einen Abstand kleiner als 8*Epsilon haben. In dieser Arbeit wird Iwanowkis Ergebnis verbessert, indem Polynomialzeitalgorithmen für Punktmengen angegeben werden, in denen keine zwei Punkte einen Abstand kleiner als 4(1+Delta)Epsilon haben, für alle Delta >0.