A large part of computer vision centers around answering the question "Do these look the same?" Many successful approaches to computational visual recognition are based on collecting large numbers of examples of object categories and for new images, repeatedly asking whether the new image looks like any of the previously collected examples. This can be formalized in a kernelized support vector machine framework. Unfortunately such an approach for classification scales linearly with the amount of training data. In addition learning the support vector weights at training time can be even more expensive. We show for additive kernels, which have been successful in computer vision, that evaluating such classifiers can be done exponentially faster, independent of the amount of training data or support vectors. We also show how to train such classifiers very efficiently. All this allows us to use these more effective classifiers for large scale image retrieval and detection (where for instance a million sub-windows might be considered for every image) settings for which they had previously been prohibitively expensive.

Classification using Intersection Kernel Support Vector Machines is Efficient Subhransu Maji, Alexander C. Berg, Jitendra Malik CVPR 2008