Graph Cuts implementation

[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



On Sun, Jun 23, 2013 at 6:31 PM, Marc de Klerk <deklerkmc at gmail.com> 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+unsubscribe at googlegroups.com.
> 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/20130624/8bb5d811/attachment.html>