Scalable classifiers for Internet vision tasks

Object recognition systems designed for Internet applications typically need to adapt to users' needs in a flexible fashion and scale up to very large data sets. In this paper we analyze the complexity of several multiclass SVM-based algorithms and highlight the computational bottleneck they suffer at test time: comparing the input image to every training image. We propose an algorithm that overcomes this bottleneck; it offers not only the efficiency of a simple nearest-neighbor classifier, by voting on class labels based on the k nearest neighbors quickly determined by a vocabulary tree, but also the recognition accuracy comparable to that of a complex SVM classifier, by incorporating SVM parameters into the voting scores incrementally accumulated from individual image features. Empirical results demonstrate that adjusting votes by relevant support vector weights can improve the recognition accuracy of a nearestneighbor classifier without sacrificing speed. Compared to existing methods, our algorithm achieves a ten-fold speed increase while incurring an acceptable accuracy loss that can be easily offset by showing about two more labels in the result. The speed, scalability, and adaptability of our algorithm makes it suitable for Internet vision applications.