opencv/src/cv/cvcascadedetect.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 #include "_cv.h"
  43 #include <cstdio>
  44
  45 #ifdef _OPENMP
  46 #include "omp.h"
  47 #endif
  48
  49 namespace cv
  50 {
  51
  52 // class for grouping object candidates, detected by Cascade Classifier, HOG etc.
  53 // instance of the class is to be passed to cv::partition (see cxoperations.hpp)
  54 class CV_EXPORTS SimilarRects
  55 {
  56 public:
  57     SimilarRects(double _eps) : eps(_eps) {}
  58     inline bool operator()(const Rect& r1, const Rect& r2) const
  59     {
  60         double delta = eps*(std::min(r1.width, r2.width) + std::min(r1.height, r2.height))*0.5;
  61         return std::abs(r1.x - r2.x) <= delta &&
  62         std::abs(r1.y - r2.y) <= delta &&
  63         std::abs(r1.x + r1.width - r2.x - r2.width) <= delta &&
  64         std::abs(r1.y + r1.height - r2.y - r2.height) <= delta;
  65     }
  66     double eps;
  67 };
  68
  69 void groupRectangles(vector<Rect>& rectList, int groupThreshold, double eps)
  70 {
  71     if( groupThreshold <= 0 || rectList.empty() )
  72         return;
  73
  74     vector<int> labels;
  75     int nclasses = partition(rectList, labels, SimilarRects(eps));
  76     vector<Rect> rrects(nclasses);
  77     vector<int> rweights(nclasses, 0);
  78     int i, nlabels = (int)labels.size();
  79     for( i = 0; i < nlabels; i++ )
  80     {
  81         int cls = labels[i];
  82         rrects[cls].x += rectList[i].x;
  83         rrects[cls].y += rectList[i].y;
  84         rrects[cls].width += rectList[i].width;
  85         rrects[cls].height += rectList[i].height;
  86         rweights[cls]++;
  87     }
  88     rectList.clear();
  89     for( i = 0; i < nclasses; i++ )
  90     {
  91         Rect r = rrects[i];
  92         if( rweights[i] <= groupThreshold )
  93             continue;
  94         float s = 1.f/rweights[i];
  95         rectList.push_back(Rect(saturate_cast<int>(r.x*s),
  96                                 saturate_cast<int>(r.y*s),
  97                                 saturate_cast<int>(r.width*s),
  98                                 saturate_cast<int>(r.height*s)));
  99     }
 100 }
 101
 102 #define CC_CASCADE_PARAMS "cascadeParams"
 103 #define CC_STAGE_TYPE     "stageType"
 104 #define CC_FEATURE_TYPE   "featureType"
 105 #define CC_HEIGHT         "height"
 106 #define CC_WIDTH          "width"
 107
 108 #define CC_STAGE_NUM    "stageNum"
 109 #define CC_STAGES       "stages"
 110 #define CC_STAGE_PARAMS "stageParams"
 111
 112 #define CC_BOOST            "BOOST"
 113 #define CC_MAX_DEPTH        "maxDepth"
 114 #define CC_WEAK_COUNT       "maxWeakCount"
 115 #define CC_STAGE_THRESHOLD  "stageThreshold"
 116 #define CC_WEAK_CLASSIFIERS "weakClassifiers"
 117 #define CC_INTERNAL_NODES   "internalNodes"
 118 #define CC_LEAF_VALUES      "leafValues"
 119
 120 #define CC_FEATURES       "features"
 121 #define CC_FEATURE_PARAMS "featureParams"
 122 #define CC_MAX_CAT_COUNT  "maxCatCount"
 123
 124 #define CC_HAAR   "HAAR"
 125 #define CC_RECTS  "rects"
 126 #define CC_TILTED "tilted"
 127
 128 #define CC_LBP  "LBP"
 129 #define CC_RECT "rect"
 130
 131 #define CV_SUM_PTRS( p0, p1, p2, p3, sum, rect, step )                    \
 132     /* (x, y) */                                                          \
 133     (p0) = sum + (rect).x + (step) * (rect).y,                            \
 134     /* (x + w, y) */                                                      \
 135     (p1) = sum + (rect).x + (rect).width + (step) * (rect).y,             \
 136     /* (x + w, y) */                                                      \
 137     (p2) = sum + (rect).x + (step) * ((rect).y + (rect).height),          \
 138     /* (x + w, y + h) */                                                  \
 139     (p3) = sum + (rect).x + (rect).width + (step) * ((rect).y + (rect).height)
 140
 141 #define CV_TILTED_PTRS( p0, p1, p2, p3, tilted, rect, step )                        \
 142     /* (x, y) */                                                                    \
 143     (p0) = tilted + (rect).x + (step) * (rect).y,                                   \
 144     /* (x - h, y + h) */                                                            \
 145     (p1) = tilted + (rect).x - (rect).height + (step) * ((rect).y + (rect).height), \
 146     /* (x + w, y + w) */                                                            \
 147     (p2) = tilted + (rect).x + (rect).width + (step) * ((rect).y + (rect).width),   \
 148     /* (x + w - h, y + w + h) */                                                    \
 149     (p3) = tilted + (rect).x + (rect).width - (rect).height                         \
 150            + (step) * ((rect).y + (rect).width + (rect).height)
 151
 152 #define CALC_SUM_(p0, p1, p2, p3, offset) \
 153     ((p0)[offset] - (p1)[offset] - (p2)[offset] + (p3)[offset])
 154
 155 #define CALC_SUM(rect,offset) CALC_SUM_((rect)[0], (rect)[1], (rect)[2], (rect)[3], offset)
 156
 157 FeatureEvaluator::~FeatureEvaluator() {}
 158 bool FeatureEvaluator::read(const FileNode&) {return true;}
 159 Ptr<FeatureEvaluator> FeatureEvaluator::clone() const { return Ptr<FeatureEvaluator>(); }
 160 int FeatureEvaluator::getFeatureType() const {return -1;}
 161 bool FeatureEvaluator::setImage(const Mat&, Size) {return true;}
 162 bool FeatureEvaluator::setWindow(Point) { return true; }
 163 double FeatureEvaluator::calcOrd(int) const { return 0.; }
 164 int FeatureEvaluator::calcCat(int) const { return 0; }
 165
 166 //----------------------------------------------  HaarEvaluator ---------------------------------------
 167 class HaarEvaluator : public FeatureEvaluator
 168 {
 169 public:
 170     struct Feature
 171     {
 172         Feature();
 173
 174         float calc( int offset ) const;
 175         void updatePtrs( const Mat& sum );
 176         bool read( const FileNode& node );
 177
 178         bool tilted;
 179
 180         enum { RECT_NUM = 3 };
 181
 182         struct
 183         {
 184             Rect r;
 185             float weight;
 186         } rect[RECT_NUM];
 187
 188         const int* p[RECT_NUM][4];
 189     };
 190
 191     HaarEvaluator();
 192     virtual ~HaarEvaluator();
 193
 194     virtual bool read( const FileNode& node );
 195     virtual Ptr<FeatureEvaluator> clone() const;
 196     virtual int getFeatureType() const { return FeatureEvaluator::HAAR; }
 197
 198     virtual bool setImage(const Mat&, Size origWinSize);
 199     virtual bool setWindow(Point pt);
 200
 201     double operator()(int featureIdx) const
 202     { return featuresPtr[featureIdx].calc(offset) * varianceNormFactor; }
 203     virtual double calcOrd(int featureIdx) const
 204     { return (*this)(featureIdx); }
 205 private:
 206     Size origWinSize;
 207     Ptr<vector<Feature> > features;
 208     Feature* featuresPtr; // optimization
 209     bool hasTiltedFeatures;
 210
 211     Mat sum0, sqsum0, tilted0;
 212     Mat sum, sqsum, tilted;
 213
 214     Rect normrect;
 215     const int *p[4];
 216     const double *pq[4];
 217
 218     int offset;
 219     double varianceNormFactor;
 220 };
 221
 222 inline HaarEvaluator::Feature :: Feature()
 223 {
 224     tilted = false;
 225     rect[0].r = rect[1].r = rect[2].r = Rect();
 226     rect[0].weight = rect[1].weight = rect[2].weight = 0;
 227     p[0][0] = p[0][1] = p[0][2] = p[0][3] =
 228         p[1][0] = p[1][1] = p[1][2] = p[1][3] =
 229         p[2][0] = p[2][1] = p[2][2] = p[2][3] = 0;
 230 }
 231
 232 inline float HaarEvaluator::Feature :: calc( int offset ) const
 233 {
 234     float ret = rect[0].weight * CALC_SUM(p[0], offset) + rect[1].weight * CALC_SUM(p[1], offset);
 235
 236     if( rect[2].weight != 0.0f )
 237         ret += rect[2].weight * CALC_SUM(p[2], offset);
 238
 239     return ret;
 240 }
 241
 242 inline void HaarEvaluator::Feature :: updatePtrs( const Mat& sum )
 243 {
 244     const int* ptr = (const int*)sum.data;
 245     size_t step = sum.step/sizeof(ptr[0]);
 246     if (tilted)
 247     {
 248         CV_TILTED_PTRS( p[0][0], p[0][1], p[0][2], p[0][3], ptr, rect[0].r, step );
 249         CV_TILTED_PTRS( p[1][0], p[1][1], p[1][2], p[1][3], ptr, rect[1].r, step );
 250         if (rect[2].weight)
 251             CV_TILTED_PTRS( p[2][0], p[2][1], p[2][2], p[2][3], ptr, rect[2].r, step );
 252     }
 253     else
 254     {
 255         CV_SUM_PTRS( p[0][0], p[0][1], p[0][2], p[0][3], ptr, rect[0].r, step );
 256         CV_SUM_PTRS( p[1][0], p[1][1], p[1][2], p[1][3], ptr, rect[1].r, step );
 257         if (rect[2].weight)
 258             CV_SUM_PTRS( p[2][0], p[2][1], p[2][2], p[2][3], ptr, rect[2].r, step );
 259     }
 260 }
 261
 262 bool HaarEvaluator::Feature :: read( const FileNode& node )
 263 {
 264     FileNode rnode = node[CC_RECTS];
 265     FileNodeIterator it = rnode.begin(), it_end = rnode.end();
 266
 267     int ri;
 268     for( ri = 0; ri < RECT_NUM; ri++ )
 269     {
 270         rect[ri].r = Rect();
 271         rect[ri].weight = 0.f;
 272     }
 273
 274     for(ri = 0; it != it_end; ++it, ri++)
 275     {
 276         FileNodeIterator it2 = (*it).begin();
 277         it2 >> rect[ri].r.x >> rect[ri].r.y >>
 278             rect[ri].r.width >> rect[ri].r.height >> rect[ri].weight;
 279     }
 280
 281     tilted = (int)node[CC_TILTED] != 0;
 282     return true;
 283 }
 284
 285 HaarEvaluator::HaarEvaluator()
 286 {
 287     features = new vector<Feature>();
 288 }
 289 HaarEvaluator::~HaarEvaluator()
 290 {
 291 }
 292
 293 bool HaarEvaluator::read(const FileNode& node)
 294 {
 295     features->resize(node.size());
 296     featuresPtr = &(*features)[0];
 297     FileNodeIterator it = node.begin(), it_end = node.end();
 298     hasTiltedFeatures = false;
 299
 300     for(int i = 0; it != it_end; ++it, i++)
 301     {
 302         if(!featuresPtr[i].read(*it))
 303             return false;
 304         if( featuresPtr[i].tilted )
 305             hasTiltedFeatures = true;
 306     }
 307     return true;
 308 }
 309
 310 Ptr<FeatureEvaluator> HaarEvaluator::clone() const
 311 {
 312     HaarEvaluator* ret = new HaarEvaluator;
 313     ret->origWinSize = origWinSize;
 314     ret->features = features;
 315     ret->featuresPtr = &(*ret->features)[0];
 316     ret->hasTiltedFeatures = hasTiltedFeatures;
 317     ret->sum0 = sum0, ret->sqsum0 = sqsum0, ret->tilted0 = tilted0;
 318     ret->sum = sum, ret->sqsum = sqsum, ret->tilted = tilted;
 319     ret->normrect = normrect;
 320     memcpy( ret->p, p, 4*sizeof(p[0]) );
 321     memcpy( ret->pq, pq, 4*sizeof(pq[0]) );
 322     ret->offset = offset;
 323     ret->varianceNormFactor = varianceNormFactor;
 324     return ret;
 325 }
 326
 327 bool HaarEvaluator::setImage( const Mat &image, Size _origWinSize )
 328 {
 329     int rn = image.rows+1, cn = image.cols+1;
 330     origWinSize = _origWinSize;
 331     normrect = Rect(1, 1, origWinSize.width-2, origWinSize.height-2);
 332
 333     if (image.cols < origWinSize.width || image.rows < origWinSize.height)
 334         return false;
 335
 336     if( sum0.rows < rn || sum0.cols < cn )
 337     {
 338         sum0.create(rn, cn, CV_32S);
 339         sqsum0.create(rn, cn, CV_64F);
 340         if (hasTiltedFeatures)
 341             tilted0.create( rn, cn, CV_32S);
 342     }
 343     sum = Mat(rn, cn, CV_32S, sum0.data);
 344     sqsum = Mat(rn, cn, CV_32S, sqsum0.data);
 345
 346     if( hasTiltedFeatures )
 347     {
 348         tilted = Mat(rn, cn, CV_32S, tilted0.data);
 349         integral(image, sum, sqsum, tilted);
 350     }
 351     else
 352         integral(image, sum, sqsum);
 353     const int* sdata = (const int*)sum.data;
 354     const double* sqdata = (const double*)sqsum.data;
 355     size_t sumStep = sum.step/sizeof(sdata[0]);
 356     size_t sqsumStep = sqsum.step/sizeof(sqdata[0]);
 357
 358     CV_SUM_PTRS( p[0], p[1], p[2], p[3], sdata, normrect, sumStep );
 359     CV_SUM_PTRS( pq[0], pq[1], pq[2], pq[3], sqdata, normrect, sqsumStep );
 360
 361     size_t fi, nfeatures = features->size();
 362
 363     for( fi = 0; fi < nfeatures; fi++ )
 364         featuresPtr[fi].updatePtrs( !featuresPtr[fi].tilted ? sum : tilted );
 365     return true;
 366 }
 367
 368 bool  HaarEvaluator::setWindow( Point pt )
 369 {
 370     if( pt.x < 0 || pt.y < 0 ||
 371         pt.x + origWinSize.width >= sum.cols-2 ||
 372         pt.y + origWinSize.height >= sum.rows-2 )
 373         return false;
 374
 375     size_t pOffset = pt.y * (sum.step/sizeof(int)) + pt.x;
 376     size_t pqOffset = pt.y * (sqsum.step/sizeof(double)) + pt.x;
 377     int valsum = CALC_SUM(p, pOffset);
 378     double valsqsum = CALC_SUM(pq, pqOffset);
 379
 380     double nf = (double)normrect.area() * valsqsum - (double)valsum * valsum;
 381     if( nf > 0. )
 382         nf = sqrt(nf);
 383     else
 384         nf = 1.;
 385     varianceNormFactor = 1./nf;
 386     offset = (int)pOffset;
 387     return true;
 388 }
 389
 390 //----------------------------------------------  LBPEvaluator -------------------------------------
 391
 392 class LBPEvaluator : public FeatureEvaluator
 393 {
 394 public:
 395     struct Feature
 396     {
 397         Feature();
 398         Feature( int x, int y, int _block_w, int _block_h  ) :
 399         rect(x, y, _block_w, _block_h) {}
 400
 401         int calc( int offset ) const;
 402         void updatePtrs( const Mat& sum );
 403         bool read(const FileNode& node );
 404
 405         Rect rect; // weight and height for block
 406         const int* p[16]; // fast
 407     };
 408
 409     LBPEvaluator();
 410     virtual ~LBPEvaluator();
 411
 412     virtual bool read( const FileNode& node );
 413     virtual Ptr<FeatureEvaluator> clone() const;
 414     virtual int getFeatureType() const { return FeatureEvaluator::LBP; }
 415
 416     virtual bool setImage(const Mat& image, Size _origWinSize);
 417     virtual bool setWindow(Point pt);
 418
 419     int operator()(int featureIdx) const
 420     { return featuresPtr[featureIdx].calc(offset); }
 421     virtual int calcCat(int featureIdx) const
 422     { return (*this)(featureIdx); }
 423 private:
 424     Size origWinSize;
 425     Ptr<vector<Feature> > features;
 426     Feature* featuresPtr; // optimization
 427     Mat sum0, sum;
 428     Rect normrect;
 429
 430     int offset;
 431 };
 432
 433
 434 inline LBPEvaluator::Feature :: Feature()
 435 {
 436     rect = Rect();
 437     for( int i = 0; i < 16; i++ )
 438         p[i] = 0;
 439 }
 440
 441 inline int LBPEvaluator::Feature :: calc( int offset ) const
 442 {
 443     int cval = CALC_SUM_( p[5], p[6], p[9], p[10], offset );
 444
 445     return (CALC_SUM_( p[0], p[1], p[4], p[5], offset ) >= cval ? 128 : 0) |   // 0
 446            (CALC_SUM_( p[1], p[2], p[5], p[6], offset ) >= cval ? 64 : 0) |    // 1
 447            (CALC_SUM_( p[2], p[3], p[6], p[7], offset ) >= cval ? 32 : 0) |    // 2
 448            (CALC_SUM_( p[6], p[7], p[10], p[11], offset ) >= cval ? 16 : 0) |  // 5
 449            (CALC_SUM_( p[10], p[11], p[14], p[15], offset ) >= cval ? 8 : 0)|  // 8
 450            (CALC_SUM_( p[9], p[10], p[13], p[14], offset ) >= cval ? 4 : 0)|   // 7
 451            (CALC_SUM_( p[8], p[9], p[12], p[13], offset ) >= cval ? 2 : 0)|    // 6
 452            (CALC_SUM_( p[4], p[5], p[8], p[9], offset ) >= cval ? 1 : 0);
 453 }
 454
 455 inline void LBPEvaluator::Feature :: updatePtrs( const Mat& sum )
 456 {
 457     const int* ptr = (const int*)sum.data;
 458     size_t step = sum.step/sizeof(ptr[0]);
 459     Rect tr = rect;
 460     CV_SUM_PTRS( p[0], p[1], p[4], p[5], ptr, tr, step );
 461     tr.x += 2*rect.width;
 462     CV_SUM_PTRS( p[2], p[3], p[6], p[7], ptr, tr, step );
 463     tr.y += 2*rect.height;
 464     CV_SUM_PTRS( p[10], p[11], p[14], p[15], ptr, tr, step );
 465     tr.x -= 2*rect.width;
 466     CV_SUM_PTRS( p[8], p[9], p[12], p[13], ptr, tr, step );
 467 }
 468
 469 bool LBPEvaluator::Feature :: read(const FileNode& node )
 470 {
 471     FileNode rnode = node[CC_RECT];
 472     FileNodeIterator it = rnode.begin();
 473     it >> rect.x >> rect.y >> rect.width >> rect.height;
 474     return true;
 475 }
 476
 477 LBPEvaluator::LBPEvaluator()
 478 {
 479     features = new vector<Feature>();
 480 }
 481 LBPEvaluator::~LBPEvaluator()
 482 {
 483 }
 484
 485 bool LBPEvaluator::read( const FileNode& node )
 486 {
 487     features->resize(node.size());
 488     featuresPtr = &(*features)[0];
 489     FileNodeIterator it = node.begin(), it_end = node.end();
 490     for(int i = 0; it != it_end; ++it, i++)
 491     {
 492         if(!featuresPtr[i].read(*it))
 493             return false;
 494     }
 495     return true;
 496 }
 497
 498 Ptr<FeatureEvaluator> LBPEvaluator::clone() const
 499 {
 500     LBPEvaluator* ret = new LBPEvaluator;
 501     ret->origWinSize = origWinSize;
 502     ret->features = features;
 503     ret->featuresPtr = &(*ret->features)[0];
 504     ret->sum0 = sum0, ret->sum = sum;
 505     ret->normrect = normrect;
 506     ret->offset = offset;
 507     return ret;
 508 }
 509
 510 bool LBPEvaluator::setImage( const Mat& image, Size _origWinSize )
 511 {
 512     int rn = image.rows+1, cn = image.cols+1;
 513     origWinSize = _origWinSize;
 514
 515     if( image.cols < origWinSize.width || image.rows < origWinSize.height )
 516         return false;
 517
 518     if( sum0.rows < rn || sum0.cols < cn )
 519         sum0.create(rn, cn, CV_32S);
 520     sum = Mat(rn, cn, CV_32S, sum0.data);
 521     integral(image, sum);
 522
 523     size_t fi, nfeatures = features->size();
 524
 525     for( fi = 0; fi < nfeatures; fi++ )
 526         featuresPtr[fi].updatePtrs( sum );
 527     return true;
 528 }
 529
 530 bool LBPEvaluator::setWindow( Point pt )
 531 {
 532     if( pt.x < 0 || pt.y < 0 ||
 533         pt.x + origWinSize.width >= sum.cols-2 ||
 534         pt.y + origWinSize.height >= sum.rows-2 )
 535         return false;
 536     offset = pt.y * ((int)sum.step/sizeof(int)) + pt.x;
 537     return true;
 538 }
 539
 540 Ptr<FeatureEvaluator> FeatureEvaluator::create(int featureType)
 541 {
 542     return featureType == HAAR ? Ptr<FeatureEvaluator>(new HaarEvaluator) :
 543         featureType == LBP ? Ptr<FeatureEvaluator>(new LBPEvaluator) : Ptr<FeatureEvaluator>();
 544 }
 545
 546 //---------------------------------------- Classifier Cascade --------------------------------------------
 547
 548 CascadeClassifier::CascadeClassifier()
 549 {
 550 }
 551
 552 CascadeClassifier::CascadeClassifier(const string& filename)
 553 { load(filename); }
 554
 555 CascadeClassifier::~CascadeClassifier()
 556 {
 557 }
 558
 559 bool CascadeClassifier::empty() const
 560 {
 561     return oldCascade.empty() && stages.empty();
 562 }
 563
 564 bool CascadeClassifier::load(const string& filename)
 565 {
 566     oldCascade.release();
 567
 568     FileStorage fs(filename, FileStorage::READ);
 569     if( !fs.isOpened() )
 570         return false;
 571
 572     if( read(fs.getFirstTopLevelNode()) )
 573         return true;
 574
 575     fs.release();
 576
 577     oldCascade = Ptr<CvHaarClassifierCascade>((CvHaarClassifierCascade*)cvLoad(filename.c_str(), 0, 0, 0));
 578     return !oldCascade.empty();
 579 }
 580
 581 template<class FEval>
 582 inline int predictOrdered( CascadeClassifier& cascade, Ptr<FeatureEvaluator> &_feval )
 583 {
 584     int si, nstages = (int)cascade.stages.size();
 585     int nodeOfs = 0, leafOfs = 0;
 586     FEval& feval = (FEval&)*_feval;
 587     float* cascadeLeaves = &cascade.leaves[0];
 588     CascadeClassifier::DTreeNode* cascadeNodes = &cascade.nodes[0];
 589     CascadeClassifier::DTree* cascadeWeaks = &cascade.classifiers[0];
 590     CascadeClassifier::Stage* cascadeStages = &cascade.stages[0];
 591
 592     for( si = 0; si < nstages; si++ )
 593     {
 594         CascadeClassifier::Stage& stage = cascadeStages[si];
 595         int wi, ntrees = stage.ntrees;
 596         double sum = 0;
 597
 598         for( wi = 0; wi < ntrees; wi++ )
 599         {
 600             CascadeClassifier::DTree& weak = cascadeWeaks[stage.first + wi];
 601             int idx = 0, root = nodeOfs;
 602
 603             do
 604             {
 605                 CascadeClassifier::DTreeNode& node = cascadeNodes[root + idx];
 606                 double val = feval(node.featureIdx);
 607                 idx = val < node.threshold ? node.left : node.right;
 608             }
 609             while( idx > 0 );
 610             sum += cascadeLeaves[leafOfs - idx];
 611             nodeOfs += weak.nodeCount;
 612             leafOfs += weak.nodeCount + 1;
 613         }
 614         if( sum < stage.threshold )
 615             return -si;
 616     }
 617     return 1;
 618 }
 619
 620 template<class FEval>
 621 inline int predictCategorical( CascadeClassifier& cascade, Ptr<FeatureEvaluator> &_feval )
 622 {
 623     int si, nstages = (int)cascade.stages.size();
 624     int nodeOfs = 0, leafOfs = 0;
 625     FEval& feval = (FEval&)*_feval;
 626     size_t subsetSize = (cascade.ncategories + 31)/32;
 627     int* cascadeSubsets = &cascade.subsets[0];
 628     float* cascadeLeaves = &cascade.leaves[0];
 629     CascadeClassifier::DTreeNode* cascadeNodes = &cascade.nodes[0];
 630     CascadeClassifier::DTree* cascadeWeaks = &cascade.classifiers[0];
 631     CascadeClassifier::Stage* cascadeStages = &cascade.stages[0];
 632
 633     for( si = 0; si < nstages; si++ )
 634     {
 635         CascadeClassifier::Stage& stage = cascadeStages[si];
 636         int wi, ntrees = stage.ntrees;
 637         double sum = 0;
 638
 639         for( wi = 0; wi < ntrees; wi++ )
 640         {
 641             CascadeClassifier::DTree& weak = cascadeWeaks[stage.first + wi];
 642             int idx = 0, root = nodeOfs;
 643             do
 644             {
 645                 CascadeClassifier::DTreeNode& node = cascadeNodes[root + idx];
 646                 int c = feval(node.featureIdx);
 647                 const int* subset = &cascadeSubsets[(root + idx)*subsetSize];
 648                 idx = (subset[c>>5] & (1 << (c & 31))) ? node.left : node.right;
 649             }
 650             while( idx > 0 );
 651             sum += cascadeLeaves[leafOfs - idx];
 652             nodeOfs += weak.nodeCount;
 653             leafOfs += weak.nodeCount + 1;
 654         }
 655         if( sum < stage.threshold )
 656             return -si;
 657     }
 658     return 1;
 659 }
 660
 661 template<class FEval>
 662 inline int predictOrderedStump( CascadeClassifier& cascade, Ptr<FeatureEvaluator> &_feval )
 663 {
 664     int si, nstages = (int)cascade.stages.size();
 665     int nodeOfs = 0, leafOfs = 0;
 666     FEval& feval = (FEval&)*_feval;
 667     float* cascadeLeaves = &cascade.leaves[0];
 668     CascadeClassifier::DTreeNode* cascadeNodes = &cascade.nodes[0];
 669     CascadeClassifier::Stage* cascadeStages = &cascade.stages[0];
 670     for( si = 0; si < nstages; si++ )
 671     {
 672         CascadeClassifier::Stage& stage = cascadeStages[si];
 673         int wi, ntrees = stage.ntrees;
 674         double sum = 0;
 675         for( wi = 0; wi < ntrees; wi++, nodeOfs++, leafOfs+= 2 )
 676         {
 677             CascadeClassifier::DTreeNode& node = cascadeNodes[nodeOfs];
 678             double val = feval(node.featureIdx);
 679             sum += cascadeLeaves[ val < node.threshold ? leafOfs : leafOfs+1 ];
 680         }
 681         if( sum < stage.threshold )
 682             return -si;
 683     }
 684     return 1;
 685 }
 686
 687 template<class FEval>
 688 inline int predictCategoricalStump( CascadeClassifier& cascade, Ptr<FeatureEvaluator> &_feval )
 689 {
 690     int si, nstages = (int)cascade.stages.size();
 691     int nodeOfs = 0, leafOfs = 0;
 692     FEval& feval = (FEval&)*_feval;
 693     size_t subsetSize = (cascade.ncategories + 31)/32;
 694     int* cascadeSubsets = &cascade.subsets[0];
 695     float* cascadeLeaves = &cascade.leaves[0];
 696     CascadeClassifier::DTreeNode* cascadeNodes = &cascade.nodes[0];
 697     CascadeClassifier::Stage* cascadeStages = &cascade.stages[0];
 698
 699     for( si = 0; si < nstages; si++ )
 700     {
 701         CascadeClassifier::Stage& stage = cascadeStages[si];
 702         int wi, ntrees = stage.ntrees;
 703         double sum = 0;
 704
 705         for( wi = 0; wi < ntrees; wi++ )
 706         {
 707             CascadeClassifier::DTreeNode& node = cascadeNodes[nodeOfs];
 708             int c = feval(node.featureIdx);
 709             const int* subset = &cascadeSubsets[nodeOfs*subsetSize];
 710             sum += cascadeLeaves[ subset[c>>5] & (1 << (c & 31)) ? leafOfs : leafOfs+1];
 711             nodeOfs++;
 712             leafOfs += 2;
 713         }
 714         if( sum < stage.threshold )
 715             return -si;
 716     }
 717     return 1;
 718 }
 719
 720 int CascadeClassifier::runAt( Ptr<FeatureEvaluator> &_feval, Point pt )
 721 {
 722     CV_Assert( oldCascade.empty() );
 723     /*if( !oldCascade.empty() )
 724         return cvRunHaarClassifierCascade(oldCascade, pt, 0);*/
 725
 726     assert(featureType == FeatureEvaluator::HAAR ||
 727            featureType == FeatureEvaluator::LBP);
 728     return !_feval->setWindow(pt) ? -1 :
 729                 is_stump_based ? ( featureType == FeatureEvaluator::HAAR ?
 730                     predictOrderedStump<HaarEvaluator>( *this, _feval ) :
 731                     predictCategoricalStump<LBPEvaluator>( *this, _feval ) ) :
 732                                  ( featureType == FeatureEvaluator::HAAR ?
 733                     predictOrdered<HaarEvaluator>( *this, _feval ) :
 734                     predictCategorical<LBPEvaluator>( *this, _feval ) );
 735 }
 736
 737
 738 bool CascadeClassifier::setImage( Ptr<FeatureEvaluator> &_feval, const Mat& image )
 739 {
 740     /*if( !oldCascade.empty() )
 741     {
 742         Mat sum(image.rows+1, image.cols+1, CV_32S);
 743         Mat tilted(image.rows+1, image.cols+1, CV_32S);
 744         Mat sqsum(image.rows+1, image.cols+1, CV_64F);
 745         integral(image, sum, sqsum, tilted);
 746         CvMat _sum = sum, _sqsum = sqsum, _tilted = tilted;
 747         cvSetImagesForHaarClassifierCascade( oldCascade, &_sum, &_sqsum, &_tilted, 1. );
 748         return true;
 749     }*/
 750     return empty() ? false : _feval->setImage(image, origWinSize );
 751 }
 752
 753
 754 struct getRect { Rect operator ()(const CvAvgComp& e) const { return e.rect; } };
 755
 756 void CascadeClassifier::detectMultiScale( const Mat& image, vector<Rect>& objects,
 757                                           double scaleFactor, int minNeighbors,
 758                                           int flags, Size minSize )
 759 {
 760     CV_Assert( scaleFactor > 1 && image.depth() == CV_8U );
 761
 762     if( empty() )
 763         return;
 764
 765     if( !oldCascade.empty() )
 766     {
 767         MemStorage storage(cvCreateMemStorage(0));
 768         CvMat _image = image;
 769         CvSeq* _objects = cvHaarDetectObjects( &_image, oldCascade, storage, scaleFactor,
 770                                               minNeighbors, flags, minSize );
 771         vector<CvAvgComp> vecAvgComp;
 772         Seq<CvAvgComp>(_objects).copyTo(vecAvgComp);
 773         objects.resize(vecAvgComp.size());
 774         std::transform(vecAvgComp.begin(), vecAvgComp.end(), objects.begin(), getRect());
 775         return;
 776     }
 777
 778     objects.clear();
 779
 780     Mat img = image, imgbuf(image.rows+1, image.cols+1, CV_8U);
 781
 782     if( img.channels() > 1 )
 783     {
 784         Mat temp;
 785         cvtColor(img, temp, CV_BGR2GRAY);
 786         img = temp;
 787     }
 788
 789     int maxNumThreads = 1;
 790 #ifdef _OPENMP
 791         maxNumThreads = omp_get_num_procs();
 792 #endif
 793
 794     vector<vector<Rect> > rects( maxNumThreads );
 795     vector<Rect>* rectsPtr = &rects[0];
 796     vector<Ptr<FeatureEvaluator> > fevals( maxNumThreads );
 797     fevals[0] = feval;
 798     Ptr<FeatureEvaluator>* fevalsPtr = &fevals[0];
 799
 800     for( double factor = 1; ; factor *= scaleFactor )
 801     {
 802         int stripCount, stripSize;
 803         Size winSize( cvRound(origWinSize.width*factor), cvRound(origWinSize.height*factor) );
 804         Size sz( cvRound( img.cols/factor ), cvRound( img.rows/factor ) );
 805         Size sz1( sz.width - origWinSize.width, sz.height - origWinSize.height );
 806
 807         if( sz1.width <= 0 || sz1.height <= 0 )
 808             break;
 809         if( winSize.width < minSize.width || winSize.height < minSize.height )
 810             continue;
 811
 812         int yStep = factor > 2. ? 1 : 2;
 813         if( maxNumThreads > 1 )
 814         {
 815             stripCount = max(min(sz1.height/yStep, maxNumThreads*3), 1);
 816             stripSize = (sz1.height + stripCount - 1)/stripCount;
 817             stripSize = (stripSize/yStep)*yStep;
 818         }
 819         else
 820         {
 821             stripCount = 1;
 822             stripSize = sz1.height;
 823         }
 824
 825         Mat img1( sz, CV_8U, imgbuf.data );
 826         resize( img, img1, sz, 0, 0, CV_INTER_LINEAR );
 827         if( !feval->setImage( img1, origWinSize ) )
 828             break;
 829         for( int i = 1; i < maxNumThreads; i++ )
 830             fevalsPtr[i] = feval->clone();
 831
 832 #ifdef _OPENMP
 833 #pragma omp parallel for num_threads(maxNumThreads) schedule(dynamic)
 834 #endif
 835         for( int i = 0; i < stripCount; i++ )
 836         {
 837                         int threadIdx = 0;
 838 #ifdef _OPENMP
 839                         threadIdx = omp_get_thread_num();
 840 #endif
 841             int y1 = i*stripSize, y2 = (i+1)*stripSize;
 842             if( i == stripCount - 1 || y2 > sz1.height )
 843                 y2 = sz1.height;
 844             Size ssz(sz1.width, y2 - y1);
 845
 846             for( int y = y1; y < y2; y += yStep )
 847                 for( int x = 0; x < ssz.width; x += yStep )
 848                 {
 849                     int r = runAt(fevalsPtr[threadIdx], Point(x,y));
 850                     if( r > 0 )
 851                         rectsPtr[threadIdx].push_back(Rect(cvRound(x*factor), cvRound(y*factor),
 852                                                winSize.width, winSize.height));
 853                     else if( r == 0 )
 854                         x += yStep;
 855                 }
 856         }
 857     }
 858     for( vector< vector<Rect> >::const_iterator it = rects.begin(); it != rects.end(); it++ )
 859         objects.insert( objects.end(), it->begin(), it->end() );
 860     groupRectangles( objects, minNeighbors, 0.2 );
 861 }
 862
 863
 864 bool CascadeClassifier::read(const FileNode& root)
 865 {
 866     // load stage params
 867     string stageTypeStr = (string)root[CC_STAGE_TYPE];
 868     if( stageTypeStr == CC_BOOST )
 869         stageType = BOOST;
 870     else
 871         return false;
 872
 873     string featureTypeStr = (string)root[CC_FEATURE_TYPE];
 874     if( featureTypeStr == CC_HAAR )
 875         featureType = FeatureEvaluator::HAAR;
 876     else if( featureTypeStr == CC_LBP )
 877         featureType = FeatureEvaluator::LBP;
 878     else
 879         return false;
 880
 881     origWinSize.width = (int)root[CC_WIDTH];
 882     origWinSize.height = (int)root[CC_HEIGHT];
 883     CV_Assert( origWinSize.height > 0 && origWinSize.width > 0 );
 884
 885     is_stump_based = (int)(root[CC_STAGE_PARAMS][CC_MAX_DEPTH]) == 1 ? true : false;
 886
 887     // load feature params
 888     FileNode fn = root[CC_FEATURE_PARAMS];
 889     if( fn.empty() )
 890         return false;
 891
 892     ncategories = fn[CC_MAX_CAT_COUNT];
 893     int subsetSize = (ncategories + 31)/32,
 894         nodeStep = 3 + ( ncategories>0 ? subsetSize : 1 );
 895
 896     // load stages
 897     fn = root[CC_STAGES];
 898     if( fn.empty() )
 899         return false;
 900
 901     stages.reserve(fn.size());
 902     classifiers.clear();
 903     nodes.clear();
 904
 905     FileNodeIterator it = fn.begin(), it_end = fn.end();
 906
 907     for( int si = 0; it != it_end; si++, ++it )
 908     {
 909         FileNode fns = *it;
 910         Stage stage;
 911         stage.threshold = fns[CC_STAGE_THRESHOLD];
 912         fns = fns[CC_WEAK_CLASSIFIERS];
 913         if(fns.empty())
 914             return false;
 915         stage.ntrees = (int)fns.size();
 916         stage.first = (int)classifiers.size();
 917         stages.push_back(stage);
 918         classifiers.reserve(stages[si].first + stages[si].ntrees);
 919
 920         FileNodeIterator it1 = fns.begin(), it1_end = fns.end();
 921         for( ; it1 != it1_end; ++it1 ) // weak trees
 922         {
 923             FileNode fnw = *it1;
 924             FileNode internalNodes = fnw[CC_INTERNAL_NODES];
 925             FileNode leafValues = fnw[CC_LEAF_VALUES];
 926             if( internalNodes.empty() || leafValues.empty() )
 927                 return false;
 928             DTree tree;
 929             tree.nodeCount = (int)internalNodes.size()/nodeStep;
 930             classifiers.push_back(tree);
 931
 932             nodes.reserve(nodes.size() + tree.nodeCount);
 933             leaves.reserve(leaves.size() + leafValues.size());
 934             if( subsetSize > 0 )
 935                 subsets.reserve(subsets.size() + tree.nodeCount*subsetSize);
 936
 937             FileNodeIterator it2 = internalNodes.begin(), it2_end = internalNodes.end();
 938
 939             for( ; it2 != it2_end; ) // nodes
 940             {
 941                 DTreeNode node;
 942                 node.left = (int)*it2; ++it2;
 943                 node.right = (int)*it2; ++it2;
 944                 node.featureIdx = (int)*it2; ++it2;
 945                 if( subsetSize > 0 )
 946                 {
 947                     for( int j = 0; j < subsetSize; j++, ++it2 )
 948                         subsets.push_back((int)*it2);
 949                     node.threshold = 0.f;
 950                 }
 951                 else
 952                 {
 953                     node.threshold = (float)*it2; ++it2;
 954                 }
 955                 nodes.push_back(node);
 956             }
 957
 958             it2 = leafValues.begin(), it2_end = leafValues.end();
 959
 960             for( ; it2 != it2_end; ++it2 ) // leaves
 961                 leaves.push_back((float)*it2);
 962         }
 963     }
 964
 965     // load features
 966     feval = FeatureEvaluator::create(featureType);
 967     fn = root[CC_FEATURES];
 968     if( fn.empty() )
 969         return false;
 970
 971     return feval->read(fn);
 972 }
 973
 974 } // namespace cv
 975
 976 /* End of file. */
 977