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

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

integral_image.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
33
34 #ifndef __INCLUDE_INTEGRAL_IMAGE_H__
35 #define __INCLUDE_INTEGRAL_IMAGE_H__
36
37 #ifndef __INCLUDE_MIST_H__
38 #include "mist.h"
39 #endif
40
41 #ifndef __INCLUDE_MIST_TYPE_TRAIT_H__
42 #include "config/type_trait.h"
43 #endif
44
45 #ifndef __INCLUDE_MIST_COLOR_H__
46 #include "config/color.h"
47 #endif
48
49
50 // mist名前空間の始まり
51 _MIST_BEGIN
52
53 // 入力のデータ型から画素値の総和のデータ型を決定するためのクラス
54 namespace __integral_image__
55 {
56 template< class T, bool Is_decimal, bool Is_color > struct integral_type { typedef typename T::template rebind< double >::other type; };
57 template< class T > struct integral_type< T, false, true > { typedef typename T::template rebind< ptrdiff_t >::other type; };
58 template< class T > struct integral_type< T, true, false > { typedef double type; };
59 template< class T > struct integral_type< T, false, false > { typedef ptrdiff_t type; };
60 }
61
77 template< typename Array >
78 class integral_image
79 {
80 };
81
82
90
91
92
124 template< typename T, typename Allocator >
125 class integral_image< array< T, Allocator > >
126 {
127 public:
128 typedef typename __integral_image__::integral_type< T, is_float< T >::value, is_color< T >::value >::type value_type;
129 typedef array< value_type > integral_image_type;
130 typedef array< T, Allocator > image_type;
131 typedef typename image_type::size_type size_type;
132 typedef typename image_type::difference_type difference_type;
133
134 private:
135 integral_image_type integral_;
136
137 public:
138
146 value_type operator ( )( const size_type begin, const size_type size ) const
147 {
148 return( integral_( begin + size ) - integral_( begin ) );
149 }
150
157 value_type operator ( )( const difference_type i ) const
158 {
159 return( integral_( i + 1 ) );
160 }
161
166 value_type overall( ) const
167 {
168 return( integral_[ integral_.size( ) - 1 ] );
169 }
170
175 size_type size( ) const
176 {
177 return( integral_.size( ) - 1 );
178 }
179
184 void construct_integral_array( const image_type &in )
185 {
186 integral_.resize( in.size( ) + 1 );
187 for( size_type i = 1 ; i < integral_.width( ) ; i ++ )
188 {
189 integral_[ i ] = in[ i - 1 ] + integral_[ i - 1 ];
190 }
191 }
192
197 integral_image( const image_type &in )
198 {
199 construct_integral_array( in );
200 }
201
204 integral_image( ) : integral_( )
205 {
206 }
207 };
208
209
241 template< typename T, typename Allocator >
242 class integral_image< array2< T, Allocator > >
243 {
244 public:
245 typedef typename __integral_image__::integral_type< T, is_float< T >::value, is_color< T >::value >::type value_type;
246 typedef array2< value_type > integral_image_type;
247 typedef array2< T, Allocator > image_type;
248 typedef typename image_type::size_type size_type;
249 typedef typename image_type::difference_type difference_type;
250
251 private:
252 integral_image_type integral_;
253
254 public:
264 value_type operator ( )( const size_type begin_i, const size_type begin_j, const size_type width, const size_type height ) const
265 {
266 typename integral_image_type::const_pointer p1 = &integral_( begin_i, begin_j );
267 typename integral_image_type::const_pointer p2 = p1 + integral_.width( ) * height;
268 return( p2[ width] + p1[ 0 ] - p1[ width ] - p2[ 0 ] );
269 //return( integral_( begin_i + width, begin_j + height ) + integral_( begin_i, begin_j ) - integral_( begin_i + width, begin_j ) - integral_( begin_i, begin_j + height ) );
270 }
271
279 const value_type & operator ( )( const difference_type i, const difference_type j ) const
280 {
281 return( integral_( i + 1, j + 1 ) );
282 }
283
291 value_type & operator ( )( const difference_type i, const difference_type j )
292 {
293 return( integral_( i + 1, j + 1 ) );
294 }
295
300 value_type overall( ) const
301 {
302 return( integral_[ integral_.size( ) - 1 ] );
303 }
304
309 size_type size1( ) const
310 {
311 return( integral_.width( ) - 1 );
312 }
313
318 size_type size2( ) const
319 {
320 return( integral_.height( ) - 1 );
321 }
322
327 size_type width( ) const
328 {
329 return( size1( ) );
330 }
331
336 size_type height( ) const
337 {
338 return( size2( ) );
339 }
340
345 size_type size( ) const
346 {
347 return( width( ) * height( ) );
348 }
349
354 void construct_integral_array( const image_type &in )
355 {
356 integral_.resize( in.width( ) + 1, in.height( ) + 1 );
357
358 #if 0
359 int iw = static_cast< int >( in.width( ) );
360 int ih = static_cast< int >( in.height( ) );
361 size_type ow = integral_.width( );
362
363 #pragma omp parallel for firstprivate( iw, ih ) schedule( guided )
364 for( int j = 0 ; j < ih ; j++ )
365 {
366 typename image_type::const_pointer ip = &in( 0, j );
367 typename integral_image_type::pointer op = &integral_( 1, j + 1 );
368
369 op[ 0 ] = ip[ 0 ];
370 for( int i = 1 ; i < iw ; i++ )
371 {
372 op[ i ] = op[ i - 1 ] + ip[ i ];
373 }
374 }
375
376 #pragma omp parallel for firstprivate( iw, ih, ow ) schedule( guided )
377 for( int i = 0 ; i < iw ; i++ )
378 {
379 typename integral_image_type::pointer op = &integral_( i + 1, 1 );
380 typename integral_image_type::value_type ov = *op;
381
382 op += ow;
383
384 for( int j = 1 ; j < ih ; j++ )
385 {
386 ov += *op;
387 *op = ov;
388 op += ow;
389 }
390 }
391 #else
392 typename image_type::const_pointer ip = &in[ 0 ];
393 typename integral_image_type::pointer op = &integral_( 1, 1 );
394
395 op[ 0 ] = ip[ 0 ];
396 for( size_type i = 1 ; i < in.width( ) ; i++ )
397 {
398 op[ i ] = op[ i - 1 ] + ip[ i ];
399 }
400
401 typename integral_image_type::pointer oop = op;
402 ip += in.width( );
403 op += integral_.width( );
404
405 for( size_type j = 1 ; j < in.height( ) ; j++ )
406 {
407 value_type tmp = ip[ 0 ];
408 op[ 0 ] = oop[ 0 ] + tmp;
409
410 for( size_type i = 1 ; i < in.width( ) ; i++ )
411 {
412 tmp += ip[ i ];
413 op[ i ] = oop[ i ] + tmp;
414 }
415
416 oop = op;
417 ip += in.width( );
418 op += integral_.width( );
419 }
420 #endif
421 }
422
427 integral_image( const image_type &in )
428 {
429 construct_integral_array( in );
430 }
431
434 integral_image( ) : integral_( )
435 {
436 }
437 };
438
439
471 template< typename T, typename Allocator >
472 class integral_image< array3< T, Allocator > >
473 {
474 public:
475 typedef typename __integral_image__::integral_type< T, is_float< T >::value, is_color< T >::value >::type value_type;
476 typedef array3< value_type > integral_image_type;
477 typedef array3< T, Allocator > image_type;
478 typedef typename image_type::size_type size_type;
479 typedef typename image_type::difference_type difference_type;
480
481 private:
482 integral_image_type integral_;
483
484 public:
496 value_type operator ( )( const size_type begin_i, const size_type begin_j, const size_type begin_k, const size_type width, const size_type height, const size_type depth ) const
497 {
498 return( integral_( begin_i + width, begin_j + height, begin_k + depth ) + integral_( begin_i, begin_j, begin_k + depth ) + integral_( begin_i, begin_j + height, begin_k ) + integral_( begin_i + width, begin_j, begin_k ) - integral_( begin_i, begin_j + height, begin_k + depth ) - integral_( begin_i + width, begin_j, begin_k + depth ) - integral_( begin_i + width, begin_j + height, begin_k ) - integral_( begin_i, begin_j, begin_k ) );
499 }
500
509 value_type operator ( )( const difference_type i, const difference_type j, const difference_type k ) const
510 {
511 return( integral_( i + 1, j + 1, k + 1 ) );
512 }
513
518 value_type overall( ) const
519 {
520 return( integral_( integral_.width( ) - 1, integral_.height( ) - 1, integral_.depth( ) - 1 ) );
521 }
522
527 size_type size1( ) const
528 {
529 return( integral_.width( ) - 1 );
530 }
531
536 size_type size2( ) const
537 {
538 return( integral_.height( ) - 1 );
539 }
540
545 size_type size3( ) const
546 {
547 return( integral_.depth( ) - 1 );
548 }
549
554 size_type width( ) const
555 {
556 return( size1( ) );
557 }
558
563 size_type height( ) const
564 {
565 return( size2( ) );
566 }
567
572 size_type depth( ) const
573 {
574 return( size3( ) );
575 }
576
581 size_type size( ) const
582 {
583 return( width( ) * height( ) * depth( ) );
584 }
585
590 void construct_integral_array( const image_type &in )
591 {
592 integral_.resize( in.width( ) + 1, in.height( ) + 1, in.depth( ) + 1 );
593 for( size_type k = 1 ; k < integral_.depth( ) ; k ++ )
594 {
595 for( size_type j = 1 ; j < integral_.height( ) ; j ++ )
596 {
597 for( size_type i = 1 ; i < integral_.width( ) ; i ++ )
598 {
599 integral_( i, j, k ) = in( i - 1, j - 1, k - 1 ) + integral_( i - 1, j, k ) + integral_( i, j - 1, k ) + integral_( i, j, k - 1 ) + integral_( i - 1, j - 1, k - 1 ) - integral_( i - 1, j - 1, k ) - integral_( i - 1, j, k - 1 ) - integral_( i, j - 1, k - 1 );
600 }
601 }
602 }
603 }
604
609 integral_image( const image_type &in )
610 {
611 construct_integral_array( in );
612 }
613
616 integral_image( ) : integral_( )
617 {
618 }
619 };
620
621
633 template < class T, class Allocator >
634 inline std::ostream &operator <<( std::ostream &out, const integral_image< array< T, Allocator > > &a )
635 {
636 typename array< T, Allocator >::size_type i;
637 for( i = 0 ; i < a.size( ) ; i++ )
638 {
639 out << a[ i ];
640 if( i != a.size1( ) - 1 ) out << ", ";
641 }
642
643 return( out );
644 }
645
646
658 template < class T, class Allocator >
659 inline std::ostream &operator <<( std::ostream &out, const integral_image< array1< T, Allocator > > &a )
660 {
661 typename array1< T, Allocator >::size_type i;
662 for( i = 0 ; i < a.size( ) ; i++ )
663 {
664 out << a[ i ];
665 if( i != a.size1( ) - 1 ) out << ", ";
666 }
667
668 return( out );
669 }
670
671
685 template < class T, class Allocator >
686 inline std::ostream &operator <<( std::ostream &out, const integral_image< array2< T, Allocator > > &a )
687 {
688 typename array2< T, Allocator >::size_type i, j;
689 for( j = 0 ; j < a.size2( ) ; j++ )
690 {
691 if( j != 0 )
692 {
693 out << std::endl;
694 }
695 for( i = 0 ; i < a.size1( ) ; i++ )
696 {
697 out << a( i, j );
698 if( i != a.size1( ) - 1 ) out << ", ";
699 }
700 }
701
702 return( out );
703 }
704
705
723 template < class T, class Allocator >
724 inline std::ostream &operator <<( std::ostream &out, const integral_image< array3< T, Allocator > > &a )
725 {
726 typename array3< T, Allocator >::size_type i, j, k;
727 for( k = 0 ; k < a.size3( ) ; k++ )
728 {
729 for( j = 0 ; j < a.size2( ) ; j++ )
730 {
731 for( i = 0 ; i < a.size1( ) ; i++ )
732 {
733 out << a( i, j, k );
734 if( i != a.size1( ) - 1 ) out << ", ";
735 }
736 out << std::endl;
737 }
738 if( k != a.size3( ) - 1 )
739 {
740 out << "----- separator -----";
741 }
742 out << std::endl;
743 }
744
745 return( out );
746 }
747
748
750 // Integral Imageグループの終わり
751
752
753 // mist名前空間の終わり
754 _MIST_END
755
756
757 #endif // __INCLUDE_INTEGRAL_IMAGE_H__
758