27
surface of a volume by painting only the outer surface. We also provide the option
to hide or display a particluar segment. Hiding a segment can help the user to paint
segments that might be occluded by other segments.
4.1 Segmentation with Graph-cut
The segmentation problem involves assigning each voxel a designation. Consider the
graph induced by the inherent connectivity in the volume data. We let each voxel
in the volume represent a node in the graph, and two nodes are connected if the
manhattan distance between their corresponding voxels is 1. The problem is then
viewed as a graph-cut problem: we want to find a minimum cut (a set of edges) that
separates the graph into к connected components where two nodes are in different
components if there does not exist a path that connects them with respect to the
cut. This construction is a fc-way min-cut∕max-fiow problem, which is known to be
NP-Hard. However, the classical 2-way max-flow∕min-cut problem is known to be
solvable in polynomial time. Dahlhaus et al. proposes a simple approximation to the
к-way min-cut problem by performing repeated 2-way cuts, taking the union of the
cuts, and removing the cut with the largest sum of weights [3]. This method has a
worst-case approximation ratio of 2.
Li et al uses the graph-cut approach in their segmentation, which is done through
a 2D interface and seeding points. The users would select points on a 2D slice of
the volume; each point denotes a point in the different segments. We build on their
basic algorithm and extend it to a 3D interface. In our method, we let the user paint
rough regions for each component of the segmentation; the user can then issue a
command to grow each rough region automatically so that each region contains one
approximate geometric component. Given n painted segments, we run n iterations
of 2-way min-cut, where each iteration i is trying to grow segment Si. We add the
segmented voxels into the graph thus: for each iteration i, we consider the voxels
marked as segment i as nodes that are connected to the source with infinite weight.