Computational Complexity Reduction of the Support Vector Machine Classifiers for Image Analysis Tasks Through the Use of the Discrete Cosine Transform

摘要

Support vector machines (SVMs) are powerful classifiers, with very good recognition rates in image analysis tasks. However their computational time in the object recognition phase is often large due to the number of classifications per scene and to the feature vector size, especially when the feature space is formed from raw image data. Several methods are reported in the literature to make the classification faster, as selecting only the most significant support vectors or reducing the feature vector length by image transforms (Wavelets, PCA) prior to SVM training and classification. The method we propose is different in principle. Instead of applying the transform prior to training and thus changing the representation space, we only perform a unitary orthogonal real transform in the classification phase on the resulting support vectors and on the pattern to be classified. As the inverse matrices of these transforms are exactly the transposed of the transform matrices, we mathematically prove that the dot product of any two vectors has the same expression in the original and the transformed space. This, combined with the energy compaction property of a suitable transform, leads to a faster computation of the dot products, if the transform has a fast implementation algorithm. We use the discrete cosine transform (DCT) due to its good energy compaction on digital images. Our first experiments on a face recognition application are promising: at the same recognition rate, our algorithm leads to an average 30% reduction in the number of elementary operations per classification.