Kovtun I. Image segmentation based on sufficient conditions for optimality in NP-complete classes of structural labeling problems

The dissertation is devoted to solving the problem of image segmentation. A special attention is given to the investigation of the possibility to the exact solving of the appropriate optimization problem, which is also called labeling problem. The labeling problem is NP-complete in general case. It is proposed to search for a part of the exact solution for such a problem. The appropriate sufficient conditions are formulated. The new model of the textured image was also proposed. The Bayesian recognition problems were considered for different penalty functions on the basis of this model. The method of approximate solution of the problem was proposed for additive penalty function.