In this thesis, we investigate a segmentation algorithm based on the normalized cut framework proposed by Shi and Malik (2000). It is a recent approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their consistencies in the image data, this approach aims at extracting the global impression of an image. We treat image segmentation as a graph partitioning problem and consider a global criterion, the normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. We show that an efficient computational technique based on a generalized eigenvalue problem can be used to optimize this criterion. In addition, we suggest a model of similarity function between two nodes and the way to determine some parameters inside such a function.
본 학위 논문에서는 Shi와 Malik이 제시한 Normalized Cut을 이용한 그래프 이론 기반의 영상 분할 방법에 대하여 알아보았다. 특히 그 분할 알고리듬 과정에서 필요한 두 픽셀간의 유사성을 계산하는 함수에 대해 자세히 논의하였다. 알고리듬 과정에서 가장 중요한 단계는 바로 영상의 특성을 잘 반영하는 함수 모델을 이상적으로 설정하는 것이다. 주어진 영상에 대하여 본 논문에서 제시하는 함수를 계산하기 위해서는 그 영상의 특성을 잘 표현하는 적절한 변수값들을 결정해야 한다. 영상의 특성은 상대적이므로 이 변수들의 값을 영상의 특성에 의존하여 결정하여야 한다. 본 논문에서는 이 변수들이 제시한 함수에서 어떤 역할을 하는 지와 이 변수들의 변화가 어떤 영향을 끼치는 지에 대하여 설명하였다. 또한 알고리듬 과정에서 이 변수들을 어떤 방식으로 영상의 특성에 부합하도록 합리적으로 선택하여야 하는 지에 관하여 논의하였다.
