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