apps/haartraining/cvhaartraining.cpp

   1 /*M///////////////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
   4 //
   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.
   8 //
   9 //
  10 //                        Intel License Agreement
  11 //                For Open Source Computer Vision Library
  12 //
  13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
  14 // Third party copyrights are property of their respective owners.
  15 //
  16 // Redistribution and use in source and binary forms, with or without modification,
  17 // are permitted provided that the following conditions are met:
  18 //
  19 //   * Redistribution's of source code must retain the above copyright notice,
  20 //     this list of conditions and the following disclaimer.
  21 //
  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.
  25 //
  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.
  28 //
  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.
  39 //
  40 //M*/
  41
  42 /*
  43  * cvhaartraining.cpp
  44  *
  45  * training of cascade of boosted classifiers based on haar features
  46  */
  47
  48 #include "cvhaartraining.h"
  49 #include "_cvhaartraining.h"
  50
  51 #include <cstdio>
  52 #include <cstdlib>
  53 #include <cmath>
  54 #include <climits>
  55 #include <ctype.h>
  56
  57 #include "highgui.h"
  58
  59 #ifdef CV_VERBOSE
  60 #include <ctime>
  61
  62 #ifdef _WIN32
  63 /* use clock() function insted of time() */
  64 #define TIME( arg ) (((double) clock()) / CLOCKS_PER_SEC)
  65 #else
  66 #define TIME( arg ) (time( arg ))
  67 #endif /* _WIN32 */
  68
  69 #endif /* CV_VERBOSE */
  70
  71 #if defined CV_OPENMP && (defined _MSC_VER || defined CV_ICC)
  72 #define CV_OPENMP 1
  73 #else
  74 #undef CV_OPENMP
  75 #endif
  76
  77 typedef struct CvBackgroundData
  78 {
  79     int    count;
  80     char** filename;
  81     int    last;
  82     int    round;
  83     CvSize winsize;
  84 } CvBackgroundData;
  85
  86 typedef struct CvBackgroundReader
  87 {
  88     CvMat   src;
  89     CvMat   img;
  90     CvPoint offset;
  91     float   scale;
  92     float   scalefactor;
  93     float   stepfactor;
  94     CvPoint point;
  95 } CvBackgroundReader;
  96
  97 /*
  98  * Background reader
  99  * Created in each thread
 100  */
 101 CvBackgroundReader* cvbgreader = NULL;
 102
 103 #if defined CV_OPENMP
 104 #pragma omp threadprivate(cvbgreader)
 105 #endif
 106
 107 CvBackgroundData* cvbgdata = NULL;
 108
 109
 110 /*
 111  * get sum image offsets for <rect> corner points
 112  * step - row step (measured in image pixels!) of sum image
 113  */
 114 #define CV_SUM_OFFSETS( p0, p1, p2, p3, rect, step )                      \
 115     /* (x, y) */                                                          \
 116     (p0) = (rect).x + (step) * (rect).y;                                  \
 117     /* (x + w, y) */                                                      \
 118     (p1) = (rect).x + (rect).width + (step) * (rect).y;                   \
 119     /* (x + w, y) */                                                      \
 120     (p2) = (rect).x + (step) * ((rect).y + (rect).height);                \
 121     /* (x + w, y + h) */                                                  \
 122     (p3) = (rect).x + (rect).width + (step) * ((rect).y + (rect).height);
 123
 124 /*
 125  * get tilted image offsets for <rect> corner points
 126  * step - row step (measured in image pixels!) of tilted image
 127  */
 128 #define CV_TILTED_OFFSETS( p0, p1, p2, p3, rect, step )                   \
 129     /* (x, y) */                                                          \
 130     (p0) = (rect).x + (step) * (rect).y;                                  \
 131     /* (x - h, y + h) */                                                  \
 132     (p1) = (rect).x - (rect).height + (step) * ((rect).y + (rect).height);\
 133     /* (x + w, y + w) */                                                  \
 134     (p2) = (rect).x + (rect).width + (step) * ((rect).y + (rect).width);  \
 135     /* (x + w - h, y + w + h) */                                          \
 136     (p3) = (rect).x + (rect).width - (rect).height                        \
 137            + (step) * ((rect).y + (rect).width + (rect).height);
 138
 139
 140 /*
 141  * icvCreateIntHaarFeatures
 142  *
 143  * Create internal representation of haar features
 144  *
 145  * mode:
 146  *  0 - BASIC = Viola
 147  *  1 - CORE  = All upright
 148  *  2 - ALL   = All features
 149  */
 150 static
 151 CvIntHaarFeatures* icvCreateIntHaarFeatures( CvSize winsize,
 152                                              int mode,
 153                                              int symmetric )
 154 {
 155     CvIntHaarFeatures* features = NULL;
 156     CvTHaarFeature haarFeature;
 157
 158     CvMemStorage* storage = NULL;
 159     CvSeq* seq = NULL;
 160     CvSeqWriter writer;
 161
 162     int s0 = 36; /* minimum total area size of basic haar feature     */
 163     int s1 = 12; /* minimum total area size of tilted haar features 2 */
 164     int s2 = 18; /* minimum total area size of tilted haar features 3 */
 165     int s3 = 24; /* minimum total area size of tilted haar features 4 */
 166
 167     int x  = 0;
 168     int y  = 0;
 169     int dx = 0;
 170     int dy = 0;
 171
 172 #if 0
 173     float factor = 1.0F;
 174
 175     factor = ((float) winsize.width) * winsize.height / (24 * 24);
 176
 177     s0 = (int) (s0 * factor);
 178     s1 = (int) (s1 * factor);
 179     s2 = (int) (s2 * factor);
 180     s3 = (int) (s3 * factor);
 181 #else
 182     s0 = 1;
 183     s1 = 1;
 184     s2 = 1;
 185     s3 = 1;
 186 #endif
 187
 188     /* CV_VECTOR_CREATE( vec, CvIntHaarFeature, size, maxsize ) */
 189     storage = cvCreateMemStorage();
 190     cvStartWriteSeq( 0, sizeof( CvSeq ), sizeof( haarFeature ), storage, &writer );
 191
 192     for( x = 0; x < winsize.width; x++ )
 193     {
 194         for( y = 0; y < winsize.height; y++ )
 195         {
 196             for( dx = 1; dx <= winsize.width; dx++ )
 197             {
 198                 for( dy = 1; dy <= winsize.height; dy++ )
 199                 {
 200                     // haar_x2
 201                     if ( (x+dx*2 <= winsize.width) && (y+dy <= winsize.height) ) {
 202                         if (dx*2*dy < s0) continue;
 203                         if (!symmetric || (x+x+dx*2 <=winsize.width)) {
 204                             haarFeature = cvHaarFeature( "haar_x2",
 205                                 x,    y, dx*2, dy, -1,
 206                                 x+dx, y, dx  , dy, +2 );
 207                             /* CV_VECTOR_PUSH( vec, CvIntHaarFeature, haarFeature, size, maxsize, step ) */
 208                             CV_WRITE_SEQ_ELEM( haarFeature, writer );
 209                         }
 210                     }
 211
 212                     // haar_y2
 213                     if ( (x+dx <= winsize.width) && (y+dy*2 <= winsize.height) ) {
 214                         if (dx*2*dy < s0) continue;
 215                         if (!symmetric || (x+x+dx <= winsize.width)) {
 216                             haarFeature = cvHaarFeature( "haar_y2",
 217                                 x, y,    dx, dy*2, -1,
 218                                 x, y+dy, dx, dy,   +2 );
 219                             CV_WRITE_SEQ_ELEM( haarFeature, writer );
 220                         }
 221                     }
 222
 223                     // haar_x3
 224                     if ( (x+dx*3 <= winsize.width) && (y+dy <= winsize.height) ) {
 225                         if (dx*3*dy < s0) continue;
 226                         if (!symmetric || (x+x+dx*3 <=winsize.width)) {
 227                             haarFeature = cvHaarFeature( "haar_x3",
 228                                 x,    y, dx*3, dy, -1,
 229                                 x+dx, y, dx,   dy, +3 );
 230                             CV_WRITE_SEQ_ELEM( haarFeature, writer );
 231                         }
 232                     }
 233
 234                     // haar_y3
 235                     if ( (x+dx <= winsize.width) && (y+dy*3 <= winsize.height) ) {
 236                         if (dx*3*dy < s0) continue;
 237                         if (!symmetric || (x+x+dx <= winsize.width)) {
 238                             haarFeature = cvHaarFeature( "haar_y3",
 239                                 x, y,    dx, dy*3, -1,
 240                                 x, y+dy, dx, dy,   +3 );
 241                             CV_WRITE_SEQ_ELEM( haarFeature, writer );
 242                         }
 243                     }
 244
 245                     if( mode != 0 /*BASIC*/ ) {
 246                         // haar_x4
 247                         if ( (x+dx*4 <= winsize.width) && (y+dy <= winsize.height) ) {
 248                             if (dx*4*dy < s0) continue;
 249                             if (!symmetric || (x+x+dx*4 <=winsize.width)) {
 250                                 haarFeature = cvHaarFeature( "haar_x4",
 251                                     x,    y, dx*4, dy, -1,
 252                                     x+dx, y, dx*2, dy, +2 );
 253                                 CV_WRITE_SEQ_ELEM( haarFeature, writer );
 254                             }
 255                         }
 256
 257                         // haar_y4
 258                         if ( (x+dx <= winsize.width ) && (y+dy*4 <= winsize.height) ) {
 259                             if (dx*4*dy < s0) continue;
 260                             if (!symmetric || (x+x+dx   <=winsize.width)) {
 261                                 haarFeature = cvHaarFeature( "haar_y4",
 262                                     x, y,    dx, dy*4, -1,
 263                                     x, y+dy, dx, dy*2, +2 );
 264                                 CV_WRITE_SEQ_ELEM( haarFeature, writer );
 265                             }
 266                         }
 267                     }
 268
 269                     // x2_y2
 270                     if ( (x+dx*2 <= winsize.width) && (y+dy*2 <= winsize.height) ) {
 271                         if (dx*4*dy < s0) continue;
 272                         if (!symmetric || (x+x+dx*2 <=winsize.width)) {
 273                             haarFeature = cvHaarFeature( "haar_x2_y2",
 274                                 x   , y,    dx*2, dy*2, -1,
 275                                 x   , y   , dx  , dy,   +2,
 276                                 x+dx, y+dy, dx  , dy,   +2 );
 277                             CV_WRITE_SEQ_ELEM( haarFeature, writer );
 278                         }
 279                     }
 280
 281                     if (mode != 0 /*BASIC*/) {
 282                         // point
 283                         if ( (x+dx*3 <= winsize.width) && (y+dy*3 <= winsize.height) ) {
 284                             if (dx*9*dy < s0) continue;
 285                             if (!symmetric || (x+x+dx*3 <=winsize.width))  {
 286                                 haarFeature = cvHaarFeature( "haar_point",
 287                                     x   , y,    dx*3, dy*3, -1,
 288                                     x+dx, y+dy, dx  , dy  , +9);
 289                                 CV_WRITE_SEQ_ELEM( haarFeature, writer );
 290                             }
 291                         }
 292                     }
 293
 294                     if (mode == 2 /*ALL*/) {
 295                         // tilted haar_x2                                      (x, y, w, h, b, weight)
 296                         if ( (x+2*dx <= winsize.width) && (y+2*dx+dy <= winsize.height) && (x-dy>= 0) ) {
 297                             if (dx*2*dy < s1) continue;
 298
 299                             if (!symmetric || (x <= (winsize.width / 2) )) {
 300                                 haarFeature = cvHaarFeature( "tilted_haar_x2",
 301                                     x, y, dx*2, dy, -1,
 302                                     x, y, dx  , dy, +2 );
 303                                 CV_WRITE_SEQ_ELEM( haarFeature, writer );
 304                             }
 305                         }
 306
 307                         // tilted haar_y2                                      (x, y, w, h, b, weight)
 308                         if ( (x+dx <= winsize.width) && (y+dx+2*dy <= winsize.height) && (x-2*dy>= 0) ) {
 309                             if (dx*2*dy < s1) continue;
 310
 311                             if (!symmetric || (x <= (winsize.width / 2) )) {
 312                                 haarFeature = cvHaarFeature( "tilted_haar_y2",
 313                                     x, y, dx, 2*dy, -1,
 314                                     x, y, dx,   dy, +2 );
 315                                 CV_WRITE_SEQ_ELEM( haarFeature, writer );
 316                             }
 317                         }
 318
 319                         // tilted haar_x3                                   (x, y, w, h, b, weight)
 320                         if ( (x+3*dx <= winsize.width) && (y+3*dx+dy <= winsize.height) && (x-dy>= 0) ) {
 321                             if (dx*3*dy < s2) continue;
 322
 323                             if (!symmetric || (x <= (winsize.width / 2) )) {
 324                                 haarFeature = cvHaarFeature( "tilted_haar_x3",
 325                                     x,    y,    dx*3, dy, -1,
 326                                     x+dx, y+dx, dx  , dy, +3 );
 327                                 CV_WRITE_SEQ_ELEM( haarFeature, writer );
 328                             }
 329                         }
 330
 331                         // tilted haar_y3                                      (x, y, w, h, b, weight)
 332                         if ( (x+dx <= winsize.width) && (y+dx+3*dy <= winsize.height) && (x-3*dy>= 0) ) {
 333                             if (dx*3*dy < s2) continue;
 334
 335                             if (!symmetric || (x <= (winsize.width / 2) )) {
 336                                 haarFeature = cvHaarFeature( "tilted_haar_y3",
 337                                     x,    y,    dx, 3*dy, -1,
 338                                     x-dy, y+dy, dx,   dy, +3 );
 339                                 CV_WRITE_SEQ_ELEM( haarFeature, writer );
 340                             }
 341                         }
 342
 343
 344                         // tilted haar_x4                                   (x, y, w, h, b, weight)
 345                         if ( (x+4*dx <= winsize.width) && (y+4*dx+dy <= winsize.height) && (x-dy>= 0) ) {
 346                             if (dx*4*dy < s3) continue;
 347
 348                             if (!symmetric || (x <= (winsize.width / 2) )) {
 349                                 haarFeature = cvHaarFeature( "tilted_haar_x4",
 350
 351
 352                                     x,    y,    dx*4, dy, -1,
 353                                     x+dx, y+dx, dx*2, dy, +2 );
 354                                 CV_WRITE_SEQ_ELEM( haarFeature, writer );
 355                             }
 356                         }
 357
 358                         // tilted haar_y4                                      (x, y, w, h, b, weight)
 359                         if ( (x+dx <= winsize.width) && (y+dx+4*dy <= winsize.height) && (x-4*dy>= 0) ) {
 360                             if (dx*4*dy < s3) continue;
 361
 362                             if (!symmetric || (x <= (winsize.width / 2) )) {
 363                                 haarFeature = cvHaarFeature( "tilted_haar_y4",
 364                                     x,    y,    dx, 4*dy, -1,
 365                                     x-dy, y+dy, dx, 2*dy, +2 );
 366                                 CV_WRITE_SEQ_ELEM( haarFeature, writer );
 367                             }
 368                         }
 369
 370
 371                         /*
 372
 373                           // tilted point
 374                           if ( (x+dx*3 <= winsize.width - 1) && (y+dy*3 <= winsize.height - 1) && (x-3*dy>= 0)) {
 375                           if (dx*9*dy < 36) continue;
 376                           if (!symmetric || (x <= (winsize.width / 2) ))  {
 377                             haarFeature = cvHaarFeature( "tilted_haar_point",
 378                                 x, y,    dx*3, dy*3, -1,
 379                                 x, y+dy, dx  , dy,   +9 );
 380                                 CV_WRITE_SEQ_ELEM( haarFeature, writer );
 381                           }
 382                           }
 383                         */
 384                     }
 385                 }
 386             }
 387         }
 388     }
 389
 390     seq = cvEndWriteSeq( &writer );
 391     features = (CvIntHaarFeatures*) cvAlloc( sizeof( CvIntHaarFeatures ) +
 392         ( sizeof( CvTHaarFeature ) + sizeof( CvFastHaarFeature ) ) * seq->total );
 393     features->feature = (CvTHaarFeature*) (features + 1);
 394     features->fastfeature = (CvFastHaarFeature*) ( features->feature + seq->total );
 395     features->count = seq->total;
 396     features->winsize = winsize;
 397     cvCvtSeqToArray( seq, (CvArr*) features->feature );
 398     cvReleaseMemStorage( &storage );
 399
 400     icvConvertToFastHaarFeature( features->feature, features->fastfeature,
 401                                  features->count, (winsize.width + 1) );
 402
 403     return features;
 404 }
 405
 406 static
 407 void icvReleaseIntHaarFeatures( CvIntHaarFeatures** intHaarFeatures )
 408 {
 409     if( intHaarFeatures != NULL && (*intHaarFeatures) != NULL )
 410     {
 411         cvFree( intHaarFeatures );
 412         (*intHaarFeatures) = NULL;
 413     }
 414 }
 415
 416
 417 void icvConvertToFastHaarFeature( CvTHaarFeature* haarFeature,
 418                                   CvFastHaarFeature* fastHaarFeature,
 419                                   int size, int step )
 420 {
 421     int i = 0;
 422     int j = 0;
 423
 424     for( i = 0; i < size; i++ )
 425     {
 426         fastHaarFeature[i].tilted = haarFeature[i].tilted;
 427         if( !fastHaarFeature[i].tilted )
 428         {
 429             for( j = 0; j < CV_HAAR_FEATURE_MAX; j++ )
 430             {
 431                 fastHaarFeature[i].rect[j].weight = haarFeature[i].rect[j].weight;
 432                 if( fastHaarFeature[i].rect[j].weight == 0.0F )
 433                 {
 434                     break;
 435                 }
 436                 CV_SUM_OFFSETS( fastHaarFeature[i].rect[j].p0,
 437                                 fastHaarFeature[i].rect[j].p1,
 438                                 fastHaarFeature[i].rect[j].p2,
 439                                 fastHaarFeature[i].rect[j].p3,
 440                                 haarFeature[i].rect[j].r, step )
 441             }
 442
 443         }
 444         else
 445         {
 446             for( j = 0; j < CV_HAAR_FEATURE_MAX; j++ )
 447             {
 448                 fastHaarFeature[i].rect[j].weight = haarFeature[i].rect[j].weight;
 449                 if( fastHaarFeature[i].rect[j].weight == 0.0F )
 450                 {
 451                     break;
 452                 }
 453                 CV_TILTED_OFFSETS( fastHaarFeature[i].rect[j].p0,
 454                                    fastHaarFeature[i].rect[j].p1,
 455                                    fastHaarFeature[i].rect[j].p2,
 456                                    fastHaarFeature[i].rect[j].p3,
 457                                    haarFeature[i].rect[j].r, step )
 458             }
 459         }
 460     }
 461 }
 462
 463
 464 /*
 465  * icvCreateHaarTrainingData
 466  *
 467  * Create haar training data used in stage training
 468  */
 469 static
 470 CvHaarTrainigData* icvCreateHaarTrainingData( CvSize winsize, int maxnumsamples )
 471 {
 472     CvHaarTrainigData* data;
 473
 474     CV_FUNCNAME( "icvCreateHaarTrainingData" );
 475
 476     __BEGIN__;
 477
 478     data = NULL;
 479     uchar* ptr = NULL;
 480     size_t datasize = 0;
 481
 482     datasize = sizeof( CvHaarTrainigData ) +
 483           /* sum and tilted */
 484         ( 2 * (winsize.width + 1) * (winsize.height + 1) * sizeof( sum_type ) +
 485           sizeof( float ) +      /* normfactor */
 486           sizeof( float ) +      /* cls */
 487           sizeof( float )        /* weight */
 488         ) * maxnumsamples;
 489
 490     CV_CALL( data = (CvHaarTrainigData*) cvAlloc( datasize ) );
 491     memset( (void*)data, 0, datasize );
 492     data->maxnum = maxnumsamples;
 493     data->winsize = winsize;
 494     ptr = (uchar*)(data + 1);
 495     data->sum = cvMat( maxnumsamples, (winsize.width + 1) * (winsize.height + 1),
 496                        CV_SUM_MAT_TYPE, (void*) ptr );
 497     ptr += sizeof( sum_type ) * maxnumsamples * (winsize.width+1) * (winsize.height+1);
 498     data->tilted = cvMat( maxnumsamples, (winsize.width + 1) * (winsize.height + 1),
 499                        CV_SUM_MAT_TYPE, (void*) ptr );
 500     ptr += sizeof( sum_type ) * maxnumsamples * (winsize.width+1) * (winsize.height+1);
 501     data->normfactor = cvMat( 1, maxnumsamples, CV_32FC1, (void*) ptr );
 502     ptr += sizeof( float ) * maxnumsamples;
 503     data->cls = cvMat( 1, maxnumsamples, CV_32FC1, (void*) ptr );
 504     ptr += sizeof( float ) * maxnumsamples;
 505     data->weights = cvMat( 1, maxnumsamples, CV_32FC1, (void*) ptr );
 506
 507     data->valcache = NULL;
 508     data->idxcache = NULL;
 509
 510     __END__;
 511
 512     return data;
 513 }
 514
 515 static
 516 void icvReleaseHaarTrainingDataCache( CvHaarTrainigData** haarTrainingData )
 517 {
 518     if( haarTrainingData != NULL && (*haarTrainingData) != NULL )
 519     {
 520         if( (*haarTrainingData)->valcache != NULL )
 521         {
 522             cvReleaseMat( &(*haarTrainingData)->valcache );
 523             (*haarTrainingData)->valcache = NULL;
 524         }
 525         if( (*haarTrainingData)->idxcache != NULL )
 526         {
 527             cvReleaseMat( &(*haarTrainingData)->idxcache );
 528             (*haarTrainingData)->idxcache = NULL;
 529         }
 530     }
 531 }
 532
 533 static
 534 void icvReleaseHaarTrainingData( CvHaarTrainigData** haarTrainingData )
 535 {
 536     if( haarTrainingData != NULL && (*haarTrainingData) != NULL )
 537     {
 538         icvReleaseHaarTrainingDataCache( haarTrainingData );
 539
 540         cvFree( haarTrainingData );
 541     }
 542 }
 543
 544 static
 545 void icvGetTrainingDataCallback( CvMat* mat, CvMat* sampleIdx, CvMat*,
 546                                  int first, int num, void* userdata )
 547 {
 548     int i = 0;
 549     int j = 0;
 550     float val = 0.0F;
 551     float normfactor = 0.0F;
 552
 553     CvHaarTrainingData* training_data;
 554     CvIntHaarFeatures* haar_features;
 555
 556 #ifdef CV_COL_ARRANGEMENT
 557     assert( mat->rows >= num );
 558 #else
 559     assert( mat->cols >= num );
 560 #endif
 561
 562     training_data = ((CvUserdata*) userdata)->trainingData;
 563     haar_features = ((CvUserdata*) userdata)->haarFeatures;
 564     if( sampleIdx == NULL )
 565     {
 566         int num_samples;
 567
 568 #ifdef CV_COL_ARRANGEMENT
 569         num_samples = mat->cols;
 570 #else
 571         num_samples = mat->rows;
 572 #endif
 573         for( i = 0; i < num_samples; i++ )
 574         {
 575             for( j = 0; j < num; j++ )
 576             {
 577                 val = cvEvalFastHaarFeature(
 578                         ( haar_features->fastfeature
 579                             + first + j ),
 580                         (sum_type*) (training_data->sum.data.ptr
 581                             + i * training_data->sum.step),
 582                         (sum_type*) (training_data->tilted.data.ptr
 583                             + i * training_data->tilted.step) );
 584                 normfactor = training_data->normfactor.data.fl[i];
 585                 val = ( normfactor == 0.0F ) ? 0.0F : (val / normfactor);
 586
 587 #ifdef CV_COL_ARRANGEMENT
 588                 CV_MAT_ELEM( *mat, float, j, i ) = val;
 589 #else
 590                 CV_MAT_ELEM( *mat, float, i, j ) = val;
 591 #endif
 592             }
 593         }
 594     }
 595     else
 596     {
 597         uchar* idxdata = NULL;
 598         size_t step    = 0;
 599         int    numidx  = 0;
 600         int    idx     = 0;
 601
 602         assert( CV_MAT_TYPE( sampleIdx->type ) == CV_32FC1 );
 603
 604         idxdata = sampleIdx->data.ptr;
 605         if( sampleIdx->rows == 1 )
 606         {
 607             step = sizeof( float );
 608             numidx = sampleIdx->cols;
 609         }
 610         else
 611         {
 612             step = sampleIdx->step;
 613             numidx = sampleIdx->rows;
 614         }
 615
 616         for( i = 0; i < numidx; i++ )
 617         {
 618             for( j = 0; j < num; j++ )
 619             {
 620                 idx = (int)( *((float*) (idxdata + i * step)) );
 621                 val = cvEvalFastHaarFeature(
 622                         ( haar_features->fastfeature
 623                             + first + j ),
 624                         (sum_type*) (training_data->sum.data.ptr
 625                             + idx * training_data->sum.step),
 626                         (sum_type*) (training_data->tilted.data.ptr
 627                             + idx * training_data->tilted.step) );
 628                 normfactor = training_data->normfactor.data.fl[idx];
 629                 val = ( normfactor == 0.0F ) ? 0.0F : (val / normfactor);
 630
 631 #ifdef CV_COL_ARRANGEMENT
 632                 CV_MAT_ELEM( *mat, float, j, idx ) = val;
 633 #else
 634                 CV_MAT_ELEM( *mat, float, idx, j ) = val;
 635 #endif
 636
 637             }
 638         }
 639     }
 640 #if 0 /*def CV_VERBOSE*/
 641     if( first % 5000 == 0 )
 642     {
 643         fprintf( stderr, "%3d%%\r", (int) (100.0 * first /
 644             haar_features->count) );
 645         fflush( stderr );
 646     }
 647 #endif /* CV_VERBOSE */
 648 }
 649
 650 static
 651 void icvPrecalculate( CvHaarTrainingData* data, CvIntHaarFeatures* haarFeatures,
 652                       int numprecalculated )
 653 {
 654     CV_FUNCNAME( "icvPrecalculate" );
 655
 656     __BEGIN__;
 657
 658     icvReleaseHaarTrainingDataCache( &data );
 659
 660     numprecalculated -= numprecalculated % CV_STUMP_TRAIN_PORTION;
 661     numprecalculated = MIN( numprecalculated, haarFeatures->count );
 662
 663     if( numprecalculated > 0 )
 664     {
 665         //size_t datasize;
 666         int m;
 667         CvUserdata userdata;
 668
 669         /* private variables */
 670         #ifdef CV_OPENMP
 671         CvMat t_data;
 672         CvMat t_idx;
 673         int first;
 674         int t_portion;
 675         int portion = CV_STUMP_TRAIN_PORTION;
 676         #endif /* CV_OPENMP */
 677
 678         m = data->sum.rows;
 679
 680 #ifdef CV_COL_ARRANGEMENT
 681         CV_CALL( data->valcache = cvCreateMat( numprecalculated, m, CV_32FC1 ) );
 682 #else
 683         CV_CALL( data->valcache = cvCreateMat( m, numprecalculated, CV_32FC1 ) );
 684 #endif
 685         CV_CALL( data->idxcache = cvCreateMat( numprecalculated, m, CV_IDX_MAT_TYPE ) );
 686
 687         userdata = cvUserdata( data, haarFeatures );
 688
 689         #ifdef CV_OPENMP
 690         #pragma omp parallel for private(t_data, t_idx, first, t_portion)
 691         for( first = 0; first < numprecalculated; first += portion )
 692         {
 693             t_data = *data->valcache;
 694             t_idx = *data->idxcache;
 695             t_portion = MIN( portion, (numprecalculated - first) );
 696
 697             /* indices */
 698             t_idx.rows = t_portion;
 699             t_idx.data.ptr = data->idxcache->data.ptr + first * ((size_t)t_idx.step);
 700
 701             /* feature values */
 702 #ifdef CV_COL_ARRANGEMENT
 703             t_data.rows = t_portion;
 704             t_data.data.ptr = data->valcache->data.ptr +
 705                 first * ((size_t) t_data.step );
 706 #else
 707             t_data.cols = t_portion;
 708             t_data.data.ptr = data->valcache->data.ptr +
 709                 first * ((size_t) CV_ELEM_SIZE( t_data.type ));
 710 #endif
 711             icvGetTrainingDataCallback( &t_data, NULL, NULL, first, t_portion,
 712                                         &userdata );
 713 #ifdef CV_COL_ARRANGEMENT
 714             cvGetSortedIndices( &t_data, &t_idx, 0 );
 715 #else
 716             cvGetSortedIndices( &t_data, &t_idx, 1 );
 717 #endif
 718
 719 #ifdef CV_VERBOSE
 720             putc( '.', stderr );
 721             fflush( stderr );
 722 #endif /* CV_VERBOSE */
 723
 724         }
 725
 726 #ifdef CV_VERBOSE
 727         fprintf( stderr, "\n" );
 728         fflush( stderr );
 729 #endif /* CV_VERBOSE */
 730
 731         #else
 732         icvGetTrainingDataCallback( data->valcache, NULL, NULL, 0, numprecalculated,
 733                                     &userdata );
 734 #ifdef CV_COL_ARRANGEMENT
 735         cvGetSortedIndices( data->valcache, data->idxcache, 0 );
 736 #else
 737         cvGetSortedIndices( data->valcache, data->idxcache, 1 );
 738 #endif
 739         #endif /* CV_OPENMP */
 740     }
 741
 742     __END__;
 743 }
 744
 745 static
 746 void icvSplitIndicesCallback( int compidx, float threshold,
 747                               CvMat* idx, CvMat** left, CvMat** right,
 748                               void* userdata )
 749 {
 750     CvHaarTrainingData* data;
 751     CvIntHaarFeatures* haar_features;
 752     int i;
 753     int m;
 754     CvFastHaarFeature* fastfeature;
 755
 756     data = ((CvUserdata*) userdata)->trainingData;
 757     haar_features = ((CvUserdata*) userdata)->haarFeatures;
 758     fastfeature = &haar_features->fastfeature[compidx];
 759
 760     m = data->sum.rows;
 761     *left = cvCreateMat( 1, m, CV_32FC1 );
 762     *right = cvCreateMat( 1, m, CV_32FC1 );
 763     (*left)->cols = (*right)->cols = 0;
 764     if( idx == NULL )
 765     {
 766         for( i = 0; i < m; i++ )
 767         {
 768             if( cvEvalFastHaarFeature( fastfeature,
 769                     (sum_type*) (data->sum.data.ptr + i * data->sum.step),
 770                     (sum_type*) (data->tilted.data.ptr + i * data->tilted.step) )
 771                 < threshold * data->normfactor.data.fl[i] )
 772             {
 773                 (*left)->data.fl[(*left)->cols++] = (float) i;
 774             }
 775             else
 776             {
 777                 (*right)->data.fl[(*right)->cols++] = (float) i;
 778             }
 779         }
 780     }
 781     else
 782     {
 783         uchar* idxdata;
 784         int    idxnum;
 785         size_t idxstep;
 786         int    index;
 787
 788         idxdata = idx->data.ptr;
 789         idxnum = (idx->rows == 1) ? idx->cols : idx->rows;
 790         idxstep = (idx->rows == 1) ? CV_ELEM_SIZE( idx->type ) : idx->step;
 791         for( i = 0; i < idxnum; i++ )
 792         {
 793             index = (int) *((float*) (idxdata + i * idxstep));
 794             if( cvEvalFastHaarFeature( fastfeature,
 795                     (sum_type*) (data->sum.data.ptr + index * data->sum.step),
 796                     (sum_type*) (data->tilted.data.ptr + index * data->tilted.step) )
 797                 < threshold * data->normfactor.data.fl[index] )
 798             {
 799                 (*left)->data.fl[(*left)->cols++] = (float) index;
 800             }
 801             else
 802             {
 803                 (*right)->data.fl[(*right)->cols++] = (float) index;
 804             }
 805         }
 806     }
 807 }
 808
 809 /*
 810  * icvCreateCARTStageClassifier
 811  *
 812  * Create stage classifier with trees as weak classifiers
 813  * data             - haar training data. It must be created and filled before call
 814  * minhitrate       - desired min hit rate
 815  * maxfalsealarm    - desired max false alarm rate
 816  * symmetric        - if not 0 it is assumed that samples are vertically symmetric
 817  * numprecalculated - number of features that will be precalculated. Each precalculated
 818  *   feature need (number_of_samples*(sizeof( float ) + sizeof( short ))) bytes of memory
 819  * weightfraction   - weight trimming parameter
 820  * numsplits        - number of binary splits in each tree
 821  * boosttype        - type of applied boosting algorithm
 822  * stumperror       - type of used error if Discrete AdaBoost algorithm is applied
 823  * maxsplits        - maximum total number of splits in all weak classifiers.
 824  *   If it is not 0 then NULL returned if total number of splits exceeds <maxsplits>.
 825  */
 826 static
 827 CvIntHaarClassifier* icvCreateCARTStageClassifier( CvHaarTrainingData* data,
 828                                                    CvMat* sampleIdx,
 829                                                    CvIntHaarFeatures* haarFeatures,
 830                                                    float minhitrate,
 831                                                    float maxfalsealarm,
 832                                                    int   symmetric,
 833                                                    float weightfraction,
 834                                                    int numsplits,
 835                                                    CvBoostType boosttype,
 836                                                    CvStumpError stumperror,
 837                                                    int maxsplits )
 838 {
 839
 840 #ifdef CV_COL_ARRANGEMENT
 841     int flags = CV_COL_SAMPLE;
 842 #else
 843     int flags = CV_ROW_SAMPLE;
 844 #endif
 845
 846     CvStageHaarClassifier* stage = NULL;
 847     CvBoostTrainer* trainer;
 848     CvCARTClassifier* cart = NULL;
 849     CvCARTTrainParams trainParams;
 850     CvMTStumpTrainParams stumpTrainParams;
 851     //CvMat* trainData = NULL;
 852     //CvMat* sortedIdx = NULL;
 853     CvMat eval;
 854     int n = 0;
 855     int m = 0;
 856     int numpos = 0;
 857     int numneg = 0;
 858     int numfalse = 0;
 859     float sum_stage = 0.0F;
 860     float threshold = 0.0F;
 861     float falsealarm = 0.0F;
 862
 863     //CvMat* sampleIdx = NULL;
 864     CvMat* trimmedIdx;
 865     //float* idxdata = NULL;
 866     //float* tempweights = NULL;
 867     //int    idxcount = 0;
 868     CvUserdata userdata;
 869
 870     int i = 0;
 871     int j = 0;
 872     int idx;
 873     int numsamples;
 874     int numtrimmed;
 875
 876     CvCARTHaarClassifier* classifier;
 877     CvSeq* seq = NULL;
 878     CvMemStorage* storage = NULL;
 879     CvMat* weakTrainVals;
 880     float alpha;
 881     float sumalpha;
 882     int num_splits; /* total number of splits in all weak classifiers */
 883
 884 #ifdef CV_VERBOSE
 885     printf( "+----+----+-+---------+---------+---------+---------+\n" );
 886     printf( "|  N |%%SMP|F|  ST.THR |    HR   |    FA   | EXP. ERR|\n" );
 887     printf( "+----+----+-+---------+---------+---------+---------+\n" );
 888 #endif /* CV_VERBOSE */
 889
 890     n = haarFeatures->count;
 891     m = data->sum.rows;
 892     numsamples = (sampleIdx) ? MAX( sampleIdx->rows, sampleIdx->cols ) : m;
 893
 894     userdata = cvUserdata( data, haarFeatures );
 895
 896     stumpTrainParams.type = ( boosttype == CV_DABCLASS )
 897         ? CV_CLASSIFICATION_CLASS : CV_REGRESSION;
 898     stumpTrainParams.error = ( boosttype == CV_LBCLASS || boosttype == CV_GABCLASS )
 899         ? CV_SQUARE : stumperror;
 900     stumpTrainParams.portion = CV_STUMP_TRAIN_PORTION;
 901     stumpTrainParams.getTrainData = icvGetTrainingDataCallback;
 902     stumpTrainParams.numcomp = n;
 903     stumpTrainParams.userdata = &userdata;
 904     stumpTrainParams.sortedIdx = data->idxcache;
 905
 906     trainParams.count = numsplits;
 907     trainParams.stumpTrainParams = (CvClassifierTrainParams*) &stumpTrainParams;
 908     trainParams.stumpConstructor = cvCreateMTStumpClassifier;
 909     trainParams.splitIdx = icvSplitIndicesCallback;
 910     trainParams.userdata = &userdata;
 911
 912     eval = cvMat( 1, m, CV_32FC1, cvAlloc( sizeof( float ) * m ) );
 913
 914     storage = cvCreateMemStorage();
 915     seq = cvCreateSeq( 0, sizeof( *seq ), sizeof( classifier ), storage );
 916
 917     weakTrainVals = cvCreateMat( 1, m, CV_32FC1 );
 918     trainer = cvBoostStartTraining( &data->cls, weakTrainVals, &data->weights,
 919                                     sampleIdx, boosttype );
 920     num_splits = 0;
 921     sumalpha = 0.0F;
 922     do
 923     {
 924
 925 #ifdef CV_VERBOSE
 926         int v_wt = 0;
 927         int v_flipped = 0;
 928 #endif /* CV_VERBOSE */
 929
 930         trimmedIdx = cvTrimWeights( &data->weights, sampleIdx, weightfraction );
 931         numtrimmed = (trimmedIdx) ? MAX( trimmedIdx->rows, trimmedIdx->cols ) : m;
 932
 933 #ifdef CV_VERBOSE
 934         v_wt = 100 * numtrimmed / numsamples;
 935         v_flipped = 0;
 936
 937 #endif /* CV_VERBOSE */
 938
 939         cart = (CvCARTClassifier*) cvCreateCARTClassifier( data->valcache,
 940                         flags,
 941                         weakTrainVals, 0, 0, 0, trimmedIdx,
 942                         &(data->weights),
 943                         (CvClassifierTrainParams*) &trainParams );
 944
 945         classifier = (CvCARTHaarClassifier*) icvCreateCARTHaarClassifier( numsplits );
 946         icvInitCARTHaarClassifier( classifier, cart, haarFeatures );
 947
 948         num_splits += classifier->count;
 949
 950         cart->release( (CvClassifier**) &cart );
 951
 952         if( symmetric && (seq->total % 2) )
 953         {
 954             float normfactor = 0.0F;
 955             CvStumpClassifier* stump;
 956
 957             /* flip haar features */
 958             for( i = 0; i < classifier->count; i++ )
 959             {
 960                 if( classifier->feature[i].desc[0] == 'h' )
 961                 {
 962                     for( j = 0; j < CV_HAAR_FEATURE_MAX &&
 963                                     classifier->feature[i].rect[j].weight != 0.0F; j++ )
 964                     {
 965                         classifier->feature[i].rect[j].r.x = data->winsize.width -
 966                             classifier->feature[i].rect[j].r.x -
 967                             classifier->feature[i].rect[j].r.width;
 968                     }
 969                 }
 970                 else
 971                 {
 972                     int tmp = 0;
 973
 974                     /* (x,y) -> (24-x,y) */
 975                     /* w -> h; h -> w    */
 976                     for( j = 0; j < CV_HAAR_FEATURE_MAX &&
 977                                     classifier->feature[i].rect[j].weight != 0.0F; j++ )
 978                     {
 979                         classifier->feature[i].rect[j].r.x = data->winsize.width -
 980                             classifier->feature[i].rect[j].r.x;
 981                         CV_SWAP( classifier->feature[i].rect[j].r.width,
 982                                  classifier->feature[i].rect[j].r.height, tmp );
 983                     }
 984                 }
 985             }
 986             icvConvertToFastHaarFeature( classifier->feature,
 987                                          classifier->fastfeature,
 988                                          classifier->count, data->winsize.width + 1 );
 989
 990             stumpTrainParams.getTrainData = NULL;
 991             stumpTrainParams.numcomp = 1;
 992             stumpTrainParams.userdata = NULL;
 993             stumpTrainParams.sortedIdx = NULL;
 994
 995             for( i = 0; i < classifier->count; i++ )
 996             {
 997                 for( j = 0; j < numtrimmed; j++ )
 998                 {
 999                     idx = icvGetIdxAt( trimmedIdx, j );
1000
1001                     eval.data.fl[idx] = cvEvalFastHaarFeature( &classifier->fastfeature[i],
1002                         (sum_type*) (data->sum.data.ptr + idx * data->sum.step),
1003                         (sum_type*) (data->tilted.data.ptr + idx * data->tilted.step) );
1004                     normfactor = data->normfactor.data.fl[idx];
1005                     eval.data.fl[idx] = ( normfactor == 0.0F )
1006                         ? 0.0F : (eval.data.fl[idx] / normfactor);
1007                 }
1008
1009                 stump = (CvStumpClassifier*) trainParams.stumpConstructor( &eval,
1010                     CV_COL_SAMPLE,
1011                     weakTrainVals, 0, 0, 0, trimmedIdx,
1012                     &(data->weights),
1013                     trainParams.stumpTrainParams );
1014
1015                 classifier->threshold[i] = stump->threshold;
1016                 if( classifier->left[i] <= 0 )
1017                 {
1018                     classifier->val[-classifier->left[i]] = stump->left;
1019                 }
1020                 if( classifier->right[i] <= 0 )
1021                 {
1022                     classifier->val[-classifier->right[i]] = stump->right;
1023                 }
1024
1025                 stump->release( (CvClassifier**) &stump );
1026
1027             }
1028
1029             stumpTrainParams.getTrainData = icvGetTrainingDataCallback;
1030             stumpTrainParams.numcomp = n;
1031             stumpTrainParams.userdata = &userdata;
1032             stumpTrainParams.sortedIdx = data->idxcache;
1033
1034 #ifdef CV_VERBOSE
1035             v_flipped = 1;
1036 #endif /* CV_VERBOSE */
1037
1038         } /* if symmetric */
1039         if( trimmedIdx != sampleIdx )
1040         {
1041             cvReleaseMat( &trimmedIdx );
1042             trimmedIdx = NULL;
1043         }
1044
1045         for( i = 0; i < numsamples; i++ )
1046         {
1047             idx = icvGetIdxAt( sampleIdx, i );
1048
1049             eval.data.fl[idx] = classifier->eval( (CvIntHaarClassifier*) classifier,
1050                 (sum_type*) (data->sum.data.ptr + idx * data->sum.step),
1051                 (sum_type*) (data->tilted.data.ptr + idx * data->tilted.step),
1052                 data->normfactor.data.fl[idx] );
1053         }
1054
1055         alpha = cvBoostNextWeakClassifier( &eval, &data->cls, weakTrainVals,
1056                                            &data->weights, trainer );
1057         sumalpha += alpha;
1058
1059         for( i = 0; i <= classifier->count; i++ )
1060         {
1061             if( boosttype == CV_RABCLASS )
1062             {
1063                 classifier->val[i] = cvLogRatio( classifier->val[i] );
1064             }
1065             classifier->val[i] *= alpha;
1066         }
1067
1068         cvSeqPush( seq, (void*) &classifier );
1069
1070         numpos = 0;
1071         for( i = 0; i < numsamples; i++ )
1072         {
1073             idx = icvGetIdxAt( sampleIdx, i );
1074
1075             if( data->cls.data.fl[idx] == 1.0F )
1076             {
1077                 eval.data.fl[numpos] = 0.0F;
1078                 for( j = 0; j < seq->total; j++ )
1079                 {
1080                     classifier = *((CvCARTHaarClassifier**) cvGetSeqElem( seq, j ));
1081                     eval.data.fl[numpos] += classifier->eval(
1082                         (CvIntHaarClassifier*) classifier,
1083                         (sum_type*) (data->sum.data.ptr + idx * data->sum.step),
1084                         (sum_type*) (data->tilted.data.ptr + idx * data->tilted.step),
1085                         data->normfactor.data.fl[idx] );
1086                 }
1087                 /* eval.data.fl[numpos] = 2.0F * eval.data.fl[numpos] - seq->total; */
1088                 numpos++;
1089             }
1090         }
1091         std::sort(eval.data.fl, eval.data.fl + numpos);
1092         threshold = eval.data.fl[(int) ((1.0F - minhitrate) * numpos)];
1093
1094         numneg = 0;
1095         numfalse = 0;
1096         for( i = 0; i < numsamples; i++ )
1097         {
1098             idx = icvGetIdxAt( sampleIdx, i );
1099
1100             if( data->cls.data.fl[idx] == 0.0F )
1101             {
1102                 numneg++;
1103                 sum_stage = 0.0F;
1104                 for( j = 0; j < seq->total; j++ )
1105                 {
1106                    classifier = *((CvCARTHaarClassifier**) cvGetSeqElem( seq, j ));
1107                    sum_stage += classifier->eval( (CvIntHaarClassifier*) classifier,
1108                         (sum_type*) (data->sum.data.ptr + idx * data->sum.step),
1109                         (sum_type*) (data->tilted.data.ptr + idx * data->tilted.step),
1110                         data->normfactor.data.fl[idx] );
1111                 }
1112                 /* sum_stage = 2.0F * sum_stage - seq->total; */
1113                 if( sum_stage >= (threshold - CV_THRESHOLD_EPS) )
1114                 {
1115                     numfalse++;
1116                 }
1117             }
1118         }
1119         falsealarm = ((float) numfalse) / ((float) numneg);
1120
1121 #ifdef CV_VERBOSE
1122         {
1123             float v_hitrate    = 0.0F;
1124             float v_falsealarm = 0.0F;
1125             /* expected error of stage classifier regardless threshold */
1126             float v_experr = 0.0F;
1127
1128             for( i = 0; i < numsamples; i++ )
1129             {
1130                 idx = icvGetIdxAt( sampleIdx, i );
1131
1132                 sum_stage = 0.0F;
1133                 for( j = 0; j < seq->total; j++ )
1134                 {
1135                     classifier = *((CvCARTHaarClassifier**) cvGetSeqElem( seq, j ));
1136                     sum_stage += classifier->eval( (CvIntHaarClassifier*) classifier,
1137                         (sum_type*) (data->sum.data.ptr + idx * data->sum.step),
1138                         (sum_type*) (data->tilted.data.ptr + idx * data->tilted.step),
1139                         data->normfactor.data.fl[idx] );
1140                 }
1141                 /* sum_stage = 2.0F * sum_stage - seq->total; */
1142                 if( sum_stage >= (threshold - CV_THRESHOLD_EPS) )
1143                 {
1144                     if( data->cls.data.fl[idx] == 1.0F )
1145                     {
1146                         v_hitrate += 1.0F;
1147                     }
1148                     else
1149                     {
1150                         v_falsealarm += 1.0F;
1151                     }
1152                 }
1153                 if( ( sum_stage >= 0.0F ) != (data->cls.data.fl[idx] == 1.0F) )
1154                 {
1155                     v_experr += 1.0F;
1156                 }
1157             }
1158             v_experr /= numsamples;
1159             printf( "|%4d|%3d%%|%c|%9f|%9f|%9f|%9f|\n",
1160                 seq->total, v_wt, ( (v_flipped) ? '+' : '-' ),
1161                 threshold, v_hitrate / numpos, v_falsealarm / numneg,
1162                 v_experr );
1163             printf( "+----+----+-+---------+---------+---------+---------+\n" );
1164             fflush( stdout );
1165         }
1166 #endif /* CV_VERBOSE */
1167
1168     } while( falsealarm > maxfalsealarm && (!maxsplits || (num_splits < maxsplits) ) );
1169     cvBoostEndTraining( &trainer );
1170
1171     if( falsealarm > maxfalsealarm )
1172     {
1173         stage = NULL;
1174     }
1175     else
1176     {
1177         stage = (CvStageHaarClassifier*) icvCreateStageHaarClassifier( seq->total,
1178                                                                        threshold );
1179         cvCvtSeqToArray( seq, (CvArr*) stage->classifier );
1180     }
1181
1182     /* CLEANUP */
1183     cvReleaseMemStorage( &storage );
1184     cvReleaseMat( &weakTrainVals );
1185     cvFree( &(eval.data.ptr) );
1186
1187     return (CvIntHaarClassifier*) stage;
1188 }
1189
1190
1191 static
1192 CvBackgroundData* icvCreateBackgroundData( const char* filename, CvSize winsize )
1193 {
1194     CvBackgroundData* data = NULL;
1195
1196     const char* dir = NULL;
1197     char full[PATH_MAX];
1198     char* imgfilename = NULL;
1199     size_t datasize = 0;
1200     int    count = 0;
1201     FILE*  input = NULL;
1202     char*  tmp   = NULL;
1203     int    len   = 0;
1204
1205     assert( filename != NULL );
1206
1207     dir = strrchr( filename, '\\' );
1208     if( dir == NULL )
1209     {
1210         dir = strrchr( filename, '/' );
1211     }
1212     if( dir == NULL )
1213     {
1214         imgfilename = &(full[0]);
1215     }
1216     else
1217     {
1218         strncpy( &(full[0]), filename, (dir - filename + 1) );
1219         imgfilename = &(full[(dir - filename + 1)]);
1220     }
1221
1222     input = fopen( filename, "r" );
1223     if( input != NULL )
1224     {
1225         count = 0;
1226         datasize = 0;
1227
1228         /* count */
1229         while( !feof( input ) )
1230         {
1231             *imgfilename = '\0';
1232             if( !fgets( imgfilename, PATH_MAX - (int)(imgfilename - full) - 1, input ))
1233                 break;
1234             len = (int)strlen( imgfilename );
1235             for( ; len > 0 && isspace(imgfilename[len-1]); len-- )
1236                 imgfilename[len-1] = '\0';
1237             if( len > 0 )
1238             {
1239                 if( (*imgfilename) == '#' ) continue; /* comment */
1240                 count++;
1241                 datasize += sizeof( char ) * (strlen( &(full[0]) ) + 1);
1242             }
1243         }
1244         if( count > 0 )
1245         {
1246             //rewind( input );
1247             fseek( input, 0, SEEK_SET );
1248             datasize += sizeof( *data ) + sizeof( char* ) * count;
1249             data = (CvBackgroundData*) cvAlloc( datasize );
1250             memset( (void*) data, 0, datasize );
1251             data->count = count;
1252             data->filename = (char**) (data + 1);
1253             data->last = 0;
1254             data->round = 0;
1255             data->winsize = winsize;
1256             tmp = (char*) (data->filename + data->count);
1257             count = 0;
1258             while( !feof( input ) )
1259             {
1260                 *imgfilename = '\0';
1261                 if( !fgets( imgfilename, PATH_MAX - (int)(imgfilename - full) - 1, input ))
1262                     break;
1263                 len = (int)strlen( imgfilename );
1264                 if( len > 0 && imgfilename[len-1] == '\n' )
1265                     imgfilename[len-1] = 0, len--;
1266                 if( len > 0 )
1267                 {
1268                     if( (*imgfilename) == '#' ) continue; /* comment */
1269                     data->filename[count++] = tmp;
1270                     strcpy( tmp, &(full[0]) );
1271                     tmp += strlen( &(full[0]) ) + 1;
1272                 }
1273             }
1274         }
1275         fclose( input );
1276     }
1277
1278     return data;
1279 }
1280
1281 static
1282 void icvReleaseBackgroundData( CvBackgroundData** data )
1283 {
1284     assert( data != NULL && (*data) != NULL );
1285
1286     cvFree( data );
1287 }
1288
1289 static
1290 CvBackgroundReader* icvCreateBackgroundReader()
1291 {
1292     CvBackgroundReader* reader = NULL;
1293
1294     reader = (CvBackgroundReader*) cvAlloc( sizeof( *reader ) );
1295     memset( (void*) reader, 0, sizeof( *reader ) );
1296     reader->src = cvMat( 0, 0, CV_8UC1, NULL );
1297     reader->img = cvMat( 0, 0, CV_8UC1, NULL );
1298     reader->offset = cvPoint( 0, 0 );
1299     reader->scale       = 1.0F;
1300     reader->scalefactor = 1.4142135623730950488016887242097F;
1301     reader->stepfactor  = 0.5F;
1302     reader->point = reader->offset;
1303
1304     return reader;
1305 }
1306
1307 static
1308 void icvReleaseBackgroundReader( CvBackgroundReader** reader )
1309 {
1310     assert( reader != NULL && (*reader) != NULL );
1311
1312     if( (*reader)->src.data.ptr != NULL )
1313     {
1314         cvFree( &((*reader)->src.data.ptr) );
1315     }
1316     if( (*reader)->img.data.ptr != NULL )
1317     {
1318         cvFree( &((*reader)->img.data.ptr) );
1319     }
1320
1321     cvFree( reader );
1322 }
1323
1324 static
1325 void icvGetNextFromBackgroundData( CvBackgroundData* data,
1326                                    CvBackgroundReader* reader )
1327 {
1328     IplImage* img = NULL;
1329     size_t datasize = 0;
1330     int round = 0;
1331     int i = 0;
1332     CvPoint offset = cvPoint(0,0);
1333
1334     assert( data != NULL && reader != NULL );
1335
1336     if( reader->src.data.ptr != NULL )
1337     {
1338         cvFree( &(reader->src.data.ptr) );
1339         reader->src.data.ptr = NULL;
1340     }
1341     if( reader->img.data.ptr != NULL )
1342     {
1343         cvFree( &(reader->img.data.ptr) );
1344         reader->img.data.ptr = NULL;
1345     }
1346
1347     #ifdef CV_OPENMP
1348     #pragma omp critical(c_background_data)
1349     #endif /* CV_OPENMP */
1350     {
1351         for( i = 0; i < data->count; i++ )
1352         {
1353             round = data->round;
1354
1355 //#ifdef CV_VERBOSE
1356 //            printf( "Open background image: %s\n", data->filename[data->last] );
1357 //#endif /* CV_VERBOSE */
1358
1359             data->last = rand() % data->count;
1360             data->last %= data->count;
1361             img = cvLoadImage( data->filename[data->last], 0 );
1362             if( !img )
1363                 continue;
1364             data->round += data->last / data->count;
1365             data->round = data->round % (data->winsize.width * data->winsize.height);
1366
1367             offset.x = round % data->winsize.width;
1368             offset.y = round / data->winsize.width;
1369
1370             offset.x = MIN( offset.x, img->width - data->winsize.width );
1371             offset.y = MIN( offset.y, img->height - data->winsize.height );
1372
1373             if( img != NULL && img->depth == IPL_DEPTH_8U && img->nChannels == 1 &&
1374                 offset.x >= 0 && offset.y >= 0 )
1375             {
1376                 break;
1377             }
1378             if( img != NULL )
1379                 cvReleaseImage( &img );
1380             img = NULL;
1381         }
1382     }
1383     if( img == NULL )
1384     {
1385         /* no appropriate image */
1386
1387 #ifdef CV_VERBOSE
1388         printf( "Invalid background description file.\n" );
1389 #endif /* CV_VERBOSE */
1390
1391         assert( 0 );
1392         exit( 1 );
1393     }
1394     datasize = sizeof( uchar ) * img->width * img->height;
1395     reader->src = cvMat( img->height, img->width, CV_8UC1, (void*) cvAlloc( datasize ) );
1396     cvCopy( img, &reader->src, NULL );
1397     cvReleaseImage( &img );
1398     img = NULL;
1399
1400     //reader->offset.x = round % data->winsize.width;
1401     //reader->offset.y = round / data->winsize.width;
1402     reader->offset = offset;
1403     reader->point = reader->offset;
1404     reader->scale = MAX(
1405         ((float) data->winsize.width + reader->point.x) / ((float) reader->src.cols),
1406         ((float) data->winsize.height + reader->point.y) / ((float) reader->src.rows) );
1407
1408     reader->img = cvMat( (int) (reader->scale * reader->src.rows + 0.5F),
1409                          (int) (reader->scale * reader->src.cols + 0.5F),
1410                           CV_8UC1, (void*) cvAlloc( datasize ) );
1411     cvResize( &(reader->src), &(reader->img) );
1412 }
1413
1414
1415 /*
1416  * icvGetBackgroundImage
1417  *
1418  * Get an image from background
1419  * <img> must be allocated and have size, previously passed to icvInitBackgroundReaders
1420  *
1421  * Usage example:
1422  * icvInitBackgroundReaders( "bg.txt", cvSize( 24, 24 ) );
1423  * ...
1424  * #pragma omp parallel
1425  * {
1426  *     ...
1427  *     icvGetBackgourndImage( cvbgdata, cvbgreader, img );
1428  *     ...
1429  * }
1430  * ...
1431  * icvDestroyBackgroundReaders();
1432  */
1433 static
1434 void icvGetBackgroundImage( CvBackgroundData* data,
1435                             CvBackgroundReader* reader,
1436                             CvMat* img )
1437 {
1438     CvMat mat;
1439
1440     assert( data != NULL && reader != NULL && img != NULL );
1441     assert( CV_MAT_TYPE( img->type ) == CV_8UC1 );
1442     assert( img->cols == data->winsize.width );
1443     assert( img->rows == data->winsize.height );
1444
1445     if( reader->img.data.ptr == NULL )
1446     {
1447         icvGetNextFromBackgroundData( data, reader );
1448     }
1449
1450     mat = cvMat( data->winsize.height, data->winsize.width, CV_8UC1 );
1451     cvSetData( &mat, (void*) (reader->img.data.ptr + reader->point.y * reader->img.step
1452                               + reader->point.x * sizeof( uchar )), reader->img.step );
1453
1454     cvCopy( &mat, img, 0 );
1455     if( (int) ( reader->point.x + (1.0F + reader->stepfactor ) * data->winsize.width )
1456             < reader->img.cols )
1457     {
1458         reader->point.x += (int) (reader->stepfactor * data->winsize.width);
1459     }
1460     else
1461     {
1462         reader->point.x = reader->offset.x;
1463         if( (int) ( reader->point.y + (1.0F + reader->stepfactor ) * data->winsize.height )
1464                 < reader->img.rows )
1465         {
1466             reader->point.y += (int) (reader->stepfactor * data->winsize.height);
1467         }
1468         else
1469         {
1470             reader->point.y = reader->offset.y;
1471             reader->scale *= reader->scalefactor;
1472             if( reader->scale <= 1.0F )
1473             {
1474                 reader->img = cvMat( (int) (reader->scale * reader->src.rows),
1475                                      (int) (reader->scale * reader->src.cols),
1476                                       CV_8UC1, (void*) (reader->img.data.ptr) );
1477                 cvResize( &(reader->src), &(reader->img) );
1478             }
1479             else
1480             {
1481                 icvGetNextFromBackgroundData( data, reader );
1482             }
1483         }
1484     }
1485 }
1486
1487
1488 /*
1489  * icvInitBackgroundReaders
1490  *
1491  * Initialize background reading process.
1492  * <cvbgreader> and <cvbgdata> are initialized.
1493  * Must be called before any usage of background
1494  *
1495  * filename - name of background description file
1496  * winsize  - size of images will be obtained from background
1497  *
1498  * return 1 on success, 0 otherwise.
1499  */
1500 static
1501 int icvInitBackgroundReaders( const char* filename, CvSize winsize )
1502 {
1503     if( cvbgdata == NULL && filename != NULL )
1504     {
1505         cvbgdata = icvCreateBackgroundData( filename, winsize );
1506     }
1507
1508     if( cvbgdata )
1509     {
1510
1511         #ifdef CV_OPENMP
1512         #pragma omp parallel
1513         #endif /* CV_OPENMP */
1514         {
1515             #ifdef CV_OPENMP
1516             #pragma omp critical(c_create_bg_data)
1517             #endif /* CV_OPENMP */
1518             {
1519                 if( cvbgreader == NULL )
1520                 {
1521                     cvbgreader = icvCreateBackgroundReader();
1522                 }
1523             }
1524         }
1525
1526     }
1527
1528     return (cvbgdata != NULL);
1529 }
1530
1531
1532 /*
1533  * icvDestroyBackgroundReaders
1534  *
1535  * Finish backgournd reading process
1536  */
1537 static
1538 void icvDestroyBackgroundReaders()
1539 {
1540     /* release background reader in each thread */
1541     #ifdef CV_OPENMP
1542     #pragma omp parallel
1543     #endif /* CV_OPENMP */
1544     {
1545         #ifdef CV_OPENMP
1546         #pragma omp critical(c_release_bg_data)
1547         #endif /* CV_OPENMP */
1548         {
1549             if( cvbgreader != NULL )
1550             {
1551                 icvReleaseBackgroundReader( &cvbgreader );
1552                 cvbgreader = NULL;
1553             }
1554         }
1555     }
1556
1557     if( cvbgdata != NULL )
1558     {
1559         icvReleaseBackgroundData( &cvbgdata );
1560         cvbgdata = NULL;
1561     }
1562 }
1563
1564
1565 /*
1566  * icvGetAuxImages
1567  *
1568  * Get sum, tilted, sqsum images and calculate normalization factor
1569  * All images must be allocated.
1570  */
1571 static
1572 void icvGetAuxImages( CvMat* img, CvMat* sum, CvMat* tilted,
1573                       CvMat* sqsum, float* normfactor )
1574 {
1575     CvRect normrect;
1576     int p0, p1, p2, p3;
1577     sum_type   valsum   = 0;
1578     sqsum_type valsqsum = 0;
1579     double area = 0.0;
1580
1581     cvIntegral( img, sum, sqsum, tilted );
1582     normrect = cvRect( 1, 1, img->cols - 2, img->rows - 2 );
1583     CV_SUM_OFFSETS( p0, p1, p2, p3, normrect, img->cols + 1 )
1584
1585     area = normrect.width * normrect.height;
1586     valsum = ((sum_type*) (sum->data.ptr))[p0] - ((sum_type*) (sum->data.ptr))[p1]
1587            - ((sum_type*) (sum->data.ptr))[p2] + ((sum_type*) (sum->data.ptr))[p3];
1588     valsqsum = ((sqsum_type*) (sqsum->data.ptr))[p0]
1589              - ((sqsum_type*) (sqsum->data.ptr))[p1]
1590              - ((sqsum_type*) (sqsum->data.ptr))[p2]
1591              + ((sqsum_type*) (sqsum->data.ptr))[p3];
1592
1593     /* sqrt( valsqsum / area - ( valsum / are )^2 ) * area */
1594     (*normfactor) = (float) sqrt( (double) (area * valsqsum - (double)valsum * valsum) );
1595 }
1596
1597
1598 /* consumed counter */
1599 typedef uint64 ccounter_t;
1600
1601 #define CCOUNTER_MAX CV_BIG_UINT(0xffffffffffffffff)
1602 #define CCOUNTER_SET_ZERO(cc) ((cc) = 0)
1603 #define CCOUNTER_INC(cc) ( (CCOUNTER_MAX > (cc) ) ? (++(cc)) : (CCOUNTER_MAX) )
1604 #define CCOUNTER_ADD(cc0, cc1) ( ((CCOUNTER_MAX-(cc1)) > (cc0) ) ? ((cc0) += (cc1)) : ((cc0) = CCOUNTER_MAX) )
1605 #define CCOUNTER_DIV(cc0, cc1) ( ((cc1) == 0) ? 0 : ( ((double)(cc0))/(double)(int64)(cc1) ) )
1606
1607
1608
1609 /*
1610  * icvGetHaarTrainingData
1611  *
1612  * Unified method that can now be used for vec file, bg file and bg vec file
1613  *
1614  * Fill <data> with samples, passed <cascade>
1615  */
1616 static
1617 int icvGetHaarTrainingData( CvHaarTrainingData* data, int first, int count,
1618                             CvIntHaarClassifier* cascade,
1619                             CvGetHaarTrainingDataCallback callback, void* userdata,
1620                             int* consumed, double* acceptance_ratio )
1621 {
1622     int i = 0;
1623     ccounter_t getcount = 0;
1624     ccounter_t thread_getcount = 0;
1625     ccounter_t consumed_count;
1626     ccounter_t thread_consumed_count;
1627
1628     /* private variables */
1629     CvMat img;
1630     CvMat sum;
1631     CvMat tilted;
1632     CvMat sqsum;
1633
1634     sum_type* sumdata;
1635     sum_type* tilteddata;
1636     float*    normfactor;
1637
1638     /* end private variables */
1639
1640     assert( data != NULL );
1641     assert( first + count <= data->maxnum );
1642     assert( cascade != NULL );
1643     assert( callback != NULL );
1644
1645     // if( !cvbgdata ) return 0; this check needs to be done in the callback for BG
1646
1647     CCOUNTER_SET_ZERO(getcount);
1648     CCOUNTER_SET_ZERO(thread_getcount);
1649     CCOUNTER_SET_ZERO(consumed_count);
1650     CCOUNTER_SET_ZERO(thread_consumed_count);
1651
1652     #ifdef CV_OPENMP
1653     #pragma omp parallel private(img, sum, tilted, sqsum, sumdata, tilteddata, \
1654                                  normfactor, thread_consumed_count, thread_getcount)
1655     #endif /* CV_OPENMP */
1656     {
1657         sumdata    = NULL;
1658         tilteddata = NULL;
1659         normfactor = NULL;
1660
1661         CCOUNTER_SET_ZERO(thread_getcount);
1662         CCOUNTER_SET_ZERO(thread_consumed_count);
1663         int ok = 1;
1664
1665         img = cvMat( data->winsize.height, data->winsize.width, CV_8UC1,
1666             cvAlloc( sizeof( uchar ) * data->winsize.height * data->winsize.width ) );
1667         sum = cvMat( data->winsize.height + 1, data->winsize.width + 1,
1668                      CV_SUM_MAT_TYPE, NULL );
1669         tilted = cvMat( data->winsize.height + 1, data->winsize.width + 1,
1670                         CV_SUM_MAT_TYPE, NULL );
1671         sqsum = cvMat( data->winsize.height + 1, data->winsize.width + 1, CV_SQSUM_MAT_TYPE,
1672                        cvAlloc( sizeof( sqsum_type ) * (data->winsize.height + 1)
1673                                                      * (data->winsize.width + 1) ) );
1674
1675         #ifdef CV_OPENMP
1676         #pragma omp for schedule(static, 1)
1677         #endif /* CV_OPENMP */
1678         for( i = first; (i < first + count); i++ )
1679         {
1680             if( !ok )
1681                 continue;
1682             for( ; ; )
1683             {
1684                 ok = callback( &img, userdata );
1685                 if( !ok )
1686                     break;
1687
1688                 CCOUNTER_INC(thread_consumed_count);
1689
1690                 sumdata = (sum_type*) (data->sum.data.ptr + i * data->sum.step);
1691                 tilteddata = (sum_type*) (data->tilted.data.ptr + i * data->tilted.step);
1692                 normfactor = data->normfactor.data.fl + i;
1693                 sum.data.ptr = (uchar*) sumdata;
1694                 tilted.data.ptr = (uchar*) tilteddata;
1695                 icvGetAuxImages( &img, &sum, &tilted, &sqsum, normfactor );
1696                 if( cascade->eval( cascade, sumdata, tilteddata, *normfactor ) != 0.0F )
1697                 {
1698                     CCOUNTER_INC(thread_getcount);
1699                     break;
1700                 }
1701             }
1702
1703 #ifdef CV_VERBOSE
1704             if( (i - first) % 500 == 0 )
1705             {
1706                 fprintf( stderr, "%3d%%\r", (int) ( 100.0 * (i - first) / count ) );
1707                 fflush( stderr );
1708             }
1709 #endif /* CV_VERBOSE */
1710         }
1711
1712         cvFree( &(img.data.ptr) );
1713         cvFree( &(sqsum.data.ptr) );
1714
1715         #ifdef CV_OPENMP
1716         #pragma omp critical (c_consumed_count)
1717         #endif /* CV_OPENMP */
1718         {
1719             /* consumed_count += thread_consumed_count; */
1720             CCOUNTER_ADD(getcount, thread_getcount);
1721             CCOUNTER_ADD(consumed_count, thread_consumed_count);
1722         }
1723     } /* omp parallel */
1724
1725     if( consumed != NULL )
1726     {
1727         *consumed = (int)consumed_count;
1728     }
1729
1730     if( acceptance_ratio != NULL )
1731     {
1732         /* *acceptance_ratio = ((double) count) / consumed_count; */
1733         *acceptance_ratio = CCOUNTER_DIV(count, consumed_count);
1734     }
1735
1736     return static_cast<int>(getcount);
1737 }
1738
1739 /*
1740  * icvGetHaarTrainingDataFromBG
1741  *
1742  * Fill <data> with background samples, passed <cascade>
1743  * Background reading process must be initialized before call.
1744  */
1745 //static
1746 //int icvGetHaarTrainingDataFromBG( CvHaarTrainingData* data, int first, int count,
1747 //                                  CvIntHaarClassifier* cascade, double* acceptance_ratio )
1748 //{
1749 //    int i = 0;
1750 //    ccounter_t consumed_count;
1751 //    ccounter_t thread_consumed_count;
1752 //
1753 //    /* private variables */
1754 //    CvMat img;
1755 //    CvMat sum;
1756 //    CvMat tilted;
1757 //    CvMat sqsum;
1758 //
1759 //    sum_type* sumdata;
1760 //    sum_type* tilteddata;
1761 //    float*    normfactor;
1762 //
1763 //    /* end private variables */
1764 //
1765 //    assert( data != NULL );
1766 //    assert( first + count <= data->maxnum );
1767 //    assert( cascade != NULL );
1768 //
1769 //    if( !cvbgdata ) return 0;
1770 //
1771 //    CCOUNTER_SET_ZERO(consumed_count);
1772 //    CCOUNTER_SET_ZERO(thread_consumed_count);
1773 //
1774 //    #ifdef CV_OPENMP
1775 //    #pragma omp parallel private(img, sum, tilted, sqsum, sumdata, tilteddata,
1776 //                                 normfactor, thread_consumed_count)
1777 //    #endif /* CV_OPENMP */
1778 //    {
1779 //        sumdata    = NULL;
1780 //        tilteddata = NULL;
1781 //        normfactor = NULL;
1782 //
1783 //        CCOUNTER_SET_ZERO(thread_consumed_count);
1784 //
1785 //        img = cvMat( data->winsize.height, data->winsize.width, CV_8UC1,
1786 //            cvAlloc( sizeof( uchar ) * data->winsize.height * data->winsize.width ) );
1787 //        sum = cvMat( data->winsize.height + 1, data->winsize.width + 1,
1788 //                     CV_SUM_MAT_TYPE, NULL );
1789 //        tilted = cvMat( data->winsize.height + 1, data->winsize.width + 1,
1790 //                        CV_SUM_MAT_TYPE, NULL );
1791 //        sqsum = cvMat( data->winsize.height + 1, data->winsize.width + 1,
1792 //                       CV_SQSUM_MAT_TYPE,
1793 //                       cvAlloc( sizeof( sqsum_type ) * (data->winsize.height + 1)
1794 //                                                     * (data->winsize.width + 1) ) );
1795 //
1796 //        #ifdef CV_OPENMP
1797 //        #pragma omp for schedule(static, 1)
1798 //        #endif /* CV_OPENMP */
1799 //        for( i = first; i < first + count; i++ )
1800 //        {
1801 //            for( ; ; )
1802 //            {
1803 //                icvGetBackgroundImage( cvbgdata, cvbgreader, &img );
1804 //
1805 //                CCOUNTER_INC(thread_consumed_count);
1806 //
1807 //                sumdata = (sum_type*) (data->sum.data.ptr + i * data->sum.step);
1808 //                tilteddata = (sum_type*) (data->tilted.data.ptr + i * data->tilted.step);
1809 //                normfactor = data->normfactor.data.fl + i;
1810 //                sum.data.ptr = (uchar*) sumdata;
1811 //                tilted.data.ptr = (uchar*) tilteddata;
1812 //                icvGetAuxImages( &img, &sum, &tilted, &sqsum, normfactor );
1813 //                if( cascade->eval( cascade, sumdata, tilteddata, *normfactor ) != 0.0F )
1814 //                {
1815 //                    break;
1816 //                }
1817 //            }
1818 //
1819 //#ifdef CV_VERBOSE
1820 //            if( (i - first) % 500 == 0 )
1821 //            {
1822 //                fprintf( stderr, "%3d%%\r", (int) ( 100.0 * (i - first) / count ) );
1823 //                fflush( stderr );
1824 //            }
1825 //#endif /* CV_VERBOSE */
1826 //
1827 //        }
1828 //
1829 //        cvFree( &(img.data.ptr) );
1830 //        cvFree( &(sqsum.data.ptr) );
1831 //
1832 //        #ifdef CV_OPENMP
1833 //        #pragma omp critical (c_consumed_count)
1834 //        #endif /* CV_OPENMP */
1835 //        {
1836 //            /* consumed_count += thread_consumed_count; */
1837 //            CCOUNTER_ADD(consumed_count, thread_consumed_count);
1838 //        }
1839 //    } /* omp parallel */
1840 //
1841 //    if( acceptance_ratio != NULL )
1842 //    {
1843 //        /* *acceptance_ratio = ((double) count) / consumed_count; */
1844 //        *acceptance_ratio = CCOUNTER_DIV(count, consumed_count);
1845 //    }
1846 //
1847 //    return count;
1848 //}
1849
1850 int icvGetHaarTraininDataFromVecCallback( CvMat* img, void* userdata )
1851 {
1852     uchar tmp = 0;
1853     int r = 0;
1854     int c = 0;
1855
1856     assert( img->rows * img->cols == ((CvVecFile*) userdata)->vecsize );
1857
1858     size_t elements_read = fread( &tmp, sizeof( tmp ), 1, ((CvVecFile*) userdata)->input );
1859     CV_Assert(elements_read == 1);
1860     elements_read = fread( ((CvVecFile*) userdata)->vector, sizeof( short ),
1861            ((CvVecFile*) userdata)->vecsize, ((CvVecFile*) userdata)->input );
1862     CV_Assert(elements_read == (size_t)((CvVecFile*) userdata)->vecsize);
1863
1864     if( feof( ((CvVecFile*) userdata)->input ) ||
1865         (((CvVecFile*) userdata)->last)++ >= ((CvVecFile*) userdata)->count )
1866     {
1867         return 0;
1868     }
1869
1870     for( r = 0; r < img->rows; r++ )
1871     {
1872         for( c = 0; c < img->cols; c++ )
1873         {
1874             CV_MAT_ELEM( *img, uchar, r, c ) =
1875                 (uchar) ( ((CvVecFile*) userdata)->vector[r * img->cols + c] );
1876         }
1877     }
1878
1879     return 1;
1880 }
1881
1882 static int icvGetHaarTrainingDataFromBGCallback ( CvMat* img, void* /*userdata*/ )
1883 {
1884     if (! cvbgdata)
1885       return 0;
1886
1887     if (! cvbgreader)
1888       return 0;
1889
1890     // just in case icvGetBackgroundImage is not thread-safe ...
1891     #ifdef CV_OPENMP
1892     #pragma omp critical (get_background_image_callback)
1893     #endif /* CV_OPENMP */
1894     {
1895       icvGetBackgroundImage( cvbgdata, cvbgreader, img );
1896     }
1897
1898     return 1;
1899 }
1900
1901 /*
1902  * icvGetHaarTrainingDataFromVec
1903  * Get training data from .vec file
1904  */
1905 static
1906 int icvGetHaarTrainingDataFromVec( CvHaarTrainingData* data, int first, int count,
1907                                    CvIntHaarClassifier* cascade,
1908                                    const char* filename,
1909                                    int* consumed )
1910 {
1911     int getcount = 0;
1912
1913     CV_FUNCNAME( "icvGetHaarTrainingDataFromVec" );
1914
1915     __BEGIN__;
1916
1917     CvVecFile file;
1918     short tmp = 0;
1919
1920     file.input = NULL;
1921     if( filename ) file.input = fopen( filename, "rb" );
1922
1923     if( file.input != NULL )
1924     {
1925         size_t elements_read1 = fread( &file.count, sizeof( file.count ), 1, file.input );
1926         size_t elements_read2 = fread( &file.vecsize, sizeof( file.vecsize ), 1, file.input );
1927         size_t elements_read3 = fread( &tmp, sizeof( tmp ), 1, file.input );
1928         size_t elements_read4 = fread( &tmp, sizeof( tmp ), 1, file.input );
1929         CV_Assert(elements_read1 == 1 && elements_read2 == 1 && elements_read3 == 1 && elements_read4 == 1);
1930
1931         if( !feof( file.input ) )
1932         {
1933             if( file.vecsize != data->winsize.width * data->winsize.height )
1934             {
1935                 fclose( file.input );
1936                 CV_ERROR( CV_StsError, "Vec file sample size mismatch" );
1937             }
1938
1939             file.last = 0;
1940             file.vector = (short*) cvAlloc( sizeof( *file.vector ) * file.vecsize );
1941             getcount = icvGetHaarTrainingData( data, first, count, cascade,
1942                 icvGetHaarTraininDataFromVecCallback, &file, consumed, NULL);
1943             cvFree( &file.vector );
1944         }
1945         fclose( file.input );
1946     }
1947
1948     __END__;
1949
1950     return getcount;
1951 }
1952
1953 /*
1954  * icvGetHaarTrainingDataFromBG
1955  *
1956  * Fill <data> with background samples, passed <cascade>
1957  * Background reading process must be initialized before call, alternaly, a file
1958  * name to a vec file may be passed, a NULL filename indicates old behaviour
1959  */
1960 static
1961 int icvGetHaarTrainingDataFromBG( CvHaarTrainingData* data, int first, int count,
1962                                   CvIntHaarClassifier* cascade, double* acceptance_ratio, const char * filename = NULL )
1963 {
1964     CV_FUNCNAME( "icvGetHaarTrainingDataFromBG" );
1965
1966     __BEGIN__;
1967
1968     if (filename)
1969     {
1970         CvVecFile file;
1971         short tmp = 0;
1972
1973         file.input = NULL;
1974         if( filename ) file.input = fopen( filename, "rb" );
1975
1976         if( file.input != NULL )
1977         {
1978             size_t elements_read1 = fread( &file.count, sizeof( file.count ), 1, file.input );
1979             size_t elements_read2 = fread( &file.vecsize, sizeof( file.vecsize ), 1, file.input );
1980             size_t elements_read3 = fread( &tmp, sizeof( tmp ), 1, file.input );
1981             size_t elements_read4 = fread( &tmp, sizeof( tmp ), 1, file.input );
1982             CV_Assert(elements_read1 == 1 && elements_read2 == 1 && elements_read3 == 1 && elements_read4 == 1);
1983             if( !feof( file.input ) )
1984             {
1985                 if( file.vecsize != data->winsize.width * data->winsize.height )
1986                 {
1987                     fclose( file.input );
1988                     CV_ERROR( CV_StsError, "Vec file sample size mismatch" );
1989                 }
1990
1991                 file.last = 0;
1992                 file.vector = (short*) cvAlloc( sizeof( *file.vector ) * file.vecsize );
1993                 icvGetHaarTrainingData( data, first, count, cascade,
1994                     icvGetHaarTraininDataFromVecCallback, &file, NULL, acceptance_ratio);
1995                 cvFree( &file.vector );
1996             }
1997             fclose( file.input );
1998         }
1999     }
2000     else
2001     {
2002         icvGetHaarTrainingData( data, first, count, cascade,
2003             icvGetHaarTrainingDataFromBGCallback, NULL, NULL, acceptance_ratio);
2004     }
2005
2006     __END__;
2007
2008     return count;
2009 }
2010
2011 void cvCreateCascadeClassifier( const char* dirname,
2012                                 const char* vecfilename,
2013                                 const char* bgfilename,
2014                                 int npos, int nneg, int nstages,
2015                                 int numprecalculated,
2016                                 int numsplits,
2017                                 float minhitrate, float maxfalsealarm,
2018                                 float weightfraction,
2019                                 int mode, int symmetric,
2020                                 int equalweights,
2021                                 int winwidth, int winheight,
2022                                 int boosttype, int stumperror )
2023 {
2024     CvCascadeHaarClassifier* cascade = NULL;
2025     CvHaarTrainingData* data = NULL;
2026     CvIntHaarFeatures* haar_features;
2027     CvSize winsize;
2028     int i = 0;
2029     int j = 0;
2030     int poscount = 0;
2031     int negcount = 0;
2032     int consumed = 0;
2033     double false_alarm = 0;
2034     char stagename[PATH_MAX];
2035     float posweight = 1.0F;
2036     float negweight = 1.0F;
2037     FILE* file;
2038
2039 #ifdef CV_VERBOSE
2040     double proctime = 0.0F;
2041 #endif /* CV_VERBOSE */
2042
2043     assert( dirname != NULL );
2044     assert( bgfilename != NULL );
2045     assert( vecfilename != NULL );
2046     assert( nstages > 0 );
2047
2048     winsize = cvSize( winwidth, winheight );
2049
2050     cascade = (CvCascadeHaarClassifier*) icvCreateCascadeHaarClassifier( nstages );
2051     cascade->count = 0;
2052
2053     if( icvInitBackgroundReaders( bgfilename, winsize ) )
2054     {
2055         data = icvCreateHaarTrainingData( winsize, npos + nneg );
2056         haar_features = icvCreateIntHaarFeatures( winsize, mode, symmetric );
2057
2058 #ifdef CV_VERBOSE
2059         printf("Number of features used : %d\n", haar_features->count);
2060 #endif /* CV_VERBOSE */
2061
2062         for( i = 0; i < nstages; i++, cascade->count++ )
2063         {
2064             sprintf( stagename, "%s%d/%s", dirname, i, CV_STAGE_CART_FILE_NAME );
2065             cascade->classifier[i] =
2066                 icvLoadCARTStageHaarClassifier( stagename, winsize.width + 1 );
2067
2068             if( !icvMkDir( stagename ) )
2069             {
2070
2071 #ifdef CV_VERBOSE
2072                 printf( "UNABLE TO CREATE DIRECTORY: %s\n", stagename );
2073 #endif /* CV_VERBOSE */
2074
2075                 break;
2076             }
2077             if( cascade->classifier[i] != NULL )
2078             {
2079
2080 #ifdef CV_VERBOSE
2081                 printf( "STAGE: %d LOADED.\n", i );
2082 #endif /* CV_VERBOSE */
2083
2084                 continue;
2085             }
2086
2087 #ifdef CV_VERBOSE
2088             printf( "STAGE: %d\n", i );
2089 #endif /* CV_VERBOSE */
2090
2091             poscount = icvGetHaarTrainingDataFromVec( data, 0, npos,
2092                 (CvIntHaarClassifier*) cascade, vecfilename, &consumed );
2093 #ifdef CV_VERBOSE
2094             printf( "POS: %d %d %f\n", poscount, consumed,
2095                     ((float) poscount) / consumed );
2096 #endif /* CV_VERBOSE */
2097
2098             if( poscount <= 0 )
2099             {
2100
2101 #ifdef CV_VERBOSE
2102             printf( "UNABLE TO OBTAIN POS SAMPLES\n" );
2103 #endif /* CV_VERBOSE */
2104
2105                 break;
2106             }
2107
2108 #ifdef CV_VERBOSE
2109             proctime = -TIME( 0 );
2110 #endif /* CV_VERBOSE */
2111
2112             negcount = icvGetHaarTrainingDataFromBG( data, poscount, nneg,
2113                 (CvIntHaarClassifier*) cascade, &false_alarm );
2114 #ifdef CV_VERBOSE
2115             printf( "NEG: %d %g\n", negcount, false_alarm );
2116             printf( "BACKGROUND PROCESSING TIME: %.2f\n",
2117                 (proctime + TIME( 0 )) );
2118 #endif /* CV_VERBOSE */
2119
2120             if( negcount <= 0 )
2121             {
2122
2123 #ifdef CV_VERBOSE
2124             printf( "UNABLE TO OBTAIN NEG SAMPLES\n" );
2125 #endif /* CV_VERBOSE */
2126
2127                 break;
2128             }
2129
2130             data->sum.rows = data->tilted.rows = poscount + negcount;
2131             data->normfactor.cols = data->weights.cols = data->cls.cols =
2132                     poscount + negcount;
2133
2134             posweight = (equalweights) ? 1.0F / (poscount + negcount) : (0.5F / poscount);
2135             negweight = (equalweights) ? 1.0F / (poscount + negcount) : (0.5F / negcount);
2136             for( j = 0; j < poscount; j++ )
2137             {
2138                 data->weights.data.fl[j] = posweight;
2139                 data->cls.data.fl[j] = 1.0F;
2140
2141             }
2142             for( j = poscount; j < poscount + negcount; j++ )
2143             {
2144                 data->weights.data.fl[j] = negweight;
2145                 data->cls.data.fl[j] = 0.0F;
2146             }
2147
2148 #ifdef CV_VERBOSE
2149             proctime = -TIME( 0 );
2150 #endif /* CV_VERBOSE */
2151
2152             icvPrecalculate( data, haar_features, numprecalculated );
2153
2154 #ifdef CV_VERBOSE
2155             printf( "PRECALCULATION TIME: %.2f\n", (proctime + TIME( 0 )) );
2156 #endif /* CV_VERBOSE */
2157
2158 #ifdef CV_VERBOSE
2159             proctime = -TIME( 0 );
2160 #endif /* CV_VERBOSE */
2161
2162             cascade->classifier[i] = icvCreateCARTStageClassifier(  data, NULL,
2163                 haar_features, minhitrate, maxfalsealarm, symmetric, weightfraction,
2164                 numsplits, (CvBoostType) boosttype, (CvStumpError) stumperror, 0 );
2165
2166 #ifdef CV_VERBOSE
2167             printf( "STAGE TRAINING TIME: %.2f\n", (proctime + TIME( 0 )) );
2168 #endif /* CV_VERBOSE */
2169
2170             file = fopen( stagename, "w" );
2171             if( file != NULL )
2172             {
2173                 cascade->classifier[i]->save(
2174                     (CvIntHaarClassifier*) cascade->classifier[i], file );
2175                 fclose( file );
2176             }
2177             else
2178             {
2179
2180 #ifdef CV_VERBOSE
2181                 printf( "FAILED TO SAVE STAGE CLASSIFIER IN FILE %s\n", stagename );
2182 #endif /* CV_VERBOSE */
2183
2184             }
2185
2186         }
2187         icvReleaseIntHaarFeatures( &haar_features );
2188         icvReleaseHaarTrainingData( &data );
2189
2190         if( i == nstages )
2191         {
2192             char xml_path[1024];
2193             int len = (int)strlen(dirname);
2194             CvHaarClassifierCascade* cascade1 = 0;
2195             strcpy( xml_path, dirname );
2196             if( xml_path[len-1] == '\\' || xml_path[len-1] == '/' )
2197                 len--;
2198             strcpy( xml_path + len, ".xml" );
2199             cascade1 = cvLoadHaarClassifierCascade( dirname, cvSize(winwidth,winheight) );
2200             if( cascade1 )
2201                 cvSave( xml_path, cascade1 );
2202             cvReleaseHaarClassifierCascade( &cascade1 );
2203         }
2204     }
2205     else
2206     {
2207 #ifdef CV_VERBOSE
2208         printf( "FAILED TO INITIALIZE BACKGROUND READERS\n" );
2209 #endif /* CV_VERBOSE */
2210     }
2211
2212     /* CLEAN UP */
2213     icvDestroyBackgroundReaders();
2214     cascade->release( (CvIntHaarClassifier**) &cascade );
2215 }
2216
2217 /* tree cascade classifier */
2218
2219 static int icvNumSplits( CvStageHaarClassifier* stage )
2220 {
2221     int i;
2222     int num;
2223
2224     num = 0;
2225     for( i = 0; i < stage->count; i++ )
2226     {
2227         num += ((CvCARTHaarClassifier*) stage->classifier[i])->count;
2228     }
2229
2230     return num;
2231 }
2232
2233 static void icvSetNumSamples( CvHaarTrainingData* training_data, int num )
2234 {
2235     assert( num <= training_data->maxnum );
2236
2237     training_data->sum.rows = training_data->tilted.rows = num;
2238     training_data->normfactor.cols = num;
2239     training_data->cls.cols = training_data->weights.cols = num;
2240 }
2241
2242 static void icvSetWeightsAndClasses( CvHaarTrainingData* training_data,
2243                               int num1, float weight1, float cls1,
2244                               int num2, float weight2, float cls2 )
2245 {
2246     int j;
2247
2248     assert( num1 + num2 <= training_data->maxnum );
2249
2250     for( j = 0; j < num1; j++ )
2251     {
2252         training_data->weights.data.fl[j] = weight1;
2253         training_data->cls.data.fl[j] = cls1;
2254     }
2255     for( j = num1; j < num1 + num2; j++ )
2256     {
2257         training_data->weights.data.fl[j] = weight2;
2258         training_data->cls.data.fl[j] = cls2;
2259     }
2260 }
2261
2262 static CvMat* icvGetUsedValues( CvHaarTrainingData* training_data,
2263                          int start, int num,
2264                          CvIntHaarFeatures* haar_features,
2265                          CvStageHaarClassifier* stage )
2266 {
2267     CvMat* ptr = NULL;
2268     CvMat* feature_idx = NULL;
2269
2270     CV_FUNCNAME( "icvGetUsedValues" );
2271
2272     __BEGIN__;
2273
2274     int num_splits;
2275     int i, j;
2276     int r;
2277     int total, last;
2278
2279     num_splits = icvNumSplits( stage );
2280
2281     CV_CALL( feature_idx = cvCreateMat( 1, num_splits, CV_32SC1 ) );
2282
2283     total = 0;
2284     for( i = 0; i < stage->count; i++ )
2285     {
2286         CvCARTHaarClassifier* cart;
2287
2288         cart = (CvCARTHaarClassifier*) stage->classifier[i];
2289         for( j = 0; j < cart->count; j++ )
2290         {
2291             feature_idx->data.i[total++] = cart->compidx[j];
2292         }
2293     }
2294     std::sort(feature_idx->data.i, feature_idx->data.i + total);
2295
2296     last = 0;
2297     for( i = 1; i < total; i++ )
2298     {
2299         if( feature_idx->data.i[i] != feature_idx->data.i[last] )
2300         {
2301             feature_idx->data.i[++last] = feature_idx->data.i[i];
2302         }
2303     }
2304     total = last + 1;
2305     CV_CALL( ptr = cvCreateMat( num, total, CV_32FC1 ) );
2306
2307
2308     #ifdef CV_OPENMP
2309     #pragma omp parallel for
2310     #endif
2311     for( r = start; r < start + num; r++ )
2312     {
2313         int c;
2314
2315         for( c = 0; c < total; c++ )
2316         {
2317             float val, normfactor;
2318             int fnum;
2319
2320             fnum = feature_idx->data.i[c];
2321
2322             val = cvEvalFastHaarFeature( haar_features->fastfeature + fnum,
2323                 (sum_type*) (training_data->sum.data.ptr
2324                         + r * training_data->sum.step),
2325                 (sum_type*) (training_data->tilted.data.ptr
2326                         + r * training_data->tilted.step) );
2327             normfactor = training_data->normfactor.data.fl[r];
2328             val = ( normfactor == 0.0F ) ? 0.0F : (val / normfactor);
2329             CV_MAT_ELEM( *ptr, float, r - start, c ) = val;
2330         }
2331     }
2332
2333     __END__;
2334
2335     cvReleaseMat( &feature_idx );
2336
2337     return ptr;
2338 }
2339
2340 /* possible split in the tree */
2341 typedef struct CvSplit
2342 {
2343     CvTreeCascadeNode* parent;
2344     CvTreeCascadeNode* single_cluster;
2345     CvTreeCascadeNode* multiple_clusters;
2346     int num_clusters;
2347     float single_multiple_ratio;
2348
2349     struct CvSplit* next;
2350 } CvSplit;
2351
2352
2353 void cvCreateTreeCascadeClassifier( const char* dirname,
2354                                     const char* vecfilename,
2355                                     const char* bgfilename,
2356                                     int npos, int nneg, int nstages,
2357                                     int numprecalculated,
2358                                     int numsplits,
2359                                     float minhitrate, float maxfalsealarm,
2360                                     float weightfraction,
2361                                     int mode, int symmetric,
2362                                     int equalweights,
2363                                     int winwidth, int winheight,
2364                                     int boosttype, int stumperror,
2365                                     int maxtreesplits, int minpos, bool bg_vecfile )
2366 {
2367     CvTreeCascadeClassifier* tcc = NULL;
2368     CvIntHaarFeatures* haar_features = NULL;
2369     CvHaarTrainingData* training_data = NULL;
2370     CvMat* vals = NULL;
2371     CvMat* cluster_idx = NULL;
2372     CvMat* idx = NULL;
2373     CvMat* features_idx = NULL;
2374
2375     CV_FUNCNAME( "cvCreateTreeCascadeClassifier" );
2376
2377     __BEGIN__;
2378
2379     int i, k;
2380     CvTreeCascadeNode* leaves;
2381     int best_num, cur_num;
2382     CvSize winsize;
2383     char stage_name[PATH_MAX];
2384     char buf[PATH_MAX];
2385     char* suffix;
2386     int total_splits;
2387
2388     int poscount;
2389     int negcount;
2390     int consumed;
2391     double false_alarm;
2392     double proctime;
2393
2394     int nleaves;
2395     double required_leaf_fa_rate;
2396     float neg_ratio;
2397
2398     int max_clusters;
2399
2400     max_clusters = CV_MAX_CLUSTERS;
2401     neg_ratio = (float) nneg / npos;
2402
2403     nleaves = 1 + MAX( 0, maxtreesplits );
2404     required_leaf_fa_rate = pow( (double) maxfalsealarm, (double) nstages ) / nleaves;
2405
2406     printf( "Required leaf false alarm rate: %g\n", required_leaf_fa_rate );
2407
2408     total_splits = 0;
2409
2410     winsize = cvSize( winwidth, winheight );
2411
2412     CV_CALL( cluster_idx = cvCreateMat( 1, npos + nneg, CV_32SC1 ) );
2413     CV_CALL( idx = cvCreateMat( 1, npos + nneg, CV_32SC1 ) );
2414
2415     CV_CALL( tcc = (CvTreeCascadeClassifier*)
2416         icvLoadTreeCascadeClassifier( dirname, winwidth + 1, &total_splits ) );
2417     CV_CALL( leaves = icvFindDeepestLeaves( tcc ) );
2418
2419     CV_CALL( icvPrintTreeCascade( tcc->root ) );
2420
2421     haar_features = icvCreateIntHaarFeatures( winsize, mode, symmetric );
2422
2423     printf( "Number of features used : %d\n", haar_features->count );
2424
2425     training_data = icvCreateHaarTrainingData( winsize, npos + nneg );
2426
2427     sprintf( stage_name, "%s/", dirname );
2428     suffix = stage_name + strlen( stage_name );
2429
2430     if (! bg_vecfile)
2431       if( !icvInitBackgroundReaders( bgfilename, winsize ) && nstages > 0 )
2432           CV_ERROR( CV_StsError, "Unable to read negative images" );
2433
2434     if( nstages > 0 )
2435     {
2436         /* width-first search in the tree */
2437         do
2438         {
2439             CvSplit* first_split;
2440             CvSplit* last_split;
2441             CvSplit* cur_split;
2442
2443             CvTreeCascadeNode* parent;
2444             CvTreeCascadeNode* cur_node;
2445             CvTreeCascadeNode* last_node;
2446
2447             first_split = last_split = cur_split = NULL;
2448             parent = leaves;
2449             leaves = NULL;
2450             do
2451             {
2452                 int best_clusters; /* best selected number of clusters */
2453                 float posweight, negweight;
2454                 double leaf_fa_rate;
2455
2456                 if( parent ) sprintf( buf, "%d", parent->idx );
2457                 else sprintf( buf, "NULL" );
2458                 printf( "\nParent node: %s\n\n", buf );
2459
2460                 printf( "*** 1 cluster ***\n" );
2461
2462                 tcc->eval = icvEvalTreeCascadeClassifierFilter;
2463                 /* find path from the root to the node <parent> */
2464                 icvSetLeafNode( tcc, parent );
2465
2466                 /* load samples */
2467                 consumed = 0;
2468                 poscount = icvGetHaarTrainingDataFromVec( training_data, 0, npos,
2469                     (CvIntHaarClassifier*) tcc, vecfilename, &consumed );
2470
2471                 printf( "POS: %d %d %f\n", poscount, consumed, ((double) poscount)/consumed );
2472
2473                 if( poscount <= 0 )
2474                     CV_ERROR( CV_StsError, "Unable to obtain positive samples" );
2475
2476                 fflush( stdout );
2477
2478                 proctime = -TIME( 0 );
2479
2480                 nneg = (int) (neg_ratio * poscount);
2481                 negcount = icvGetHaarTrainingDataFromBG( training_data, poscount, nneg,
2482                     (CvIntHaarClassifier*) tcc, &false_alarm, bg_vecfile ? bgfilename : NULL );
2483                 printf( "NEG: %d %g\n", negcount, false_alarm );
2484
2485                 printf( "BACKGROUND PROCESSING TIME: %.2f\n", (proctime + TIME( 0 )) );
2486
2487                 if( negcount <= 0 )
2488                     CV_ERROR( CV_StsError, "Unable to obtain negative samples" );
2489
2490                 leaf_fa_rate = false_alarm;
2491                 if( leaf_fa_rate <= required_leaf_fa_rate )
2492                 {
2493                     printf( "Required leaf false alarm rate achieved. "
2494                             "Branch training terminated.\n" );
2495                 }
2496                 else if( nleaves == 1 && tcc->next_idx == nstages )
2497                 {
2498                     printf( "Required number of stages achieved. "
2499                             "Branch training terminated.\n" );
2500                 }
2501                 else
2502                 {
2503                     CvTreeCascadeNode* single_cluster;
2504                     CvTreeCascadeNode* multiple_clusters;
2505                     int single_num;
2506
2507                     icvSetNumSamples( training_data, poscount + negcount );
2508                     posweight = (equalweights) ? 1.0F / (poscount + negcount) : (0.5F/poscount);
2509                     negweight = (equalweights) ? 1.0F / (poscount + negcount) : (0.5F/negcount);
2510                     icvSetWeightsAndClasses( training_data,
2511                         poscount, posweight, 1.0F, negcount, negweight, 0.0F );
2512
2513                     fflush( stdout );
2514
2515                     /* precalculate feature values */
2516                     proctime = -TIME( 0 );
2517                     icvPrecalculate( training_data, haar_features, numprecalculated );
2518                     printf( "Precalculation time: %.2f\n", (proctime + TIME( 0 )) );
2519
2520                     /* train stage classifier using all positive samples */
2521                     CV_CALL( single_cluster = icvCreateTreeCascadeNode() );
2522                     fflush( stdout );
2523
2524                     proctime = -TIME( 0 );
2525                     single_cluster->stage =
2526                         (CvStageHaarClassifier*) icvCreateCARTStageClassifier(
2527                             training_data, NULL, haar_features,
2528                             minhitrate, maxfalsealarm, symmetric,
2529                             weightfraction, numsplits, (CvBoostType) boosttype,
2530                             (CvStumpError) stumperror, 0 );
2531                     printf( "Stage training time: %.2f\n", (proctime + TIME( 0 )) );
2532
2533                     single_num = icvNumSplits( single_cluster->stage );
2534                     best_num = single_num;
2535                     best_clusters = 1;
2536                     multiple_clusters = NULL;
2537
2538                     printf( "Number of used features: %d\n", single_num );
2539
2540                     if( maxtreesplits >= 0 )
2541                     {
2542                         max_clusters = MIN( max_clusters, maxtreesplits - total_splits + 1 );
2543                     }
2544
2545                     /* try clustering */
2546                     vals = NULL;
2547                     for( k = 2; k <= max_clusters; k++ )
2548                     {
2549                         int cluster;
2550                         int stop_clustering;
2551
2552                         printf( "*** %d clusters ***\n", k );
2553
2554                         /* check whether clusters are big enough */
2555                         stop_clustering = ( k * minpos > poscount );
2556                         if( !stop_clustering )
2557                         {
2558                             int num[CV_MAX_CLUSTERS];
2559
2560                             if( k == 2 )
2561                             {
2562                                 proctime = -TIME( 0 );
2563                                 CV_CALL( vals = icvGetUsedValues( training_data, 0, poscount,
2564                                     haar_features, single_cluster->stage ) );
2565                                 printf( "Getting values for clustering time: %.2f\n", (proctime + TIME(0)) );
2566                                 printf( "Value matirx size: %d x %d\n", vals->rows, vals->cols );
2567                                 fflush( stdout );
2568
2569                                 cluster_idx->cols = vals->rows;
2570                                 for( i = 0; i < negcount; i++ ) idx->data.i[i] = poscount + i;
2571                             }
2572
2573                             proctime = -TIME( 0 );
2574
2575                             CV_CALL( cvKMeans2( vals, k, cluster_idx, CV_TERM_CRITERIA() ) );
2576
2577                             printf( "Clustering time: %.2f\n", (proctime + TIME( 0 )) );
2578
2579                             for( cluster = 0; cluster < k; cluster++ ) num[cluster] = 0;
2580                             for( i = 0; i < cluster_idx->cols; i++ )
2581                                 num[cluster_idx->data.i[i]]++;
2582                             for( cluster = 0; cluster < k; cluster++ )
2583                             {
2584                                 if( num[cluster] < minpos )
2585                                 {
2586                                     stop_clustering = 1;
2587                                     break;
2588                                 }
2589                             }
2590                         }
2591
2592                         if( stop_clustering )
2593                         {
2594                             printf( "Clusters are too small. Clustering aborted.\n" );
2595                             break;
2596                         }
2597
2598                         cur_num = 0;
2599                         cur_node = last_node = NULL;
2600                         for( cluster = 0; (cluster < k) && (cur_num < best_num); cluster++ )
2601                         {
2602                             CvTreeCascadeNode* new_node;
2603
2604                             int num_splits;
2605                             int last_pos;
2606                             int total_pos;
2607
2608                             printf( "Cluster: %d\n", cluster );
2609
2610                             last_pos = negcount;
2611                             for( i = 0; i < cluster_idx->cols; i++ )
2612                             {
2613                                 if( cluster_idx->data.i[i] == cluster )
2614                                 {
2615                                     idx->data.i[last_pos++] = i;
2616                                 }
2617                             }
2618                             idx->cols = last_pos;
2619
2620                             total_pos = idx->cols - negcount;
2621                             printf( "# pos: %d of %d. (%d%%)\n", total_pos, poscount,
2622                                 100 * total_pos / poscount );
2623
2624                             CV_CALL( new_node = icvCreateTreeCascadeNode() );
2625                             if( last_node ) last_node->next = new_node;
2626                             else cur_node = new_node;
2627                             last_node = new_node;
2628
2629                             posweight = (equalweights)
2630                                 ? 1.0F / (total_pos + negcount) : (0.5F / total_pos);
2631                             negweight = (equalweights)
2632                                 ? 1.0F / (total_pos + negcount) : (0.5F / negcount);
2633
2634                             icvSetWeightsAndClasses( training_data,
2635                                 poscount, posweight, 1.0F, negcount, negweight, 0.0F );
2636
2637                             /* CV_DEBUG_SAVE( idx ); */
2638
2639                             fflush( stdout );
2640
2641                             proctime = -TIME( 0 );
2642                             new_node->stage = (CvStageHaarClassifier*)
2643                                 icvCreateCARTStageClassifier( training_data, idx, haar_features,
2644                                     minhitrate, maxfalsealarm, symmetric,
2645                                     weightfraction, numsplits, (CvBoostType) boosttype,
2646                                     (CvStumpError) stumperror, best_num - cur_num );
2647                             printf( "Stage training time: %.2f\n", (proctime + TIME( 0 )) );
2648
2649                             if( !(new_node->stage) )
2650                             {
2651                                 printf( "Stage training aborted.\n" );
2652                                 cur_num = best_num + 1;
2653                             }
2654                             else
2655                             {
2656                                 num_splits = icvNumSplits( new_node->stage );
2657                                 cur_num += num_splits;
2658
2659                                 printf( "Number of used features: %d\n", num_splits );
2660                             }
2661                         } /* for each cluster */
2662
2663                         if( cur_num < best_num )
2664                         {
2665                             icvReleaseTreeCascadeNodes( &multiple_clusters );
2666                             best_num = cur_num;
2667                             best_clusters = k;
2668                             multiple_clusters = cur_node;
2669                         }
2670                         else
2671                         {
2672                             icvReleaseTreeCascadeNodes( &cur_node );
2673                         }
2674                     } /* try different number of clusters */
2675                     cvReleaseMat( &vals );
2676
2677                     CvSplit* curSplit;
2678                     CV_CALL( curSplit = (CvSplit*) cvAlloc( sizeof( *curSplit ) ) );
2679                     memset(curSplit, 0, sizeof(*curSplit));
2680
2681                     if( last_split ) last_split->next = curSplit;
2682                     else first_split = curSplit;
2683                     last_split = curSplit;
2684
2685                     curSplit->single_cluster = single_cluster;
2686                     curSplit->multiple_clusters = multiple_clusters;
2687                     curSplit->num_clusters = best_clusters;
2688                     curSplit->parent = parent;
2689                     curSplit->single_multiple_ratio = (float) single_num / best_num;
2690                 }
2691
2692                 if( parent ) parent = parent->next_same_level;
2693             } while( parent );
2694
2695             /* choose which nodes should be splitted */
2696             do
2697             {
2698                 float max_single_multiple_ratio;
2699
2700                 cur_split = NULL;
2701                 max_single_multiple_ratio = 0.0F;
2702                 last_split = first_split;
2703                 while( last_split )
2704                 {
2705                     if( last_split->single_cluster && last_split->multiple_clusters &&
2706                         last_split->single_multiple_ratio > max_single_multiple_ratio )
2707                     {
2708                         max_single_multiple_ratio = last_split->single_multiple_ratio;
2709                         cur_split = last_split;
2710                     }
2711                     last_split = last_split->next;
2712                 }
2713                 if( cur_split )
2714                 {
2715                     if( maxtreesplits < 0 ||
2716                         cur_split->num_clusters <= maxtreesplits - total_splits + 1 )
2717                     {
2718                         cur_split->single_cluster = NULL;
2719                         total_splits += cur_split->num_clusters - 1;
2720                     }
2721                     else
2722                     {
2723                         icvReleaseTreeCascadeNodes( &(cur_split->multiple_clusters) );
2724                         cur_split->multiple_clusters = NULL;
2725                     }
2726                 }
2727             } while( cur_split );
2728
2729             /* attach new nodes to the tree */
2730             leaves = last_node = NULL;
2731             last_split = first_split;
2732             while( last_split )
2733             {
2734                 cur_node = (last_split->multiple_clusters)
2735                     ? last_split->multiple_clusters : last_split->single_cluster;
2736                 parent = last_split->parent;
2737                 if( parent ) parent->child = cur_node;
2738
2739                 /* connect leaves via next_same_level and save them */
2740                 for( ; cur_node; cur_node = cur_node->next )
2741                 {
2742                     FILE* file;
2743
2744                     if( last_node ) last_node->next_same_level = cur_node;
2745                     else leaves = cur_node;
2746                     last_node = cur_node;
2747                     cur_node->parent = parent;
2748
2749                     cur_node->idx = tcc->next_idx;
2750                     tcc->next_idx++;
2751                     sprintf( suffix, "%d/%s", cur_node->idx, CV_STAGE_CART_FILE_NAME );
2752                     file = NULL;
2753                     if( icvMkDir( stage_name ) && (file = fopen( stage_name, "w" )) != 0 )
2754                     {
2755                         cur_node->stage->save( (CvIntHaarClassifier*) cur_node->stage, file );
2756                         fprintf( file, "\n%d\n%d\n",
2757                             ((parent) ? parent->idx : -1),
2758                             ((cur_node->next) ? tcc->next_idx : -1) );
2759                     }
2760                     else
2761                     {
2762                         printf( "Failed to save classifier into %s\n", stage_name );
2763                     }
2764                     if( file ) fclose( file );
2765                 }
2766
2767                 if( parent ) sprintf( buf, "%d", parent->idx );
2768                 else sprintf( buf, "NULL" );
2769                 printf( "\nParent node: %s\n", buf );
2770                 printf( "Chosen number of splits: %d\n\n", (last_split->multiple_clusters)
2771                     ? (last_split->num_clusters - 1) : 0 );
2772
2773                 cur_split = last_split;
2774                 last_split = last_split->next;
2775                 cvFree( &cur_split );
2776             } /* for each split point */
2777
2778             printf( "Total number of splits: %d\n", total_splits );
2779
2780             if( !(tcc->root) ) tcc->root = leaves;
2781             CV_CALL( icvPrintTreeCascade( tcc->root ) );
2782
2783         } while( leaves );
2784
2785         /* save the cascade to xml file */
2786         {
2787             char xml_path[1024];
2788             int len = (int)strlen(dirname);
2789             CvHaarClassifierCascade* cascade = 0;
2790             strcpy( xml_path, dirname );
2791             if( xml_path[len-1] == '\\' || xml_path[len-1] == '/' )
2792                 len--;
2793             strcpy( xml_path + len, ".xml" );
2794             cascade = cvLoadHaarClassifierCascade( dirname, cvSize(winwidth,winheight) );
2795             if( cascade )
2796                 cvSave( xml_path, cascade );
2797             cvReleaseHaarClassifierCascade( &cascade );
2798         }
2799
2800     } /* if( nstages > 0 ) */
2801
2802     /* check cascade performance */
2803     printf( "\nCascade performance\n" );
2804
2805     tcc->eval = icvEvalTreeCascadeClassifier;
2806
2807     /* load samples */
2808     consumed = 0;
2809     poscount = icvGetHaarTrainingDataFromVec( training_data, 0, npos,
2810         (CvIntHaarClassifier*) tcc, vecfilename, &consumed );
2811
2812     printf( "POS: %d %d %f\n", poscount, consumed,
2813         (consumed > 0) ? (((float) poscount)/consumed) : 0 );
2814
2815     if( poscount <= 0 )
2816         fprintf( stderr, "Warning: unable to obtain positive samples\n" );
2817
2818     proctime = -TIME( 0 );
2819
2820     negcount = icvGetHaarTrainingDataFromBG( training_data, poscount, nneg,
2821         (CvIntHaarClassifier*) tcc, &false_alarm, bg_vecfile ? bgfilename : NULL );
2822
2823     printf( "NEG: %d %g\n", negcount, false_alarm );
2824
2825     printf( "BACKGROUND PROCESSING TIME: %.2f\n", (proctime + TIME( 0 )) );
2826
2827     if( negcount <= 0 )
2828         fprintf( stderr, "Warning: unable to obtain negative samples\n" );
2829
2830     __END__;
2831
2832     if (! bg_vecfile)
2833       icvDestroyBackgroundReaders();
2834
2835     if( tcc ) tcc->release( (CvIntHaarClassifier**) &tcc );
2836     icvReleaseIntHaarFeatures( &haar_features );
2837     icvReleaseHaarTrainingData( &training_data );
2838     cvReleaseMat( &cluster_idx );
2839     cvReleaseMat( &idx );
2840     cvReleaseMat( &vals );
2841     cvReleaseMat( &features_idx );
2842 }
2843
2844
2845
2846 void cvCreateTrainingSamples( const char* filename,
2847                               const char* imgfilename, int bgcolor, int bgthreshold,
2848                               const char* bgfilename, int count,
2849                               int invert, int maxintensitydev,
2850                               double maxxangle, double maxyangle, double maxzangle,
2851                               int showsamples,
2852                               int winwidth, int winheight )
2853 {
2854     CvSampleDistortionData data;
2855
2856     assert( filename != NULL );
2857     assert( imgfilename != NULL );
2858
2859     if( !icvMkDir( filename ) )
2860     {
2861         fprintf( stderr, "Unable to create output file: %s\n", filename );
2862         return;
2863     }
2864     if( icvStartSampleDistortion( imgfilename, bgcolor, bgthreshold, &data ) )
2865     {
2866         FILE* output = NULL;
2867
2868         output = fopen( filename, "wb" );
2869         if( output != NULL )
2870         {
2871             int hasbg;
2872             int i;
2873             CvMat sample;
2874             int inverse;
2875
2876             hasbg = 0;
2877             hasbg = (bgfilename != NULL && icvInitBackgroundReaders( bgfilename,
2878                      cvSize( winwidth,winheight ) ) );
2879
2880             sample = cvMat( winheight, winwidth, CV_8UC1, cvAlloc( sizeof( uchar ) *
2881                             winheight * winwidth ) );
2882
2883             icvWriteVecHeader( output, count, sample.cols, sample.rows );
2884
2885             if( showsamples )
2886             {
2887                 cvNamedWindow( "Sample", CV_WINDOW_AUTOSIZE );
2888             }
2889
2890             inverse = invert;
2891             for( i = 0; i < count; i++ )
2892             {
2893                 if( hasbg )
2894                 {
2895                     icvGetBackgroundImage( cvbgdata, cvbgreader, &sample );
2896                 }
2897                 else
2898                 {
2899                     cvSet( &sample, cvScalar( bgcolor ) );
2900                 }
2901
2902                 if( invert == CV_RANDOM_INVERT )
2903                 {
2904                     inverse = (rand() > (RAND_MAX/2));
2905                 }
2906                 icvPlaceDistortedSample( &sample, inverse, maxintensitydev,
2907                     maxxangle, maxyangle, maxzangle,
2908                     0   /* nonzero means placing image without cut offs */,
2909                     0.0 /* nozero adds random shifting                  */,
2910                     0.0 /* nozero adds random scaling                   */,
2911                     &data );
2912
2913                 if( showsamples )
2914                 {
2915                     cvShowImage( "Sample", &sample );
2916                     if( cvWaitKey( 0 ) == 27 )
2917                     {
2918                         showsamples = 0;
2919                     }
2920                 }
2921
2922                 icvWriteVecSample( output, &sample );
2923
2924 #ifdef CV_VERBOSE
2925                 if( i % 500 == 0 )
2926                 {
2927                     printf( "\r%3d%%", 100 * i / count );
2928                 }
2929 #endif /* CV_VERBOSE */
2930             }
2931             icvDestroyBackgroundReaders();
2932             cvFree( &(sample.data.ptr) );
2933             fclose( output );
2934         } /* if( output != NULL ) */
2935
2936         icvEndSampleDistortion( &data );
2937     }
2938
2939 #ifdef CV_VERBOSE
2940     printf( "\r      \r" );
2941 #endif /* CV_VERBOSE */
2942
2943 }
2944
2945 #define CV_INFO_FILENAME "info.dat"
2946
2947
2948 void cvCreateTestSamples( const char* infoname,
2949                           const char* imgfilename, int bgcolor, int bgthreshold,
2950                           const char* bgfilename, int count,
2951                           int invert, int maxintensitydev,
2952                           double maxxangle, double maxyangle, double maxzangle,
2953                           int showsamples,
2954                           int winwidth, int winheight )
2955 {
2956     CvSampleDistortionData data;
2957
2958     assert( infoname != NULL );
2959     assert( imgfilename != NULL );
2960     assert( bgfilename != NULL );
2961
2962     if( !icvMkDir( infoname ) )
2963     {
2964
2965 #if CV_VERBOSE
2966         fprintf( stderr, "Unable to create directory hierarchy: %s\n", infoname );
2967 #endif /* CV_VERBOSE */
2968
2969         return;
2970     }
2971     if( icvStartSampleDistortion( imgfilename, bgcolor, bgthreshold, &data ) )
2972     {
2973         char fullname[PATH_MAX];
2974         char* filename;
2975         CvMat win;
2976         FILE* info;
2977
2978         if( icvInitBackgroundReaders( bgfilename, cvSize( 10, 10 ) ) )
2979         {
2980             int i;
2981             int x, y, width, height;
2982             float scale;
2983             float maxscale;
2984             int inverse;
2985
2986             if( showsamples )
2987             {
2988                 cvNamedWindow( "Image", CV_WINDOW_AUTOSIZE );
2989             }
2990
2991             info = fopen( infoname, "w" );
2992             strcpy( fullname, infoname );
2993             filename = strrchr( fullname, '\\' );
2994             if( filename == NULL )
2995             {
2996                 filename = strrchr( fullname, '/' );
2997             }
2998             if( filename == NULL )
2999             {
3000                 filename = fullname;
3001             }
3002             else
3003             {
3004                 filename++;
3005             }
3006
3007             count = MIN( count, cvbgdata->count );
3008             inverse = invert;
3009             for( i = 0; i < count; i++ )
3010             {
3011                 icvGetNextFromBackgroundData( cvbgdata, cvbgreader );
3012
3013                 maxscale = MIN( 0.7F * cvbgreader->src.cols / winwidth,
3014                                    0.7F * cvbgreader->src.rows / winheight );
3015                 if( maxscale < 1.0F ) continue;
3016
3017                 scale = (maxscale - 1.0F) * rand() / RAND_MAX + 1.0F;
3018                 width = (int) (scale * winwidth);
3019                 height = (int) (scale * winheight);
3020                 x = (int) ((0.1+0.8 * rand()/RAND_MAX) * (cvbgreader->src.cols - width));
3021                 y = (int) ((0.1+0.8 * rand()/RAND_MAX) * (cvbgreader->src.rows - height));
3022
3023                 cvGetSubArr( &cvbgreader->src, &win, cvRect( x, y ,width, height ) );
3024                 if( invert == CV_RANDOM_INVERT )
3025                 {
3026                     inverse = (rand() > (RAND_MAX/2));
3027                 }
3028                 icvPlaceDistortedSample( &win, inverse, maxintensitydev,
3029                                          maxxangle, maxyangle, maxzangle,
3030                                          1, 0.0, 0.0, &data );
3031
3032
3033                 sprintf( filename, "%04d_%04d_%04d_%04d_%04d.jpg",
3034                          (i + 1), x, y, width, height );
3035
3036                 if( info )
3037                 {
3038                     fprintf( info, "%s %d %d %d %d %d\n",
3039                         filename, 1, x, y, width, height );
3040                 }
3041
3042                 cvSaveImage( fullname, &cvbgreader->src );
3043                 if( showsamples )
3044                 {
3045                     cvShowImage( "Image", &cvbgreader->src );
3046                     if( cvWaitKey( 0 ) == 27 )
3047                     {
3048                         showsamples = 0;
3049                     }
3050                 }
3051             }
3052             if( info ) fclose( info );
3053             icvDestroyBackgroundReaders();
3054         }
3055         icvEndSampleDistortion( &data );
3056     }
3057 }
3058
3059
3060 /* End of file. */