DGtal
1.4.beta

Part of the Topology package.
This part of the manual describes how to define digital objects. Subset of a digital sets are not really objects as long as they do not have some adjacency relation which describes how points (pixels in 2D, voxels in 3D, spels in nD) are connected. Digital topology was introduced by Rosenfeld as a framework to describe consistently how objects are connected and how complements of objects are connected. It has lead him to define two different adjacencies relations, one for the foreground (object), one for the background (complement of object). For well chosen adjacency relations, we find again some classical results of topology in continuous domains. For instance, the Jordan property may hold for several couples of adjacencies.
The topology kernel of DGtal allows to define adjacencies, topologies, objects, and operations with objects in a very generic framework. Some of these operations have been specialized for standard spaces and topologies, in order to keep operations as fast as possible.
Once a topology (class DigitalTopology) has been defined from two adjacencies (models of concepts::CAdjacency), a digital object (class Object) has a border which is the set of elements adjacent to its complement. The border is again a digital object. A digital object can also be seen as a graph, which can be traversed in many ways, although the breadthfirst is often very useful (class Expander).
An adjacency relation in a digital space X describes which points of the digital space are close to each other. Generally it is a reflexive and symmetric relation over the points of X. Interested readers can read the works of Azriel Rosenfeld and Gabor Herman to see a wellfounded theory of digital spaces.
In \( Z^2 \), two adjacencies are used. The socalled 4adjacency tells that a 2D point is adjacent to itself and to four other points (north, east, south, and west points). The socalled 8adjacency tells that a 2D point is adjacent to itself and to eight other points (the four points of the 4adjacency relation added with four points in the diagonals). These two adjacencies relations are translation invariant, symmetric, reflexive. You can define them as follows with DGtal:
You can equivalently use the types Z2i::Adj4 and Z2i::Adj8, (namespace Z2i in "DGtal/helpers/StdDefs.h"), defined on SpaceND<2,int>
.
It is well known that if you choose the 4adjacency for an object, one should choose the 8adjacency for the background in order to get consistent topological properties. For instance a simple 4connected digital close curve (of more than 4 points) splits the digital space into two 8connected background components (digital Jordan theorem). The same is true if you choose the 8adjacency relation for the object, the 4adjacency should be choosed for the background. This is called the digital Jordan theorem (Rosenfeld).
Similarly as the 4,8 adjacencies in 3D, the name of the 6, 18, 26 adjacencies defined in Z3 comes from the number of proper adjacent points for each point. Seeing a digital 3D point as a cube, the 6neighbors are the points sharing at least a face with the cube, the 18neighbors are the ones sharing at least an edge, while the 26neighbors are the ones sharing at least a vertex. These three adjacencies relations are translation invariant, symmetric, reflexive. You can define them as follows with DGtal:
You can equivalently use the types Z3i::Adj6, Z3i::Adj18 and Z3i::Adj26, (namespace Z3i in "DGtal/helpers/StdDefs.h"), defined on SpaceND<3,int>
.
Adjacencies based on metrics can be defined in arbitrary dimension. They all have the properties to be translation invariant, reflexive and symmetric. They include the standard 4, 8adjacencies in Z2 and 6, 18, and 26adjacencies in Z3. Given a maximal 1norm n1
, two points p1
and p2
are adjacent if and only if \( \ p2  p1 \_1 \le n1 \) and \( \ p2  p1 \_\infty \le 1 \). Metric adjacencies are implemented in the template class MetricAdjacency. For now, only metric adjacencies in Z2 are specialized, so as to be (slightly) optimized.
Adjacencies are used at many places as a basis for more complex operations. To keep genericity and efficiency, adjacencies should satisfy the concept concepts::CAdjacency. They are specialized only at instanciation as argument to templates. A model of concepts::CAdjacency should define the following inner types:
It should also define the following methods:
Methods writeNeighborhood
and writeProperNeighborhood
are overloaded so as to substitute their own predicate with another usergiven predicate. They are useful to restrict neighborhoods.
A concepts::CDomainAdjacency refines a concepts::CAdjacency by specifying a limiting domain for the adjacency. It adds the following inner types:
It should also define the following methods:
A digital topology is a couple of adjacencies, one for the foreground, one for the background. The template class DigitalTopology can be used to create such a couple.
The following lines of code creates the classical (6,18) topology over \( Z^3 \).
The foreground adjacency is classically called kappa \( \kappa \) while the background is called lambda \( \lambda \) . Any topology has a reversed topology which is the topology \( (\lambda,\kappa) \).
A topology can be a Jordan couple. In this case, some objects of this space have nice properties. The reader is referred to the papers of Herman or to its book Geometry of digital spaces .
A digital object is a set of points together with a topology describing how points are close to each others. In DGtal, they are defined by the template class Object, parameterized by the topology (a DigitalTopology) and a digital set of points (any model of CDigitalSet like DigitalSetBySTLSet or DigitalSetBySTLVector).
The digital object stores its own set of points with a copyonwrite smart pointer. This means that a digital object can be copied without overhead, and may for instance be passed by value or returned. The input digital set given at construction specifies the domain of the object, which remains the same for the lifetime of the object.
A digital object is generally initialized with some given set. The type of the set can be chosen so as to leave to the user the choice of the best set container for the object. You may use the DigitalSetSelector to let the compiler choose your digital set container at compilation time according to some preferences. The choice DigitalSetBySTLSet is the most versatile and generally the most efficient. The choice DigitalSetBySTLVector is only good for very small objects.
Objects may also be initialized empty, so that you can easily use a container to store them. Of course, they are not valid in this case.
An object proposes several methods to return the neighborhood of a given point of the object.
Objects have a border, which are the points which touch the complement in the sense of background adjacency. A border of an object is itself an object, with the same topology as the object.
The resulting border can be visualized for instance by: (see 3dBorderExtraction.cpp)
see example 3dBorderExtraction.cpp
see example: 3dBorderExtractionImg.cpp
The digital topology induces a connectedness relation on the object (transitive closure of the foreground adjacency) and a connectedness relation on the complement of the set (transitive closure of the background adjacency). Objects may be connected or not. The connectedness is stored with the object, if it is known. The method Object::connectedness returns CONNECTED, DISCONNECTED or UNKNOWN depending on the connectedness of this object and if it has been computed. The method Object::computeConnectedness forces the computation. After this process, the connectedness is either CONNECTED or DISCONNECTED.
Furthermore, you can use the method Object::writeComponents to compute all the connected components of this object. It also updates the connectedness of this object to either CONNECTED or DISCONNECTED depending on the number of connected components. Each connected component is of course CONNECTED.
You may use writeComponents as follows:
You must be careful when using an output iterator writing in the same container as 'this' object (see Object::writeComponents).
A basic mechanism for simple points is implemented in the Object class. It relies on the wellknown definition of simple points of [13] , based on the number of connected components in a geodesic neighborhood of the point. It is valid in 2D and 3D. It should not be sufficient in nD, since toric connected components may appear. However, you can use it anyway as a kind of "extended" simplicity.
To test if a point is simple for an object, just call the method Object::isSimple with the point as parameter. To illustrate this, we give the full code for the homotopic thinning of a shape in 2D and 3D.
The file homotopicThinning3D.cpp illustrates the homotopic thinning on a 26_6 object.
First a digital object (with 6_26 adjacency) is defined from a digital set representing two rings :
Then the thinning is performed by testing if a point is simple:
Finally the result can simply be displayed using Viewer3D:
We obtain the following result:
Object::isSimple(input_point)
is an example of a predicate (ie. a function returning a Boolean value) that depends on the topology of the object and on the occupancy configuration of the input_point
neighborhood.
There is a limited amount of possible configuration of the neighborhood depending on the dimension of the space. In 2D, there are 2^8 different neighborhood configurations, and in 3D 2^26. The result of the predicate will vary depending on the topology of the space, but the number of occupancy configurations will be the same for any topology in that dimension.
The calculation of a predicate for each point is repetitive and can be computationally intensive. However thanks to the limited amount of neighborhood occupancy configurations, we can precompute the Boolean result of the predicate for each configuration and store it in a look up table.
In DGtal, precomputed look up tables for different predicates and topologies are distributed with the source code, and decompressed at build/install time to be ready to use. The tables locations are stored in string variables in: "DGtal/topology/tables/NeighborhoodTables.h"
Different functions to work with these precomputed tables are in the header: "DGtal/topology/NeighborhoodConfigurations.h"
Object is able to take advantage of this just preloading the table before calling isSimple. This speeds up a thinning process by orders of magnitude.
In 2D: