-
Notifications
You must be signed in to change notification settings - Fork 0
graph_cuts
Conversion of my old graph cuts implementation to have a Python interface, albeit incomplete as I only needed to solve binary labelling problems at the time, so didn't bother with alpha expansion. Nothing special.
If you are reading readme.txt then you can generate documentation by running make_doc.py
Contains the following files:
maxflow.py - Provides a max flow implementation.
binary_label.py - Wrapper around above for solving binary labelling problems on nD grids.
test_*.py - Some test scripts, that are also demos of system usage.
readme.txt - This file, which is included in the html documentation.
make_doc.py - Builds the html documentation.
For solving the max-flow (min-cut) problem. You initialise with the number of vertices and the number of edges, and then set one vertex to be the source, another to be the sink. The edges are then initialised with which vertices they connect, and the maximum flow they can do in both directions. After this solve can be called to find how much flow to send over each edge to obtain the maximum flow across the graph. Once solved the total flow, which side of the minimum cut each vertex is and the remaining flow (Noting that saturated means it is on the minimum cut) of each edge. It can be run repeatedtly, though the maximum flows are lost after each run and hence need to be reset.
get_sink(?)
Returns the index of the sink vertex.
get_source(?)
Returns the index of the source vertex.
reset_edges(?)
Resets the edges, so they can be overwritten using set_edges_range. Note that this is only needed if replacing the edge structure after a first run using the set_edges_range method - the set_edges method includes this implicitly as its setting all of them.
resize(?)
Resizes the number of vertices/edges in the object, reseting everything as it does so - simply allows you to reuse an object instead of creating a new one every time. If the new count is smaller than the previous one it keeps the old block of memory around, and can later be made larger upto the original memory blocks size without the cost of a realloc.
set_edges(?)
Using two numpy vectors sets the edges, where each edge is from the vertex in the first array to the vertex in the second array.
set_edges_range(?)
Sets a range of edges - same as set_edges except the first parameter is a start index, and the array length indicates how many to set. You can only set each edge once - if you try and set an edge a second time nothing happens. Because of this you can't use this to partially reconfigure the edges, only to write all the edges in stages.
set_flow_cap(?)
Using two numpy floating point vectors sets the flow limit in each direction for each edge. The first array is the negative direction of flow, the second the positive direction of flow.
set_flow_cap_range(?)
Identical to set_flow_cap, except the first parameter is a start index in the edge array, and the length of the arrays determines how many values to write. Unlike edge construction this always writes over the current values.
set_sink(?)
Sets the sink, using an index into the vertex array.
set_source(?)
Sets the source, using an index into the vertex array.
solve(?)
Solves to find the maximum flow, after which you can extract various results via the variables/methods. Can be called repeatedly, though note that the flow limits are lost, and need to be set each time.
store_side(?)
After solve has been called this allows you to query which side of the minimum cut each vertex is on, putting the output into an array. Actually takes an output array and then two other entities - one to be copied over when its source, one when its sink. These two entities can be (independently) None to do nothing, an integer to write an integer, a float to write a float or another 1D array, to index into
store_side_range(?)
Same as store_side, except it outputs a range of values - first parameter is start, as an offset into the vertices, with the lengths of the provided array(s) indicating how many to read.
store_unused(?)
Writes into two output arrays the remaining flow after it has been solved. These must be floating point 1D arrays of length the number of edges, the first the remaining in the negative direction, the second in the positive direction. Aligned with the original edge endpoint and flow setting.
edge_count = Number of edges in the graph.
half_edge_count = Number of half-edges in the graph - divide by two to get the actual number of edges.
max_flow = Maximum flow across the graph - will be 0.0 if the algorithm has not been run.
vertex_count = Number of vertices in the graph.
Uses maximum flow to solve a MRF on a n-dimensional grid, under the usual condition that the costs be metric/sub-modular. (i.e. the costs can not encourage dissimilarity.) The output labels will be False and True, hence the naming scheme.
addCostAdjacent(self, dim, cdFalseFalse, cdFalseTrue, cdTrueFalse, cdTrueTrue)
Does the same as addCostDifferent, but allows you to provide the full set of costs for all 4 possible adjacencies, and it updates the costs accordingly, including offsetting. In the event you provide something that is not sub-modular this can result in negative costs in the system, which will be clamped to zero at runtime. The variables provided are named so the element with the lowest index comes first.
addCostConstant(self, costConstant)
A constant cost is stored, so you can get the right cost out at the end - this allows you to offset it. Can't actually think of any scenario where you would use it, but here it is just incase
addCostDifferent(self, dim, cd)
Adds to the cost of being different - you might want to instead provide the costs for the various neighbour combinations, in which case use the addCostAdjacent method. First you provide the index of the dimension for which the costs are to be added, the a numpy array of costs that must broadcast to the provided shape, with one subtracted from the column of the dimension, to account for the links being between random variables.
addCostFalse(self, costFalse)
Incriments the stored costs of assigning the label False with those in the array. Input array must broadcast to the shape provided on construction.
addCostTrue(self, costTrue)
Incriments the stored costs of assigning the label False with those in the array. Input array must broadcast to the shape provided on construction.
fix(self, fix, almost_inf = 1e+32)
Given an array of integers that matches the shape this fixes the values of some labels - where the array is zero the label is left free to take either value, where it is negative it is forced to be False, when it is positive it is forced to be True. This updates the cost function, so you should call this last before the costs are used.
reset(self)
Resets all the costs to zero, so they can be rebuilt if you want.
setLonelyCost(self, target_cost)
Goes through all costs and increases them for each random variable such that every pixel has at least the given cost of having the same label as one of its neighbours - a cute noise reduction hack.
shape(self)
Returns the shape of the structure
solve(self)
Solves for the contained costs, returning a boolean numpy array giving the highest probability labeling, in a tuple with its cost - (array, cost).