DGtal  1.4.beta
Helpers for digital surfaces
Author(s) of this documentation:
Bertrand Kerautret and Jacques-Olivier Lachaud.

Part of the Topology package.

This part of the manual describes how to use the helper class Surfaces to build digital surfaces, closed or open, or contours within digital surfaces. A lot of the ideas, concepts, algorithms, documentation and code is a backport from ImaGene.

All the code presented here require:

#include "DGtal/topology/helpers/Surfaces.h"
This class is useful if you wish only to obtain the set of surfels of a given digital surface or if you wish to obtain 2D contours (in 2D or 3D). If you require more advanced operations on surfaces (for instance using afterwards the topology defined on the surface), it is better to wrap a DigitalSurface object around your surface of interest, see Digital surfaces.

The 2D case: the boundary is a sequence of cells

The surfaces classes offers the possibility to extract an open or closed contour as a sequence of surfels obtained from a DigitalSet and a starting surfel. The full code of this example is available in file ctopo-2.cpp .

The first step to extract the surfel boudary of a 2D digital set is to obtain an initial boundary surfel:

aCell = Surfaces<Z2i::KSpace>::findABel(ks, set2d);

The first surfel can also be displayed in red with Board2D:

Board2D board;
board << image.domain() << set2d; // display domain and set
board << CustomStyle( aCell.className(), new CustomColors( Board2D::Color( 255, 0, 0 ),
Board2D::Color( 192, 0, 0 ) ));
board << aCell;

Start surfel before a tracking (in red).
Then you can extract the sequence of consecutive surfels:
std::vector<Z2i::SCell> vectBdrySCell;
SurfelAdjacency<2> SAdj( true );
ks, SAdj, set2d, aCell );
and display it:
GradientColorMap<int> cmap_grad( 0, vectBdrySCell.size() );
cmap_grad.addColor( Board2D::Color( 50, 50, 255 ) );
cmap_grad.addColor( Board2D::Color( 255, 0, 0 ) );
cmap_grad.addColor( Board2D::Color( 255, 255, 10 ) );
unsigned int d=0;
std::vector<Z2i::SCell>::iterator it;
for ( it=vectBdrySCell.begin() ; it != vectBdrySCell.end(); it++ ){
board<< CustomStyle((*it).className() ,
new CustomColors( Board2D::Color::Black,
cmap_grad( d )))<< *it;

You will obtain the following ordered sequence of surfels:

Tracking of a closed 2D contour.

The resulting sequence of surfels does not necessary present an open contour (try for instance image "samples/circleR10modif.pgm"):

Tracking of an open 2D contour.

Tracking a 3D boundary to build a surface.

With only few modifications we can apply the same extraction on 3D surfel set. The file ctopo-2-3d.cpp shows the same previous example adapted in 3D.

with the same code we can get a surfel boundary:

From this SCell all the surfel connected sets can be extracted:

// Extracting all boundary surfels which are connected to the initial boundary Cell.
ks,SAdj, set3d, aCell );

To see both initial surfel and the surfel set, we can use the transparent mode:

viewer << SetMode3D((*(vectBdrySCellALL.begin())).className(), "Transparent");

To avoid surfel superposition we need to increase with a small shift the surfel size, for this purpose you can add the following key:

viewer << Viewer3D<>::shiftSurfelVisu;

or use the special mode "Highlighted" which increase automaticly the surfel size.

You can obtain for instance the following visualisation:

Tracking surfaces in 3D (start surfel in green).

Since in 3D there are several choice for the direction used to exctract surfel boundary, we can specify the constant direction need to drive the surfel extraction:

// Extract the boundary contour associated to the initial surfel in its first direction
ks, *(ks.sDirs( aCell )),SAdj, set3d, aCell );

After extracting the two surfels cut you may obtain the following visualisation:

Tracking surfaces and slices in 3D (start surfel in green).

Extracting surface of connected components

The class Surfaces provides other useful function to extract connected boundary surfels from a digital set and given a surfel adjacency definition. The example 3dKSSurfaceExtraction.cpp shows an example of such an extraction.

From a domain we construct a DigitalSet inserting points under given conditions (see. 3dKSSurfaceExtraction.cpp for more details)

#include "DGtal/helpers/Surfaces.h"
#include "DGtal/topology/KhalimskySpaceND.h"
Domain domain( p1, p2);
DigitalSet diamond_set( domain );
diamond_set.insertNew( *it );

With this domain bounding points (p1, p2), a KhalimskySpace is constructed and a SurfelAdjacency definition is introduced.

K.init(p1, p2, true);
SurfelAdjacency<3> SAdj( true );

Then we can extract all connected surfels from the digitalSet surface :

SetPredicate<DigitalSet> shape_set_predicate( diamond_set );
Surfaces<KSpace>::extractAllConnectedSCell(vectConnectedSCell,K, SAdj, shape_set_predicate);

After processing a simple display of each resulting connecting component you can obtain such a visualisation:

Visualisation of connected set of SignedKhalimskySpaceND

Here since the last argument is set to true, the resulting SignedKhalimskySpaceND are signed in order to indicate the direction of exterior. You can also get the SignedKhalimskySpaceND with default sign:

Surfaces<KSpace>::extractAllConnectedSCell(vectConnectedSCell,K, SAdj, shape_set_predicate, false);

and you will get the resulting cell display:

Visualisation of connected set of oriented surfels of a KhalimskySpaceND.

Filling oriented digital contours

The helper class Surface also proposes some methods to fill the interior/exterior of a digital set of 1-SCell which can be defined from an oriented FreemanChain. These methods can be usefull in particular to reconstruct images (as given for instance in the tool of freeman2pgm given in DGtalTools.).

The example ctopo-fillContours.cpp illustrates a basic filling with a shape containing a hole. The main steps to fill a contour represented by a FreemanChain are the following:

First we construct two FreemanChain to illustrate the fill with two different orientations:

FreemanChain<int> fc1 ("001001001001001111101111011222222223222222322233333330301033333003", 6, 14);
FreemanChain<int> fc2 ("1111000033332222", 6, 20);

To construct the set of signed SCell, we use the method getInterPixelLinels of FreemanChain class:

The that the resulting Cell orientation is defined by convention such that a contour defined in the direct orientation will generate the fill of the interior of the shape (with the uComputeInterior method) while the indirect orientation should be used to define a hole (see example below).

Afterwards the region associated with the direct oriented contour (fc1) can be filled by using the method uComputeInterior with the parameter empty_is_inside set to false. This parameter choice is justified since here a line which does not contain any boundary element is necessary at the outside of the contour.

typedef ImageContainerBySTLMap< Z2i::Domain, bool> BoolImage2D;
BoolImage2D::Domain imageDomain( Z2i::Point(0,10), Z2i::Point(20,30) );
BoolImage2D interiorCellImage( imageDomain );
Surfaces<DGtal::KhalimskySpaceND< 2, int > >::uFillInterior(K, functors::SurfelSetPredicate<std::set<SCell>,SCell>(boundarySCell),
interiorCellImage, 1, false);

The interior Cells obtained from such a contour are illustrated here:

Filling interior of direct oriented contour.

We can also reconstruct region with hole by using a contour in the indirect direction. For instance we can define

And after adding it to the previous set boundarySCell you will obtain such a display:

Filling interior of direct oriented contour.
From an indirect oriented contour you can also fill both the interior and exterior:
BoolImage2D interiorCellHoleImage( imageDomain );
BoolImage2D exteriorCellHoleImage( imageDomain );
Surfaces<DGtal::KhalimskySpaceND< 2, int > >::uFillInterior(K, functors::SurfelSetPredicate<std::set<SCell>, SCell>(boundarySCellhole),
interiorCellHoleImage, 1, true);
Surfaces<DGtal::KhalimskySpaceND< 2, int > >::uFillExterior(K, functors::SurfelSetPredicate<std::set<SCell>, SCell>(boundarySCellhole),
exteriorCellHoleImage, 1, false);
For the interior region, the parameter empty_is_inside parameter is set to true since a line without boundary element will correspond to the interior of the shape (since the contour is given the indirect orientation). In the same way, the parameter empty_is_outside is set to false. You will obtain such a representation:
Filling interior (lightgray) and exterior (dark gray) of indirect oriented contour.

Your challenge

Now you are able both to extract a set of contours and to fill contours. The exercise is now to reconstruct an image from a given set of contours.


You challenge is to code:

  1. The load the set of all the Freeman Chains given in a text file.
  2. Transform Freeman Chains into signed cells of KhalimskySpaceND (SCell).
  3. Reconstruct an image associated to its Freeman Chains by filling.
  4. Identify image hole and fill it with specific gray level.
  5. Exporting resulting image in pgm format.


  • The class PointListReader contains various method to read input from text file. In particular you can use the method getFreemanChainsFromFile (step 1). To reconstruct the image you can first define some types from KhalimskySpaceND with also the resulting image:
    To apply the reconstruction, you can use the following file given in this path: DGtal/examples/samples/contourS2.fc
  • Then you will also need to transform the freeman chain into signed cells (SCell) given in the KhalimskySpaceND. For this purpose you can use the FreemanChain method getInterPixelLinels (step 2).
  • For the step (3) you have first to save on cell by exploiting the filling described in the previous section. Then you can update the resulting image in particular with the method uCoords from KhalimskySpaceND which allows you to recover the coordinate in image domain. For instance to set to 255 the image pixel associated to the Cell c, you can do:
    imageResult.setValue(ks.uCoords(*it), 255);
  • To identify the holes of step (4) you have to exploit the contour orientation. For this purpose you can use the method ccwLoops of the FreemanChain class.
    We recall that by convention holes are oriented in the CW direction (or indirect order).
  • Finally you can export the result just by including the GenericWriter and the flux operator:
    #include "DGtal/io/writers/GenericWriter.h"
    yourImage >> "yourImageName.pgm";


If you succeed the exercise you will obtain the following pgm image:

Awaited result of exercice with the main region filled in white and holes represented in gray.
Space::Point Point
Definition: StdDefs.h:95
Definition: ImageContainerBySTLVector.h:126
bool init(const Point &lower, const Point &upper, bool isClosed)
Specifies the upper and lower bounds for the maximal cells in this space.
KSpace K
Definition: testCubicalComplex.cpp:62
DirIterator sDirs(const SCell &p) const
Given a signed cell [p], returns an iterator to iterate over each coordinate the cell spans.
Represents a signed cell in a cellular grid space by its Khalimsky coordinates and a boolean value.
Definition: KhalimskySpaceND.h:208
static void getInterPixelLinels(const KhalimskySpaceND< 2, TInteger > &aKSpace, const FreemanChain &fc, typename KhalimskySpaceND< 2, TInteger >::SCellSet &aSCellContour, bool aFlagForAppend=false)
static void trackBoundary(SCellSet &surface, const KSpace &K, const SurfelAdjacency< KSpace::dimension > &surfel_adj, const PointPredicate &pp, const SCell &start_surfel)
Z3i::KSpace KSpace
Definition: testArithmeticalDSSComputerOnSurfels.cpp:48
KhalimskyCell< dim, Integer > Cell
Definition: KhalimskySpaceND.h:415
SignedKhalimskyCell< dim, Integer > SCell
Definition: KhalimskySpaceND.h:417
static void track2DBoundary(std::vector< SCell > &aSCellContour2D, const KSpace &K, const SurfelAdjacency< KSpace::dimension > &surfel_adj, const PointPredicate &pp, const SCell &start_surfel)
static SCell findABel(const KSpace &K, const PointPredicate &pp, unsigned int nbtries=1000)
HyperRectDomain< Space > Domain
Definition: testSimpleRandomAccessRangeFromPoint.cpp:44
Point uCoords(const Cell &c) const
Return its digital coordinates.
KSpace::SCell SCell
Definition: StdDefs.h:149
static void extractAllConnectedSCell(std::vector< std::vector< SCell > > &aVectConnectedSCell, const KSpace &aKSpace, const SurfelAdjacency< KSpace::dimension > &aSurfelAdj, const PointPredicate &pp, bool forceOrientCellExterior=false)
Domain domain
Definition: testProjection.cpp:88
KSpace::Cell Cell
Definition: testCubicalComplex.cpp:56
Z3i::SCell SCell
Definition: digitalPolyhedronBuilder3D.cpp:79
Aim: A wrapper class around a STL associative container for storing sets of digital points within som...
Definition: DigitalSetByAssociativeContainer.h:89
Aim: This class is a model of CCellularGridSpaceND. It represents the cubical grid as a cell complex,...
Definition: KhalimskySpaceND.h:64