Branch-and-Bound Search for Training Cascades of Classifiers

We propose a general algorithm that treats cascade training as a tree search process working according to the branch-and-bound technique. The algorithm allows to reduce the expected number of features used by an operating cascade—a key quantity we focus on in the paper. While searching, we observe suitable lower bounds on partial expectations and prune tree branches that cannot improve the best-so-far result. Both exact and approximate variants of the approach are formulated. Experiments pertain to cascades trained to be face or letter detectors with Haar-like features or Zernike moments being the input information, respectively. Results confirm shorter operating times of cascades obtained owing to the reduction in the number of extracted features.