Digital topology and digital objects

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 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 breadth-first is often very useful (class Expander).

  1. Adjacency relations
    1. 4- and 8- adjacencies in Z2
    2. 6-, 18- and 26- adjacencies in Z3
    3. Metric adjacencies in Zn
    4. Concepts CAdjacency et CDomainAdjacency
  2. Digital topology over a digital space
  3. Digital objects
    1. Construction of digital objects
    2. Neighborhood of a point in an object
    3. Border of a digital object
    4. Connectedness and connected components
    5. Simple points

Adjacency relations

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 well-founded theory of digital spaces.

4- and 8- adjacencies in Z2

In $ Z^2 $, two adjacencies are used. The so-called 4-adjacency tells that a 2D point is adjacent to itself and to four other points (north, east, south, and west points). The so-called 8-adjacency tells that a 2D point is adjacent to itself and to eight other points (the four points of the 4-adjacency 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:

 typedef int Integer;                // choose your digital line here.
 typedef SpaceND<int,2> Z2;          // Z^2
 typedef MetricAdjacency<Z2,1> Adj4; // 4-adjacency type
 typedef MetricAdjacency<Z2,2> Adj8; // 8-adjacency type
 Adj4 adj4;                          // instance of 4-adjacency
 Adj8 adj8;                          // instance of 8-adjacency

You can equivalently use the types Z2Adj4 and Z2Adj8, defined on SpaceND<int,2>.

It is well known that if you choose the 4-adjacency for an object, one should choose the 8-adjacency for the background in order to get consistent topological properties. For instance a simple 4-connected digital close curve (of more than 4 points) splits the digital space into two 8-connected background components (digital Jordan theorem). The same is true if you choose the 8-adjacency relation for the object, the 4-adjacency should be choosed for the background. This is called the digital Jordan theorem (Rosenfeld).


Illustration of a Digital Object with the 4-adjacency


Illustration of a Digital Object with the 8-adjacency

6-, 18- and 26- adjacencies in Z3

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 6-neighbors are the points sharing at least a face with the cube, the 18-neighbors are the ones sharing at least an edge, while the 26-neighbors 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:

 typedef int Integer;                 // choose your digital line here.
 typedef SpaceND<int,3> Z3;           // Z^3
 typedef MetricAdjacency<Z3,1> Adj6;  // 6-adjacency type
 typedef MetricAdjacency<Z3,2> Adj18; // 18-adjacency type
 typedef MetricAdjacency<Z3,3> Adj26; // 26-adjacency type
 Adj6 adj6;                           // instance of 6-adjacency
 Adj18 adj18;                         // instance of 18-adjacency
 Adj26 adj26;                         // instance of 26-adjacency

You can equivalently use the types Z3Adj6, Z3Adj18 and Z3Adj26, defined on SpaceND<int,3>.

Metric adjacencies in Zn

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-, 8-adjacencies in Z2 and 6-, 18-, and 26-adjacencies in Z3. Given a maximal 1-norm n1, two points p1 and p2 are adjacent if and only if $ \| p2 - p1 \|_1 \le n1 $ and $ \| p2 - p1 \|_\infty \le 1 $.

 const int n = ...;                   // choose your dimension.
 typedef int Integer;                 // choose your digital line here.
 typedef SpaceND<int,n> Zn;           // Z^N
 const int n1 = ...;                  // choose your max 1-norm here.
 typedef MetricAdjacency<Zn,n1> MyAdj;// your adjacency type.
 Myadj myAdj;                         // your instance.

Concepts CAdjacency et CDomainAdjacency

Adjacencies are used at many places as a basis for more complex operations. To keep genericity and efficiency, adjacencies should satisfy the concept CAdjacency. They are specialized only at instanciation as argument to templates. A CAdjacency concept 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 user-given predicate. They are useful to restrict neighborhoods.

A CDomainAdjacency refines a CAdjacency by specifying a limiting domain for the adjacency. It adds the following inner types:

It should also define the following methods:

Digital topology over a digital space

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 $.

 typedef SpaceND< int, 3 > Z3;
 typedef MetricAdjacency< Z3, 1 > Adj6;
 typedef MetricAdjacency< Z3, 2 > Adj18;
 typedef DigitalTopology< Adj6, Adj18 > DT6_18;

 Adj6 adj6;
 Adj18 adj18;
 DT6_18 dt6_18( adj6, adj18, JORDAN_DT );

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 .

Digital objects

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 copy-on-write 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.

Construction of digital objects

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.

 typedef Z3::Point Point;
 typedef HyperRectDomain< Z3 > Domain; 
 typedef Domain::ConstIterator DomainConstIterator; 
 typedef DigitalSetSelector< Domain, BIG_DS+HIGH_BEL_DS >::Type DigitalSet;
 typedef Object<DT6_18, DigitalSet> ObjectType;

 Point p1( -50, -50, -50 );
 Point p2( 50, 50, 50 );
 Domain domain( p1, p2 );
 Point c( 0, 0 );
 // diamond of radius 30
 DigitalSet diamond_set( domain );
 for ( DomainConstIterator it = domain.begin(); it != domain.end(); ++it )
     if ( (*it - c ).norm1() <= 30 ) diamond_set.insertNew( *it );
 ObjectType diamond( dt6_18, diamond_set );
 // The following line takes almost no time.
 ObjectType diamond_clone( diamond );
 // Since one of the objects is modified, the set is duplicated at the following line
 diamond_clone.pointSet().erase( c );

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.

 ObjectType object;          // valid
 vector<ObjectType> objects; // valid

Neighborhood of a point in an object

An object proposes several methods to return the neighborhood of a given point of the object.

Border of a digital 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.

 ObjectType bdiamond = diamond.border(); // one component
 ObjectType bdiamond_clone = diamond_clone.border(); // two components

Connectedness and connected components

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:

 std::vector< ObjectType > objects;
 std::back_insert_iterator< std::vector< ObjectType > > inserter( objects );
 // nbc == 1 since the boundary of the diamond is connected.
 unsigned int nbc = bdiamond.writeComponents( inserter );
 // nbd == 2 since the boundary of the diamond minus its center is disconnected.
 unsigned int nbd = bdiamond_clone.writeComponents( inserter );
 // objects.size() == 3

You must be careful when using an output iterator writing in the same container as 'this' object (see Object::writeComponents).

Simple points


Generated on Wed Oct 6 10:18:19 2010 for DGtal by  doxygen 1.6.3