Abstract The representation of local image patches is crucial for the good performance and effificiency of many vision tasks. Patch descriptors have been designed to generalize towards diverse variations, depending on the application, as well as the desired compromise between accuracy and effificiency. We present a novel formulation of patch description, that serves such issues well. Sparse quantization lies at its heart. This allows for effificient encodings, leading to powerful, novel binary descriptors, yet also to the generalization of existing descriptors like SIFT or BRIEF. We demonstrate the capabilities of our formulation for both keypoint matching and image classifification. Our binary descriptors achieve state-of-the-art results for two keypoint matching benchmarks, namely those by Brown [6] and Mikolajczyk [18]. For image classifification, we propose new descriptors that perform similar to SIFT on Caltech101 [10] and PASCAL VOC07 [9].