DGtal  0.9.4beta
Digital straight lines and segments

Table of Contents

Author
Tristan Roussillon

Part of the Geometry package.

This module gathers classes that represent and recognize digital straight segments. To dynamically recognize DSSs along a sequence of points, the basic class is ArithmeticalDSSComputer, which is a model of concepts::CDynamicBidirectionalSegmentComputer. Each instance of ArithmeticalDSSComputer has an instance of ArithmeticalDSS, which represents the recognized digital straight segment. Moreover, any instance of ArithmeticalDSS has an instance of ArithmeticalDSL, which represents the bounding digital straight line of minimal parameters. We detail below these three classes in a reverse order.

Related examples are exampleArithmeticalDSL.cpp, exampleArithmeticalDSS.cpp, and exampleArithmeticalDSSComputer.cpp

Digital straight lines

A digital straight line (DSL) of slope \( a/b \) (with \( a,b, \in \mathbb{Z} \), \( \gcd(a,b) = 1 \)), intercept \( \mu \in \mathbb{Z} \) and thickness \( \omega \in \mathbb{Z} \), which is conveniently denoted by \( D(a,b,\mu,\omega) \), is the set of digital points \( (x,y) \in \mathbb{Z}^2 \) such that \( \mu \leq ax - by < \mu + \omega \) (Reveilles, 1991 [62]).

Any DSL such that \( \omega = \max(|a|,|b|) \) (resp. \( \omega = |a| + |b| \)) is said to be naive (resp. standard) and is simply 8-connected (resp. 4-connected) (Reveilles, 1991 [62]).

For instance, the naive DSL \( D(2,5,0,5) \) is depicted below:

NaiveDSL.png
Example of Naive DSL

The standard DSL \( D(2,5,0,7) \) is thicker:

StandardDSL.png
Standard DSL of same slope and same intercept

From now on, let us assume that \( \omega \) is either equal to \(\max(|a|,|b|) \) (naive case) or to \( |a| + |b| \) (standard case). Then, any DSL is merely denoted by \( D(a,b,\mu) \).

Short example

A naive DSL can be declared and constructed as follows:

// Construct a naive DSL from a, b, mu
NaiveDSL<Integer> line( 2, 5, 0 );

Then, within a window defined by two points (called firstPoint and lastPoint below), you can iterate over the DSL points:

// Draw the DSL points between firstPoint and lastPoint
for ( NaiveDSL<Integer>::ConstIterator
it = line.begin(firstPoint),
ite = line.end(lastPoint);
it != ite; ++it )
{
board << SetMode( it->className(), "Paving" )
<< *it; //Draw the point
}
Note
Note the difference of semantic between method ArithmeticalDSL.begin(), which returns an iterator pointing to the input point, and method ArithmeticalDSL.end(), which returns an iterator pointing past to the input point.

In the standard case, it is enough to replace Naive by Standard.

// Construct a standard DSL from a, b, mu
StandardDSL<Integer> line( 2, 5, 0 );

In order to use classes NaiveDSL and StandardDSL, you must include the following file:

#include "DGtal/geometry/curves/ArithmeticalDSL.h"

Classes NaiveDSL and StandardDSL are both aliases of the class ArithmeticalDSL, which represents either a naive or a standard DSL. It gathers the generic code that represents a DSL in any octant.

Orientation

The arithmetical representation \( (a, b, \mu) \) is redondant. Exactly two representations describe one DSL. For instance, \( D(2,5,0) \) and \( D(-2,-5,-5) \) corresponds to the same set of points. This representation is thus interesting, since it includes an orientation preferably chosen to iterate over the DSL points from any point belonging to the DSL.

StandardDSL.png
D(2,5,0) and D(-2,-5,-5) represents the same set of points
Note
Note that you must use method ArithmeticalDSL.negate() to get a representation from another one. Note also that method ArithmeticalDSL.equalsTo() compare two representations and returns 'true' iff the parameters \( a, b \) and \( \mu \) of the two representations are equal. However, the equality operator ArithmeticalDSL.operator== compare two sets of points and returns 'true' iff the two sets of points are equal, whatever the orientation.

Data members

ArithmeticalDSL stores as data members not only the parameters \( a, b \) and \( \mu \), but also redondant parameters described below. These extra parameters are useful to efficiently iterate over the DSL points.

Note
Data member myShift (resp. mySteps) is computed with respect to myA and myB in ArithmeticalDSLKernel::steps() (resp. ArithmeticalDSLKernel::shift()). ArithmeticalDSLKernel contains the part of the code that depends on the arithmetical thickness (either naive or standard).

Below, three naive DSLs are depicted in the first three octants. Vectors mySteps.first ( \( v \)), mySteps.second ( \( w \)) and myShift ( \( s \)), are repectively depicted in blue, green and red. The two vectors of the orthonormal basis are depicted in black.

ArithmeticalDSL-8-0-5-8.png
Naive DSL D(5,8,0)
ArithmeticalDSL-8-1-8-5.png
Naive DSL D(8,5,0)
ArithmeticalDSL-8-2-8-m5.png
Naive DSL D(8,-5,0)

Other octants and specific cases are generated in exampleArithmeticalDSL.cpp.

Main features

ArithmeticalDSL is a model of CPointFunctor, ie. it has a function operator ArithmeticalDSL.operator() that returns 'true' iff the input point belongs to the DSL. Note that a point \( (x,y) \) belongs to the DSL iff its remainder \( ax - by \) lies between \( \mu \) (included) and \( \mu + \omega \) (excluded). Method ArithmeticalDSL.remainder() returns the remainder of any input point.

On the other hand, there is a one-to-one mapping between a DSL point and its position in the DSL. For instance, for each x-coordinate \( x \), there is one and only one point \( (x,y) \in \mathbb{Z}^2 \) that belongs to the naive DSL \( D(2,5,0) \). Similarly, for each value \( x+y \), there is one and only one point \( (x,y) \in \mathbb{Z}^2 \) that belongs to the standard DSL \( D(2,5,0) \). Method ArithmeticalDSL.position() returns the position of any input point, whereas method ArithmeticalDSL.getPoint() returns the point located at the specified position. Methods ArithmeticalDSL.before() and ArithmeticalDSL.beforeOrEqual() provide a way of comparing the position of two given points, with respect to the orientation given by \( a \) and \( b \).

ArithmeticalDSL also provides services to iterate over the DSL points from any point belonging to the DSL. ArithmeticalDSL is a model of CConstBidirectionalRange that has inner types called ArithmeticalDSL::ConstIterator and ArithmeticalDSL::ConstReverseIterator, both models of readable iterator and random access iterator. The reader may have a look at the increment and decrement operator of ArithmeticalDSL::ConstIterator (ie. ArithmeticalDSL::ConstIterator.increment and ArithmeticalDSL::ConstIterator.decrement) to see that the code is generic.

We list below the main methods of ArithmeticalDSL:

Avoiding overflows

You may have noticed that myLowerBound ( \( \mu \)) is a member of type ArithmeticalDSL::Integer, whereas myA ( \( a \)) and myB ( \( b \)) are members of type ArithmeticalDSL::Coordinate. For any lower leaning point of coordinates \( (x, y) \) such that \( ax - by = \mu \), myLowerBound may require \( 2n+1 \) bits if \( a \) and \( b \) are stored with \( n \) bits. Therefore, NaiveDSL and StandardDSL have not only one template parameter, but two. The first one for the coordinates and the slope, the second one, which should represent a larger domain of integers, for the intercepts and the remainders.

You can set the second template parameter as follows in order to avoid any overflow:

NaiveDSL<DGtal::int16_t, DGtal::int32_t> line2( 17711, 28657, 1607895256 );
//NB: 1 607 895 256 is the remainder of the point (32 767,-32 767),
//whose coordinates are representable by the type DGtal::int16_t
trace.info() << line2 << line2.isValid(); //ok

Note that an instance of ArithmeticalDSL is valid iff parameters \( a \) and \( b \) are not both null, are relatively prime, and all the redondant parameters are consistents (see ArithmeticalDSL.isValid() and ArithmeticalDSL.checkShiftAndSteps()).

To go further

In order to perform operations on the continued fraction expansion of the slope, you may consider the usage of the class StandardDSLQ0 (see Patterns, digital straight lines and subsegments). The main differences between ArithmeticalDSL and StandardDSLQ0 are listed below:

Class -ArithmeticalDSL- -StandardDSLQ0-
Slope representation two signed integers an irreductible fraction, whose type is a model of CPositiveIrreducibleFraction
Orientation any octant first quadrant only
Thickness naive and standard standard only

Digital straight segments

We have seen that the points of a DSL may be visited within a range bounded by two points. A digital straight segment (DSS) represents such a set of points.

Short example

A 8-connected naive DSS can be declared and constructed as follows:

// Construct a naive DSS
NaiveDSS8<Integer> segment( 5, 8, //slope
Point(0,0), Point(8,5), //ending points
Point(0,0), Point(8,5), //upper points
Point(3,1), Point(3,1) //lower points
);

You can iterate over the whole set of DSS points as follows:

// Trace the position and remainder of each point
for (NaiveDSS8<Integer>::ConstIterator
it = segment.begin(),
ite = segment.end();
it != ite; ++it )
{
trace.info() << "("
<< segment.position( *it ) << ","
<< segment.remainder( *it )
<< ") ";
}

In addition, you can draw either the points of a DSS or its bounding box with Board2D (there are two drawing modes: "Points" and "BoundingBox").

Board2D board;
// Draw the grid
Domain domain( Point(0,0), Point(8,5) );
board << SetMode(domain.className(), "Grid")
<< domain;
//Draw the points of the DSS
board << SetMode("PointVector", "Both");
board << SetMode(segment.className(), "Points")
<< segment;
// Draw the bounding box
board << SetMode(segment.className(), "BoundingBox")
<< segment;

The result of this short example taken from exampleArithmeticalDSS.cpp is presented below:

NaiveDSS8.png
A simply 8-connected naive DSS with its bounding box

See Board2D: a stream mechanism for displaying 2D digital objects to read more about the drawing mechanism.

Similarly, in the standard case, you may write:

// Construct a standard DSS
StandardDSS4<Integer> segment( 5, 8, //slope
Point(0,0), Point(8,5), //ending points
Point(0,0), Point(8,5), //upper points
Point(4,1), Point(4,1) //lower points
);
Note
According to the drawing mode that is chosen for the points, the DSS points can be either drawn as a sequence of edge-connected squares ("Paving" or "Both" mode) or as a polygonal line ("Grid" mode).
StandardDSS4bis.png
A simply 4-standard DSS with its bounding box
StandardDSS4.png
Another view of the same DSS

In order to use classes NaiveDSS8 and StandardDSS4, you must include the following file:

#include "DGtal/geometry/curves/ArithmeticalDSS.h"

Main features

Classes NaiveDSS8 and StandardDSS4 are both aliases of the class ArithmeticalDSS, which gathers the generic code to represent both a simply 8-connected sequence of points belonging to a naive DSL and a simply 4-connected sequence of points belonging to a standard DSL. As ArithmeticalDSL, ArithmeticalDSS is a model of CPointFunctor, ie. it has a function operator ArithmeticalDSS.operator() that returns 'true' iff the input point belongs to the DSS. As ArithmeticalDSL, it provides services to iterate over the DSS points. Indeed, ArithmeticalDSS is a model of concepts::CConstBidirectionalRange. It has two inner types called ArithmeticalDSS::ConstIterator and ArithmeticalDSS::ConstReverseIterator, which are both models of readable iterator and bidirectional iterator.

Obviously, a given DSS belongs to infinitely many DSLs, but one of them has minimal parameters, ie has a minimal \( \omega \). ArithmeticalDSS uses this minimal bounding DSL to represent its slope and its intercept. Note that an instance of ArithmeticalDSS is oriented with respect to the orientation of its minimal bounding DSL. In addition, ArithmeticalDSS stores as data members not only its minimal bounding DSL, but also its ending points as well as the first and last lower and upper leaning points, due to the role that these points play in the recognition algorithm [Debled and Reveilles, 1995 : [29]].

We list below the main methods of ArithmeticalDSS:

Note
Note that the first lower leaning point, the last lower leaning point and the first (or last) upper leaning points are always clockwise-oriented. In other words, with respect to the orientation of the bounding DSL (and its parameters \( a \) and \( b \)), the lower leaning points are always on the left, while the upper leaning points are always on the right of the bounding DSL. This invariant is an important feature of ArithmeticalDSL and ArithmeticalDSS that may be used to link DSS leaning points and convex hull vertices in a convex part. It is used in the computation of the Faithful Polygon (FP) (see Roussillon and Sivignon, 2011 [65]).

Different ways of constructing DSSs

You can construct a DSS by specifying the value of all its data members. Though, the resulting DSS may be not valid and you should test its validity before using it. An instance of ArithmeticalDSS is valid iff the DSL parameters, the ending points and the leaning points are consistent.

There are five extra ways of constructing an instance of ArithmeticalDSS:

Recognition of digital straight segments

Debled and Reveilles [29] present an algorithm to incrementally recognize a naive DSS. Even if their algorithm originally deals with naive DSSs only, it is trivial to extend it to standard DSSs.

Extension

Let us assume that we have a DSS \( S \). The problem consists in deciding whether the union between \( S \) and a point \( M \) is still a DSS or not. If it is a DSS, we want to have the parameters of the bounding DSL of minimal parameters. The point \( M \) is assumed to be simply connected to the front (resp. back) point of \( S \). ArithmeticalDSS provides two methods for this purpose: ArithmeticalDSS::extendFront() (resp. ArithmeticalDSS::extendBack()), based on [29].

Method ArithmeticalDSS::isExtendableFront() (resp. ArithmeticalDSS::isExtendableBack()), tells if \( S \cup M \) is still a DSS and how to update \( S \) in this case, whereas method ArithmeticalDSS::extendFront() (resp. ArithmeticalDSS::extendBack()) calls method ArithmeticalDSS::isExtendableFront() (resp. ArithmeticalDSS::isExtendableBack()) and performs the update accordingly.

Note
Only ArithmeticalDSS::isExtendableFront() and ArithmeticalDSS::extendFront() share the implementation of the recognition algorithm. ArithmeticalDSS::isExtendableBack() and ArithmeticalDSS::extendBack() respectively calls ArithmeticalDSS::isExtendableFront() and ArithmeticalDSS::extendFront() after having negated the DSS representation (see ArithmeticalDSS::negate()).

Let us consider that \( S \) and \( M \) are defined as follows:

Point M(11, 7);
NaiveDSS8<Integer> S( 5, 8, //slope
Point(0,0), Point(10,6), //ending points
Point(0,0), Point(8,5), //upper points
Point(3,1), Point(3,1) //lower points
);
NaiveDSS8ExtInit.png
Extension to the red point

The extention is simply done as follows:

bool resExtention = S.extendFront( M );

In this case, the return value is true and the resulting DSS is:

NaiveDSS8ExtDone.png
Extended DSS

Retraction

ArithmeticalDSS can also perform the converse operation, ie. removing the front (resp. back) point of a given DSS \( S \) and computing the parameters of the resulting DSS (Feschet and Tougne [35], Lachaud et. al. [45]).

For instance, the following code just undoes the previous extension:

bool resRetraction = S.retractFront();
Note
ArithmeticalDSS::retractFront() reverts the extension performed by ArithmeticalDSS::extendFront() to the front of the DSS. Conversely, ArithmeticalDSS::retractBack() reverts the extension performed by ArithmeticalDSS::extendBack() to the back of the DSS. You can keep in mind the following diagram to remember the rationale of the methods name.
BackFrontFigure.png
Operations applied to the back and front of a DSS

To sum up, we list below the update methods of ArithmeticalDSS:

NaiveDSS8Computer and StandardDSS4Computer

ArithmeticalDSS is an arithmetical representation of the DSS primitive. As we have just seen, some methods are available to update the representation in some cases. However, the Geometry package provides objects, called segment computers, devoted to the recognition of primitives (See Analysis of one-dimensional discrete structures). In this framework, ArithmeticalDSSComputer is a wrapper around ArithmeticalDSS devoted to the dynamic recognition of DSSs along any sequence of points. ArithmeticalDSSComputer has two aliases: NaiveDSS8Computer and StandardDSS4Computer.

As a model of CDynamicBidirectionalSegmentComputer, its main methods are:

Moreover, ArithmeticalDSSComputer::primitive() returns an object of type ArithmeticalDSSComputer::Primitive that is actually one of 2D DSSs.

Before using a DSS Computer, you must include the following header:

#include "DGtal/geometry/curves/ArithmeticalDSSComputer.h"

Then, you can construct a DSS computer as follows:

// Container of digital points
typedef std::vector<Z2::Point> Container;
// Iterator on the container
typedef Container::const_iterator ConstIterator;
// StandardDSS4 computer
typedef StandardDSS4Computer<ConstIterator> DSSComputer;
// Construction of the computer
DSSComputer theDSSComputer;

The extension is simply done as follows:

// Add points while it is possible
theDSSComputer.init( contour.begin() );
while ( ( theDSSComputer.end() != contour.end() ) &&
( theDSSComputer.extendFront() ) ) {}
Note
You don't need to provide the next point, because ArithmeticalDSSComputer can access to the points by iterators.

Finally, you can get the resulting DSS as follows:

DSSComputer::Primitive theDSS = theDSSComputer.primitive();

The whole example may be found in exampleArithmeticalDSSComputer.cpp. The use of NaiveDSS8Computer is quite similar.

Naive3DDSSComputer

Recognition of a 3D straight line segments is based on a projection of the corresponding 3D digital curve onto three base planes. Then these projections are segmented iteratively as long as at least two such 2D segmentation remains valid. By valid we understand that there are no two points of 3D curve which have the same projection onto a 2D plane.

As a model of concepts::CForwardSegmentComputer, its main methods are:

Moreover, Naive3DDSSComputer::arithmeticalDSS2d( Dimension ) returns an object of type Naive3DDSSComputer::ArithmeticalDSSComputer2d that is actually the current 2D DSS in a given projection.

Before using a 3D DSS Computer, you must include the following header:

#include "DGtal/geometry/curves/Naive3DDSSComputer.h"

Then, you can construct a 3D DSS computer as follows:

// Container of digital points
typedef std::vector<Z3::Point> Container;
// Iterator on the container
typedef Container::const_iterator ConstIterator;
// Naive3DDSS computer
typedef Naive3DDSSComputer< ConstIterator, int, 8 > DSSComputer;
// Construction of the computer
DSSComputer theDSSComputer;

The extension is simply done as follows:

// Add points while it is possible
theDSSComputer.init( contour.begin() );
while ( ( theDSSComputer.end() != contour.end() ) &&
( theDSSComputer.extendFront() ) ) {}
Note
You don't need to provide the next point, because Naive3DDSSComputer can access to the points by iterators.

You can check which 2D DSS are valid as follows ( 0 - YZ, 1 - XZ, 2 - XY ):

theDSSComputer.validArithmeticalDSS2d( 0 );

And access them:

DSSComputer::ArithmeticalDSSComputer2d theDSS = theDSSComputer.arithmeticalDSS2d( 0 );

Finally to obtain the parameters of 3D DSS

DSSComputer::Point3d directionZ3;
DSSComputer::PointR3d intercept;
DSSComputer::PointR3d thikness;
theDSSComputer.getParameters ( directionZ3, intercept, thikness );

The whole example may be found in exampleNaive3DDSSComputer.cpp.

Application of the straight line segment recognition

This section contains several examples of application of straight line recognition.

Estimation of tangent direction

Example below shows how to estimate tangent directions of a digital curve while using Lambda Maximal Segment Tangent estimation introduced by Lachaud et. al. [45].

Before using the LMST 2D estimator, you must include the following headers:

#include "DGtal/geometry/curves/ArithmeticalDSSComputer.h"
#include "DGtal/geometry/curves/SaturatedSegmentation.h"
#include "DGtal/geometry/curves/estimation/LambdaMST2D.h"

Then, you can construct estimator as follows:

typedef vector < Point > Container;
typedef Container::const_iterator ConstIterator;
typedef ArithmeticalDSSComputer < ConstIterator, int, 8 > SegmentComputer;
typedef SaturatedSegmentation<SegmentComputer> Segmentation;
LambdaMST2D < Segmentation > lmst;

Notice that by default polynomial lambda function is used. Another ones are implemented in FunctorsLambdaMST.h

We need also to generate a tangential cover:

// Initialization of tangential cover
Segmentation segmenter ( contour.begin(), contour.end(), SegmentComputer() );
lmst.attach ( segmenter );

Finally, we can estimate tangent direction point-by-point:

for ( ConstIterator it = contour.begin(); it != contour.end(); ++it )
lmst.eval ( it );

or when we want to calculate tangent directions for a range of points better choice is to do this in following way:

lmst.init ( contour.begin(), contour.end() );
std::vector < RealVector > tangent;
lmst.eval < back_insert_iterator< vector < RealVector > > > ( contour.begin(), contour.end(), back_inserter ( tangent ) );

Note that the 3D extension provides similar interface:

#include "DGtal/geometry/curves/Naive3DDSSComputer.h"
#include "DGtal/geometry/curves/SaturatedSegmentation.h"
#include "DGtal/geometry/curves/estimation/LambdaMST3D.h"
typedef vector < Point > Container;
typedef Container::const_iterator ConstIterator;
typedef Naive3DDSSComputer < ConstIterator, int, 8 > SegmentComputer;
typedef SaturatedSegmentation < SegmentComputer > Segmentation;
LambdaMST3D < Segmentation > lmst;
// Initialization of tangential cover
Segmentation segmenter ( contour.begin(), contour.end(), SegmentComputer() );
lmst.attach ( segmenter );
for ( ConstIterator it = contour.begin(); it != contour.end(); ++it )
lmst.eval ( it );
lmst.init ( contour.begin(), contour.end() );
std::vector < RealVector > tangent;
lmst.eval < std::back_insert_iterator< std::vector < RealVector > > > ( contour.begin(), contour.end(), std::back_insert_iterator< vector < RealVector > > ( tangent ) );

Notice that both LambdaMST2D and LambdaMST3D are models of CCurveLocalGeometricEstimator.

Both examples are in exampleLMST2D.cpp and exampleLMST3D.cpp