Indexing Billions of Images for Sketch-based Retrieval

Because of the popularity of touch-screen devices, it has be-
come a highly desirable feature to retrieve images from a
huge repository by matching with a hand-drawn sketch. Al-
though searching images via keywords or an example image
has been successfully launched in some commercial search
engines of billions of images, it is still very challenging for
both academia and industry to develop a sketch-based image
retrieval system on a billion-level database. In this work, we
systematically study this problem and try to build a sys-
tem to support query-by-sketch for two billion images. The
raw edge pixel and Chamfer matching are selected as the
basic representation and matching in this system, owning
to the superior performance compared with other methods
in extensive experiments. To get a more compact feature
and a faster matching, a vector-like Chamfer feature pair is
introduced, based on which the complex matching is refor-
mulated as the crossover dot-product of feature pairs. Based
on this new formulation, a compact shape code is developed
to represent each image/sketch by projecting the Chamfer
features to a linear subspace followed by a non-linear source
coding. Finally, the multi-probe Kmedoids-LSH is leveraged
to index database images, and the compact shape codes are
further used for fast reranking. Extensive experiments show
the effectiveness of the proposed features and algorithms in
building such a sketch-based image search system.