DGtal  0.9.4.1
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 = freemanCode4C(dx, 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 template <typename TInteger>
840 inline
841 short DGtal::FreemanChain<TInteger>::freemanCode4C(int dx, int dy)
842 {
843  short number = ( dx != 0 ? (1 - dx) : (2 - dy) );
844  if ( (number < 0) || (number > 3) )
845  {
846  return 8;
847  }
848  return number;
849 }
850 
851 
852 
853 template <typename TInteger>
854 inline
855 void
856 DGtal::FreemanChain<TInteger>::displacement( int & dx, int & dy, char aCode )
857 {
858  switch ( aCode )
859  {
860  case '0': dx = 1; dy = 0; break;
861  case '1': dx = 0; dy = 1; break;
862  case '2': dx = -1; dy = 0; break;
863  case '3': dx = 0; dy = -1; break;
864  }
865 }
866 
867 
868 template <typename TInteger>
869 inline
870 typename DGtal::PointVector<2,TInteger>
871 DGtal::FreemanChain<TInteger>::displacement( char aCode )
872 {
873  switch ( aCode )
874  {
875  case '0': return Point({1,0});
876  case '1': return Point({0,1});
877  case '2': return Point({-1,0});
878  case '3': return Point({0,-1});
879  }
880  return Point({0,0});
881 }
882 
883 
884 
885 template <typename TInteger>
886 inline
887 char
888 DGtal::FreemanChain<TInteger>::turnedCode( char aCode, bool ccw )
889 {
890  if ( ccw ) return ( aCode == '3' ) ? '0' : ( aCode + 1 );
891  else return ( aCode == '0' ) ? '3' : ( aCode - 1 );
892 }
893 //DGtal::FreemanChain<TInteger>::turnedCode( unsigned int aCode, bool ccw )
894 //{
895 // if ( ccw ) return ( aCode + 1 ) & 0x3;
896 // else return ( aCode - 1 ) & 0x3;
897 //}
898 
899 
900 
901 
902 
903 
904 
905 template <typename TInteger>
906 void DGtal::FreemanChain<TInteger>::innerContour(
907  FreemanChain & aInnerChain,
908  std::vector<unsigned int> & aOuter2inner,
909  std::vector<unsigned int> & aInner2outer,
910  const FreemanChain & aOuterChain,
911  bool ccw )
912 {
913  unsigned int nb = (unsigned int)aOuterChain.chain.size();
914  unsigned int j = 0;
915  aOuter2inner.clear();
916  aOuter2inner.reserve( nb );
917  // aInnerChain.chain.reserve( nb + 4 );
918  aInnerChain.chain = "";
919  aInner2outer.clear();
920  aInner2outer.reserve( nb + ( ccw ? 4 : -4 ) );
921  int dx0=0, dy0=0;
922  int dx1=0, dy1=0;
923  FreemanChain<TInteger>::displacement( dx0, dy0, aOuterChain.code( 0 ) );
924  int turn = ccw ? 1 : 3;
925  //FreemanChain<TInteger>::displacement( dx1, dy1, ( aOuterChain.code( 0 ) + turn ) % 4 );
926  FreemanChain<TInteger>::displacement( dx1, dy1, addToCode( aOuterChain.code( 0 ) , turn ) );
927  dx0 += dx1;
928  dy0 += dy1;
929  aInnerChain.x0 = dx0 > 0 ? aOuterChain.x0 : aOuterChain.x0 - 1;
930  aInnerChain.y0 = dy0 > 0 ? aOuterChain.y0 : aOuterChain.y0 - 1;
931 
932  ConstIterator it_begin = aOuterChain.begin();
933  ConstIterator it = it_begin;
934  it.next();
935  for ( unsigned int i = 0; i < nb; ++i )
936  {
937  // Check if contour is open.
938  // cerr << "i=" << i << " code=" << aOuterChain.code( i ) << endl;
939  switch ( movement( aOuterChain.code( i ), aOuterChain.code( ( i + 1 ) % nb ), ccw ) )
940  {
941  case '0':
942  // contour going in then out.
943  aInnerChain.chain += aOuterChain.chain[ i ];
944  //aInnerChain.chain += ( ( ( (unsigned int) ( aOuterChain.chain[ i ] - '0' )
945  // + ( ccw ? 3 : 1 ) ) )
946  // % 4 ) + '0';
947  aInnerChain.chain += addToCode ( aOuterChain.chain[ i ], (ccw) ? 3 : 1 );
948  aInnerChain.chain += aOuterChain.chain[ ( i + 1 ) % nb ];
949  aOuter2inner.push_back( j );
950  aInner2outer.push_back( i );
951  aInner2outer.push_back( i + 1 );
952  aInner2outer.push_back( i + 1 );
953  j += 3;
954  break;
955 
956  case '1':
957  // contour turning toward its inside.
958  aOuter2inner.push_back( j );
959  break;
960 
961  case '2':
962  // contour going straight ahead
963  aInnerChain.chain += aOuterChain.chain[ i ];
964  aOuter2inner.push_back( j );
965  aInner2outer.push_back( i );
966  ++j;
967  break;
968 
969  case '3':
970  // contour turning toward its outside.
971  aInnerChain.chain += aOuterChain.chain[ i ];
972  aInnerChain.chain += aOuterChain.chain[ ( i + 1 ) % nb ];
973  aOuter2inner.push_back( j );
974  aInner2outer.push_back( i );
975  aInner2outer.push_back( i + 1 );
976  j += 2;
977  break;
978  }
979 
980  // Advances along contour and check if it is a closed contour.
981  it.next();
982  if ( ( i == nb - 1 )
983  && ( *it_begin != *it ) )
984  // freeman chain is *not* a closed loop.
985  {
986  aInnerChain.chain += aOuterChain.chain[ i ];
987  aOuter2inner.push_back( j );
988  aInner2outer.push_back( i );
989  ++i;
990  ++j;
991  break;
992  }
993  }
994 }
995 
996 
997 
998 
999 template <typename TInteger>
1000 bool DGtal::FreemanChain<TInteger>::cleanOuterSpikes(
1001  FreemanChain & aCleanC,
1002  std::vector<unsigned int> & aC2clean,
1003  std::vector<unsigned int> & aClean2c,
1004  const FreemanChain & c,
1005  bool ccw )
1006 {
1007  unsigned int nb = (unsigned int)c.chain.size();
1008  if ( nb == 0 )
1009  {
1010  std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1011  << " cleanOuterSpikes: Empty input chain"
1012  << std::endl;
1013  return false;
1014  }
1015 
1016  ModuloComputer< DGtal::int32_t > mc( nb );
1017  ModuloComputer< DGtal::int32_t >::UnsignedInteger i = 0;
1018  ModuloComputer< DGtal::int32_t >::UnsignedInteger j = 0;
1019  std::vector<unsigned int> c2cleanTMP;
1020  aCleanC.chain.reserve( nb );
1021  aCleanC.chain = "";
1022  aC2clean.clear();
1023  aClean2c.clear();
1024  aC2clean.reserve( nb );
1025  aClean2c.reserve( nb );
1026  c2cleanTMP.reserve( nb );
1027  ConstIterator it = c.begin();
1028  ConstIterator itn = c.begin();
1029  itn.nextInLoop();
1030  // Find a consistent starting point.
1031  unsigned int n;
1032  unsigned int size_spike = 0;
1033  for ( n = 0; n < nb; ++n )
1034  {
1035  size_spike = 0;
1036  while ( movement( it.getCode(), itn.getCode(), ccw ) == '0' )
1037  {
1038  it.previousInLoop();
1039  itn.nextInLoop();
1040  mc.increment( i );
1041  size_spike += 2;
1042  if ( size_spike >= nb )
1043  {
1044  std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1045  << " Spike is longer than contour !"
1046  << " size_spike=" << size_spike
1047  << " nb=" << nb
1048  << std::endl;
1049  return false;
1050  }
1051  }
1052  mc.increment( i );
1053  it = itn;
1054  itn.nextInLoop();
1055  if ( size_spike > 0 )
1056  break;
1057  }
1058  unsigned int start_idx = it.position();
1059  i = start_idx;
1060  // JOL : 2009/07/07, added starting coordinates
1061  // XP : 2011/09/06, added ending coordinates
1062  Point P = *it;
1063  aCleanC.x0 = P[0];
1064  aCleanC.y0 = P[1];
1065  aCleanC.xn = P[0];
1066  aCleanC.yn = P[1];
1067 
1068  // cerr << "Starting point is " << i << endl;
1069  ASSERT( ( n < nb ) || ( i == 0 ) );
1070  if ( n == nb )
1071  { // do nothing
1072  aCleanC.chain = c.chain;
1073  for ( unsigned int ni = 0; ni < nb; ++ni )
1074  {
1075  aC2clean.push_back( ni );
1076  aClean2c.push_back( ni );
1077  }
1078  if ( size_spike != 0 )
1079  std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1080  << "No starting point found (only spikes !)" << std::endl;
1081 
1082  return size_spike == 0;
1083  }
1084  // Loops over all letters.
1085  ConstIterator it_begin = it;
1086  std::deque<unsigned int> clean_code;
1087  std::deque<unsigned int> clean_idx;
1088  std::vector<unsigned int> begin_outer_spike;
1089  std::vector<unsigned int> end_outer_spike;
1090  // i follows iterator it.
1091  do
1092  {
1093  clean_code.push_back( it.getCode() );
1094  clean_idx.push_back( i );
1095  itn = it;
1096  it.nextInLoop();
1097  mc.increment( i );
1098  // cerr << "- i=" << i << " (" << clean_code.back()
1099  // << it.getCode() << ") ";
1100  size_spike = 0;
1101  unsigned int last_spike_idx = end_outer_spike.empty() ?
1102  start_idx :
1103  end_outer_spike.back();
1104  j = i;
1105  while ( ( ! clean_code.empty() )
1106  && ( j != last_spike_idx )
1107  && ( movement( clean_code.back(), it.getCode(), ccw ) == '0' )
1108  && ( it != it_begin ) )
1109  {
1110  clean_code.pop_back();
1111  clean_idx.pop_back();
1112  mc.increment( i );
1113  mc.decrement( j );
1114  it.nextInLoop();
1115  itn.previousInLoop();
1116  size_spike += 2;
1117  }
1118  // cerr << "i=" << i << " size_spike=" << size_spike
1119  // << " last_spike_idx=" << last_spike_idx
1120  // << endl;
1121  if ( size_spike != 0 )
1122  {
1123  // There is a spike. Is it an outer one ?
1124  unsigned int previous_code = itn.getCode();
1125  unsigned int previous_idx = itn.position();
1126  // JOL : do not
1127  // consider any more "cleaned contour" since we cannot go
1128  // further than the last spike.
1129  // unsigned int previous_code =
1130  // clean_code.empty() ? itn.getCode() : clean_code.back();
1131  // unsigned int previous_idx =
1132  // clean_code.empty() ? itn.position() : clean_idx.back();
1133  itn = it;
1134  itn.previousInLoop();
1135  unsigned int move1 = movement( previous_code, addToCode ( itn.getCode() , 2 ), ccw );
1136  unsigned int move2 = movement( itn.getCode(), it.getCode() , ccw );
1137  bool return_spike = ( move1 == '0' ) || ( move2 == '0' );
1138  bool outer_spike = ( move1 == '3' ) || ( move2 == '3' );
1139  // if ( return_spike )
1140  // cerr << "[DGtal::FreemanChain::cleanOuterSpikes] return spike."
1141  // << endl;
1142  // if ( ! ( ( outer_spike && ( move1 != 1 ) && ( move2 != 1 ) )
1143  // || ( ! outer_spike && ( move1 != 3 ) && ( move2 != 3 ) ) ) )
1144  // cerr << "[DGtal::FreemanChain::cleanOuterSpikes] "
1145  // << "Weird spike. Invalid contour (expected 3 3) ?"
1146  // << " move1=" << move1
1147  // << " move2=" << move2
1148  // << " ccw=" << ccw
1149  // << " start_idx=" << start_idx
1150  // << " size_spike=" << size_spike
1151  // << " it=" << it.position()
1152  // << " itp=" << previous_idx
1153  // << endl
1154  // << c.chain << endl;
1155  // Process waiting steps.
1156  if ( outer_spike || return_spike )
1157  {
1158  begin_outer_spike.push_back( mc.next( previous_idx ) );
1159  end_outer_spike.push_back( i );
1160  // cout << " outer spike [" << begin_outer_spike.back()
1161  // << "," << end_outer_spike.back() << "[ " << endl;
1162  }
1163  }
1164  }
1165  while ( it != it_begin );
1166 
1167  // Once outer spikes are known, we can create the new contour.
1168  aC2clean.resize( nb );
1169  i = start_idx % nb;
1170  j = 0;
1171  unsigned int nb_spikes = (unsigned int)begin_outer_spike.size();
1172  unsigned int k = 0;
1173  n = 0;
1174  while ( n < nb )
1175  {
1176  if ( ( k == nb_spikes ) || ( i != begin_outer_spike[ k ] ) )
1177  {
1178  aCleanC.chain.push_back( c.chain[ i ] );
1179  aC2clean[ i ] = j;
1180  aClean2c.push_back( i );
1181  mc.increment( i );
1182  ++j;
1183  ++n;
1184  }
1185  else
1186  {
1187  while ( i != end_outer_spike[ k ] )
1188  {
1189  aC2clean[ i ] = j;
1190  mc.increment( i );
1191  ++n;
1192  }
1193  ++k;
1194  }
1195  }
1196  for ( unsigned int ii = 0; ii < nb; ++ii )
1197  if ( aC2clean[ ii ] >= aCleanC.chain.size() )
1198  {
1199  if ( aC2clean[ ii ] == aCleanC.chain.size() )
1200  aC2clean[ ii ] = 0;
1201  else
1202  {
1203  std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1204  << "Bad correspondence for aC2clean[" << ii << "]"
1205  << " = " << aC2clean[ ii ] << " >= " << aCleanC.chain.size()
1206  << std::endl;
1207  aC2clean[ ii ] = aC2clean[ ii ] % aCleanC.chain.size();
1208  }
1209  }
1210 
1211  for ( unsigned int jj = 0; j < aCleanC.chain.size(); ++jj )
1212  if ( aClean2c[ jj ] >= nb )
1213  {
1214  std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1215  << "Bad correspondence for aClean2c[" << jj << "]"
1216  << " = " << aClean2c[ jj ] << " >= " << nb
1217  << std::endl;
1218  aClean2c[ jj ] = aClean2c[ jj ] % nb;
1219  }
1220  return true;
1221 }
1222 
1223 ///////////////////////////////////////////////////////////////////////////////
1224 // Drawing services
1225 
1226 template <typename TInteger>
1227 inline
1228 std::string
1229 DGtal::FreemanChain<TInteger>::className() const
1230 {
1231  return "FreemanChain";
1232 }
1233 
1234 template <typename TInteger>
1235 inline
1236 void
1237 DGtal::FreemanChain<TInteger>::computeLastPoint()
1238 {
1239  ConstIterator it = this->begin();
1240  for (unsigned int i=0; i < chain.size(); ++i)
1241  it++;
1242  xn = (*it)[0];
1243  yn = (*it)[1];
1244 }
1245 
1246 
1247 
1248 
1249 
1250 
1251 ///////////////////////////////////////////////////////////////////////////////
1252 // Implementation of inline functions and external operators //
1253 
1254 /**
1255  * Overloads 'operator<<' for displaying objects of class 'FreemanChain'.
1256  * @param out the output stream where the object is written.
1257  * @param object the object of class 'FreemanChain' to write.
1258  * @return the output stream after the writing.
1259  */
1260 template <typename TInteger>
1261 inline
1262  std::ostream&
1263 DGtal::operator<< ( std::ostream & out,
1264  const FreemanChain<TInteger> & aObject )
1265 {
1266  aObject.selfDisplay ( out );
1267  return out;
1268 }
1269 
1270 // //
1271 ///////////////////////////////////////////////////////////////////////////////
1272 
1273