Graph Cut solver with CUDA (either NPP or thrust)

Hi all, I need your help to solve a problem I’m thinking of.

I currently need a graph cut algorithm (ideally push-relabel) and it seems like nppiGraphcut can do the trick with the 4neighbor and 8neighbor as described in grabcut algorithm :

I want to know if npp’s graph cut can help me solve for the logical graph cut outputs for {S,T} (i.e. source set and sink set) needed according to the height (distance) solved on the following graph input.

IN matlab, I have the following going into the BK graph cut ‘mxMaxFlow.mex’ algorithm:

[output, flow]=mxMaxFlow2(nNodes,int32(eFrom2),int32(eTo2),weights(:,1),weights(:,2),sourceWeights,sinkWeights);

  • nNodes is the total number of nodes (not including source/sink), usually in the order of 3000 or more
  • eFrom2 are the ‘from’ nodes of the arc
  • eTo2 are the ‘to’ nodes of the arc
  • weights(:,1) = 1e15 or infinite, for the forward capacities between non-st nodes (i.e. n2->n3->n4…etc)
  • weights(:,2) = 0 or zero, for the reverse capacities between non-st nodes (i.e. n2<-n3<-n4…etc)
    -sourceWeights are the capacities/weights of the source branching to all nodes (excluding target/sink node)
  • sourceWeights are the capacities/weights of the all nodes towards sink (excluding source node)

Can npp graphcut help me solve for the output (i.e. logical 1’s for source set, and 0’s for sink set based on height/distance of each non-st node)? And can it solve for the max flow / min cut?

Or would the thrust library be better to construct my graph?

If so, how do I go about constructin the graph based on the inputs above?

Your help will be super appreciated!


Let me correct myself:

I reconstructed my 3D volume (voxels) into a 1D array of ‘from’ nodes, and ‘to’ nodes, with each node connected to a source and sink.

like this, where source connects to nodes <1><2><3> with sourceWeights, and nodes <1><2><3> connect to sink node with sinkWeights. And likewise, there are nodes between capacities, but only connected in one direction (i.e. the reverse capacity is 0).

Can this be used in nppGraphCut as a 1D array (<1><2><3>) to perform graph cut on?


<1> -> <2> -> <3> -> <4> -> <5> -> <6> …


or is there a way to invoke just the graph cut, but not the graph construction of the NPP graph cut functions.?