1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
22 // * Redistribution's in binary form must reproduce the above copyright notice,
23 // this list of conditions and the following disclaimer in the documentation
24 // and/or other materials provided with the distribution.
26 // * The name of Intel Corporation may not be used to endorse or promote products
27 // derived from this software without specific prior written permission.
29 // This software is provided by the copyright holders and contributors "as is" and
30 // any express or implied warranties, including, but not limited to, the implied
31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
32 // In no event shall the Intel Corporation or contributors be liable for any direct,
33 // indirect, incidental, special, exemplary, or consequential damages
34 // (including, but not limited to, procurement of substitute goods or services;
35 // loss of use, data, or profits; or business interruption) however caused
36 // and on any theory of liability, whether in contract, strict liability,
37 // or tort (including negligence or otherwise) arising in any way out of
38 // the use of this software, even if advised of the possibility of such damage.
43 * cvhaarclassifier.cpp
45 * haar classifiers (stump, CART, stage, cascade)
48 #include "_cvhaartraining.h"
51 CvIntHaarClassifier* icvCreateCARTHaarClassifier( int count )
53 CvCARTHaarClassifier* cart;
56 datasize = sizeof( *cart ) +
58 sizeof( CvTHaarFeature ) + sizeof( CvFastHaarFeature ) +
59 sizeof( float ) + sizeof( int ) + sizeof( int ) ) * count +
60 sizeof( float ) * (count + 1);
62 cart = (CvCARTHaarClassifier*) cvAlloc( datasize );
63 memset( cart, 0, datasize );
65 cart->feature = (CvTHaarFeature*) (cart + 1);
66 cart->fastfeature = (CvFastHaarFeature*) (cart->feature + count);
67 cart->threshold = (float*) (cart->fastfeature + count);
68 cart->left = (int*) (cart->threshold + count);
69 cart->right = (int*) (cart->left + count);
70 cart->val = (float*) (cart->right + count);
71 cart->compidx = (int*) (cart->val + count + 1 );
73 cart->eval = icvEvalCARTHaarClassifier;
74 cart->save = icvSaveCARTHaarClassifier;
75 cart->release = icvReleaseHaarClassifier;
77 return (CvIntHaarClassifier*) cart;
81 void icvReleaseHaarClassifier( CvIntHaarClassifier** classifier )
88 void icvInitCARTHaarClassifier( CvCARTHaarClassifier* carthaar, CvCARTClassifier* cart,
89 CvIntHaarFeatures* intHaarFeatures )
93 for( i = 0; i < cart->count; i++ )
95 carthaar->feature[i] = intHaarFeatures->feature[cart->compidx[i]];
96 carthaar->fastfeature[i] = intHaarFeatures->fastfeature[cart->compidx[i]];
97 carthaar->threshold[i] = cart->threshold[i];
98 carthaar->left[i] = cart->left[i];
99 carthaar->right[i] = cart->right[i];
100 carthaar->val[i] = cart->val[i];
101 carthaar->compidx[i] = cart->compidx[i];
103 carthaar->count = cart->count;
104 carthaar->val[cart->count] = cart->val[cart->count];
108 float icvEvalCARTHaarClassifier( CvIntHaarClassifier* classifier,
109 sum_type* sum, sum_type* tilted, float normfactor )
115 if( cvEvalFastHaarFeature(
116 ((CvCARTHaarClassifier*) classifier)->fastfeature + idx, sum, tilted )
117 < (((CvCARTHaarClassifier*) classifier)->threshold[idx] * normfactor) )
119 idx = ((CvCARTHaarClassifier*) classifier)->left[idx];
123 idx = ((CvCARTHaarClassifier*) classifier)->right[idx];
127 return ((CvCARTHaarClassifier*) classifier)->val[-idx];
131 CvIntHaarClassifier* icvCreateStageHaarClassifier( int count, float threshold )
133 CvStageHaarClassifier* stage;
136 datasize = sizeof( *stage ) + sizeof( CvIntHaarClassifier* ) * count;
137 stage = (CvStageHaarClassifier*) cvAlloc( datasize );
138 memset( stage, 0, datasize );
140 stage->count = count;
141 stage->threshold = threshold;
142 stage->classifier = (CvIntHaarClassifier**) (stage + 1);
144 stage->eval = icvEvalStageHaarClassifier;
145 stage->save = icvSaveStageHaarClassifier;
146 stage->release = icvReleaseStageHaarClassifier;
148 return (CvIntHaarClassifier*) stage;
152 void icvReleaseStageHaarClassifier( CvIntHaarClassifier** classifier )
156 for( i = 0; i < ((CvStageHaarClassifier*) *classifier)->count; i++ )
158 if( ((CvStageHaarClassifier*) *classifier)->classifier[i] != NULL )
160 ((CvStageHaarClassifier*) *classifier)->classifier[i]->release(
161 &(((CvStageHaarClassifier*) *classifier)->classifier[i]) );
165 cvFree( classifier );
170 float icvEvalStageHaarClassifier( CvIntHaarClassifier* classifier,
171 sum_type* sum, sum_type* tilted, float normfactor )
177 for( i = 0; i < ((CvStageHaarClassifier*) classifier)->count; i++ )
180 ((CvStageHaarClassifier*) classifier)->classifier[i]->eval(
181 ((CvStageHaarClassifier*) classifier)->classifier[i],
182 sum, tilted, normfactor );
189 CvIntHaarClassifier* icvCreateCascadeHaarClassifier( int count )
191 CvCascadeHaarClassifier* ptr;
194 datasize = sizeof( *ptr ) + sizeof( CvIntHaarClassifier* ) * count;
195 ptr = (CvCascadeHaarClassifier*) cvAlloc( datasize );
196 memset( ptr, 0, datasize );
199 ptr->classifier = (CvIntHaarClassifier**) (ptr + 1);
201 ptr->eval = icvEvalCascadeHaarClassifier;
203 ptr->release = icvReleaseCascadeHaarClassifier;
205 return (CvIntHaarClassifier*) ptr;
209 void icvReleaseCascadeHaarClassifier( CvIntHaarClassifier** classifier )
213 for( i = 0; i < ((CvCascadeHaarClassifier*) *classifier)->count; i++ )
215 if( ((CvCascadeHaarClassifier*) *classifier)->classifier[i] != NULL )
217 ((CvCascadeHaarClassifier*) *classifier)->classifier[i]->release(
218 &(((CvCascadeHaarClassifier*) *classifier)->classifier[i]) );
222 cvFree( classifier );
227 float icvEvalCascadeHaarClassifier( CvIntHaarClassifier* classifier,
228 sum_type* sum, sum_type* tilted, float normfactor )
232 for( i = 0; i < ((CvCascadeHaarClassifier*) classifier)->count; i++ )
234 if( ((CvCascadeHaarClassifier*) classifier)->classifier[i]->eval(
235 ((CvCascadeHaarClassifier*) classifier)->classifier[i],
236 sum, tilted, normfactor )
237 < ( ((CvStageHaarClassifier*)
238 ((CvCascadeHaarClassifier*) classifier)->classifier[i])->threshold
239 - CV_THRESHOLD_EPS) )
249 void icvSaveHaarFeature( CvTHaarFeature* feature, FILE* file )
251 fprintf( file, "%d\n", ( ( feature->rect[2].weight == 0.0F ) ? 2 : 3) );
252 fprintf( file, "%d %d %d %d %d %d\n",
253 feature->rect[0].r.x,
254 feature->rect[0].r.y,
255 feature->rect[0].r.width,
256 feature->rect[0].r.height,
258 (int) (feature->rect[0].weight) );
259 fprintf( file, "%d %d %d %d %d %d\n",
260 feature->rect[1].r.x,
261 feature->rect[1].r.y,
262 feature->rect[1].r.width,
263 feature->rect[1].r.height,
265 (int) (feature->rect[1].weight) );
266 if( feature->rect[2].weight != 0.0F )
268 fprintf( file, "%d %d %d %d %d %d\n",
269 feature->rect[2].r.x,
270 feature->rect[2].r.y,
271 feature->rect[2].r.width,
272 feature->rect[2].r.height,
274 (int) (feature->rect[2].weight) );
276 fprintf( file, "%s\n", &(feature->desc[0]) );
280 void icvLoadHaarFeature( CvTHaarFeature* feature, FILE* file )
288 int values_read = fscanf( file, "%d", &nrect );
289 CV_Assert(values_read == 1);
291 assert( nrect <= CV_HAAR_FEATURE_MAX );
293 for( j = 0; j < nrect; j++ )
295 values_read = fscanf( file, "%d %d %d %d %d %d",
296 &(feature->rect[j].r.x),
297 &(feature->rect[j].r.y),
298 &(feature->rect[j].r.width),
299 &(feature->rect[j].r.height),
301 CV_Assert(values_read == 6);
302 feature->rect[j].weight = (float) weight;
304 for( j = nrect; j < CV_HAAR_FEATURE_MAX; j++ )
306 feature->rect[j].r.x = 0;
307 feature->rect[j].r.y = 0;
308 feature->rect[j].r.width = 0;
309 feature->rect[j].r.height = 0;
310 feature->rect[j].weight = 0.0f;
312 values_read = fscanf( file, "%s", &(feature->desc[0]) );
313 CV_Assert(values_read == 1);
314 feature->tilted = ( feature->desc[0] == 't' );
318 void icvSaveCARTHaarClassifier( CvIntHaarClassifier* classifier, FILE* file )
323 count = ((CvCARTHaarClassifier*) classifier)->count;
324 fprintf( file, "%d\n", count );
325 for( i = 0; i < count; i++ )
327 icvSaveHaarFeature( &(((CvCARTHaarClassifier*) classifier)->feature[i]), file );
328 fprintf( file, "%e %d %d\n",
329 ((CvCARTHaarClassifier*) classifier)->threshold[i],
330 ((CvCARTHaarClassifier*) classifier)->left[i],
331 ((CvCARTHaarClassifier*) classifier)->right[i] );
333 for( i = 0; i <= count; i++ )
335 fprintf( file, "%e ", ((CvCARTHaarClassifier*) classifier)->val[i] );
337 fprintf( file, "\n" );
341 CvIntHaarClassifier* icvLoadCARTHaarClassifier( FILE* file, int step )
343 CvCARTHaarClassifier* ptr;
348 int values_read = fscanf( file, "%d", &count );
349 CV_Assert(values_read == 1);
353 ptr = (CvCARTHaarClassifier*) icvCreateCARTHaarClassifier( count );
354 for( i = 0; i < count; i++ )
356 icvLoadHaarFeature( &(ptr->feature[i]), file );
357 values_read = fscanf( file, "%f %d %d", &(ptr->threshold[i]), &(ptr->left[i]),
359 CV_Assert(values_read == 3);
361 for( i = 0; i <= count; i++ )
363 values_read = fscanf( file, "%f", &(ptr->val[i]) );
364 CV_Assert(values_read == 1);
366 icvConvertToFastHaarFeature( ptr->feature, ptr->fastfeature, ptr->count, step );
369 return (CvIntHaarClassifier*) ptr;
373 void icvSaveStageHaarClassifier( CvIntHaarClassifier* classifier, FILE* file )
379 count = ((CvStageHaarClassifier*) classifier)->count;
380 fprintf( file, "%d\n", count );
381 for( i = 0; i < count; i++ )
383 ((CvStageHaarClassifier*) classifier)->classifier[i]->save(
384 ((CvStageHaarClassifier*) classifier)->classifier[i], file );
387 threshold = ((CvStageHaarClassifier*) classifier)->threshold;
389 /* to be compatible with the previous implementation */
390 /* threshold = 2.0F * ((CvStageHaarClassifier*) classifier)->threshold - count; */
392 fprintf( file, "%e\n", threshold );
397 static CvIntHaarClassifier* icvLoadCARTStageHaarClassifierF( FILE* file, int step )
399 CvStageHaarClassifier* ptr = NULL;
401 //CV_FUNCNAME( "icvLoadCARTStageHaarClassifierF" );
412 int values_read = fscanf( file, "%d", &count );
413 CV_Assert(values_read == 1);
416 ptr = (CvStageHaarClassifier*) icvCreateStageHaarClassifier( count, 0.0F );
417 for( i = 0; i < count; i++ )
419 ptr->classifier[i] = icvLoadCARTHaarClassifier( file, step );
422 values_read = fscanf( file, "%f", &threshold );
423 CV_Assert(values_read == 1);
425 ptr->threshold = threshold;
426 /* to be compatible with the previous implementation */
427 /* ptr->threshold = 0.5F * (threshold + count); */
431 ptr->release( (CvIntHaarClassifier**) &ptr );
438 return (CvIntHaarClassifier*) ptr;
442 CvIntHaarClassifier* icvLoadCARTStageHaarClassifier( const char* filename, int step )
444 CvIntHaarClassifier* ptr = NULL;
446 CV_FUNCNAME( "icvLoadCARTStageHaarClassifier" );
452 file = fopen( filename, "r" );
455 CV_CALL( ptr = icvLoadCARTStageHaarClassifierF( file, step ) );
464 /* tree cascade classifier */
466 /* evaluates a tree cascade classifier */
468 float icvEvalTreeCascadeClassifier( CvIntHaarClassifier* classifier,
469 sum_type* sum, sum_type* tilted, float normfactor )
471 CvTreeCascadeNode* ptr;
473 ptr = ((CvTreeCascadeClassifier*) classifier)->root;
477 if( ptr->stage->eval( (CvIntHaarClassifier*) ptr->stage,
478 sum, tilted, normfactor )
479 >= ptr->stage->threshold - CV_THRESHOLD_EPS )
485 while( ptr && ptr->next == NULL ) ptr = ptr->parent;
486 if( ptr == NULL ) return 0.0F;
494 /* sets path int the tree form the root to the leaf node */
496 void icvSetLeafNode( CvTreeCascadeClassifier* tcc, CvTreeCascadeNode* leaf )
498 CV_FUNCNAME( "icvSetLeafNode" );
502 CvTreeCascadeNode* ptr;
507 leaf->child_eval = ptr;
513 while( leaf && leaf != ptr ) leaf = leaf->next;
515 CV_ERROR( CV_StsError, "Invalid tcc or leaf node." );
517 tcc->root_eval = ptr;
522 /* evaluates a tree cascade classifier. used in filtering */
524 float icvEvalTreeCascadeClassifierFilter( CvIntHaarClassifier* classifier, sum_type* sum,
525 sum_type* tilted, float normfactor )
527 CvTreeCascadeNode* ptr;
528 //CvTreeCascadeClassifier* tree;
530 //tree = (CvTreeCascadeClassifier*) classifier;
534 ptr = ((CvTreeCascadeClassifier*) classifier)->root_eval;
537 if( ptr->stage->eval( (CvIntHaarClassifier*) ptr->stage,
538 sum, tilted, normfactor )
539 < ptr->stage->threshold - CV_THRESHOLD_EPS )
543 ptr = ptr->child_eval;
549 /* creates tree cascade node */
551 CvTreeCascadeNode* icvCreateTreeCascadeNode()
553 CvTreeCascadeNode* ptr = NULL;
555 CV_FUNCNAME( "icvCreateTreeCascadeNode" );
560 data_size = sizeof( *ptr );
561 CV_CALL( ptr = (CvTreeCascadeNode*) cvAlloc( data_size ) );
562 memset( ptr, 0, data_size );
569 /* releases all tree cascade nodes accessible via links */
571 void icvReleaseTreeCascadeNodes( CvTreeCascadeNode** node )
573 //CV_FUNCNAME( "icvReleaseTreeCascadeNodes" );
579 CvTreeCascadeNode* ptr;
580 CvTreeCascadeNode* ptr_;
586 while( ptr->child ) ptr = ptr->child;
588 if( ptr->stage ) ptr->stage->release( (CvIntHaarClassifier**) &ptr->stage );
591 while( ptr && ptr->next == NULL ) ptr = ptr->parent;
592 if( ptr ) ptr = ptr->next;
602 /* releases tree cascade classifier */
604 void icvReleaseTreeCascadeClassifier( CvIntHaarClassifier** classifier )
606 if( classifier && *classifier )
608 icvReleaseTreeCascadeNodes( &((CvTreeCascadeClassifier*) *classifier)->root );
609 cvFree( classifier );
615 void icvPrintTreeCascade( CvTreeCascadeNode* root )
617 //CV_FUNCNAME( "icvPrintTreeCascade" );
621 CvTreeCascadeNode* node;
622 CvTreeCascadeNode* n;
630 level = max_level = 0;
633 while( node->child ) { node = node->child; level++; }
634 if( level > max_level ) { max_level = level; }
635 while( node && !node->next ) { node = node->parent; level--; }
636 if( node ) node = node->next;
639 printf( "\nTree Classifier\n" );
641 for( i = 0; i <= max_level; i++ ) printf( "+---" );
643 for( i = 0; i <= max_level; i++ ) printf( "|%3d", i );
645 for( i = 0; i <= max_level; i++ ) printf( "+---" );
653 sprintf( buf + strlen( buf ), "%3d", node->idx );
657 sprintf( buf + strlen( buf ),
658 ((node->idx < 10) ? "---%d" : ((node->idx < 100) ? "--%d" : "-%d")),
661 printf( " %s\n", buf );
663 while( node && !node->next ) { node = node->parent; }
673 sprintf( buf0, " | %s", buf );
675 sprintf( buf0, " %s", buf );
679 printf( " %s |\n", buf );
690 CvIntHaarClassifier* icvLoadTreeCascadeClassifier( const char* filename, int step,
693 CvTreeCascadeClassifier* ptr = NULL;
694 CvTreeCascadeNode** nodes = NULL;
696 CV_FUNCNAME( "icvLoadTreeCascadeClassifier" );
701 CvStageHaarClassifier* stage;
702 char stage_name[PATH_MAX];
706 int result, parent=0, next=0;
709 if( !splits ) splits = &stub;
713 data_size = sizeof( *ptr );
715 CV_CALL( ptr = (CvTreeCascadeClassifier*) cvAlloc( data_size ) );
716 memset( ptr, 0, data_size );
718 ptr->eval = icvEvalTreeCascadeClassifier;
719 ptr->release = icvReleaseTreeCascadeClassifier;
721 sprintf( stage_name, "%s/", filename );
722 suffix = stage_name + strlen( stage_name );
726 sprintf( suffix, "%d/%s", i, CV_STAGE_CART_FILE_NAME );
727 f = fopen( stage_name, "r" );
735 data_size = sizeof( *nodes ) * num;
736 CV_CALL( nodes = (CvTreeCascadeNode**) cvAlloc( data_size ) );
738 for( i = 0; i < num; i++ )
740 sprintf( suffix, "%d/%s", i, CV_STAGE_CART_FILE_NAME );
741 f = fopen( stage_name, "r" );
742 CV_CALL( stage = (CvStageHaarClassifier*)
743 icvLoadCARTStageHaarClassifierF( f, step ) );
745 result = ( f && stage ) ? fscanf( f, "%d%d", &parent, &next ) : 0;
754 printf( "Stage %d loaded\n", i );
756 if( parent >= i || (next != -1 && next != i + 1) )
757 CV_ERROR( CV_StsError, "Invalid tree links" );
759 CV_CALL( nodes[i] = icvCreateTreeCascadeNode() );
760 nodes[i]->stage = stage;
762 nodes[i]->parent = (parent != -1 ) ? nodes[parent] : NULL;
763 nodes[i]->next = ( next != -1 ) ? nodes[i] : NULL;
764 nodes[i]->child = NULL;
766 for( i = 0; i < num; i++ )
771 nodes[i]->next = nodes[i+1];
773 if( nodes[i]->parent && nodes[i]->parent->child == NULL )
775 nodes[i]->parent->child = nodes[i];
778 ptr->root = nodes[0];
785 return (CvIntHaarClassifier*) ptr;
789 CvTreeCascadeNode* icvFindDeepestLeaves( CvTreeCascadeClassifier* tcc )
791 CvTreeCascadeNode* leaves;
793 //CV_FUNCNAME( "icvFindDeepestLeaves" );
797 int level, cur_level;
798 CvTreeCascadeNode* ptr;
799 CvTreeCascadeNode* last;
801 leaves = last = NULL;
807 /* find leaves with maximal level */
810 if( ptr->child ) { ptr = ptr->child; cur_level++; }
813 if( cur_level == level )
815 last->next_same_level = ptr;
816 ptr->next_same_level = NULL;
819 if( cur_level > level )
823 ptr->next_same_level = NULL;
825 while( ptr && ptr->next == NULL ) { ptr = ptr->parent; cur_level--; }
826 if( ptr ) ptr = ptr->next;