Graph Cuts implementation

[Emmanuelle Gouillart]

Hi Mark,

thanks for this first survey. I'll read articles [2] and [4] in the next
days, so that I can give you more feedback. For the multicore
programming, is it an embarrassingly parallel problem where you could use
joblib.Parallel (or simply multiprocessing), or do you have a large
number of low-level "small operations" that need to be performed
together? Anyway, maybe you can write a first version of the code that is
not parallel, convince yourself that the implementation is correct, and
only after think about the parallelization?

Cheers,
Emmanuelle

On Thu, Jun 20, 2013 at 03:17:16AM -0700, Marc de Klerk wrote:
> Hi Everyone,

> One of items on my todo list in first three weeks of my GSOC is to implement a
> CPU Graph-cuts.
> I've made a couple points from a preliminary literature survey and would like
> to get some feedback / recommendations / advice.

> Graph cut algorithms can generally be regarded as either begin push-relabel
> (PR) or augmenting paths (AP) style.
> - The goto algorithm has typically been the Boykov and Kolmogorov algorithm
> (AP) [1]
> - The current state-of-art graph-cut is packaged as GridCut, product of [2]
> - Based on [1]
> - Multi core (from [3])
> - Cache efficient memory layout (from [2])
> - For grid-like topologies
> - A push relabel variant exists from [4]
> - Multi core (from [3])
> - Not bound by memory constraints
> - For grid-like topologies
> - From what I can gather BK typically outperforms other approaches such as the
> push-relabel algorithm, but to what extent I'm can't tell from the literature…
> - [4] describes memory layout strategies to optimize caching for both AP and PR
> style algorithms, but that choose the implement their strategies on BK.
> - PR style algorithms are not limited by memory constraints, whereas AP style
> algorithms are, however doing graph cuts on a coarse to fine scale seem to be
> an answer.
> - PR is the only feasible way to do graph cuts on the GPU.

> So I'm suggestions to implement the PR style algorithm of [4] using the
> strategies described in [2] to speed things up. This then let's us make a
> fairer comparison between CPU and GPU versions of the graph cut

> Does this sound like a good way forward?
> It does require some multi-core programming which I'm not familiar with - are
> there any examples of something similar in scikit-image?

> [1] Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison of min-cut/
> max- flow algorithms for energy minimization in vision. Pattern Analysis and
> Machine Intelligence, IEEE Transactions on, 26(9), 1124–1137. doi:10.1109/
> TPAMI.2004.60
> [2] Jamriska, O., Sykora, D., & Hornung, A. (2012). Cache-efficient graph cuts
> on structured grids (pp. 3673–3680). Presented at the Computer Vision and
> Pattern Recognition (CVPR), 2012 IEEE Conference on. doi:10.1109/
> CVPR.2012.6248113
> [3] Liu, J., & Sun, J. (2010). Parallel graph-cuts by adaptive bottom-up
> merging (pp. 2181–2188). Presented at the Computer Vision and Pattern
> Recognition (CVPR), 2010 IEEE Conference on. doi:10.1109/CVPR.2010.5539898
> [4] Delong, A., & Boykov, Y. (2008). A Scalable graph-cut algorithm for N-D
> grids (pp. 1–8). Presented at the Computer Vision and Pattern Recognition,
> 2008. CVPR 2008. IEEE Conference on. doi:10.1109/CVPR.2008.4587464