Research On Image Segmentation Based On Improved Graph Cuts

Image segmentation based on graph theory has been highly concerned by the academic circles, because it can take account of both local and global feature of image. Graph Cuts as a typical image segmentation method based on graph theory, is an important technology in the field of computer graphics. However, with the development of image technology and the improvement of image resolution, the scale of graph in Graph Cuts is bigger, resulting in a series of problems such as complex structure, large storage space, slow calculation speed, and so on.In order to solve these problems when processing high resolution images, a feasible method is to reduce the complexity of graph by reducing the number of nodes and edges in the graph. In this way, it can reduce the time of mapping process and max-flow computation, and ultimately improve the efficiency of Graph Cuts. This paper focuses on maximum flow and minimum cut theorem, and proposed two improved Graph Cuts algorithm, which based on improved energy function and flow testing method respectively.Firstly, this paper improves Boykov-Jolly energy function, and then improves Graph Cuts algorithm. In standard Graph Cuts, each pixel node needs to connect to two terminal nodes simultaneously. But in improved Graph Cuts, each node only needs to connect to one terminal node, because the modified energy function can consider the feature of foreground and background at the same time. In this way, the number of edges between nodes and terminal has reduced, and the complexity of graph has reduced. Experiments show that under the premise of ensuring the result of the image segmentation, the running speed of improved algorithm becomes faster, and ultimately improves the efficiency of Graph Cuts.Secondly, this paper designs a flow testing method to judge whether a node is useful for the maximum flow calculation. According to flow conservation conditions, many of the nodes and edges in the graph are useless when calculating the maximum flow, because they will not be passed by any flow and all the flow can be provided or absorbed by the annular region which outside the object. Deleting these useless nodes and useless edges from the graph can effectively reduce the number of nodes and edges in the graph. Experiments show that under the premise of ensuring the result of the image segmentation, the improved graph cut algorithm reduces the scale of graph and reduces the time complexity of Graph Cuts, and does not need any low-level segmentation tools.