active_search.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 
35 #ifndef __INCLUDE_ACTIVE_SEARCH_H__
36 #define __INCLUDE_ACTIVE_SEARCH_H__
37 
38 
39 
40 #include <mist/mist.h>
41 #include <mist/config/color.h>
42 
43 #include <functional>
44 
45 
46 
47 // mist名前空間の始まり
48 _MIST_BEGIN
49 
50 
51 
52 
60 
65 struct active_search_style
66 {
68  enum style
69  {
70  speed,
71  memory,
72  };
73 };
74 
75 
76 
77 
78 namespace _active_search_
79 {
80 
81 
82  /*************************************************************************************************************************************************
83  **
84  ** 参考文献:
85  **
86  ** 村瀬 洋，V.V.Vinod, 局所色情報を用いた高速物体探索 -アクティブ探索法- (Fast visual search using focussed color matching - active search -),
87  ** 電子情報通信学会論文誌, Vol. J81-DII,No,9, pp.2035-2042, 1998.
88  **
89  **************************************************************************************************************************************************/
90 
91 
92  inline double _minimum(
93  const double &v0,
94  const double &v1 )
95  {
96  return ( v0 < v1 ) ? v0 : v1;
97  }
98 
99  inline double _upper(
100  const size_t &overlap,
101  const size_t &size,
102  const double &sim )
103  {
104  return ( _minimum( sim * size, static_cast< double >( overlap ) ) + size - overlap ) / size;
105  }
106 
107  template < typename Histogram_type >
108  inline double _similarity(
109  const Histogram_type &histo0,
110  const Histogram_type &histo1 )
111  {
112  double similarity = 0.0;
113  for( size_t i = 0 ; i < histo0.size( ) ; i ++ )
114  {
115  similarity += _minimum( histo0[ i ], histo1[ i ] );
116  }
117  return similarity;
118  }
119 
120  template < typename Functor >
121  inline void _quantize(
122  const array< typename Functor::argument_type > &in,
123  array< typename Functor::result_type > &out,
124  const Functor &f )
125  {
126  for( size_t i = 0 ; i < in.size( ) ; i ++ )
127  {
128  out[ i ] = f( in[ i ] );
129  }
130  }
131 
132 
133 
134 
135  template < typename Argument_type, typename Result_type >
136  struct _functor : std::unary_function< Argument_type, Result_type >
137  {
138  typedef typename std::unary_function< Argument_type, Result_type > base_type;
139  typedef typename base_type::argument_type argument_type;
140  typedef typename base_type::result_type result_type;
141  _functor( )
142  {
143  }
144  const result_type &operator ( )( const argument_type &v ) const
145  {
146  return v;
147  }
148  };
149 
150  template < >
151  struct _functor< rgb< unsigned char >, unsigned int > : std::unary_function< rgb< unsigned char >, unsigned int >
152  {
153  typedef std::unary_function< rgb< unsigned char >, unsigned int > base_type;
154  typedef base_type::argument_type argument_type;
155  typedef base_type::result_type result_type;
156  unsigned char level_;
157  size_t d1_;
158  size_t d2_;
159  _functor( const size_t &num_of_bins ) : level_( static_cast< unsigned char >( ( 256 % num_of_bins == 0 ) ? ( 256 / num_of_bins ) : ( 256 / ( num_of_bins - 1 ) ) ) ), d1_( num_of_bins ), d2_( num_of_bins * num_of_bins )
160  {
161  }
162  result_type operator ( )( const argument_type &v ) const
163  {
164  return static_cast< result_type >( ( v.r / level_ ) * d2_ + ( v.g / level_ ) * d1_ + ( v.b / level_ ) );
165  }
166  };
167 
168 
169 
170  template < typename Array_type, typename Histogram_type, typename Functor >
171  inline void _make_histogram(
172  const Array_type &array,
173  Histogram_type &histo,
174  const size_t &bi,
175  const size_t &w,
176  const Functor &f )
177  {
178  histo.fill( 0.0 );
179  const double gain = 1.0 / w;
180  for( size_t i = 0 ; i < w ; i ++ )
181  {
182  histo[ f( array[ bi + i ] ) ] += gain;
183  }
184  }
185 
186  template < typename Array_type, typename Histogram_type, typename Functor >
187  inline void _diff_histogram(
188  const Array_type &array,
189  Histogram_type &histo,
190  const size_t &bi,
191  const size_t &pbi,
192  const size_t &w,
193  const Functor &f )
194  {
195  if( bi < pbi + w )
196  {
197  const double gain = 1.0 / w;
198  for( size_t i = 0 ; i < bi - pbi ; i ++ )
199  {
200  histo[ f( array[ pbi + i ] ) ] -= gain;
201  histo[ f( array[ pbi + w + i ] ) ] += gain;
202  }
203  }
204  else
205  {
206  _make_histogram( array, histo, bi, w, f );
207  }
208  }
209 
210  template< typename Table_type >
211  inline void _culling(
212  Table_type &c_tab,
213  const size_t &bi,
214  const size_t &w,
215  const double &sim,
216  const double &max_sim )
217  {
218  const size_t size = w;
219  for( size_t i = 0 ; i < w ; i ++ )
220  {
221  if( _upper( w - i, size, sim ) < max_sim )
222  {
223  c_tab[ bi + i ] = true;
224  }
225  else
226  {
227  break;
228  }
229  }
230  }
231 
232  template< typename Array_type, typename Functor >
233  inline bool __search(
234  const Array_type &in,
235  const Array_type &ref,
236  unsigned int &x,
237  double &scale,
238  double &similarity,
239  const size_t &num_of_bins,
240  const Functor &f,
241  const double &b_scale,
242  const double &e_scale,
243  const double &scale_factor )
244  {
245  typedef array< double > histogram_type;
246 
247  histogram_type i_histo( num_of_bins );
248  histogram_type r_histo( num_of_bins );
249  _make_histogram( ref, r_histo, 0, ref.size( ), f );
250  array< bool > culling_table( in.size( ) );
251  x = 0;
252  scale = b_scale;
253  similarity = ( similarity < 0.0 || 1.0 < similarity ) ? 0.0 : similarity;
254  double s = b_scale;
255  double sim = 0.0;
256  size_t w, pi;
257  bool is_found = false;
258 
259  while( ( scale_factor > 1.0 ) ? ( s <= e_scale ) : ( s >= e_scale ) )
260  {
261  w = static_cast< size_t >( ref.size( ) * s );
262  _make_histogram( in, i_histo, 0, w, f );
263  pi = 0;
264  culling_table.fill( false );
265  for( size_t i = 0 ; i < in.size( ) - w + 1 ; i ++ )
266  {
267  if( !culling_table[ i ] )
268  {
269  _diff_histogram( in, i_histo, i, pi, w, f );
270  pi = i;
271  sim = _similarity( i_histo, r_histo );
272  if( sim > similarity )
273  {
274  is_found = true;
275  x = static_cast< unsigned int >( i );
276  scale = s;
277  similarity = sim;
278  }
279  _culling( culling_table, i, w, sim, similarity );
280  }
281  }
282  s *= scale_factor;
283  }
284  return is_found;
285  }
286 
287  template< typename Array_type, typename Functor >
288  inline bool _search_memory(
289  const Array_type &in,
290  const Array_type &ref,
291  unsigned int &x,
292  double &scale,
293  double &similarity,
294  const size_t &num_of_bins,
295  const Functor &f,
296  const double &b_scale,
297  const double &e_scale,
298  const double &scale_factor )
299  {
300  //std::cout << "memory" << std::endl;
301  return __search( in, ref, x, scale, similarity, num_of_bins, f, b_scale, e_scale, scale_factor );
302  }
303 
304  template< typename Array_type, typename Functor >
305  inline bool _search_speed(
306  const Array_type &in2,
307  const Array_type &ref2,
308  unsigned int &x,
309  double &scale,
310  double &similarity,
311  const size_t &num_of_bins,
312  const Functor &f,
313  const double &b_scale,
314  const double &e_scale,
315  const double &scale_factor )
316  {
317  //std::cout << "speed" << std::endl;
318  typedef typename Functor::result_type value_type;
319  array< value_type > in( in2.size( ) );
320  _quantize( in2, in, f );
321  array< value_type > ref( ref2.size( ) );
322  _quantize( ref2, ref, f );
323  return __search( in, ref, x, scale, similarity, num_of_bins, _functor< value_type, value_type >( ), b_scale, e_scale, scale_factor );
324  }
325 
326  template< typename Array_type, typename Functor >
327  inline bool _search(
328  const Array_type &input,
329  const Array_type &reference,
330  unsigned int &x,
331  double &scale,
332  double &similarity,
333  double min_scale,
334  double max_scale,
335  const double &scale_factor,
336  const size_t &num_of_bins,
337  const Functor &f,
338  const active_search_style::style &style )
339  {
340  if( scale_factor <= 0.0 || scale_factor == 1.0 )
341  {
342  return false;
343  }
344  const double u_bound = static_cast< double >( input.size( ) ) / reference.size( );
345  const double l_bound = 0.01;
346  min_scale = ( min_scale < l_bound ) ? l_bound : min_scale;
347  min_scale = ( min_scale > u_bound ) ? u_bound : min_scale;
348  max_scale = ( max_scale < l_bound ) ? l_bound : max_scale;
349  max_scale = ( max_scale > u_bound ) ? u_bound : max_scale;
350  if( min_scale > max_scale )
351  {
352  double tmp = min_scale;
353  min_scale = max_scale;
354  max_scale = tmp;
355  }
356  double begin_scale, end_scale;
357  if( scale_factor > 1.0 )
358  {
359  begin_scale = min_scale;
360  end_scale = max_scale;
361  }
362  else
363  {
364  begin_scale = max_scale;
365  end_scale = min_scale;
366  }
367  if( style == active_search_style::speed )
368  {
369  return _search_speed( input, reference, x, scale, similarity, num_of_bins, f, begin_scale, end_scale, scale_factor );
370  }
371  if( style == active_search_style::memory )
372  {
373  return _search_memory( input, reference, x, scale, similarity, num_of_bins, f, begin_scale, end_scale, scale_factor );
374  }
375  return false;
376  }
377 
378 
379 
380 
381  template < typename Array_type, typename Histogram_type, typename Functor >
382  inline void _make_histogram(
383  const Array_type &array,
384  Histogram_type &histo,
385  const size_t &bi,
386  const size_t &bj,
387  const size_t &w,
388  const size_t &h,
389  const Functor &f )
390  {
391  histo.fill( 0.0 );
392  const double gain = 1.0 / ( w * h );
393  for( size_t j = 0 ; j < h ; j ++ )
394  {
395  for( size_t i = 0 ; i < w ; i ++ )
396  {
397  histo[ f( array( bi + i, bj + j ) ) ] += gain;
398  }
399  }
400  }
401 
402  template < typename Array_type, typename Histogram_type, typename Functor >
403  inline void _diff_histogram(
404  const Array_type &array,
405  Histogram_type &histo,
406  const size_t &bi,
407  const size_t &bj,
408  const size_t &pbi,
409  const size_t &pbj,
410  const size_t &w,
411  const size_t &h,
412  const Functor &f )
413  {
414  if( bi < pbi + w )
415  {
416  const double gain = 1.0 / ( w * h );
417  size_t j = 0;
418  for( ; j < bj - pbj ; j ++ )
419  {
420  for( size_t i = 0 ; i < w ; i ++ )
421  {
422  histo[ f( array( pbi + i, pbj + j ) ) ] -= gain;
423  histo[ f( array( bi + i, pbj + h + j ) ) ] += gain;
424  }
425  }
426  for( ; j < h ; j ++ )
427  {
428  for( size_t i = 0 ; i < bi - pbi ; i ++ )
429  {
430  histo[ f( array( pbi + i, pbj + j ) ) ] -= gain;
431  histo[ f( array( pbi + w + i, bj + j ) ) ] += gain;
432  }
433  }
434  }
435  else
436  {
437  _make_histogram( array, histo, bi, bj, w, h, f );
438  }
439  }
440 
441  template< typename Table_type >
442  inline void _culling(
443  Table_type &c_tab,
444  const size_t &bi,
445  const size_t &bj,
446  const size_t &w,
447  const size_t &h,
448  const double &sim,
449  const double &max_sim )
450  {
451  const size_t size = w * h;
452  for( size_t j = 0 ; j < h ; j ++ )
453  {
454  if( _upper( w * ( h - j ), size, sim ) >= max_sim )
455  {
456  break;
457  }
458  for( size_t i = 0 ; i < w ; i ++ )
459  {
460  if( _upper( ( w - i ) * ( h - j ), size, sim ) < max_sim )
461  {
462  c_tab( bi + i, bj + j ) = true;
463  if( i <= bi )
464  {
465  c_tab( bi - i, bj + j ) = true;
466  }
467  }
468  else
469  {
470  break;
471  }
472  }
473  }
474  }
475 
476  template< typename Array_type, typename Functor >
477  inline bool __search(
478  const Array_type &in,
479  const Array_type &ref,
480  unsigned int &x,
481  unsigned int &y,
482  double &scale,
483  double &similarity,
484  const size_t &num_of_bins,
485  const Functor &f,
486  const double &b_scale,
487  const double &e_scale,
488  const double &scale_factor )
489  {
490  typedef array< double > histogram_type;
491 
492  histogram_type i_histo( num_of_bins );
493  histogram_type r_histo( num_of_bins );
494  _make_histogram( ref, r_histo, 0, 0, ref.width( ), ref.height( ), f );
495  array2< bool > culling_table( in.width( ), in.height( ) );
496  x = 0;
497  y = 0;
498  scale = b_scale;
499  similarity = ( similarity < 0.0 || 1.0 < similarity ) ? 0.0 : similarity;
500  double s = b_scale;
501  double sim = 0.0;
502  size_t w, h, pi, pj;
503  histogram_type histo( num_of_bins );
504  bool is_found = false;
505 
506  while( ( scale_factor > 1.0 ) ? ( s <= e_scale ) : ( s >= e_scale ) )
507  {
508  w = static_cast< size_t >( ref.width( ) * s );
509  h = static_cast< size_t >( ref.height( ) * s );
510  _make_histogram( in, histo, 0, 0, w, h, f );
511  culling_table.fill( false );
512  pj = 0;
513  for( size_t j = 0 ; j < in.height( ) - h + 1 ; j ++ )
514  {
515  _diff_histogram( in, histo, 0, j, 0, pj, w, h, f );
516  i_histo = histo;
517  pj = j;
518  pi = 0;
519  for( size_t i = 0 ; i < in.width( ) - w + 1 ; i ++ )
520  {
521  if( !culling_table( i, j ) )
522  {
523  _diff_histogram( in, i_histo, i, j, pi, pj, w, h, f );
524  pi = i;
525  sim = _similarity( i_histo, r_histo );
526  if( sim > similarity )
527  {
528  is_found = true;
529  x = static_cast< unsigned int >( i );
530  y = static_cast< unsigned int >( j );
531  scale = s;
532  similarity = sim;
533  }
534  _culling( culling_table, i, j, w, h, sim, similarity );
535  }
536  }
537  }
538  s *= scale_factor;
539  }
540  return is_found;
541  }
542 
543  template< typename Array_type, typename Functor >
544  inline bool _search_memory(
545  const Array_type &in,
546  const Array_type &ref,
547  unsigned int &x,
548  unsigned int &y,
549  double &scale,
550  double &similarity,
551  const size_t &num_of_bins,
552  const Functor &f,
553  const double &b_scale,
554  const double &e_scale,
555  const double &scale_factor )
556  {
557  //std::cout << "memory" << std::endl;
558  return __search( in, ref, x, y, scale, similarity, num_of_bins, f, b_scale, e_scale, scale_factor );
559  }
560 
561  template< typename Array_type, typename Functor >
562  inline bool _search_speed(
563  const Array_type &in2,
564  const Array_type &ref2,
565  unsigned int &x,
566  unsigned int &y,
567  double &scale,
568  double &similarity,
569  const size_t &num_of_bins,
570  const Functor &f,
571  const double &b_scale,
572  const double &e_scale,
573  const double &scale_factor )
574  {
575  //std::cout << "speed" << std::endl;
576  typedef typename Functor::result_type value_type;
577  array2< value_type > in( in2.width( ), in2.height( ) );
578  _quantize( in2, in, f );
579  array2< value_type > ref( ref2.width( ), ref2.height( ) );
580  _quantize( ref2, ref, f );
581  return __search( in, ref, x, y, scale, similarity, num_of_bins, _functor< value_type, value_type >( ), b_scale, e_scale, scale_factor );
582  }
583 
584  template< typename Array_type, typename Functor >
585  inline bool _search(
586  const Array_type &input,
587  const Array_type &reference,
588  unsigned int &x,
589  unsigned int &y,
590  double &scale,
591  double &similarity,
592  double min_scale,
593  double max_scale,
594  const double &scale_factor,
595  const size_t &num_of_bins,
596  const Functor &f,
597  const active_search_style::style &style )
598  {
599  if( scale_factor <= 0.0 || scale_factor == 1.0 )
600  {
601  return false;
602  }
603  const double u_bound = _minimum( static_cast< double >( input.width( ) ) / reference.width( ), static_cast< double >( input.height( ) ) / reference.height( ) );
604  const double l_bound = 0.01;
605  min_scale = ( min_scale < l_bound ) ? l_bound : min_scale;
606  min_scale = ( min_scale > u_bound ) ? u_bound : min_scale;
607  max_scale = ( max_scale < l_bound ) ? l_bound : max_scale;
608  max_scale = ( max_scale > u_bound ) ? u_bound : max_scale;
609  if( min_scale > max_scale )
610  {
611  double tmp = min_scale;
612  min_scale = max_scale;
613  max_scale = tmp;
614  }
615  double begin_scale, end_scale;
616  if( scale_factor > 1.0 )
617  {
618  begin_scale = min_scale;
619  end_scale = max_scale;
620  }
621  else
622  {
623  begin_scale = max_scale;
624  end_scale = min_scale;
625  }
626  if( style == active_search_style::speed )
627  {
628  return _search_speed( input, reference, x, y, scale, similarity, num_of_bins, f, begin_scale, end_scale, scale_factor );
629  }
630  if( style == active_search_style::memory )
631  {
632  return _search_memory( input, reference, x, y, scale, similarity, num_of_bins, f, begin_scale, end_scale, scale_factor );
633  }
634  return false;
635  }
636 
637 
638 
639  template < typename Array_type, typename Histogram_type, typename Functor >
640  inline void _make_histogram(
641  const Array_type &array,
642  Histogram_type &histo,
643  const size_t &bi,
644  const size_t &bj,
645  const size_t &bk,
646  const size_t &w,
647  const size_t &h,
648  const size_t &d,
649  const Functor &f )
650  {
651  histo.fill( 0.0 );
652  const double gain = 1.0 / ( w * h * d );
653  for( size_t k = 0 ; k < d ; k ++ )
654  {
655  for( size_t j = 0 ; j < h ; j ++ )
656  {
657  for( size_t i = 0 ; i < w ; i ++ )
658  {
659  histo[ f( array( bi + i, bj + j, bk + k ) ) ] += gain;
660  }
661  }
662  }
663  }
664 
665  template < typename Array_type, typename Histogram_type, typename Functor >
666  inline void _diff_histogram(
667  const Array_type &array,
668  Histogram_type &histo,
669  const size_t &bi,
670  const size_t &bj,
671  const size_t &bk,
672  const size_t &pbi,
673  const size_t &pbj,
674  const size_t &pbk,
675  const size_t &w,
676  const size_t &h,
677  const size_t &d,
678  const Functor &f )
679  {
680  if( bi < pbi + w )
681  {
682  const double gain = 1.0 / ( w * h * d );
683  size_t k = 0;
684  for( ; k < bk - pbk ; k ++ )
685  {
686  for( size_t j = 0 ; j < h ; j ++ )
687  {
688  for( size_t i = 0 ; i < w ; i ++ )
689  {
690  histo[ f( array( pbi + i, pbj + j, pbk + k ) ) ] -= gain;
691  histo[ f( array( bi + i, bj + j, pbk + d + k ) ) ] += gain;
692  }
693  }
694  }
695  for( ; k < d ; k ++ )
696  {
697  size_t j = 0;
698  for( ; j < bj - pbj ; j ++ )
699  {
700  for( size_t i = 0 ; i < w ; i ++ )
701  {
702  histo[ f( array( pbi + i, pbj + j, bk + k ) ) ] -= gain;
703  histo[ f( array( bi + i, pbj + h + j, bk + k ) ) ] += gain;
704  }
705  }
706  for( ; j < h ; j ++ )
707  {
708  for( size_t i = 0 ; i < bi - pbi ; i ++ )
709  {
710  histo[ f( array( pbi + i, bj + j, bk + k ) ) ] -= gain;
711  histo[ f( array( pbi + w + i, bj + j, bk + k ) ) ] += gain;
712  }
713  }
714  }
715  }
716  else
717  {
718  _make_histogram( array, histo, bi, bj, bk, w, h, d, f );
719  }
720  }
721 
722  template< typename Table_type >
723  inline void _culling(
724  Table_type &c_tab,
725  const size_t &bi,
726  const size_t &bj,
727  const size_t &bk,
728  const size_t &w,
729  const size_t &h,
730  const size_t &d,
731  const double &sim,
732  const double &max_sim )
733  {
734  const size_t size = w * h * d;
735  for( size_t k = 0 ; k < d ; k ++ )
736  {
737  if( _upper( w * h * ( d - k ), size, sim ) >= max_sim )
738  {
739  break;
740  }
741  for( size_t j = 0 ; j < h ; j ++ )
742  {
743  if( _upper( w * ( h - j ) * ( d - k ), size, sim ) >= max_sim )
744  {
745  break;
746  }
747  for( size_t i = 0 ; i < w ; i ++ )
748  {
749  if( _upper( ( w - i ) * ( h - j ) * ( d - k ), size, sim ) < max_sim )
750  {
751  c_tab( bi + i, bj + j, bk + k ) = true;
752  if( j <= bj )
753  {
754  c_tab( bi + i, bj - j, bk + k ) = true;
755  }
756  if( i <= bi )
757  {
758  c_tab( bi - i, bj + j, bk + k ) = true;
759  if( j <= bj )
760  {
761  c_tab( bi - i, bj - j, bk + k ) = true;
762  }
763  }
764  }
765  else
766  {
767  break;
768  }
769  }
770  }
771  }
772  }
773 
774  template< typename Array_type, typename Functor >
775  inline bool __search(
776  const Array_type &in,
777  const Array_type &ref,
778  unsigned int &x,
779  unsigned int &y,
780  unsigned int &z,
781  double &scale,
782  double &similarity,
783  const size_t &num_of_bins,
784  const Functor &f,
785  const double &b_scale,
786  const double &e_scale,
787  const double &scale_factor )
788  {
789  typedef array< double > histogram_type;
790 
791  histogram_type i_histo( num_of_bins );
792  histogram_type r_histo( num_of_bins );
793  _make_histogram( ref, r_histo, 0, 0, 0, ref.width( ), ref.height( ), ref.depth( ), f );
794  array3< bool > culling_table( in.width( ), in.height( ), in.depth( ) );
795  x = 0;
796  y = 0;
797  z = 0;
798  scale = b_scale;
799  similarity = ( similarity < 0.0 || 1.0 < similarity ) ? 0.0 : similarity;
800  double s = b_scale;
801  double sim = 0.0;
802  size_t w, h, d, pi, pj, pk;
803  histogram_type histo1( num_of_bins ), histo2( num_of_bins );
804  bool is_found = false;
805 
806  while( ( scale_factor > 1.0 ) ? ( s <= e_scale ) : ( s >= e_scale ) )
807  {
808  w = static_cast< size_t >( ref.width( ) * s );
809  h = static_cast< size_t >( ref.height( ) * s );
810  d = static_cast< size_t >( ref.depth( ) * s );
811  _make_histogram( in, histo2, 0, 0, 0, w, h, d, f );
812  culling_table.fill( false );
813  pk = 0;
814  for( size_t k = 0 ; k < in.depth( ) - d + 1 ; k ++ )
815  {
816  _diff_histogram( in, histo2, 0, 0, k, 0, 0, pk, w, h, d, f );
817  histo1 = histo2;
818  pk = k;
819  pj = 0;
820  for( size_t j = 0 ; j < in.height( ) - h + 1 ; j ++ )
821  {
822  _diff_histogram( in, histo1, 0, j, k, 0, pj, pk, w, h, d, f );
823  i_histo = histo1;
824  pj = j;
825  pi = 0;
826  for( size_t i = 0 ; i < in.width( ) - w + 1 ; i ++ )
827  {
828  if( !culling_table( i, j, k ) )
829  {
830  //_make_histogram( in, i_histo, i, j, k, w, h, d, f );
831  _diff_histogram( in, i_histo, i, j, k, pi, pj, pk, w, h, d, f );
832  pi = i;
833  sim = _similarity( i_histo, r_histo );
834  if( sim > similarity )
835  {
836  is_found = true;
837  x = static_cast< unsigned int >( i );
838  y = static_cast< unsigned int >( j );
839  z = static_cast< unsigned int >( k );
840  scale = s;
841  similarity = sim;
842  }
843  _culling( culling_table, i, j, k, w, h, d, sim, similarity );
844  }
845  }
846  }
847  }
848  s *= scale_factor;
849  }
850  return is_found;
851  }
852 
853  template< typename Array_type, typename Functor >
854  inline bool _search_memory(
855  const Array_type &in,
856  const Array_type &ref,
857  unsigned int &x,
858  unsigned int &y,
859  unsigned int &z,
860  double &scale,
861  double &similarity,
862  const size_t &num_of_bins,
863  const Functor &f,
864  const double &b_scale,
865  const double &e_scale,
866  const double &scale_factor )
867  {
868  //std::cout << "memory" << std::endl;
869  return __search( in, ref, x, y, z, scale, similarity, num_of_bins, f, b_scale, e_scale, scale_factor );
870  }
871 
872  template< typename Array_type, typename Functor >
873  inline bool _search_speed(
874  const Array_type &in2,
875  const Array_type &ref2,
876  unsigned int &x,
877  unsigned int &y,
878  unsigned int &z,
879  double &scale,
880  double &similarity,
881  const size_t &num_of_bins,
882  const Functor &f,
883  const double &b_scale,
884  const double &e_scale,
885  const double &scale_factor )
886  {
887  //std::cout << "speed" << std::endl;
888  typedef typename Functor::result_type value_type;
889  array3< value_type > in( in2.width( ), in2.height( ), in2.depth( ) );
890  _quantize( in2, in, f );
891  array3< value_type > ref( ref2.width( ), ref2.height( ), ref2.depth( ) );
892  _quantize( ref2, ref, f );
893  return __search( in, ref, x, y, z, scale, similarity, num_of_bins, _functor< value_type, value_type >( ), b_scale, e_scale, scale_factor );
894  }
895 
896  template< typename Array_type, typename Functor >
897  inline bool _search(
898  const Array_type &input,
899  const Array_type &reference,
900  unsigned int &x,
901  unsigned int &y,
902  unsigned int &z,
903  double &scale,
904  double &similarity,
905  double min_scale,
906  double max_scale,
907  const double &scale_factor,
908  const size_t &num_of_bins,
909  const Functor &f,
910  const active_search_style::style &style )
911  {
912  if( scale_factor <= 0.0 || scale_factor == 1.0 )
913  {
914  return false;
915  }
916  const double u_bound = _minimum( static_cast< double >( input.width( ) ) / reference.width( ), _minimum( static_cast< double >( input.height( ) ) / reference.height( ), static_cast< double >( input.depth( ) ) / reference.depth( ) ) );
917  const double l_bound = 0.01;
918  min_scale = ( min_scale < l_bound ) ? l_bound : min_scale;
919  min_scale = ( min_scale > u_bound ) ? u_bound : min_scale;
920  max_scale = ( max_scale < l_bound ) ? l_bound : max_scale;
921  max_scale = ( max_scale > u_bound ) ? u_bound : max_scale;
922  if( min_scale > max_scale )
923  {
924  double tmp = min_scale;
925  min_scale = max_scale;
926  max_scale = tmp;
927  }
928  double begin_scale, end_scale;
929  if( scale_factor > 1.0 )
930  {
931  begin_scale = min_scale;
932  end_scale = max_scale;
933  }
934  else
935  {
936  begin_scale = max_scale;
937  end_scale = min_scale;
938  }
939  if( style == active_search_style::speed )
940  {
941  return _search_speed( input, reference, x, y, z, scale, similarity, num_of_bins, f, begin_scale, end_scale, scale_factor );
942  }
943  if( style == active_search_style::memory )
944  {
945  return _search_memory( input, reference, x, y, z, scale, similarity, num_of_bins, f, begin_scale, end_scale, scale_factor );
946  }
947  return false;
948  }
949 
950 }
951 
952 
953 
954 
955 
977 inline bool active_search(
978  const array2< rgb< unsigned char > > &input,
979  const array2< rgb< unsigned char > > &reference,
980  unsigned int &x,
981  unsigned int &y,
982  double &scale,
983  double &similarity,
984  const double &min_scale,
985  const double &max_scale,
986  const double &scale_factor,
987  size_t num_of_bins2 )
988 {
989  //std::cout << "rgb" << std::endl;
990  typedef _active_search_::_functor< rgb< unsigned char >, unsigned int > functor;
991  num_of_bins2 = ( num_of_bins2 > 256 ) ? 256 : num_of_bins2;
992  const size_t num_of_bins = num_of_bins2 * num_of_bins2 * num_of_bins2;
993  return _active_search_::_search( input, reference, x, y, scale, similarity, min_scale, max_scale, scale_factor, num_of_bins, functor( num_of_bins2 ), active_search_style::speed );
994 }
995 
1014 inline bool active_search(
1015  const array2< rgb< unsigned char > > &input,
1016  const array2< rgb< unsigned char > > &reference,
1017  unsigned int &x,
1018  unsigned int &y,
1019  double &similarity,
1020  const double &scale,
1021  size_t num_of_bins2 )
1022 {
1023  //std::cout << "rgb" << std::endl;
1024  typedef _active_search_::_functor< rgb< unsigned char >, unsigned int > functor;
1025  num_of_bins2 = ( num_of_bins2 > 256 ) ? 256 : num_of_bins2;
1026  const size_t num_of_bins = num_of_bins2 * num_of_bins2 * num_of_bins2;
1027  double tmp;
1028  return _active_search_::_search( input, reference, x, y, tmp, similarity, scale, scale, 2.0, num_of_bins, functor( num_of_bins2 ), active_search_style::speed );
1029 }
1030 
1031 
1032 
1033 
1056 template < typename Value_type, typename Allocator >
1057 inline bool active_search(
1058  const array< Value_type, Allocator > &input,
1059  const array< Value_type, Allocator > &reference,
1060  unsigned int &x,
1061  double &scale,
1062  double &similarity,
1063  const double &min_scale,
1064  const double &max_scale,
1065  const double &scale_factor,
1066  const size_t &num_of_bins )
1067 {
1068  //std::cout << "default" << std::endl;
1069  typedef typename _active_search_::_functor< Value_type, Value_type > functor;
1070  return _active_search_::_search( input, reference, x, scale, similarity, min_scale, max_scale, scale_factor, num_of_bins, functor( ), active_search_style::memory );
1071 }
1072 
1092 template < typename Value_type, typename Allocator >
1093 inline bool active_search(
1094  const array< Value_type, Allocator > &input,
1095  const array< Value_type, Allocator > &reference,
1096  unsigned int &x,
1097  double &similarity,
1098  const double &scale,
1099  const size_t &num_of_bins )
1100 {
1101  //std::cout << "default" << std::endl;
1102  typedef typename _active_search_::_functor< Value_type, Value_type > functor;
1103  double tmp;
1104  return _active_search_::_search( input, reference, x, tmp, similarity, scale, scale, 2.0, num_of_bins, functor( ), active_search_style::memory );
1105 }
1106 
1133 template < typename Value_type, typename Allocator, typename Functor >
1134 inline bool active_search(
1135  const array< Value_type, Allocator > &input,
1136  const array< Value_type, Allocator > &reference,
1137  unsigned int &x,
1138  double &scale,
1139  double &similarity,
1140  const double &min_scale,
1141  const double &max_scale,
1142  const double &scale_factor,
1143  const size_t &num_of_bins,
1144  const Functor &f,
1145  const active_search_style::style &style = active_search_style::memory )
1146 {
1147  //std::cout << "functor" << std::endl;
1148  return _active_search_::_search( input, reference, x, scale, similarity, min_scale, max_scale, scale_factor, num_of_bins, f, style );
1149 }
1150 
1174 template < typename Value_type, typename Allocator, typename Functor >
1175 inline bool active_search(
1176  const array< Value_type, Allocator > &input,
1177  const array< Value_type, Allocator > &reference,
1178  unsigned int &x,
1179  double &similarity,
1180  const double &scale,
1181  const size_t &num_of_bins,
1182  const Functor &f,
1183  const active_search_style::style &style = active_search_style::memory )
1184 {
1185  //std::cout << "functor" << std::endl;
1186  double tmp;
1187  return _active_search_::_search( input, reference, x, tmp, similarity, scale, scale, 2.0, num_of_bins, f, style );
1188 }
1189 
1190 
1191 
1192 
1215 template < typename Value_type, typename Allocator >
1216 inline bool active_search(
1217  const array1< Value_type, Allocator > &input,
1218  const array1< Value_type, Allocator > &reference,
1219  unsigned int &x,
1220  double &scale,
1221  double &similarity,
1222  const double &min_scale,
1223  const double &max_scale,
1224  const double &scale_factor,
1225  const size_t &num_of_bins )
1226 {
1227  //std::cout << "default" << std::endl;
1228  typedef typename _active_search_::_functor< Value_type, Value_type > functor;
1229  return _active_search_::_search( input, reference, x, scale, similarity, min_scale, max_scale, scale_factor, num_of_bins, functor( ), active_search_style::memory );
1230 }
1231 
1251 template < typename Value_type, typename Allocator >
1252 inline bool active_search(
1253  const array1< Value_type, Allocator > &input,
1254  const array1< Value_type, Allocator > &reference,
1255  unsigned int &x,
1256  double &similarity,
1257  const double &scale,
1258  const size_t &num_of_bins )
1259 {
1260  //std::cout << "default" << std::endl;
1261  typedef typename _active_search_::_functor< Value_type, Value_type > functor;
1262  double tmp;
1263  return _active_search_::_search( input, reference, x, tmp, similarity, scale, scale, 2.0, num_of_bins, functor( ), active_search_style::memory );
1264 }
1265 
1292 template < typename Value_type, typename Allocator, typename Functor >
1293 inline bool active_search(
1294  const array1< Value_type, Allocator > &input,
1295  const array1< Value_type, Allocator > &reference,
1296  unsigned int &x,
1297  double &scale,
1298  double &similarity,
1299  const double &min_scale,
1300  const double &max_scale,
1301  const double &scale_factor,
1302  const size_t &num_of_bins,
1303  const Functor &f,
1304  const active_search_style::style &style = active_search_style::memory )
1305 {
1306  //std::cout << "functor" << std::endl;
1307  return _active_search_::_search( input, reference, x, scale, similarity, min_scale, max_scale, scale_factor, num_of_bins, f, style );
1308 }
1309 
1333 template < typename Value_type, typename Allocator, typename Functor >
1334 inline bool active_search(
1335  const array1< Value_type, Allocator > &input,
1336  const array1< Value_type, Allocator > &reference,
1337  unsigned int &x,
1338  double &similarity,
1339  const double &scale,
1340  const size_t &num_of_bins,
1341  const Functor &f,
1342  const active_search_style::style &style = active_search_style::memory )
1343 {
1344  //std::cout << "functor" << std::endl;
1345  double tmp;
1346  return _active_search_::_search( input, reference, x, tmp, similarity, scale, scale, 2.0, num_of_bins, f, style );
1347 }
1348 
1349 
1350 
1351 
1375 template < typename Value_type, typename Allocator >
1376 inline bool active_search(
1377  const array2< Value_type, Allocator > &input,
1378  const array2< Value_type, Allocator > &reference,
1379  unsigned int &x,
1380  unsigned int &y,
1381  double &scale,
1382  double &similarity,
1383  const double &min_scale,
1384  const double &max_scale,
1385  const double &scale_factor,
1386  const size_t &num_of_bins )
1387 {
1388  //std::cout << "default" << std::endl;
1389  typedef typename _active_search_::_functor< Value_type, Value_type > functor;
1390  return _active_search_::_search( input, reference, x, y, scale, similarity, min_scale, max_scale, scale_factor, num_of_bins, functor( ), active_search_style::memory );
1391 }
1392 
1413 template < typename Value_type, typename Allocator >
1414 inline bool active_search(
1415  const array2< Value_type, Allocator > &input,
1416  const array2< Value_type, Allocator > &reference,
1417  unsigned int &x,
1418  unsigned int &y,
1419  double &similarity,
1420  const double &scale,
1421  const size_t &num_of_bins )
1422 {
1423  //std::cout << "default" << std::endl;
1424  typedef typename _active_search_::_functor< Value_type, Value_type > functor;
1425  double tmp;
1426  return _active_search_::_search( input, reference, x, y, tmp, similarity, scale, scale, 2.0, num_of_bins, functor( ), active_search_style::memory );
1427 }
1428 
1456 template < typename Value_type, typename Allocator, typename Functor >
1457 inline bool active_search(
1458  const array2< Value_type, Allocator > &input,
1459  const array2< Value_type, Allocator > &reference,
1460  unsigned int &x,
1461  unsigned int &y,
1462  double &scale,
1463  double &similarity,
1464  const double &min_scale,
1465  const double &max_scale,
1466  const double &scale_factor,
1467  const size_t &num_of_bins,
1468  const Functor &f,
1469  const active_search_style::style &style = active_search_style::memory )
1470 {
1471  //std::cout << "functor" << std::endl;
1472  return _active_search_::_search( input, reference, x, y, scale, similarity, min_scale, max_scale, scale_factor, num_of_bins, f, style );
1473 }
1474 
1499 template < typename Value_type, typename Allocator, typename Functor >
1500 inline bool active_search(
1501  const array2< Value_type, Allocator > &input,
1502  const array2< Value_type, Allocator > &reference,
1503  unsigned int &x,
1504  unsigned int &y,
1505  double &similarity,
1506  const double &scale,
1507  const size_t &num_of_bins,
1508  const Functor &f,
1509  const active_search_style::style &style = active_search_style::memory )
1510 {
1511  //std::cout << "functor" << std::endl;
1512  double tmp;
1513  return _active_search_::_search( input, reference, x, y, tmp, similarity, scale, scale, 2.0, num_of_bins, f, style );
1514 }
1515 
1516 
1517 
1518 
1543 template < typename Value_type, typename Allocator >
1544 inline bool active_search(
1545  const array3< Value_type, Allocator > &input,
1546  const array3< Value_type, Allocator > &reference,
1547  unsigned int &x,
1548  unsigned int &y,
1549  unsigned int &z,
1550  double &scale,
1551  double &similarity,
1552  const double &min_scale,
1553  const double &max_scale,
1554  const double &scale_factor,
1555  const size_t &num_of_bins )
1556 {
1557  //std::cout << "default" << std::endl;
1558  typedef typename _active_search_::_functor< Value_type, Value_type > functor;
1559  return _active_search_::_search( input, reference, x, y, z, scale, similarity, min_scale, max_scale, scale_factor, num_of_bins, functor( ), active_search_style::memory );
1560 }
1561 
1583 template < typename Value_type, typename Allocator >
1584 inline bool active_search(
1585  const array3< Value_type, Allocator > &input,
1586  const array3< Value_type, Allocator > &reference,
1587  unsigned int &x,
1588  unsigned int &y,
1589  unsigned int &z,
1590  double &similarity,
1591  const double &scale,
1592  const size_t &num_of_bins )
1593 {
1594  //std::cout << "default" << std::endl;
1595  typedef typename _active_search_::_functor< Value_type, Value_type > functor;
1596  double tmp;
1597  return _active_search_::_search( input, reference, x, y, z, tmp, similarity, scale, scale, 2.0, num_of_bins, functor( ), active_search_style::memory );
1598 }
1599 
1628 template < typename Value_type, typename Allocator, typename Functor >
1629 inline bool active_search(
1630  const array3< Value_type, Allocator > &input,
1631  const array3< Value_type, Allocator > &reference,
1632  unsigned int &x,
1633  unsigned int &y,
1634  unsigned int &z,
1635  double &scale,
1636  double &similarity,
1637  const double &min_scale,
1638  const double &max_scale,
1639  const double &scale_factor,
1640  const size_t &num_of_bins,
1641  const Functor &f,
1642  const active_search_style::style &style = active_search_style::memory )
1643 {
1644  //std::cout << "functor" << std::endl;
1645  return _active_search_::_search( input, reference, x, y, z, scale, similarity, min_scale, max_scale, scale_factor, num_of_bins, f, style );
1646 }
1647 
1673 template < typename Value_type, typename Allocator, typename Functor >
1674 inline bool active_search(
1675  const array3< Value_type, Allocator > &input,
1676  const array3< Value_type, Allocator > &reference,
1677  unsigned int &x,
1678  unsigned int &y,
1679  unsigned int &z,
1680  double &similarity,
1681  const double &scale,
1682  const size_t &num_of_bins,
1683  const Functor &f,
1684  const active_search_style::style &style = active_search_style::memory )
1685 {
1686  //std::cout << "functor" << std::endl;
1687  double tmp;
1688  return _active_search_::_search( input, reference, x, y, z, tmp, similarity, scale, scale, 2.0, num_of_bins, f, style );
1689 }
1690 
1691 
1693 // Active Search グループの終わり
1694 
1695 
1696 // mist名前空間の終わり
1697 _MIST_END
1698 
1699 
1700 #endif // #ifdef __INCLUDE_ACTIVE_SEARCH_H__
1701 
Generated on Wed Nov 12 2014 19:44:13 for MIST by doxygen 1.8.1.2