Study On Polynomial-time Algorithms For Graphical Models And Their Applications

Many of the problems arising in early vision can be naturally expressed in terms of energyminimization. The computational task of minimizing the energy is usually quite difficult as itgenerally requires minimizing a function in a space with thousands of dimensions. Thedevelopment of polynomial-time algorithms for the inference in the graphical model is crucial incomputer vision.This paper mainly studies the polynomial-time inference algorithms based on the Isinggraphical model and the application of these algorithms to solve the image segmentation problemoften encountered in computer vision. Image segmentation is a fundamental step in computervision. Image segmentation is the process of assigning a label to every pixel in an image and thiscan be achieved by making use of graphical models. This makes the adjacent pixels with the samefeatures in the same area, in order to extract the foreground and the background. The timeefficiency for image segmentation is of great significance.This paper firstly introduces the knowledge of graph theory and the theory of graphicalmodels, and then focuses on the Ising model and the polynomial-time algorithm based on thismodel. After that, this paper describes the specific content of image segmentation and the novelmethod for image segmentation. Each node of the Ising model can have one of two random states,which is used to label the foreground or background of the corresponding pixel. According to thesefacts, a novel approach for image segmentation is proposed by setting the appropriate weights andtransforming the segmentation problem into the minimum energy problem based on the Isingmodel. The minimum energy of the Ising model can be obtained by an exact inference algorithmand thus the segmentation process can be completed efficiently. The weight values play animportant role in the image segmentation task. This paper uses the gray and color information toset the weights in order to obtain the desired results, and also analyzes the effect of weight-settingon the results of image segmentation.Finally, the experimental results obtained by the new method are compared with othermethods. It shows that the proposed method can obtain ideal segmentation results in a short time.