The alpha-tree algorithm : theory, algorithms, and applications

A new multi-scale graph-space connectivity framework is presented. It is based upon a measure of dissimilarity between adjacent elements of the graph that is used to construct a hierarchy of partitions. Connected components or partition cells are either preserved or rejected based on a set of attribute criteria that are enumerated through logical predicates. Enforcing attribute constraints generates a dichotomy of the partition hierarchy that can be used for image segmentation and other related applications. The framework is supported by an efficient union-find based algorithm that delivers a tree representation of the totally ordered set of graph-space partitions. It is referred to as the Alpha-Tree. The practical complexity of the algorithm is linear with respect to the number of pixels. Processes on the tree can be launched interactively and in real-time, from a separate module detached from the tree construction phase. The type of attributes and attribute thresholds can be set and adjusted interactively. Timed experiments on highly complicated and massive satellite image tiles are presented, complemented by comparisons to the standard method.