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

[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

[Marc de Klerk]

Hi Emmanuelle,

I'll have to go have a look weather it's that simple, but thanks for the pointing me in the direction of joblib...

In the mean I got a lot of the scaffolding down and put together a demo for Grow Cuts on the GPU.

Installation instructions are on my gsoc blog - http://mygsoc.blogspot.com/2013/06/a-kickstart-to-first-week.html

Cheers!

Marc

[Thouis (Ray) Jones]

I would suggest implementing some sort of graph simplification, as in:

http://www.3dtv-con2009.org/papers/data/883/paper_EMMCVPR_11.pdf

or

http://hal.archives-ouvertes.fr/docs/00/78/66/55/PDF/main.pdf

These can be quite effective at reducing the complexity of the graph for planar st-mincut problems, without being too difficult to implement.

Ray Jones

--
You received this message because you are subscribed to the Google Groups "scikit-image" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scikit-image...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Marc de Klerk]

Thanks Ray,

That was a great read! Slimcuts look promising.

Do you have any thoughts on the implementation?

From what I gather each node must be visited and then to check if any adjacent edge has a capacity larger than the sum of the capacities of the remaining adjacent edges. This process is seemingly them performed repeatedly.

This will break the regular structure of the graph meaning that vertex indicies will have to be looked up and I can't figure out how they manage to attain the reported performance. I guess once they have the reduced graph graph-cuts is fast, but I can't see how creating the reducing graph can be fast.

They did however mention that C source files are available for research purposes - Does GSOC / scikit-image count as research?

Marc

[Andreas Mueller]

Hey Marc.
I just saw that you are working on graph cuts and segmentation for skimage.
That is pretty awesome. I'm super busy at the moment so I only sort of
follow skimage at the time
and I can't see melange.
Could you shortly give an idea of what the goals of your GSOC are?
Are you also planning to implement alpha-expansion? And what are the
thoughts about the patent issues?

Also, I seem to have completely missed the fact that skimage wants to do
gpu now.
Are there any pointers on how this is planned / what is already implemented?

I implemented some of the segmentation algorithms in skimage and I'd
really like to
know what is happening and if I could help in any way.
I also did some energy minimization stuff, but was a bit bummed out by
the patent issues.

Btw, the slic implementation is not identical with the reference
implementation.
If you want to work on segmentation, I think this should really be
investigated ....

Cheers,
Andy

[Andreas Mueller]

ps:
your blog says your GSoC is aboug graph cuts, grow cuts and quickshift.
But quickshift is already implemented, right?
There is also a CUDA implementation of Quickshift by Brian Fulkerson and a
paper about it.
I used the implementation regularly before switching to slic.
Is there any reason you prefer quickshift over slic?

Cheers,
Andy

[Andreas Mueller]

pps:
have you read about CUDA cuts?
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4563095&tag=1

[Andreas Mueller]

Also this:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.6159
Ok, now O'm going back to work and stop flooding the skimage list, sorry ;)

[Marc de Klerk]

Hey Andy,

My apologies - I'm a few days late on replying, but here's a rundown:

• Graph-cut implementations (Cython and GPU) (I had not planned on implementing alpha extension, I'll have to to my list of nice-to-haves)
• Grow-cut implementations (Cython and GPU)
• QuickShift implementation (GPU)
• A feasibility study of GPU algorithms and their integration into skim age

My full proposal is at https://google-melange.appspot.com/gsoc/proposal/review/google/gsoc2013/deklerkmc/1

Mmm, I'm not aware of any patent issues!! Could you point in the direction where I can find out!?

Skimage isn't really planning on going the GPU route right now, Stéfan told me they did have a GSOC student a couple years ago that worked on creating an easily-switchable GPU backend, but it didn't materialize for a number of reasons. One of the goals of this project is to see weather we should look into it again though...

That's great! I could do with a hand - which seg algorithms did you do?

Caio,

Marc

[Marc de Klerk]

Ah yeah! those are the two papers that I've been using!

- CudaCuts

- Brian Fulkerson's Really Quick Shift

I haven't actually had any experience with slic - in all honestly I've seen it for the first time now.

Have you worked with both of them? - What are your thoughts?

Caio again,

Marc

[Andreas Mueller]

On 07/01/2013 09:40 AM, Marc de Klerk wrote:

Hey Andy,

My apologies - I'm a few days late on replying, but here's a rundown:

Not at all, I'm pretty busy myself.
Emanuelle added me to the GSoC group, so we can also discuss there.

• Graph-cut implementations (Cython and GPU) (I had not planned on implementing alpha extension, I'll have to to my list of nice-to-haves)
  

For graph-cut, I think it would be most convenient to compare against my python wrappers for GCO: http://peekaboo-vision.blogspot.de/2012/05/graphcuts-for-python-pygco.html
GCO includes the Boykov implementation of Boykov-Kolmogorov.

• Grow-cut implementations (Cython and GPU)

I haven't heard about that yet. Have to have a look at the papers..

• QuickShift implementation (GPU)

Why do you want to reimplement QuickShift for the GPU?
The implementation by Brian Fulkerson is open source, isn't it?

My full proposal is at https://google-melange.appspot.com/gsoc/proposal/review/google/gsoc2013/deklerkmc/1

Yeah, I did find it in the end, thanks :)

Mmm, I'm not aware of any patent issues!! Could you point in the direction where I can find out!?

That was mostly about alpha-expansion. I have no idea about grow cut, I'll have a look at the papers.

Skimage isn't really planning on going the GPU route right now, Stéfan told me they did have a GSOC student a couple years ago that worked on creating an easily-switchable GPU backend, but it didn't materialize for a number of reasons. One of the goals of this project is to see weather we should look into it again though...

Adding GPU code would make packaging and platform independence much harder, I was a bit surprised when I saw that you would do it.

That's great! I could do with a hand - which seg algorithms did you do?

I implemented the "fast graph based" / Felsenszwalbs, Quickshift and SLIC for skimage in Cython.
There is a blog-post by me here: http://peekaboo-vision.blogspot.de/2012/09/segmentation-algorithms-in-scikits-image.html

For SLIC vs quickshift: They have a similar approach to the problem, only SLIC uses a much simpler clustering method, k-means.
The thing is that (at least subjectively) the GPU implementation of quickshift seems to be similarly fast as the CPU implementation of slic.
When using the algorithms for semantic image segmentation using CRFs (which is what I do), SLIC seems to do slightly better even.
My gut feeling is that they are on par for many tasks, with SLIC being much faster. SLIC provies usually much more compact segments than quickshift,
but that can be tuned.
There is also a GPU slic implementation, with a pretty nice realtime video:
https://www.youtube.com/watch?v=6o2HogjeZkE

I would be really really interested in graph cuts if they are similarly fast as the Boykov or Kolmogorov implementations.
I really need that for pystruct: http://pystruct.github.io/
but I was to lazy to do it yet.

It has been a while since I looked into the graph cut gpu implementations, but I had the feeling the speedups were a bit meager.
What do you think can be expected?

Really looking forward to what you'll come up with :)

Cheers,
Andy