Wavelet Frame Accelerated Reduced
Matthias Rätsch, Gerd Teschke, Sami Romdhani, Thomas R. Vetter · 2008
Inthispaper,anovelmethodforreducingtheruntime complexity of a support vector machine classifier is presented. The new training algorithm is fast and simple. This is achieved by an over-complete wavelet transform that finds the optimal approxi- mation of the support vectors.The presented derivationshowsthat the wavelet theory provides an upper bound on the distance be- tween the decision function of the support vector machine and our classifier. The obtained classifier is fast, since a Haar wavelet ap- proximation of the support vectors is used, enabling efficient in- tegral image-based kernel evaluations. This provides a set of cas- caded classifiers of increasing complexity for an early rejection of vectorseasyto discriminate. Thisexcellent runtimeperformanceis achieved by using a hierarchical evaluation over the number of in- corporated and additional over the approximation accuracy of the reduced set vectors. Here, this algorithm is applied to the problem of face detection, but it can also be used for other image-based clas- sifications. The algorithm presented, provides a 530-fold speedup over the support vector machine, enabling face detection at more than 25 fps on a standard PC.