Clustering using maximum affinity spanning trees
Larry S. Shapiro · Cambridge University Press eBooks · 1995
Introduction Once the corner tracker has generated a set of image trajectories, the next task is to group these points into putative objects. The practice of classifying objects into sensible groupings is termed “clustering”, and is fundamental to many scientific disciplines. This chapter presents a novel clustering technique that groups points together on the basis of their affine structure and motion. The system copes with sparse, noisy and partially incorrect input data, and with scenes containing multiple, independently moving objects undergoing general 3D motion. The key contributions are as follows: A graph theory framework is employed (in the spirit of [119]) using maximum affinity spanning trees (MAST's), and the clusters are computed by a local, parallel network, with each unit performing simple operations. The use of such networks has long been championed by Ullman, who has used them to fill in subjective contours [150], compute apparent motion [151] and detect salient curves [132]. Clustering occurs over multiple frames, unlike the more familiar two–frame formulations (e.g. [3, 80, 134]). A graduated motion analysis scheme extends the much–used simplistic image motion models, e.g. grouping on the basis of parallel and equal image velocity vectors (as in [80, 134]) is only valid for a fronto–parallel plane translating parallel to the image. The layered complexity of our models utilises full 3D information where available, but doesn't use a more complex model than is required. The termination criteria (to control cluster growth) are based on sound statistical noise models, in contrast to many heuristic measures and thresholds (e.g. [119, 134]).