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