Abstract

We present a novel algorithm for recovering a smooth man- ifold of unknown dimension and topology from a set of points known to belong to it. Numerous applications in computer vision can be naturally interpreted as instanciations of this fundamental problem. Recently, a non-iterative discrete approach, tensor voting, has been introduced to solve this problem and has been applied successfully to various appli- cations. As an alternative, we propose a variational formulation of this problem in the continuous setting and derive an iterative algorithm which approximates its solutions. This method and tensor voting are some- what the difierential and integral form of one another. Although iterative methods are slower in general, the strength of the suggested method is that it can easily be applied when the ambient space is not Euclidean, which is important in many applications. The algorithm consists in solv- ing a partial difierential equation that performs a special anisotropic difiusion on an implicit representation of the known set of points. This results in connecting isolated neighbouring points. This approach is very simple, mathematically sound, robust and powerful since it handles in a homogeneous way manifolds of arbitrary dimension and topology, em- bedded in Euclidean or non-Euclidean spaces, with or without border. We shall present this approach and demonstrate both its bene?ts and shortcomings in two different contexts: (i) data visual analysis, (ii) skin detection in color images.