Graph Cuts implementation

[Marc de Klerk]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scikit-image/attachments/20130620/733f45da/attachment.html>