Simpler editing of graph-based segmentation hierarchies using zipping algorithms

- We present reusable algorithms to simplify segmentation hierarchy editing.
- They allow hierarchical segmentation techniques to make better use of user input.
- We show the use of our algorithms for non-sibling node merging and parent switching.
- Non-sibling node merging hugely reduces input requirements for >55% of merges.
- Parent switching allows 4× more switches than the state-of-the-art relinking method.

Graph-based image segmentation is popular, because graphs can naturally represent image parts and the relationships between them. Whilst many single-scale approaches exist, significant interest has been shown in segmentation hierarchies, which represent image objects at different scales. However, segmenting arbitrary images automatically remains elusive: segmentation is under-specified, with different users expecting different outcomes. Hierarchical segmentation compounds this, since it is unclear where in the hierarchy objects should appear. Users can easily edit flat segmentations to influence the outcome, but editing hierarchical segmentations is harder: indeed, many existing interactive editing techniques make only small, local hierarchy changes. In this paper, we address this by introducing 'zipping' operations for segmentation hierarchies to facilitate user interaction. We use these operations to implement algorithms for non-sibling node merging and parent switching, and perform experiments on both 2D and 3D images to show that these latter algorithms can significantly reduce the interaction burden on the user.

91