We discuss an effective method to find an optimal cut in an segmentation algorithm based on normalized cut proposed by by Shi and Malik (2000). In the algorithm, there is a problem about finding a splitting point after calculating the second smallest eigenvector of the Laplacian matrix. Shi and Malik suggested a method to find a splitting point after calculating normalized cut of some splitting points. Rather than using this hueristic method, we propose to investigate histograms of components of the second smallest eigenvector and choose a splitting point near the lowest bin. This aims at decrease of the cost of calculating normalized cuts so that we segment the image fast. To validate our proposal, compare histogram and normalized cut.
본 학위 논문에서는 Shi와 Malik이 제시한 Normalized Cut을 이용한 그래프 이론 기반의 영상 분할 알고리듬에서 최적 Cut을 찾는 효율적인 방법에 대해서 논의하였다. Ncut을 여러 번 계산하는 기존의 방법과 달리, 본 논문에서는 계산량이 적은 최적 Cut을 구하는 방법을 제시하였다. 알고리듬 과정에서 고유벡터의 성분들이 분리되어 있고, 그 경계에서 Ncut값이 작아진다는 가정 하에 성분들의 히스토그램을 이용하였다. 초기 선택은 히스토그램의 막대가 높이가 가장 낮은 부분에서 하였다. Ding과 He가 제시한Linear Ordering에 기반하여 Ncut대신 LocalNcut으로 Gradient Descent 방법을 적용해서 최적 Cut을 찾았다. 실험에서 확인한 결과, 히스토그램의 막대가 낮은 부분에 최적 Cut이 있고, 초기 예측으로부터 최적 Cut을 찾아냄을 확인할 수 있었다.
