Given the Push-Relabel Graph Cut algorithm described in this article I wish to perform binary image segmentation. My question is regarding initialisation of the graph.
When representing the image as a graph with a lattice structure(MRF), one would usually formulate the problem as per the standard unary and pairwise terms energy function, as per section 3, equation 1 in this paper, where the unary term is a data energy and the pairwise term models smoothness in some neighbourhood.
I am struggling to make the connection between this MRF optimisation formulation and the formulation of the max-flow algorithm in the linked article. To my understanding, the capacities between neighbouring nodes can be represented by some distance function(based on spatial distance and intensity values), for example section 2, equation 7 in this paper. However, it is not clear how one would incorporate prior knowledge in to the graph initialisation, such as initial distributions for seed points.
At a higher level, given an image with some labelled seed points pertaining to background or object classes, how does one initialise the flow graph such that max-flow can be used to perform binary segmentation?
The graph has a vertex for every pixel, but it also has a source vertex and a sink vertex, neither of which corresponds to a pixel. One possible interpretation of these special vertices is that the source represents the "foreground" segment, and the sink represents the "background" segment.
The capacity of the arc from the source to a pixel vertex is a log-likelihood that that pixel is in the foreground. The capacity of the arc from a pixel vertex to the sink is a log-likelihood that that pixel is in the background. The capacity of an arc between pixel vertices represents a log-likelihood that the pixels are both in the foreground or both in the background. This belief should be higher when the pixels are close to each other and when the pixels have similar colors.