28
This iterative marking ensures that voxels chosen as part of Si will not be re-colored
as part of another segment. Furthermore, for all voxels v such that v ∈ Sj where j ≠ i,
V is connected to the sink node with infinite weight. These edge connections ensure
that segments that are already painted will not be over-written. All other visible
voxels are considered to be free nodes in the graph. After a min-cut is performed, we
classify all nodes in the graph as part of either the source or sink component of the
graph. Voxels that correspond to nodes that are part of the source component will
be re-grouped as part of Si. This process is repeated for all Si for i = 1,..., n.
To reduce the size of the graph, we do not include colored voxels whose neighbors
are all painted. These inner voxels do not affect the outcome of the cut as the edges
that connect them cannot be removed under our construction of the graph. This
constraint also implies that as the user paints more regions, the number of nodes in
the graph-cut will reduce, and the min-cut will perform faster.
Note that our algorithm is not explicity finding an approximate minimum cut,
but rather, heuristically separating the volume into components. Therefore, our cut
does not maintain an approximation ratio of 2; furthermore, it is often the case that
there will be un-colored voxels (or voxels that do not belong to a segment) at the end
of the process. These regions will require further input from the user to be further
segmented. Leaving voxels un-colored is an acceptable approach as the unpainted
regions are often regions that require further input from the user.
4.2 Results
Our method has been implemented and tested on a Intel Xeon 5150 machine with 2
CPUs running at 2.66GHz. We use an nVidia GTX280 graphics card with IGB of
video RAM. The shaders are written in GLSL. We use OpenMP to enable multi-core
processing for easily parallelizable portions of the code. We use the Boykov et al’s
implementation of min-cut, which has good practical running time.