Simpler Editing of Spatially−Connected Graph Hierarchies using Zipping Algorithms

Abstract

Graph hierarchies, the data structures that result from hierarchically clustering the nodes of a graph, are widely used as a multi-scale way of representing data in many computing fields, including image segmentation, mesh simplification, hierarchical pathfinding and visualisation. As a result, significant efforts have been made over the years to find ways of constructing 'good' graph hierarchies, a task that is an instance of the hierarchical segmentation problem. However, it is still comparatively rare to see techniques for editing graph hierarchies, despite the fact that such editing has many potential uses, e.g. for tasks such as correcting initially poor segmentations of images, or visualising the effects of hypothetical changes to a network. We believe that this relative lack of attention may be partly explained by the fact that graph hierarchies in many domains have spatial connectivity constraints associated with them that must be preserved during editing, significantly complicating the development of techniques that require non-trivial changes to be made to the hierarchy. In this paper, we therefore propose a way of facilitating the development of editing algorithms for such 'spatially-connected graph hierarchies' by introducing multi-level split and merge algorithms ('zipping algorithms') for them that can be used as building blocks for more sophisticated editing. We demonstrate the advantages of our zipping algorithms by using them to solve the practical problem of how to merge non-sibling image regions in millipede, our tool for 3D hierarchical image segmentation. We also demonstrate how our zipping algorithms can be used to reformulate existing techniques in the literature to make them either more general or easier to understand.