The surface information about a three-dimensional object is very important in diverse fields such as medical imaging and computer animation. The triangulation technique is an attractive solution for generating it from a set of wire-frame contours. This thesis deals with the surface modeling problem called the contour triangulation.
Major topics of this thesis are concentrated on five issues: the correspondence finding, the surface generation from range contour, the tiling surfaces between a pair of contours, multiple bifurcation and hole handling. For the correspondence finding, which is the first step of the contour triangulation, we find the topological skeleton of the object by using the superimposition degree between contours.
In the second topic, the contours obtained from $2\frac{1}{2}$-dimensional data such as range image or contour map are considered. The surface generation from these contours, called range contours, is separated from the general three-dimensional cases, and a robust solution which is based on the constrained Delaunay triangulation is proposed. Using our method, the surface representation approximating range contours can be produced efficiently without considering the complicated problems such as bifurcation of contours and holes.
The tiling problem tries to create natural surface between a pair of contours at adjacent levels. A heuristic method called iterative chain partitioning algorithm is proposed. It decomposes iteratively the surface generation between a pair of chains into two subproblems between two pairs of subchains.
A solution for the branching problem, that is how to handle the case when there are branches in the surface, is also discussed. We divide the surface branching into the double branching and the multiple branching. A method for handling the double branching problem is described which is based on the partition of the root contour. The multiple branching is interpreted as a set of double branching problems and an algorithm based on contour merging is developed. A procedure for handling general cases of branching is also introduced. It can successfully transform the complicated branch graph into a simple reduced branch graph.
The last subject is more difficult than the others and there is a few research results in this area. We introduce a full case study of the hole propagation between a pair of adjacent slices and propose the generalized branch graph to represent the topological skeleton of the elementary polygons. The correspondence finding algorithm is generalized such that it can handle the complicated bifurcation of holes. Two solutions, mouth opening and mouth closing, are proposed to simplify the hole open/close problem into tiling problems. The former approach tries to remove the hole polygon by absorbing it to the boundary polygon, and the mouth closing separates the mouth chain from the boundary polygon. Some suggestion for handling more complicated hole propagation is also introduced to generalize our method.
The experimental result shows that our method works well in practical application. Conclusions and further research issues on the contour triangulation are addressed at the end of this thesis.
3차원 물체의 표면 정보는 의료영상이나 컴퓨터 그래픽스 등 다양한 분야에서 매우 중요하게 사용되고 있다. 이러한 정보들은 보통 단층촬영 영상으로 주어지게 되는데, 이들로부터 등고선(contour)을 구하고 등고선들 사이의 표면을 삼각형 표면조각들으로 근사화하는 등고선 삼각분할법(Contour Triangulation)은 단층촬영 영상으로부터 3차원 표면을 구해내는 좋은 방법중 하나이다. 이 논문에서는 등고선 삼각분할법에서 발생하는 여러가지 모호성(ambiguity), 즉 등고선의 대응성 문제, $2\frac{1}{2}$ 차원의 등고선에 대한 문제, 타일링 문제, 표면 분기문제 및 홀 문제등을 체계적으로 분석하고 이들을 해결하기 위한 새로운 방법들을 제안하였다.
이들중 가장 먼저 해결 되어야 하는 등고선의 대응성 문제(correspondence problem) 는 입력으로 주어지는 등고선들에 대한 서로간의 연결성을 결정하는 문제로, 두 등고선 사이의 중첩되는 영역에 근거한 척도를 이용하여 해결하였다.
두번째 문제에서는 거리영상이나 등고선지도와 같은 $2\frac{1}{2}$ 차원의 정보로 부터 구한 등고선에서부터 표면을 재구성하는 문제로, 제약 들러니 삼각분할(Constrained Delaunay Triangulation)을 이용하여 해결하는 방법을 제안하였다. 이 문제를 일반적인 3차원 등고선에서의 문제와 분리하여 처리함으로써 표면 분기나 홀(hole) 문제등을 고려할 필요없이 안정되고 효과적으로 표면을 재구성 할 수 있다.
타일링 문제(tiling problem)는 인접한 층에 있는 두 등고선사이의 표면을 삼각형 조각들을 이용하여 근사화하는 문제이며, 이를 해결하기 위하여 연속 체인분할(iterative chain partitioning) 알고리즘을 제안하였다. 이 방법은 한쌍의 체인사이의 표면 생성 문제를 두쌍의 부분체인(subchain) 사이의 문제로 연속적으로 간략화 하여 궁극적인 표면을 생성하는 방법으로 기존의 최적화방법(optimal method)들에 비해 시간적으로 효과적이며 휴리스틱 접근방식들에 비해 좋은 표면을 만든다는 장점이 있다.
표면의 분기문제는 하나의 등고선이 인접한 충의 여러개의 등고선으로 연결되어야 하는경우에 발생하며, 이를 이중분기(double branching)와 다중분기(multiple branching)로 나누어 해결하였다. 먼저 이중분기문제를 해결하기 위하여, 뿌리등고선(root contour)을 분할하는것에 기초하는 알고리즘을 제안하였고, 다중분기를 연속적인 이중분기로 재 해석하여 해결하는 방법을 제안하였다. 또한 가장 일반적인 분기(general cases)를 해결하기 위해 복잡한 분기 그래프를 간략화된 분기 그래프(reduced branch graph)로 변환하는 방법을 제시하였다.
마지막으로, 홀 문제(hole problem)는 등고선 삼각화법에서 가장 복잡한경우로 기존에 제안된 대부분의 논문에서 체계적으로 다루어지지 않았다. 본 논문에서는 이를 해결하기위하여, 먼저 홀이 발생하는 다양한 경우를 몇가지 전형적인 집합으로 분류하였다. 또한 각 기초다각형(elementary polygon)들의 대응성을 나타내기 위하여 일반 분기 그래프(generalized branch graph)를 제안하였고 분기와 홀들이 복잡하게 발생하는 상황에서 도 이 그래프를 구할수 있는 알고리즘을 제안하였다. 홀의 전파과정중 가장 복잡한 홀의 열림/닫힘(open/close)경우를 해결하기 위하여 입열기/입닫기(mouth opening/closing) 알고리즘을 제안하였다.
제안된 알고리즘들의 특성을 조사하기 위하여 몇가지의 인공 등고선을 만들어 시험해 보았으며, 의료영상들에서 실지로 구한 인체내의 각 기관들에대한 등고선에도 적용해본 결과 안정되고 좋은 결과를 나타냄을 알수 있었다.
