Graph Cuts implementation

Tue Jun 25 18:20:13 EDT 2013

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

On Tuesday, June 25, 2013 3:22:52 AM UTC+2, Thouis (Ray) Jones wrote:
>
> 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
>
>
>
> On Sun, Jun 23, 2013 at 6:31 PM, Marc de Klerk <dekl... at gmail.com<javascript:>
> > wrote:
>
>> 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
>>
>>
>> On Sunday, June 23, 2013 11:44:03 PM UTC+2, Emmanuelle Gouillart wrote:
>>>
>>> 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 
>>>
>>  -- 
>> 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... at googlegroups.com <javascript:>.
>> For more options, visit https://groups.google.com/groups/opt_out.
>>  
>>  
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scikit-image/attachments/20130625/85bcac1e/attachment.html>