Loading [MathJax]/extensions/TeX/AMSsymbols.js
DGtal 2.0.0
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
48template <typename TInteger>
49inline
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 */
73template <typename TInteger>
74inline
75typename DGtal::FreemanChain<TInteger>::ConstIterator &
76DGtal::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
88template <typename TInteger>
89inline
90void 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
108template <typename TInteger>
109inline
110void 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
126template <typename TInteger>
127inline
128void 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
153template <typename TInteger>
154inline
155void 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 */
181template <typename TInteger>
182DGtal::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 */
192template <typename TInteger>
193DGtal::FreemanChain<TInteger>::
194FreemanChain( 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 */
205template <typename TInteger>
206DGtal::FreemanChain<TInteger>::FreemanChain(std::istream & in ){
207 read(in, *this);
208 computeLastPoint();
209}
210
211
212/**
213 * Copy constructor.
214 * @param aOther the object to clone.
215 */
216template <typename TInteger>
217DGtal::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 */
230template <typename TInteger>
231typename DGtal::FreemanChain<TInteger> &
232DGtal::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
253template <typename TInteger>
254typename DGtal::FreemanChain<TInteger>::ConstIterator
255DGtal::FreemanChain<TInteger>::begin() const
256{
257 return ConstIterator( *this, 0 );
258}
259
260
261template <typename TInteger>
262typename DGtal::FreemanChain<TInteger>::ConstIterator
263DGtal::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 aPos a position in the chain code.
272 * @return the next position.
273 */
274template <typename TInteger>
275typename DGtal::FreemanChain<TInteger>::Index
276DGtal::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 aPos a position in the chain code.
286 * @return the previous position.
287 */
288template <typename TInteger>
289typename DGtal::FreemanChain<TInteger>::Index
290DGtal::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 */
301template <typename TInteger>
302char
303DGtal::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 */
314template <typename TInteger>
315inline
316typename DGtal::FreemanChain<TInteger>::Index
317DGtal::FreemanChain<TInteger>::size() const
318{
319 return (typename DGtal::FreemanChain<TInteger>::Size)(chain.size());
320}
321
322
323template <typename TInteger>
324inline
325void 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
349template <typename TInteger>
350inline
351typename DGtal::FreemanChain<TInteger>::ConstIterator
352DGtal::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
400template <typename TInteger>
401inline
402typename DGtal::FreemanChain<TInteger>::ConstIterator
403DGtal::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
458template <typename TInteger>
459inline
460int DGtal::FreemanChain<TInteger>::isClosed() const
461{
462 return (x0 == xn) && (y0 == yn);
463}
464
465
466template <typename TInteger>
467inline
468int 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
499template <typename TInteger>
500inline
501typename DGtal::FreemanChain<TInteger>
502DGtal::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
516template <typename TInteger>
517inline
518typename DGtal::FreemanChain<TInteger>
519DGtal::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
532template <typename TInteger>
533inline
534typename DGtal::FreemanChain<TInteger>&
535DGtal::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
545template <typename TInteger>
546inline
547typename DGtal::FreemanChain<TInteger>::Point
548DGtal::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
571template <typename TInteger>
572inline
573typename DGtal::FreemanChain<TInteger> &
574DGtal::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
589template <typename TInteger>
590inline
591typename DGtal::FreemanChain<TInteger> &
592DGtal::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
611template <typename TInteger>
612inline
613void 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 */
623template <typename TInteger>
624inline
625bool 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
642template <typename TInteger>
643inline
644void 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
661template <typename TInteger>
662template <typename TConstIterator>
663inline
664void 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
706template <typename TInteger>
707template <typename TRange>
708inline
709void 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
715template <typename TInteger>
716inline
717void 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
729template <typename TInteger>
730inline
731void 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
770template <typename TInteger>
771void
772DGtal::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
782template <typename TInteger>
783inline
784char DGtal::FreemanChain<TInteger>::movement( char aCode1,
785 char aCode2, bool ccw )
786{
787 unsigned int cfg = ( ccw ? 0 : 16 ) + ( (aCode1 - '0') << 2 ) + (aCode2 - '0');
788 static const char tbl[ 32 ] =
789 {
790 '2', '1', '0', '3', '3', '2', '1', '0',
791 '0', '3', '2', '1', '1', '0', '3', '2',
792 '2', '3', '0', '1', '1', '2', '3', '0',
793 '0', '1', '2', '3', '3', '0', '1', '2'
794 };
795 return tbl[ cfg ];
796}
797
798
799
800template <typename TInteger>
801inline
802char DGtal::FreemanChain<TInteger>::addToCode( char code, int n)
803{
804 return '0' + ( ( (code - '0' ) + n ) & 3 );
805}
806
807
808
809template <typename TInteger>
810inline
811short DGtal::FreemanChain<TInteger>::freemanCode4C(int dx, int dy)
812{
813 short number = static_cast<short>(( dx != 0 ? (1 - dx) : (2 - dy) ));
814 if ( (number < 0) || (number > 3) )
815 {
816 return 8;
817 }
818 return number;
819}
820
821
822
823template <typename TInteger>
824inline
825void
826DGtal::FreemanChain<TInteger>::displacement( int & dx, int & dy, char aCode )
827{
828 switch ( aCode )
829 {
830 case '0': dx = 1; dy = 0; break;
831 case '1': dx = 0; dy = 1; break;
832 case '2': dx = -1; dy = 0; break;
833 case '3': dx = 0; dy = -1; break;
834 }
835}
836
837
838template <typename TInteger>
839inline
840typename DGtal::PointVector<2,TInteger>
841DGtal::FreemanChain<TInteger>::displacement( char aCode )
842{
843 switch ( aCode )
844 {
845 case '0': return Point({1,0});
846 case '1': return Point({0,1});
847 case '2': return Point({-1,0});
848 case '3': return Point({0,-1});
849 }
850 return Point({0,0});
851}
852
853
854
855template <typename TInteger>
856inline
857char
858DGtal::FreemanChain<TInteger>::turnedCode( char aCode, bool ccw )
859{
860 if ( ccw ) return ( aCode == '3' ) ? '0' : ( aCode + 1 );
861 else return ( aCode == '0' ) ? '3' : ( aCode - 1 );
862}
863//DGtal::FreemanChain<TInteger>::turnedCode( unsigned int aCode, bool ccw )
864//{
865// if ( ccw ) return ( aCode + 1 ) & 0x3;
866// else return ( aCode - 1 ) & 0x3;
867//}
868
869
870
871
872
873
874
875template <typename TInteger>
876void DGtal::FreemanChain<TInteger>::innerContour(
877 FreemanChain & aInnerChain,
878 std::vector<unsigned int> & aOuter2inner,
879 std::vector<unsigned int> & aInner2outer,
880 const FreemanChain & aOuterChain,
881 bool ccw )
882{
883 unsigned int nb = (unsigned int)aOuterChain.chain.size();
884 unsigned int j = 0;
885 aOuter2inner.clear();
886 aOuter2inner.reserve( nb );
887 // aInnerChain.chain.reserve( nb + 4 );
888 aInnerChain.chain = "";
889 aInner2outer.clear();
890 aInner2outer.reserve( nb + ( ccw ? 4 : -4 ) );
891 int dx0=0, dy0=0;
892 int dx1=0, dy1=0;
893 FreemanChain<TInteger>::displacement( dx0, dy0, aOuterChain.code( 0 ) );
894 int turn = ccw ? 1 : 3;
895 //FreemanChain<TInteger>::displacement( dx1, dy1, ( aOuterChain.code( 0 ) + turn ) % 4 );
896 FreemanChain<TInteger>::displacement( dx1, dy1, addToCode( aOuterChain.code( 0 ) , turn ) );
897 dx0 += dx1;
898 dy0 += dy1;
899 aInnerChain.x0 = dx0 > 0 ? aOuterChain.x0 : aOuterChain.x0 - 1;
900 aInnerChain.y0 = dy0 > 0 ? aOuterChain.y0 : aOuterChain.y0 - 1;
901
902 ConstIterator it_begin = aOuterChain.begin();
903 ConstIterator it = it_begin;
904 it.next();
905 for ( unsigned int i = 0; i < nb; ++i )
906 {
907 // Check if contour is open.
908 // cerr << "i=" << i << " code=" << aOuterChain.code( i ) << endl;
909 switch ( movement( aOuterChain.code( i ), aOuterChain.code( ( i + 1 ) % nb ), ccw ) )
910 {
911 case '0':
912 // contour going in then out.
913 aInnerChain.chain += aOuterChain.chain[ i ];
914 //aInnerChain.chain += ( ( ( (unsigned int) ( aOuterChain.chain[ i ] - '0' )
915 // + ( ccw ? 3 : 1 ) ) )
916 // % 4 ) + '0';
917 aInnerChain.chain += addToCode ( aOuterChain.chain[ i ], (ccw) ? 3 : 1 );
918 aInnerChain.chain += aOuterChain.chain[ ( i + 1 ) % nb ];
919 aOuter2inner.push_back( j );
920 aInner2outer.push_back( i );
921 aInner2outer.push_back( i + 1 );
922 aInner2outer.push_back( i + 1 );
923 j += 3;
924 break;
925
926 case '1':
927 // contour turning toward its inside.
928 aOuter2inner.push_back( j );
929 break;
930
931 case '2':
932 // contour going straight ahead
933 aInnerChain.chain += aOuterChain.chain[ i ];
934 aOuter2inner.push_back( j );
935 aInner2outer.push_back( i );
936 ++j;
937 break;
938
939 case '3':
940 // contour turning toward its outside.
941 aInnerChain.chain += aOuterChain.chain[ i ];
942 aInnerChain.chain += aOuterChain.chain[ ( i + 1 ) % nb ];
943 aOuter2inner.push_back( j );
944 aInner2outer.push_back( i );
945 aInner2outer.push_back( i + 1 );
946 j += 2;
947 break;
948 }
949
950 // Advances along contour and check if it is a closed contour.
951 it.next();
952 if ( ( i == nb - 1 )
953 && ( *it_begin != *it ) )
954 // freeman chain is *not* a closed loop.
955 {
956 aInnerChain.chain += aOuterChain.chain[ i ];
957 aOuter2inner.push_back( j );
958 aInner2outer.push_back( i );
959 ++i;
960 ++j;
961 break;
962 }
963 }
964}
965
966
967
968
969template <typename TInteger>
970bool DGtal::FreemanChain<TInteger>::cleanOuterSpikes(
971 FreemanChain & aCleanC,
972 std::vector<unsigned int> & aC2clean,
973 std::vector<unsigned int> & aClean2c,
974 const FreemanChain & c,
975 bool ccw )
976{
977 unsigned int nb = (unsigned int)c.chain.size();
978 if ( nb == 0 )
979 {
980 std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
981 << " cleanOuterSpikes: Empty input chain"
982 << std::endl;
983 return false;
984 }
985
986 ModuloComputer< DGtal::int32_t > mc( nb );
987 ModuloComputer< DGtal::int32_t >::UnsignedInteger i = 0;
988 ModuloComputer< DGtal::int32_t >::UnsignedInteger j = 0;
989 std::vector<unsigned int> c2cleanTMP;
990 aCleanC.chain.reserve( nb );
991 aCleanC.chain = "";
992 aC2clean.clear();
993 aClean2c.clear();
994 aC2clean.reserve( nb );
995 aClean2c.reserve( nb );
996 c2cleanTMP.reserve( nb );
997 ConstIterator it = c.begin();
998 ConstIterator itn = c.begin();
999 itn.nextInLoop();
1000 // Find a consistent starting point.
1001 unsigned int n;
1002 unsigned int size_spike = 0;
1003 for ( n = 0; n < nb; ++n )
1004 {
1005 size_spike = 0;
1006 while ( movement( it.getCode(), itn.getCode(), ccw ) == '0' )
1007 {
1008 it.previousInLoop();
1009 itn.nextInLoop();
1010 mc.increment( i );
1011 size_spike += 2;
1012 if ( size_spike >= nb )
1013 {
1014 std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1015 << " Spike is longer than contour !"
1016 << " size_spike=" << size_spike
1017 << " nb=" << nb
1018 << std::endl;
1019 return false;
1020 }
1021 }
1022 mc.increment( i );
1023 it = itn;
1024 itn.nextInLoop();
1025 if ( size_spike > 0 )
1026 break;
1027 }
1028 unsigned int start_idx = it.position();
1029 i = start_idx;
1030 // JOL : 2009/07/07, added starting coordinates
1031 // XP : 2011/09/06, added ending coordinates
1032 Point P = *it;
1033 aCleanC.x0 = P[0];
1034 aCleanC.y0 = P[1];
1035 aCleanC.xn = P[0];
1036 aCleanC.yn = P[1];
1037
1038 // cerr << "Starting point is " << i << endl;
1039 ASSERT( ( n < nb ) || ( i == 0 ) );
1040 if ( n == nb )
1041 { // do nothing
1042 aCleanC.chain = c.chain;
1043 for ( unsigned int ni = 0; ni < nb; ++ni )
1044 {
1045 aC2clean.push_back( ni );
1046 aClean2c.push_back( ni );
1047 }
1048 if ( size_spike != 0 )
1049 std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1050 << "No starting point found (only spikes !)" << std::endl;
1051
1052 return size_spike == 0;
1053 }
1054 // Loops over all letters.
1055 ConstIterator it_begin = it;
1056 std::deque<unsigned int> clean_code;
1057 std::deque<unsigned int> clean_idx;
1058 std::vector<unsigned int> begin_outer_spike;
1059 std::vector<unsigned int> end_outer_spike;
1060 // i follows iterator it.
1061 do
1062 {
1063 clean_code.push_back( it.getCode() );
1064 clean_idx.push_back( i );
1065 itn = it;
1066 it.nextInLoop();
1067 mc.increment( i );
1068 // cerr << "- i=" << i << " (" << clean_code.back()
1069 // << it.getCode() << ") ";
1070 size_spike = 0;
1071 unsigned int last_spike_idx = end_outer_spike.empty() ?
1072 start_idx :
1073 end_outer_spike.back();
1074 j = i;
1075 while ( ( ! clean_code.empty() )
1076 && ( j != last_spike_idx )
1077 && ( movement( clean_code.back(), it.getCode(), ccw ) == '0' )
1078 && ( it != it_begin ) )
1079 {
1080 clean_code.pop_back();
1081 clean_idx.pop_back();
1082 mc.increment( i );
1083 mc.decrement( j );
1084 it.nextInLoop();
1085 itn.previousInLoop();
1086 size_spike += 2;
1087 }
1088 // cerr << "i=" << i << " size_spike=" << size_spike
1089 // << " last_spike_idx=" << last_spike_idx
1090 // << endl;
1091 if ( size_spike != 0 )
1092 {
1093 // There is a spike. Is it an outer one ?
1094 unsigned int previous_code = itn.getCode();
1095 unsigned int previous_idx = itn.position();
1096 // JOL : do not
1097 // consider any more "cleaned contour" since we cannot go
1098 // further than the last spike.
1099 // unsigned int previous_code =
1100 // clean_code.empty() ? itn.getCode() : clean_code.back();
1101 // unsigned int previous_idx =
1102 // clean_code.empty() ? itn.position() : clean_idx.back();
1103 itn = it;
1104 itn.previousInLoop();
1105 unsigned int move1 = movement( previous_code, addToCode ( itn.getCode() , 2 ), ccw );
1106 unsigned int move2 = movement( itn.getCode(), it.getCode() , ccw );
1107 bool return_spike = ( move1 == '0' ) || ( move2 == '0' );
1108 bool outer_spike = ( move1 == '3' ) || ( move2 == '3' );
1109 // if ( return_spike )
1110 // cerr << "[DGtal::FreemanChain::cleanOuterSpikes] return spike."
1111 // << endl;
1112 // if ( ! ( ( outer_spike && ( move1 != 1 ) && ( move2 != 1 ) )
1113 // || ( ! outer_spike && ( move1 != 3 ) && ( move2 != 3 ) ) ) )
1114 // cerr << "[DGtal::FreemanChain::cleanOuterSpikes] "
1115 // << "Weird spike. Invalid contour (expected 3 3) ?"
1116 // << " move1=" << move1
1117 // << " move2=" << move2
1118 // << " ccw=" << ccw
1119 // << " start_idx=" << start_idx
1120 // << " size_spike=" << size_spike
1121 // << " it=" << it.position()
1122 // << " itp=" << previous_idx
1123 // << endl
1124 // << c.chain << endl;
1125 // Process waiting steps.
1126 if ( outer_spike || return_spike )
1127 {
1128 begin_outer_spike.push_back( mc.next( previous_idx ) );
1129 end_outer_spike.push_back( i );
1130 // cout << " outer spike [" << begin_outer_spike.back()
1131 // << "," << end_outer_spike.back() << "[ " << endl;
1132 }
1133 }
1134 }
1135 while ( it != it_begin );
1136
1137 // Once outer spikes are known, we can create the new contour.
1138 aC2clean.resize( nb );
1139 i = start_idx % nb;
1140 j = 0;
1141 unsigned int nb_spikes = (unsigned int)begin_outer_spike.size();
1142 unsigned int k = 0;
1143 n = 0;
1144 while ( n < nb )
1145 {
1146 if ( ( k == nb_spikes ) || ( i != begin_outer_spike[ k ] ) )
1147 {
1148 aCleanC.chain.push_back( c.chain[ i ] );
1149 aC2clean[ i ] = j;
1150 aClean2c.push_back( i );
1151 mc.increment( i );
1152 ++j;
1153 ++n;
1154 }
1155 else
1156 {
1157 while ( i != end_outer_spike[ k ] )
1158 {
1159 aC2clean[ i ] = j;
1160 mc.increment( i );
1161 ++n;
1162 }
1163 ++k;
1164 }
1165 }
1166 for ( unsigned int ii = 0; ii < nb; ++ii )
1167 if ( aC2clean[ ii ] >= aCleanC.chain.size() )
1168 {
1169 if ( aC2clean[ ii ] == aCleanC.chain.size() )
1170 aC2clean[ ii ] = 0;
1171 else
1172 {
1173 std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1174 << "Bad correspondence for aC2clean[" << ii << "]"
1175 << " = " << aC2clean[ ii ] << " >= " << aCleanC.chain.size()
1176 << std::endl;
1177 aC2clean[ ii ] = aC2clean[ ii ] % aCleanC.chain.size();
1178 }
1179 }
1180
1181 for ( unsigned int jj = 0; j < aCleanC.chain.size(); ++jj )
1182 if ( aClean2c[ jj ] >= nb )
1183 {
1184 std::cerr << "[DGtal::FreemanChain::cleanOuterSpikes]"
1185 << "Bad correspondence for aClean2c[" << jj << "]"
1186 << " = " << aClean2c[ jj ] << " >= " << nb
1187 << std::endl;
1188 aClean2c[ jj ] = aClean2c[ jj ] % nb;
1189 }
1190 return true;
1191}
1192
1193///////////////////////////////////////////////////////////////////////////////
1194// Drawing services
1195
1196template <typename TInteger>
1197inline
1198std::string
1199DGtal::FreemanChain<TInteger>::className() const
1200{
1201 return "FreemanChain";
1202}
1203
1204template <typename TInteger>
1205inline
1206void
1207DGtal::FreemanChain<TInteger>::computeLastPoint()
1208{
1209 ConstIterator it = this->begin();
1210 for (unsigned int i=0; i < chain.size(); ++i)
1211 it++;
1212 xn = (*it)[0];
1213 yn = (*it)[1];
1214}
1215
1216
1217
1218
1219
1220
1221///////////////////////////////////////////////////////////////////////////////
1222// Implementation of inline functions and external operators //
1223
1224/**
1225 * Overloads 'operator<<' for displaying objects of class 'FreemanChain'.
1226 * @param out the output stream where the object is written.
1227 * @param aObject the object of class 'FreemanChain' to write.
1228 * @return the output stream after the writing.
1229 */
1230template <typename TInteger>
1231inline
1232 std::ostream&
1233DGtal::operator<< ( std::ostream & out,
1234 const FreemanChain<TInteger> & aObject )
1235{
1236 aObject.selfDisplay ( out );
1237 return out;
1238}
1239
1240// //
1241///////////////////////////////////////////////////////////////////////////////
1242
1243