In many applications in computer graphics, computer vision, pattern recognition, or other related fields, shape matching plays a key role. In this thesis we consider several shape matching problems and give algorithms to solve them.
First, we introduce an approximate version of the largest common point set problem. The largest common point set problem is a standard problem in pattern matching. For two given point sets, we want to find a transformation that matches maximum subsets of the two point sets under a certain metric. Our algorithm works in the plane and we assume that point sets move under translations.
Second, we present an approximation algorithm to return a rigid motion of three-dimensional Euclidean space for two given convex polyhedra such that the volume of the overlap of the polyhedra is maximized. We apply an existing algorithm for translations for many sampled candidate rotations. The challenge is to deal with three-dimensional rotations.
Last, we explore convex polytope matching problem with respect to the volume of the symmetric difference metric. We prove that the function of the volume of the symmetric difference is convex and therefore we can apply convex programming to our problem. We give necessary and sufficient conditions for local minima of the function.
모양매칭 문제는 컴퓨터 그래픽스, 컴퓨터 비전과 같은 분야에서 널리 쓰이는 문제이다. 주로 점이나 다각형과 같은 기하물체의 유사정도를 하우스돌프 거리(Hausdorff Distance)나 겹침넓이와 같은 기하함수를 이용하여 측정한다. 본 학위논문에서는 총 세 가지 모양매칭 문제를 다룬다.
첫 번째는 점집합 부분매칭 문제로 점의 개수가 각각 $n$과 $m$인 두 점집합이 주어졌을 때 병목거리(Bottleneck Distance)를 $\eps$ 이하로 가지는 평행이동을 찾는 문제이다. 병목거리는 항상 같은 개수의 두 점집합에서 정의되기 때문에 가장 큰 부분집합을 고려하여 계산한다. 본 학위논문에서는 2차원에서의 근사 문제를 다루었으며 $\eta$가 $\eps$에 대한 근사 변수일 때 $O(n^{2.5}m\log{\frac{n}{\eta}})$인 알고리즘을 제시한다.
두 번째로 두 3차원 볼록다면체가 주어졌을 때 겹침 부피를 최대로 하는 강체이동을 찾는 문제를 다룬다. 여기서 두 볼록다면체의 최대 겹침 부피가 항상 두 볼록다면체의 일정 비율 이상이라고 가정한다. 강체이동이란 평행이동과 회전이동을 말한다. 평행이동만을 허용했을 때 최대 겹침 부피를 계산하는 알고리즘이 이미 현존하기 때문에 이를 이용하여 회전이동을 적절히 추출하는 방법으로 최대 겹침 부피의 $(1-\eps)$배 이상인 강체이동을 찾아주는 알고리즘을 소개한다.
마지막으로 대칭차부피(Volume of the Symmetric Difference)를 유사도로 하는 볼록다면체 매칭문제를 다룬다. 이 문제에서는 볼록다면체의 평행이동과 확대축소만 허용한다. 대칭차부피 함수는 허용한 이동공간에서 두 개 이상의 국소최저값을 가질 수 있지만 제한된 정의역에서 유일한 최저값을 가진다는 것을 증명함으로 볼록 제한식 계획(Convex Programming)을 이용할 수 있다는 것을 보인다. 또한 대칭차부피 함수의 국소최적값을 가지는 이동들의 필요충분조건에 대하여 알아본다.
