A texture is said to have a symmetry if there is a transformation such that the texture before transformation is matched with that after transformation on their overlapping region. Particularly, when such a transformation preserves distance, it is called an isometry. There are four kinds of isometries in the plane: translation, reflection, rotation and glide reflection. A texture is said to be regular if it has translation symmetries in at least two distinct directions. Given a regular texture, a collection of symmetries for the texture form a group. It is called the symmetry group for the texture. A mathematical analysis of these group shows that there are exactly seventeen different symmetry groups in the plane. A fundamental region is a smallest polygonal subregion of the texture that can reproduce the texture by applying the isometries for the texture to the region. Given a regular texture, the symmetry group for the texture and its fundamental region give a complete representation of the texture.
In this thesis, we propose an algorithm that classifies a digitized regular texture to identify the symmetry group for the texture and its fundamental region. Our algorithm mainly consists of two parts: motif analysis and symmetry group identification. A motif is a smallest parallelogramed subregion of a texture that can regenerate the texture by repetition. To obtain the motif, we first propose a distance matching function to effectively compute a set of equivalent points, called a lattice, that is spanned by two translations specifying the regular texture. This lattice is constructed by clustering and grouping the points. The motif is then specified by determining two vectors which span the lattice points dominantly.
The motif contains all symmetries for a texture because it can reproduce the texture by repetition. This characteristic makes it possible to only consider symmetries embedded in the motif to determine the symmetry group for the texture. Since a symmetry in the motif is a combination of reflection, rotation and glide reflection, we present algorithms that identify each of the symmetries in a systematic way. Finally, we give the classification diagrams to identify all symmetry groups. The fundamental region is easily identified by rearranging the motif with respect to the identified symmetries. For a texture of size m × n, our algorithm identifies the symmetry group for the texture and its fundamental region in O(mnlogmn)time.
주어진 텍스츄어(texture)가 변환(transformation)되어 자신과 겹치면, 그 텍스츄어는 대칭(symmetry)을 가진다고 한다. 이러한 대칭은 이차원 평면에서 전이 대칭(translational symmetry), 회전 대칭(rotational symmetry), 반사 대칭(reflection symmetry), 전이 반사 대칭(glide reflection symmetry)으로 구분되고 각각의 대칭을 나타내는 변환은 2차원 벡터로 표현된다. 만약 어떠한 텍스츄어가 서로 다른 두 방향으로 전이 대칭을 가지면, 그 텍스츄어를 반복 텍스츄어(regular texture)라고 한다. 반복 텍스츄어가 가지는 모든 대칭들은 수학적으로 그룹(group)을 형성하는데 이를 그 텍스츄어의 대칭 그룹(symmetry group)이라 하고, 17가지의 대칭 그룹만이 존재한다는 것이 알려져 있다. 텍스츄어의 기본영역(fundamental region)은 텍스츄어가 가지는 대칭들을 그 영역에 적용하여 원래 텍스츄어를 만들 수 있는 텍스츄어의 최소 부영역이다.
본 논문에서는 노이즈를 가지는 반복 텍스츄어의 대칭 그룹과 기본영역을 효율적으로 알아내는 알고리즘(algorithm)을 제시한다. 이 알고리즘은 크게 모티프(motif)해석과 대칭 그룹의 해석으로 나뉘어진다. 텍스츄어의 모티프는 반복하였을때, 원래 텍스츄어와 같은 텍스츄어를 생성할 수 있는 평행 사변형의 텍스츄어 부영역이다. 모티프를 얻기 위하여 본 논문에서는 거리 정합 함수(distance matching function)를 제시하고, 이를 이용하여 텍스츄어 상에서 상대적으로 같은 위치에 있는 점들을 효율적으로 계산하는 방법을 제시한다. 텍스츄어의 모티프는 이러한 점들을 가장 많이 스팬(span)하는 두전이 벡터에 의해 결정된다.
모티프는 이를 반복하면 원래 텍스츄어를 만들 수 있기 때문에 원래 텍스츄어의 모든 대칭을 가진다. 따라서, 모티프가 가지는 대칭성을 해석함으로서 주어진 텍스츄어의 대칭 그룹을 결정할 수 있다. 모티프가 가지는 대칭들은 회전 대칭, 반사 대칭, 전이반사 대칭의 조합이다. 본 논문에서는 먼저, 주어진 모티프에 대해, 이들 각각을 효율적으로 찾아내는 방법들을 제시한다. 최종적으로, 텍스츄어의 대칭 그룹을 알아내는 구분도(classification diagram)를 제시한다. 텍스츄어의 기본영역은 알아낸 대칭들에 대해 모티프를 정렬하면 쉽게 얻을 수 있다. 본 논문에서 제시하는 알고리즘은 주어진 텍스츄어의 크기가 m × n일때, O(mnlogmn)의 시간 복잡도(time complexity)를 가진다.
