Girish Mahajan (Editor)

Cascade Learning Based on Adaboost

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

The Boosting Algorithms for Detector Cascade Learning is proposed by Mohammad Saberian and Nuno Vasconcelos in 2014, it is based on Viola–Jones object detection framework.

Contents

g 1 [ f 1 , f 2 ] ( x ) = f 1 ( x ) u [ f 1 ( x ) ] + u [ f 1 ( x ) ] f 2 ( x ) = { f 1 ( x ) if  f 1 ( x ) < 0 f 2 ( x ) if  f 1 ( x ) > 0

F k ( x ) = { f m ( x ) , k = m f k ( x ) u [ f k ( x ) ] + u [ f k ( x ) ] F k + 1 ( x ) , 1 k < m

g 2 [ f 1 , f 2 ] ( x ) = f 1 ( x ) u [ f 1 ( x ) ] + u [ f 1 ( x ) ] f 1 ( x ) f 2 ( x ) = { f 1 ( x ) if  f 1 ( x ) < 0 f 2 ( x ) f 1 ( x ) if  f 1 ( x ) > 0

F k ( x ) = { f m ( x ) , k = m f k ( x ) u [ f k ( x ) ] + u [ f k ( x ) ] f k ( x ) F k + 1 ( x ) , 1 k < m

L [ f ] = R E [ F ] + η R C [ F ]

Motivation of improvement

Paul Viola and Michael Jones propose great ideas in cascade learning classifier based on Ad- aboost. However, we can see, how to determine the number of stage in cascade classifier and the number of feature per stage to construct Adaboost classifier is hard to get. In Viola and Jones, Rapid Object Detection using a Boosted Cascade of Simple Features, just give a crude way to determine configuration: number of features in the first five layers of the detector is 1, 10, 25, 25 and 50 features respectively. The remaining layers have increasingly more features.

It is an important topic discussed in Boosting Algorithms for Detector Cascade Learning. In this work, they address the problem of automatically learning both the configuration and the stages of a high detection rate detector cascade. This is accomplished with the fast cascade boosting (FCBoost) algorithm, which is derived from a Lagrangian risk that trades-off detection performs and speed. FCBoost optimizes this risk with respect to a predictor that complies with the sequential decision making structure of the cascade architecture.

last-stage

The first family of cascade predictors that we consider is derived from the generator

g 1 [ f 1 , f 2 ] ( x ) = f 1 ( x ) u [ f 1 ( x ) ] + u [ f 1 ( x ) ] f 2 ( x ) = { f 1 ( x ) if  f 1 ( x ) < 0 f 2 ( x ) if  f 1 ( x ) > 0

The associated predictor recursion is

F k ( x ) = { f m ( x ) , k = m f k ( x ) u [ f k ( x ) ] + u [ f k ( x ) ] F k + 1 ( x ) , 1 k < m

Multiplicative cascades

The second family of cascade predictors has generator

g 2 [ f 1 , f 2 ] ( x ) = f 1 ( x ) u [ f 1 ( x ) ] + u [ f 1 ( x ) ] f 1 ( x ) f 2 ( x ) = { f 1 ( x ) if  f 1 ( x ) < 0 f 2 ( x ) f 1 ( x ) if  f 1 ( x ) > 0

The associated predictor recursion is

F k ( x ) = { f m ( x ) , k = m f k ( x ) u [ f k ( x ) ] + u [ f k ( x ) ] f k ( x ) F k + 1 ( x ) , 1 k < m

Learning the cascade configuration

This consists of determining the number of cascade stages and the number of weak learners per stage. In this work, they start by assuming that the number of cascade stages is known, and concentrate on the composition of theses stages. By minimizing Lagrangian risk to accomplish this goal, the Lagrangian risk is a trade-off about searching most accurate detector under a complexity constraint. Because more accurate detector, more complexity it has.

L [ f ] = R E [ F ] + η R C [ F ]

where F ( x ) and R E [ F ] are the cascade predictor and classification risk, We have assumed that the number of cascade stages is known at first. However this is usually not the case, there is a need for a procedure that learns this component of the cascade configuration. In the work, they adopt a greedy strategy, where cascade stages are added by the boosting algorithm itself, whenever this leads to a reduction of the risk. It is assumed that a new stage, or predictor g, can only be added at the end of the existing cascade. But it is often to meet problem that no update is taken, so they introduce the concept of neutral predictors.

The FCBoost algorithm

FCBoost is initialized with a neutral predictor. At each iteration, it finds the best update g k ( x ) (which a best weak learner for stage k) for each of the cascade stages and the best stage to add at the end of the cascade. It then selects the stage k whose update g k ( x ) most reduces the Lagrangian L[F]. If k is the newly added stage, a new stage is created and appended to the cascade. The only parameters are the multiplier η in Lagrange risk, which gives the relative importance of cascade speed and accuracy for the cascade designer.

From algorithm of FCBoost above, it can automatically determine both the cascade configuration(number of stages and number of weak learners per stage through iteration) and the predictor of each stage, so as to optimize the trade-off between detection accuracy and complex- ity through given parameter η.

The two cascade predictor(last-stage and multiplicative cascade) cover the two predominant cascade structures, first (last-stage) is the independent stage, i.e. stage predictors are designed independently(Viola and Jones, 2001). The second(multiplicative) is embedded stage where predictors of consecutive stages are related by

f k + 1 ( x ) = f k ( x ) = w ( x )

and w(x) is a single or linear combination of weak learners.

last-stage:

itr: 1) g1

itr: 2) g1 -> g1 + g2

itr: 3) g1 + g3 -> g1 + g2

itr: 4) g1 + g3 -> g1 + g2 -> g1 + g2 + g4

Multiplicative Cascades:

itr: 1) 1 + g1

itr: 2) 1 + g1 -> 1 + g2

itr: 3) 1 + g1 + g3 -> 1 + g2

itr: 4) 1 + g1 + g3 -> 1 + g2 -> 1 + g4

Conclusion

FCBoost is the new cascade boosting algorithm proposed by Saberian and Vasconcelos. It can determine cascade learning configuration automatically by just given a Lagrange multiplier η (which is relative importance of detect accurate and speed). And in algorithm, it is very efficient to implement and have good performances compared to original work.

References

Cascade Learning Based on Adaboost Wikipedia