A new image segmentation algorithm using minimum spanning trees is proposed in this thesis. In the algorithm, each pixel of an input image is considered as a node of an undirected connected weighted graph. The graph is formed by connecting four neighboring nodes of each node with each branch weight being the absolute gray value difference between its associated nodes. From the connected graph given above, an unconnected graph is constructed by eliminating those branches of branch weight greater than a given threshold. A minimum spanning forest of the unconnected graph is found. Each tree of the minimum spanning forest corresponds to a segmented region of the input image.
It is shown that in the use of the new algorithm, dividing the input image into small subimages, segmenting each image, and combining the results of segmentation produces exactly the same result as the application of the algorithm to the input image. Thus, we can apply the algorithm to very large size images without rapid increase in time and space complexity.
Two variations of the algorithm are made, in which regions found by the forest can be merged together depending on their average gray values and optionally their sizes, thus making the algorithm more flexible.
Several examples are shown which clearly demonstrate the effectiveness of the algorithms. We can also note from these examples the closeness between the results and human perception. For comparisons, the results obtained by a well-known segmentation technique, split-and-merge are also shown.
Finally, in this thesis, an object detection scheme based on region adjacency graph is studied as an application of image segmentation. Several examples are given demonstrating some usefulness of the scheme.
영상 영역화는 computer vision system 에서, 가장 기초적이고 중요한 과정중의 하나이다. 또한 영상영역화 기법을 이용하여, 영상에 있는 물체들을 인식하는 작업도 실제 응용에서 매우 요긴하다.
본 논문에서는 Minimum Spanning Tree를 이용한 새로운 영상 영역화 기법을 제시하였다. 이 기법은 매우 큰 크기의 영상에 대해서도 시간과 기억 용량을 최소로 줄이면서 효율적으로 적용될 수 있음을 보여 주었다. 실험결과 또한 인간의 인식결과와 매우 근사하는 좋은 결과를 얻었다. 끝으로, 본 논문에서, 위의 새로운 영상영역화 기법과 region adjacency graph를 이용한 새로운 영상안의 물체 인식 기법을 제안하였다. 이 기법의 유통성을 보여주는 실험결과들이 첨가되었다.
