00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #ifndef __LABELING_H__
00030 #define __LABELING_H__
00031
00032 #include <iostream>
00033
00034 #include <algorithm>
00035 #include <list>
00036 #include <queue>
00037
00038 #define CLEAR_DST_BUFFER 1
00039 #define CLEAR_ALL_DST_BUFFER 0
00040 #define CALC_CENTER_OF_GRAVITY 1
00041
00042 template<class SrcT, class DstT>
00043 class Labeling {
00044 public:
00045
00046
00047
00048 class RasterSegment {
00049 private:
00050 int left_x;
00051 int right_x;
00052 int y;
00053 SrcT source_value;
00054 public:
00055 RasterSegment( const int n_left_x, const int n_right_x,
00056 const int n_y, const SrcT n_source_value )
00057 : left_x( n_left_x ), right_x( n_right_x ), y( n_y ),
00058 source_value( n_source_value )
00059 {
00060 }
00061
00062 ~RasterSegment()
00063 {
00064 }
00065
00066
00067
00068 inline int
00069 GetLeftX( void ) const
00070 {
00071 return left_x;
00072 }
00073
00074 inline int
00075 GetRightX( void ) const
00076 {
00077 return right_x;
00078 }
00079
00080 inline int
00081 GetY( void ) const
00082 {
00083 return y;
00084 }
00085
00086 inline SrcT
00087 GetSourceValue( void ) const
00088 {
00089 return source_value;
00090 }
00091
00092
00093
00094 inline int
00095 LeftX( void ) const
00096 {
00097 return left_x;
00098 }
00099
00100 inline int
00101 RightX( void ) const
00102 {
00103 return right_x;
00104 }
00105
00106 inline int
00107 Y( void ) const
00108 {
00109 return y;
00110 }
00111
00112 inline SrcT
00113 SourceValue( void ) const
00114 {
00115 return source_value;
00116 }
00117
00118 friend std::ostream&
00119 operator<<( std::ostream& s, RasterSegment& rs )
00120 {
00121 s << rs.LeftX() << " "
00122 << rs.RightX() << " "
00123 << rs.Y() << " "
00124 << rs.SourceValue() << std::endl;
00125
00126 return s;
00127 }
00128 };
00129
00130 typedef std::list<RasterSegment *> RSPList;
00131 typedef typename std::list<RasterSegment *>::iterator RSPIterator;
00132
00133 typedef std::queue<RasterSegment *> RSPQueue;
00134
00135
00136
00137 class RegionInfo {
00138
00139 private:
00140 int num_of_pixels;
00141 float center_x, center_y;
00142 int size_x, size_y;
00143 int min_x, min_y;
00144 int max_x, max_y;
00145 SrcT source_value;
00146 DstT result;
00147 RSPList raster_segment_list;
00148 #if CALC_CENTER_OF_GRAVITY
00149 float gravity_x, gravity_y;
00150 #endif
00151 public:
00152
00153
00154 RegionInfo()
00155 {
00156 raster_segment_list.clear();
00157 }
00158
00159 ~RegionInfo()
00160 {
00161 RSPIterator rspi;
00162 for ( rspi = raster_segment_list.begin();
00163 rspi != raster_segment_list.end(); rspi++ ) {
00164 RasterSegment *rs = *rspi;
00165 delete rs;
00166 }
00167 raster_segment_list.erase( raster_segment_list.begin(),
00168 raster_segment_list.end());
00169 }
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180 inline void
00181 SetNumOfPixels( const int n_num_of_pixels )
00182 {
00183 num_of_pixels = n_num_of_pixels;
00184 }
00185
00186 inline void
00187 SetCenter( const float x, const float y )
00188 {
00189 center_x = x;
00190 center_y = y;
00191 }
00192
00193 inline void
00194 SetSize( const int x, const int y )
00195 {
00196 size_x = x;
00197 size_y = y;
00198 }
00199
00200 inline void
00201 SetMin( const int x, const int y )
00202 {
00203 min_x = x;
00204 min_y = y;
00205 }
00206
00207 inline void
00208 SetMax( const int x, const int y )
00209 {
00210 max_x = x;
00211 max_y = y;
00212 }
00213
00214 inline void
00215 SetMinMax( const int n_min_x, const int n_min_y,
00216 const int n_max_x, const int n_max_y )
00217 {
00218 SetMin( n_min_x, n_min_y );
00219 SetMax( n_max_x, n_max_y );
00220 SetCenter(( n_min_x + n_max_x ) / 2.0f,
00221 ( n_min_y + n_max_y ) / 2.0f );
00222 SetSize( n_max_x - n_min_x + 1, n_max_y - n_min_y + 1 );
00223 }
00224
00225 inline void
00226 SetCenterOfGravity( const float x, const float y )
00227 {
00228 gravity_x = x;
00229 gravity_y = y;
00230 }
00231
00232 inline void
00233 SetSourceValue( const SrcT n_source_value )
00234 {
00235 source_value = n_source_value;
00236 }
00237
00238 inline void
00239 SetResult( const DstT n_result )
00240 {
00241 result = n_result;
00242 }
00243
00244
00245
00246 inline int
00247 GetNumOfPixels( void ) const
00248 {
00249 return num_of_pixels;
00250 }
00251
00252 inline void
00253 GetCenter( float& x, float& y ) const
00254 {
00255 x = center_x;
00256 y = center_y;
00257 }
00258
00259 inline void
00260 GetSize( int& x, int& y ) const
00261 {
00262 x = size_x;
00263 y = size_y;
00264 }
00265
00266 inline void
00267 GetMin( int& x, int& y ) const
00268 {
00269 x = min_x;
00270 y = min_y;
00271 }
00272
00273 inline void
00274 GetMax( int& x, int& y ) const
00275 {
00276 x = max_x;
00277 y = max_y;
00278 }
00279
00280 inline void
00281 GetCenterOfGravity( float& x, float& y ) const
00282 {
00283 x = gravity_x;
00284 y = gravity_y;
00285 }
00286
00287 inline SrcT
00288 GetSourceValue( void ) const
00289 {
00290 return source_value;
00291 }
00292
00293 inline DstT
00294 GetResult( void ) const
00295 {
00296 return result;
00297 }
00298
00299
00300
00301 inline RSPList&
00302 GetRasterSegmentList( void )
00303 {
00304 return raster_segment_list;
00305 }
00306
00307 inline void
00308 Push( RasterSegment *rs )
00309 {
00310 raster_segment_list.push_front( rs );
00311 }
00312
00313 inline void
00314 Pop( RasterSegment * & rs )
00315 {
00316 RSPIterator rspi = raster_segment_list.begin();
00317 rs = *rspi;
00318 raster_segment_list.erase( rspi );
00319 }
00320
00321 inline int
00322 GetNumOfRasterSegments( void )
00323 {
00324 return raster_segment_list.size();
00325 }
00326
00327
00328
00329 friend bool
00330 operator<( const RegionInfo& l, const RegionInfo& r )
00331 {
00332 bool b = ( l.GetNumOfPixels() < r.GetNumOfPixels());
00333 return b;
00334 }
00335
00336 friend std::ostream&
00337 operator<<( std::ostream& s, RegionInfo& ri )
00338 {
00339 int x, y;
00340 float cx, cy;
00341
00342 s << "num_of_pixels: " << ri.GetNumOfPixels() << std::endl;
00343
00344 ri.GetCenter( cx, cy );
00345 s << "center: " << cx << "," << cy << std::endl;
00346
00347 ri.GetSize( x, y );
00348 s << "size: " << x << "," << y << std::endl;
00349
00350 ri.GetMin( x, y );
00351 s << "min: " << x << "," << y << std::endl;
00352
00353 ri.GetMax( x, y );
00354 s << "max: " << x << "," << y << std::endl;
00355
00356 #if CALC_CENTER_OF_GRAVITY
00357 ri.GetCenterOfGravity( cx, cy );
00358 s << "center_of_graivty: " << cx << "," << cy << std::endl;
00359 #endif
00360
00361 s << "source_value: "
00362 << static_cast<int>( ri.GetSourceValue()) << std::endl
00363 << "result: "
00364 << static_cast<int>( ri.GetResult()) << std::endl;
00365
00366 return s;
00367 }
00368 };
00369
00370 typedef std::list<RegionInfo *> RIPList;
00371 typedef typename std::list<RegionInfo *>::iterator RIPIterator;
00372
00373 typedef std::vector<RegionInfo *> RIPVector;
00374
00375 private:
00376 static const int DEFAULT_REGION_SIZE_MIN = 10;
00377
00378 SrcT *src_frame;
00379 DstT *dst_frame;
00380 int width;
00381 int height;
00382 int total_num;
00383
00384 RSPList *raster_segment_list;
00385 int num_of_raster_segments;
00386
00387 RSPQueue seed_queue;
00388
00389 RIPList region_info_list;
00390 int num_of_regions;
00391
00392 RIPVector result_region_info;
00393 int num_of_result_regions;
00394
00395
00396
00397 void
00398 RegisterSegment( const int lx, const int rx,
00399 const int y, const SrcT src_value )
00400 {
00401 RasterSegment *rs = new RasterSegment( lx, rx, y, src_value );
00402
00403 raster_segment_list[ y ].push_back( rs );
00404 num_of_raster_segments++;
00405 }
00406
00407 void
00408 SearchNeighboringSegment( RasterSegment *rs_seed, const int dy )
00409 {
00410 RSPList *rspl_p = &raster_segment_list[ rs_seed->Y() + dy ];
00411 RSPIterator rspi;
00412
00413 int rs_seed_lx = rs_seed->LeftX();
00414 int rs_seed_rx = rs_seed->RightX();
00415 int rs_seed_source_value = rs_seed->SourceValue();
00416
00417 rspi = rspl_p->begin();
00418
00419 #if 1
00420 if ( rspi == rspl_p->end()) {
00421 return;
00422 }
00423
00424 while (( *rspi )->RightX() < rs_seed_lx ) {
00425 rspi++;
00426 if ( rspi == rspl_p->end()) {
00427 return;
00428 }
00429 }
00430 RasterSegment *rs;
00431 while (( rs = *rspi )->LeftX() <= rs_seed_rx ) {
00432 if ( rs_seed_source_value == rs->SourceValue()) {
00433 rspi = rspl_p->erase( rspi );
00434 seed_queue.push( rs );
00435 } else {
00436 rspi++;
00437 }
00438 if ( rspi == rspl_p->end()) {
00439 return;
00440 }
00441 }
00442
00443 return;
00444 #endif
00445 #if 0
00446 while ( rspi != rspl_p->end()) {
00447 RasterSegment *rs = *rspi;
00448 if ( rs_seed_source_value == rs->SourceValue()
00449 && rs_seed_lx <= rs->RightX()
00450 && rs_seed_rx >= rs->LeftX()) {
00451 rspi = rspl_p->erase( rspi );
00452 seed_queue.push( rs );
00453 } else {
00454 rspi++;
00455 }
00456 }
00457 #endif
00458 }
00459
00460 RegionInfo *
00461 ConnectRasterSegment( RasterSegment *rs_seed,
00462 const DstT region_num )
00463 {
00464 RegionInfo *ri = new RegionInfo;
00465
00466 int num_of_pixels = 0;
00467 int min_x, min_y;
00468 int max_x, max_y;
00469 SrcT source_value;
00470
00471 min_x = rs_seed->LeftX();
00472 max_x = rs_seed->RightX();
00473 min_y = max_y = rs_seed->Y();
00474 source_value = rs_seed->SourceValue();
00475
00476 #if CALC_CENTER_OF_GRAVITY
00477 int sum_x = 0;
00478 int sum_y = 0;
00479 #endif
00480
00481 seed_queue.push( rs_seed );
00482
00483 while ( seed_queue.size() > 0 ) {
00484 RasterSegment *rs = seed_queue.front();
00485 seed_queue.pop();
00486 ri->Push( rs );
00487
00488 int n = rs->RightX() - rs->LeftX() + 1;
00489 num_of_pixels += n;
00490 if ( rs->LeftX() < min_x ) {
00491 min_x = rs->LeftX();
00492 }
00493 if ( rs->RightX() > max_x ) {
00494 max_x = rs->RightX();
00495 }
00496 if ( rs->Y() < min_y ) {
00497 min_y = rs->Y();
00498 } else if ( rs->Y() > max_y ) {
00499 max_y = rs->Y();
00500 }
00501 #if CALC_CENTER_OF_GRAVITY
00502 sum_x += ( rs->LeftX() + rs->RightX()) * n;
00503 sum_y += rs->Y() * n;
00504 #endif
00505
00506 if ( rs->Y() > 0 ) {
00507 SearchNeighboringSegment( rs, -1 );
00508 }
00509 if ( rs->Y() < height - 1 ) {
00510 SearchNeighboringSegment( rs, 1 );
00511 }
00512 }
00513
00514 ri->SetNumOfPixels( num_of_pixels );
00515 ri->SetMinMax( min_x, min_y, max_x, max_y );
00516 ri->SetSourceValue( source_value );
00517 ri->SetResult( region_num );
00518 #if CALC_CENTER_OF_GRAVITY
00519 float gx = static_cast<float>( sum_x ) / ( 2 * num_of_pixels );
00520 float gy = static_cast<float>( sum_y ) / num_of_pixels;
00521 ri->SetCenterOfGravity( gx, gy );
00522 #endif
00523 return ri;
00524 }
00525
00526 static bool
00527 RevCompRegionInfoPointer( const RegionInfo * const &l,
00528 const RegionInfo * const &r )
00529 {
00530 bool b = ( l->GetNumOfPixels() > r->GetNumOfPixels());
00531 if ( l->GetNumOfPixels() == r->GetNumOfPixels()) {
00532 int lx, ly, rx, ry;
00533 l->GetMin( lx, ly );
00534 r->GetMin( rx, ry );
00535 b = ( ly > ry );
00536 }
00537 return b;
00538 }
00539
00540 void
00541 FillFrame( RegionInfo *ri, const DstT fill_value )
00542 {
00543 #if 0
00544 while ( ri->GetNumOfRasterSegments() > 0 ) {
00545 RasterSegment *rs;
00546 ri->Pop( rs );
00547 DstT *sp = dst_frame + rs->LeftX() + rs->Y() * width;
00548 for ( int i = 0; i < rs->RightX() - rs->LeftX() + 1; i++ ) {
00549 *sp++ = fill_value;
00550 }
00551 }
00552 #endif
00553 RSPList rspl = ri->GetRasterSegmentList();
00554 for ( RSPIterator rspi = rspl.begin(); rspi != rspl.end(); rspi++ ) {
00555 RasterSegment *rs = *rspi;
00556 int lx = rs->LeftX();
00557 int rx = rs->RightX();
00558 int y = rs->Y();
00559 DstT *sp = dst_frame + lx + y * width;
00560 for ( int i = 0; i < ( rx - lx + 1 ); i++ ) {
00561 *sp++ = fill_value;
00562 }
00563 }
00564 }
00565
00566 public:
00567
00568 inline int
00569 GetNumOfRegions( void ) const
00570 {
00571 return num_of_regions;
00572 }
00573
00574 inline int
00575 GetNumOfResultRegions( void ) const
00576 {
00577 return num_of_result_regions;
00578 }
00579
00580 inline RegionInfo *
00581 GetResultRegionInfo( const int num ) const
00582 {
00583 return result_region_info[ num ];
00584 }
00585
00586 Labeling()
00587 {
00588 raster_segment_list = 0;
00589 region_info_list.clear();
00590 result_region_info.clear();
00591 }
00592
00593 virtual ~Labeling()
00594 {
00595 for ( RIPIterator ripi = region_info_list.begin();
00596 ripi != region_info_list.end(); ripi++ ) {
00597 RegionInfo *ri = *ripi;
00598 delete ri;
00599 }
00600 region_info_list.erase( region_info_list.begin(),
00601 region_info_list.end());
00602 result_region_info.clear();
00603 }
00604
00605 #define CHECK_FOR_PHASE1 0
00606 #define CHECK_FOR_PHASE2 0
00607
00608 int
00609 Exec( SrcT *target, DstT *result,
00610 int target_width, int target_height,
00611 const bool is_sort_region,
00612 const int region_size_min )
00613 {
00614 src_frame = target;
00615 dst_frame = result;
00616
00617 width = target_width;
00618 height = target_height;
00619 total_num = width * height;
00620
00621
00622
00623 for ( RIPIterator ripi = region_info_list.begin();
00624 ripi != region_info_list.end(); ripi++ ) {
00625 RegionInfo *ri = *ripi;
00626 delete ri;
00627 }
00628 region_info_list.erase( region_info_list.begin(),
00629 region_info_list.end());
00630 result_region_info.clear();
00631
00632 raster_segment_list = new RSPList[ height ];
00633 num_of_raster_segments = 0;
00634
00635
00636
00637 SrcT *p = src_frame;
00638
00639 #if ( CLEAR_DST_BUFFER || CLEAR_ALL_DST_BUFFER )
00640 DstT *q = dst_frame;
00641 #endif
00642 if ( src_frame != reinterpret_cast<SrcT *>( dst_frame )) {
00643 #if CLEAR_ALL_DST_BUFFER
00644 for ( int i = 0; i < width * height; i++ ) {
00645 *q++ = 0;
00646 }
00647 #endif
00648 for ( int y = 0; y < height; y++ ) {
00649 int lx = 0;
00650 int current_src_value = 0;
00651 for ( int x = 0; x < width; x++ ) {
00652 if ( *p != current_src_value ) {
00653 if ( current_src_value != 0 ) {
00654 RegisterSegment( lx, x - 1, y, current_src_value );
00655 }
00656 current_src_value = *p;
00657 lx = x;
00658 }
00659 #if ( CLEAR_DST_BUFFER && !CLEAR_ALL_DST_BUFFER )
00660 if ( *p == 0 ) {
00661 *q = 0;
00662 }
00663 q++;
00664 #endif
00665 p++;
00666 }
00667 if ( current_src_value != 0 ) {
00668 RegisterSegment( lx, width - 1, y, current_src_value );
00669 }
00670 }
00671 } else {
00672 for ( int y = 0; y < height; y++ ) {
00673 int lx = 0;
00674 int current_src_value = 0;
00675 for ( int x = 0; x < width; x++ ) {
00676 if ( *p != current_src_value ) {
00677 if ( current_src_value != 0 ) {
00678 RegisterSegment( lx, x - 1, y, current_src_value );
00679 }
00680 current_src_value = *p;
00681 lx = x;
00682 }
00683 p++;
00684 }
00685 if ( current_src_value != 0 ) {
00686 RegisterSegment( lx, width - 1, y, current_src_value );
00687 }
00688 }
00689 }
00690
00691 #if CHECK_FOR_PHASE1
00692 for ( int y = 0; y < height; y++ ) {
00693 cout << y << ":" << raster_segment_list[ y ].size() << endl;
00694 RSPList *rspl_p = &raster_segment_list[ y ];
00695 RSPIterator i;
00696 for ( i = rspl_p->begin(); i != rspl_p->end(); i++ ) {
00697 RasterSegment *rs = *i;
00698 cout << *rs;
00699 }
00700 }
00701 cout << "num_of_raster_segments: " << num_of_raster_segments << endl;
00702 #endif
00703
00704
00705
00706 region_info_list.clear();
00707 num_of_regions = 0;
00708
00709
00710
00711 for ( int y = 0; y < height; y++ ) {
00712 RSPList *rspl_p = &raster_segment_list[ y ];
00713 while ( rspl_p->size() > 0 ) {
00714 RSPIterator rspi = rspl_p->begin();
00715 RasterSegment *rs = *rspi;
00716 rspl_p->erase( rspi );
00717
00718 RegionInfo *rip = ConnectRasterSegment( rs,
00719 num_of_regions + 1 );
00720 region_info_list.push_back( rip );
00721 num_of_regions++;
00722 }
00723 }
00724
00725 #if CHECK_FOR_PHASE2
00726 for ( int y = 0; y < height; y++ ) {
00727 if ( !raster_segment_list[ y ].empty()) {
00728 cout << "mmmm" << y << endl;
00729 }
00730 }
00731
00732 int n_p = 0;
00733 for ( RIPIterator ripi = region_info_list.begin();
00734 ripi != region_info_list.end(); ripi++ ) {
00735 RegionInfo *ri = *ripi;
00736 n_p += ri->GetNumOfPixels();
00737 while ( ri->GetNumOfRasterSegments() > 0 ) {
00738 RasterSegment *rs;
00739 ri->Pop( rs );
00740 cout << *rs;
00741 }
00742 }
00743 cout << "num_of_pixels: " << n_p << endl;
00744 cout << "num_of_regions: " << num_of_regions << endl;
00745 #endif
00746
00747
00748
00749
00750 result_region_info.resize( num_of_regions );
00751 int n = 0;
00752 for ( RIPIterator ripi = region_info_list.begin();
00753 ripi != region_info_list.end(); ripi++ ) {
00754 result_region_info[ n ] = *ripi;
00755 n++;
00756 }
00757
00758 if ( is_sort_region ) {
00759
00760
00761 sort( result_region_info.begin(), result_region_info.end(),
00762 RevCompRegionInfoPointer );
00763 }
00764
00765
00766
00767 if ( is_sort_region && region_size_min > 0 ) {
00768 int n = 0;
00769 while ( n < num_of_regions
00770 && result_region_info[ n ]->GetNumOfPixels()
00771 >= region_size_min ) {
00772 result_region_info[ n ]->SetResult( n + 1 );
00773 n++;
00774 }
00775 num_of_result_regions = n;
00776 for ( int i = n; i < num_of_regions; i++ ) {
00777 result_region_info[ i ]->SetResult( 0 );
00778 }
00779 } else {
00780 for ( int i = 0; i < num_of_regions; i++ ) {
00781 result_region_info[ i ]->SetResult( i + 1 );
00782 }
00783 num_of_result_regions = num_of_regions;
00784 }
00785
00786
00787
00788
00789 for ( int i = 0; i < num_of_regions; i++ ) {
00790 RegionInfo *ri = result_region_info[ i ];
00791 FillFrame( ri, ri->GetResult());
00792 }
00793
00794
00795
00796 delete [] raster_segment_list;
00797
00798 return 0;
00799 }
00800 };
00801
00802 typedef Labeling<unsigned char,short> LabelingBS;
00803 typedef Labeling<short,short> LabelingSS;
00804 typedef Labeling<unsigned char,short>::RegionInfo RegionInfoBS;
00805 typedef Labeling<short,short>::RegionInfo RegionInfoSS;
00806
00807 #endif // __LABELING_H__