Contours and discrete geometrics estimators

Jump to bottom

troussil edited this page Jun 27, 2011 · 14 revisions

Preliminaries

The concept CRange(Note: CSequence is called now CRange) describes a sequence of elements (the order matters) and provides:
- inner type: ConstIterator, a STL bidirectionnal const_iterator
- begin(): ConstIterator
- end(): ConstIterator
The concept CSegment describes a subrange for which a given predicate is true. Moreover, the predicate has to be true for any subrange of any segment. We do not precise further this concept because we focus on their detection along ranges.
(Incremental) detection algorithms should verify the concept CSegmentComputer<typename ConstIterator>
- inner types:
  - ConstIterator (is the template parameter ConstIterator).
  - Self, defined as SegmentComputer<typename ConstIterator>.
  - Reverse, defined as SegmentComputer<typename std::reverse_iterator<ConstIterator> >.
- in addition to the default and copy constructors, it should also define the following methods :
  - void init ( const ConstIterator& it ) : initialize the algorithm from one element.
  - bool extend ( const ConstIterator& it ) : extend the current segment to the next element and return TRUE if it is possible, FALSE otherwise.
Note that the input parameters are iterators (and not elements) to be able to scan all the visited elements if it is necessary in the detection algorithm. Moreover, when passed as input parameters, iterators are assumed to have been incremented and their validity is assumed to have been checked because the detection algorithm does not care about how the end of the range has to be processed.
The concept CDecomposition<typename Range, typename SegmentComputer> describes an object that covers a model of CRange into segments detected thanks to a model of CSegmentComputer. More precisely, it provides:
- an inner type SegmentIterator :
  - default and copy constructors
  - dereference operator: return an instance of a model of CSegmentComputer.
  - getBack(), getFront(): return iterators on the range, respectively, at the first element and one-past-the-end element of the segment.
  - intersectPrevious(), intersectNext(): return TRUE if the current segment intersects, respectively, the previous and the next one (when they exist), FALSE otherwise.
- void init(const Range & r, const SegmentComputer s, bool closed) : called once, r describes the range to process, s is the detection algorithm, closed tells what to do when arriving at r.end().

Grid curve, the class that provides the ranges:

template <typename KSpace> class GridCurve<KSpace> : describes a 4-connected oriented interpixel curve, closed or open. For instance, the topological boundary of a simply connected digital shape is a closed GridCurve. This object provides several ranges, each of them are models of CRange:
- PointsRange, CodesRange, LinelsRange, ArrowsRange: Each of them provides the following types/methods: - inner type = ConstIterator - ConstIterator begin() const - ConstIterator end() const
- PointsRange: the ConstIterator is a model of CConstIteratorOnPoint<KSpace::Space> It returns the successive coordinates (KSpace::Space::Point) of the pointels of the grid curve (even the last when the curve is open).
- CodesRange: the ConstIterator is a model of CConstIteratorOnCode It returns the successive chaincodes (unsigned int in 0-3) of the linels of the grid curve
- LinelsRange: the ConstIterator is a model of CConstIteratorOnLinel<KSpace> It returns the successive linels (KSpace::SCell) of the grid curve.
- ArrowsRange: the ConstIterator is a model of CConstIteratorOnArrow<KSpace::Space> It returns the successive arrows corresponding to linels as a std::pair<KSpace::Space::Point,KSpace::Space::Vector> where the point describes the coordinates of the pointel and the vector stands for the displacement.
- ConstraintsRange: the ConstIterator is a model of CConstIteratorOnConstraints<KSpace::Space> It returns the center of the two pixels incident to the successive linels as a std::pair<KSpace::Space::Point,KSpace::Space::Point>

Estimators

The concept CLocalCurveGeometricEstimator describes an object that can process a range so as to return one estimated quantity for each element of the range (or a given subrange). More precisely, it provides:
- inner types: Range a model of CRange, Quantity the type of the estimated quantity. Note that Range should provide an inner type ConstIterator.
- void init( double h, const Range & s, bool closed ) : called once, h is the grid step, s describes the piece to process, closed tells what to do when arriving at s.end().
- template <typename OutputIterator> void eval( Range::ConstIterator itb, Range::ConstIterator ite, OutputIterator itw ) const : writes estimated quantities from positions itb till ite excluded on the output with *itw++.
- Quantity eval( Sequence::ConstIterator it) const : returns the estimated quantity at position it.
We think to provide a rather generic class for building geometric estimators from models of CSegmentComputer. For instance, given a SegmentComputer and a functor on SegmentComputer, we may provide an estimator which returns the functor value of the most centered segment. The class should be written as template <typename Range, typename SegmentComputer, typename SegmentComputerFunctor> class MostCenteredMaximalSegmentEstimator, where
- Range is a model of CRange
- SegmentComputer is a standard model of CSegmentComputer
- SegmentComputerFunctor has
  - inner type Value.
  - Value operator()( const SegmentComputer & sc )
- inner types: Range (is template parameter Range), Quantity (is SegmentComputerFunctor::Value)
- void init( double h, const Range & s, bool closed )
- template <typename OutputIterator> void eval( Range::ConstIterator itb, Range::ConstIterator ite, OutputIterator itw ) const
- Quantity eval( Range::ConstIterator it) const
Similarly, we could provide a lambda-Maximal Segment estimator built similarly from maximal segments.
When computing the 'true' geometrical quantities from an implicite shape for comparison, we return one quantity for each element of the range so that we also think about providing a generic class to get true values from implicite shapes. The class should be written as template <typename Range, typename ImpliciteShape, typename ImliciteShapeFunctor> class TrueEstimator, where
- Range is a model of CRange
- ImpliciteShape is a model of CImpliciteShape
- ImliciteShapeFunctor has
  - inner type Value.
  - Value operator()( const ImpliciteShape & sc )
- inner types: Range (is template parameter Range), Quantity (is SegmentComputerFunctor::Value)
- void init( double h, const Range & s, bool closed )
- template <typename OutputIterator> void eval( Range::ConstIterator itb, Range::ConstIterator ite, OutputIterator itw ) const
- Quantity eval( Range::ConstIterator it) const
The concept CGlobalCurveGeometricEstimator describes an object that can process a CRange so as to return a single Quantity. More precisely:
- inner types: Range the type of the sequence or range, Quantity the type of the estimated quantity. Note that Range should provide an inner type ConstIterator.
- void init( double h, const Range & s, bool closed ) : called once, h is the grid step, s describes the range to process, closed tells what to do when arriving at s.end().
- Quantity eval( ) const : returns the estimated quantity for the range.
- Examples of model: length by MLP,FP, greedy DSSs segmentation.
The concept CGlobalGeometricEstimator describes an object that can process a CDigitalSetor a CObject (don't know if there exist topology dependent global geometric estimators) so as to return a single Quantity. More precisely:
- inner types: Set or Object the type of the object, Quantity the type of the estimated quantity. Note that Object should provide an inner type ConstIterator.
- void init( double h, const Set & s) : called once, h is the grid step, s describes the set to process.
- Quantity eval( ) const : returns the estimated quantity for the object
  - Examples of model: geometrical moments, circularity, ...