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 fscanf( file, "%d", &nrect );
290 assert( nrect <= CV_HAAR_FEATURE_MAX );
292 for( j = 0; j < nrect; j++ )
294 fscanf( file, "%d %d %d %d %d %d",
295 &(feature->rect[j].r.x),
296 &(feature->rect[j].r.y),
297 &(feature->rect[j].r.width),
298 &(feature->rect[j].r.height),
300 feature->rect[j].weight = (float) weight;
302 for( j = nrect; j < CV_HAAR_FEATURE_MAX; j++ )
304 feature->rect[j].r.x = 0;
305 feature->rect[j].r.y = 0;
306 feature->rect[j].r.width = 0;
307 feature->rect[j].r.height = 0;
308 feature->rect[j].weight = 0.0f;
310 fscanf( file, "%s", &(feature->desc[0]) );
311 feature->tilted = ( feature->desc[0] == 't' );
315 void icvSaveCARTHaarClassifier( CvIntHaarClassifier* classifier, FILE* file )
320 count = ((CvCARTHaarClassifier*) classifier)->count;
321 fprintf( file, "%d\n", count );
322 for( i = 0; i < count; i++ )
324 icvSaveHaarFeature( &(((CvCARTHaarClassifier*) classifier)->feature[i]), file );
325 fprintf( file, "%e %d %d\n",
326 ((CvCARTHaarClassifier*) classifier)->threshold[i],
327 ((CvCARTHaarClassifier*) classifier)->left[i],
328 ((CvCARTHaarClassifier*) classifier)->right[i] );
330 for( i = 0; i <= count; i++ )
332 fprintf( file, "%e ", ((CvCARTHaarClassifier*) classifier)->val[i] );
334 fprintf( file, "\n" );
338 CvIntHaarClassifier* icvLoadCARTHaarClassifier( FILE* file, int step )
340 CvCARTHaarClassifier* ptr;
345 fscanf( file, "%d", &count );
348 ptr = (CvCARTHaarClassifier*) icvCreateCARTHaarClassifier( count );
349 for( i = 0; i < count; i++ )
351 icvLoadHaarFeature( &(ptr->feature[i]), file );
352 fscanf( file, "%f %d %d", &(ptr->threshold[i]), &(ptr->left[i]),
355 for( i = 0; i <= count; i++ )
357 fscanf( file, "%f", &(ptr->val[i]) );
359 icvConvertToFastHaarFeature( ptr->feature, ptr->fastfeature, ptr->count, step );
362 return (CvIntHaarClassifier*) ptr;
366 void icvSaveStageHaarClassifier( CvIntHaarClassifier* classifier, FILE* file )
372 count = ((CvStageHaarClassifier*) classifier)->count;
373 fprintf( file, "%d\n", count );
374 for( i = 0; i < count; i++ )
376 ((CvStageHaarClassifier*) classifier)->classifier[i]->save(
377 ((CvStageHaarClassifier*) classifier)->classifier[i], file );
380 threshold = ((CvStageHaarClassifier*) classifier)->threshold;
382 /* to be compatible with the previous implementation */
383 /* threshold = 2.0F * ((CvStageHaarClassifier*) classifier)->threshold - count; */
385 fprintf( file, "%e\n", threshold );
390 CvIntHaarClassifier* icvLoadCARTStageHaarClassifierF( FILE* file, int step )
392 CvStageHaarClassifier* ptr = NULL;
394 //CV_FUNCNAME( "icvLoadCARTStageHaarClassifierF" );
405 fscanf( file, "%d", &count );
408 ptr = (CvStageHaarClassifier*) icvCreateStageHaarClassifier( count, 0.0F );
409 for( i = 0; i < count; i++ )
411 ptr->classifier[i] = icvLoadCARTHaarClassifier( file, step );
414 fscanf( file, "%f", &threshold );
416 ptr->threshold = threshold;
417 /* to be compatible with the previous implementation */
418 /* ptr->threshold = 0.5F * (threshold + count); */
422 ptr->release( (CvIntHaarClassifier**) &ptr );
429 return (CvIntHaarClassifier*) ptr;
433 CvIntHaarClassifier* icvLoadCARTStageHaarClassifier( const char* filename, int step )
435 CvIntHaarClassifier* ptr = NULL;
437 CV_FUNCNAME( "icvLoadCARTStageHaarClassifier" );
443 file = fopen( filename, "r" );
446 CV_CALL( ptr = icvLoadCARTStageHaarClassifierF( file, step ) );
455 /* tree cascade classifier */
457 /* evaluates a tree cascade classifier */
459 float icvEvalTreeCascadeClassifier( CvIntHaarClassifier* classifier,
460 sum_type* sum, sum_type* tilted, float normfactor )
462 CvTreeCascadeNode* ptr;
464 ptr = ((CvTreeCascadeClassifier*) classifier)->root;
468 if( ptr->stage->eval( (CvIntHaarClassifier*) ptr->stage,
469 sum, tilted, normfactor )
470 >= ptr->stage->threshold - CV_THRESHOLD_EPS )
476 while( ptr && ptr->next == NULL ) ptr = ptr->parent;
477 if( ptr == NULL ) return 0.0F;
485 /* sets path int the tree form the root to the leaf node */
487 void icvSetLeafNode( CvTreeCascadeClassifier* tcc, CvTreeCascadeNode* leaf )
489 CV_FUNCNAME( "icvSetLeafNode" );
493 CvTreeCascadeNode* ptr;
498 leaf->child_eval = ptr;
504 while( leaf && leaf != ptr ) leaf = leaf->next;
506 CV_ERROR( CV_StsError, "Invalid tcc or leaf node." );
508 tcc->root_eval = ptr;
513 /* evaluates a tree cascade classifier. used in filtering */
515 float icvEvalTreeCascadeClassifierFilter( CvIntHaarClassifier* classifier, sum_type* sum,
516 sum_type* tilted, float normfactor )
518 CvTreeCascadeNode* ptr;
519 CvTreeCascadeClassifier* tree;
521 tree = (CvTreeCascadeClassifier*) classifier;
525 ptr = ((CvTreeCascadeClassifier*) classifier)->root_eval;
528 if( ptr->stage->eval( (CvIntHaarClassifier*) ptr->stage,
529 sum, tilted, normfactor )
530 < ptr->stage->threshold - CV_THRESHOLD_EPS )
534 ptr = ptr->child_eval;
540 /* creates tree cascade node */
542 CvTreeCascadeNode* icvCreateTreeCascadeNode()
544 CvTreeCascadeNode* ptr = NULL;
546 CV_FUNCNAME( "icvCreateTreeCascadeNode" );
551 data_size = sizeof( *ptr );
552 CV_CALL( ptr = (CvTreeCascadeNode*) cvAlloc( data_size ) );
553 memset( ptr, 0, data_size );
560 /* releases all tree cascade nodes accessible via links */
562 void icvReleaseTreeCascadeNodes( CvTreeCascadeNode** node )
564 //CV_FUNCNAME( "icvReleaseTreeCascadeNodes" );
570 CvTreeCascadeNode* ptr;
571 CvTreeCascadeNode* ptr_;
577 while( ptr->child ) ptr = ptr->child;
579 if( ptr->stage ) ptr->stage->release( (CvIntHaarClassifier**) &ptr->stage );
582 while( ptr && ptr->next == NULL ) ptr = ptr->parent;
583 if( ptr ) ptr = ptr->next;
593 /* releases tree cascade classifier */
595 void icvReleaseTreeCascadeClassifier( CvIntHaarClassifier** classifier )
597 if( classifier && *classifier )
599 icvReleaseTreeCascadeNodes( &((CvTreeCascadeClassifier*) *classifier)->root );
600 cvFree( classifier );
606 void icvPrintTreeCascade( CvTreeCascadeNode* root )
608 //CV_FUNCNAME( "icvPrintTreeCascade" );
612 CvTreeCascadeNode* node;
613 CvTreeCascadeNode* n;
621 level = max_level = 0;
624 while( node->child ) { node = node->child; level++; }
625 if( level > max_level ) { max_level = level; }
626 while( node && !node->next ) { node = node->parent; level--; }
627 if( node ) node = node->next;
630 printf( "\nTree Classifier\n" );
632 for( i = 0; i <= max_level; i++ ) printf( "+---" );
634 for( i = 0; i <= max_level; i++ ) printf( "|%3d", i );
636 for( i = 0; i <= max_level; i++ ) printf( "+---" );
644 sprintf( buf + strlen( buf ), "%3d", node->idx );
648 sprintf( buf + strlen( buf ),
649 ((node->idx < 10) ? "---%d" : ((node->idx < 100) ? "--%d" : "-%d")),
652 printf( " %s\n", buf );
654 while( node && !node->next ) { node = node->parent; }
664 sprintf( buf0, " | %s", buf );
666 sprintf( buf0, " %s", buf );
670 printf( " %s |\n", buf );
681 CvIntHaarClassifier* icvLoadTreeCascadeClassifier( const char* filename, int step,
684 CvTreeCascadeClassifier* ptr = NULL;
685 CvTreeCascadeNode** nodes = NULL;
687 CV_FUNCNAME( "icvLoadTreeCascadeClassifier" );
692 CvStageHaarClassifier* stage;
693 char stage_name[PATH_MAX];
697 int result, parent=0, next=0;
700 if( !splits ) splits = &stub;
704 data_size = sizeof( *ptr );
706 CV_CALL( ptr = (CvTreeCascadeClassifier*) cvAlloc( data_size ) );
707 memset( ptr, 0, data_size );
709 ptr->eval = icvEvalTreeCascadeClassifier;
710 ptr->release = icvReleaseTreeCascadeClassifier;
712 sprintf( stage_name, "%s/", filename );
713 suffix = stage_name + strlen( stage_name );
717 sprintf( suffix, "%d/%s", i, CV_STAGE_CART_FILE_NAME );
718 f = fopen( stage_name, "r" );
726 data_size = sizeof( *nodes ) * num;
727 CV_CALL( nodes = (CvTreeCascadeNode**) cvAlloc( data_size ) );
729 for( i = 0; i < num; i++ )
731 sprintf( suffix, "%d/%s", i, CV_STAGE_CART_FILE_NAME );
732 f = fopen( stage_name, "r" );
733 CV_CALL( stage = (CvStageHaarClassifier*)
734 icvLoadCARTStageHaarClassifierF( f, step ) );
736 result = ( f && stage ) ? fscanf( f, "%d%d", &parent, &next ) : 0;
745 printf( "Stage %d loaded\n", i );
747 if( parent >= i || (next != -1 && next != i + 1) )
748 CV_ERROR( CV_StsError, "Invalid tree links" );
750 CV_CALL( nodes[i] = icvCreateTreeCascadeNode() );
751 nodes[i]->stage = stage;
753 nodes[i]->parent = (parent != -1 ) ? nodes[parent] : NULL;
754 nodes[i]->next = ( next != -1 ) ? nodes[i] : NULL;
755 nodes[i]->child = NULL;
757 for( i = 0; i < num; i++ )
762 nodes[i]->next = nodes[i+1];
764 if( nodes[i]->parent && nodes[i]->parent->child == NULL )
766 nodes[i]->parent->child = nodes[i];
769 ptr->root = nodes[0];
776 return (CvIntHaarClassifier*) ptr;
780 CvTreeCascadeNode* icvFindDeepestLeaves( CvTreeCascadeClassifier* tcc )
782 CvTreeCascadeNode* leaves;
784 //CV_FUNCNAME( "icvFindDeepestLeaves" );
788 int level, cur_level;
789 CvTreeCascadeNode* ptr;
790 CvTreeCascadeNode* last;
792 leaves = last = NULL;
798 /* find leaves with maximal level */
801 if( ptr->child ) { ptr = ptr->child; cur_level++; }
804 if( cur_level == level )
806 last->next_same_level = ptr;
807 ptr->next_same_level = NULL;
810 if( cur_level > level )
814 ptr->next_same_level = NULL;
816 while( ptr && ptr->next == NULL ) { ptr = ptr->parent; cur_level--; }
817 if( ptr ) ptr = ptr->next;