Wavelet frame accelerated reduced support vector machines.
In this paper, a novel method for reducing the runtime 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 approximation of the support vectors. The presented derivation shows that the wavelet theory provides an upper bound on the distance between the decision function of the support vector machine and our classifier. The obtained classifier is fast, since a Haar wavelet approximation of the support vectors is used, enabling efficient integral image-based kernel evaluations. This provides a set of cascaded classifiers of increasing complexity for an early rejection of vectors easy to discriminate. This excellent runtime performance is achieved by using a hierarchical evaluation over the number of incorporated 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 classifications. 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.
Ratsch
Matthias
M
Computer Science Department, University of Basel, Bernoullistrasse 16, CH-4057 Basel, Switzerland. matthias.raetsch@unibas.ch
Teschke
Gerd
G
Romdhani
Sami
S
Vetter
Thomas
T
D000465:Algorithms; D001185:Artificial Intelligence; D001699:Biometry / Q000379:methods*; D005145:Face / Q000033:anatomy & histology*; D006801:Humans; D007089:Image Enhancement / Q000379:methods*; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D012815:Signal Processing, Computer-Assisted