DGtal  0.9.2
FreemanChain.ih
1 /**
2  * This program is free software: you can redistribute it and/or modify
3  * it under the terms of the GNU Lesser General Public License as
4  * published by the Free Software Foundation, either version 3 of the
5  * License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program. If not, see <http://www.gnu.org/licenses/>.
14  *
15  **/
16 
17 /**
18  * @file FreemanChain.ih
19  * @author Jacques-Olivier Lachaud (\c jacques-olivier.lachaud@univ-savoie.fr )
20  * Laboratory of Mathematics (CNRS, UMR 5807), University of Savoie, France
21  * @author Bertrand Kerautret (\c kerautre@loria.fr )
22  * LORIA (CNRS, UMR 7503), University of Nancy, France
23  * @author Xavier Provençal (\c xavier.provencal@univ-savoie.fr )
24  * Laboratory of Mathematics (CNRS, UMR 5807), University of Savoie, France
25  * @author Tristan Roussillon (\c
26  * tristan.roussillon@liris.cnrs.fr ) Laboratoire d'InfoRmatique en
27  * Image et Systèmes d'information - LIRIS (CNRS, UMR 5205), CNRS,
28  * France
29  *
30  * @date 2010/07/01
31  *
32  * @brief Implementation of inline methods defined in FreemanChain.h
33  *
34  * This file is part of the DGtal library.
35  */
36 
37 ///////////////////////////////////////////////////////////////////////////////
38 // IMPLEMENTATION of inline methods.
39 ///////////////////////////////////////////////////////////////////////////////
40 
41 
42 
43 
44 ///////////////////////////////////////////////////////////////////////////////
45 // Iterator on points
46 
47 
48 template <typename TInteger>
49 inline
50  DGtal::FreemanChain<TInteger>::ConstIterator::ConstIterator(
51  ConstAlias<FreemanChain> aChain, unsigned int n)
52  : myFc( &aChain ), myPos( 0 )
53 {
54  if ( n < myFc->chain.size() )
55  {
56  myXY[0] = myFc->x0;
57  myXY[1] = myFc->y0;
58  while ( myPos < n ) this->next();
59  }
60  else
61  {// iterator end()
62  myXY[0] = myFc->xn;
63  myXY[1] = myFc->yn;
64  myPos = (typename DGtal::FreemanChain<TInteger>::Index)(myFc->chain.size()+1);
65  }
66 }
67 
68 /**
69  * Assignment.
70  * @param other the iterator to copy.
71  * @return a reference on 'this'.
72  */
73 template <typename TInteger>
74 inline
75 typename DGtal::FreemanChain<TInteger>::ConstIterator &
76 DGtal::FreemanChain<TInteger>::ConstIterator::operator= ( const ConstIterator & other )
77 {
78  if ( this != &other )
79  {
80  myFc = other.myFc;
81  myPos = other.myPos;
82  myXY = other.myXY;
83  }
84  return *this;
85 }
86 
87 
88 template <typename TInteger>
89 inline
90 void DGtal::FreemanChain<TInteger>::ConstIterator::next()
91 {
92  if ( myPos < myFc->chain.size() )
93  {
94  switch ( myFc->code( myPos ) )
95  {
96  case '0': (myXY[0])++; break;
97  case '1': (myXY[1])++; break;
98  case '2': (myXY[0])--; break;
99  case '3': (myXY[1])--; break;
100  }
101  ++myPos;
102  } else ++myPos;
103 }
104 
105 
106 
107 
108 template <typename TInteger>
109 inline
110 void DGtal::FreemanChain<TInteger>::ConstIterator::nextInLoop()
111 {
112  if ( myPos < myFc->chain.size() )
113  {
114  switch ( myFc->code( myPos ) )
115  {
116  case '0': (myXY[0])++; break;
117  case '1': (myXY[1])++; break;
118  case '2': (myXY[0])--; break;
119  case '3': (myXY[1])--; break;
120  }
121  myPos = ( myPos + 1 ) % myFc->chain.size();
122  }
123 }
124 
125 
126 template <typename TInteger>
127 inline
128 void DGtal::FreemanChain<TInteger>::ConstIterator::previous()
129 {
130  if ( myPos == myFc->chain.size() + 1 )
131  {
132  myXY = myFc->lastPoint();
133  --myPos;
134  }
135  else
136  {
137  if ( myPos >= 1 )
138  --myPos;
139  if ( myPos < myFc->chain.size() )
140  {
141  switch ( myFc->code( myPos ) )
142  {
143  case '0': (myXY[0])--; break;
144  case '1': (myXY[1])--; break;
145  case '2': (myXY[0])++; break;
146  case '3': (myXY[1])++; break;
147  }
148  }
149  }
150 }
151 
152 
153 template <typename TInteger>
154 inline
155 void DGtal::FreemanChain<TInteger>::ConstIterator::previousInLoop()
156 {
157  if ( myPos == 0 ) myPos = (typename DGtal::FreemanChain<TInteger>::Index)(myFc->chain.size() - 1);
158  else --myPos;
159  switch ( myFc->code( myPos ) )
160  {
161  case '0': (myXY[0])--; break;
162  case '1': (myXY[1])--; break;
163  case '2': (myXY[0])++; break;
164  case '3': (myXY[1])++; break;
165  }
166 }
167 
168 
169 
170 ///////////////////////////////////////////////////////////////////////////////
171 // ----------------------- Standard services ------------------------------
172 
173 
174 
175 /**
176  * Constructor.
177  * @param s the chain code.
178  * @param x the x-coordinate of the first point.
179  * @param y the y-coordinate of the first point.
180  */
181 template <typename TInteger>
182 DGtal::FreemanChain<TInteger>::FreemanChain( const std::string & s, TInteger x, TInteger y )
183  : chain( s ), x0( x ), y0( y ), xn( x ), yn( y )
184 {
185  DGtal::FreemanChain<TInteger>::computeLastPoint();
186 }
187 
188 
189 /**
190  * Constructor.
191  */
192 template <typename TInteger>
193 DGtal::FreemanChain<TInteger>::
194 FreemanChain( const std::vector<Point>& vectPoints )
195 {
196  readFromPointsRange(vectPoints.begin(), vectPoints.end(), *this);
197 }
198 
199 
200 
201 /**
202  * Constructor.
203  * @param in any input stream,
204  */
205 template <typename TInteger>
206 DGtal::FreemanChain<TInteger>::FreemanChain(std::istream & in ){
207  read(in, *this);
208  computeLastPoint();
209 }
210 
211 
212 /**
213  * Copy constructor.
214  * @param other the object to clone.
215  */
216 template <typename TInteger>
217 DGtal::FreemanChain<TInteger>::FreemanChain( const FreemanChain<TInteger> & aOther )
218  : chain( aOther.chain ), x0( aOther.x0 ), y0( aOther.y0 ),
219  xn( aOther.xn), yn( aOther.yn)
220 { }
221 
222 
223 
224 
225 /**
226  * Assignment.
227  * @param aOther the object to copy.
228  * @return a reference on 'this'.
229  */
230 template <typename TInteger>
231 typename DGtal::FreemanChain<TInteger> &
232 DGtal::FreemanChain<TInteger>::operator=( const FreemanChain<TInteger> & aOther )
233 {
234  if ( this != &aOther )
235  {
236  chain = aOther.chain;
237  x0 = aOther.x0;
238  y0 = aOther.y0;
239  xn = aOther.xn;
240  yn = aOther.yn;
241  }
242  return *this;
243 }
244 
245 
246 
247 
248 
249 ///////////////////////////////////////////////////////////////////////////////
250 // Iterators services
251 
252 
253 template <typename TInteger>
254 typename DGtal::FreemanChain<TInteger>::ConstIterator
255 DGtal::FreemanChain<TInteger>::begin() const
256 {
257  return ConstIterator( *this, 0 );
258 }
259 
260 
261 template <typename TInteger>
262 typename DGtal::FreemanChain<TInteger>::ConstIterator
263 DGtal::FreemanChain<TInteger>::end() const
264 {
265  Point p(0,0); // *(end()) is invalid
266  return ConstIterator( *this, (typename DGtal::FreemanChain<TInteger>::Index)(chain.size() + 1), p );
267 }
268 
269 
270 /**
271  * @param pos a position in the chain code.
272  * @return the next position.
273  */
274 template <typename TInteger>
275 typename DGtal::FreemanChain<TInteger>::Index
276 DGtal::FreemanChain<TInteger>::next( Index aPos ) const
277 {
278  ++aPos;
279  if ( aPos >= chain.size() )
280  aPos = 0;
281  return aPos;
282 }
283 
284 /**
285  * @param pos a position in the chain code.
286  * @return the previous position.
287  */
288 template <typename TInteger>
289 typename DGtal::FreemanChain<TInteger>::Index
290 DGtal::FreemanChain<TInteger>::previous( Index aPos ) const
291 {
292  if ( aPos == 0 ) aPos = chain.size() - 1;
293  else --aPos;
294  return aPos;
295 }
296 
297 /**
298  * @param aPos a position in the chain code.
299  * @return the code at position [aPos].
300  */
301 template <typename TInteger>
302 char
303 DGtal::FreemanChain<TInteger>::code( Index aPos ) const
304 {
305  ASSERT( aPos < chain.size() );
306  //return chain[ aPos ] - '0';
307  return chain[ aPos ];
308 }
309 
310 
311 /**
312  * @return the length of the Freeman chain code.
313  */
314 template <typename TInteger>
315 inline
316 typename DGtal::FreemanChain<TInteger>::Index
317 DGtal::FreemanChain<TInteger>::size() const
318 {
319  return (typename DGtal::FreemanChain<TInteger>::Size)(chain.size());
320 }
321 
322 
323 template <typename TInteger>
324 inline
325 void DGtal::FreemanChain<TInteger>::computeBoundingBox( TInteger & min_x,
326  TInteger& min_y, TInteger& max_x, TInteger& max_y ) const
327 {
328  min_x = max_x = x0;
329  min_y = max_y = y0;
330  for ( ConstIterator it = begin();
331  it != end();
332  ++it )
333  {
334  Point p( *it );
335  if ( p[0] < min_x )
336  min_x = p[0];
337  else
338  if ( p[0] > max_x )
339  max_x = p[0];
340  if ( p[1] < min_y )
341  min_y = p[1];
342  else
343  if ( p[1] > max_y )
344  max_y = p[1];
345  }
346 }
347 
348 
349 template <typename TInteger>
350 inline
351 typename DGtal::FreemanChain<TInteger>::ConstIterator
352 DGtal::FreemanChain<TInteger>::findQuadrantChange( OrderedAlphabet & A ) const
353 {
354  ConstIterator it = begin();
355  ConstIterator it_end = end();
356  // find first letters a and b.
357  char code1 = it.getCode();
358  it.next();
359  while ( ( it != it_end ) && ( it.getCode() == code1 ) )
360  it.next();
361  ASSERT( ( it != it_end )
362  && "[DGtal::FreemanChain::findQuadrantChange( OrderedAlphabet & A ) const] 1-letter freeman chain." );
363  char code2 = it.getCode();
364  // find third letter c.
365  while ( ( it != it_end ) && ( ( it.getCode() == code1 )
366  || ( it.getCode() == code2 ) ) )
367  it.next();
368  ASSERT( ( it != it_end )
369  && "[DGtal::FreemanChain::findQuadrantChange( OrderedAlphabet & A ) const] 2-letters Freeman chain." );
370  // reorder a and b.
371  it.previous();
372  if ( it.getCode() != code2 )
373  std::swap( code1, code2 );
374  // find first a.
375  do
376  {
377  it.previous();
378  }
379  while ( it.getCode() == code2 );
380  char a_char = chain[ it.position() ];
381  // the next is the first b.
382  it.next();
383  char b_char = chain[ it.position() ];
384  // Reorder the alphabet to match the quadrant change.
385  while ( A.order( b_char ) != 1 )
386  A.shiftLeft();
387  if ( A.order( a_char ) == 0 )
388  {
389  A.reverse();
390  while ( A.order( b_char ) != 1 )
391  A.shiftLeft();
392  }
393  ASSERT( ( A.order( b_char ) == 1 )
394  && ( A.order( a_char ) == 2 )
395  && "[DGtal::FreemanChain::findQuadrantChange( OrderedAlphabet & A ) const] Internal error: invalid Quadrant change found." );
396  return it;
397 }
398 
399 
400 template <typename TInteger>
401 inline
402 typename DGtal::FreemanChain<TInteger>::ConstIterator
403 DGtal::FreemanChain<TInteger>::findQuadrantChange4( OrderedAlphabet & A ) const
404 {
405  ConstIterator it = begin();
406  ConstIterator it_end = end();
407  // find first letters a and b.
408  uint8_t code1 = it.getCode();
409  it.next();
410  while ( ( it != it_end ) && ( it.getCode() == code1 ) )
411  it.next();
412  ASSERT( ( it != it_end )
413  && "[DGtal::FreemanChain::findQuadrantChange( OrderedAlphabet & A ) const] 1-letter freeman chain." );
414  uint8_t code2 = it.getCode();
415  // find third letter c.
416  while ( ( it != it_end ) && ( ( it.getCode() == code1 )
417  || ( it.getCode() == code2 ) ) )
418  it.next();
419  ASSERT( ( it != it_end )
420  && "[DGtal::FreemanChain::findQuadrantChange( OrderedAlphabet & A ) const] 2-letters Freeman chain." );
421  uint8_t code3 = it.getCode();
422  // find fourth letter d.
423  while ( ( it != it_end ) && ( ( it.getCode() == code1 )
424  || ( it.getCode() == code2 )
425  || ( it.getCode() == code3 ) ) )
426  it.next();
427  ASSERT( ( it != it_end )
428  && "[DGtal::FreemanChain::findQuadrantChange( OrderedAlphabet & A ) const] 3-letters Freeman chain." );
429  // define true c.
430  it.previous();
431  code3 = it.getCode();
432  // find first b.
433  do
434  {
435  it.previous();
436  }
437  while ( it.getCode() == code3 );
438  char a_char = chain[ it.position() ];
439  // the next is the first c.
440  it.next();
441  char b_char = chain[ it.position() ];
442  // Reorder the alphabet to match the quadrant change.
443  while ( A.order( b_char ) != 1 )
444  A.shiftLeft();
445  if ( A.order( a_char ) == 0 )
446  {
447  A.reverse();
448  while ( A.order( b_char ) != 1 )
449  A.shiftLeft();
450  }
451  ASSERT( ( A.order( b_char ) == 1 )
452  && ( A.order( a_char ) == 2 )
453  && "[DGtal::FreemanChain::findQuadrantChange( OrderedAlphabet & A ) const] Internal error: invalid Quadrant change found." );
454  return it;
455 }
456 
457 
458 template <typename TInteger>
459 inline
460 int DGtal::FreemanChain<TInteger>::isClosed() const
461 {
462  return (x0 == xn) && (y0 == yn);
463 }
464 
465 
466 template <typename TInteger>
467 inline
468 int DGtal::FreemanChain<TInteger>::ccwLoops() const
469 {
470  ConstIterator it = this->begin();
471  ConstIterator it_end = this->end();
472  --it_end;
473  ConstIterator it_suiv = it;
474  Point spos = *it;
475  int nb_ccw_turns = 0;
476  while ( it != it_end )
477  {
478  int code1 = it.getCode();
479  it_suiv.nextInLoop();
480  int code2 = it_suiv.getCode();
481  char diff = ( code2 - code1 + 4 ) % 4;
482  if ( diff == 1 )
483  ++nb_ccw_turns;
484  else
485  if ( diff == 3 )
486  --nb_ccw_turns;
487  else
488  if ( diff == 2 )
489  return 0;
490  ++it;
491  }
492  if ( spos == *it_suiv )
493  return nb_ccw_turns / 4;
494  else
495  return 0;
496 }
497 
498 
499 template <typename TInteger>
500 inline
501 typename DGtal::FreemanChain<TInteger>
502 DGtal::FreemanChain<TInteger>::subChain(Index pos, Size n) const
503 {
504  Self newChain;
505  Point startPoint = getPoint(pos);
506  Point endPoint = getPoint(pos+n);
507  newChain.chain = chain.substr(pos,n);
508  newChain.x0 = startPoint[0];
509  newChain.y0 = startPoint[1];
510  newChain.xn = endPoint[0];
511  newChain.yn = endPoint[1];
512  return newChain;
513 }
514 
515 
516 template <typename TInteger>
517 inline
518 typename DGtal::FreemanChain<TInteger>
519 DGtal::FreemanChain<TInteger>::operator+(const Self& aOther) const
520 {
521  Self newChain;
522  newChain.chain = chain + aOther.chain;
523  newChain.x0 = x0;
524  newChain.y0 = y0;
525  Point newLastPoint = lastPoint() + ( aOther.lastPoint() - aOther.firstPoint() );
526  newChain.xn = newLastPoint[0];
527  newChain.yn = newLastPoint[1];
528  return newChain;
529 }
530 
531 
532 template <typename TInteger>
533 inline
534 typename DGtal::FreemanChain<TInteger>&
535 DGtal::FreemanChain<TInteger>::operator+=(const Self& aOther)
536 {
537  chain += aOther.chain;
538  Point newLastPoint = lastPoint() + ( aOther.lastPoint() - aOther.firstPoint() );
539  xn = newLastPoint[0];
540  yn = newLastPoint[1];
541  return *this;
542 }
543 
544 
545 template <typename TInteger>
546 inline
547 typename DGtal::FreemanChain<TInteger>::Point
548 DGtal::FreemanChain<TInteger>::getPoint(Index aPos) const
549 {
550  ConstIterator it;
551  Size n = this->size();
552  if ( aPos < n / 2 ) {
553  it = begin();
554  for (unsigned int i=0; i<aPos; ++i)
555  it++;
556  }
557  else
558  {
559  it = end();
560  it--;
561  n = n-aPos;
562  for (unsigned int i=0; i<n; ++i) {
563  it--;
564  }
565  }
566  return *it;
567 }
568 
569 
570 
571 template <typename TInteger>
572 inline
573 typename DGtal::FreemanChain<TInteger> &
574 DGtal::FreemanChain<TInteger>::extend(char aCode)
575 {
576  chain += std::string( &aCode, 1);
577  int dx=0, dy=0;
578  //displacement( dx, dy, aCode - '0' );
579  displacement( dx, dy, aCode );
580  xn += dx;
581  yn += dy;
582  return *this;
583 }
584 
585 
586 
587 
588 
589 template <typename TInteger>
590 inline
591 typename DGtal::FreemanChain<TInteger> &
592 DGtal::FreemanChain<TInteger>::retract(Size n)
593 {
594  ConstIterator it = end();
595  for (unsigned int i=0; i<=n; ++i)
596  it--;
597  xn = (*it)[0];
598  yn = (*it)[1];
599  Size mySize = size();
600  ASSERT( (n <= mySize) && "Tried to shorten a FreemanChain by more then its length");
601  chain.resize( mySize - n );
602  return *this;
603 }
604 
605 
606 
607 
608 // ----------------------- Interface --------------------------------------
609 
610 
611 template <typename TInteger>
612 inline
613 void DGtal::FreemanChain<TInteger>::selfDisplay ( std::ostream & out ) const
614 {
615  out << x0 << " " << y0 << " " << chain;
616 }
617 
618 
619 /**
620  * Checks the validity/consistency of the object.
621  * @return 'true' if the object is valid, 'false' otherwise.
622  */
623 template <typename TInteger>
624 inline
625 bool DGtal::FreemanChain<TInteger>::isValid () const
626 {
627  return true;
628 }
629 
630 
631 
632 
633 
634 
635 
636 
637 
638 ///////////////////////////////////////////////////////////////////////////////
639 // Static services
640 
641 
642 template <typename TInteger>
643 inline
644 void DGtal::FreemanChain<TInteger>::read( std::istream & in, FreemanChain & c )
645 {
646  std::string str;
647  while ( true )
648  {
649  getline( in, str );
650  if ( ! in.good() )
651  return;
652  if ( ( str.size() > 0 ) && ( str[ 0 ] != '#' ) )
653  {
654  std::istringstream str_in( str );
655  str_in >> c.x0 >> c.y0 >> c.chain;
656  return;
657  }
658  }
659 }
660 
661 template <typename TInteger>
662 template <typename TConstIterator>
663 inline
664 void DGtal::FreemanChain<TInteger>::readFromPointsRange( const TConstIterator& itBegin, const TConstIterator& itEnd, FreemanChain & c )
665 {
666  TConstIterator it( itBegin );
667 
668  if (it != itEnd)
669  { //if the range is not empty
670  Point startingPt( *it );
671  ++it;
672 
673  if (it != itEnd)
674  { //if there is more than one element
675  std::ostringstream oss;
676  Point pt( startingPt );
677  do
678  {
679 
680  Point ptSuiv( *it );
681  Integer dx = ptSuiv[0] - pt[0];
682  Integer dy = ptSuiv[1] - pt[1];
683  short number = ( dx != 0 ? (1 - dx) : (2 - dy) );
684  if ( (number < 0) || (number > 3) )
685  {
686  std::cerr << "not connected points (method readFromPointsRange of FreemanChain)" << std::endl;
687  throw ConnectivityException();
688  }
689  oss << number;
690  pt = ptSuiv;
691  ++it;
692 
693  } while ( it != itEnd );
694 
695  c.xn=pt[0];
696  c.yn=pt[1];
697  c.chain = oss.str();
698  }
699 
700  c.x0=startingPt[0];
701  c.y0=startingPt[1];
702  }
703 
704 }
705 
706 template <typename TInteger>
707 template <typename TRange>
708 inline
709 void DGtal::FreemanChain<TInteger>::readFromPointsRange( const TRange& aRange, FreemanChain & c )
710 {
711  BOOST_CONCEPT_ASSERT(( concepts::CConstSinglePassRange<TRange> ));
712  readFromPointsRange( aRange.begin(), aRange.end(), c );
713 }
714 
715 template <typename TInteger>
716 inline
717 void DGtal::FreemanChain<TInteger>::getContourPoints(
718  const FreemanChain & fc, std::vector<Point> & aVContour)
719 {
720  aVContour.clear();
721  for ( ConstIterator it = fc.begin();
722  it != fc.end();
723  ++it )
724  {
725  aVContour.push_back(*it);
726  }
727 }
728 
729 template <typename TInteger>
730 inline
731 void DGtal::FreemanChain<TInteger>::getInterPixelLinels(const KhalimskySpaceND<2, TInteger> &aKSpace,
732  const FreemanChain & fc,
733  typename KhalimskySpaceND<2, TInteger>::SCellSet &aSCellContour,
734  bool aFlagForAppend){
735  if(!aFlagForAppend){
736  aSCellContour.clear();
737  }
738  unsigned int pos=0;
739  for ( ConstIterator it = fc.begin();
740  it != fc.end();
741  ++it )
742  {
743  // By convention the FreemanChain in InterGrid mode is shifted by a (-0.5, 0.5) vector.
744  Point pt ((*it)[0]*2, ((*it)[1]+1)*2);
745  KhalimskySpaceND<2, int>::SCell linel;
746  switch ( fc.code(pos%fc.size()) )
747  {
748  case '0':
749  linel = aKSpace.sCell(pt+Point(1,0), false);
750  break;
751  case '1':
752  linel = aKSpace.sCell(pt+Point(0,1), false);
753  break;
754  case '2':
755  linel = aKSpace.sCell(pt+Point(-1,0), true);
756  break;
757  case '3':
758  linel = aKSpace.sCell(pt+Point(0,-1), true);
759  break;
760  }
761 
762  aSCellContour.insert(linel);
763  pos++;
764  }
765 
766 }
767 
768 
769 
770 template <typename TInteger>
771 void
772 DGtal::FreemanChain<TInteger>::movePointFromFC(Point & aPoint, char aCode ){
773  switch ( aCode )
774  {
775  case '0': aPoint[0]++; break;
776  case '1': aPoint[1]++; break;
777  case '2': aPoint[0]--; break;
778  case '3': aPoint[1]--; break;
779  }
780 }
781 
782 // Depreciated
783 //
784 //template <typename TInteger>
785 //void
786 //DGtal::FreemanChain<TInteger>::alphabet( char & aZero, char & aOne, char aQuadrant )
787 //{
788 // switch ( aQuadrant )
789 // {
790 // case '0':
791 // aZero = '0';
792 // aOne = '1';
793 // break;
794 // case '1':
795 // aZero = '1';
796 // aOne = '2';
797 // break;
798 // case '2':
799 // aZero = '2';
800 // aOne = '3';
801 // break;
802 // case '3':
803 // aZero = '3';
804 // aOne = '0';
805 // break;
806 // }
807 //
808 //};
809 
810 
811 
812 template <typename TInteger>
813 inline
814 char DGtal::FreemanChain<TInteger>::movement( char aCode1,
815  char aCode2, bool ccw )
816 {
817  unsigned int cfg = ( ccw ? 0 : 16 ) + ( (aCode1 - '0') << 2 ) + (aCode2 - '0');
818  static const char tbl[ 32 ] =
819  {
820  '2', '1', '0', '3', '3', '2', '1', '0',
821  '0', '3', '2', '1', '1', '0', '3', '2',
822  '2', '3', '0', '1', '1', '2', '3', '0',
823  '0', '1', '2', '3', '3', '0', '1', '2'
824  };
825  return tbl[ cfg ];
826 }
827 
828 
829 
830 template <typename TInteger>
831 inline
832 char DGtal::FreemanChain<TInteger>::addToCode( char code, int n)
833 {
834  return '0' + ( ( (code - '0' ) + n ) & 3 );
835 }
836 
837 
838 
839 
840 
841 template <typename TInteger>
842 inline
843 void
844 DGtal::FreemanChain<TInteger>::displacement( int & dx, int & dy, char aCode )
845 {
846  switch ( aCode )
847  {
848  case '0': dx = 1; dy = 0; break;
849  case '1': dx = 0; dy = 1; break;
850  case '2': dx = -1; dy = 0; break;
851  case '3': dx = 0; dy = -1; break;
852  }
853 }
854 
855 
856 template <typename TInteger>
857 inline
858 typename DGtal::PointVector<2,TInteger>
859 DGtal::FreemanChain<TInteger>::displacement( char aCode )
860 {
861  switch ( aCode )
862  {
863  case '0': return Point({1,0});
864  case '1': return Point({0,1});
865  case '2': return Point({-1,0});
866  case '3': return Point({0,-1});
867  }
868  return Point({0,0});
869 }
870 
871 
872 
873 template <typename TInteger>
874 inline
875 char
876 DGtal::FreemanChain<TInteger>::turnedCode( char aCode, bool ccw )
877 {
878  if ( ccw ) return ( aCode == '3' ) ? '0' : ( aCode + 1 );
879  else return ( aCode == '0' ) ? '3' : ( aCode - 1 );
880 }
881 //DGtal::FreemanChain<TInteger>::turnedCode( unsigned int aCode, bool ccw )
882 //{
883 // if ( ccw ) return ( aCode + 1 ) & 0x3;
884 // else return ( aCode - 1 ) & 0x3;
885 //}
886 
887 
888 
889 
890 
891 
892 
893 template <typename TInteger>
894 void DGtal::FreemanChain<TInteger>::innerContour(
895  FreemanChain & aInnerChain,
896  std::vector<unsigned int> & aOuter2inner,
897  std::vector<unsigned int> & aInner2outer,
898  const FreemanChain & aOuterChain,
899  bool ccw )
900 {
901  unsigned int nb = (unsigned int)aOuterChain.chain.size();
902  unsigned int j = 0;
903  aOuter2inner.clear();
904  aOuter2inner.reserve( nb );
905  // aInnerChain.chain.reserve( nb + 4 );
906  aInnerChain.chain = "";
907  aInner2outer.clear();
908  aInner2outer.reserve( nb + ( ccw ? 4 : -4 ) );
909  int dx0=0, dy0=0;
910  int dx1=0, dy1=0;
911  FreemanChain<TInteger>::displacement( dx0, dy0, aOuterChain.code( 0 ) );
912  int turn = ccw ? 1 : 3;
913  //FreemanChain<TInteger>::displacement( dx1, dy1, ( aOuterChain.code( 0 ) + turn ) % 4 );
914  FreemanChain<TInteger>::displacement( dx1, dy1, addToCode( aOuterChain.code( 0 ) , turn ) );
915  dx0 += dx1;
916  dy0 += dy1;
917  aInnerChain.x0 = dx0 > 0 ? aOuterChain.x0 : aOuterChain.x0 - 1;
918  aInnerChain.y0 = dy0 > 0 ? aOuterChain.y0 : aOuterChain.y0 - 1;
919 
920  ConstIterator it_begin = aOuterChain.begin();
921  ConstIterator it = it_begin;
922  it.next();
923  for ( unsigned int i = 0; i < nb; ++i )
924  {
925  // Check if contour is open.
926  // cerr << "i=" << i << " code=" << aOuterChain.code( i ) << endl;
927  switch ( movement( aOuterChain.code( i ), aOuterChain.code( ( i + 1 ) % nb ), ccw ) )
928  {
929  case '0':
930  // contour going in then out.
931  aInnerChain.chain += aOuterChain.chain[ i ];
932  //aInnerChain.chain += ( ( ( (unsigned int) ( aOuterChain.chain[ i ] - '0' )
933  // + ( ccw ? 3 : 1 ) ) )
934  // % 4 ) + '0';
935  aInnerChain.chain += addToCode ( aOuterChain.chain[ i ], (ccw) ? 3 : 1 );
936  aInnerChain.chain += aOuterChain.chain[ ( i + 1 ) % nb ];
937  aOuter2inner.push_back( j );
938  aInner2outer.push_back( i );
939  aInner2outer.push_back( i + 1 );
940  aInner2outer.push_back( i + 1 );
941  j += 3;
942  break;
943 
944  case '1':
945  // contour turning toward its inside.
946  aOuter2inner.push_back( j );
947  break;
948 
949  case '2':
950  // contour going straight ahead
951  aInnerChain.chain += aOuterChain.chain[ i ];
952  aOuter2inner.push_back( j );
953  aInner2outer.push_back( i );
954  ++j;
955  break;
956 
957  case '3':
958  // contour turning toward its outside.
959  aInnerChain.chain += aOuterChain.chain[ i ];
960  aInnerChain.chain += aOuterChain.chain[ ( i + 1 ) % nb ];
961  aOuter2inner.push_back( j );
962  aInner2outer.push_back( i );
963  aInner2outer.push_back( i + 1 );
964  j += 2;
965  break;
966  }
967 
968  // Advances along contour and check if it is a closed contour.
969  it.next();
970  if ( ( i == nb - 1 )
971  && ( *it_begin != *it ) )
972  // freeman chain is *not* a closed loop.
973  {
974  aInnerChain.chain += aOuterChain.chain[ i ];
975  aOuter2inner.push_back( j );
976  aInner2outer.push_back( i );
977  ++i;
978  ++j;
979  break;
980  }
981  }
982 }
983 
984 
985 
986 
987 template <typename TInteger>
988 bool DGtal::FreemanChain<TInteger>::cleanOuterSpikes(
989  FreemanChain & aCleanC,
990  std::vector<unsigned int> & aC2clean,
991  std::vector<unsigned int> & aClean2c,
992  const FreemanChain & c,
993  bool ccw )
994 {
995  unsigned int nb = (unsigned int)c.chain.size();
996  if ( nb == 0 )
997  {
998  std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
999  << " cleanOuterSpikes: Empty input chain"
1000  << std::endl;
1001  return false;
1002  }
1003 
1004  ModuloComputer< DGtal::int32_t > mc( nb );
1005  ModuloComputer< DGtal::int32_t >::UnsignedInteger i = 0;
1006  ModuloComputer< DGtal::int32_t >::UnsignedInteger j = 0;
1007  std::vector<unsigned int> c2cleanTMP;
1008  aCleanC.chain.reserve( nb );
1009  aCleanC.chain = "";
1010  aC2clean.clear();
1011  aClean2c.clear();
1012  aC2clean.reserve( nb );
1013  aClean2c.reserve( nb );
1014  c2cleanTMP.reserve( nb );
1015  ConstIterator it = c.begin();
1016  ConstIterator itn = c.begin();
1017  itn.nextInLoop();
1018  // Find a consistent starting point.
1019  unsigned int n;
1020  unsigned int size_spike = 0;
1021  for ( n = 0; n < nb; ++n )
1022  {
1023  size_spike = 0;
1024  while ( movement( it.getCode(), itn.getCode(), ccw ) == '0' )
1025  {
1026  it.previousInLoop();
1027  itn.nextInLoop();
1028  mc.increment( i );
1029  size_spike += 2;
1030  if ( size_spike >= nb )
1031  {
1032  std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1033  << " Spike is longer than contour !"
1034  << " size_spike=" << size_spike
1035  << " nb=" << nb
1036  << std::endl;
1037  return false;
1038  }
1039  }
1040  mc.increment( i );
1041  it = itn;
1042  itn.nextInLoop();
1043  if ( size_spike > 0 )
1044  break;
1045  }
1046  unsigned int start_idx = it.position();
1047  i = start_idx;
1048  // JOL : 2009/07/07, added starting coordinates
1049  // XP : 2011/09/06, added ending coordinates
1050  Point P = *it;
1051  aCleanC.x0 = P[0];
1052  aCleanC.y0 = P[1];
1053  aCleanC.xn = P[0];
1054  aCleanC.yn = P[1];
1055 
1056  // cerr << "Starting point is " << i << endl;
1057  ASSERT( ( n < nb ) || ( i == 0 ) );
1058  if ( n == nb )
1059  { // do nothing
1060  aCleanC.chain = c.chain;
1061  for ( unsigned int ni = 0; ni < nb; ++ni )
1062  {
1063  aC2clean.push_back( ni );
1064  aClean2c.push_back( ni );
1065  }
1066  if ( size_spike != 0 )
1067  std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1068  << "No starting point found (only spikes !)" << std::endl;
1069 
1070  return size_spike == 0;
1071  }
1072  // Loops over all letters.
1073  ConstIterator it_begin = it;
1074  std::deque<unsigned int> clean_code;
1075  std::deque<unsigned int> clean_idx;
1076  std::vector<unsigned int> begin_outer_spike;
1077  std::vector<unsigned int> end_outer_spike;
1078  // i follows iterator it.
1079  do
1080  {
1081  clean_code.push_back( it.getCode() );
1082  clean_idx.push_back( i );
1083  itn = it;
1084  it.nextInLoop();
1085  mc.increment( i );
1086  // cerr << "- i=" << i << " (" << clean_code.back()
1087  // << it.getCode() << ") ";
1088  size_spike = 0;
1089  unsigned int last_spike_idx = end_outer_spike.empty() ?
1090  start_idx :
1091  end_outer_spike.back();
1092  j = i;
1093  while ( ( ! clean_code.empty() )
1094  && ( j != last_spike_idx )
1095  && ( movement( clean_code.back(), it.getCode(), ccw ) == '0' )
1096  && ( it != it_begin ) )
1097  {
1098  clean_code.pop_back();
1099  clean_idx.pop_back();
1100  mc.increment( i );
1101  mc.decrement( j );
1102  it.nextInLoop();
1103  itn.previousInLoop();
1104  size_spike += 2;
1105  }
1106  // cerr << "i=" << i << " size_spike=" << size_spike
1107  // << " last_spike_idx=" << last_spike_idx
1108  // << endl;
1109  if ( size_spike != 0 )
1110  {
1111  // There is a spike. Is it an outer one ?
1112  unsigned int previous_code = itn.getCode();
1113  unsigned int previous_idx = itn.position();
1114  // JOL : do not
1115  // consider any more "cleaned contour" since we cannot go
1116  // further than the last spike.
1117  // unsigned int previous_code =
1118  // clean_code.empty() ? itn.getCode() : clean_code.back();
1119  // unsigned int previous_idx =
1120  // clean_code.empty() ? itn.position() : clean_idx.back();
1121  itn = it;
1122  itn.previousInLoop();
1123  unsigned int move1 = movement( previous_code, addToCode ( itn.getCode() , 2 ), ccw );
1124  unsigned int move2 = movement( itn.getCode(), it.getCode() , ccw );
1125  bool return_spike = ( move1 == '0' ) || ( move2 == '0' );
1126  bool outer_spike = ( move1 == '3' ) || ( move2 == '3' );
1127  // if ( return_spike )
1128  // cerr << "[DGtal::FreemanChain::cleanOuterSpikes] return spike."
1129  // << endl;
1130  // if ( ! ( ( outer_spike && ( move1 != 1 ) && ( move2 != 1 ) )
1131  // || ( ! outer_spike && ( move1 != 3 ) && ( move2 != 3 ) ) ) )
1132  // cerr << "[DGtal::FreemanChain::cleanOuterSpikes] "
1133  // << "Weird spike. Invalid contour (expected 3 3) ?"
1134  // << " move1=" << move1
1135  // << " move2=" << move2
1136  // << " ccw=" << ccw
1137  // << " start_idx=" << start_idx
1138  // << " size_spike=" << size_spike
1139  // << " it=" << it.position()
1140  // << " itp=" << previous_idx
1141  // << endl
1142  // << c.chain << endl;
1143  // Process waiting steps.
1144  if ( outer_spike || return_spike )
1145  {
1146  begin_outer_spike.push_back( mc.next( previous_idx ) );
1147  end_outer_spike.push_back( i );
1148  // cout << " outer spike [" << begin_outer_spike.back()
1149  // << "," << end_outer_spike.back() << "[ " << endl;
1150  }
1151  }
1152  }
1153  while ( it != it_begin );
1154 
1155  // Once outer spikes are known, we can create the new contour.
1156  aC2clean.resize( nb );
1157  i = start_idx % nb;
1158  j = 0;
1159  unsigned int nb_spikes = (unsigned int)begin_outer_spike.size();
1160  unsigned int k = 0;
1161  n = 0;
1162  while ( n < nb )
1163  {
1164  if ( ( k == nb_spikes ) || ( i != begin_outer_spike[ k ] ) )
1165  {
1166  aCleanC.chain.push_back( c.chain[ i ] );
1167  aC2clean[ i ] = j;
1168  aClean2c.push_back( i );
1169  mc.increment( i );
1170  ++j;
1171  ++n;
1172  }
1173  else
1174  {
1175  while ( i != end_outer_spike[ k ] )
1176  {
1177  aC2clean[ i ] = j;
1178  mc.increment( i );
1179  ++n;
1180  }
1181  ++k;
1182  }
1183  }
1184  for ( unsigned int ii = 0; ii < nb; ++ii )
1185  if ( aC2clean[ ii ] >= aCleanC.chain.size() )
1186  {
1187  if ( aC2clean[ ii ] == aCleanC.chain.size() )
1188  aC2clean[ ii ] = 0;
1189  else
1190  {
1191  std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1192  << "Bad correspondence for aC2clean[" << ii << "]"
1193  << " = " << aC2clean[ ii ] << " >= " << aCleanC.chain.size()
1194  << std::endl;
1195  aC2clean[ ii ] = aC2clean[ ii ] % aCleanC.chain.size();
1196  }
1197  }
1198 
1199  for ( unsigned int jj = 0; j < aCleanC.chain.size(); ++jj )
1200  if ( aClean2c[ jj ] >= nb )
1201  {
1202  std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1203  << "Bad correspondence for aClean2c[" << jj << "]"
1204  << " = " << aClean2c[ jj ] << " >= " << nb
1205  << std::endl;
1206  aClean2c[ jj ] = aClean2c[ jj ] % nb;
1207  }
1208  return true;
1209 }
1210 
1211 ///////////////////////////////////////////////////////////////////////////////
1212 // Drawing services
1213 
1214 template <typename TInteger>
1215 inline
1216 std::string
1217 DGtal::FreemanChain<TInteger>::className() const
1218 {
1219  return "FreemanChain";
1220 }
1221 
1222 template <typename TInteger>
1223 inline
1224 void
1225 DGtal::FreemanChain<TInteger>::computeLastPoint()
1226 {
1227  ConstIterator it = this->begin();
1228  for (unsigned int i=0; i < chain.size(); ++i)
1229  it++;
1230  xn = (*it)[0];
1231  yn = (*it)[1];
1232 }
1233 
1234 
1235 
1236 
1237 
1238 
1239 ///////////////////////////////////////////////////////////////////////////////
1240 // Implementation of inline functions and external operators //
1241 
1242 /**
1243  * Overloads 'operator<<' for displaying objects of class 'FreemanChain'.
1244  * @param out the output stream where the object is written.
1245  * @param object the object of class 'FreemanChain' to write.
1246  * @return the output stream after the writing.
1247  */
1248 template <typename TInteger>
1249 inline
1250  std::ostream&
1251 DGtal::operator<< ( std::ostream & out,
1252  const FreemanChain<TInteger> & aObject )
1253 {
1254  aObject.selfDisplay ( out );
1255  return out;
1256 }
1257 
1258 // //
1259 ///////////////////////////////////////////////////////////////////////////////
1260 
1261