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

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

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