Viola-Jones人脸检测--AdaptBoost特征选择

矫情吗；* 2022-01-09 15:34 357阅读 0赞

Viola-Jones人脸检测算法的伟大之处不不仅仅在于其算法的实时效果，更重要的是其提出了解决目标检测这一类问题的一种通用思路。该算法有两个亮点，一个是积分图技术，一个是Cascade训练模型，一经提出便引起了极大关注，在很多优秀的论文中都能看到他们的身影。如TLD算法中Detector部分，以及BING objectness训练时的两层SVM模型等，很难说这没有受到Viola-Jones算法的影响。下面就来介绍构成Cascade模型的其中的一个基本元素AdaptBoost吧。

AdaptBoost并不是Viola-Jones的原创算法，它是机器学习领域的产物，属于Ensemble Learning中boosting的类别。Ensemble类的学习算法分为bagging和boosting两个类别，都是基于弱分类器构造强分类器的思想，其中bagging的代表算法是RandomForests，boosting的代表算法是AdaptBoost。这里推荐一篇论文，介绍AdaptBoost算法理论的，《A Brief Introduction to Boosting》。

本着分享交流的目的，下面的内容包括对AdaptBoost算法的理论介绍及给出用标准C++实现AdaptBoost的代码。对于不想依赖特定库的伙伴们来说，标准C++的这个版本是个不错的选择。如果有什么不正确的地方，请多多指教。

1.AdaptBoost原理

我们知道对于一个给定窗口大小的图像，其Harr特征的维度是很高的，如果用直接用对训练样本计算出的Harr特征来训练分类器这是不太可行的，我们需要对高维的Harr特征进行选择，选择部分来进行分类器的训练。而AdaptBoost恰好就符合这样的思想，其基本思想是由弱分类器构造强分类器，用弱分类器的联合分类结果作为强分类器的结果。AdaptBoost的弱分类器可以是一个stump，也就是树桩的意思，就是一个弱分类器是一个二分类树。在众多维的Harr特征中进行特征选择的方法是，要求选择一个特征，及选择一个该特征下用于二分类的阈值，如果在该特征和阈值下对训练样本的分类误差最小，就以该特征和其二分类阈值作为一个训练好的弱分类器，算法的具体实现可以参看实现部分的bestStump（）接口。在每一次为弱分类器选择特征完成后，对于用于训练的样本的分布（也就是各样本的权重，初始值一般是相等的，都是1/N，N为样本个数）进行更新，每次的更新是由上一次的弱分类器的分类结果确定的，对于上一次弱分类器判断错误的样本，其权重会增大，判断正确的样本其权重会减小。AdaptBoost与RandomForest的一个区别是，在计算强分类器的结果时，AdaptBoost的弱分类器的权重是不一样的，而RandomForest的弱分类器的权重是相等的。

AdaptBoost算法的伪代码描述如下：

wKioL1U7gcji6QY0AAD7nu0zyTE143.jpg

2.标准C++实现

下面的这个接口部分，包含train的接口不包含test的部分，你可以在这个基础上增加test的接口部分。

  1. #ifndef _ADAPTBOOST_H_
  2. #define _ADAPTBOOST_H_
  3. #include <vector>
  4. #include <utility>
  5. #include <cmath>
  6. using namespace std;
  9. /**
  10.  * @brief decision stump declaration
  11.  *
  12.  * @param featureIndex
  13.  * @param weightedError achieved weighted error
  14.  * @param threshold
  15.  * @param margin achieved margin
  16.  * @param toggle +1 or -1
  17.  */
  18. struct StumpRule{
  19.     int featureIndex;
  20.     long double weightedError;
  21.     double threshold;
  22.     float margin;
  23.     int toggle;
  24. };
  27. /**
  28. 　* @brief what's inside AdaptBoost
  29. 　*
  30. 　* @param nPositives number of positive examples
  31. 　* @param nNegatives number of negative examples
  32. 　* @param initialPositiveWeight how much weight we give to positives at the outset
  33. 　* @param ascendingFeatures for each feature, we have (float feature value, int exampleIndex)
  34. 　*
  35. 　* @param sampleCount nPositives + nNegatives
  36. 　* @param inTrain is this a training set or a validation set
  37. 　* @param exponentialRisk exponential risk for training set
  38. 　* @param positiveTotalWeight total weight received by positive examples currently 
  39. 　* @param negativeTotalWeight total weight received by negative examples currently
  40. 　* @param minWeight minimum weight among all weights currently
  41. 　* @param maxWeight maximum weight among all weights currently
  42. 　* @param weights weight vector for all examples involved
  43. 　* @param labels are they positive or negative examples
  44. 　* @param featureCount how many features are there
  45. 　* @param committee what's the learned committee
  46. 　*/
  47. class AdaptBoost{
  48. private:
  50.     int nPositives;
  51.     int nNegatives;
  52.     long double initialPositiveWeight;
  53.     vector< vector<pair<float, int>> > ascendingFeatures;
  55.     int sampleCount;
  56.     int featureCount;
  57.     long double positiveTotalWeight;
  58.     long double negativeTotalWeight;
  59.     long double minWeight;
  60.     long double maxWeight;
  61.     long double exponentialRisk;
  62.     vector<double> weights;
  63.     vector<int> labels;
  64.     vector<StumpRule> committee;
  66.     /**
  67.      * @brief prevent copy and assignment 
  68.      */
  69.     AdaptBoost(const AdaptBoost&);
  70.     AdaptBoost operator=(const AdaptBoost&);
  72. protected:
  73.     /**
  74.      * @brief return for an element pointed by iterator and featureIndex its exampleIndex
  75.      */
  76.     int getTrainingExampleIndex(int featureIndex, int iterator);
  78.     /**
  79.      * @brief return for an element pointed by iterator and featureIndex its example value
  80.      */
  81.     float getTrainingExampleFeature(int featureIndex, int iterator);
  83.     /**
  84.      * @brief sort each featrue from different samples
  85.      */
  86.     void sortFeatures(
  87.         vector< vector<pair<float, int>> >& features
  88.     );
  90.     /**
  91.      * @brief best stump given a feature
  92.      */
  93.     void decisionStump(
  94.         int featureIndex
  95.     ,     StumpRule & best
  96.     );
  98.     /**
  99.      * @brief best stump among all features
  100.      */
  101.     StumpRule bestStump();
  103. public:
  104.     /**
  105.      * @brief constructor
  106.      * @param nPositives number of positives for training examples
  107.      * @param nNegatives number of negatives for training examples
  108.      * @param initialPositiveWeight initial weight of positives
  109.      * @param data for training examples, positves front and negatives back
  110.      */
  111.     AdaptBoost(
  112.         int nPositives
  113.     ,    int nNegatives
  114.     ,    long double initialPositiveWeight
  115.     ,    const vector< vector<float> >& data
  116.     );
  118.     /**
  119.      * @brief destructor
  120.      */
  121.     ~AdaptBoost();
  123.     /**
  124.      * @brief perform one round of adaboost
  125.      */
  126.     void oneRoundOfAdaboostTraining();
  128.     /**
  129.      * @brief get committee adaptboost trained
  130.      */
  131.     vector<StumpRule> getCommittee() {
  132.         return committee;
  133.     }
  135.     /**
  136.      * @brief get committee size
  137.      */
  138.     int getCommitteeSize() {
  139.         return committee.size();
  140.     }
  142.     /**
  143.      * @brief given the number of weak classifiers train for a committee
  144.      * @param numOfWeakClassifier for number of weak classifiers of adapt boost
  145.      */
  146.     void adaptBoostTraining(int numOfWeakClassifier);
  148.     /**
  149.      * @brief evaluate how the committee fares on a training dataset
  150.      *
  151.      * @param tweak for predictLableOfTrainingExamples
  152.      * @return falsePositive
  153.      * @return detectionRate
  154.      * @vector<int> return a blackList,if element of balckList is 0, then it means that
  155.      *  this sample could be used again otherwise it means not usable
  156.      */
  157.     vector<int> calcEmpiricalErrorInAdaBoostTraining(
  158.         float tweak
  159.     ,    float & falsePositive
  160.     ,    float & detectionRate
  161.     );
  163.     /**
  164.      * @brief given a tweak and a committe, what prediction do you make as to the training examples
  165.      *
  166.      * @param thresholdTweak tweak
  167.      * @return prediction
  168.      * @param onlyMostRecent use all the committee or its most recent member (a weak learner)
  169.      */
  170.     void predictLabelOfTrainingExamples(
  171.         float tweakThreshold
  172.     ,     vector<int> & prediction
  173.     ,     bool onlyMostRecent=false
  174.     );
  176. };
  179. #endif
  181. #include <cassert>
  182. #include <algorithm>
  183. #include <iostream>
  184. #include <iomanip>
  185. #include "VJAdaptBoost.h"
  187. using namespace std;
  188. #define VERBOSE true
  190. //fail and messaging
  191. static void fail(const char* message){
  192.     cerr << "Error:" <<  message << endl;
  193.     exit(EXIT_FAILURE);
  194. }
  195. //order definition for this type of pairs
  196. //compare only the feature values
  197. static bool myPairOrder(
  198.     const pair<float, int>& one
  199. ,    const pair<float, int>& other
  200. ){
  201.     return one.first < other.first;
  202. }
  203. //why is one stump better than the other
  204. static bool myStumpOrder(
  205.     const StumpRule & one
  206. ,    const StumpRule & other
  207. ){
  208.     if(one.weightedError < other.weightedError)
  209.         return true;
  210.     if(one.weightedError == other.weightedError && one.margin > other.margin)
  211.         return true;
  212.     return false;
  213. }
  215. int AdaptBoost::getTrainingExampleIndex(int featureIndex, int iterator){
  216.     assert(ascendingFeatures.size() > 0 && ascendingFeatures[0].size() >0);
  218.     return ascendingFeatures[featureIndex][iterator].second;
  219. }
  221. float AdaptBoost::getTrainingExampleFeature(int featureIndex, int iterator){
  222.     assert(ascendingFeatures.size() > 0 && ascendingFeatures[0].size() >0);
  224.     if(_isnan(ascendingFeatures[featureIndex][iterator].first)){
  225.         cerr<<"ERROR: nan feature "<<featureIndex<<" detected for example "<<getTrainingExampleIndex(featureIndex, iterator)<<endl;
  226.         exit(EXIT_FAILURE);
  227.     }
  228.     return ascendingFeatures[featureIndex][iterator].first;
  229. }
  231. //constructor
  232. AdaptBoost::AdaptBoost(
  233.     int positives
  234. ,    int negatives
  235. ,    long double positiveWeight
  236. ,    const vector< vector<float> >& data) {
  237.     assert(positives > 0 && negatives > 0);
  238.     assert(positiveWeight > 0 && positiveWeight < 1);
  239.     assert(data.size() > 0 && data[0].size() > 0 );
  240.     assert(data.size() == (positives + negatives));
  242.     //add number of data info to features
  243.     vector< vector<pair<float, int>> > features(data.size(), vector<pair<float, int>>(data[0].size(), pair<float, int>(0,0)));
  244.     for(int i=0; i<features.size(); i++) {
  245.         for(int j=0; j<features[0].size(); j++) {
  246.             features[i][j] = pair<float, int>(data[i][j], i);
  247.         }
  248.     }
  250.     //initialize the class attributes for the training set
  251.     nPositives = positives;
  252.     nNegatives = negatives;
  253.     initialPositiveWeight = positiveWeight;
  254.     sortFeatures(features);//initialize ascendingFeatures
  256.     sampleCount = positives + negatives;
  257.     featureCount = ascendingFeatures.size();
  258.     positiveTotalWeight = positiveWeight;
  259.     negativeTotalWeight = 1 - positiveWeight;
  260.     long double posAverageWeight = positiveTotalWeight/(long double)nPositives;
  261.     long double negAverageWeight = negativeTotalWeight/(long double)nNegatives;
  262.     maxWeight = max(posAverageWeight, negAverageWeight);
  263.     minWeight = min(posAverageWeight, negAverageWeight);
  264.     exponentialRisk = 1;
  266.     //set weights for each example
  267.     for(int exampleIndex = 0; exampleIndex < sampleCount; exampleIndex++){
  268.         weights.push_back(exampleIndex < nPositives ? posAverageWeight : negAverageWeight);
  269.         labels.push_back(exampleIndex < nPositives ? 1 : -1);
  270.     }
  272. }
  274. //destructor
  275. AdaptBoost::~AdaptBoost() {
  277. }
  279. //adaptBoost interface for training
  280. void AdaptBoost::adaptBoostTraining(int numOfWeakClassifier) {
  281.     assert(numOfWeakClassifier > 0);
  282.     for(int i=0; i<numOfWeakClassifier; i++) {
  283.         oneRoundOfAdaboostTraining();
  284.     }
  285. }
  287. //validation procedure using training examples
  288. vector<int> AdaptBoost::calcEmpiricalErrorInAdaBoostTraining(
  289.     float tweak
  290. ,    float & falsePositive
  291. ,    float & detectionRate
  292. ){
  293.     vector<int> blackList;
  294.     blackList.resize(nPositives, 0);
  295.     blackList.resize(nPositives+nNegatives, 1);
  297.     int nFalsePositive = 0;
  298.     int nFalseNegative = 0;
  300.     //initially let all be positive
  301.     vector<int> prediction;
  302.     prediction.resize(sampleCount,0);
  303.     predictLabelOfTrainingExamples(tweak, prediction, false);
  305.     //evaluate prediction errors
  306.     vector<int> agree(sampleCount);
  307.     for(int i=0; i<sampleCount; i++) {
  308.         agree[i] = labels[i]*prediction[i];
  309.     }
  310.     for(int exampleIndex = 0; exampleIndex < sampleCount; exampleIndex++){
  311.         if(agree[exampleIndex] < 0)     {
  312.             if(exampleIndex < nPositives){
  313.                 nFalseNegative += 1;
  314.                 blackList[exampleIndex] = 1;
  315.             }else{
  316.                 nFalsePositive += 1;
  317.                 blackList[exampleIndex] = 0;
  318.             }
  319.         }
  320.     }
  322.     //set the returned values
  323.     falsePositive = nFalsePositive/(float)nNegatives;
  324.     detectionRate = 1 - nFalseNegative/(float)nPositives;
  326.     return blackList;
  327. }
  329. //given a tweak and a committe, what prediction does it make as to the training examples
  330. void AdaptBoost::predictLabelOfTrainingExamples(
  331.     float tweakThreshold
  332. ,    vector<int> & prediction
  333. ,    bool onlyMostRecent
  334. ){
  335.     int committeeSize = committee.size();
  336.     //no need to weigh a single member's decision
  337.     onlyMostRecent = committeeSize == 1 ? true : onlyMostRecent;
  338.     int start = onlyMostRecent ? committeeSize - 1 : 0;
  339.     //double to be more precise
  340.     vector<vector<double>> memberVerdict;
  341.     for(int i=0; i<committeeSize; i++) {//initialize memberVerdict
  342.         vector<double> row(sampleCount);
  343.         memberVerdict.push_back(row);
  344.     }
  345.     vector<double> memberWeight(committeeSize);
  346.     //members, go ahead
  347.     for(int member = start; member < committeeSize; member++){
  348.         //sanity check
  349.         if(committee[member].weightedError == 0 && member != 0)
  350.             fail("Boosting Error Occured!");
  351.         //0.5 does not count here
  352.         //if member's weightedError is zero, member weight is nan, but it won't be used anyway
  353.         memberWeight[member] = log(1./committee[member].weightedError -1);
  354.         int feature = committee[member].featureIndex;
  355.         #pragma omp parallel for schedule(static)
  356.         for(int iterator = 0; iterator < sampleCount; iterator++){
  357.             int exampleIndex = getTrainingExampleIndex(feature, iterator);
  358.             memberVerdict[member][exampleIndex] = (getTrainingExampleFeature(feature, iterator) >
  359.                 committee[member].threshold ? 1 : -1)*committee[member].toggle + tweakThreshold;
  360.         }
  361.     }
  362.     //joint session
  363.     if(!onlyMostRecent){
  364.         vector<double> finalVerdict(sampleCount);
  365.         for(int i=0; i<sampleCount; i++) {
  366.             double predict = 0;
  367.             for(int j=0; j<committeeSize; j++) {
  368.                 predict += (memberWeight[j] * memberVerdict[j][i]);
  369.             }
  370.             finalVerdict[i] = predict;
  371.         }
  372.         for(int exampleIndex = 0; exampleIndex < sampleCount; exampleIndex++)
  373.             prediction[exampleIndex] = finalVerdict[exampleIndex] > 0 ? 1 : -1;
  374.     }else{
  375.         for(int exampleIndex = 0; exampleIndex < sampleCount; exampleIndex++)
  376.             prediction[exampleIndex] = memberVerdict[start][exampleIndex] > 0 ? 1 : -1;
  377.     }
  378. }
  380. void AdaptBoost::oneRoundOfAdaboostTraining(){
  381.     //try to be friendly here
  382.     static int trainPhase = 0;
  383.     if(VERBOSE && trainPhase == 0){
  384.         cout << "\n#############################ADABOOST MESSAGE EXPLAINED####################################################\n\n";
  385.         cout << "INFO: Adaboost starts. Exponential Risk is expected to go down steadily and strictly," << endl;
  386.         cout << "INFO: and Exponential Risk should bound the (weighted) Empirical Error from above." << endl;
  387.         cout << "INFO: Train Phase is the current boosting iteration." << endl;
  388.         cout << "INFO: Best Feature is the most discriminative feature selected by decision stump at this iteration." << endl;
  389.         cout << "INFO: Threshold and Toggle are two parameters that define a real valued decision stump.\n" << endl;
  390.     }
  391.     trainPhase++;
  393.     //get and store the rule
  394.     StumpRule rule = bestStump();
  395.     committee.push_back(rule);
  397.     //how it fares
  398.     vector<int> prediction(sampleCount);
  399.     predictLabelOfTrainingExamples(
  400.         0
  401.     ,    prediction
  402.     ,    /*onlyMostRecent*/ true);
  403.     vector<bool> agree(sampleCount);
  404.     for(int i=0; i<sampleCount; i++) {
  405.         if(prediction[i] == labels[i]) {
  406.             agree[i] = true;
  407.         }else {
  408.             agree[i] = false;
  409.         }
  410.     }
  412.     //update weights
  413.     vector<double> weightUpdate;
  414.     weightUpdate.resize(sampleCount,1);
  415.     bool errorFlag = false;
  416.     for(int exampleIndex = 0; exampleIndex < sampleCount; exampleIndex++){
  417.         //more weight for a difficult example
  418.         if(!agree[exampleIndex]){
  419.             weightUpdate[exampleIndex] = 1/rule.weightedError - 1;
  420.             errorFlag = true;
  421.         }
  422.     }
  424.     //update weights only if there is an error
  425.     if(errorFlag){
  426.         double weightSum = 0;
  427.         for(int i=0; i<sampleCount; i++) {
  428.             weights[i] *= weightUpdate[i];
  429.             weightSum += weights[i];
  430.         }
  431.         for(int i=0; i<sampleCount; i++) {
  432.             weights[i] /= weightSum;
  433.         }
  435.         double posTotalWeight = 0;
  436.         for(int i=0; i<nPositives; i++) {
  437.             posTotalWeight += weights[i];
  438.         }
  439.         positiveTotalWeight = posTotalWeight;
  440.         negativeTotalWeight = 1-positiveTotalWeight;
  442.         double min,max;
  443.         min = max = weights[0];
  444.         for(int i=0; i<sampleCount; i++) {
  445.             if(weights[i] < min) {
  446.                 min = weights[i];
  447.             }else if(weights[i] > max) {
  448.                 max = weights[i];
  449.             }
  450.         }
  451.         minWeight = min;
  452.         maxWeight = max;
  453.     }
  455.     //exponentialRisk can be zero at the first boosting
  456.     exponentialRisk *= 2*sqrt((1-rule.weightedError)*rule.weightedError);
  458.     //print some statistics
  459.     if(VERBOSE){
  460.         float tweak = 0;
  461.         float falsePositive = 0;
  462.         float detectionRate = 0;
  463.         calcEmpiricalErrorInAdaBoostTraining(tweak, falsePositive, detectionRate);
  464.         float empError = static_cast<float>(falsePositive*(1-initialPositiveWeight)+initialPositiveWeight*(1-detectionRate));
  465.         cout << "Training Performance Explanation (before threshold tweaking): falsePositive " << falsePositive 
  466.              << " detectionRate " << detectionRate << endl;
  467.         cout <<"###########################################################################################################\n";
  468.         cout << "\nTrain Phase " << trainPhase << endl << endl;
  469. //        whatFeature(rule.featureIndex);
  470.         cout << "\tExponential Risk " << setw(12) << exponentialRisk << setw(19) << "Weighted Error " 
  471.              << setw(11) << rule.weightedError << setw(14) << "Threshold " << setw(10) << rule.threshold 
  472.              << setw(13) <<"Toggle " << setw(12) << rule.toggle <<  endl;
  473.         cout << "\tPositive Weight" << setw(14) << positiveTotalWeight << setw(14) << "MinWeight " 
  474.              << setw(16) << minWeight << setw(14) << "MaxWeight " << setw(10) << maxWeight << setw(22) 
  475.              << "Empirical Error " << setw(10) << empError << endl << endl;
  476.     }
  477. }
  479. //get a feature from features and put them in ascending order
  480. //and record at the same time the permuted example order
  481. void AdaptBoost::sortFeatures(vector< vector<pair<float, int>> >& features) {
  482.     assert(features.size()!=0 && features[0].size() !=0 );
  484.     for(unsigned int i=0; i<features[0].size(); i++) {
  485.         vector<pair<float, int>> temp = vector<pair<float, int>>();
  486.         for(unsigned int j=0; j<features.size(); j++) {
  487.             temp.push_back(features[j][i]);
  488.         }
  489.         //sort
  490.         sort(temp.begin(), temp.end(), myPairOrder);
  491.         ascendingFeatures.push_back(temp);
  492.     }
  494. }
  497. //base learner is a stump, a decision tree of depth 1
  498. //decisionStump has to look at feature and return rule
  499. void AdaptBoost::decisionStump(
  500.     int featureIndex
  501. ,    StumpRule & best
  502. ){
  503.     //a stump is determined by threshold and toggle, the other two attributes measures its performance
  504.     //initialize with some crazy values
  505.     best.featureIndex = featureIndex;
  506.     best.weightedError = 2;
  507.     best.threshold = getTrainingExampleFeature(featureIndex, 0) - 1;
  508.     best.margin = -1;
  509.     best.toggle = 0;
  511.     StumpRule current = best;
  513.     //error_p and error_n allow to set the best toggle
  514.     long double error_p, error_n;
  516.     //initialize: r denotes right hand side and l left hand side
  517.     //convention: in TrainExamples nPositives positive samples are followed by negatives samples
  518.     long double rPositiveWeight = positiveTotalWeight;
  519.     long double rNegativeWeight = negativeTotalWeight;
  520.     //yes, nothing to the left of the sample with the smallest feature
  521.     long double lPositiveWeight = 0;
  522.     long double lNegativeWeight = 0;
  524.     //go through all these observations one after another
  525.     int iterator = -1;
  527.     //to build a decision stump, you need a toggle and an admissible threshold
  528.     //which doesn't coincide with any of the observations
  529.     while(true){
  531.         //We've got a threshold. So determine the best toggle based on two types of error
  532.         //toggle = 1, positive prediction if and only if the observed feature > the threshold
  533.         //toggle = -1, positive prediction if and only if the observed feature < the threshold
  535.         //error_p denotes the error introduced by toggle = 1, error_n the error by toggle = -1
  536.         error_p = rNegativeWeight + lPositiveWeight;
  537.         error_n = rPositiveWeight + lNegativeWeight;
  538.         current.toggle = error_p < error_n ? 1 : -1;
  540.         //sometimes shit happens, prevent error from being negative
  541.         long double smallerError = min(error_p, error_n);
  542.         //this prevents some spurious nonzero: for currentError must be at least equal to minWeight
  543.         current.weightedError = smallerError < minWeight * 0.9 ? 0 : smallerError;
  545.         //update if necessary
  546.         if(myStumpOrder(current, best))
  547.             best = current;
  549.         //move on
  550.         iterator++;
  552.         //we don't actually need to look at the sample with the largest feature
  553.         //because its rule is exactly equivalent to those produced
  554.         //by the sample with the smallest feature on training observations
  555.         //but it won't do any harm anyway
  556.         if(iterator == sampleCount)
  557.             break;
  559.         //handle duplicates, update lr weights and find a new threshold
  560.         while(true){
  562.             //take this guy's attributes
  563.             int exampleIndex = getTrainingExampleIndex(featureIndex, iterator);
  564.             int label = labels[exampleIndex];
  565.             long double weight = weights[exampleIndex];
  567.             //update weights
  568.             if(label < 0){
  569.                 lNegativeWeight += weight;
  570.                 rNegativeWeight -= weight;
  571.             }else{
  572.                 lPositiveWeight += weight;
  573.                 rPositiveWeight -= weight;
  574.             }
  576.             //if a new threshold can be found, break
  577.             //two cases are possible: either it is the last observation
  578.             if(iterator == sampleCount - 1)
  579.                 break;
  580.             //or no duplicate. If there is a duplicate, repeat
  581.             if(getTrainingExampleFeature(featureIndex, iterator) != getTrainingExampleFeature(featureIndex, iterator + 1)){
  582.                 double test = ((double)getTrainingExampleFeature(featureIndex, iterator) 
  583.                     + (double)getTrainingExampleFeature(featureIndex, iterator + 1))/2;
  584.                 //well that's a bit frustrating: I want to keep float because of memory constraint, but apparently
  585.                 //features are so close, sometimes, numerical precision arises as an unexpected problem, so I decide
  586.                 //to use a double threshold so as to separate float features
  587.                 if(getTrainingExampleFeature(featureIndex, iterator) < test && test < getTrainingExampleFeature(featureIndex, iterator + 1))
  588.                     break;
  589.                 else{
  590.                     #pragma omp critical
  591.                     {
  592.                         cout << "ERROR: numerical precision breached: problem feature values " 
  593.                              << getTrainingExampleFeature(featureIndex, iterator) 
  594.                              << " : " << getTrainingExampleFeature(featureIndex, iterator+1) 
  595.                              << ". Problem feature " << featureIndex << " and problem example " 
  596.                              << getTrainingExampleIndex(featureIndex, iterator) << " : " 
  597.                              << getTrainingExampleIndex(featureIndex, iterator+1) << endl;
  598.                     }
  599.                     fail("fail to find a suitable threshold.");
  600.                 }
  601.             }
  602.             iterator++;
  603.         }
  605.         //update threshold
  606.         if(iterator < sampleCount - 1){
  607.             current.threshold = ((double)getTrainingExampleFeature(featureIndex, iterator) 
  608.                 + (double)getTrainingExampleFeature(featureIndex, iterator + 1))/2;
  609.             current.margin = getTrainingExampleFeature(featureIndex, iterator + 1) - getTrainingExampleFeature(featureIndex, iterator);
  610.         }else{
  611.             //slightly to the right of the biggest observation
  612.             current.threshold = getTrainingExampleFeature(featureIndex, iterator) + 1;
  613.             current.margin = 0;
  614.         }
  615.     }
  617. }
  619. //implement the feature selection's outer loop
  620. //return the most discriminative feature and its rule
  621. StumpRule AdaptBoost::bestStump(
  622. ){
  623.     vector<StumpRule> candidates;
  624.     candidates.resize(featureCount);
  625.     #pragma omp parallel for schedule(static)
  626.     for(int featureIndex = 0; featureIndex < featureCount; featureIndex++)
  627.         decisionStump(featureIndex, candidates[featureIndex]);
  629.     //loop over all the features
  630.     //the best rule has the smallest weighted error and the largest margin
  631.     StumpRule best = candidates[0];
  632.     for(int featureIndex = 1; featureIndex < featureCount; featureIndex++){
  633.         if(myStumpOrder(candidates[featureIndex], best))
  634.             best = candidates[featureIndex];
  635.     }
  637.     //if shit happens, tell me
  638.     if( best.weightedError >= 0.5 )
  639.         fail("Decision Stump failed: base error >= 0.5");
  641.     //return
  642.     return best;
  643. }

reference：

Yi-Qing Wang, An Analysis of the Viola-Jones Face Detection Algorithm, IPOL.

转载于:https://blog.51cto.com/remyspot/1638356

发表评论

表情：
评论列表 （有 0 条评论，357人围观）

还没有评论，来说两句吧...

相关阅读

    相关 人脸特征检测--基于DLIB库

    　　Dlib是一个C++编写的工具包，它包含了机器学习算法以及一些用来解决现实复杂问题的工具，可以广泛应用于机器人、嵌入式设备、手机，甚至高性能计算中，可以在其官网了解更多。这

    港控/mmm°港控/mmm°/ 0 赞/ 132 阅读

    相关 特征选择_过滤特征选择

    一：方差选择法： 使用方差作为特征评分标准，如果某个特征的取值差异不大，通常认为该特征对区分样本的贡献度不大 因此在构造特征过程中去掉方差小于阈值特征 f

    野性酷女野性酷女/ 0 赞/ 374 阅读