A Study on Computational Complexity and Efficient Implementation of Region Segmentation Problem of an Image under Various criteria

点击翻译按钮获取中文摘要

In this study we considered regions segmentation problem which is a basis for image understanding from as viewpoint of algorithm theory. First, for each of various criteria for regions segmentation we analyzed the computational complexity of the problem of finding an optimal solution under the criterion together with consideration on requirements for polynomial-time implementation. One of the main results is that we obtained a polynomial-time algorithm for finding an optimal segmentation based on discriminant analysis. Experimental results suggest practical application of the algorithm. Especially various algorithmic techniques developed in computational geometry made great contributions to the algorithm.The research results were presented in several international conferences and accepted for publication in international journals. One of the future plans is to do more computer experiments for really practical applications.