Discrete Optimization For Semi-supervised Clustering Based On Signed Graphs And Its Application To Image Segmentation

Graph-based semi-supervised clustering is a typical semi-supervised learning method,which usually represents data in unsigned graphs and uses non-negative weights to measure the similarity between nodes.In real complex system,unsigned graphs are difficult to distinguish between irrelevant and opposite relationships,while the negative edges in signed graphs can express the opposite relationships explicitly and provide more effective information for clustering.Recently,signed graphs have been effective in some fields,such as image segmentation,etc.This paper focuses on discrete optimization for semi-supervised clustering based on Signed Normalized cut(SNcut)and its application to image segmentation.Existing results are few and exist obvious deficiencies.In image segmentation,only scribble is considered,but for other weaker forms of supervision,there is no solution on how to construct signed graphs.In model optimization,spectral method is mainly used,which needs to solve discrete clustering problems in real domain space and the results are rough.Meanwhile,the computational complexity increases significantly when the scale of graphs is large.Although one study has tried to use other method to discretely optimize the first-order approximate functions of a SNcut objective,its effect has not been further verified.Taking image segmentation as the experimental object,this paper discusses the construction of signed graphs and the discrete optimization of SNcut objective functions.The main work includes the following aspects:(1)Using Gaussian mixture model to construct signed graphs and applying signed graph-based clustering to interactive image segmentation in box form.First,box is difficult to transform into pairwise constraints directly and we use Gaussian mixture model to solve it and construct signed graphs.Then,the spectral method is used to optimize the clustering objective of signed graphs.The experimental results show that the negative edges in signed graphs improve the clustering effect,and the clustering performance of signed graphs is better than unsigned graphs.(2)Constructing first-order upper-bound functions for several SNcut which are solved by kernel cut and applying them to interactive image segmentation in box form.Markov Random Fields(MRF)regularization term is introduced to enhance the alignment of target boundary and then solved by kernel cut,which combines bound optimization and graph cut.The experimental results verify that the negative edges in signed graphs improves the clustering effect,and the clustering performance of signed graphs is better than unsigned graphs.(3)Constructing second-order approximation functions for several graph-based clustering objectives,which are optimized by trust region search framework after local submodular optimization and applying them to interactive image segmentation in box form.In order to solve the problem that the pair information may be lost in the firstorder approximation,second-order approximation functions are constructed for several graph-based clustering objectives.Non-submodular second-order approximation functions regularized by MRF are optimized by local submodular optimization and incorporated into the trust region search framework and solved by graph cut.The experimental results show that the results of trust region are better than kernel cut and the negative edges in signed graphs improves the clustering effect,meanwhile the clustering performance is better than unsigned graphs.