Digital surfaces and singular surfaces

( J.-O. Lachaud , Stéphane Simon )

Digital surfaces are sets of surfels with specific properties. For instance, the boundary of a set of voxels in 3D (defined as the cube faces that separates object voxels from background voxels) is a digital surface. Digital surfaces are defined in arbitrary dimension and can be seen as n-1-cells in the cubic cellular decomposition of Rⁿ.
Digital surfaces can be used to extract isosurfaces in images. They can also be used to approach implicit surfaces by tracking changes of sign of the implicit surface. They can be efficiently implemented in arbitrary dimension. We are currently investigating the extraction of singular surfaces with digital surfaces and cubical complexes.

Efficient and generic implementation of digital topology algorithms

Digital objects, digital surfaces and other digital subsets can be modeled as subsets of some extended cartesian grid Zⁿ, sometimes called cartesian complexes, subsets of Khalimsky space, subsets of the cubic regular cell decomposition of the Euclidean space. We have proposed an efficient technique to model cells, sets of cells, in arbritrary dimension, and implemented a lot of digital topology and geometry algorithms: digital surface tracking, isosurface reconstruction, geometric estimators.

[ Lachaud07b , Lachaud03c Lachaud03b , ]

Extraction of singular surfaces

A lot of surfaces are defined implicitly (meaning as the set of solution to some equation f(x,y,z)=0). Standard extraction and visualization algorithms rely on the change of sign around 0 to numerically determine a geometric model that approaches this set. It is clear however that the set f²(x,y,z)=0 being the same, it is a digital surface. It is also straightforward to see that one cannot rely on any change of sign to locate it. There are more complex examples, even with algebraic surfaces. This class of problematic surfaces is often called singular surfaces, and it is difficult to extract their singularities, ie places where the gradient is also nul. Such places may be 0-dimensional, 1-dimensional, or 2-dimensional. The following example shows simple implicit surfaces and their reconstruction with Maple.

Sphere	Whitney's Umbrella	Four lines example
f(x,y,z)=x^2+y^2+z^2-1	f(x,y,z)=x^2-y^2*z	f(x,y,z)=xy(y-x)(y-xz)

We are developing an original technique for extracting singular surfaces, which combines digital surfaces in Z⁴ and digital surface tracking, cubical complexes, collapses, and projections. The following steps computes it.

The implicit function is interpreted as its graph, or as the zero-level of 4D implicit function F, defined as F(x,y,z,t)=f(x,y,z)-t.
The implicit surface {F=0} is a smooth 3-manifold in R⁴, homeomorphic to some plane.
The 4D space is subdivided into a grid of hypercubes (4D cubes)
The surface {F=0} is extracted by digital surface tracking. It is a digital 3-manifold, its surfels are 3-cubes.
The intersection of {F=0} and {t=0}, projected onto the latter hyperplane gives a cellular complex, which is some approximation of {f=0}.
This complex is then simplified by topological collapses to get a thin representation of the sought for singular surface.
The collapsed complex is projected onto the zero-level of f.

Some examples are given below. The meshing algorithm correctly detect singularities of implicit surfaces. The handle of Whitney's umbrella is detected {z<0, x=y=0}, as well as the intersection of two sheaves around {z>=0, x=y=0}.

Sphere	Whitney's Umbrella	Four lines example
f(x,y,z)=x^2+y^2+z^2-1	f(x,y,z)=x^2-y^2*z	f(x,y,z)=xy(y-x)(y-xz)

We give below a few other examples. On the left column, it is the extracted set {F=0} inter {t=0}. Middle left column represents these sets after collapse. Middle right column after projection with Newton-Raphson. Right columns show a raycasting rendering of the surface (taken from here, very nice but no reconstruction).

Implicit surface	Cubical complex {F=0} inter {t=0}	After collapse	After projection	Raycasting rendering
Whitney umbrella f(x,y,z)=x^2-y^2*z
Crixxi f(x,y,z)=(y^2+z^2-1)^2 +(x^2+y^2-1)^3 = 0
Buggle f(x,y,z)=x^4y^2+y^4x^2-x^2y^2+z^6 = 0

Lachaud07b , Lachaud03c , Lachaud03b

J.-O. Lachaud and R. Malgouyres, Géométrie discrète et images numériques, chapter 3. Topologie, courbes et surfaces discrètes. Traité IC2. Hermès, 2007. In french.

[BibTeX reference] [chapter PS gzipped] [Lavoisier]

Abstract:
La topologie digitale est l'étude des propriétés des objets discrets qui sont indépendantes de leurs propriétés métriques. L'existence d'un trou dans un objet (au sens où un anneau a un trou et un pantalon a deux trous) n'est pas modifiée par une déformation ``continue'' de l'objet. D'un point de vue algorithmique, on cherche souvent à concevoir des méthodes de traitement d'image qui ne modifient pas la topologie des objets (connexité, existence d'un trou, etc). Le formalisme mathématique nécessaire pour définir de telles méthodes est assez abstrait.
Au sens de la topologie, on peut dire que toutes les courbes fermées simples sont équivalentes (ou homéomorphes), et toute courbe fermée simple dans le plan possède un trou, au sens où elle sépare le plan (théorème de Jordan). La notion de déformation continue est formalisée dans la notion d'homotopie. Cette notion permet d'associer aux objets discrets des objets algébriques (des groupes), de manière qu'à deux objets topologiquement équivalents soient associés deux groupes équivalents. Ces invariants algébriques sont fondamentaux dans l'étude des propriétés topologiques des objets. Cette même notion d'homotopie permet de définir les points simples, qui sont les points qu'on peut enlever d'un objet sans en modifier la topologie. Les points simples sont en particulier à la base des algorithmes de squelettisation topologique.
D'autres notions fondamentales en topologie sont les frontières et les surfaces. Par exemple, la frontière d'un objet connexe sans cavité est connexe. Une telle frontière doit satisfaire la propriété de séparation de Jordan. En topologie digitale, on se donne les outils pour définir des frontières et surfaces discrètes qui ont une bonne propriété de séparation. Ces frontières sont ensuite munies de structures de graphes, qui permettent de les construire et de les parcourir efficacement. Des outils existent ensuite pour estimer la géométrie de ces objets ou pour en fabriquer des modèles géométriques.

Keywords: digital topology, digital surface, surface tracking, homotopy, topological invariant

J.-O. Lachaud and A. Vialard, Geometric measures on arbitrary dimensional digital surfaces. In Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI'2003), Napoli, Italy, November 2003, volume 2886 of Lecture Notes in Computer Science, pages 434-443, 2003. Springer.

[BibTeX reference] [paper PS gzipped] [slides PDF] [LNCS]

Abstract:
This paper proposes a set of tools to analyse the geometry of multidimensional digital surfaces. Our approach is based on several works of digital topology and discrete geometry: representation of digital surfaces, bel adjacencies and digital surface tracking, 2D tangent computation by discrete line recognition, 3D normal estimation from slice contours. The main idea is to notice that each surface element is the crossing point of n-1 discrete contours lying on the surface. Each of them can be seen as a 4-connected 2D contour. We combine the directions of the tangents extracted on each of these contours to compute the normal vector at the considered surface element. We then define the surface area from the normal field. The presented geometric estimators have been implemented in a framework able to represent subsets of n-dimensional spaces. As shown by our experiments, this generic implementation is also efficient.

Keywords:
discrete geometry, digital surface, geometric estimators, normal estimation, area estimation

J.-O. Lachaud. Coding cells of digital spaces: a framework to write generic digital topology algorithms. In Proc. Int. Work. Combinatorial Image Analysis (IWCIA'2003), Palermo, Italy, volume 12 of Electronic Notes in Discrete Mathematics, 2003.

[BibTeX reference] [paper PS gzipped] [slides PDF] [ENDM]

Abstract:
This paper proposes a concise coding of the cells of n-dimensional finite regular grids. It induces a simple, generic and efficient framework for implementing classical digital topology data structures and algorithms. Discrete subsets of multidimensional images (e.g. regions, digital surfaces, cubical cell complexes) have then a common and compact representation. Moreover, algorithms have a straightforward and efficient implementation, which is independent from the dimension or sizes of digital images. We illustrate that point with generic hypersurface boundary extraction algorithms by scanning or tracking. This framework has been implemented and basic operations as well as the presented applications have been benchmarked.

Keywords:
digital topology, Khalimsky topology, digital surface tracking, cell coding