DGtal
1.5.beta

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
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 [101]).
Any DSL such that \( \omega = \max(a,b) \) (resp. \( \omega = a + b \)) is said to be naive (resp. standard) and is simply 8connected (resp. 4connected) (Reveilles, 1991 [101]).
For instance, the naive DSL \( D(2,5,0,5) \) is depicted below:
The standard DSL \( D(2,5,0,7) \) is thicker:
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) \).
A naive DSL can be declared and constructed as follows:
Then, within a window defined by two points (called firstPoint and lastPoint below), you can iterate over the DSL points:
In the standard case, it is enough to replace Naive by Standard.
In order to use classes NaiveDSL and StandardDSL, you must include the following file:
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.
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.
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.
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.
Other octants and specific cases are generated in exampleArithmeticalDSL.cpp.
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 onetoone mapping between a DSL point and its position in the DSL. For instance, for each xcoordinate \( 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:
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:
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()).
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 
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.
A 8connected naive DSS can be declared and constructed as follows:
You can iterate over the whole set of DSS points as follows:
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").
The result of this short example taken from exampleArithmeticalDSS.cpp is presented below:
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:
In order to use classes NaiveDSS8 and StandardDSS4, you must include the following file:
Classes NaiveDSS8 and StandardDSS4 are both aliases of the class ArithmeticalDSS, which gathers the generic code to represent both a simply 8connected sequence of points belonging to a naive DSL and a simply 4connected 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 : [46]].
We list below the main methods of ArithmeticalDSS:
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:
Debled and Reveilles [46] 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.
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 [46].
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.
Let us consider that \( S \) and \( M \) are defined as follows:
The extention is simply done as follows:
In this case, the return value is true and the resulting DSS is:
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 [56], Lachaud et. al. [74]).
For instance, the following code just undoes the previous extension:
To sum up, we list below the update methods of ArithmeticalDSS:
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 onedimensional 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:
Then, you can construct a DSS computer as follows:
The extension is simply done as follows:
Finally, you can get the resulting DSS as follows:
The whole example may be found in exampleArithmeticalDSSComputer.cpp. The use of NaiveDSS8Computer is quite similar.
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:
Then, you can construct a 3D DSS computer as follows:
The extension is simply done as follows:
You can check which 2D DSS are valid as follows ( 0  YZ, 1  XZ, 2  XY ):
And access them:
Finally to obtain the parameters of 3D DSS
The whole example may be found in exampleNaive3DDSSComputer.cpp.
This section contains several examples of application of straight line recognition.
Example below shows how to estimate tangent directions of a digital curve while using Lambda Maximal Segment Tangent estimation introduced by Lachaud et. al. [74].
Before using the LMST 2D estimator, you must include the following headers:
Then, you can construct estimator as follows:
Notice that by default polynomial lambda function is used. Another ones are implemented in FunctorsLambdaMST.h
We need also to generate a tangential cover:
Finally, we can estimate tangent direction pointbypoint:
or when we want to calculate tangent directions for a range of points better choice is to do this in following way:
Note that the 3D extension provides a similar interface, but also allows for filtration of DSSes. In the below example, each DSS of length lower equal 7 is not taken into account durin the estimation:
Notice that both LambdaMST2D and LambdaMST3D are models of CCurveLocalGeometricEstimator.
Both examples are in exampleLMST2D.cpp and exampleLMST3D.cpp
Moreover, there exists a version of LamdaMST3D that uses only 2D projections of the 3D curve (see LambdaMST3DBy2D.h). This version detects maximal axes during segmentation of the 2D projections, and then the 3D tangent is reconstructed from two 2D tangents that were computed for valid 2D projections. This version does not provide meaningful information in the curve's regions that do not have unique main axis i.e., there exist points such that at least two DSSes passing thru the points have different main axes. Note that, this version has only a research value, and for any application LambdaMST3D should be used.
Note that this 3D by 2D tangent estimator provides a similar interface to the two other versions: