labeling.h
説明を見る。
1 //
2 // Copyright (c) 2003-2011, MIST Project, Nagoya University
3 // All rights reserved.
4 //
5 // Redistribution and use in source and binary forms, with or without modification,
6 // are permitted provided that the following conditions are met:
7 //
8 // 1. Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 //
11 // 2. Redistributions in binary form must reproduce the above copyright notice,
12 // this list of conditions and the following disclaimer in the documentation
13 // and/or other materials provided with the distribution.
14 //
15 // 3. Neither the name of the Nagoya University nor the names of its contributors
16 // may be used to endorse or promote products derived from this software
17 // without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
21 // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
22 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25 // IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
26 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 //
28 
38 
39 #ifndef __INCLUDE_MIST_LABELING__
40 #define __INCLUDE_MIST_LABELING__
41 
42 #ifndef __INCLUDE_MIST_H__
43 #include "../mist.h"
44 #endif
45 
46 #ifndef __INCLUDE_MIST_LIMITS__
47 #include "../limits.h"
48 #endif
49 
50 #include <vector>
51 #include <list>
52 
53 
54 
55 // mist名前空間の始まり
56 _MIST_BEGIN
57 
58 
59 namespace __labeling_controller__
60 {
61  template < class T > struct default_label_num2
62  {
63  _MIST_CONST( size_t, value, 2560 );
64  };
65  template < > struct default_label_num2< char >
66  {
67  _MIST_CONST( size_t, value, 127 );
68  };
69  template < > struct default_label_num2< signed char >
70  {
71  _MIST_CONST( size_t, value, 127 );
72  };
73  template < > struct default_label_num2< unsigned char >
74  {
75  _MIST_CONST( size_t, value, 255 );
76  };
77 
78  template < class T > struct default_label_num3
79  {
80  _MIST_CONST( size_t, value, 10000 );
81  };
82  template < > struct default_label_num3< char >
83  {
84  _MIST_CONST( size_t, value, 127 );
85  };
86  template < > struct default_label_num3< signed char >
87  {
88  _MIST_CONST( size_t, value, 127 );
89  };
90  template < > struct default_label_num3< unsigned char >
91  {
92  _MIST_CONST( size_t, value, 255 );
93  };
94 
95 
96  template < int nc >
97  struct neighbors
98  {
99  _MIST_CONST( size_t, array_num, 13 );
100 
101  template < class Array, class Vector >
102  static inline typename Array::size_type neighbor( Array &in, const Vector &T, typename Vector::value_type *L,
103  const typename Array::size_type i, const typename Array::size_type j, const typename Array::size_type k,
104  const typename Array::size_type w, const typename Array::size_type h, const typename Array::size_type d )
105  {
106  typedef typename Array::size_type size_type;
107 
108  L[ 0 ] = k > 0 ? T[ static_cast< size_type >( in( i , j , k - 1 ) ) ] : 0;
109  L[ 1 ] = j > 0 ? T[ static_cast< size_type >( in( i , j - 1, k ) ) ] : 0;
110  L[ 2 ] = i > 0 ? T[ static_cast< size_type >( in( i - 1, j , k ) ) ] : 0;
111  L[ 3 ] = j > 0 && k > 0 ? T[ static_cast< size_type >( in( i , j - 1, k - 1 ) ) ] : 0;
112  L[ 4 ] = i > 0 && k > 0 ? T[ static_cast< size_type >( in( i - 1, j , k - 1 ) ) ] : 0;
113  L[ 5 ] = i + 1 < w && k > 0 ? T[ static_cast< size_type >( in( i + 1, j , k - 1 ) ) ] : 0;
114  L[ 6 ] = j + 1 < h && k > 0 ? T[ static_cast< size_type >( in( i , j + 1, k - 1 ) ) ] : 0;
115  L[ 7 ] = i > 0 && j > 0 ? T[ static_cast< size_type >( in( i - 1, j - 1, k ) ) ] : 0;
116  L[ 8 ] = i + 1 < w && j > 0 ? T[ static_cast< size_type >( in( i + 1, j - 1, k ) ) ] : 0;
117  L[ 9 ] = i > 0 && j > 0 && k > 0 ? T[ static_cast< size_type >( in( i - 1, j - 1, k - 1 ) ) ] : 0;
118  L[ 10 ] = i + 1 < w && j > 0 && k > 0 ? T[ static_cast< size_type >( in( i + 1, j - 1, k - 1 ) ) ] : 0;
119  L[ 11 ] = i > 0 && j + 1 < h && k > 0 ? T[ static_cast< size_type >( in( i - 1, j + 1, k - 1 ) ) ] : 0;
120  L[ 12 ] = i + 1 < w && j + 1 < h && k > 0 ? T[ static_cast< size_type >( in( i + 1, j + 1, k - 1 ) ) ] : 0;
121 
122  return( 0 );
123  }
124  };
125 
126  template < >
127  struct neighbors< 18 >
128  {
129  _MIST_CONST( size_t, array_num, 9 );
130 
131  template < class Array, class Vector >
132  static inline typename Array::size_type neighbor( Array &in, const Vector &T, typename Vector::value_type *L,
133  const typename Array::size_type i, const typename Array::size_type j, const typename Array::size_type k,
134  const typename Array::size_type w, const typename Array::size_type h, const typename Array::size_type d )
135  {
136  typedef typename Array::size_type size_type;
137 
138  L[ 0 ] = k > 0 ? T[ static_cast< size_type >( in( i , j , k - 1 ) ) ] : 0;
139  L[ 1 ] = j > 0 ? T[ static_cast< size_type >( in( i , j - 1, k ) ) ] : 0;
140  L[ 2 ] = i > 0 ? T[ static_cast< size_type >( in( i - 1, j , k ) ) ] : 0;
141  L[ 3 ] = j > 0 && k > 0 ? T[ static_cast< size_type >( in( i , j - 1, k - 1 ) ) ] : 0;
142  L[ 4 ] = i > 0 && k > 0 ? T[ static_cast< size_type >( in( i - 1, j , k - 1 ) ) ] : 0;
143  L[ 5 ] = i + 1 < w && k > 0 ? T[ static_cast< size_type >( in( i + 1, j , k - 1 ) ) ] : 0;
144  L[ 6 ] = j + 1 < h && k > 0 ? T[ static_cast< size_type >( in( i , j + 1, k - 1 ) ) ] : 0;
145  L[ 7 ] = i > 0 && j > 0 ? T[ static_cast< size_type >( in( i - 1, j - 1, k ) ) ] : 0;
146  L[ 8 ] = i + 1 < w && j > 0 ? T[ static_cast< size_type >( in( i + 1, j - 1, k ) ) ] : 0;
147 
148  return( 0 );
149  }
150  };
151 
152  template < >
153  struct neighbors< 6 >
154  {
155  _MIST_CONST( size_t, array_num, 3 );
156 
157  template < class Array, class Vector >
158  static inline typename Array::size_type neighbor( Array &in, const Vector &T, typename Vector::value_type *L,
159  const typename Array::size_type i, const typename Array::size_type j, const typename Array::size_type k,
160  const typename Array::size_type w, const typename Array::size_type h, const typename Array::size_type d )
161  {
162  typedef typename Array::size_type size_type;
163 
164  L[ 0 ] = k > 0 ? T[ static_cast< size_type >( in( i , j , k - 1 ) ) ] : 0;
165  L[ 1 ] = j > 0 ? T[ static_cast< size_type >( in( i , j - 1, k ) ) ] : 0;
166  L[ 2 ] = i > 0 ? T[ static_cast< size_type >( in( i - 1, j , k ) ) ] : 0;
167 
168  return( 0 );
169  }
170  };
171 
172  template < >
173  struct neighbors< 8 >
174  {
175  _MIST_CONST( size_t, array_num, 4 );
176 
177  template < class Array, class Vector >
178  static inline typename Array::size_type neighbor( Array &in, const Vector &T, typename Vector::value_type *L,
179  const typename Array::size_type i, const typename Array::size_type j, const typename Array::size_type /* k */,
180  const typename Array::size_type w, const typename Array::size_type /* h */, const typename Array::size_type /* d */ )
181  {
182  typedef typename Array::size_type size_type;
183 
184  L[ 0 ] = i > 0 && j > 0 ? T[ static_cast< size_type >( in( i - 1, j - 1 ) ) ] : 0;
185  L[ 1 ] = j > 0 ? T[ static_cast< size_type >( in( i , j - 1 ) ) ] : 0;
186  L[ 2 ] = i + 1 < w && j > 0 ? T[ static_cast< size_type >( in( i + 1, j - 1 ) ) ] : 0;
187  L[ 3 ] = i > 0 ? T[ static_cast< size_type >( in( i - 1, j ) ) ] : 0;
188 
189  return( 0 );
190  }
191  };
192 
193  template < >
194  struct neighbors< 4 >
195  {
196  _MIST_CONST( size_t, array_num, 2 );
197 
198  template < class Array, class Vector >
199  static inline typename Array::size_type neighbor( Array &in, const Vector &T, typename Vector::value_type *L,
200  const typename Array::size_type i, const typename Array::size_type j, const typename Array::size_type k,
201  const typename Array::size_type w, const typename Array::size_type h, const typename Array::size_type d )
202  {
203  typedef typename Array::size_type size_type;
204 
205  L[ 0 ] = j > 0 ? T[ static_cast< size_type >( in( i , j - 1 ) ) ] : 0;
206  L[ 1 ] = i > 0 ? T[ static_cast< size_type >( in( i - 1, j ) ) ] : 0;
207 
208  return( 0 );
209  }
210  };
211 
212 
213  template < class Array, class neighbor, class Functor >
214  typename Array::size_type labeling( Array &in, typename Array::size_type label_max, const neighbor /* dmy */, Functor f )
215  {
216  typedef typename Array::size_type size_type;
217  typedef typename Array::difference_type difference_type;
218  typedef typename Array::value_type value_type;
219 
220 // typedef difference_type label_value_type;
221 // typedef size_type label_value_type;
222  typedef unsigned int label_value_type;
223 
224  typedef std::vector< label_value_type >::value_type vector_label_value_type;
225  typedef std::list< label_value_type > label_list_type;
226 
227  size_type label_num = 0;
228  size_type i, j, k, l, count;
229 
230  std::vector< label_value_type > T;
231  std::vector< label_list_type > TBL;
232  label_value_type L[ neighbor::array_num ];
233  const size_type width = in.width( );
234  const size_type height = in.height( );
235  const size_type depth = in.depth( );
236 
237  T.reserve( label_max );
238  T.push_back( 0 ); // T[ 0 ]
239  TBL.push_back( label_list_type( ) ); // T[ 0 ]
240 
241  const bool bprogress1 = depth == 1;
242  const bool bprogress2 = depth > 1;
243 
244  if( is_float< value_type >::value )
245  {
246  label_max = type_limits< size_type >::maximum( );
247  }
248  else
249  {
250  label_max = static_cast< size_type >( type_limits< value_type >::maximum( ) );
251  }
252 
253  f( 0.0 );
254 
255  for( k = 0 ; k < depth ; k++ )
256  {
257  for( j = 0 ; j < height ; j++ )
258  {
259  for( i = 0 ; i < width ; i++ )
260  {
261  // 0画素はラベリングしない
262  if( in( i, j, k ) == 0 )
263  {
264  continue;
265  }
266 
267  // 操作済みの要素のラベルを取得する
268  neighbor::neighbor( in, T, L, i, j, k, width, height, depth );
269 
270  // 近傍で最小のラベル番号を持つものを取得し，ラベル番号が0で無い物の数を数え上げる
271  label_value_type L1 = static_cast< label_value_type >( label_max );
272  for( l = 0, count = 0 ; l < neighbor::array_num ; l++ )
273  {
274  if( L[ l ] > 0 )
275  {
276  if( L1 != L[ l ] )
277  {
278  count++;
279  }
280  if( L1 > L[ l ] )
281  {
282  L1 = L[ l ];
283  }
284  }
285  }
286 
287  if( count == 0 )
288  {
289  // 近傍に，すでに割り当てられているラベルは存在しないため，新規にラベルを割り当てる
290  // 出力ラベル値が出力データ型の最大値を超えなければ，ラベル数を更新する
291  if( label_num < label_max )
292  {
293  label_num++;
294  }
295 
296  T.push_back( static_cast< label_value_type >( label_num ) );
297 
298  label_list_type ll;
299  ll.push_back( static_cast< label_value_type >( label_num ) );
300  TBL.push_back( ll );
301 
302  in( i, j, k ) = static_cast< value_type >( label_num );
303  }
304  else if( count == 1 )
305  {
306  // 近傍に，割り当てられているラベルが1つしか存在しないため，そのラベルを割り当てる
307  in( i, j, k ) = static_cast< value_type >( L1 );
308  }
309  else
310  {
311  in( i, j, k ) = static_cast< value_type >( L1 );
312 
313  // 複数のラベルが結合するため，テーブルを修正する
314  for( l = 0 ; l < neighbor::array_num ; l++ )
315  {
316  label_value_type L0 = L[ l ];
317  if( T[ L0 ] != L1 )
318  {
319  typename label_list_type::iterator ite = TBL[ L0 ].begin( );
320  typename label_list_type::iterator eite = TBL[ L0 ].end( );
321 
322  for( ; ite != eite ; ++ite )
323  {
324  T[ *ite ] = static_cast< vector_label_value_type >( L1 );
325  }
326 
327  //label_list_type &TBL1 = TBL[ L0 ];
328  TBL[ L1 ].insert( TBL[ L1 ].end( ), TBL[ L0 ].begin( ), TBL[ L0 ].end( ) );
329  TBL[ L0 ].clear( );
330  }
331  }
332  }
333  }
334 
335  if( bprogress1 )
336  {
337  f( static_cast< double >( j + 1 ) / static_cast< double >( height ) * 100.0 );
338  }
339  }
340 
341  if( bprogress2 )
342  {
343  f( static_cast< double >( k + 1 ) / static_cast< double >( depth ) * 100.0 );
344  }
345  }
346 
347  f( 100.0 );
348 
349  // ラベルの振り直しを行う
350  size_type *NT = new size_type[ label_num + 1 ];
351  for( i = 0 ; i <= label_num ; i++ )
352  {
353  NT[ i ] = 0;
354  }
355 
356  // 使用しているラベルをチェックする
357  for( i = 1 ; i <= label_num ; i++ )
358  {
359  NT[ T[ i ] ] = 1;
360  }
361 
362  // 使用しているラベルをチェックする
363  for( i = 1, count = 1 ; i <= label_num ; i++ )
364  {
365  if( NT[ i ] != 0 )
366  {
367  NT[ i ] = count++;
368  }
369  }
370 
371  label_num = 0;
372  for( i = 0 ; i < in.size( ) ; i++ )
373  {
374  if( in[ i ] == 0 )
375  {
376  continue;
377  }
378 
379  size_type label = NT[ T[ static_cast< size_type >( in[ i ] ) ] ];
380  in[ i ] = static_cast< value_type >( label );
381  if( label_num < label )
382  {
383  label_num = label;
384  }
385  }
386 
387  f( 100.1 );
388 
389  delete [] NT;
390 
391  return( label_num );
392  }
393 }
394 
395 
396 
397 
405 
406 
425 template < class T1, class T2, class Allocator1, class Allocator2, class Functor >
426 typename array2< T2, Allocator2 >::size_type labeling4( const array2< T1, Allocator1 > &in, array2< T2, Allocator2 > &out, typename array2< T2, Allocator2 >::size_type max_label, Functor f )
427 {
428  typedef typename array2< T2, Allocator2 >::size_type size_type;
429  typedef typename array2< T2, Allocator2 >::value_type value_type;
430 
431  if( max_label == 0 )
432  {
433  if( is_float< value_type >::value )
434  {
435  max_label = type_limits< size_type >::maximum( );
436  }
437  else
438  {
439  max_label = static_cast< size_type >( type_limits< value_type >::maximum( ) );
440  }
441  }
442 
443  out.resize( in.size1( ), in.size2( ) );
444  out.reso1( in.reso1( ) );
445  out.reso2( in.reso2( ) );
446 
447  for( size_type i = 0 ; i < in.size( ) ; i++ )
448  {
449  out[ i ] = static_cast< value_type >( in[ i ] > 0 ? 1 : 0 );
450  }
451  return( __labeling_controller__::labeling( out, max_label, __labeling_controller__::neighbors< 4 >( ), f ) );
452 }
453 
454 
472 template < class T1, class T2, class Allocator1, class Allocator2 >
473 typename array2< T2, Allocator2 >::size_type labeling4( const array2< T1, Allocator1 > &in, array2< T2, Allocator2 > &out, typename array2< T2, Allocator2 >::size_type max_label = __labeling_controller__::default_label_num2< T2 >::value )
474 {
475  return( labeling4( in, out, max_label, __mist_dmy_callback__( ) ) );
476 }
477 
478 
497 template < class T1, class T2, class Allocator1, class Allocator2, class Functor >
498 typename array2< T2, Allocator2 >::size_type labeling8( const array2< T1, Allocator1 > &in, array2< T2, Allocator2 > &out, typename array2< T2, Allocator2 >::size_type max_label, Functor f )
499 {
500  typedef typename array2< T2, Allocator2 >::size_type size_type;
501  typedef typename array2< T2, Allocator2 >::value_type value_type;
502 
503  if( max_label == 0 )
504  {
505  if( is_float< value_type >::value )
506  {
507  max_label = type_limits< size_type >::maximum( );
508  }
509  else
510  {
511  max_label = static_cast< size_type >( type_limits< value_type >::maximum( ) );
512  }
513  }
514 
515  out.resize( in.size1( ), in.size2( ) );
516  out.reso1( in.reso1( ) );
517  out.reso2( in.reso2( ) );
518 
519  for( size_type i = 0 ; i < in.size( ) ; i++ )
520  {
521  out[ i ] = static_cast< value_type >( in[ i ] > 0 ? 1 : 0 );
522  }
523  return( __labeling_controller__::labeling( out, max_label, __labeling_controller__::neighbors< 8 >( ), f ) );
524 }
525 
526 
544 template < class T1, class T2, class Allocator1, class Allocator2 >
545 inline typename array2< T2, Allocator2 >::size_type labeling8( const array2< T1, Allocator1 > &in, array2< T2, Allocator2 > &out, typename array2< T2, Allocator2 >::size_type max_label = __labeling_controller__::default_label_num2< T2 >::value )
546 {
547  return( labeling8( in, out, max_label, __mist_dmy_callback__( ) ) );
548 }
549 
550 
569 template < class T1, class T2, class Allocator1, class Allocator2, class Functor >
570 typename array3< T2, Allocator2 >::size_type labeling6( const array3< T1, Allocator1 > &in, array3< T2, Allocator2 > &out, typename array3< T2, Allocator2 >::size_type max_label, Functor f )
571 {
572  typedef typename array3< T2, Allocator2 >::size_type size_type;
573  typedef typename array3< T2, Allocator2 >::value_type value_type;
574 
575  if( max_label == 0 )
576  {
577  if( is_float< value_type >::value )
578  {
579  max_label = type_limits< size_type >::maximum( );
580  }
581  else
582  {
583  max_label = static_cast< size_type >( type_limits< value_type >::maximum( ) );
584  }
585  }
586 
587  out.resize( in.size1( ), in.size2( ), in.size3( ) );
588  out.reso1( in.reso1( ) );
589  out.reso2( in.reso2( ) );
590  out.reso3( in.reso3( ) );
591 
592  for( size_type i = 0 ; i < in.size( ) ; i++ )
593  {
594  out[ i ] = static_cast< value_type >( in[ i ] > 0 ? 1 : 0 );
595  }
596  return( __labeling_controller__::labeling( out, max_label, __labeling_controller__::neighbors< 6 >( ), f ) );
597 }
598 
616 template < class T1, class T2, class Allocator1, class Allocator2 >
617 inline typename array3< T2, Allocator2 >::size_type labeling6( const array3< T1, Allocator1 > &in, array3< T2, Allocator2 > &out, typename array3< T2, Allocator2 >::size_type max_label = __labeling_controller__::default_label_num3< T2 >::value )
618 {
619  return( labeling6( in, out, max_label, __mist_dmy_callback__( ) ) );
620 }
621 
622 
641 template < class T1, class T2, class Allocator1, class Allocator2, class Functor >
642 typename array3< T2, Allocator2 >::size_type labeling18( const array3< T1, Allocator1 > &in, array3< T2, Allocator2 > &out, typename array3< T2, Allocator2 >::size_type max_label, Functor f )
643 {
644  typedef typename array3< T2, Allocator2 >::size_type size_type;
645  typedef typename array3< T2, Allocator2 >::value_type value_type;
646 
647  if( max_label == 0 )
648  {
649  if( is_float< value_type >::value )
650  {
651  max_label = type_limits< size_type >::maximum( );
652  }
653  else
654  {
655  max_label = static_cast< size_type >( type_limits< value_type >::maximum( ) );
656  }
657  }
658 
659  out.resize( in.size1( ), in.size2( ), in.size3( ) );
660  out.reso1( in.reso1( ) );
661  out.reso2( in.reso2( ) );
662  out.reso3( in.reso3( ) );
663 
664  for( size_type i = 0 ; i < in.size( ) ; i++ )
665  {
666  out[ i ] = static_cast< value_type >( in[ i ] > 0 ? 1 : 0 );
667  }
668  return( __labeling_controller__::labeling( out, max_label, __labeling_controller__::neighbors< 18 >( ), f ) );
669 }
670 
688 template < class T1, class T2, class Allocator1, class Allocator2 >
689 inline typename array3< T2, Allocator2 >::size_type labeling18( const array3< T1, Allocator1 > &in, array3< T2, Allocator2 > &out, typename array3< T2, Allocator2 >::size_type max_label = __labeling_controller__::default_label_num3< T2 >::value )
690 {
691  return( labeling18( in, out, max_label, __mist_dmy_callback__( ) ) );
692 }
693 
694 
713 template < class T1, class T2, class Allocator1, class Allocator2, class Functor >
714 typename array3< T2, Allocator2 >::size_type labeling26( const array3< T1, Allocator1 > &in, array3< T2, Allocator2 > &out, typename array3< T2, Allocator2 >::size_type max_label, Functor f )
715 {
716  typedef typename array3< T2, Allocator2 >::size_type size_type;
717  typedef typename array3< T2, Allocator2 >::value_type value_type;
718 
719  if( max_label == 0 )
720  {
721  if( is_float< value_type >::value )
722  {
723  max_label = type_limits< size_type >::maximum( );
724  }
725  else
726  {
727  max_label = static_cast< size_type >( type_limits< value_type >::maximum( ) );
728  }
729  }
730 
731  out.resize( in.size1( ), in.size2( ), in.size3( ) );
732  out.reso1( in.reso1( ) );
733  out.reso2( in.reso2( ) );
734  out.reso3( in.reso3( ) );
735 
736  for( size_type i = 0 ; i < in.size( ) ; i++ )
737  {
738  out[ i ] = static_cast< value_type >( in[ i ] > 0 ? 1 : 0 );
739  }
740  return( __labeling_controller__::labeling( out, max_label, __labeling_controller__::neighbors< 26 >( ), f ) );
741 }
742 
743 
759 template < class T1, class T2, class Allocator1, class Allocator2 >
760 inline typename array3< T2, Allocator2 >::size_type labeling26( const array3< T1, Allocator1 > &in, array3< T2, Allocator2 > &out, typename array3< T2, Allocator2 >::size_type max_label = __labeling_controller__::default_label_num3< T2 >::value )
761 {
762  return( labeling26( in, out, max_label, __mist_dmy_callback__( ) ) );
763 }
764 
765 
766 
767 
782 template < class T1, class T2, class Allocator1, class Allocator2 >
783 void maximum_region(
784  const array2< T1, Allocator1 > &in,
785  array2< T2, Allocator2 > &out,
786  typename array2< T1, Allocator1 >::size_type sx,
787  typename array2< T1, Allocator1 >::size_type ex,
788  typename array2< T1, Allocator1 >::size_type sy,
789  typename array2< T1, Allocator1 >::size_type ey,
790  typename array2< T1, Allocator1 >::size_type max_label = __labeling_controller__::default_label_num2< T2 >::value
791  )
792 {
793  typedef typename array2< T1, Allocator1 >::size_type size_type;
794  typedef typename array2< T1, Allocator1 >::difference_type difference_type;
795 
796  array2< size_type > tmp;
797  size_type i, j;
798 
799  size_type label_num = mist::labeling8( in, tmp, max_label );
800 
801  // 指定された範囲内の最大ラベルを探索
802  sx = sx < 0 ? 0 : sx;
803  sy = sy < 0 ? 0 : sy;
804  sx = sx < in.width( ) ? sx : in.width( ) - 1;
805  sy = sy < in.height( ) ? sy : in.height( ) - 1;
806 
807  ex = ex < 0 ? 0 : ex;
808  ey = ey < 0 ? 0 : ey;
809  ex = ex < in.width( ) ? ex : in.width( ) - 1;
810  ey = ey < in.height( ) ? ey : in.height( ) - 1;
811 
812  size_type *menseki = new size_type[ label_num + 1 ];
813  for( i = 0 ; i <= label_num ; i++ )
814  {
815  menseki[ i ] = 0;
816  }
817 
818  for( j = sy ; j <= ey ; j++ )
819  {
820  for( i = sx ; i <= ex ; i++ )
821  {
822  menseki[ tmp( i, j ) ]++;
823  }
824  }
825 
826  max_label = 1;
827  for( i = 2 ; i <= label_num ; i++ )
828  {
829  max_label = menseki[ i ] > menseki[ max_label ] ? i : max_label;
830  }
831  delete [] menseki;
832 
833  out.resize( in.size1( ), in.size2( ) );
834  out.reso1( in.reso1( ) );
835  out.reso2( in.reso2( ) );
836 
837  for( i = 0 ; i < out.size( ) ; i++ )
838  {
839  out[ i ] = tmp[ i ] == max_label ? 1 : 0;
840  }
841 }
842 
843 
856 template < class T1, class T2, class Allocator1, class Allocator2 >
857 void maximum_region( const array2< T1, Allocator1 > &in, array2< T2, Allocator2 > &out, typename array2< T1, Allocator1 >::size_type max_label = __labeling_controller__::default_label_num2< T2 >::value )
858 {
859  maximum_region( in, out, 0, in.width( ) - 1, 0, in.height( ) - 1, max_label );
860 }
861 
862 
863 
882 template < class T1, class T2, class Allocator1, class Allocator2 >
883 void maximum_region(
884  const array3< T1, Allocator1 > &in,
885  array3< T2, Allocator2 > &out,
886  typename array3< T1, Allocator1 >::size_type sx,
887  typename array3< T1, Allocator1 >::size_type ex,
888  typename array3< T1, Allocator1 >::size_type sy,
889  typename array3< T1, Allocator1 >::size_type ey,
890  typename array3< T1, Allocator1 >::size_type sz,
891  typename array3< T1, Allocator1 >::size_type ez,
892  typename array3< T1, Allocator1 >::size_type max_label = __labeling_controller__::default_label_num3< T2 >::value
893  )
894 {
895  typedef typename array3< T1, Allocator1 >::size_type size_type;
896  typedef typename array3< T1, Allocator1 >::difference_type difference_type;
897 
898  array3< size_type > tmp;
899  size_type i, j, k;
900 
901  size_type label_num = mist::labeling26( in, tmp, max_label );
902 
903  // 指定された範囲内の最大ラベルを探索
904  sx = sx < 0 ? 0 : sx;
905  sy = sy < 0 ? 0 : sy;
906  sz = sz < 0 ? 0 : sz;
907  sx = sx < in.width( ) ? sx : in.width( ) - 1;
908  sy = sy < in.height( ) ? sy : in.height( ) - 1;
909  sz = sz < in.depth( ) ? sz : in.depth( ) - 1;
910 
911  ex = ex < 0 ? 0 : ex;
912  ey = ey < 0 ? 0 : ey;
913  ez = ez < 0 ? 0 : ez;
914  ex = ex < in.width( ) ? ex : in.width( ) - 1;
915  ey = ey < in.height( ) ? ey : in.height( ) - 1;
916  ez = ez < in.depth( ) ? ez : in.depth( ) - 1;
917 
918  size_type *menseki = new size_type[ label_num + 1 ];
919  for( i = 0 ; i <= label_num ; i++ )
920  {
921  menseki[ i ] = 0;
922  }
923 
924  for( k = sz ; k <= ez ; k++ )
925  {
926  for( j = sy ; j <= ey ; j++ )
927  {
928  for( i = sx ; i <= ex ; i++ )
929  {
930  menseki[ tmp( i, j, k ) ]++;
931  }
932  }
933  }
934 
935  max_label = 1;
936  for( i = 2 ; i <= label_num ; i++ )
937  {
938  max_label = menseki[ i ] > menseki[ max_label ] ? i : max_label;
939  }
940  delete [] menseki;
941 
942  out.resize( in.size1( ), in.size2( ), in.size3( ) );
943  out.reso1( in.reso1( ) );
944  out.reso2( in.reso2( ) );
945  out.reso3( in.reso3( ) );
946 
947  for( i = 0 ; i < out.size( ) ; i++ )
948  {
949  out[ i ] = static_cast< typename array3< T2, Allocator2 >::value_type >( tmp[ i ] == max_label ? 1 : 0 );
950  }
951 }
952 
953 
966 template < class T1, class T2, class Allocator1, class Allocator2 >
967 void maximum_region( const array3< T1, Allocator1 > &in, array3< T2, Allocator2 > &out, typename array3< T1, Allocator1 >::size_type max_label = __labeling_controller__::default_label_num3< T2 >::value )
968 {
969  maximum_region( in, out, 0, in.width( ) - 1, 0, in.height( ) - 1, 0, in.depth( ) - 1, max_label );
970 }
971 
972 
973 
974 
986 template < class T1, class T2, class Allocator1, class Allocator2 >
987 void remove_hole_region( const array2< T1, Allocator1 > &in, array2< T2, Allocator2 > &out, const bool include_corner_labels, typename array2< T1, Allocator1 >::size_type max_label = __labeling_controller__::default_label_num2< T2 >::value )
988 {
989  typedef typename array2< T1, Allocator1 >::size_type size_type;
990  typedef typename array2< T1, Allocator1 >::difference_type difference_type;
991 
992  array2< size_type > tmp;
993  size_type i;
994 
995  tmp.resize( in.size1( ), in.size2( ) );
996  tmp.reso1( in.reso1( ) );
997  tmp.reso2( in.reso2( ) );
998 
999  // 反転した画像を作成する
1000  for( i = 0 ; i < tmp.size( ) ; i++ )
1001  {
1002  tmp[ i ] = in[ i ] == 0;
1003  }
1004 
1005  size_type label_num = mist::labeling4( tmp, tmp, max_label );
1006 
1007  if ( include_corner_labels )
1008  {
1009  size_type *L = new size_type[ label_num + 1 ];
1010 
1011  for( size_type i = 0 ; i <= label_num ; i++ )
1012  {
1013  L[ i ] = static_cast< size_type >( i );
1014  }
1015 
1016  L[ tmp( 0, 0 ) ] = 1;
1017  L[ tmp( tmp.width() - 1, 0 ) ] = 1;
1018  L[ tmp( 0, tmp.height() - 1 ) ] = 1;
1019  L[ tmp( tmp.width() - 1, tmp.height() - 1 ) ] = 1;
1020 
1021  for( size_type i = 0 ; i < tmp.size( ) ; i++ )
1022  {
1023  tmp[ i ] = L[ tmp[ i ] ];
1024  }
1025 
1026  delete [] L;
1027  }
1028 
1029  // 指定された範囲内の最大ラベルを探索
1030  size_type *menseki = new size_type[ label_num + 1 ];
1031  for( i = 0 ; i <= label_num ; i++ )
1032  {
1033  menseki[ i ] = 0;
1034  }
1035 
1036  for( i = 0 ; i < tmp.size( ) ; i++ )
1037  {
1038  menseki[ tmp[ i ] ]++;
1039  }
1040 
1041  max_label = 1;
1042  for( i = 2 ; i <= label_num ; i++ )
1043  {
1044  max_label = menseki[ i ] > menseki[ max_label ] ? i : max_label;
1045  }
1046  delete [] menseki;
1047 
1048  out.resize( in.size1( ), in.size2( ) );
1049  out.reso1( in.reso1( ) );
1050  out.reso2( in.reso2( ) );
1051 
1052  // 最大成分を残し，反転した画像を出力する
1053  for( i = 0 ; i < out.size( ) ; i++ )
1054  {
1055  out[ i ] = tmp[ i ] == max_label ? 0 : 1;
1056  }
1057 }
1058 
1059 
1070 template < class T1, class T2, class Allocator1, class Allocator2 >
1071 void remove_hole_region( const array2< T1, Allocator1 > &in, array2< T2, Allocator2 > &out, typename array2< T1, Allocator1 >::size_type max_label = __labeling_controller__::default_label_num2< T2 >::value )
1072 {
1073  remove_hole_region( in, out, false, max_label );
1074 }
1075 
1076 
1088 template < class T1, class T2, class Allocator1, class Allocator2 >
1089 void remove_hole_region( const array3< T1, Allocator1 > &in, array3< T2, Allocator2 > &out, const bool include_corner_labels, typename array3< T1, Allocator1 >::size_type max_label = __labeling_controller__::default_label_num3< T2 >::value )
1090 {
1091  typedef typename array2< T1, Allocator1 >::size_type size_type;
1092  typedef typename array2< T1, Allocator1 >::difference_type difference_type;
1093 
1094  array3< size_type > tmp;
1095  size_type i;
1096 
1097  tmp.resize( in.size1( ), in.size2( ), in.size3( ) );
1098  tmp.reso1( in.reso1( ) );
1099  tmp.reso2( in.reso2( ) );
1100  tmp.reso3( in.reso3( ) );
1101 
1102  // 反転した画像を作成する
1103  for( i = 0 ; i < tmp.size( ) ; i++ )
1104  {
1105  tmp[ i ] = in[ i ] == 0;
1106  }
1107 
1108  size_type label_num = mist::labeling6( tmp, tmp, max_label );
1109 
1110  if ( include_corner_labels )
1111  {
1112  size_type *L = new size_type[ label_num + 1 ];
1113 
1114  for( size_type i = 0 ; i <= label_num ; i++ )
1115  {
1116  L[ i ] = static_cast< size_type >( i );
1117  }
1118 
1119  L[ tmp( 0, 0, 0 ) ] = 1;
1120  L[ tmp( tmp.width() - 1, 0, 0 ) ] = 1;
1121  L[ tmp( 0, tmp.height() - 1, 0 ) ] = 1;
1122  L[ tmp( 0, 0, tmp.depth() - 1 ) ] = 1;
1123  L[ tmp( tmp.width() - 1, tmp.height() - 1, 0 ) ] = 1;
1124  L[ tmp( 0, tmp.height() - 1, tmp.depth() - 1 ) ] = 1;
1125  L[ tmp( tmp.width() - 1, 0, tmp.depth() - 1 ) ] = 1;
1126  L[ tmp( tmp.width() - 1, tmp.height() - 1, tmp.depth() - 1 ) ] = 1;
1127 
1128  for( size_type i = 0 ; i < tmp.size( ) ; i++ )
1129  {
1130  tmp[ i ] = L[ tmp[ i ] ];
1131  }
1132 
1133  delete [] L;
1134  }
1135 
1136  // 指定された範囲内の最大ラベルを探索
1137  size_type *menseki = new size_type[ label_num + 1 ];
1138  for( i = 0 ; i <= label_num ; i++ )
1139  {
1140  menseki[ i ] = 0;
1141  }
1142 
1143  for( i = 0 ; i < tmp.size( ) ; i++ )
1144  {
1145  menseki[ tmp[ i ] ]++;
1146  }
1147 
1148  max_label = 1;
1149  for( i = 2 ; i <= label_num ; i++ )
1150  {
1151  max_label = menseki[ i ] > menseki[ max_label ] ? i : max_label;
1152  }
1153  delete [] menseki;
1154 
1155  out.resize( in.size1( ), in.size2( ), in.size3( ) );
1156  out.reso1( in.reso1( ) );
1157  out.reso2( in.reso2( ) );
1158  out.reso3( in.reso3( ) );
1159 
1160  // 最大成分を残し，反転した画像を出力する
1161  for( i = 0 ; i < out.size( ) ; i++ )
1162  {
1163  out[ i ] = tmp[ i ] == max_label ? 0 : 1;
1164  }
1165 }
1166 
1177 template < class T1, class T2, class Allocator1, class Allocator2 >
1178 void remove_hole_region( const array3< T1, Allocator1 > &in, array3< T2, Allocator2 > &out, typename array3< T1, Allocator1 >::size_type max_label = __labeling_controller__::default_label_num3< T2 >::value )
1179 {
1180  remove_hole_region( in, out, false, max_label );
1181 }
1182 
1183 
1184 namespace __he__
1185 {
1186  template< class L >
1187  struct table_type
1188  {
1189  typedef typename array< L >::value_type label_type;
1190 
1191  label_type label;
1192  table_type *next;
1193  table_type *tail;
1194 
1195  table_type( ) : label( 0 ), next( NULL ), tail( NULL ){}
1196  };
1197 
1198  template< class L, class Allocator >
1199  inline void resolve( const typename array< L, Allocator >::value_type::label_type u, const typename array< L, Allocator >::value_type::label_type v, array< table_type< L >, Allocator > &table )
1200  {
1201  typedef typename array< L, Allocator >::value_type table_type;
1202  typedef typename table_type::label_type label_type;
1203  if( table[ u ].label != table[ v ].label )
1204  {
1205  table_type *pu;
1206  table_type *pv;
1207  if( table[ u ].label < table[ v ].label )
1208  {
1209  pu = &table[ table[ u ].label ];
1210  pv = &table[ table[ v ].label ];
1211  }
1212  else
1213  {
1214  pu = &table[ table[ v ].label ];
1215  pv = &table[ table[ u ].label ];
1216  }
1217  pu->tail->next = pv;
1218  pu->tail = pv->tail;
1219  while( pv )
1220  {
1221  pv->label = pu->label;
1222  pv = pv->next;
1223  }
1224  }
1225  }
1226 
1227  template< class L, class Allocator >
1228  inline void update( typename array< L, Allocator >::value_type::label_type &m, array< table_type< L >, Allocator > &table )
1229  {
1230  table[ m ].label = m;
1231  table[ m ].tail = &table[ m ];
1232  m++;
1233  }
1234 }
1235 
1236 
1237 namespace he
1238 {
1255  template< typename T1, class Allocator1, typename T2, class Allocator2 >
1256  inline typename array2< T2, Allocator2 >::size_type labeling8( const array2< T1, Allocator1 > &b, array2< T2, Allocator2 > &v )
1257  {
1258  typedef typename array2< T1, Allocator1 >::size_type size_type;
1259  typedef typename array2< T1, Allocator1 >::difference_type difference_type;
1260  typedef typename array2< T1, Allocator1 >::value_type value_type;
1261  typedef typename array2< T2, Allocator2 >::value_type label_type;
1262  typedef typename array2< T1, Allocator1 >::const_pointer ipointer;
1263  typedef typename array2< T2, Allocator2 >::pointer opointer;
1264 
1265  typedef typename __he__::table_type< label_type > table_type;
1266 
1267  const size_type size = ( ( b.width( ) + 1 ) / 2 ) * ( ( b.height( ) + 1 ) / 2 );
1268  array< table_type > table( size );
1269  label_type m = 1;
1270 
1271  v.resize( b.width( ), b.height( ) );
1272 
1273  ipointer ip = &b( 0, 0 );
1274  opointer op1 = &v( 0, 0 );
1275 
1276  if( ip[ 0 ] != 0 )
1277  {
1278  op1[ 0 ] = m;
1279  __he__::update( m, table );
1280  }
1281  else
1282  {
1283  op1[ 0 ] = 0;
1284  }
1285 
1286  for( size_type i = 1 ; i < b.width( ) ; i++ )
1287  {
1288  if( ip[ i ] != 0 )
1289  {
1290  if( op1[ i - 1 ] != 0 )
1291  {
1292  op1[ i ] = op1[ i - 1 ];
1293  }
1294  else
1295  {
1296  op1[ i ] = m;
1297  __he__::update( m, table );
1298  }
1299  }
1300  else
1301  {
1302  op1[ 0 ] = 0;
1303  }
1304  }
1305 
1306  // 一つ前のラインを覚える
1307  opointer op0 = op1;
1308 
1309  // 1ライン下に進める
1310  ip += b.width( );
1311  op1 += v.width( );
1312 
1313  for( size_type j = 1 ; j < b.height( ) ; j++ )
1314  {
1315  if( ip[ 0 ] != 0 )
1316  {
1317  if( op0[ 0 ] != 0 )
1318  {
1319  op1[ 0 ] = op0[ 0 ];
1320  }
1321  else if( op0[ 1 ] != 0 )
1322  {
1323  op1[ 0 ] = op0[ 1 ];
1324  }
1325  else
1326  {
1327  op1[ 0 ] = m;
1328  __he__::update( m, table );
1329  }
1330  }
1331  else
1332  {
1333  op1[ 0 ] = 0;
1334  }
1335 
1336  size_type i = 1;
1337  for( ; i < b.width( ) - 1 ; i++ )
1338  {
1339  if( ip[ i ] != 0 )
1340  {
1341  if( op0[ i ] != 0 )
1342  {
1343  op1[ i ] = op0[ i ];
1344  }
1345  else if( op1[ i - 1 ] != 0 )
1346  {
1347  op1[ i ] = op1[ i - 1 ];
1348  if( op0[ i + 1 ] != 0 )
1349  {
1350  __he__::resolve( op1[ i - 1 ], op0[ i + 1 ], table );
1351  }
1352  }
1353  else if( op0[ i - 1 ] != 0 )
1354  {
1355  op1[ i ] = op0[ i - 1 ];
1356  if( op0[ i + 1 ] != 0 )
1357  {
1358  __he__::resolve( op0[ i - 1 ], op0[ i + 1 ], table );
1359  }
1360  }
1361  else if( op0[ i + 1 ] != 0 )
1362  {
1363  op1[ i ] = op0[ i + 1 ];
1364  }
1365  else
1366  {
1367  op1[ i ] = m;
1368  __he__::update( m, table );
1369  }
1370  }
1371  else
1372  {
1373  op1[ i ] = 0;
1374  }
1375  }
1376 
1377  if( ip[ i ] != 0 )
1378  {
1379  if( op0[ i ] != 0 )
1380  {
1381  op1[ i ] = op0[ i ];
1382  }
1383  else if( op1[ i - 1 ] != 0 )
1384  {
1385  op1[ i ] = op1[ i - 1 ];
1386  }
1387  else if( op0[ i - 1 ] != 0 )
1388  {
1389  op1[ i ] = op0[ i - 1 ];
1390  }
1391  else
1392  {
1393  op1[ i ] = m;
1394  __he__::update( m, table );
1395  }
1396  }
1397  else
1398  {
1399  op1[ i ] = 0;
1400  }
1401 
1402  op0 = op1;
1403  ip += b.width( );
1404  op1 += v.width( );
1405  }
1406 
1407  array< label_type > l_table( m );
1408  label_type l = 0;
1409  for( size_type i = 1 ; i < m ; i++ )
1410  {
1411  if( l_table[ table[ i ].label ] == 0 )
1412  {
1413  l++;
1414  l_table[ table[ i ].label ] = l;
1415  }
1416  }
1417 
1418  for( size_t i = 0 ; i < v.size( ) ; i++ )
1419  {
1420  v[ i ] = l_table[ table[ v[ i ] ].label ];
1421  }
1422 
1423  return( static_cast< size_type >( l ) );
1424  }
1425 
1442  template< typename T1, class Allocator1, typename T2, class Allocator2 >
1443  inline typename array3< T2, Allocator2 >::value_type labeling26( const array3< T1, Allocator1 > &b, array3< T2, Allocator2 > &l )
1444  {
1445  typedef typename array3< T1, Allocator1 >::size_type size_type;
1446  typedef typename array3< T1, Allocator1 >::difference_type difference_type;
1447  typedef typename array3< T1, Allocator1 >::value_type value_type;
1448  typedef typename array3< T2, Allocator2 >::value_type label_type;
1449  typedef typename array3< T1, Allocator1 >::const_pointer ipointer;
1450  typedef typename array3< T2, Allocator2 >::pointer opointer;
1451 
1452  typedef typename __he__::table_type< label_type > table_type;
1453 
1454  const size_type size = ( ( b.width( ) + 1 ) / 2 ) * ( ( b.height( ) + 1 ) / 2 ) * ( ( b.depth( ) + 1 ) / 2 );
1455  array< table_type > table( size );
1456  l.resize( b.width( ), b.height( ), b.depth( ) );
1457  label_type label = 1;
1458  {// k = 0
1459  const size_t k = 0;
1460  {// j = 0
1461  const size_t j = 0;
1462  {// i = 0
1463  const size_t i = 0;
1464  if( b( i, j, k ) != 0 )
1465  {
1466  l( i, j, k ) = label;
1467  __he__::update( label, table );
1468  }
1469  else
1470  {
1471  l( i, j, k ) = 0;
1472  }
1473  }
1474  for( size_t i = 1 ; i != b.width( ) ; ++ i )
1475  {
1476  const label_type &l1 = l( i - 1, j , k );
1477  if( b( i, j, k ) != 0 )
1478  {
1479  if( l1 != 0 )
1480  {
1481  l( i, j, k ) = l1;
1482  }
1483  else
1484  {
1485  l( i, j, k ) = label;
1486  __he__::update( label, table );
1487  }
1488  }
1489  else
1490  {
1491  l( i, j, k ) = 0;
1492  }
1493  }
1494  }
1495  for( size_t j = 1 ; j != b.height( ) ; ++ j )
1496  {
1497  {// i = 0
1498  const size_t i = 0;
1499  const label_type &l3 = l( i, j - 1, k );
1500  const label_type &l4 = l( i + 1, j - 1, k );
1501  if( b( i, j, k ) != 0 )
1502  {
1503  if( l3 != 0 )
1504  {
1505  l( i, j, k ) = l3;
1506  }
1507  else if( l4 != 0 )
1508  {
1509  l( i, j, k ) = l4;
1510  }
1511  else
1512  {
1513  l( i, j, k ) = label;
1514  __he__::update( label, table );
1515  }
1516  }
1517  else
1518  {
1519  l( i, j, k ) = 0;
1520  }
1521  }
1522  for( size_t i = 1 ; i != b.width( ) - 1 ; ++ i )
1523  {
1524  const label_type &l1 = l( i - 1, j , k );
1525  const label_type &l2 = l( i - 1, j - 1, k );
1526  const label_type &l3 = l( i, j - 1, k );
1527  const label_type &l4 = l( i + 1, j - 1, k );
1528  if( b( i, j, k ) != 0 )
1529  {
1530  if( l3 != 0 )
1531  {
1532  l( i, j, k ) = l3;
1533  }
1534  else if( l1 != 0 )
1535  {
1536  l( i, j, k ) = l1;
1537  if( l4 != 0 )
1538  {
1539  __he__::resolve( l1, l4, table );
1540  }
1541  }
1542  else if( l2 != 0 )
1543  {
1544  l( i, j, k ) = l2;
1545  if( l4 != 0 )
1546  {
1547  __he__::resolve( l2, l4, table );
1548  }
1549  }
1550  else if( l4 != 0 )
1551  {
1552  l( i, j, k ) = l4;
1553  }
1554  else
1555  {
1556  l( i, j, k ) = label;
1557  __he__::update( label, table );
1558  }
1559  }
1560  else
1561  {
1562  l( i, j, k ) = 0;
1563  }
1564  }
1565  {// i = width - 1
1566  const size_t i = b.width( ) - 1;
1567  const label_type &l1 = l( i - 1, j, k );
1568  const label_type &l2 = l( i - 1, j - 1, k );
1569  const label_type &l3 = l( i, j - 1, k );
1570  if( b( i, j, k ) != 0 )
1571  {
1572  if( l3 != 0 )
1573  {
1574  l( i, j, k ) = l3;
1575  }
1576  else if( l1 != 0 )
1577  {
1578  l( i, j, k ) = l1;
1579  }
1580  else if( l2 != 0 )
1581  {
1582  l( i, j, k ) = l2;
1583  }
1584  else
1585  {
1586  l( i, j, k ) = label;
1587  __he__::update( label, table );
1588  }
1589  }
1590  else
1591  {
1592  l( i, j, k ) = 0;
1593  }
1594  }
1595  }
1596  }
1597  for( size_t k = 1 ; k != b.depth( ) ; ++ k )
1598  {
1599  {// j = 0
1600  const size_t j = 0;
1601  {// i = 0
1602  const size_t i = 0;
1603  const label_type &l9 = l( i, j, k - 1 );
1604  const label_type &l10 = l( i + 1, j, k - 1 );
1605  const label_type &l12 = l( i, j + 1, k - 1 );
1606  const label_type &l13 = l( i + 1, j + 1, k - 1 );
1607  if( b( i, j, k ) != 0 )
1608  {
1609  if( l9 != 0 )
1610  {
1611  l( i, j, k ) = l9;
1612  }
1613  else if( l10 != 0 )
1614  {
1615  l( i, j, k ) = l10;
1616  }
1617  else if( l12 != 0 )
1618  {
1619  l( i, j, k ) = l12;
1620  }
1621  else if( l13 != 0 )
1622  {
1623  l( i, j, k ) = l13;
1624  }
1625  else
1626  {
1627  l( i, j, k ) = label;
1628  __he__::update( label, table );
1629  }
1630  }
1631  else
1632  {
1633  l( i, j, k ) = 0;
1634  }
1635  }
1636  for( size_t i = 1 ; i != b.width( ) - 1 ; ++ i )
1637  {
1638  const label_type &l1 = l( i - 1, j , k );
1639  const label_type &l8 = l( i - 1, j, k - 1 );
1640  const label_type &l9 = l( i, j, k - 1 );
1641  const label_type &l10 = l( i + 1, j, k - 1 );
1642  const label_type &l11 = l( i - 1, j + 1, k - 1 );
1643  const label_type &l12 = l( i, j + 1, k - 1 );
1644  const label_type &l13 = l( i + 1, j + 1, k - 1 );
1645  if( b( i, j, k ) != 0 )
1646  {
1647  if( l9 != 0 )
1648  {
1649  l( i, j, k ) = l9;
1650  }
1651  else if( l1 != 0 )
1652  {
1653  l( i, j, k ) = l1;
1654  if( l10 != 0 && l12 == 0 )
1655  {
1656  __he__::resolve( l1, l10, table );
1657  }
1658  else if( l13 != 0 && l12 == 0 )
1659  {
1660  __he__::resolve( l1, l13, table );
1661  }
1662  }
1663  else if( l8 != 0 )
1664  {
1665  l( i, j, k ) = l8;
1666  if( l10 != 0 && l12 == 0 )
1667  {
1668  __he__::resolve( l8, l10, table );
1669  }
1670  else if( l13 != 0 && l12 == 0 )
1671  {
1672  __he__::resolve( l8, l13, table );
1673  }
1674  }
1675  else if( l10 != 0 )
1676  {
1677  l( i, j, k ) = l10;
1678  if( l11 != 0 && l12 == 0 )
1679  {
1680  __he__::resolve( l10, l11, table );
1681  }
1682  }
1683  else if( l12 != 0 )
1684  {
1685  l( i, j, k ) = l12;
1686  }
1687  else if( l11 != 0 )
1688  {
1689  l( i, j, k ) = l11;
1690  if( l13 != 0 )
1691  {
1692  __he__::resolve( l11, l13, table );
1693  }
1694  }
1695  else if( l13 != 0 )
1696  {
1697  l( i, j, k ) = l13;
1698  }
1699  else
1700  {
1701  l( i, j, k ) = label;
1702  __he__::update( label, table );
1703  }
1704  }
1705  else
1706  {
1707  l( i, j, k ) = 0;
1708  }
1709  }
1710  {// i = width - 1
1711  const size_t i = b.width( ) - 1;
1712  const label_type &l1 = l( i - 1, j , k );
1713  const label_type &l8 = l( i - 1, j, k - 1 );
1714  const label_type &l9 = l( i, j, k - 1 );
1715  const label_type &l11 = l( i - 1, j + 1, k - 1 );
1716  const label_type &l12 = l( i, j + 1, k - 1 );
1717  if( b( i, j, k ) != 0 )
1718  {
1719  if( l9 != 0 )
1720  {
1721  l( i, j, k ) = l9;
1722  }
1723  else if( l1 != 0 )
1724  {
1725  l( i, j, k ) = l1;
1726  }
1727  else if( l8 != 0 )
1728  {
1729  l( i, j, k ) = l8;
1730  }
1731  else if( l12 != 0 )
1732  {
1733  l( i, j, k ) = l12;
1734  }
1735  else if( l11 != 0 )
1736  {
1737  l( i, j, k ) = l11;
1738  }
1739  else
1740  {
1741  l( i, j, k ) = label;
1742  __he__::update( label, table );
1743  }
1744  }
1745  else
1746  {
1747  l( i, j, k ) = 0;
1748  }
1749  }
1750  }
1751  for( size_t j = 1 ; j != b.height( ) - 1 ; ++ j )
1752  {
1753  {// i = 0
1754  const size_t i = 0;
1755  const label_type &l3 = l( i, j - 1, k );
1756  const label_type &l4 = l( i + 1, j - 1, k );
1757  const label_type &l6 = l( i, j - 1, k - 1 );
1758  const label_type &l7 = l( i + 1, j - 1, k - 1 );
1759  const label_type &l9 = l( i, j, k - 1 );
1760  const label_type &l10 = l( i + 1, j, k - 1 );
1761  const label_type &l12 = l( i, j + 1, k - 1 );
1762  const label_type &l13 = l( i + 1, j + 1, k - 1 );
1763  if( b( i, j, k ) != 0 )
1764  {
1765  if( l9 != 0 )
1766  {
1767  l( i, j, k ) = l9;
1768  }
1769  else if( l3 != 0 )
1770  {
1771  l( i, j, k ) = l3;
1772  if( l12 != 0 && l10 == 0 )
1773  {
1774  __he__::resolve( l3, l12, table );
1775  }
1776  else
1777  {
1778  if( l13 != 0 && l10 == 0 )
1779  {
1780  __he__::resolve( l3, l13, table );
1781  }
1782  }
1783  }
1784  else if( l6 != 0 )
1785  {
1786  l( i, j, k ) = l6;
1787  if( l12 != 0 && l10 == 0 )
1788  {
1789  __he__::resolve( l6, l12, table );
1790  }
1791  else
1792  {
1793  if( l13 != 0 && l10 == 0 )
1794  {
1795  __he__::resolve( l6, l13, table );
1796  }
1797  }
1798  }
1799  else if( l10 != 0 )
1800  {
1801  l( i, j, k ) = l10;
1802  }
1803  else if( l12 != 0 )
1804  {
1805  l( i, j, k ) = l12;
1806  if( l4 != 0 )
1807  {
1808  __he__::resolve( l12, l4, table );
1809  }
1810  else if( l7 != 0 )
1811  {
1812  __he__::resolve( l12, l7, table );
1813  }
1814  }
1815  else if( l4 != 0 )
1816  {
1817  l( i, j, k ) = l4;
1818  if( l13 != 0 )
1819  {
1820  __he__::resolve( l4, l13, table );
1821  }
1822  }
1823  else if( l7 != 0 )
1824  {
1825  l( i, j, k ) = l7;
1826  if( l13 != 0 )
1827  {
1828  __he__::resolve( l7, l13, table );
1829  }
1830  }
1831  else if( l13 != 0 )
1832  {
1833  l( i, j, k ) = l13;
1834  }
1835  else
1836  {
1837  l( i, j, k ) = label;
1838  __he__::update( label, table );
1839  }
1840  }
1841  else
1842  {
1843  l( i, j, k ) = 0;
1844  }
1845  }
1846  for( size_t i = 1 ; i != b.width( ) - 1 ; ++ i )
1847  {
1848  const label_type &l1 = l( i - 1, j , k );
1849  const label_type &l2 = l( i - 1, j - 1, k );
1850  const label_type &l3 = l( i, j - 1, k );
1851  const label_type &l4 = l( i + 1, j - 1, k );
1852  const label_type &l5 = l( i - 1, j - 1, k - 1 );
1853  const label_type &l6 = l( i, j - 1, k - 1 );
1854  const label_type &l7 = l( i + 1, j - 1, k - 1 );
1855  const label_type &l8 = l( i - 1, j, k - 1 );
1856  const label_type &l9 = l( i, j, k - 1 );
1857  const label_type &l10 = l( i + 1, j, k - 1 );
1858  const label_type &l11 = l( i - 1, j + 1, k - 1 );
1859  const label_type &l12 = l( i, j + 1, k - 1 );
1860  const label_type &l13 = l( i + 1, j + 1, k - 1 );
1861  if( b( i, j, k ) != 0 )
1862  {
1863  if( l9 != 0 )
1864  {
1865  l( i, j, k ) = l9;
1866  }
1867  else if( l3 != 0 )
1868  {
1869  l( i, j, k ) = l3;
1870  if( l12 != 0 && l8 == 0 && l10 == 0 )
1871  {
1872  __he__::resolve( l3, l12, table );
1873  }
1874  else
1875  {
1876  if( l11 != 0 && l8 == 0 )
1877  {
1878  __he__::resolve( l3, l11, table );
1879  }
1880  if( l13 != 0 && l10 == 0 )
1881  {
1882  __he__::resolve( l3, l13, table );
1883  }
1884  }
1885  }
1886  else if( l6 != 0 )
1887  {
1888  l( i, j, k ) = l6;
1889  if( l12 != 0 && l8 == 0 && l10 == 0 )
1890  {
1891  __he__::resolve( l6, l12, table );
1892  }
1893  else
1894  {
1895  if( l11 != 0 && l8 == 0 )
1896  {
1897  __he__::resolve( l6, l11, table );
1898  }
1899  if( l13 != 0 && l10 == 0 )
1900  {
1901  __he__::resolve( l6, l13, table );
1902  }
1903  }
1904  }
1905  else if( l1 != 0 )
1906  {
1907  l( i, j, k ) = l1;
1908  if( l10 != 0 && l12 == 0 )
1909  {
1910  __he__::resolve( l1, l10, table );
1911  }
1912  else if( l7 != 0 )
1913  {
1914  __he__::resolve( l1, l7, table );
1915  if( l13 != 0 )
1916  {
1917  __he__::resolve( l1, l13, table );
1918  }
1919  }
1920  else if( l4 != 0 )
1921  {
1922  __he__::resolve( l1, l4, table );
1923  if( l13 != 0 )
1924  {
1925  __he__::resolve( l1, l13, table );
1926  }
1927  }
1928  else if( l13 != 0 && l12 == 0 )
1929  {
1930  __he__::resolve( l1, l13, table );
1931  }
1932  }
1933  else if( l8 != 0 )
1934  {
1935  l( i, j, k ) = l8;
1936  if( l10 != 0 && l12 == 0 )
1937  {
1938  __he__::resolve( l8, l10, table );
1939  }
1940  else if( l7 != 0 )
1941  {
1942  __he__::resolve( l8, l7, table );
1943  if( l13 != 0 )
1944  {
1945  __he__::resolve( l8, l13, table );
1946  }
1947  }
1948  else if( l4 != 0 )
1949  {
1950  __he__::resolve( l8, l4, table );
1951  if( l13 != 0 )
1952  {
1953  __he__::resolve( l8, l13, table );
1954  }
1955  }
1956  else if( l13 != 0 && l12 == 0 )
1957  {
1958  __he__::resolve( l8, l13, table );
1959  }
1960  }
1961  else if( l10 != 0 )
1962  {
1963  l( i, j, k ) = l10;
1964  if( l11 != 0 && l12 == 0 )
1965  {
1966  __he__::resolve( l10, l11, table );
1967  }
1968  if( l5 != 0 )
1969  {
1970  __he__::resolve( l10, l5, table );
1971  }
1972  else if( l2 != 0 )
1973  {
1974  __he__::resolve( l10, l2, table );
1975  }
1976  }
1977  else if( l12 != 0 )
1978  {
1979  l( i, j, k ) = l12;
1980  if( l4 != 0 )
1981  {
1982  __he__::resolve( l12, l4, table );
1983  }
1984  else if( l7 != 0 )
1985  {
1986  __he__::resolve( l12, l7, table );
1987  }
1988  if( l2 != 0 )
1989  {
1990  __he__::resolve( l12, l2, table );
1991  }
1992  else if( l5 != 0 )
1993  {
1994  __he__::resolve( l12, l5, table );
1995  }
1996  }
1997  else if( l5 != 0 )
1998  {
1999  l( i, j, k ) = l5;
2000  if( l4 != 0 )
2001  {
2002  __he__::resolve( l5, l4, table );
2003  }
2004  else if( l7 != 0 )
2005  {
2006  __he__::resolve( l5, l7, table );
2007  }
2008  if( l11 != 0 )
2009  {
2010  __he__::resolve( l5, l11, table );
2011  }
2012  if( l13 != 0 )
2013  {
2014  __he__::resolve( l5, l13, table );
2015  }
2016  }
2017  else if( l2 != 0 )
2018  {
2019  l( i, j, k ) = l2;
2020  if( l4 != 0 )
2021  {
2022  __he__::resolve( l2, l4, table );
2023  }
2024  else if( l7 != 0 )
2025  {
2026  __he__::resolve( l2, l7, table );
2027  }
2028  if( l11 != 0 )
2029  {
2030  __he__::resolve( l2, l11, table );
2031  }
2032  if( l13 != 0 )
2033  {
2034  __he__::resolve( l2, l13, table );
2035  }
2036  }
2037  else if( l4 != 0 )
2038  {
2039  l( i, j, k ) = l4;
2040  if( l11 != 0 )
2041  {
2042  __he__::resolve( l4, l11, table );
2043  }
2044  if( l13 != 0 )
2045  {
2046  __he__::resolve( l4, l13, table );
2047  }
2048  }
2049  else if( l7 != 0 )
2050  {
2051  l( i, j, k ) = l7;
2052  if( l11 != 0 )
2053  {
2054  __he__::resolve( l7, l11, table );
2055  }
2056  if( l13 != 0 )
2057  {
2058  __he__::resolve( l7, l13, table );
2059  }
2060  }
2061  else if( l11 != 0 )
2062  {
2063  l( i, j, k ) = l11;
2064  if( l13 != 0 )
2065  {
2066  __he__::resolve( l11, l13, table );
2067  }
2068  }
2069  else if( l13 != 0 )
2070  {
2071  l( i, j, k ) = l13;
2072  }
2073  else
2074  {
2075  l( i, j, k ) = label;
2076  __he__::update( label, table );
2077  }
2078  }
2079  else
2080  {
2081  l( i, j, k ) = 0;
2082  }
2083  }
2084  {// i = width - 1
2085  const size_t i = b.width( ) - 1;
2086  const label_type &l1 = l( i - 1, j , k );
2087  const label_type &l2 = l( i - 1, j - 1, k );
2088  const label_type &l3 = l( i, j - 1, k );
2089  const label_type &l5 = l( i - 1, j - 1, k - 1 );
2090  const label_type &l6 = l( i, j - 1, k - 1 );
2091  const label_type &l8 = l( i - 1, j, k - 1 );
2092  const label_type &l9 = l( i, j, k - 1 );
2093  const label_type &l11 = l( i - 1, j + 1, k - 1 );
2094  const label_type &l12 = l( i, j + 1, k - 1 );
2095  if( b( i, j, k ) != 0 )
2096  {
2097  if( l9 != 0 )
2098  {
2099  l( i, j, k ) = l9;
2100  }
2101  else if( l3 != 0 )
2102  {
2103  l( i, j, k ) = l3;
2104  if( l12 != 0 && l8 == 0 )
2105  {
2106  __he__::resolve( l3, l12, table );
2107  }
2108  else
2109  {
2110  if( l11 != 0 && l8 == 0 )
2111  {
2112  __he__::resolve( l3, l11, table );
2113  }
2114  }
2115  }
2116  else if( l6 != 0 )
2117  {
2118  l( i, j, k ) = l6;
2119  if( l12 != 0 && l8 == 0 )
2120  {
2121  __he__::resolve( l6, l12, table );
2122  }
2123  else
2124  {
2125  if( l11 != 0 && l8 == 0 )
2126  {
2127  __he__::resolve( l6, l11, table );
2128  }
2129  }
2130  }
2131  else if( l1 != 0 )
2132  {
2133  l( i, j, k ) = l1;
2134  }
2135  else if( l8 != 0 )
2136  {
2137  l( i, j, k ) = l8;
2138  }
2139  else if( l12 != 0 )
2140  {
2141  l( i, j, k ) = l12;
2142  if( l2 != 0 )
2143  {
2144  __he__::resolve( l12, l2, table );
2145  }
2146  else if( l5 != 0 )
2147  {
2148  __he__::resolve( l12, l5, table );
2149  }
2150  }
2151  else if( l5 != 0 )
2152  {
2153  l( i, j, k ) = l5;
2154  if( l11 != 0 )
2155  {
2156  __he__::resolve( l5, l11, table );
2157  }
2158  }
2159  else if( l2 != 0 )
2160  {
2161  l( i, j, k ) = l2;
2162  if( l11 != 0 )
2163  {
2164  __he__::resolve( l2, l11, table );
2165  }
2166  }
2167  else if( l11 != 0 )
2168  {
2169  l( i, j, k ) = l11;
2170  }
2171  else
2172  {
2173  l( i, j, k ) = label;
2174  __he__::update( label, table );
2175  }
2176  }
2177  else
2178  {
2179  l( i, j, k ) = 0;
2180  }
2181  }
2182  }
2183  {// j = height - 1
2184  const size_t j = b.height( ) - 1;
2185  {// i = 0
2186  const size_t i = 0;
2187  const label_type &l3 = l( i, j - 1, k );
2188  const label_type &l4 = l( i + 1, j - 1, k );
2189  const label_type &l6 = l( i, j - 1, k - 1 );
2190  const label_type &l7 = l( i + 1, j - 1, k - 1 );
2191  const label_type &l9 = l( i, j, k - 1 );
2192  const label_type &l10 = l( i + 1, j, k - 1 );
2193  if( b( i, j, k ) != 0 )
2194  {
2195  if( l9 != 0 )
2196  {
2197  l( i, j, k ) = l9;
2198  }
2199  else if( l3 != 0 )
2200  {
2201  l( i, j, k ) = l3;
2202  }
2203  else if( l6 != 0 )
2204  {
2205  l( i, j, k ) = l6;
2206  }
2207  else if( l10 != 0 )
2208  {
2209  l( i, j, k ) = l10;
2210  }
2211  else if( l4 != 0 )
2212  {
2213  l( i, j, k ) = l4;
2214  }
2215  else if( l7 != 0 )
2216  {
2217  l( i, j, k ) = l7;
2218  }
2219  else
2220  {
2221  l( i, j, k ) = label;
2222  __he__::update( label, table );
2223  }
2224  }
2225  else
2226  {
2227  l( i, j, k ) = 0;
2228  }
2229  }
2230  for( size_t i = 1 ; i != b.width( ) - 1 ; ++ i )
2231  {
2232  const label_type &l1 = l( i - 1, j , k );
2233  const label_type &l2 = l( i - 1, j - 1, k );
2234  const label_type &l3 = l( i, j - 1, k );
2235  const label_type &l4 = l( i + 1, j - 1, k );
2236  const label_type &l5 = l( i - 1, j - 1, k - 1 );
2237  const label_type &l6 = l( i, j - 1, k - 1 );
2238  const label_type &l7 = l( i + 1, j - 1, k - 1 );
2239  const label_type &l8 = l( i - 1, j, k - 1 );
2240  const label_type &l9 = l( i, j, k - 1 );
2241  const label_type &l10 = l( i + 1, j, k - 1 );
2242  if( b( i, j, k ) != 0 )
2243  {
2244  if( l9 != 0 )
2245  {
2246  l( i, j, k ) = l9;
2247  }
2248  else if( l3 != 0 )
2249  {
2250  l( i, j, k ) = l3;
2251  }
2252  else if( l6 != 0 )
2253  {
2254  l( i, j, k ) = l6;
2255  }
2256  else if( l1 != 0 )
2257  {
2258  l( i, j, k ) = l1;
2259  if( l10 != 0 )
2260  {
2261  __he__::resolve( l1, l10, table );
2262  }
2263  else if( l7 != 0 )
2264  {
2265  __he__::resolve( l1, l7, table );
2266  }
2267  else if( l4 != 0 )
2268  {
2269  __he__::resolve( l1, l4, table );
2270  }
2271  }
2272  else if( l8 != 0 )
2273  {
2274  l( i, j, k ) = l8;
2275  if( l10 != 0 )
2276  {
2277  __he__::resolve( l8, l10, table );
2278  }
2279  else if( l7 != 0 )
2280  {
2281  __he__::resolve( l8, l7, table );
2282  }
2283  else if( l4 != 0 )
2284  {
2285  __he__::resolve( l8, l4, table );
2286  }
2287  }
2288  else if( l10 != 0 )
2289  {
2290  l( i, j, k ) = l10;
2291  if( l5 != 0 )
2292  {
2293  __he__::resolve( l10, l5, table );
2294  }
2295  else if( l2 != 0 )
2296  {
2297  __he__::resolve( l10, l2, table );
2298  }
2299  }
2300  else if( l5 != 0 )
2301  {
2302  l( i, j, k ) = l5;
2303  if( l4 != 0 )
2304  {
2305  __he__::resolve( l5, l4, table );
2306  }
2307  else if( l7 != 0 )
2308  {
2309  __he__::resolve( l5, l7, table );
2310  }
2311  }
2312  else if( l2 != 0 )
2313  {
2314  l( i, j, k ) = l2;
2315  if( l4 != 0 )
2316  {
2317  __he__::resolve( l2, l4, table );
2318  }
2319  else if( l7 != 0 )
2320  {
2321  __he__::resolve( l2, l7, table );
2322  }
2323  }
2324  else if( l4 != 0 )
2325  {
2326  l( i, j, k ) = l4;
2327  }
2328  else if( l7 != 0 )
2329  {
2330  l( i, j, k ) = l7;
2331  }
2332  else
2333  {
2334  l( i, j, k ) = label;
2335  __he__::update( label, table );
2336  }
2337  }
2338  else
2339  {
2340  l( i, j, k ) = 0;
2341  }
2342  }
2343  {// i = width - 1
2344  const size_t i = b.width( ) - 1;
2345  const label_type &l1 = l( i - 1, j , k );
2346  const label_type &l2 = l( i - 1, j - 1, k );
2347  const label_type &l3 = l( i, j - 1, k );
2348  const label_type &l5 = l( i - 1, j - 1, k - 1 );
2349  const label_type &l6 = l( i, j - 1, k - 1 );
2350  const label_type &l8 = l( i - 1, j, k - 1 );
2351  const label_type &l9 = l( i, j, k - 1 );
2352  if( b( i, j, k ) != 0 )
2353  {
2354  if( l9 != 0 )
2355  {
2356  l( i, j, k ) = l9;
2357  }
2358  else if( l3 != 0 )
2359  {
2360  l( i, j, k ) = l3;
2361  }
2362  else if( l6 != 0 )
2363  {
2364  l( i, j, k ) = l6;
2365  }
2366  else if( l1 != 0 )
2367  {
2368  l( i, j, k ) = l1;
2369  }
2370  else if( l8 != 0 )
2371  {
2372  l( i, j, k ) = l8;
2373  }
2374  else if( l5 != 0 )
2375  {
2376  l( i, j, k ) = l5;
2377  }
2378  else if( l2 != 0 )
2379  {
2380  l( i, j, k ) = l2;
2381  }
2382  else
2383  {
2384  l( i, j, k ) = label;
2385  __he__::update( label, table );
2386  }
2387  }
2388  else
2389  {
2390  l( i, j, k ) = 0;
2391  }
2392  }
2393  }
2394  }
2395  mist::array< label_type > l_table( label );
2396  label_type ret = 0;
2397  for( size_t i = 1 ; i != label ; ++ i )
2398  {
2399  if( l_table[ table[ i ].label ] == 0 )
2400  {
2401  ret ++;
2402  l_table[ table[ i ].label ] = ret;
2403  }
2404  }
2405  for( size_t i = 0 ; i != l.size( ) ; ++ i )
2406  {
2407  l[ i ] = l_table[ table[ l[ i ] ].label ];
2408  }
2409  return ret;
2410  }
2411 }
2412 
2413 
2415 // ラベリンググループの終わり
2416 
2417 
2418 // mist名前空間の終わり
2419 _MIST_END
2420 
2421 
2422 #endif // __INCLUDE_MIST_LABELING__
2423 
Generated on Wed Nov 12 2014 19:44:17 for MIST by doxygen 1.8.1.2