- メインページ
- モジュール
- ネームスペース
- データ構造
- ファイル

- ファイル一覧
- グローバル

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