We introduce a novel minimally-interactive watershed algorithm that needs no initial parameterization, but lets the user refine the automatic segmentation close to real-time. In contrast to previous proposals, our algorithm encapsulates all time consuming calculation in a processing step executed only once. Thereby, a hierarchical subdivision of the incoming image data is generated. This subdivision serves as a basis for computing automatic segmentation results according to a given multi-dimensional classification scheme as well as for interactive refinement according to local markers. We have successfully applied our algorithm to efficiently removing bone structures from computed tomography angiography data, which is among the very challenging segmentation problems in medical image analysis.