Encourage object boundaries at edges in Graph cut segmentation

Question

Up to now I have been segmenting some grayscale images using either Otsu's method or K-means. I noticed however that the segmentation cannot be "perfect" only based on the intensity. At least one would have to consider local gradients in the image.

I then did some research and came across the graph cut segmentation algorithm. I thought this algorithm would be beneficial since

1. The relationship between neighboring pixels is considered
2. I could incorporate prior knowledge if I know of pixels that belong to a certain class beforehand.

I now have been doing some tests using Shai's MATLAB Graph Cut wrapper and noticed that Graph Cut does not seem as beneficial as I thought. Based on the gradient I can reduce the penalty for a class border, but I can't encourage the algorithm to draw boundaries at edges - if a boundary is not present in the initialization via K-Means/Otsus (to create Dc) the algorithm won't draw one even though there might be a strong local edge. I think this is due to the fact that costs need to be positive. Hence it seems as that Graph-Cut here only helps to smoothen boundaries but it won't help me to introduce "new ones".

Long story short: Does my story above sound plausible to you, i.e. do my conclusions make sense? Or, is there a way to use edges to create boundaries?

Thanks!

PS. Sorry, I can't show a real image I am talking about here :(

Answer 1

To cut a long story short: using the "conventional" graph cut formulation, the pair-wise term is used to encourage smoothness. It can be tuned based on local gradients to be weaker across image boundary, but as you correctly noted, it is always non-negative, thus, it never encourages changing of label (unless strong evidence exists in the per-pixel term).

The requirement for non-negative pair-wise terms is called "sub-modularity" and only for sub-modular energies there exist a polynomial time solution (exact for the 2-labels case, good approximation for multiple labels).
You can read more about the "sub-modularity" in this context at Kolmogorov and Zabih, What Energy Functions can be Minimized via Graph Cuts?, PAMI 2004.

However, you can define non sub-modular weights for the pairwise terms across image boundaries. You will no longer be able to use the "conventional" GCMex implementation, however, there are some nice approximation algorithms that can give not reasonable results even in the shaky realm of non sub-modular energies.
The first approximation to explore, for the two-labels case, is QPBO, described at Kolmogorov and Rother, Minimizing non-submodular functions with graph cuts - a review, PAMI 2007.
The next step is a multi-label, multi-scale approximation, described at Bagon and Galun, A Multiscale Framework for Challenging Discrete Optimization, NIPS 2012.

Last but not least, if you only have pair-wise interactions (positive and negative) and no clear per-pixel terms, you might want to consider segmentation using Correlation Clustering functional.