DGtal 1.3.0

Part of the Topology package.
This part of the manual describes how to define cellular grid space or cartesian cubic spaces, as well as the main objects living in these spaces. A lot of the ideas, concepts, algorithms, documentation and code is a backport from ImaGene.
2D images are often seen as two dimensional arrays, where each cell is a pixel with some value (a gray level, a color). If \(\mathbf{Z}\) is the set of integer numbers, then an image is a map from a rectangular subset of \(\mathbf{Z} \times \mathbf{Z}\) to some space (gray levels, colors).
More generally, a nD image is a map from a parallelepipedic subset of \(\mathbf{Z}^n\) to some space (gray levels, colors).
Many algorithms need to represent positions in images (ie pixels and voxels), in order to represent regions in images. Often, we need also to measure the shape of a region, for instance its perimeter, or we may be interested in the interface between two regions. In these cases, it is often convenient (and generally it is also the theoretic way) to represent other elements in digital spaces, such as paths inbetween regions, the thin boundary or surface of a region, etc. We need in this case to represent not only the "squares" (pixels) or "cubes" (voxels) of images, but also their faces, edges, vertices.
We therefore model not only ndimensional cells (the hypercubes in nD), but also all the lower dimensional cells of the space. For instance, in 2D, we have:
The set of all cells \(\mathbf{F}^n\) is called the ndimensional space of cubical complexes, or ndimensional cellular grid space. The couple \((\mathbf{F}^n,\subseteq)\) is a partially ordered set or poset. Let \(X\) be any subset of \(\mathbf{F}^n\). The set \(\mathcal{U}=\{U \subseteq X / \forall x \in U, x^{\uparrow} \subseteq U \}\), where \(x^{\uparrow}=\{y \in X, x \le y\}\) or the up incident cells of x, is a topology on \(X\), called the Aleksandrov topology. Therefore we can use standard combinatorial topology results for any subset of the cellular grid space.
Cells of the cellular grid space are illustrated below. The paving mode of digital space gives a nice illustration of what is this space. The 2cell is in red, the 1cell in green, the 0cell in blue.
We use now the regularity of the cubical grid to represent it efficiently. In 1D, the cubical grid is a simple line alternating closed points {k} and open unit segments (k,k+1). Khalimsky noticed that this (topological) space is homeomorphic to the integer set \(\mathbf{Z}\), if we declare every even integer as closed and every odd integer as open.
A digital cell in 1D is thus just an integer. Its topology is defined by its parity. The cell 2k is the closed point {k}; the cell 2k+1 is the segment (k,k+1) (considered open).
In 2D, we use the fact that \(\mathbf{Z}^2\) is a cartesian product. A digital cell in 2D is thus a couple of integer
In nD, the principle is the same. A cell is thus uniquely identifed by an ntuple of integers whose parities define the topology of the cell. These integers are called the Khalimsky coordinates of the cell.
For instance, the pixel (x,y) of the digital space \(\mathbf{Z}^2\) corresponds to the 2cell (2x+1,2y+1) of the cellular grid space \(\mathbf{F}^2\).
Instead of chosing a specific implementation of a cellular grid space, we keep the genericity and efficiency objective of DGtal by defining a cellular grid space as the concept CCellularGridSpaceND. It provides a set of types (Cell, SCell, etc) and methods to manipulate cells of arbitrary dimension. Models of CCellularGridSpaceND are:
The inner types are:
find
, model of boost::UniqueAssociativeContainer and boost::SimpleAssociativeContainer).find
, model of boost::UniqueAssociativeContainer and boost::SimpleAssociativeContainer).find
, model of boost::UniqueAssociativeContainer and boost::SimpleAssociativeContainer).typename
X::template CellMap<Value>::Type, which is a model of boost::UniqueAssociativeContainer and boost::PairAssociativeContainer.typename
X::template SCellMap<Value>::Type, which is a model of boost::UniqueAssociativeContainer and boost::PairAssociativeContainer.typename
X::template SurfelMap<Value>::Type, which is a model of boost::UniqueAssociativeContainer and boost::PairAssociativeContainer.Methods include:
An comprehensive description is given in CCellularGridSpaceND.
We use hereafter the model KhalimskySpaceND. To create a 2D cellular grid space where cells have coordinates coded with standard int
(32 bits generally), we can write:
Note that the cellular grid space is limited by the given bounds. Since the user has chosen a closed space, the Khalimsky coordinates of cells are bounded by:
Another frequent way of constructing a cellular grid space is to start from a preexisting digital space and HyperRectDomain. You can define the associated cellular grid space as follows:
If you wish to build a digital space and a HyperRectDomain from a cellular grid space K, you may write:
Last but not least, for standard users it is generally enough to use the default types provided in DGtal/helpers/StdDefs.h.
There are many ways of creating cells within a cellular grid space. The simplest way is certainly to give the Khalimsky coordinates of the cell you wish to create. Its topology is then induced by its coordinates. We use generally KhalimskySpaceND::uCell for arbitrary cells, KhalimskySpaceND::uSpel for ndimensional cells, KhalimskySpaceND::uPointel for 0dimensional cells.
The full code of this example is in file ctopo1.cpp. Pointels or 0cells are displayed in blue, linels or 1cells in green, pixels or 2cells in red. Note that KhalimskySpaceND::uCell requires Khalimsky coordinates while the two others require digital coordinates (the topology is known in the two latter cases).
The file ctopo13d.cpp shows another example in 3D:
Up to now, we have only consider unsigned cells (type Cell). However it is often convenient to assign a sign (POS or NEG) to a cell, a kind of orientation. The sign is especially useful to define boundary operators and digital surfaces. It is also used in algebraic topological models of cubical complexes, for instance to define chains (formal sums of cells).
Signed cells have type SCell. They are created using methods KhalimskySpaceND::sCell for arbitrary cells, KhalimskySpaceND::sSpel for ndimensional cells, KhalimskySpaceND::sPointel for 0dimensional cells. The user gives the sign at creation, either K.POS or K.NEG if K is the space.
You may use methods KhalimskySpaceND::sSign, KhalimskySpaceND::sSetSign KhalimskySpaceND::signs, KhalimskySpaceND::unsigns, KhalimskySpaceND::sOpp, respectively to get the sign of a signed cell, to change the sign of a signed cell, to sign an unsigned cell, to unsign a signed cell, and to compute the cell with opposite sign.
All methods concerning unsigned cells are prefixed by u
, all methods concerning signed cells are prefixed by s
.
Note that the sign of the signed and unsigned are well taked into account in the display with Viewer3D .
Since one does not necessarily know which model of CCellularGridSpaceND you may be using, you cannot access the cell coordinates directly. Therefore a model of CCellularGridSpaceND provides a set of methods to access and modify cell coordinates and topology. Here a few of them (with the model example KhalimskySpaceND)
Note that you dispose also of a whole set of methods to determine cells according to different geometric queries. The following methods do not change the topology of the input cell only the coordiantes. Again the prefix u
is related to method taking as input unsigned cells while the prefix s
is related to signed cells:
Getting the next cell in this space such that if one starts from the first cell (with same topology) of the space and iterates this process, then all cells of the space with same topology were visited. This may be done with KhalimskySpaceND::uNext, KhalimskySpaceND::sNext. Below is a code snippet that does a scanning of all cells of same topology between first and last cell.
For instance (see. khalimskySpaceScanner.cpp) you will obtain the default following scan:
As said above, the cell topology is defined by the parity of its Khalimsky coordinates. The number of coordinates where the cell is open define the dimension of the cell. A cell of maximal dimension (n) is called a pixel in 2D, a voxel in 3D, and sometimes called a spel or xel in nD. A cell of minimial dimension (0) is often called a pointel. n1 cells are called surfels (or sometimes linels in 2D). Here are the methods related to the cell topology.
you may iterate over all open coordinates (or all closed coordinates) of a cell with the iterator returned by KhalimskySpaceND::uDirs and KhalimskySpaceND::sDirs (KhalimskySpaceND::uOrthDirs and KhalimskySpaceND::sOrthDirs for closed coordinates), such as in this snippet:
You may obtain the cells of same topology which are (face)adjacent to a given cell with the following methods:
Cells incident to some cell touch the cell but do not have the same dimension. Cells lower incident to a cell have lower dimensions, cells upper incident to a cell have higher dimensions. Specific rules determine the sign of incident cells to a signed cell:
These rules together allow the definition of (co)boundary operators, which are homomorphisms between chains of cells. They have the property that applied twice they give the null chain. Otherwise said, the boundary of a set of cells has an empty boundary.
The cell incident to some given cell along some axis and in forward or backward direction is returned by KhalimskySpaceND::uIncident and KhalimskySpaceND::sIncident.
One of the two cells that are incident to some signed cells along some axis has a positive sign. The orientation (forward or backward) is called the direct orientation. It is returned by KhalimskySpaceND::sDirect. It is worth to note that the following assertion is always true:
In addition to the CCellularGridSpaceND requirements, KhalimskySpaceND allows the use of different closures for each dimension and the use of periodic dimension.
The closure is specified at the space initialization:
Therefore, any coordinates are valid along a periodic dimension but the coordinates accessors of KhalimskySpaceND will always return a coordinate between the two bounds given at the initialization:
It is also possible to span a subspace that crosses the bounds along a periodic dimension:
If you need to arbitrarily manipulate the cells coordinates without bounds checking, or if you simply doesn't need a bounded space, you may consider KhalimskyPreSpaceND.
It is a model of CPreCellularGridSpaceND, that is a base concept of CCellularGridSpaceND. The main difference is that CPreCellularGridSpaceND doesn't require to initialize the space with bounds and some bounds related methods (like KhalimskySpaceND::uGetMin) are not available.
Therefore, KhalimskyPreSpaceND is a purely static class that provides almost all the methods of KhalimskySpaceND but without bounds influence (coordinates validity, restricted neighborhood, ...) and is also fully compatible with KhalimskySpaceNDbased algorithms when bounds are not necessary.
The main features are:
coordinates
public member of KhalimskyPreCell and SignedKhalimskyPreCell: