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