The Improvement of the Processes of a Class of Graph-Cut-Based Image Segmentation Algorithms

Shengxiao NIU  Gengsheng CHEN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.12   pp.3053-3059
Publication Date: 2016/12/01
Publicized: 2016/09/14
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2016EDP7347
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
graph cut,  image segmentation,  energy function,  maximum flow,  

Full Text: PDF(906.3KB)>>
Buy this Article




Summary: 
In this paper, an analysis of the basic process of a class of interactive-graph-cut-based image segmentation algorithms indicates that it is unnecessary to construct n-links for all adjacent pixel nodes of an image before calculating the maximum flow and the minimal cuts. There are many pixel nodes for which it is not necessary to construct n-links at all. Based on this, we propose a new algorithm for the dynamic construction of all necessary n-links that connect the pixel nodes explored by the maximum flow algorithm. These n-links are constructed dynamically and without redundancy during the process of calculating the maximum flow. The Berkeley segmentation dataset benchmark is used to prove that this method can reduce the average running time of segmentation algorithms on the premise of correct segmentation results. This improvement can also be applied to any segmentation algorithm based on graph cuts.