Discrete Surfaces and Frontier Orders

Many applications require the extraction of an object boundary from a discrete image. In most cases, the result of such a process is expected to be, topologically, a surface, and this property might be required in subsequent operations. However, only through careful design can such a guarantee be provided. In the present article we will focus on partially ordered sets and the notion of n-surfaces introduced by Evako et al. to deal with this issue. Partially ordered sets are topological spaces that can represent the topology of a wide range of discrete spaces, including abstract simplicial complexes and regular grids. It will be proved in this article that (in the framework of simplicial complexes) any n-surface is an n-pseudomanifold, and that any n-dimensional combinatorial manifold is an n-surface. Moreover, given a subset of an n-surface (an object), we show how to build a partially ordered set called frontier order, which represents the boundary of this object. Similarly to the continuous case, where the boundary of an n-manifold, if not empty, is an (n−1)-manifold, we prove that the frontier order associated to an object is a union of disjoint (n−1)-surfaces. Thanks to this property, we show how topologically consistent Marching Cubes-like algorithms can be designed using the framework of partially ordered sets.X. Daragon is a Ph.D. student at ESIEE, A2SI laboratory. He received a DEA in computer science from Marne-La-Vallee University in 2000. His research focuses on order theory and its applications to image analysis and computer graphics, mainly in the field of 3D medical imaging (segmentation of the cerebral neo-cortex).Michel Couprie received his Ingénieur’s degree from the École Supérieure d’Ingénieurs en Électrotechnique et Électronique (Paris, France) in 1985 and the Ph.D. degree from the Pierre et Marie Curie University (Paris, France) in 1988. Since 1988 he has been working in ESIEE where he is an Associate Professor. He is a member of the Laboratoire Algorithmique et Architecture des Systèmes Informatiques, ESIEE, Paris, and of the Institut Gaspard Monge, Université de Marne-la-Vallée. His current research interests include image analysis and discrete mathematics.Gilles Bertrand received his Ingénieur’s degree from the École Centrale des Arts et Manufactures in 1976. Until 1983 he was with the Thomson-CSF company, where he designed image processing systems for aeronautical applications. He received his Ph.D. from the École Centrale in 1986. He is currently teaching and doing research with the Laboratoire Algorithmique et Architecture des Systèmes Informatiques, ESIEE, Paris, and with the Institut Gaspard Monge, Université de Marne-la-Vallée. His research interests are image analysis, pattern recognition, mathematical morphology and digital topology.