Abstract: Current state-of-the-art image categorization systems rely on bag-of-words representations that model image content as a histogram of quantization indices that code local image appearance. In this context, randomized tree-structured quantizers have been shown to be both computationally efficient and yielding discriminative visual words for a given categorization task. This paper presents a new algorithm that builds tree-structured quantizers not to optimize patch classification but to directly optimize the image classification performance. This approach is experimentally validated on several challenging data sets for which it outperforms other patch quantizers such as standard decision trees or k-means.