Graph Cuts implementation

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