A Clustering Model of Boundary Formation

Abstract

We present a graph-based hierarchical clustering method for chaining edges together into boundaries. The notion of edge employed is quite general, viz., directed line segment with associated probability. Edges are treated as vertices in an arc-weighted directed graph, EG. The weight of any arc, ei ej, in EG is a value between 1 and representing the degree to which the edge ej continues ei, lower values corresponding to better continuations. The measure of continuation from one edge to another is a function of their probabilities, lengths, and locations. EG is initially partitioned into simple chains by deleting any arc ei + ej unless it is both the lowest weighted arc leaving ei and the lowest weighted arc terminating at ej. Further subdivision of these chains leads to a tree structure of subgraphs, each of which corresponds directly to a boundary. A probability for each subgraph/boundary is then computed, based on the number of its vertices (edges) and the weight of its highest weighted arc (weakest edge continuation) relative to values of the same characteristics for its ancestors and descendants in the tree.