1. A computer-readable storage medium that stores program instructions computer-executable to implement: receiving a plurality of feature descriptors for a plurality of images, wherein each feature descriptor encodes a respective feature in an image, and wherein each feature descriptor is transformed into a plurality of sub-descriptors in accordance with a specified transformation scheme, wherein the feature descriptors correspond to an image feature descriptor space for the plurality of images, wherein the sub-descriptors correspond to a plurality of subspaces of the image feature descriptor space, and wherein the plurality of subspaces span the image feature descriptor space; and quantizing each subspace of the plurality of subspaces using cluster analysis applied to the sub-descriptors, thereby determining a respective one or more feature primitives for each subspace, wherein the feature primitives are useable to characterize image features.